[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [59463] trunk/blender/source/blender/ blenlib: ghash and edgehash api, allow newly defined hashes to take in the size of the hash as an arg ( avoids resizing in simple cases when the hash is created and filled immediately ).

[Campbell Barton]

Revision: 59463
          http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=59463
Author:   campbellbarton
Date:     2013-08-24 13:04:03 +0000 (Sat, 24 Aug 2013)
Log Message:
-----------
ghash and edgehash api, allow newly defined hashes to take in the size of the hash as an arg (avoids resizing in simple cases when the hash is created and filled immediately).

Modified Paths:
--------------
    trunk/blender/source/blender/blenlib/BLI_edgehash.h
    trunk/blender/source/blender/blenlib/BLI_ghash.h
    trunk/blender/source/blender/blenlib/intern/BLI_ghash.c
    trunk/blender/source/blender/blenlib/intern/edgehash.c

Modified: trunk/blender/source/blender/blenlib/BLI_edgehash.h
===================================================================
--- trunk/blender/source/blender/blenlib/BLI_edgehash.h	2013-08-24 12:53:47 UTC (rev 59462)
+++ trunk/blender/source/blender/blenlib/BLI_edgehash.h	2013-08-24 13:04:03 UTC (rev 59463)
@@ -40,6 +40,7 @@
 	EDGEHASH_FLAG_ALLOW_DUPES = (1 << 0),  /* only checked for in debug mode */
 };
 
+EdgeHash       *BLI_edgehash_new_ex(const unsigned int nentries_reserve);
 EdgeHash       *BLI_edgehash_new(void);
 void            BLI_edgehash_free(EdgeHash *eh, EdgeHashFreeFP valfreefp);
 void            BLI_edgehash_insert(EdgeHash *eh, unsigned int v0, unsigned int v1, void *val);

Modified: trunk/blender/source/blender/blenlib/BLI_ghash.h
===================================================================
--- trunk/blender/source/blender/blenlib/BLI_ghash.h	2013-08-24 12:53:47 UTC (rev 59462)
+++ trunk/blender/source/blender/blenlib/BLI_ghash.h	2013-08-24 13:04:03 UTC (rev 59463)
@@ -58,6 +58,8 @@
 
 /* *** */
 
+GHash *BLI_ghash_new_ex(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info,
+                        const unsigned int nentries_reserve);
 GHash *BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info);
 void   BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
 void   BLI_ghash_insert(GHash *gh, void *key, void *val);

Modified: trunk/blender/source/blender/blenlib/intern/BLI_ghash.c
===================================================================
--- trunk/blender/source/blender/blenlib/intern/BLI_ghash.c	2013-08-24 12:53:47 UTC (rev 59462)
+++ trunk/blender/source/blender/blenlib/intern/BLI_ghash.c	2013-08-24 13:04:03 UTC (rev 59463)
@@ -86,6 +86,11 @@
 
 /* internal utility API */
 
+BLI_INLINE bool ghash_test_expand_buckets(const unsigned int nentries, const unsigned int nbuckets)
+{
+	return (nentries > nbuckets / 2);
+}
+
 BLI_INLINE unsigned int ghash_keyhash(GHash *gh, const void *key)
 {
 	return gh->hashfp(key) % gh->nbuckets;
@@ -122,7 +127,7 @@
 	e->val = val;
 	gh->buckets[hash] = e;
 
-	if (UNLIKELY(++gh->nentries > gh->nbuckets / 2)) {
+	if (UNLIKELY(ghash_test_expand_buckets(++gh->nentries, gh->nbuckets))) {
 		Entry **old = gh->buckets;
 		const unsigned nold = gh->nbuckets;
 		unsigned int i;
@@ -147,7 +152,8 @@
 
 /* Public API */
 
-GHash *BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info)
+GHash *BLI_ghash_new_ex(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info,
+                        const unsigned int nentries_reserve)
 {
 	GHash *gh = MEM_mallocN(sizeof(*gh), info);
 
@@ -159,12 +165,24 @@
 	gh->cursize = 0;
 	gh->flag = 0;
 
+	/* if we have reserved the number of elements that this hash will contain */
+	if (nentries_reserve) {
+		while (ghash_test_expand_buckets(nentries_reserve, gh->nbuckets)) {
+			gh->nbuckets = hashsizes[++gh->cursize];
+		}
+	}
+
 	gh->buckets = MEM_callocN(gh->nbuckets * sizeof(*gh->buckets), "buckets");
 	gh->entrypool = BLI_mempool_create(sizeof(Entry), 64, 64, 0);
 
 	return gh;
 }
 
+GHash *BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info)
+{
+	return BLI_ghash_new_ex(hashfp, cmpfp, info, 0);
+}
+
 int BLI_ghash_size(GHash *gh)
 {
 	return (int)gh->nentries;

Modified: trunk/blender/source/blender/blenlib/intern/edgehash.c
===================================================================
--- trunk/blender/source/blender/blenlib/intern/edgehash.c	2013-08-24 12:53:47 UTC (rev 59462)
+++ trunk/blender/source/blender/blenlib/intern/edgehash.c	2013-08-24 13:04:03 UTC (rev 59463)
@@ -86,6 +86,11 @@
 
 #define EDGE_HASH(v0, v1)  ((v0 * 39) ^ (v1 * 31))
 
+BLI_INLINE bool edgehash_test_expand_buckets(const unsigned int nentries, const unsigned int nbuckets)
+{
+	return (nentries > nbuckets / 2);
+}
+
 BLI_INLINE unsigned int edgehash_keyhash(EdgeHash *eh, unsigned int v0, unsigned int v1)
 {
 	BLI_assert(v0 < v1);
@@ -130,7 +135,7 @@
 	e->val = val;
 	eh->buckets[hash] = e;
 
-	if (UNLIKELY(++eh->nentries > eh->nbuckets / 2)) {
+	if (UNLIKELY(edgehash_test_expand_buckets(++eh->nentries, eh->nbuckets))) {
 		EdgeEntry **old = eh->buckets;
 		const unsigned int nold = eh->nbuckets;
 		unsigned int i;
@@ -157,7 +162,7 @@
 
 /* Public API */
 
-EdgeHash *BLI_edgehash_new(void)
+EdgeHash *BLI_edgehash_new_ex(const unsigned int nentries_reserve)
 {
 	EdgeHash *eh = MEM_callocN(sizeof(*eh), "EdgeHash");
 
@@ -166,12 +171,24 @@
 	eh->cursize = 0;
 	eh->flag = 0;
 
+	/* if we have reserved the number of elements that this hash will contain */
+	if (nentries_reserve) {
+		while (edgehash_test_expand_buckets(nentries_reserve, eh->nbuckets)) {
+			eh->nbuckets = _ehash_hashsizes[++eh->cursize];
+		}
+	}
+
 	eh->buckets = MEM_callocN(eh->nbuckets * sizeof(*eh->buckets), "eh buckets 2");
 	eh->epool = BLI_mempool_create(sizeof(EdgeEntry), 512, 512, BLI_MEMPOOL_SYSMALLOC);
 
 	return eh;
 }
 
+EdgeHash *BLI_edgehash_new(void)
+{
+	return BLI_edgehash_new_ex(0);
+}
+
 /**
  * Insert edge (\a v0, \a v1) into hash with given value, does
  * not check for duplicates.