lib/util Move bitmap.c to lib/util

3 files changed, 176 insertions, 1 deletions

diff --git a/lib/util/bitmap.c b/lib/util/bitmap.c
new file mode 100644
index 0000000000..7defd77840
--- /dev/null
+++ b/lib/util/bitmap.c
@@ -0,0 +1,137 @@
+/*
+   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 "includes.h"
+#include "lib/util/bitmap.h"
+
+/* 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 = talloc(mem_ctx, struct bitmap);
+
+	if (!bm) return NULL;
+
+	bm->n = n;
+	bm->b = talloc_zero_array(bm, uint32_t, (n+31)/32);
+	if (!bm->b) {
+		TALLOC_FREE(bm);
+		return NULL;
+	}
+	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] |= (1<<(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] &= ~(1<<(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] & (1<<(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;
+}
diff --git a/lib/util/bitmap.h b/lib/util/bitmap.h
new file mode 100644
index 0000000000..cf7aa1b0bd
--- /dev/null
+++ b/lib/util/bitmap.h
@@ -0,0 +1,32 @@
+/*
+   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/>.
+*/
+
+/* The following definitions come from lib/bitmap.c  */
+
+struct bitmap {
+	uint32_t *b;
+	unsigned int n;
+};
+
+struct bitmap *bitmap_talloc(TALLOC_CTX *mem_ctx, int n);
+int bitmap_copy(struct bitmap * const dst, const struct bitmap * const src);
+bool bitmap_set(struct bitmap *bm, unsigned i);
+bool bitmap_clear(struct bitmap *bm, unsigned i);
+bool bitmap_query(struct bitmap *bm, unsigned i);
+int bitmap_find(struct bitmap *bm, unsigned ofs);
diff --git a/lib/util/wscript_build b/lib/util/wscript_build
index bdc9d10150..f8386fa73f 100755
--- a/lib/util/wscript_build
+++ b/lib/util/wscript_build
@@ -84,5 +84,11 @@ bld.SAMBA_LIBRARY('tdb-wrap',
                   deps='tdb_compat talloc samba-util',
                   private_library=True,
                   local_include=False
-                  )
+                 )
+
+bld.SAMBA_LIBRARY('bitmap',
+		  source='bitmap.c',
+		  deps='talloc samba-util',
+                  local_include=False,
+		  private_library=True)