Commit 406dd556e20117b3cc2e5c53410d65314fd14056
2013-07-10T21:05:47
bitvec: Simplify the bit vector code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101
diff --git a/src/bitvec.h b/src/bitvec.h
index a033f53..fd6f0cc 100644
--- a/src/bitvec.h
+++ b/src/bitvec.h
@@ -19,58 +19,43 @@
typedef struct {
size_t length;
union {
- uint8_t *ptr;
+ uint64_t *words;
uint64_t bits;
} u;
} git_bitvec;
GIT_INLINE(int) git_bitvec_init(git_bitvec *bv, size_t capacity)
{
- if (capacity < 64) {
- bv->length = 0;
- bv->u.bits = 0;
- return 0;
+ memset(bv, 0x0, sizeof(*bv));
+
+ if (capacity >= 64) {
+ bv->length = (capacity / 64) + 1;
+ bv->u.words = git__calloc(bv->length, sizeof(uint64_t));
+ if (!bv->u.words)
+ return -1;
}
- bv->length = (capacity + 7) / 8;
- bv->u.ptr = git__calloc(bv->length, 1);
- return bv->u.ptr ? 0 : -1;
+ return 0;
}
-#define GIT_BITVEC_MASK_INLINE(BIT) (((uint64_t)1) << BIT)
-
-#define GIT_BITVEC_MASK_BYTE(BIT) (((uint8_t)1) << ((BIT) & 0x07))
-#define GIT_BITVEC_INDEX_BYTE(BIT) ((BIT) >> 3)
+#define GIT_BITVEC_MASK(BIT) ((uint64_t)1 << (BIT % 64))
+#define GIT_BITVEC_WORD(BV, BIT) (BV->length ? &BV->u.words[BIT / 64] : &BV->u.bits)
GIT_INLINE(void) git_bitvec_set(git_bitvec *bv, size_t bit, bool on)
{
- if (!bv->length) {
- assert(bit < 64);
-
- if (on)
- bv->u.bits |= GIT_BITVEC_MASK_INLINE(bit);
- else
- bv->u.bits &= ~GIT_BITVEC_MASK_INLINE(bit);
- } else {
- assert(bit < bv->length * 8);
+ uint64_t *word = GIT_BITVEC_WORD(bv, bit);
+ uint64_t mask = GIT_BITVEC_MASK(bit);
- if (on)
- bv->u.ptr[GIT_BITVEC_INDEX_BYTE(bit)] |= GIT_BITVEC_MASK_BYTE(bit);
- else
- bv->u.ptr[GIT_BITVEC_INDEX_BYTE(bit)] &= ~GIT_BITVEC_MASK_BYTE(bit);
- }
+ if (on)
+ *word |= mask;
+ else
+ *word &= ~mask;
}
GIT_INLINE(bool) git_bitvec_get(git_bitvec *bv, size_t bit)
{
- if (!bv->length) {
- assert(bit < 64);
- return (bv->u.bits & GIT_BITVEC_MASK_INLINE(bit)) != 0;
- } else {
- assert(bit < bv->length * 8);
- return (bv->u.ptr[GIT_BITVEC_INDEX_BYTE(bit)] &
- GIT_BITVEC_MASK_BYTE(bit)) != 0;
- }
+ uint64_t *word = GIT_BITVEC_WORD(bv, bit);
+ return (*word & GIT_BITVEC_MASK(bit)) != 0;
}
GIT_INLINE(void) git_bitvec_clear(git_bitvec *bv)
@@ -78,15 +63,13 @@ GIT_INLINE(void) git_bitvec_clear(git_bitvec *bv)
if (!bv->length)
bv->u.bits = 0;
else
- memset(bv->u.ptr, 0, bv->length);
+ memset(bv->u.words, 0x0, bv->length * sizeof(uint64_t));
}
GIT_INLINE(void) git_bitvec_free(git_bitvec *bv)
{
- if (bv->length) {
- git__free(bv->u.ptr);
- memset(bv, 0, sizeof(*bv));
- }
+ if (bv->length)
+ git__free(bv->u.words);
}
#endif