Commit 6fc5a58197bf04e1b5c6ca1bdb5765e90d3eb106
2013-07-08T22:42:02
Basic bit vector This is a simple bit vector object that is not resizable after the initial allocation but can be of arbitrary size. It will keep the bti vector entirely on the stack for vectors 64 bits or less, and will allocate the vector on the heap for larger sizes. The API is uniform regardless of storage location. This is very basic right now and all the APIs are inline functions, but it is useful for storing an array of boolean values.
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 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168
diff --git a/src/bitvec.h b/src/bitvec.h
new file mode 100644
index 0000000..a033f53
--- /dev/null
+++ b/src/bitvec.h
@@ -0,0 +1,92 @@
+/*
+ * Copyright (C) the libgit2 contributors. All rights reserved.
+ *
+ * This file is part of libgit2, distributed under the GNU GPL v2 with
+ * a Linking Exception. For full terms see the included COPYING file.
+ */
+#ifndef INCLUDE_bitvec_h__
+#define INCLUDE_bitvec_h__
+
+#include "util.h"
+
+/*
+ * This is a silly little fixed length bit vector type that will store
+ * vectors of 64 bits or less directly in the structure and allocate
+ * memory for vectors longer than 64 bits. You can use the two versions
+ * transparently through the API and avoid heap allocation completely when
+ * using a short bit vector as a result.
+ */
+typedef struct {
+ size_t length;
+ union {
+ uint8_t *ptr;
+ 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;
+ }
+
+ bv->length = (capacity + 7) / 8;
+ bv->u.ptr = git__calloc(bv->length, 1);
+ return bv->u.ptr ? 0 : -1;
+}
+
+#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)
+
+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);
+
+ 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);
+ }
+}
+
+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;
+ }
+}
+
+GIT_INLINE(void) git_bitvec_clear(git_bitvec *bv)
+{
+ if (!bv->length)
+ bv->u.bits = 0;
+ else
+ memset(bv->u.ptr, 0, bv->length);
+}
+
+GIT_INLINE(void) git_bitvec_free(git_bitvec *bv)
+{
+ if (bv->length) {
+ git__free(bv->u.ptr);
+ memset(bv, 0, sizeof(*bv));
+ }
+}
+
+#endif
diff --git a/tests-clar/core/bitvec.c b/tests-clar/core/bitvec.c
new file mode 100644
index 0000000..48d7b99
--- /dev/null
+++ b/tests-clar/core/bitvec.c
@@ -0,0 +1,64 @@
+#include "clar_libgit2.h"
+#include "bitvec.h"
+
+#if 0
+static void print_bitvec(git_bitvec *bv)
+{
+ int b;
+
+ if (!bv->length) {
+ for (b = 63; b >= 0; --b)
+ fprintf(stderr, "%d", (bv->u.bits & (1ul << b)) ? 1 : 0);
+ } else {
+ for (b = bv->length * 8; b >= 0; --b)
+ fprintf(stderr, "%d", (bv->u.ptr[b >> 3] & (b & 0x0ff)) ? 1 : 0);
+ }
+ fprintf(stderr, "\n");
+}
+#endif
+
+static void set_some_bits(git_bitvec *bv, size_t length)
+{
+ size_t i;
+
+ for (i = 0; i < length; ++i) {
+ if (i % 3 == 0 || i % 7 == 0)
+ git_bitvec_set(bv, i, true);
+ }
+}
+
+static void check_some_bits(git_bitvec *bv, size_t length)
+{
+ size_t i;
+
+ for (i = 0; i < length; ++i)
+ cl_assert_equal_b(i % 3 == 0 || i % 7 == 0, git_bitvec_get(bv, i));
+}
+
+void test_core_bitvec__0(void)
+{
+ git_bitvec bv;
+
+ cl_git_pass(git_bitvec_init(&bv, 32));
+ set_some_bits(&bv, 16);
+ check_some_bits(&bv, 16);
+ git_bitvec_clear(&bv);
+ set_some_bits(&bv, 32);
+ check_some_bits(&bv, 32);
+ git_bitvec_clear(&bv);
+ set_some_bits(&bv, 64);
+ check_some_bits(&bv, 64);
+ git_bitvec_free(&bv);
+
+ cl_git_pass(git_bitvec_init(&bv, 128));
+ set_some_bits(&bv, 32);
+ check_some_bits(&bv, 32);
+ set_some_bits(&bv, 128);
+ check_some_bits(&bv, 128);
+ git_bitvec_free(&bv);
+
+ cl_git_pass(git_bitvec_init(&bv, 4000));
+ set_some_bits(&bv, 4000);
+ check_some_bits(&bv, 4000);
+ git_bitvec_free(&bv);
+}