move smallhash into its own C file, was inlineing fairly large functions.

5 files changed, 308 insertions, 229 deletions

diff --git a/source/blender/blenlib/BLI_smallhash.h b/source/blender/blenlib/BLI_smallhash.h
index 2fafda9b2b8..c956b8c63ea 100755
--- a/source/blender/blenlib/BLI_smallhash.h
+++ b/source/blender/blenlib/BLI_smallhash.h
@@ -28,221 +28,46 @@
 #ifndef BLI_SMALLHASH_H
 #define BLI_SMALLHASH_H
 
-/*******a light stack-friendly hash library******
- *      (it uses stack space for smallish hash tables)     */
+/** \file BLI_smallhash.h
+ *  \ingroup bli
+ */
 
-/*based on a doubling non-chaining approach */
+/* a light stack-friendly hash library,
+ * (it uses stack space for smallish hash tables) */
 
-#include "MEM_guardedalloc.h"
-#include "BLO_sys_types.h"
-#include "BLI_utildefines.h"
-#include <string.h>
+/* based on a doubling non-chaining approach */
 
-extern unsigned int hashsizes[];
-#define NONHASH	-25436536
-typedef struct entry {uintptr_t key; void *val;} entry;
+typedef struct {
+	uintptr_t key;
+	void *val;
+} SmallHashEntry;
 
 /*how much stack space to use before dynamically allocating memory*/
 #define SMSTACKSIZE	521
 typedef struct SmallHash {
-	entry *table, _stacktable[SMSTACKSIZE], _copytable[SMSTACKSIZE];
-	entry *stacktable, *copytable;
+	SmallHashEntry *table;
+	SmallHashEntry _stacktable[SMSTACKSIZE];
+	SmallHashEntry _copytable[SMSTACKSIZE];
+	SmallHashEntry *stacktable, *copytable;
 	int used;
 	int curhash;
 	int size;
 } SmallHash;
 
