summaryrefslogtreecommitdiff
path: root/src/basic/bitmap.c
AgeCommit message (Collapse)Author
2015-07-31bitmap: make bitmap_clear free the bitmap arrayMartin Mikkelsen
Given two bitmaps and the following code: Bitmap *a = bitmap_new(), *b = bitmap_new(); bitmap_set(a, 1); bitmap_clear(a); bitmap_set(a, 0); bitmap_set(b, 0); These two bitmaps should now have the same bits set and they should be equal but bitmap_equal() will return false in this case because while bitmap_clear() resets the number of elements in the array it does not clear the array and bitmap_set() expects the array to be cleared. GREEDY_REALLOC0 looks at the allocated size and not the actual size so it does not clear any memory. Fix this by freeing the allocated memory and resetting the whole Bitmap to an initial state in bitmap_clear(). This also adds test code for this issue.
2015-07-31bitmap: fix bitmap_equal on bitmaps with unset bitsMartin Mikkelsen
Given two bitmaps and the following code: Bitmap *a = bitmap_new(), *b = bitmap_new(); bitmap_set(a, 0); bitmap_unset(a, 0); These two bitmaps should now have the same bits set and they should be equal but bitmap_equal() will return false in this case because the bitmaps array in a is larger because of the bit which was previously set. Fix this by comparing only the bits which exists in both bitmaps and then check that the rest of the bits (if any) is all zero. This also adds test code for this issue.
2015-07-23bitmap: various clean-upsLennart Poettering
a) use memcmp() to compare bitmaps efficiently b) use UINT64_C() macro instead of ULL suffixes to get right suffix for uint64_t constants c) add a few assert()s d) when comparing integers with 0 we generally try to make this explicit with "!= 0". e) remove redundant bitmap_isset() if check, as we don't have it in bitmap_isset() either. f) It should be fine to invoke bitmap_unset() on a NULL bitmap
2015-07-23basic: bitmap: use uint64_t instead if long long unsignedDaniel Mack
long long unsigned is always 64 bit wide, so use a more readable type.
2015-07-23bitmap: bitmap_clear()Lennart Poettering
No need to actually reset the bitmap, we can just truncate it back zero size. That not only makes bitmap_clear() quicker, but also subsequent bitmap_isclear().
2015-07-17basic: bitmap - complete fix for bitshift overflowTom Gundersen
The bug found by David existed in several places, fix them all. Also extend the tests to cover these cases.
2015-07-17bitmap: avoid 32bit integer overflow in shiftDavid Herrmann
We really must use 64bit integers to calculate long-long shifts. Otherwise, we will never get higher masks than 2^31.
2015-07-17bitmap: allow bitmap_iterate() on NULL bitmapDavid Herrmann
Make sure we properly treat NULL bitmaps as empty. Right now, we don't (which really looks like a typo).
2015-07-16bitmap: use external iteratorTom Gundersen
Reuse the Iterator object from hashmap.h and expose a similar API. This allows us to do { Iterator i; unsigned n; BITMAP_FOREACH(n, b, i) { Iterator j; unsigned m; BITMAP_FOREACH(m, b, j) { ... } } } without getting confused. Requested by David.
2015-07-14basic: add a Bitmap implementationTom Gundersen
For when a Hashmap is overkill.