Context Navigation

← Previous Changeset
Next Changeset →

Changeset ef412e8a5380c00b588923cc5697d2ea5d55584e

Timestamp:

05/14/08 16:14:36 (8 months ago)

Author:

David Balmain <dbalmain@…>

Parents:

3021e363641eff71706f13f24f0d3775d2645bfd

Children:

b41949970248718694169a0b3308b006814802b9

git-committer:

David Balmain <dbalmain@gmail.com> / 2008-05-14T16:14:36Z+1000

Message:

Fixed a couple of bugs in bitvector.h

* bv_not wasn't setting bits above bv->size correctly
* bitvector scanning was overrunning the bitvector

Location:

Files:

: 6 modified

include/bitvector.h (modified) (3 diffs)
include/global.h (modified) (1 diff)
include/internal.h (modified) (12 diffs)
src/bitvector.c (modified) (3 diffs)
src/index.c (modified) (2 diffs)
test/test_bitvector.c (modified) (2 diffs)

Legend:

: Unmodified
: Added
: Removed

c/include/bitvector.h

r208885f	ref412e
279	279	/* Keep only the bits above this position */
280	280	word &= ~0 << (bit & 31);
281		if (word)
	281	if (word) {
282	282	goto done;
283
284		for (pos++; pos < (frt_u32)bv->size; ++pos)
285		{
286		if ( (word = bv->bits[pos]) )
287		goto done;
288		}
289		return -1;
	283	}
	284	else {
	285	frt_u32 word_size = FRT_TO_WORD(bv->size);
	286	for (pos++; pos < word_size; ++pos)
	287	{
	288	if ( (word = bv->bits[pos]) )
	289	goto done;
	290	}
	291	}
	292	return -1;
