summaryrefslogtreecommitdiffstats
path: root/lib/util/bitmap.c
diff options
context:
space:
mode:
Diffstat (limited to 'lib/util/bitmap.c')
-rw-r--r--lib/util/bitmap.c144
1 files changed, 144 insertions, 0 deletions
diff --git a/lib/util/bitmap.c b/lib/util/bitmap.c
new file mode 100644
index 0000000..12cdfe4
--- /dev/null
+++ b/lib/util/bitmap.c
@@ -0,0 +1,144 @@
+/*
+ Unix SMB/CIFS implementation.
+ simple bitmap functions
+ Copyright (C) Andrew Tridgell 1992-1998
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 3 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see <http://www.gnu.org/licenses/>.
+*/
+
+#include "replace.h"
+#include <talloc.h>
+#include "lib/util/bitmap.h"
+#include "lib/util/debug.h"
+#include "lib/util/fault.h"
+
+struct bitmap {
+ unsigned int n;
+ uint32_t b[1]; /* We allocate more */
+};
+
+/* these functions provide a simple way to allocate integers from a
+ pool without repetition */
+
+/****************************************************************************
+talloc a bitmap
+****************************************************************************/
+struct bitmap *bitmap_talloc(TALLOC_CTX *mem_ctx, int n)
+{
+ struct bitmap *bm;
+
+ bm = (struct bitmap *)talloc_zero_size(
+ mem_ctx,
+ offsetof(struct bitmap, b) + sizeof(uint32_t)*((n+31)/32));
+
+ if (!bm) return NULL;
+
+ talloc_set_name_const(bm, "struct bitmap");
+
+ bm->n = n;
+ return bm;
+}
+
+/****************************************************************************
+copy as much of the source bitmap as will fit in the destination bitmap.
+****************************************************************************/
+
+int bitmap_copy(struct bitmap * const dst, const struct bitmap * const src)
+{
+ int count = MIN(dst->n, src->n);
+
+ SMB_ASSERT(dst->b != src->b);
+ memcpy(dst->b, src->b, sizeof(uint32_t)*((count+31)/32));
+
+ return count;
+}
+
+/****************************************************************************
+set a bit in a bitmap
+****************************************************************************/
+bool bitmap_set(struct bitmap *bm, unsigned i)
+{
+ if (i >= bm->n) {
+ DEBUG(0,("Setting invalid bitmap entry %d (of %d)\n",
+ i, bm->n));
+ return false;
+ }
+ bm->b[i/32] |= (1U<<(i%32));
+ return true;
+}
+
+/****************************************************************************
+clear a bit in a bitmap
+****************************************************************************/
+bool bitmap_clear(struct bitmap *bm, unsigned i)
+{
+ if (i >= bm->n) {
+ DEBUG(0,("clearing invalid bitmap entry %d (of %d)\n",
+ i, bm->n));
+ return false;
+ }
+ bm->b[i/32] &= ~(1U<<(i%32));
+ return true;
+}
+
+/****************************************************************************
+query a bit in a bitmap
+****************************************************************************/
+bool bitmap_query(struct bitmap *bm, unsigned i)
+{
+ if (i >= bm->n) return false;
+ if (bm->b[i/32] & (1U<<(i%32))) {
+ return true;
+ }
+ return false;
+}
+
+/****************************************************************************
+find a zero bit in a bitmap starting at the specified offset, with
+wraparound
+****************************************************************************/
+int bitmap_find(struct bitmap *bm, unsigned ofs)
+{
+ unsigned int i, j;
+
+ if (ofs > bm->n) ofs = 0;
+
+ i = ofs;
+ while (i < bm->n) {
+ if (~(bm->b[i/32])) {
+ j = i;
+ do {
+ if (!bitmap_query(bm, j)) return j;
+ j++;
+ } while (j & 31 && j < bm->n);
+ }
+ i += 32;
+ i &= ~31;
+ }
+
+ i = 0;
+ while (i < ofs) {
+ if (~(bm->b[i/32])) {
+ j = i;
+ do {
+ if (!bitmap_query(bm, j)) return j;
+ j++;
+ } while (j & 31 && j < bm->n);
+ }
+ i += 32;
+ i &= ~31;
+ }
+
+ return -1;
+}