Line data Source code
1 : /* $Id: bitvector.c 492816 2012-01-25 00:14:30Z ib-builder $
2 : *
3 : * bitvector.c - Bit vector manipulation
4 : *
5 : * Dave Katz, March 2008
6 : *
7 : * Copyright (c) 2008, Juniper Networks, Inc.
8 : * All rights reserved.
9 : */
10 :
11 : /*
12 : * See bitvector.h for an overview of how this stuff works.
13 : */
14 :
15 :
16 : #include "bvx_environment.h"
17 : #include "bitvector.h"
18 : #include "bitvector_private.h"
19 :
20 :
21 : static bvx_block_tag bv_ent_tag;
22 :
23 : /*
24 : * Array of count of bits set.
25 : *
26 : * Index into this array with a byte of data, returns the number of bits
27 : * set in the byte.
28 : */
29 : static const uint8_t bitcount_array[256] =
30 : {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
31 : 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
32 : 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
33 : 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
34 : 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
35 : 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
36 : 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
37 : 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
38 : 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
39 : 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
40 : 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
41 : 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
42 : 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
43 : 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
44 : 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
45 : 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};
46 :
47 :
48 : /*
49 : * bv_bitcount
50 : *
51 : * Returns the number of set bits in a vector word.
52 : */
53 : static uint32_t
54 118 : bv_bitcount (bv_word_t word)
55 : {
56 : uint32_t bitcount;
57 : uint32_t bytenum;
58 : uint8_t byteval;
59 :
60 118 : bitcount = 0;
61 :
62 : /* Walk each byte and accumulate the bit count. */
63 :
64 179 : for (bytenum = 0; bytenum < sizeof(bv_word_t); bytenum++) {
65 :
66 : /* Quick cheat. If the residual is zero, we're done. */
67 :
68 179 : if (!word)
69 118 : break;
70 61 : byteval = word & 0xff;
71 61 : bitcount += bitcount_array[byteval];
72 61 : word >>= 8;
73 : }
74 :
75 118 : return bitcount;
76 : }
77 :
78 :
79 : /*
80 : * Array of bit number of the first set bit.
81 : *
82 : * Index into this array with a byte of data, returns the bit number of the
83 : * first one bit. A value of -1 means that all bits are clear.
84 : */
85 : static const int8_t bitset_array[256] =
86 : {-1, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
87 : 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
88 : 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
89 : 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
90 : 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
91 : 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
92 : 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
93 : 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
94 : 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
95 : 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
96 : 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
97 : 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
98 : 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
99 : 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
100 : 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
101 : 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0};
102 :
103 :
104 : /*
105 : * bv_first_set
106 : *
107 : * Returns the bit number of the first bit set in a word, or 1 if no bits
108 : * are set.
109 : */
110 : static int
111 0 : bv_first_set (bv_word_t word)
112 : {
113 : int bitnum;
114 : uint32_t bytenum;
115 : uint8_t byteval;
116 :
117 : /* Quick cheat. Bail if the word is zero. */
118 :
119 0 : if (word == 0)
120 0 : return -1;
121 :
122 : /* Walk each byte looking for the first set bit. */
123 :
124 0 : for (bytenum = 0; bytenum < sizeof(bv_word_t); bytenum++) {
125 :
126 : /* Quick cheat. If the residual is zero, we're done. */
127 :
128 0 : if (!word)
129 0 : return -1;
130 0 : byteval = word & 0xff;
131 0 : bitnum = bitset_array[byteval];
132 0 : if (bitnum >= 0)
133 0 : return ((bytenum * 8) + bitnum);
134 0 : word >>= 8;
135 : }
136 :
137 : /* We shouldn't get here, but quiet the compiler. */
138 :
139 0 : return -1;
140 : }
141 :
142 :
143 : /*
144 : * Array of bit number of the first clear bit.
145 : *
146 : * Index into this array with a byte of data, returns the bit number of the
147 : * first zero bit. A value of -1 means that all bits are set.
148 : */
149 : static const int8_t bitclear_array[256] =
150 : {0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
151 : 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5,
152 : 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
153 : 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6,
154 : 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
155 : 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5,
156 : 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
157 : 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 7,
158 : 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
159 : 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5,
160 : 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
161 : 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6,
162 : 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
163 : 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5,
164 : 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
165 : 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, -1};
166 :
167 :
168 : /*
169 : * bv_first_clear
170 : *
171 : * Returns the bit number of the first bit clear in a word, or -1 if no bits
172 : * are clear.
173 : */
174 : static int
175 23 : bv_first_clear (bv_word_t word)
176 : {
177 : int bitnum;
178 : uint32_t bytenum;
179 : uint8_t byteval;
180 :
181 : /* Quick cheat. Bail if the word is all one. */
182 :
183 23 : if (word == BV_ALLSET)
184 0 : return -1;
185 :
186 : /* Walk each byte looking for the first clear bit. */
187 :
188 28 : for (bytenum = 0; bytenum < sizeof(bv_word_t); bytenum++) {
189 :
190 28 : byteval = word & 0xff;
191 28 : bitnum = bitclear_array[byteval];
192 28 : if (bitnum >= 0)
193 23 : return ((bytenum * 8) + bitnum);
194 5 : word >>= 8;
195 : }
196 :
197 : /* We shouldn't get here, but quiet the compiler. */
198 :
199 0 : return -1;
200 : }
201 :
202 :
203 : /*
204 : * bv_empty_cb
205 : *
206 : * Callback for seeing if there are any set bits. We set the flag and
207 : * abort the search if we get called (meaning there was a bit set.)
208 : */
209 : static boolean
210 118 : bv_empty_cb (void *context, bv_bitnum_t bit_number BVX_UNUSED,
211 : boolean new_bit_value BVX_UNUSED,
212 : boolean old_bit_value BVX_UNUSED)
213 : {
214 : boolean *bit_found;
215 :
216 118 : bit_found = context;
217 118 : *bit_found = TRUE;
218 :
219 118 : return TRUE; /* Abort */
220 : }
221 :
222 :
223 : /*
224 : * bv_empty
225 : *
226 : * Returns TRUE if a bit vector is empty, or FALSE if not.
227 : */
228 : boolean
229 199 : bv_empty (bit_vector *bv)
230 : {
231 : boolean bit_found;
232 :
233 : /* No touching the vector from a callback routine. */
234 :
235 199 : bvx_assert(!bv->bv_cb_result);
236 199 : bvx_assert(!bv->bv_cb_source);
237 :
238 : /* If the entry count is zero, it's definitely empty. */
239 :
240 199 : bit_found = (bv->bv_entry_count != 0);
241 199 : if (bit_found) {
242 : /*
243 : * If we're using fast vectors, we can't rely on the entry count, since
244 : * we don't always delete empty entries. So walk it instead.
245 : */
246 118 : if (bv->bv_fastvects) {
247 118 : bv_walk_vector(bv, bv_empty_cb, &bit_found);
248 : }
249 : }
250 199 : return (!bit_found);
251 : }
252 :
253 :
254 : /*
255 : * bv_entry_active_here
256 : *
257 : * Returns TRUE if the specified vector entry matches our current position.
258 : */
259 : static inline boolean
260 1502 : bv_entry_active_here (bv_entry *bv_ent, bv_bitnum_t start_bitnum)
261 : {
262 1502 : return (bv_ent && bv_ent->bv_start == start_bitnum);
263 : }
264 :
265 :
266 : /*
267 : * bv_next_entry
268 : *
269 : * Returns the next entry pointer for a vector, given the current one,
270 : * or NULL if none are left.
271 : */
272 : static bv_entry *
273 610 : bv_next_entry (bit_vector *bv, bv_entry *cur_ent)
274 : {
275 : bv_entry *next_ent;
276 :
277 : next_ent =
278 610 : bv_patnode_to_bv_entry(bvx_patricia_get_next(bv->bv_root,
279 : &cur_ent->bv_ent_node));
280 610 : return next_ent;
281 : }
282 :
283 :
284 : /*
285 : * bv_advance_entry
286 : *
287 : * Advance the entry pointer for a vector if it's pointing at our current
288 : * position. Otherwise leave the pointer be.
289 : *
290 : * Returns a pointer, or NULL if nothing left.
291 : */
292 : static bv_entry *
293 720 : bv_advance_entry (bit_vector *bv, bv_entry *cur_ent, bv_bitnum_t start_bitnum)
294 : {
295 : bv_entry *next_ent;
296 :
297 : /* If the current entry is NULL, so is the next one. */
298 :
299 720 : if (!cur_ent)
300 421 : return NULL;
301 :
302 299 : if (bv_entry_active_here(cur_ent, start_bitnum)) {
303 299 : next_ent = bv_next_entry(bv, cur_ent);
304 : } else {
305 0 : next_ent = cur_ent;
306 : }
307 :
308 299 : return next_ent;
309 : }
310 :
311 :
312 : /*
313 : * bv_init_vector
314 : *
315 : * Initialize a bit vector.
316 : *
317 : * Zeroes the block and initializes it. We allocate the patricia tree
318 : * when it's time to add the first entry.
319 : */
320 : void
321 791 : bv_init_vector (bit_vector *bv, boolean fast_vects)
322 : {
323 791 : memset(bv, 0, sizeof(bit_vector));
324 791 : bv->bv_fastvects = fast_vects;
325 791 : bv->bv_freed_ord = BV_BAD_BITNUM;
326 791 : thread_new_circular_thread(&bv->bv_nonfull_head);
327 791 : }
328 :
329 :
330 : /*
331 : * bv_init_vector_tree
332 : *
333 : * Initialize a bit vector tree.
334 : *
335 : * Returns 0 if all OK, or -1 if out of memory.
336 : */
337 : static int
338 297 : bv_init_vector_tree (bit_vector *bv)
339 : {
340 : /* Create the patricia tree. */
341 :
342 297 : bv->bv_root = bvx_patroot_init(sizeof(bv_bitnum_t),
343 : BVX_PATRICIA_OFFSET(bv_entry,
344 : bv_ent_node,
345 : bv_key));
346 297 : if (!bv->bv_root)
347 0 : return -1; /* Out of memory */
348 :
349 297 : return 0;
350 : }
351 :
352 :
353 : /*
354 : * bv_build_key
355 : *
356 : * Build a patricia key (which consists of putting the low-order bits
357 : * of the start bit number into the highest address of the key so that
358 : * it ends up in lexicographic order.) In big-endian machines this
359 : * will burn some CPU but still do the right thing.
360 : */
361 : static void
362 1382 : bv_build_key (uint8_t key_ptr[], bv_bitnum_t bit_number)
363 : {
364 : int key_count;
365 :
366 1382 : key_count = sizeof(bv_bitnum_t);
367 : do {
368 5528 : key_count--;
369 5528 : key_ptr[key_count] = bit_number & 0xff;
370 5528 : bit_number >>= 8;
371 5528 : } while (key_count);
372 1382 : }
373 :
374 :
375 : /*
376 : * bv_ent_create
377 : *
378 : * Create a bit vector entry, initialize it, and put it into the tree,
379 : * given the desired bit number.
380 : *
381 : * Returns a pointer to the vector entry, or NULL if out of memory.
382 : */
383 : static bv_entry *
384 311 : bv_ent_create (bit_vector *bv, bv_bitnum_t bit_number)
385 : {
386 : bv_entry *bv_ent;
387 : bv_entry *next_ent;
388 : bv_bitnum_t next_ord;
389 :
390 : /* If the tree doesn't exist yet, create it. */
391 :
392 311 : if (!bv->bv_root) {
393 297 : if (bv_init_vector_tree(bv) < 0)
394 0 : return NULL; /* Out of memory */
395 : }
396 :
397 : /* Create the memory block if it doesn't already exist. */
398 :
399 311 : if (!bv_ent_tag) {
400 125 : bv_ent_tag =
401 125 : bvx_malloc_block_create(sizeof(bv_entry), "Bit vector entry");
402 : }
403 :
404 : /* Allocate the block. */
405 :
406 311 : bv_ent = bvx_malloc_block(bv_ent_tag);
407 311 : if (!bv_ent)
408 0 : return bv_ent; /* Out of memory */
409 :
410 : /* Got the entry. Initialize it and put it into the tree. */
411 :
412 311 : bv_ent->bv_start = bv_start_bit(bit_number);
413 311 : bv_build_key(bv_ent->bv_key, bv_ent->bv_start);
414 :
415 311 : thread_circular_add_top(&bv->bv_nonfull_head,
416 : &bv_ent->bv_ent_nonfull_thread);
417 311 : bvx_assert(bvx_patricia_add(bv->bv_root, &bv_ent->bv_ent_node));
418 311 : bv->bv_entry_count++;
419 :
420 : /*
421 : * If the freed ordinal was pointing at this one, or there isn't
422 : * one noted yet, look at the next entry in the tree. If it is
423 : * nonexistent, or there is a hole in the bit number space, save
424 : * the ordinal after the current block as being free. Otherwise,
425 : * set it to BADNUM since we don't know where to find one.
426 : */
427 311 : if (bv->bv_freed_ord == bv_ent->bv_start ||
428 293 : bv->bv_freed_ord == BV_BAD_BITNUM) {
429 311 : next_ent = bv_next_entry(bv, bv_ent);
430 311 : next_ord = bv_ent->bv_start + BV_BITSIZE;
431 311 : if (next_ent && next_ent->bv_start == next_ord)
432 0 : next_ord = BV_BAD_BITNUM; /* No hole here. */
433 311 : bv->bv_freed_ord = next_ord;
434 : }
435 311 : return bv_ent;
436 : }
437 :
438 :
439 : /*
440 : * bv_ent_destroy
441 : *
442 : * Destroy a bit vector entry. The entry is deleted from the bit vector
443 : * patricia tree and freed.
444 : */
445 : static void
446 311 : bv_ent_destroy (bit_vector *bv, bv_entry *bv_ent)
447 : {
448 : /*
449 : * If the ordinal of this entry is less than the current freed ordinal,
450 : * or the freed ordinal is unset, point the freed ordinal at this one.
451 : */
452 311 : if (bv->bv_freed_ord == BV_BAD_BITNUM ||
453 311 : bv_ent->bv_start < bv->bv_freed_ord) {
454 311 : bv->bv_freed_ord = bv_ent->bv_start;
455 : }
456 :
457 : /* Delete the entry from the tree and free it. */
458 :
459 311 : bvx_patricia_delete(bv->bv_root, &bv_ent->bv_ent_node);
460 311 : thread_remove(&bv_ent->bv_ent_nonfull_thread);
461 311 : bvx_free_block(bv_ent_tag, bv_ent);
462 311 : bvx_assert(bv->bv_entry_count > 0);
463 311 : bv->bv_entry_count--;
464 311 : }
465 :
466 :
467 : /*
468 : * bv_attempt_entry_free
469 : *
470 : * Destroy a bit vector entry if it is known to be all zero.
471 : *
472 : * Tolerates NULL pointers.
473 : */
474 : static void
475 480 : bv_attempt_entry_free (bit_vector *bv, bv_entry *bv_ent)
476 : {
477 480 : if (bv && bv_ent) {
478 299 : if (bv_ent->bv_setcount == 0) {
479 27 : bv_ent_destroy(bv, bv_ent);
480 : }
481 : }
482 480 : }
483 :
484 :
485 : /*
486 : * bv_ent_lookup
487 : *
488 : * Look up the bit vector entry containing the specified bit number.
489 : *
490 : * Returns a pointer to the entry, or NULL if not present.
491 : */
492 : static bv_entry *
493 1650 : bv_ent_lookup (bit_vector *bv, bv_bitnum_t bit_number)
494 : {
495 : bv_entry *result;
496 : bvx_patnode *node;
497 : bv_bitnum_t start_bit;
498 : uint8_t key[sizeof(bv_bitnum_t)];
499 :
500 : /* If there's no bit vector or patricia tree, the entry isn't here. */
501 :
502 1650 : if (!bv || !bv->bv_root)
503 579 : return NULL;
504 :
505 : /* Look it up in the patricia tree. */
506 :
507 1071 : start_bit = bv_start_bit(bit_number);
508 1071 : bv_build_key(key, start_bit);
509 1071 : node = bvx_patricia_lookup(bv->bv_root, key);
510 1071 : result = bv_patnode_to_bv_entry(node);
511 :
512 1071 : return result;
513 : }
514 :
515 :
516 : /*
517 : * bv_ent_lookup_first
518 : *
519 : * Look up the first bit vector entry in a vector.
520 : *
521 : * Returns a pointer to the entry, or NULL if nothing's there.
522 : */
523 : static bv_entry *
524 1981 : bv_ent_lookup_first (bit_vector *bv)
525 : {
526 : bv_entry *bv_ent;
527 :
528 : /* If no vector, there's nothing there. */
529 :
530 1981 : if (!bv)
531 735 : return NULL;
532 :
533 : /* If no tree, there's nothing here. */
534 :
535 1246 : if (!bv->bv_root)
536 591 : return NULL;
537 :
538 : bv_ent =
539 655 : bv_patnode_to_bv_entry(bvx_patricia_lookup_least(bv->bv_root));
540 :
541 655 : return bv_ent;
542 : }
543 :
544 :
545 : /*
546 : * bv_ent_lookup_last
547 : *
548 : * Look up the last bit vector entry in a vector.
549 : *
550 : * Returns a pointer to the entry, or NULL if nothing's there.
551 : */
552 : static bv_entry *
553 4 : bv_ent_lookup_last (bit_vector *bv)
554 : {
555 : bv_entry *bv_ent;
556 :
557 : /* If no vector, there's nothing there. */
558 :
559 4 : if (!bv)
560 0 : return NULL;
561 :
562 : /* If no tree, there's nothing here. */
563 :
564 4 : if (!bv->bv_root)
565 4 : return NULL;
566 :
567 : bv_ent =
568 0 : bv_patnode_to_bv_entry(bvx_patricia_lookup_greatest(bv->bv_root));
569 :
570 0 : return bv_ent;
571 : }
572 :
573 :
574 : /*
575 : * bv_destroy_tree
576 : *
577 : * Destroys the patricia tree root in the bit vector.
578 : */
579 : static void
580 378 : bv_destroy_tree (bit_vector *bv)
581 : {
582 : /* Toss the tree. */
583 :
584 378 : bvx_patroot_destroy(bv->bv_root);
585 378 : bv->bv_root = NULL;
586 378 : }
587 :
588 :
589 : /*
590 : * bv_clean
591 : *
592 : * Destroy all bit vector entries on a bit vector.
593 : *
594 : * Leaves the vector squeaky clean.
595 : */
596 : void
597 655 : bv_clean (bit_vector *bv)
598 : {
599 : bv_entry *bv_ent;
600 :
601 : /* No touching the vector from a callback routine. */
602 :
603 655 : bvx_assert(!bv->bv_cb_result);
604 655 : bvx_assert(!bv->bv_cb_source);
605 :
606 : /* Bail if the tree is pristine. */
607 :
608 655 : if (!bv->bv_root)
609 417 : return;
610 :
611 : /* Walk all of the vector entries and free them. */
612 :
613 : while (TRUE) {
614 :
615 : /* See if the next node is there. */
616 :
617 238 : bv_ent = bv_ent_lookup_first(bv);
618 238 : if (!bv_ent)
619 238 : break; /* All done */
620 :
621 : /* Got it. Destroy it. */
622 :
623 0 : bv_ent_destroy(bv, bv_ent);
624 : }
625 :
626 : /* Toss the tree. */
627 :
628 238 : bv_destroy_tree(bv);
629 : }
630 :
631 :
632 : /*
633 : * bv_set_bit
634 : *
635 : * Set a bit in a bit vector.
636 : *
637 : * May allocate a new bit vector entry.
638 : *
639 : * Returns the previous bit setting, or -1 if out of memory.
640 : */
641 : int
642 528 : bv_set_bit (bit_vector *bv, bv_bitnum_t bit_number)
643 : {
644 : bv_entry *bv_ent;
645 : boolean bit_is_set;
646 : bv_word_t *bit_word;
647 : bv_word_t bit_mask;
648 :
649 : /* No touching the vector from a callback routine. */
650 :
651 528 : bvx_assert(!bv->bv_cb_result);
652 :
653 : /*
654 : * If this vector is a callback source, we better only be touching the
655 : * current bit.
656 : */
657 528 : if (bv->bv_cb_source)
658 0 : bvx_assert(bv->bv_callback_ord == bit_number);
659 :
660 : /* The bit number better be valid. */
661 :
662 528 : bvx_assert(bit_number < BV_MAX_BITNUM);
663 :
664 : /* Look up the bit vector entry. */
665 :
666 528 : bit_is_set = FALSE;
667 528 : bv_ent = bv_ent_lookup(bv, bit_number);
668 528 : bit_mask = bv_word_mask(bit_number);
669 528 : if (!bv_ent) {
670 :
671 : /* No entry. Create one. */
672 :
673 311 : bv_ent = bv_ent_create(bv, bit_number);
674 311 : if (!bv_ent)
675 0 : return -1; /* Out of memory */
676 311 : bit_word = &bv_ent->bv_bits[bv_word_offset(bit_number)];
677 :
678 : } else {
679 :
680 : /* Entry is there. Note if the bit is already set. */
681 :
682 217 : bit_word = &bv_ent->bv_bits[bv_word_offset(bit_number)];
683 217 : bit_is_set = ((*bit_word & bit_mask) != 0);
684 : }
685 :
686 : /* Got the entry. If the bit isn't already set, do so now. */
687 :
688 528 : if (!bit_is_set) {
689 528 : *bit_word |= bit_mask;
690 528 : if (bv_ent->bv_setcount != BV_UNKNOWN_COUNT) {
691 :
692 : /*
693 : * We're manipulating bit counts. Bump this one. If it's
694 : * full, take it off of the non-full thread.
695 : */
696 528 : bv_ent->bv_setcount++;
697 528 : bvx_assert(bv_ent->bv_setcount <= BV_BITSIZE);
698 528 : if (bv_ent->bv_setcount == BV_BITSIZE)
699 0 : thread_remove(&bv_ent->bv_ent_nonfull_thread);
700 : }
701 : }
702 :
703 528 : return bit_is_set;
704 : }
705 :
706 :
707 : /*
708 : * bv_clear_bit
709 : *
710 : * Clear a bit in a bit vector.
711 : *
712 : * Returns the previous bit setting.
713 : *
714 : * May free the vector entry.
715 : */
716 : boolean
717 406 : bv_clear_bit (bit_vector *bv, bv_bitnum_t bit_number)
718 : {
719 : bv_entry *bv_ent;
720 : boolean bit_is_set;
721 : bv_word_t *bit_word;
722 : bv_word_t bit_mask;
723 :
724 : /* No touching the vector from a callback routine. */
725 :
726 406 : bvx_assert(!bv->bv_cb_result);
727 :
728 : /*
729 : * If this vector is a callback source, we better only be touching the
730 : * current bit.
731 : */
732 406 : if (bv->bv_cb_source)
733 59 : bvx_assert(bv->bv_callback_ord == bit_number);
734 :
735 : /* The bit number better be valid. */
736 :
737 406 : bvx_assert(bit_number < BV_MAX_BITNUM);
738 :
739 : /*
740 : * Look up the bit vector entry. If it's not there, the bit is
741 : * already clear.
742 : */
743 406 : bit_is_set = FALSE;
744 406 : bv_ent = bv_ent_lookup(bv, bit_number);
745 406 : if (bv_ent) {
746 406 : bit_mask = bv_word_mask(bit_number);
747 406 : bit_word = &bv_ent->bv_bits[bv_word_offset(bit_number)];
748 :
749 : /* Entry is there. Note if the bit is set. */
750 :
751 406 : bit_is_set = ((*bit_word & bit_mask) != 0);
752 406 : if (bit_is_set) {
753 :
754 : /* Bit is set. Clear it. */
755 :
756 406 : *bit_word &= ~bit_mask;
757 :
758 : /* Manipulate the bit count if appropriate. */
759 :
760 406 : if (bv_ent->bv_setcount != BV_UNKNOWN_COUNT) {
761 :
762 : /* We're keeping track of bits. Decrement this one. */
763 :
764 406 : bvx_assert(bv_ent->bv_setcount > 0);
765 406 : bv_ent->bv_setcount--;
766 :
767 : /* If all bits are clear, free the vector entry. */
768 :
769 406 : if (!bv_ent->bv_setcount) {
770 :
771 : /*
772 : * All bits are clear. Destroy the entry unless we're
773 : * on a callback with this vector as a source (we'll
774 : * free the entry later if so.)
775 : */
776 252 : if (!bv->bv_cb_source) {
777 225 : bv_ent_destroy(bv, bv_ent);
778 : }
779 252 : bv_ent = NULL;
780 : }
781 : }
782 :
783 : /*
784 : * If we still have an entry (it wasn't destroyed) we know that
785 : * it is no longer full, since we just cleared a bit. Add it
786 : * to the not-full list in that case.
787 : */
788 406 : if (bv_ent) {
789 154 : if (!thread_node_on_thread(&bv_ent->bv_ent_nonfull_thread)) {
790 0 : thread_circular_add_top(&bv->bv_nonfull_head,
791 : &bv_ent->bv_ent_nonfull_thread);
792 : }
793 : }
794 : }
795 : }
796 :
797 406 : return bit_is_set;
798 : }
799 :
800 :
801 : /*
802 : * bv_bit_is_set
803 : *
804 : * Returns TRUE if the specified bit is set, or FALSE if not.
805 : */
806 : boolean
807 236 : bv_bit_is_set (bit_vector *bv, bv_bitnum_t bit_number)
808 : {
809 : boolean bit_is_set;
810 : bv_entry *bv_ent;
811 : bv_word_t bit_mask, bit_word;
812 :
813 : /* No touching the vector from a callback routine. */
814 :
815 236 : bvx_assert(!bv->bv_cb_result);
816 :
817 : /* The bit number better be valid. */
818 :
819 236 : bvx_assert(bit_number < BV_MAX_BITNUM);
820 :
821 : /* Look up the bit vector entry. If it's not there, the bit is clear. */
822 :
823 236 : bit_is_set = FALSE;
824 236 : bv_ent = bv_ent_lookup(bv, bit_number);
825 236 : if (bv_ent) {
826 :
827 : /* Entry is there. Note if the bit is set. */
828 :
829 135 : bit_mask = bv_word_mask(bit_number);
830 135 : bit_word = bv_ent->bv_bits[bv_word_offset(bit_number)];
831 135 : bit_is_set = ((bit_word & bit_mask) != 0);
832 : }
833 :
834 236 : return bit_is_set;
835 : }
836 :
837 :
838 : /*
839 : * bv_find_clear_in_ent
840 : *
841 : * Finds a clear bit in a vector entry.
842 : *
843 : * Returns the vector bit number, or BV_BAD_BITNUM if there are no
844 : * clear bits in the entry.
845 : *
846 : * As a side effect, if the entry turns out to have no free bits, we
847 : * set the bit count if we lost track earlier, since we've gone to the
848 : * trouble of looking at all the bits.
849 : */
850 : static bv_bitnum_t
851 23 : bv_find_clear_in_ent (bv_entry *bv_ent)
852 : {
853 : uint32_t word_offset;
854 : bv_word_t bitword;
855 : int word_bitnum;
856 :
857 : /* Walk the words looking for a free bit. */
858 :
859 23 : for (word_offset = 0; word_offset < BV_WORDSIZE; word_offset++) {
860 23 : bitword = bv_ent->bv_bits[word_offset];
861 23 : if (bitword != BV_ALLSET) {
862 :
863 : /*
864 : * Got a word with at least one clear bit. Calculate the
865 : * first clear bit.
866 : */
867 23 : word_bitnum = bv_first_clear(bitword);
868 23 : bvx_assert(word_bitnum >= 0);
869 23 : return (bv_ent->bv_start + (word_offset * BV_BITSPERWORD) +
870 : word_bitnum);
871 : }
872 : }
873 :
874 : /* Didn't find one. Set the bit count to the max. */
875 :
876 0 : bvx_assert(bv_ent->bv_setcount == BV_BITSIZE ||
877 : bv_ent->bv_setcount == BV_UNKNOWN_COUNT);
878 0 : bv_ent->bv_setcount = BV_BITSIZE;
879 :
880 0 : return BV_BAD_BITNUM; /* Didn't find one. */
881 : }
882 :
883 :
884 : /*
885 : * bv_first_clear_bit
886 : *
887 : * Returns the ordinal of the lowest-numbered zero bit. One will
888 : * always be found unless there are two billion bits set, though it
889 : * may be past the end of the current array.
890 : *
891 : * If one is not particular about finding the lowest bit number,
892 : * bv_find_clear_bit() is potentially less expensive.
893 : *
894 : * Returns the bit number, or BV_BAD_BITNUM if all bits are exhausted.
895 : */
896 : bv_bitnum_t
897 125 : bv_first_clear_bit (bit_vector *bv)
898 : {
899 : bv_entry *bv_ent;
900 : bv_bitnum_t bitnum, ret_bitnum;
901 :
902 : /* No touching the vector from a callback routine. */
903 :
904 125 : bvx_assert(!bv->bv_cb_result);
905 :
906 : /* Look up the first vector entry. */
907 :
908 125 : bv_ent = bv_ent_lookup_first(bv);
909 125 : bitnum = 0;
910 :
911 : /* Walk all tree entries. */
912 :
913 : while (TRUE) {
914 :
915 : /* If we've exceeded the maximum bit number, bail. */
916 :
917 125 : if (bitnum >= BV_MAX_BITNUM)
918 0 : return BV_BAD_BITNUM;
919 :
920 : /* If there is no entry at this position, we've found a free bit. */
921 :
922 125 : if (!bv_entry_active_here(bv_ent, bitnum))
923 125 : return bitnum;
924 :
925 : /*
926 : * Process the entry if we think it's not full. Note that this
927 : * test will include any entries where we've lost track of the
928 : * bit count, so such entries may in fact be full.
929 : */
930 0 : if (bv_ent->bv_setcount != BV_BITSIZE) {
931 :
932 : /* Find a clear bit in the entry. */
933 :
934 0 : ret_bitnum = bv_find_clear_in_ent(bv_ent);
935 0 : if (ret_bitnum != BV_BAD_BITNUM)
936 0 : return ret_bitnum;
937 : }
938 :
939 : /* Advance to the next entry. */
940 :
941 0 : bv_ent = bv_advance_entry(bv, bv_ent, bitnum);
942 0 : bitnum += BV_BITSIZE;
943 : }
944 :
945 : return BV_BAD_BITNUM; /* Quiet the compiler. */
946 : }
947 :
948 :
949 : /*
950 : * bv_find_clear_bit
951 : *
952 : * Returns the ordinal of any zero bit. One will always be found
953 : * (unless two billion bits are set), though it may be past the end
954 : * of the current array.
955 : *
956 : * This routine will always return a free bit in an existing vector
957 : * entry if it can, which may be more memory-efficient.
958 : *
959 : * This routine will potentially be more expensive if fast vector
960 : * operations are in use, as it may be forced to walk the tree
961 : * searching for free bits instead of pulling entries from the non-full
962 : * thread, though we try hard to optimize it.
963 : *
964 : * Returns the bit ordinal, or BV_BAD_BITNUM if all bits are exhausted.
965 : */
966 : bv_bitnum_t
967 34 : bv_find_clear_bit (bit_vector *bv)
968 : {
969 : bv_entry *bv_ent;
970 : bv_bitnum_t bitnum, ret_bitnum;
971 : task_thread *thread_ptr;
972 : bv_bitnum_t missing_bitnum;
973 : boolean found_missing;
974 :
975 : /* No touching the vector from a callback routine. */
976 :
977 34 : bvx_assert(!bv->bv_cb_result);
978 :
979 : /* First, try the head of the non-full thread. */
980 :
981 34 : thread_ptr = thread_circular_top(&bv->bv_nonfull_head);
982 34 : bv_ent = bv_thread_to_bv_entry(thread_ptr);
983 34 : if (bv_ent) {
984 :
985 : /* Got an entry on the thread. It better have a free bit. */
986 :
987 23 : ret_bitnum = bv_find_clear_in_ent(bv_ent);
988 23 : bvx_assert(ret_bitnum != BV_BAD_BITNUM);
989 23 : return ret_bitnum;
990 : }
991 :
992 : /*
993 : * Nothing in the non-full thread. If fast vectors are off, this
994 : * means that all existing entries are definitely full, given that
995 : * there was nothing in the non-full list. See if we've cached
996 : * a free entry, and use it if so.
997 : */
998 11 : if (!bv->bv_fastvects) {
999 11 : if (bv->bv_freed_ord != BV_BAD_BITNUM)
1000 7 : return bv->bv_freed_ord;
1001 :
1002 : /*
1003 : * No freed ordinal was cached. Look up the last entry in the
1004 : * tree and return the next ordinal after that.
1005 : */
1006 4 : bv_ent = bv_ent_lookup_last(bv);
1007 :
1008 : /*
1009 : * See if we got an entry. If we didn't, the tree is completely
1010 : * empty, so we return bit number zero.
1011 : */
1012 4 : if (!bv_ent)
1013 4 : return 0;
1014 :
1015 : /*
1016 : * Got the last entry. If we're running out of bit numbers,
1017 : * fall through to a brute-force search. Otherwise, return
1018 : * the bit number of the next (as yet nonexistent) block.
1019 : */
1020 0 : if (bv_ent->bv_start < (BV_MAX_BITNUM - BV_BITSIZE))
1021 0 : return bv_ent->bv_start + BV_BITSIZE;
1022 : }
1023 :
1024 : /*
1025 : * If we've gotten here, we need to do a brute-force search to find an
1026 : * entry with a free bit. First, look up the first vector entry.
1027 : */
1028 0 : bv_ent = bv_ent_lookup_first(bv);
1029 0 : bitnum = 0;
1030 0 : missing_bitnum = 0;
1031 0 : found_missing = FALSE;
1032 :
1033 : /* Walk all tree entries. */
1034 :
1035 0 : while (bv_ent) {
1036 :
1037 : /* If we've exceeded the maximum bit number, bail. */
1038 :
1039 0 : if (bitnum >= BV_MAX_BITNUM)
1040 0 : return BV_BAD_BITNUM;
1041 :
1042 : /*
1043 : * If there is no entry at this position, and it's the first one
1044 : * that was empty, note it.
1045 : */
1046 0 : if (!bv_entry_active_here(bv_ent, bitnum) && !found_missing) {
1047 0 : missing_bitnum = bitnum;
1048 0 : found_missing = TRUE;
1049 : }
1050 :
1051 : /* Update the bit position to match the entry. */
1052 :
1053 0 : bitnum = bv_ent->bv_start;
1054 :
1055 : /* Found an entry. Process the entry if it might not be full. */
1056 :
1057 0 : if (bv_ent->bv_setcount != BV_BITSIZE) {
1058 :
1059 : /* Possibly not full. Walk the words looking for a free bit. */
1060 :
1061 0 : ret_bitnum = bv_find_clear_in_ent(bv_ent);
1062 0 : if (ret_bitnum != BV_BAD_BITNUM)
1063 0 : return ret_bitnum;
1064 : }
1065 :
1066 : /* Advance to the next entry. */
1067 :
1068 0 : bv_ent = bv_next_entry(bv, bv_ent);
1069 0 : bitnum += BV_BITSIZE;
1070 : }
1071 :
1072 : /*
1073 : * If we've gotten this far, we didn't find any free bits in any
1074 : * vector entry that exists. If we found a hole in the entry
1075 : * space (indicating a block of free bits), return that value.
1076 : */
1077 0 : if (found_missing)
1078 0 : return missing_bitnum;
1079 :
1080 : /*
1081 : * The entire bit array is packed full. Return the bit number of
1082 : * the next (nonexistent) entry unless we've hit the max.
1083 : */
1084 0 : if (bitnum >= BV_MAX_BITNUM)
1085 0 : return BV_BAD_BITNUM;
1086 :
1087 0 : return bitnum;
1088 : }
1089 :
1090 :
1091 : /*
1092 : * bv_first_set_bit
1093 : *
1094 : * Returns the ordinal of the first nonzero bit, or BV_BAD_BITNUM if
1095 : * none are found.
1096 : */
1097 : bv_bitnum_t
1098 0 : bv_first_set_bit (bit_vector *bv)
1099 : {
1100 : bv_entry *bv_ent;
1101 : uint32_t word_offset;
1102 : bv_bitnum_t bitnum;
1103 : int word_bitnum;
1104 : bv_word_t bitword;
1105 :
1106 : /* No touching the vector from a callback routine. */
1107 :
1108 0 : bvx_assert(!bv->bv_cb_result);
1109 0 : bvx_assert(!bv->bv_cb_source);
1110 :
1111 : /*
1112 : * Walk all tree entries. If we haven't done any fast set
1113 : * operations, we're guaranteed to find a set bit in the first
1114 : * block, so this is pretty cheap. But if any fast vector operations
1115 : * have been done, there may be empty blocks on the tree, so, we
1116 : * may potentially walk all blocks and never find anything.
1117 : */
1118 : while (TRUE) {
1119 :
1120 : /* Look up the first vector entry. */
1121 :
1122 0 : bv_ent = bv_ent_lookup_first(bv);
1123 :
1124 : /* Bail if there are no set bits. */
1125 :
1126 0 : if (!bv_ent)
1127 0 : break;
1128 :
1129 : /* Find the first nonzero bit in the vector entry. */
1130 :
1131 0 : bitnum = bv_ent->bv_start;
1132 0 : for (word_offset = 0; word_offset < BV_WORDSIZE; word_offset++) {
1133 0 : bitword = bv_ent->bv_bits[word_offset];
1134 0 : if (bitword) {
1135 :
1136 : /* Got a word with bits set. Calculate the first set bit. */
1137 :
1138 0 : word_bitnum = bv_first_set(bitword);
1139 0 : bvx_assert(word_bitnum >= 0);
1140 0 : return (bitnum + (word_offset * BV_BITSPERWORD) + word_bitnum);
1141 : }
1142 : }
1143 :
1144 : /*
1145 : * If we've gotten this far, we walked all of the words of a
1146 : * vector entry and saw no set bits. This can happen if we're
1147 : * doing fast vector operations, since we may have lost track
1148 : * of the bit count. Delete the block and fetch the next one.
1149 : */
1150 0 : bvx_assert(bv_ent->bv_setcount == 0 ||
1151 : bv_ent->bv_setcount == BV_UNKNOWN_COUNT);
1152 0 : bv_ent_destroy(bv, bv_ent);
1153 : }
1154 :
1155 0 : return BV_BAD_BITNUM;
1156 : }
1157 :
1158 :
1159 : /*
1160 : * bv_update_result
1161 : *
1162 : * Update a result word with an updated value.
1163 : *
1164 : * Returns the net number of bits set in the entry. Returns BV_MAX_BITNUM
1165 : * if the callback routine aborted the walk.
1166 : *
1167 : * This routine can be called with a NULL destination pointer. In this
1168 : * case no result bits are generated, but callbacks are made (it's not
1169 : * too useful if there is no callback pointer.)
1170 : *
1171 : * If the Fast Vector flag is set and no callback was supplied, just
1172 : * do straight word copies and flag that the bit count in the entry
1173 : * has been lost.
1174 : *
1175 : * This routine is pretty ugly because it tries to do some optimizations.
1176 : * The core issues are this, assuming fast vector processing isn't happening.
1177 : * Firstly, if the value and the existing destination values are different,
1178 : * the bit count in the destination needs to be updated. Secondly, if
1179 : * a bits-set callback is provided, we need to process every bit set in the
1180 : * value, even if the destination bit is the same.
1181 : */
1182 : static int
1183 358 : bv_update_result (bit_vector *bv, bv_entry *dest_ent, uint32_t word_index,
1184 : bv_word_t value, bv_bitnum_t word_bitnum,
1185 : bit_vector *src_bv1, bit_vector *src_bv2,
1186 : bv_callback callback, void *context,
1187 : bv_callback_option cb_opt)
1188 : {
1189 : bv_word_t dest_copy, value_copy;
1190 : bv_word_t *dest_ptr;
1191 : int net_set_count;
1192 : uint32_t dest_bit, value_bit;
1193 : uint32_t byte_ix, bit_ix;
1194 : uint8_t dest_copy_byte, value_copy_byte;
1195 : boolean cb_bitset;
1196 : boolean abort_walk;
1197 : bv_bitnum_t cur_bitnum;
1198 :
1199 : /* Flag that we might be doing a callback. */
1200 :
1201 358 : if (bv)
1202 59 : bv->bv_cb_result = TRUE;
1203 358 : if (src_bv1)
1204 299 : src_bv1->bv_cb_source = TRUE;
1205 358 : if (src_bv2)
1206 118 : src_bv2->bv_cb_source = TRUE;
1207 :
1208 : /* Note if we need to callback on bit sets. */
1209 :
1210 358 : cb_bitset = (callback && (cb_opt == BV_CALL_SET));
1211 :
1212 : /*
1213 : * Initialize. If no destination was specified, assume the old
1214 : * bits were zero.
1215 : */
1216 358 : net_set_count = 0;
1217 358 : if (dest_ent) {
1218 118 : dest_ptr = &dest_ent->bv_bits[word_index];
1219 118 : dest_copy = *dest_ptr;
1220 : } else {
1221 240 : dest_ptr = NULL;
1222 240 : dest_copy = 0;
1223 : }
1224 358 : value_copy = value;
1225 :
1226 : /* Update the result word. */
1227 :
1228 358 : if (dest_ptr)
1229 118 : *dest_ptr = value;
1230 :
1231 : /*
1232 : * See if we're doing fast vector processing without a callback.
1233 : * If so, we don't need to walk the bits.
1234 : */
1235 358 : if (bv && bv->bv_fastvects && !callback) {
1236 :
1237 : /*
1238 : * Doing fast vector processing. Flag that we're losing track
1239 : * of the bit count. Also remove the entry from the nonfull
1240 : * thread, since we don't know if it's not full.
1241 : */
1242 0 : if (dest_ent) {
1243 0 : dest_ent->bv_setcount = BV_UNKNOWN_COUNT;
1244 0 : thread_remove(&dest_ent->bv_ent_nonfull_thread);
1245 : }
1246 :
1247 358 : } else if (!callback) {
1248 :
1249 : /*
1250 : * There's no callback, so we don't have to walk all of the bits.
1251 : * We just need to calculate the difference in bit count between
1252 : * the old and new values.
1253 : */
1254 59 : net_set_count = bv_bitcount(value_copy) - bv_bitcount(dest_copy);
1255 :
1256 : } else {
1257 :
1258 : /*
1259 : * Walk each byte of the word, and each bit therein, and call
1260 : * the callback for each indicated bit if one has been
1261 : * specified.
1262 : */
1263 487 : for (byte_ix = 0; byte_ix < sizeof(bv_word_t); byte_ix++) {
1264 :
1265 : /*
1266 : * See if we can bail from the loop. We can do so if
1267 : * the remaining word values are equal (so we don't
1268 : * need to do any more bit count updates) and either
1269 : * we're not doing bit-set callbacks or both word values
1270 : * are zero.
1271 : */
1272 487 : if (dest_copy == value_copy && (!cb_bitset || value_copy == 0))
1273 : break;
1274 :
1275 : /*
1276 : * See if we have to process this byte . We need to do so
1277 : * if the bytes are unequal (so we can update the
1278 : * destination bit count), or if we're calling back on set
1279 : * bits and the result byte is nonzero.
1280 : */
1281 306 : dest_copy_byte = dest_copy & 0xff;
1282 306 : value_copy_byte = value_copy & 0xff;
1283 :
1284 306 : if (dest_copy_byte != value_copy_byte ||
1285 0 : (cb_bitset && dest_copy_byte != 0)) {
1286 :
1287 : /* Walk each bit in the byte. */
1288 :
1289 829 : for (bit_ix = 0; bit_ix < 8; bit_ix++) {
1290 :
1291 : /*
1292 : * See if we can exit early. We can do so if the
1293 : * remaining bits are all the same and either
1294 : * we're not calling back on set bits (no bit
1295 : * count to adjust and no callback to make) or
1296 : * both the remaining value and result bits are
1297 : * all zero (ditto.)
1298 : */
1299 823 : if ((dest_copy_byte == value_copy_byte) &&
1300 122 : (!cb_bitset || dest_copy_byte == 0)) {
1301 : break;
1302 : }
1303 :
1304 : /*
1305 : * We still need to continue . Mask off the low order
1306 : * bits. We need to call back if either CHANGE is
1307 : * indicated and the bits are different, or if SET is
1308 : * indicated and the result bit is set.
1309 : */
1310 641 : dest_bit = dest_copy_byte & 1;
1311 641 : value_bit = value_copy_byte & 1;
1312 641 : net_set_count += value_bit - dest_bit;
1313 641 : if (callback &&
1314 641 : ((dest_bit != value_bit && cb_opt == BV_CALL_CHANGE) ||
1315 363 : (value_bit && cb_opt == BV_CALL_SET))) {
1316 485 : cur_bitnum = word_bitnum + (byte_ix * 8) + bit_ix;
1317 485 : if (src_bv1)
1318 363 : src_bv1->bv_callback_ord = cur_bitnum;
1319 485 : if (src_bv2)
1320 121 : src_bv2->bv_callback_ord = cur_bitnum;
1321 : abort_walk =
1322 485 : (*callback)(context, cur_bitnum,
1323 : (boolean) value_bit,
1324 : (boolean) dest_bit);
1325 485 : if (abort_walk) {
1326 118 : net_set_count = BV_MAX_BITNUM;
1327 118 : goto bail;
1328 : }
1329 : }
1330 :
1331 : /* Shift the bytes down a bit. */
1332 :
1333 523 : dest_copy_byte >>= 1;
1334 523 : value_copy_byte >>= 1;
1335 : }
1336 : }
1337 :
1338 : /* Shift the words down a byte. */
1339 :
1340 188 : dest_copy >>= 8;
1341 188 : value_copy >>= 8;
1342 : }
1343 : }
1344 :
1345 181 : bail:
1346 :
1347 : /* Clear the callback flags. */
1348 :
1349 358 : if (bv)
1350 59 : bv->bv_cb_result = FALSE;
1351 358 : if (src_bv1)
1352 299 : src_bv1->bv_cb_source = FALSE;
1353 358 : if (src_bv2)
1354 118 : src_bv2->bv_cb_source = FALSE;
1355 :
1356 358 : return net_set_count;
1357 : }
1358 :
1359 :
1360 : /*
1361 : * bv_clear_result_entry
1362 : *
1363 : * The result of a bit operation is all zeros. Clear out the result entry,
1364 : * if present, and free it.
1365 : */
1366 : static void
1367 59 : bv_clear_result_entry (bit_vector *src1, bit_vector *src2, bit_vector *result,
1368 : bv_entry *result_ent, bv_bitnum_t start_bitnum,
1369 : bv_callback callback, void *context,
1370 : bv_callback_option cb_opt)
1371 : {
1372 : uint32_t i;
1373 : int net_set_count;
1374 :
1375 : /* Only bother if there's an entry here. */
1376 :
1377 59 : if (bv_entry_active_here(result_ent, start_bitnum)) {
1378 :
1379 : /* Update the vector if there is a callback. */
1380 :
1381 59 : if (callback) {
1382 118 : for (i = 0; i < BV_WORDSIZE; i++) {
1383 : net_set_count =
1384 59 : bv_update_result(result, result_ent, i, 0,
1385 59 : start_bitnum + (i * BV_BITSPERWORD),
1386 : src1, src2, callback, context, cb_opt);
1387 59 : if (net_set_count == BV_MAX_BITNUM)
1388 0 : return; /* Callback aborted */
1389 : }
1390 : }
1391 :
1392 : /* Destroy the result entry. */
1393 :
1394 59 : bv_ent_destroy(result, result_ent);
1395 : }
1396 : }
1397 :
1398 :
1399 : /*
1400 : * bv_clear_all_bits
1401 : *
1402 : * Clears all bits in the bit vector. All vector entries are freed as a
1403 : * side effect, along with the tree root. This is equivalent to bv_clean,
1404 : * but with a callback for each cleared bit.
1405 : */
1406 : void
1407 140 : bv_clear_all_bits (bit_vector *bv, bv_callback callback, void *context,
1408 : bv_callback_option cb_opt)
1409 : {
1410 : bv_entry *bv_ent;
1411 :
1412 : /* No touching the vector from a callback routine. */
1413 :
1414 140 : bvx_assert(!bv->bv_cb_result);
1415 140 : bvx_assert(!bv->bv_cb_source);
1416 :
1417 : /*
1418 : * If there's no callback, simply free the vector entries.
1419 : */
1420 140 : if (!callback) {
1421 0 : bv_clean(bv);
1422 0 : return;
1423 : }
1424 :
1425 : /* Walk the entire vector entry tree. */
1426 :
1427 : while (TRUE) {
1428 :
1429 : /* Look up the first vector entry. */
1430 :
1431 199 : bv_ent = bv_ent_lookup_first(bv);
1432 :
1433 : /* Bail if there's nothing left. */
1434 :
1435 199 : if (!bv_ent)
1436 140 : break;
1437 :
1438 : /* Clear the vector entry. */
1439 :
1440 59 : bv_clear_result_entry(NULL, NULL, bv, bv_ent, bv_ent->bv_start,
1441 : callback, context, cb_opt);
1442 : }
1443 :
1444 : /* Get rid of the tree root. */
1445 :
1446 140 : bv_destroy_tree(bv);
1447 : }
1448 :
1449 :
1450 : /*
1451 : * bv_copy_result
1452 : *
1453 : * Copy a vector entry to a result entry, and make any necessary
1454 : * callbacks. If there is no copied entry, clear the result entry
1455 : * instead.
1456 : *
1457 : * If there is no result pointer, the callbacks are made but the results
1458 : * are not stored.
1459 : *
1460 : * Returns 0 if all OK, or -1 if out of memory.
1461 : */
1462 : static int
1463 240 : bv_copy_result (bit_vector *src1, bit_vector *src2, bv_entry *copy_ptr,
1464 : bit_vector *result, bv_entry *result_ent,
1465 : bv_bitnum_t start_bitnum, bv_callback callback, void *context,
1466 : bv_callback_option cb_opt)
1467 : {
1468 : int net_set_count;
1469 : int set_count_delta;
1470 : uint32_t i;
1471 :
1472 : /* See if the entry copied from is present. */
1473 :
1474 240 : if (bv_entry_active_here(copy_ptr, start_bitnum)) {
1475 :
1476 : /*
1477 : * Something to copy. See if there is a result entry in this
1478 : * position.
1479 : */
1480 240 : if (result && !bv_entry_active_here(result_ent, start_bitnum)) {
1481 :
1482 : /*
1483 : * No active entry present here. Create a result entry at
1484 : * the new position.
1485 : */
1486 0 : result_ent = bv_ent_create(result, start_bitnum);
1487 0 : if (!result_ent)
1488 0 : return -1; /* Out of memory */
1489 : }
1490 :
1491 : /*
1492 : * If doing fast vector operations without a callback, just
1493 : * copy the bits.
1494 : */
1495 240 : if (result && result->bv_fastvects && !callback) {
1496 0 : memmove(&result_ent->bv_bits, ©_ptr->bv_bits, sizeof(result_ent->bv_bits));
1497 0 : result_ent->bv_setcount = BV_UNKNOWN_COUNT;
1498 0 : thread_remove(&result_ent->bv_ent_nonfull_thread);
1499 :
1500 : } else {
1501 :
1502 : /* Update the bits. */
1503 :
1504 240 : net_set_count = 0;
1505 362 : for (i = 0; i < BV_WORDSIZE; i++) {
1506 : set_count_delta =
1507 240 : bv_update_result(result, result_ent, i,
1508 : copy_ptr->bv_bits[i],
1509 240 : start_bitnum + (i * BV_BITSPERWORD),
1510 : src1, src2, callback, context, cb_opt);
1511 240 : if (set_count_delta == BV_MAX_BITNUM)
1512 118 : return 0; /* Callback aborted */
1513 122 : net_set_count += set_count_delta;
1514 : }
1515 :
1516 122 : if (result_ent && result_ent->bv_setcount != BV_UNKNOWN_COUNT) {
1517 0 : result_ent->bv_setcount += net_set_count;
1518 0 : bvx_assert(result_ent->bv_setcount >= 0);
1519 : }
1520 : }
1521 :
1522 : } else {
1523 :
1524 : /* Nothing to copy. Clear the result entry if present. */
1525 :
1526 0 : if (result)
1527 0 : bv_clear_result_entry(src1, src2, result, result_ent, start_bitnum,
1528 : callback, context, cb_opt);
1529 : }
1530 :
1531 122 : return 0;
1532 : }
1533 :
1534 :
1535 : /*
1536 : * Vector operation types
1537 : */
1538 : typedef enum {
1539 : VEC_OP_AND, /* AND operation */
1540 : VEC_OP_OR, /* OR operation */
1541 : VEC_OP_XOR, /* XOR operation */
1542 : VEC_OP_CLEAR, /* CLEAR operation */
1543 : VEC_OP_COPY, /* Copy operation */
1544 : VEC_OP_WALK /* Walk operation */
1545 : } vector_op_type;
1546 :
1547 :
1548 : /*
1549 : * bv_vector_op
1550 : *
1551 : * Perform the specified operation on two bit vectors, and store the result.
1552 : *
1553 : * The result may be the same as one of the parameters.
1554 : *
1555 : * Returns 0 if all ok, or -1 if out of memory.
1556 : *
1557 : * If a callback is supplied, it is called based on the callback
1558 : * option type--either for every bit changed in the result, or for
1559 : * every bit set in the result.
1560 : *
1561 : * We crawl down the three vectors (two sources and the result) and
1562 : * perform the operation requested. Each of the vectors may have
1563 : * holes in it (corresponding to a block of zero bits) and the code
1564 : * deals with that properly.
1565 : *
1566 : * We're lazy and pull the destination block off of the not-full list.
1567 : * Otherwise we'd have to keep track from down in the bowels as to
1568 : * whether the current destination entry was freed, and pass that all
1569 : * the way up here in order to know whether the pointer is valid.
1570 : */
1571 : static int
1572 473 : bv_vector_op (vector_op_type op_type, bit_vector *first, bit_vector *second,
1573 : bit_vector *result, bv_callback callback, void *context,
1574 : bv_callback_option cb_opt)
1575 : {
1576 : bv_entry *first_ent, *second_ent, *result_ent;
1577 : bv_entry *first_next, *second_next, *result_next;
1578 : bv_bitnum_t start_bitnum;
1579 : bv_word_t result_bits;
1580 : int net_set_count;
1581 : int set_count_delta;
1582 : bv_entry scratch_ent;
1583 : bv_entry *result_ptr;
1584 : bv_entry *copy_ptr;
1585 : uint32_t i;
1586 : boolean local_result;
1587 :
1588 : /* No null result with no callback. */
1589 :
1590 473 : bvx_assert(!(!result && !callback));
1591 :
1592 : /* Sources must be different. */
1593 :
1594 473 : bvx_assert(first != second);
1595 :
1596 : /* No touching the result vector from a callback routine. */
1597 :
1598 473 : if (result)
1599 0 : bvx_assert(!result->bv_cb_result);
1600 :
1601 : /* Walk the vectors. */
1602 :
1603 473 : first_ent = bv_ent_lookup_first(first);
1604 473 : second_ent = bv_ent_lookup_first(second);
1605 473 : result_ent = bv_ent_lookup_first(result);
1606 :
1607 713 : while (first_ent || second_ent || result_ent) {
1608 :
1609 : /*
1610 : * Update our current start bit position. It's the lowest of
1611 : * the positions of any of the current vector entries.
1612 : */
1613 240 : start_bitnum = BV_MAX_BITNUM;
1614 240 : if (first_ent && first_ent->bv_start < start_bitnum)
1615 240 : start_bitnum = first_ent->bv_start;
1616 240 : if (second_ent && second_ent->bv_start < start_bitnum)
1617 0 : start_bitnum = second_ent->bv_start;
1618 240 : if (result_ent && result_ent->bv_start < start_bitnum)
1619 0 : start_bitnum = result_ent->bv_start;
1620 :
1621 : /*
1622 : * Get the next entry for each vector, in case we end up deleting
1623 : * an entry. We advance any entry that matches our bit position.
1624 : */
1625 240 : first_next = bv_advance_entry(first, first_ent, start_bitnum);
1626 240 : second_next = bv_advance_entry(second, second_ent, start_bitnum);
1627 240 : result_next = bv_advance_entry(result, result_ent, start_bitnum);
1628 :
1629 : /*
1630 : * Take the result entry off of the not-full list, since it
1631 : * isn't easy to keep track of this once we get done toying
1632 : * with the entry (or freeing it.)
1633 : */
1634 240 : if (bv_entry_active_here(result_ent, start_bitnum))
1635 0 : thread_remove(&result_ent->bv_ent_nonfull_thread);
1636 :
1637 : /*
1638 : * See if we're missing one or the other of the parameters (or both.)
1639 : */
1640 480 : if (!bv_entry_active_here(first_ent, start_bitnum) ||
1641 240 : !bv_entry_active_here(second_ent, start_bitnum)) {
1642 :
1643 : /*
1644 : * One of them is missing. Optimize this case based on
1645 : * the operation.
1646 : */
1647 181 : switch (op_type) {
1648 0 : case VEC_OP_AND:
1649 :
1650 : /*
1651 : * AND operation. The result will be all clear. Clear
1652 : * the result, if any.
1653 : */
1654 0 : bv_clear_result_entry(first, second, result, result_ent,
1655 : start_bitnum, callback, context, cb_opt);
1656 0 : break;
1657 :
1658 0 : case VEC_OP_OR:
1659 : case VEC_OP_XOR:
1660 :
1661 : /*
1662 : * OR or XOR operation. Copy whichever entry is
1663 : * present, if any, to the result. This has the side
1664 : * effect of clearing the result if the entry is all
1665 : * zero.
1666 : */
1667 0 : copy_ptr = NULL;
1668 0 : if (bv_entry_active_here(first_ent, start_bitnum)) {
1669 0 : copy_ptr = first_ent;
1670 : } else {
1671 0 : copy_ptr = second_ent;
1672 : }
1673 0 : if (bv_copy_result(first, second, copy_ptr, result, result_ent,
1674 : start_bitnum, callback, context,
1675 : cb_opt) < 0) {
1676 0 : return -1; /* Out of memory */
1677 : }
1678 0 : break;
1679 :
1680 0 : case VEC_OP_CLEAR:
1681 :
1682 : /*
1683 : * Clear operation. If the first entry isn't present, clear
1684 : * the result.
1685 : */
1686 0 : if (!bv_entry_active_here(first_ent, start_bitnum)) {
1687 0 : bv_clear_result_entry(first, second, result, result_ent,
1688 : start_bitnum, callback, context,
1689 : cb_opt);
1690 : } else {
1691 :
1692 : /*
1693 : * The first entry is here (meaning that the second is
1694 : * not.) Copy it to the result.
1695 : */
1696 0 : if (bv_copy_result(first, second, first_ent, result,
1697 : result_ent, start_bitnum, callback,
1698 : context, cb_opt) < 0)
1699 0 : return -1; /* Out of memory */
1700 : }
1701 0 : break;
1702 :
1703 0 : case VEC_OP_COPY:
1704 :
1705 : /*
1706 : * Copy operation. Copy the first vector, if present,
1707 : * to the result. This has the side effect of
1708 : * clearing the result if it is all zero.
1709 : */
1710 0 : if (bv_copy_result(first, second, first_ent, result,
1711 : result_ent, start_bitnum, callback, context,
1712 : cb_opt) < 0) {
1713 0 : return -1; /* Out of memory */
1714 : }
1715 0 : break;
1716 :
1717 181 : case VEC_OP_WALK:
1718 :
1719 : /*
1720 : * Walk operation. Copy the first vector to the result, which
1721 : * is known to be NULL. This results in executing the callback
1722 : * for every set bit.
1723 : */
1724 181 : if (bv_copy_result(first, second, first_ent, result,
1725 : result_ent, start_bitnum, callback, context,
1726 : cb_opt) < 0) {
1727 0 : return -1; /* Out of memory */
1728 : }
1729 181 : break;
1730 :
1731 0 : default:
1732 0 : bvx_assert(FALSE);
1733 : break;
1734 : }
1735 :
1736 : } else {
1737 :
1738 : /*
1739 : * Both the first and second entries have something at this
1740 : * position. Walk the words, performing the operation. We use a
1741 : * local temporary entry if there is no result entry at
1742 : * this point.
1743 : */
1744 59 : net_set_count = 0;
1745 59 : if (bv_entry_active_here(result_ent, start_bitnum)) {
1746 0 : result_ptr = result_ent;
1747 0 : local_result = FALSE;
1748 : } else {
1749 59 : memset(&scratch_ent, 0, sizeof(scratch_ent));
1750 59 : scratch_ent.bv_start = start_bitnum;
1751 59 : result_ptr = &scratch_ent;
1752 59 : local_result = TRUE;
1753 : }
1754 118 : for (i = 0; i < BV_WORDSIZE; i++) {
1755 59 : switch (op_type) {
1756 59 : case VEC_OP_AND:
1757 59 : result_bits =
1758 59 : first_ent->bv_bits[i] & second_ent->bv_bits[i];
1759 59 : break;
1760 :
1761 0 : case VEC_OP_OR:
1762 0 : result_bits =
1763 0 : first_ent->bv_bits[i] | second_ent->bv_bits[i];
1764 0 : break;
1765 :
1766 0 : case VEC_OP_XOR:
1767 0 : result_bits =
1768 0 : first_ent->bv_bits[i] ^ second_ent->bv_bits[i];
1769 0 : break;
1770 :
1771 0 : case VEC_OP_CLEAR:
1772 0 : result_bits =
1773 0 : first_ent->bv_bits[i] & ~(second_ent->bv_bits[i]);
1774 0 : break;
1775 :
1776 0 : default:
1777 0 : bvx_assert(FALSE);
1778 : result_bits = 0; /* Quiet the compiler */
1779 : }
1780 :
1781 : /*
1782 : * Slightly grody hack. If we're updating a local result,
1783 : * we don't want to call the callback, since that will
1784 : * happen when we do the copy later.
1785 : */
1786 : set_count_delta =
1787 59 : bv_update_result(result, result_ptr, i, result_bits,
1788 59 : start_bitnum + (i * BV_BITSPERWORD),
1789 : first, second,
1790 : (local_result ? NULL : callback),
1791 : context, cb_opt);
1792 59 : if (set_count_delta == BV_MAX_BITNUM)
1793 0 : return 0; /* Callback aborted */
1794 59 : net_set_count += set_count_delta;
1795 : }
1796 :
1797 : /* See if there was a result entry at this location. */
1798 :
1799 59 : if (!local_result) {
1800 :
1801 : /*
1802 : * We were updating a live result entry. Update the count.
1803 : * Delete the entry if all bits are clear and we're allowed
1804 : * to release blocks.
1805 : */
1806 0 : if (result_ent->bv_setcount != BV_UNKNOWN_COUNT) {
1807 0 : result_ent->bv_setcount += net_set_count;
1808 0 : bvx_assert(result_ent->bv_setcount >= 0);
1809 0 : if (result_ent->bv_setcount == 0) {
1810 0 : bv_ent_destroy(result, result_ent);
1811 0 : result_ent = NULL;
1812 : }
1813 : }
1814 :
1815 : } else {
1816 :
1817 : /*
1818 : * There was no live result entry. See if there were
1819 : * any nonzero bits created (if we can tell.) If not,
1820 : * we're done.
1821 : */
1822 59 : if (net_set_count ||
1823 0 : scratch_ent.bv_setcount == BV_UNKNOWN_COUNT) {
1824 :
1825 : /*
1826 : * Copy the results into the result vector
1827 : * (creating a new entry.)
1828 : */
1829 59 : if (scratch_ent.bv_setcount != BV_UNKNOWN_COUNT)
1830 59 : scratch_ent.bv_setcount = net_set_count;
1831 59 : if (bv_copy_result(first, second, &scratch_ent, result,
1832 : result_ent, start_bitnum, callback,
1833 : context, cb_opt) < 0) {
1834 0 : return -1; /* Out of memory */
1835 : }
1836 : }
1837 : }
1838 : }
1839 :
1840 : /*
1841 : * We're done with the current entry. Try freeing the source
1842 : * entries in case the callback routine cleared the last bits.
1843 : * We need to look up the source entries again, since one or
1844 : * the other may have been freed above as a side effect if
1845 : * one is being used as the result vector.
1846 : */
1847 240 : first_ent = bv_ent_lookup(first, start_bitnum);
1848 240 : bv_attempt_entry_free(first, first_ent);
1849 240 : second_ent = bv_ent_lookup(second, start_bitnum);
1850 240 : bv_attempt_entry_free(second, second_ent);
1851 :
1852 : /* Advance the pointers. */
1853 :
1854 240 : first_ent = first_next;
1855 240 : second_ent = second_next;
1856 240 : result_ent = result_next;
1857 : }
1858 :
1859 473 : return 0;
1860 : }
1861 :
1862 :
1863 : /*
1864 : * bv_and_vectors
1865 : *
1866 : * Perform an AND operation on two bit vectors, and store the result.
1867 : *
1868 : * The result may be the same as one of the parameters.
1869 : *
1870 : * Returns 0 if all ok, or -1 if out of memory.
1871 : *
1872 : * If a callback is supplied, it is called for every bit that either changes
1873 : * or is set in the result, according to cb_opt.
1874 : */
1875 : int
1876 59 : bv_and_vectors (bit_vector *first, bit_vector *second, bit_vector *result,
1877 : bv_callback callback, void *context, bv_callback_option cb_opt)
1878 : {
1879 59 : return bv_vector_op(VEC_OP_AND, first, second, result, callback, context,
1880 : cb_opt);
1881 : }
1882 :
1883 :
1884 : /*
1885 : * bv_or_vectors
1886 : *
1887 : * Perform an OR operation on two bit vectors, and store the result.
1888 : *
1889 : * The result may be the same as one of the parameters.
1890 : *
1891 : * Returns 0 if all ok, or -1 if out of memory.
1892 : *
1893 : * If a callback is supplied, it is called for every bit that either changes
1894 : * or is set in the result, according to cb_opt.
1895 : */
1896 : int
1897 0 : bv_or_vectors (bit_vector *first, bit_vector *second, bit_vector *result,
1898 : bv_callback callback, void *context, bv_callback_option cb_opt)
1899 : {
1900 0 : return bv_vector_op(VEC_OP_OR, first, second, result, callback, context,
1901 : cb_opt);
1902 : }
1903 :
1904 :
1905 : /*
1906 : * bv_xor_vectors
1907 : *
1908 : * Perform an XOR operation on two bit vectors, and store the result. This
1909 : * is also handy as a compare operation; if BV_CALL_CHANGE is used, a
1910 : * callback will be made for every bit that is different between the two.
1911 : *
1912 : * The result may be the same as one of the parameters.
1913 : *
1914 : * Returns 0 if all ok, or -1 if out of memory.
1915 : *
1916 : * If a callback is supplied, it is called for every bit that either changes
1917 : * or is set in the result, according to cb_opt.
1918 : */
1919 : int
1920 0 : bv_xor_vectors (bit_vector *first, bit_vector *second, bit_vector *result,
1921 : bv_callback callback, void *context, bv_callback_option cb_opt)
1922 : {
1923 0 : return bv_vector_op(VEC_OP_XOR, first, second, result, callback, context,
1924 : cb_opt);
1925 : }
1926 :
1927 :
1928 : /*
1929 : * bv_clear_vectors
1930 : *
1931 : * Perform a Clear operation on two bit vectors, and store the result.
1932 : * Any set bits in the second parameter are cleared from the first.
1933 : *
1934 : * The result may be the same as one of the parameters.
1935 : *
1936 : * Returns 0 if all ok, or -1 if out of memory.
1937 : *
1938 : * If a callback is supplied, it is called for every bit that either changes
1939 : * or is set in the result, according to cb_opt.
1940 : */
1941 : int
1942 152 : bv_clear_vectors (bit_vector *first, bit_vector *second, bit_vector *result,
1943 : bv_callback callback, void *context,
1944 : bv_callback_option cb_opt)
1945 : {
1946 152 : return bv_vector_op(VEC_OP_CLEAR, first, second, result, callback,
1947 : context, cb_opt);
1948 : }
1949 :
1950 :
1951 : /*
1952 : * bv_copy_vector
1953 : *
1954 : * Copy a bit vector to another one.
1955 : *
1956 : * Returns 0 if all ok, or -1 if out of memory.
1957 : *
1958 : * If a callback is supplied, it is called for every bit that either changes
1959 : * or is set in the result, according to cb_opt.
1960 : */
1961 : int
1962 0 : bv_copy_vector (bit_vector *src, bit_vector *dest, bv_callback callback,
1963 : void *context, bv_callback_option cb_opt)
1964 : {
1965 0 : return bv_vector_op(VEC_OP_COPY, src, NULL, dest, callback, context,
1966 : cb_opt);
1967 : }
1968 :
1969 :
1970 : /*
1971 : * bv_walk_vector
1972 : *
1973 : * Walk a bit vector,
1974 : *
1975 : * Returns 0 if all ok, or -1 if out of memory.
1976 : *
1977 : * The callback is called for every bit that is set in the vector,
1978 : * according to cb_opt.
1979 : */
1980 : int
1981 262 : bv_walk_vector (bit_vector *vect, bv_callback callback, void *context)
1982 : {
1983 262 : return bv_vector_op(VEC_OP_WALK, vect, NULL, NULL, callback, context,
1984 : BV_CALL_SET);
1985 : }
|