-typedef struct SmallHashIter {
+typedef struct {
 	SmallHash *hash;
 	int i;
 } SmallHashIter;
 
-/*CELL_UNUSED means this cell is inside a key series, while CELL_FREE
-  means this cell terminates a key series.
-  
-  no chance of anyone shoving INT32_MAX-2 into a *val pointer, I
-  imagine.  hopefully. */
-#define CELL_UNUSED	((void*)0x7FFFFFFF)
-#define CELL_FREE	((void*)0x7FFFFFFD)
-
-#define NONZERO(n) ((n) + !(n))
-#define HASHNEXT(h, hoff) ABS(((h) + ((hoff=NONZERO(hoff*2)+1), hoff)))
-
-BM_INLINE void BLI_smallhash_init(SmallHash *hash)
-{
-	int i;
-	
-	memset(hash, 0, sizeof(*hash));
-	
-	hash->table = hash->_stacktable;
-	hash->curhash = 2;
-	hash->size = hashsizes[hash->curhash];
-	
-	hash->copytable = hash->_copytable;
-	hash->stacktable = hash->_stacktable;
-	
-	for (i=0; i<hash->size; i++) {
-		hash->table[i].val = CELL_FREE;
-	}
-}
-
-/*NOTE: does *not* free *hash itself!  only the direct data!*/
-BM_INLINE void BLI_smallhash_release(SmallHash *hash)
-{
-	if (!hash)
-		return;
-	
-	if (hash->table != hash->stacktable)
-		MEM_freeN(hash->table);
-}
-
-BM_INLINE void BLI_smallhash_insert(SmallHash *hash, uintptr_t key, void *item) 
-{
-	int h, hoff=1;
-
-	if (hash->size < hash->used*3) {
-		int newsize = hashsizes[++hash->curhash];
-		entry *tmp;
-		int i = 0;
-		
-		if (hash->table != hash->stacktable || newsize > SMSTACKSIZE) {
-			tmp = MEM_callocN(sizeof(*hash->table)*newsize, "new hashkeys");
-		} else {
-			SWAP(entry*, hash->stacktable, hash->copytable);
-			tmp = hash->stacktable;
-		}
-		
-		SWAP(entry*, tmp, hash->table);
-		
-		hash->size = newsize;
-		
-		for (i=0; i<hash->size; i++) {
-			hash->table[i].val = CELL_FREE;
-		}
-		
-		for (i=0; i<hashsizes[hash->curhash-1]; i++) {
-			if (ELEM(tmp[i].val, CELL_UNUSED, CELL_FREE))
-				continue;
-			
-			h = ABS((int)(tmp[i].key));
-			hoff = 1;
-			while (!ELEM(hash->table[h % newsize].val, CELL_UNUSED, CELL_FREE))
-				h = HASHNEXT(h, hoff);
-			
-			h %= newsize;
-			
-			hash->table[h].key = tmp[i].key;
-			hash->table[h].val = tmp[i].val;
-		}
-		
-		if (tmp != hash->stacktable && tmp != hash->copytable) {
-			MEM_freeN(tmp);
-		}
-	}
-	
-	h = ABS((int)key);
-	hoff = 1;
-	while (!ELEM(hash->table[h % hash->size].val, CELL_UNUSED, CELL_FREE))
-		h = HASHNEXT(h, hoff);
-	
-	h %= hash->size;
-	hash->table[h].key = key;
-	hash->table[h].val = item;
-	
-	hash->used++;
-}
-
-BM_INLINE void BLI_smallhash_remove(SmallHash *hash, uintptr_t key)
-{
-	int h, hoff=1;
-
-	h = ABS((int)key);
-	
-	while (hash->table[h % hash->size].key != key 
-	      || hash->table[h % hash->size].val == CELL_UNUSED)
-	{
-		if (hash->table[h % hash->size].val == CELL_FREE)
-			return;
-		h = HASHNEXT(h, hoff);
-	}
-	
-	h %= hash->size;
-	hash->table[h].key = 0;
-	hash->table[h].val = CELL_UNUSED;
-}
-
-BM_INLINE void *BLI_smallhash_lookup(SmallHash *hash, uintptr_t key)
-{
-	int h, hoff=1;
-	void *v;
-
-	h = ABS((int)key);
-	
-	if (!hash->table)
-		return NULL;
-	
-	while (hash->table[h % hash->size].key != key 
-	      || hash->table[h % hash->size].val == CELL_UNUSED)
-	{
-		if (hash->table[h % hash->size].val == CELL_FREE)
-			return NULL;
-		h = HASHNEXT(h, hoff);
-	}
-	
-	v = hash->table[h % hash->size].val;
-	if (ELEM(v, CELL_UNUSED, CELL_FREE))
-		return NULL;
-	return v;
-}
-
-
-BM_INLINE int BLI_smallhash_haskey(SmallHash *hash, uintptr_t key)
-{
-	int h = ABS((int)key);
-	int hoff =1;
-	
-	if (!hash->table)
-		return 0;
-	
-	while (hash->table[h % hash->size].key != key 
-	      || hash->table[h % hash->size].val == CELL_UNUSED)
-	{
-		if (hash->table[h % hash->size].val == CELL_FREE)
-			return 0;
-		h = HASHNEXT(h, hoff);
-	}
-	
-	return !ELEM(hash->table[h % hash->size].val, CELL_UNUSED, CELL_FREE);
-}
-
-BM_INLINE int BLI_smallhash_count(SmallHash *hash)
-{
-	return hash->used;
-}
-
-BM_INLINE void *BLI_smallhash_iternext(SmallHashIter *iter, uintptr_t *key)
-{
-	while (iter->i < iter->hash->size) {
-		if (iter->hash->table[iter->i].val != CELL_UNUSED && iter->hash->table[iter->i].val != CELL_FREE) {
-			if (key)
-				*key = iter->hash->table[iter->i].key;
-			
-			iter->i++;
-			return iter->hash->table[iter->i-1].val;
-		}
-		
-		iter->i++;
-	}
-	
-	return NULL;
-}
-
-BM_INLINE void *BLI_smallhash_iternew(SmallHash *hash, SmallHashIter *iter, uintptr_t *key) 
-{
-	iter->hash = hash;
-	iter->i = 0;
-	
-	return BLI_smallhash_iternext(iter, key);
-}
+void	BLI_smallhash_init(SmallHash *hash);
+void	BLI_smallhash_release(SmallHash *hash);
+void	BLI_smallhash_insert(SmallHash *hash, uintptr_t key, void *item);
+void	BLI_smallhash_remove(SmallHash *hash, uintptr_t key);
+void *	BLI_smallhash_lookup(SmallHash *hash, uintptr_t key);
+int		BLI_smallhash_haskey(SmallHash *hash, uintptr_t key);
+int		BLI_smallhash_count(SmallHash *hash);
+void *	BLI_smallhash_iternext(SmallHashIter *iter, uintptr_t *key);
+void *	BLI_smallhash_iternew(SmallHash *hash, SmallHashIter *iter, uintptr_t *key);
+/* void BLI_smallhash_print(SmallHash *hash); */ /* UNUSED */
 
 #endif // BLI_SMALLHASH_H
diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt
index 0fde91000b4..7ca1dba9cdc 100644
--- a/source/blender/blenlib/CMakeLists.txt
+++ b/source/blender/blenlib/CMakeLists.txt
@@ -79,6 +79,7 @@ set(SRC
 	intern/rand.c
 	intern/rct.c
 	intern/scanfill.c
+	intern/smallhash.c
 	intern/storage.c
 	intern/string.c
 	intern/threads.c
diff --git a/source/blender/blenlib/intern/smallhash.c b/source/blender/blenlib/intern/smallhash.c
new file mode 100644
index 00000000000..c78dcd415cc
--- /dev/null
+++ b/source/blender/blenlib/intern/smallhash.c
@@ -0,0 +1,280 @@
+/**
+ * ***** 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., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2008 Blender Foundation.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): Joseph Eagar.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#include "MEM_guardedalloc.h"
+#include "BLI_utildefines.h"
+#include <string.h>
+
+#include "BLI_smallhash.h"
+
+/* SMHASH_CELL_UNUSED means this cell is inside a key series,
+ * while SMHASH_CELL_FREE means this cell terminates a key series.
+ *
+ * no chance of anyone shoving INT32_MAX-2 into a *val pointer, I
+ * imagine.  hopefully.
+ *
+ * note: these have the SMHASH suffix because we may want to make them public.
+ */
+#define SMHASH_CELL_UNUSED	((void *)0x7FFFFFFF)
+#define SMHASH_CELL_FREE	((void *)0x7FFFFFFD)
+
+#define SMHASH_NONZERO(n) ((n) + !(n))
+#define SMHASH_NEXT(h, hoff) ABS(((h) + ((hoff=SMHASH_NONZERO(hoff*2)+1), hoff)))
+
+extern unsigned int hashsizes[];
+
+void BLI_smallhash_init(SmallHash *hash)
+{
+	int i;
+
+	memset(hash, 0, sizeof(*hash));
+
+	hash->table = hash->_stacktable;
+	hash->curhash = 2;
+	hash->size = hashsizes[hash->curhash];
+
+	hash->copytable = hash->_copytable;
+	hash->stacktable = hash->_stacktable;
+
+	for (i=0; i<hash->size; i++) {
+		hash->table[i].val = SMHASH_CELL_FREE;
+	}
+}
+
+/*NOTE: does *not* free *hash itself!  only the direct data!*/
+void BLI_smallhash_release(SmallHash *hash)
+{
+	if (hash == NULL) {
+		return;
+	}
+
+	if (hash->table != hash->stacktable) {
+		MEM_freeN(hash->table);
+	}
+}
+
+void BLI_smallhash_insert(SmallHash *hash, uintptr_t key, void *item)
+{
+	int h, hoff=1;
+
+	if (hash->size < hash->used * 3) {
+		int newsize = hashsizes[++hash->curhash];
+		SmallHashEntry *tmp;
+		int i = 0;
+
+		if (hash->table != hash->stacktable || newsize > SMSTACKSIZE) {
+			tmp = MEM_callocN(sizeof(*hash->table) * newsize, "new hashkeys");
+		}
+		else {
+			SWAP(SmallHashEntry *, hash->stacktable, hash->copytable);
+			tmp = hash->stacktable;
+		}
+
+		SWAP(SmallHashEntry *, tmp, hash->table);
+
+		hash->size = newsize;
+
+		for (i=0; i<hash->size; i++) {
+			hash->table[i].val = SMHASH_CELL_FREE;
+		}
+
+		for (i=0; i<hashsizes[hash->curhash-1]; i++) {
+			if (ELEM(tmp[i].val, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE)) {
+				continue;
+			}
+
+			h = ABS((int)(tmp[i].key));
+			hoff = 1;
+			while (!ELEM(hash->table[h % newsize].val, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE)) {
+				h = SMHASH_NEXT(h, hoff);
+			}
+
+			h %= newsize;
+
+			hash->table[h].key = tmp[i].key;
+			hash->table[h].val = tmp[i].val;
+		}
+
+		if (tmp != hash->stacktable && tmp != hash->copytable) {
+			MEM_freeN(tmp);
+		}
+	}
+
+	h = ABS((int)key);
+	hoff = 1;
+
+	while (!ELEM(hash->table[h % hash->size].val, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE)) {
+		h = SMHASH_NEXT(h, hoff);
+	}
+
+	h %= hash->size;
+	hash->table[h].key = key;
+	hash->table[h].val = item;
+
+	hash->used++;
+}
+
+void BLI_smallhash_remove(SmallHash *hash, uintptr_t key)
+{
+	int h, hoff=1;
+
+	h = ABS((int)key);
+
+	while ((hash->table[h % hash->size].key != key) ||
+	       (hash->table[h % hash->size].val == SMHASH_CELL_UNUSED))
+	{
+		if (hash->table[h % hash->size].val == SMHASH_CELL_FREE) {
+			return;
+		}
+
+		h = SMHASH_NEXT(h, hoff);
+	}
+
+	h %= hash->size;
+	hash->table[h].key = 0;
+	hash->table[h].val = SMHASH_CELL_UNUSED;
+}
+
+void *BLI_smallhash_lookup(SmallHash *hash, uintptr_t key)
+{
+	int h, hoff=1;
+	void *v;
+
+	h = ABS((int)key);
+
+	if (hash->table == NULL) {
+		return NULL;
+	}
+
+	while ((hash->table[h % hash->size].key != key) ||
+	       (hash->table[h % hash->size].val == SMHASH_CELL_UNUSED))
+	{
+		if (hash->table[h % hash->size].val == SMHASH_CELL_FREE) {
+			return NULL;
+		}
+
+		h = SMHASH_NEXT(h, hoff);
+	}
+
+	v = hash->table[h % hash->size].val;
+	if (ELEM(v, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE)) {
+		return NULL;
+	}
+
+	return v;
+}
+
+
+int BLI_smallhash_haskey(SmallHash *hash, uintptr_t key)
+{
+	int h = ABS((int)key);
+	int hoff =1;
+
+	if (hash->table == NULL) {
+		return 0;
+	}
+
+	while ((hash->table[h % hash->size].key != key) ||
+	       (hash->table[h % hash->size].val == SMHASH_CELL_UNUSED))
+	{
+		if (hash->table[h % hash->size].val == SMHASH_CELL_FREE) {
+			return 0;
+		}
+
+		h = SMHASH_NEXT(h, hoff);
+	}
+
+	return !ELEM(hash->table[h % hash->size].val, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE);
+}
+
+int BLI_smallhash_count(SmallHash *hash)
+{
+	return hash->used;
+}
+
+void *BLI_smallhash_iternext(SmallHashIter *iter, uintptr_t *key)
+{
+	while (iter->i < iter->hash->size) {
+		if (    (iter->hash->table[iter->i].val != SMHASH_CELL_UNUSED) &&
+		        (iter->hash->table[iter->i].val != SMHASH_CELL_FREE))
+		{
+			if (key) {
+				*key = iter->hash->table[iter->i].key;
+			}
+
+			iter->i++;
+
+			return iter->hash->table[iter->i-1].val;
+		}
+
+		iter->i++;
+	}
+
+	return NULL;
+}
+
+void *BLI_smallhash_iternew(SmallHash *hash, SmallHashIter *iter, uintptr_t *key)
+{
+	iter->hash = hash;
+	iter->i = 0;
+
+	return BLI_smallhash_iternext(iter, key);
+}
+
+/* note, this was called _print_smhash in knifetool.c
+ * it may not be intended for general use - campbell */
+#if 0
+void BLI_smallhash_print(SmallHash *hash)
+{
+	int i, linecol=79, c=0;
+
+	printf("{");
+	for (i=0; i<hash->size; i++) {
+		if (hash->table[i].val == SMHASH_CELL_UNUSED) {
+			printf("--u-");
+		}
+		else if (hash->table[i].val == SMHASH_CELL_FREE) {
+			printf("--f-");
+		}
+		else	{
+			printf("%2x", (unsigned int)hash->table[i].key);
+		}
+
+		if (i != hash->size-1)
+			printf(", ");
+
+		c += 6;
+
+		if (c >= linecol) {
+			printf("\n ");
+			c = 0;
+		}
+	}
+
+	fflush(stdout);
+}
+#endif
diff --git a/source/blender/editors/mesh/knifetool.c b/source/blender/editors/mesh/knifetool.c
index 848b395f696..6dd5da6511a 100755
--- a/source/blender/editors/mesh/knifetool.c
+++ b/source/blender/editors/mesh/knifetool.c
@@ -745,34 +745,6 @@ static void knifetool_draw(const bContext *UNUSED(C), ARegion *UNUSED(ar), void
 	glEnable(GL_DEPTH_TEST);
 }
 
-static void _print_smhash(SmallHash *hash)
-{
-	int i, linecol=79, c=0;
-	
-	printf("{");
-	for (i=0; i<hash->size; i++) {
-		if (hash->table[i].val == CELL_UNUSED) {
-			printf("--u-");
-		} else if (hash->table[i].val == CELL_FREE) {
-			printf("--f-");
-		} else	{
-			printf("%2x", (unsigned int)hash->table[i].key);
-		}
-		
-		if (i != hash->size-1)
-			printf(", ");
-		
-		c += 6;
-		
-		if (c >= linecol) {
-			printf("\n ");
-			c = 0;
-		}
-	}
-	
-	fflush(stdout);
-}
-
 static int kfe_vert_in_edge(KnifeEdge *e, KnifeVert *v) {
 	return e->v1 == v || e->v2 == v;
 }
diff --git a/source/blender/modifiers/intern/MOD_mirror.c b/source/blender/modifiers/intern/MOD_mirror.c
index d93d7aecb5d..4aa17b9762e 100644
--- a/source/blender/modifiers/intern/MOD_mirror.c
+++ b/source/blender/modifiers/intern/MOD_mirror.c
@@ -33,6 +33,8 @@
 #include "DNA_meshdata_types.h"
 #include "DNA_object_types.h"
 
+#include "MEM_guardedalloc.h"
+
 #include "BLI_math.h"
 #include "BLI_smallhash.h"
 #include "BLI_array.h"
@@ -44,7 +46,6 @@
 #include "BKE_utildefines.h"
 #include "BKE_tessmesh.h"
 
-#include "MEM_guardedalloc.h"
 #include "depsgraph_private.h"
 
 static void initData(ModifierData *md)