290	293	done:
291	294	return bv->curr_bit = (pos << 5) + frt_count_trailing_zeros(word);
…	…
326	329	/* Set all of the bits below this position */
327	330	word \|= (1 << (bit & 31)) - 1;
328		if (~word)
	331	if (~word) {
329	332	goto done;
330
331		for (pos++; pos < (frt_u32)bv->size; ++pos)
332		{
333		if ( ~(word = bv->bits[pos]) )
334		goto done;
	333	}
	334	else {
	335	frt_u32 word_size = FRT_TO_WORD(bv->size);
	336	for (pos++; pos < word_size; ++pos)
	337	{
	338	if ( ~(word = bv->bits[pos]) )
	339	goto done;
	340	}
335	341	}
336	342	return -1;
…	…
468	474	bv->bits[i] = ~(bv1->bits[i]);
469	475
	476	memset(bv->bits + word_size, (bv->extends_as_ones ? 0xFF : 0),
	477	sizeof(frt_u32) * (bv->capa - word_size));
	478
470	479	frt_bv_recount(bv);
471	480	return bv;

c/include/global.h

r509f04	ref412e
71	71
72	72	#define FRT_ABS(n) ((n >= 0) ? n : -n)
73		#define FRT_TO_WORD(n) (((n) >> 5) + 1)
	73	#define FRT_TO_WORD(n) (((n - 1) >> 5) + 1)
74	74
75	75	#define FRT_RECAPA(self, len, capa, ptr, type) \

c/include/internal.h

r3021e3	ref412e
1	1	#ifndef FRT_INTERNAL_H
2	2	#define FRT_INTERNAL_H
3
4		~~#ifdef __cplusplus~~
5		~~extern "C" {~~
6		~~#endif~~
7	3
8	4	/* Constants */
…	…
15	11	#define ARY_INIT_CAPA FRT_ARY_INIT_CAPA
16	12	#define ARY_META_CNT FRT_ARY_META_CNT
	13	#define ATTR_ALWAYS_INLINE FRT_ATTR_ALWAYS_INLINE
	14	#define ATTR_CONST FRT_ATTR_CONST
	15	#define ATTR_MALLOC FRT_ATTR_MALLOC
	16	#define ATTR_PURE FRT_ATTR_PURE
17	17	#define BC_MUST FRT_BC_MUST
18	18	#define BC_MUST_NOT FRT_BC_MUST_NOT
…	…
23	23	#define BUFFER_SIZE FRT_BUFFER_SIZE
24	24	#define BV_INIT_CAPA FRT_BV_INIT_CAPA
	25	#define BV_OP FRT_BV_OP
25	26	#define BYTE_FIELD_INDEX_CLASS FRT_BYTE_FIELD_INDEX_CLASS
26	27	#define COMMIT_LOCK_NAME FRT_COMMIT_LOCK_NAME
…	…
43	44	#define EXPLANATION_DETAILS_START_SIZE FRT_EXPLANATION_DETAILS_START_SIZE
44	45	#define EXTENDED_ENGLISH_STOP_WORDS FRT_EXTENDED_ENGLISH_STOP_WORDS
	46	#define EXTERNC FRT_EXTERNC
45	47	#define FERRET_ERROR FRT_FERRET_ERROR
46	48	#define FILE_NOT_FOUND_ERROR FRT_FILE_NOT_FOUND_ERROR
…	…
172	174	#define TE_BUCKET_INIT_CAPA FRT_TE_BUCKET_INIT_CAPA
173	175	#define THREAD_ONCE_INIT FRT_THREAD_ONCE_INIT
	176	#define TO_WORD FRT_TO_WORD
174	177	#define TRY FRT_TRY
175	178	#define TV_FIELD_INIT_CAPA FRT_TV_FIELD_INIT_CAPA
…	…
183	186	#define WILD_CHAR FRT_WILD_CHAR
184	187	#define WILD_STRING FRT_WILD_STRING
185		~~#define WIN32_H FRT_WIN32_H~~
186	188	#define WRITE_LOCK_NAME FRT_WRITE_LOCK_NAME
187	189	#define XCATCHALL FRT_XCATCHALL
…	…
381	383	#define bq_new_max frt_bq_new_max
382	384	#define bv_and frt_bv_and
	385	#define bv_and_ext frt_bv_and_ext
	386	#define bv_and_i frt_bv_and_i
383	387	#define bv_and_x frt_bv_and_x
	388	#define bv_capa frt_bv_capa
384	389	#define bv_clear frt_bv_clear
385	390	#define bv_destroy frt_bv_destroy
…	…
390	395	#define bv_new_capa frt_bv_new_capa
391	396	#define bv_not frt_bv_not
	397	#define bv_not_i frt_bv_not_i
392	398	#define bv_not_x frt_bv_not_x
393	399	#define bv_or frt_bv_or
	400	#define bv_or_ext frt_bv_or_ext
	401	#define bv_or_i frt_bv_or_i
394	402	#define bv_or_x frt_bv_or_x
395	403	#define bv_recount frt_bv_recount
…	…
401	409	#define bv_set frt_bv_set
402	410	#define bv_set_fast frt_bv_set_fast
	411	#define bv_set_value frt_bv_set_value
403	412	#define bv_unset frt_bv_unset
404	413	#define bv_xor frt_bv_xor
	414	#define bv_xor_ext frt_bv_xor_ext
	415	#define bv_xor_i frt_bv_xor_i
405	416	#define bv_xor_x frt_bv_xor_x
406	417	#define byte2float frt_byte2float
…	…
410	421	#define co_create frt_co_create
411	422	#define co_hash_create frt_co_hash_create
	423	#define count_leading_ones frt_count_leading_ones
	424	#define count_leading_zeros frt_count_leading_zeros
	425	#define count_ones frt_count_ones
	426	#define count_trailing_ones frt_count_trailing_ones
	427	#define count_trailing_zeros frt_count_trailing_zeros
	428	#define count_zeros frt_count_zeros
412	429	#define csq_new frt_csq_new
413	430	#define csq_new_nr frt_csq_new_nr
…	…
787	804	#define register_for_cleanup frt_register_for_cleanup
788	805	#define rfilt_new frt_rfilt_new
	806	#define round2 frt_round2
789	807	#define rq_new frt_rq_new
790	808	#define rq_new_less frt_rq_new_less
…	…
983	1001	#define xraise frt_xraise
984	1002
985		~~#ifdef __cplusplus~~
986		~~} // extern "C"~~
987	1003	#endif
988
989		~~#endif~~

c/src/bitvector.c

r208885f	ref412e
9	9	/* The capacity passed by the user is number of bits allowed, however we
10	10	* store capacity as the number of words (U32) allocated. */
11		bv->capa = ~~(capa >> 5) + 1~~;
	11	bv->capa = max2(TO_WORD(capa), 4);
12	12	bv->bits = ALLOC_AND_ZERO_N(u32, bv->capa);
13	13	bv->curr_bit = -1;
…	…
44	44	int bv_eq(BitVector bv1, BitVector bv2)
45	45	{
46		if (bv1 == bv2)
	46	if (bv1 == bv2) {
47	47	return true;
	48	}
48	49
49		if (bv1->extends_as_ones != bv2->extends_as_ones)
	50	if (bv1->extends_as_ones != bv2->extends_as_ones) {
50	51	return false;
	52	}
51	53
52	54	u32 *bits = bv1->bits;
53	55	u32 *bits2 = bv2->bits;
54	56	int min_size = min2(bv1->size, bv2->size);
55		int word_size = ~~FRT_~~TO_WORD(min_size);
	57	int word_size = TO_WORD(min_size);
56	58	int ext_word_size = 0;
57	59	int i;
58	60
59	61	for (i = 0; i < word_size; i++) {
60		if (bits[i] != bits2[i])
	62	if (bits[i] != bits2[i]) {
61	63	return false;
	64	}
62	65	}
63	66	if (bv1->size > min_size) {
64	67	bits = bv1->bits;
65		ext_word_size = ~~FRT_~~TO_WORD(bv1->size);
	68	ext_word_size = TO_WORD(bv1->size);
66	69	}
67	70	else if (bv2->size > min_size) {
68	71	bits = bv2->bits;
69		ext_word_size = ~~FRT_~~TO_WORD(bv2->size);
	72	ext_word_size = TO_WORD(bv2->size);
70	73	}
71	74	if (ext_word_size) {
72	75	const u32 expected = (bv1->extends_as_ones ? 0xFFFFFFFF : 0);
73	76	for (i = word_size; i < ext_word_size; i++) {
74		if (bits[i] != expected)
	77	if (bits[i] != expected) {
75	78	return false;
	79	}
76	80	}
77	81	}
…	…
84	88	const u32 empty_word = bv->extends_as_ones ? 0xFFFFFFFF : 0;
85	89	int i;
86		for (i = ~~FRT_~~TO_WORD(bv->size) - 1; i >= 0; i--) {
	90	for (i = TO_WORD(bv->size) - 1; i >= 0; i--) {
87	91	const u32 word = bv->bits[i];
88	92	if (word != empty_word)

c/src/index.c

r76d73d	ref412e
4354	4354	OutStream *os = store->new_output(store, name);
4355	4355	os_write_vint(os, bv->size);
4356		for (i = (~~bv->size~~ >> 5); i >= 0; i--) {
	4356	for (i = ((bv->size-1) >> 5); i >= 0; i--) {
4357	4357	os_write_u32(os, bv->bits[i]);
4358	4358	}
…	…
4371	4371	bv->ref_cnt = 1;
4372	4372	TRY
4373		for (i = (~~bv->size~~ >> 5); i >= 0; i--) {
	4373	for (i = ((bv->size-1) >> 5); i >= 0; i--) {
4374	4374	bv->bits[i] = is_read_u32(is);
4375	4375	}

c/test/test_bitvector.c

rcf8e43	ref412e
147	147	}
148	148
149		#define test_bveq(_bv1, _bv2) \
150		do { \
151		BitVector _not_bv1, _not_bv2; \
152		Assert(bv_eq(_bv1, _bv2), "BitVectors are equal~~");~~ \
153		Assert(bv_eq(_bv2, _bv1), "BitVectors are equal~~");~~ \
154		Assert(bv_eq(_bv1, _bv1), "bv_eq on self should work"); \
155		Aiequal(bv_hash(_bv1), bv_hash(_bv2)); \
156		/* test flipped bitvectors */ \
157		_not_bv1 = bv_not(_bv1); _not_bv2 = bv_not(_bv2); \
158		bv_set(_not_bv1, 1100); /* should make no difference */ \
159		Assert(bv_eq(_not_bv1, _not_bv2), "~~BitVectors are equal~~"); \
160		Assert(bv_eq(_not_bv2, _not_bv1), "~~BitVectors are equal~~"); \
161		Assert(bv_eq(_not_bv1, _not_bv1), "bv_eq on self should work"); \
162		Aiequal(bv_hash(_not_bv1), bv_hash(_not_bv2)); \
163		bv_destroy(_not_bv1); bv_destroy(_not_bv2); \
	149	#define test_bveq(_bv1, _bv2) \
	150	do { \
	151	BitVector _not_bv1, _not_bv2; \
	152	Assert(bv_eq(_bv1, _bv2), "BitVectors are equal ->"); \
	153	Assert(bv_eq(_bv2, _bv1), "BitVectors are equal <-"); \
	154	Assert(bv_eq(_bv1, _bv1), "bv_eq on self should work"); \
	155	Aiequal(bv_hash(_bv1), bv_hash(_bv2)); \
	156	/* test flipped bitvectors */ \
	157	_not_bv1 = bv_not(_bv1); _not_bv2 = bv_not(_bv2); \
	158	bv_set(_not_bv1, 1100); /* should make no difference */ \
	159	Assert(bv_eq(_not_bv1, _not_bv2), "!BitVectors are equal ->"); \
	160	Assert(bv_eq(_not_bv2, _not_bv1), "!BitVectors are equal -<"); \
	161	Assert(bv_eq(_not_bv1, _not_bv1), "bv_eq on self should work"); \
	162	Aiequal(bv_hash(_not_bv1), bv_hash(_not_bv2)); \
	163	bv_destroy(_not_bv1); bv_destroy(_not_bv2); \
164	164	} while (0)
165	165
166		#define test_bvneq(_bv1, _bv2) \
167		do { \
168		BitVector _not_bv1, _not_bv2; \
169		Assert(!bv_eq(_bv1, _bv2), "BitVectors are not equal~~");~~ \
170		Assert(!bv_eq(_bv2, _bv1), "BitVectors are not equal~~");~~ \
171		Assert(bv_hash(_bv1) != bv_hash(_bv2), "BitVectors not equal"); \
172		/* test flipped bitvectors */ \
173		_not_bv1 = bv_not(_bv1); _not_bv2 = bv_not(_bv2); \
174		Assert(!bv_eq(_not_bv1, _not_bv2), "~~BitVectors are not equal~~"); \
175		Assert(!bv_eq(_not_bv2, _not_bv1), "~~BitVectors are not equal~~"); \
176		Assert(bv_hash(_not_bv1) != bv_hash(_not_bv2), "Bitvectors !=");\
177		bv_destroy(_not_bv1); bv_destroy(_not_bv2); \
	166	#define test_bvneq(_bv1, _bv2) \
	167	do { \
	168	BitVector _not_bv1, _not_bv2; \
	169	Assert(!bv_eq(_bv1, _bv2), "BitVectors are not equal ->"); \
	170	Assert(!bv_eq(_bv2, _bv1), "BitVectors are not equal <-"); \
	171	Assert(bv_hash(_bv1) != bv_hash(_bv2), "BitVector hash not equal"); \
	172	/* test flipped bitvectors */ \
	173	_not_bv1 = bv_not(_bv1); _not_bv2 = bv_not(_bv2); \
	174	Assert(!bv_eq(_not_bv1, _not_bv2), "!BitVectors are not equal ->"); \
	175	Assert(!bv_eq(_not_bv2, _not_bv1), "!BitVectors are not equal <-"); \
	176	Assert(bv_hash(_not_bv1) != bv_hash(_not_bv2), "Bitvector hash !=");\
	177	bv_destroy(_not_bv1); bv_destroy(_not_bv2); \
178	178	} while (0)
179	179
…	…
534	534	/* test scan_next_from where size is actually greater than the highest set
535	535	* bit */
536		bv~~->size++~~;
537		~~not_bv->size++~~;
	536	bv_unset(bv, bv->size);
	537	bv_set(not_bv, not_bv->size);
538	538
539	539	bv_scan_reset(bv);