Move PBVH bitmap to separate header in blenlib.

The implementation was also changed in a couple ways: use unsigned
integers as its base type rather than unsigned chars, and uses macros
rather than functions. (These could be changed to inline functions.)

Currently it is still only used during PBVH building, but now it's
accessible elsewhere.

3 files changed, 87 insertions, 28 deletions

diff --git a/source/blender/blenlib/BLI_bitmap.h b/source/blender/blenlib/BLI_bitmap.h
new file mode 100644
index 00000000000..16a6fb8ee15
--- /dev/null
+++ b/source/blender/blenlib/BLI_bitmap.h
@@ -0,0 +1,82 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * 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 2
+ * 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, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2012 by Nicholas Bishop
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#ifndef __BLI_BITMAP_H__
+#define __BLI_BITMAP_H__
+
+typedef unsigned int* BLI_bitmap;
+
+/* warning: the bitmap does not keep track of its own size or check
+   for out-of-bounds access */
+
+/* internal use */
+/* 2^5 = 32 (bits) */
+#define BLI_BITMAP_POWER 5
+/* 0b11111 */
+#define BLI_BITMAP_MASK 31
+
+/* number of blocks needed to hold '_tot' bits */
+#define BLI_BITMAP_NUM_BLOCKS(_tot) \
+	(((_tot) >> BLI_BITMAP_POWER) + 1)
+
+/* size (in bytes) used to hold '_tot' bits */
+#define BLI_BITMAP_SIZE(_tot) \
+	(BLI_BITMAP_NUM_BLOCKS(_tot) * sizeof(unsigned int))
+
+/* allocate memory for a bitmap with '_tot' bits; free
+   with MEM_freeN() */
+#define BLI_BITMAP_NEW(_tot, _alloc_string) \
+	((BLI_bitmap)MEM_callocN(BLI_BITMAP_SIZE(_tot), \
+							 _alloc_string))
+
+/* get the value of a single bit at '_index' */
+#define BLI_BITMAP_GET(_bitmap, _index) \
+	((_bitmap)[(_index) >> BLI_BITMAP_POWER] & \
+	 (1 << ((_index) & BLI_BITMAP_MASK)))
+
+/* set the value of a single bit at '_index' */
+#define BLI_BITMAP_SET(_bitmap, _index) \
+	((_bitmap)[(_index) >> BLI_BITMAP_POWER] |= \
+	 (1 << ((_index) & BLI_BITMAP_MASK)))
+
+/* clear the value of a single bit at '_index' */
+#define BLI_BITMAP_CLEAR(_bitmap, _index) \
+	((_bitmap)[(_index) >> BLI_BITMAP_POWER] &= \
+	 ~(1 << ((_index) & BLI_BITMAP_MASK)))
+
+/* set or clear the value of a single bit at '_index' */
+#define BLI_BITMAP_MODIFY(_bitmap, _index, _set) \
+	do { \
+		if(_set) \
+			BLI_BITMAP_SET(_bitmap, _index); \
+		else \
+			BLI_BITMAP_CLEAR(_bitmap, _index); \
+	} while(0)
+
+/* resize bitmap to have space for '_tot' bits */
+#define BLI_BITMAP_RESIZE(_bitmap, _tot) \
+	(_bitmap) = MEM_reallocN(_bitmap, BLI_BITMAP_SIZE(_tot))
+
+#endif
diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt
index 6e8da84cb24..46538a6e0c1 100644
--- a/source/blender/blenlib/CMakeLists.txt
+++ b/source/blender/blenlib/CMakeLists.txt
@@ -90,6 +90,7 @@ set(SRC
 	intern/winstuff.c
 
 	BLI_array.h
+	BLI_bitmap.h
 	BLI_smallhash.h
 	BLI_sparsemap.h
 	BLI_args.h
diff --git a/source/blender/blenlib/intern/pbvh.c b/source/blender/blenlib/intern/pbvh.c
index 87fa4437ec1..318cd15d2e9 100644
--- a/source/blender/blenlib/intern/pbvh.c
+++ b/source/blender/blenlib/intern/pbvh.c
@@ -28,6 +28,7 @@
 
 #include "MEM_guardedalloc.h"
 
+#include "BLI_bitmap.h"
 #include "BLI_math.h"
 #include "BLI_utildefines.h"
 #include "BLI_ghash.h"
@@ -43,31 +44,6 @@
 
 //#define PERFCNTRS
 
-/* Bitmap */
-typedef char* BLI_bitmap;
-
-static BLI_bitmap BLI_bitmap_new(int tot)
-{
-	return MEM_callocN((tot >> 3) + 1, "BLI bitmap");
-}
-
-static int BLI_bitmap_get(BLI_bitmap b, int index)
-{
-	return b[index >> 3] & (1 << (index & 7));
-}
-
-static void BLI_bitmap_set(BLI_bitmap b, int index)
-{
-	b[index >> 3] |= (1 << (index & 7));
-}
-
-#if 0 /* UNUSED */
-static void BLI_bitmap_clear(BLI_bitmap b, int index)
-{
-	b[index >> 3] &= ~(1 << (index & 7));
-}
-#endif
-
 /* Axis-aligned bounding box */
 typedef struct {
 	float bmin[3], bmax[3];
@@ -343,12 +319,12 @@ static int map_insert_vert(PBVH *bvh, GHash *map,
 	void *value, *key = SET_INT_IN_POINTER(vertex);
 
 	if(!BLI_ghash_haskey(map, key)) {
-		if(BLI_bitmap_get(bvh->vert_bitmap, vertex)) {
+		if(BLI_BITMAP_GET(bvh->vert_bitmap, vertex)) {
 			value = SET_INT_IN_POINTER(~(*face_verts));
 			++(*face_verts);
 		}
 		else {
-			BLI_bitmap_set(bvh->vert_bitmap, vertex);
+			BLI_BITMAP_SET(bvh->vert_bitmap, vertex);
 			value = SET_INT_IN_POINTER(*uniq_verts);
 			++(*uniq_verts);
 		}
@@ -553,7 +529,7 @@ void BLI_pbvh_build_mesh(PBVH *bvh, MFace *faces, MVert *verts, int totface, int
 
 	bvh->faces = faces;
 	bvh->verts = verts;
-	bvh->vert_bitmap = BLI_bitmap_new(totvert);
+	bvh->vert_bitmap = BLI_BITMAP_NEW(totvert, "bvh->vert_bitmap");
 	bvh->totvert = totvert;
 	bvh->leaf_limit = LEAF_LIMIT;