[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [59225] trunk/blender/source/blender: add hash function BLI_ghash_assign, BLI_edgehash_assign
Campbell Barton
ideasman42 at gmail.com
Sun Aug 18 05:41:40 CEST 2013
Revision: 59225
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=59225
Author: campbellbarton
Date: 2013-08-18 03:41:39 +0000 (Sun, 18 Aug 2013)
Log Message:
-----------
add hash function BLI_ghash_assign, BLI_edgehash_assign
avoids remove,insert and only hashes the key once.
Modified Paths:
--------------
trunk/blender/source/blender/blenkernel/intern/object_deform.c
trunk/blender/source/blender/blenkernel/intern/pbvh_bmesh.c
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
trunk/blender/source/blender/bmesh/intern/bmesh_log.c
trunk/blender/source/blender/makesrna/intern/rna_define.c
Modified: trunk/blender/source/blender/blenkernel/intern/object_deform.c
===================================================================
--- trunk/blender/source/blender/blenkernel/intern/object_deform.c 2013-08-18 02:35:39 UTC (rev 59224)
+++ trunk/blender/source/blender/blenkernel/intern/object_deform.c 2013-08-18 03:41:39 UTC (rev 59225)
@@ -100,11 +100,13 @@
bPoseChannel *chan;
for (chan = pose->chanbase.first; chan; chan = chan->next) {
+ void **val_p;
if (chan->bone->flag & BONE_NO_DEFORM)
continue;
- if (BLI_ghash_remove(gh, chan->name, NULL, NULL)) {
- BLI_ghash_insert(gh, chan->name, SET_INT_IN_POINTER(1));
+ val_p = BLI_ghash_lookup_p(gh, chan->name);
+ if (val_p) {
+ *val_p = SET_INT_IN_POINTER(1);
}
}
}
Modified: trunk/blender/source/blender/blenkernel/intern/pbvh_bmesh.c
===================================================================
--- trunk/blender/source/blender/blenkernel/intern/pbvh_bmesh.c 2013-08-18 02:35:39 UTC (rev 59224)
+++ trunk/blender/source/blender/blenkernel/intern/pbvh_bmesh.c 2013-08-18 03:41:39 UTC (rev 59225)
@@ -367,12 +367,12 @@
BLI_assert(current_owner != new_owner);
/* Remove current ownership */
- BLI_ghash_remove(bvh->bm_vert_to_node, v, NULL, NULL);
+ // BLI_ghash_remove(bvh->bm_vert_to_node, v, NULL, NULL); // assign handles below
BLI_ghash_remove(current_owner->bm_unique_verts, v, NULL, NULL);
/* Set new ownership */
- BLI_ghash_insert(bvh->bm_vert_to_node, v,
- SET_INT_IN_POINTER(new_owner - bvh->nodes));
+ BLI_ghash_assign(bvh->bm_vert_to_node, v,
+ SET_INT_IN_POINTER(new_owner - bvh->nodes), NULL, NULL);
BLI_ghash_insert(new_owner->bm_unique_verts, v, NULL);
BLI_ghash_remove(new_owner->bm_other_verts, v, NULL, NULL);
BLI_assert(!BLI_ghash_haskey(new_owner->bm_other_verts, v));
Modified: trunk/blender/source/blender/blenlib/BLI_edgehash.h
===================================================================
--- trunk/blender/source/blender/blenlib/BLI_edgehash.h 2013-08-18 02:35:39 UTC (rev 59224)
+++ trunk/blender/source/blender/blenlib/BLI_edgehash.h 2013-08-18 03:41:39 UTC (rev 59225)
@@ -43,6 +43,7 @@
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);
+void BLI_edgehash_assign(EdgeHash *eh, unsigned int v0, unsigned int v1, void *val);
void *BLI_edgehash_lookup(EdgeHash *eh, unsigned int v0, unsigned int v1);
void **BLI_edgehash_lookup_p(EdgeHash *eh, unsigned int v0, unsigned int v1);
bool BLI_edgehash_haskey(EdgeHash *eh, unsigned int v0, unsigned int v1);
Modified: trunk/blender/source/blender/blenlib/BLI_ghash.h
===================================================================
--- trunk/blender/source/blender/blenlib/BLI_ghash.h 2013-08-18 02:35:39 UTC (rev 59224)
+++ trunk/blender/source/blender/blenlib/BLI_ghash.h 2013-08-18 03:41:39 UTC (rev 59225)
@@ -59,6 +59,7 @@
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);
+void BLI_ghash_assign(GHash *gh, void *key, void *val, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
void *BLI_ghash_lookup(GHash *gh, const void *key);
void **BLI_ghash_lookup_p(GHash *gh, const void *key);
bool BLI_ghash_remove(GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
Modified: trunk/blender/source/blender/blenlib/intern/BLI_ghash.c
===================================================================
--- trunk/blender/source/blender/blenlib/intern/BLI_ghash.c 2013-08-18 02:35:39 UTC (rev 59224)
+++ trunk/blender/source/blender/blenlib/intern/BLI_ghash.c 2013-08-18 03:41:39 UTC (rev 59225)
@@ -84,30 +84,35 @@
/* -------------------------------------------------------------------- */
/* GHash API */
-GHash *BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info)
+/* internal utility API */
+
+BLI_INLINE unsigned int ghash_keyhash(GHash *gh, const void *key)
{
- GHash *gh = MEM_mallocN(sizeof(*gh), info);
- gh->hashfp = hashfp;
- gh->cmpfp = cmpfp;
- gh->entrypool = BLI_mempool_create(sizeof(Entry), 64, 64, 0);
+ return gh->hashfp(key) % gh->nbuckets;
+}
- gh->cursize = 0;
- gh->nentries = 0;
- gh->nbuckets = hashsizes[gh->cursize];
+BLI_INLINE Entry *ghash_lookup_entry_ex(GHash *gh, const void *key,
+ const unsigned int hash)
+{
+ Entry *e;
- gh->buckets = MEM_callocN(gh->nbuckets * sizeof(*gh->buckets), "buckets");
-
- return gh;
+ for (e = gh->buckets[hash]; e; e = e->next) {
+ if (gh->cmpfp(key, e->key) == 0) {
+ return e;
+ }
+ }
+ return NULL;
}
-int BLI_ghash_size(GHash *gh)
+BLI_INLINE Entry *ghash_lookup_entry(GHash *gh, const void *key)
{
- return (int)gh->nentries;
+ const unsigned int hash = ghash_keyhash(gh, key);
+ return ghash_lookup_entry_ex(gh, key, hash);
}
-void BLI_ghash_insert(GHash *gh, void *key, void *val)
+static void ghash_insert_ex(GHash *gh, void *key, void *val,
+ unsigned int hash)
{
- unsigned int hash = gh->hashfp(key) % gh->nbuckets;
Entry *e = (Entry *)BLI_mempool_alloc(gh->entrypool);
BLI_assert((gh->flag & GHASH_FLAG_ALLOW_DUPES) || (BLI_ghash_haskey(gh, key) == 0));
@@ -129,7 +134,7 @@
Entry *e_next;
for (e = old[i]; e; e = e_next) {
e_next = e->next;
- hash = gh->hashfp(e->key) % gh->nbuckets;
+ hash = ghash_keyhash(gh, e->key);
e->next = gh->buckets[hash];
gh->buckets[hash] = e;
}
@@ -139,17 +144,57 @@
}
}
-BLI_INLINE Entry *ghash_lookup_entry(GHash *gh, const void *key)
+
+/* Public API */
+
+GHash *BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info)
{
- const unsigned int hash = gh->hashfp(key) % gh->nbuckets;
- Entry *e;
+ GHash *gh = MEM_mallocN(sizeof(*gh), info);
+ gh->hashfp = hashfp;
+ gh->cmpfp = cmpfp;
+ gh->entrypool = BLI_mempool_create(sizeof(Entry), 64, 64, 0);
- for (e = gh->buckets[hash]; e; e = e->next) {
- if (gh->cmpfp(key, e->key) == 0) {
- return e;
- }
+ gh->cursize = 0;
+ gh->nentries = 0;
+ gh->nbuckets = hashsizes[gh->cursize];
+
+ gh->buckets = MEM_callocN(gh->nbuckets * sizeof(*gh->buckets), "buckets");
+
+ return gh;
+}
+
+int BLI_ghash_size(GHash *gh)
+{
+ return (int)gh->nentries;
+}
+
+void BLI_ghash_insert(GHash *gh, void *key, void *val)
+{
+ const unsigned int hash = ghash_keyhash(gh, key);
+ ghash_insert_ex(gh, key, val, hash);
+}
+
+/**
+ * Assign a new value to a key that may already be in ghash.
+ * Avoids #BLI_ghash_remove, #BLI_ghash_insert calls (double lookups)
+ *
+ * \note We may want to have 'BLI_ghash_assign_ex' function that takes
+ * GHashKeyFreeFP & GHashValFreeFP args. for now aren't needed.
+ */
+void BLI_ghash_assign(GHash *gh, void *key, void *val, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
+{
+ const unsigned int hash = ghash_keyhash(gh, key);
+ Entry *e = ghash_lookup_entry_ex(gh, key, hash);
+ if (e) {
+ if (keyfreefp) keyfreefp(e->key);
+ if (valfreefp) valfreefp(e->val);
+
+ e->key = key;
+ e->val = val;
}
- return NULL;
+ else {
+ ghash_insert_ex(gh, key, val, hash);
+ }
}
void *BLI_ghash_lookup(GHash *gh, const void *key)
@@ -166,7 +211,7 @@
bool BLI_ghash_remove(GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
{
- unsigned int hash = gh->hashfp(key) % gh->nbuckets;
+ const unsigned int hash = ghash_keyhash(gh, key);
Entry *e;
Entry *p = NULL;
@@ -196,7 +241,7 @@
* no free value argument since it will be returned */
void *BLI_ghash_pop(GHash *gh, void *key, GHashKeyFreeFP keyfreefp)
{
- unsigned int hash = gh->hashfp(key) % gh->nbuckets;
+ const unsigned int hash = ghash_keyhash(gh, key);
Entry *e;
Entry *p = NULL;
Modified: trunk/blender/source/blender/blenlib/intern/edgehash.c
===================================================================
--- trunk/blender/source/blender/blenlib/intern/edgehash.c 2013-08-18 02:35:39 UTC (rev 59224)
+++ trunk/blender/source/blender/blenlib/intern/edgehash.c 2013-08-18 03:41:39 UTC (rev 59225)
@@ -55,8 +55,6 @@
268435459
};
-#define EDGE_HASH(v0, v1) ((v0 * 39) ^ (v1 * 31))
-
/* ensure v0 is smaller */
#define EDGE_ORD(v0, v1) \
if (v0 > v1) { \
@@ -84,37 +82,48 @@
/* -------------------------------------------------------------------- */
/* EdgeHash API */
-EdgeHash *BLI_edgehash_new(void)
+/* internal utility API */
+
+#define EDGE_HASH(v0, v1) ((v0 * 39) ^ (v1 * 31))
+
+BLI_INLINE unsigned int edgehash_keyhash(EdgeHash *eh, unsigned int v0, unsigned int v1)
{
- EdgeHash *eh = MEM_callocN(sizeof(*eh), "EdgeHash");
- eh->cursize = 0;
- eh->nentries = 0;
- 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);
+ BLI_assert(v0 < v1);
+ return EDGE_HASH(v0, v1) % eh->nbuckets;
+}
- return eh;
+BLI_INLINE EdgeEntry *edgehash_lookup_entry_ex(EdgeHash *eh, unsigned int v0, unsigned int v1,
+ const unsigned int hash)
+{
+ EdgeEntry *e;
+ BLI_assert(v0 < v1);
+ for (e = eh->buckets[hash]; e; e = e->next) {
+ if (v0 == e->v0 && v1 == e->v1) {
+ return e;
+ }
+ }
+ return NULL;
}
-/**
- * Insert edge (\a v0, \a v1) into hash with given value, does
- * not check for duplicates.
- */
-void BLI_edgehash_insert(EdgeHash *eh, unsigned int v0, unsigned int v1, void *val)
+BLI_INLINE EdgeEntry *edgehash_lookup_entry(EdgeHash *eh, unsigned int v0, unsigned int v1)
{
unsigned int hash;
+ EDGE_ORD(v0, v1); /* ensure v0 is smaller */
+ hash = edgehash_keyhash(eh, v0, v1);
+ return edgehash_lookup_entry_ex(eh, v0, v1, hash);
+}
+
+static void edgehash_insert_ex(EdgeHash *eh, unsigned int v0, unsigned int v1, void *val,
+ unsigned int hash)
+{
EdgeEntry *e = BLI_mempool_alloc(eh->epool);
BLI_assert((eh->flag & EDGEHASH_FLAG_ALLOW_DUPES) || (BLI_edgehash_haskey(eh, v0, v1) == 0));
/* this helps to track down errors with bad edge data */
+ BLI_assert(v0 < v1);
BLI_assert(v0 != v1);
- EDGE_ORD(v0, v1); /* ensure v0 is smaller */
-
- hash = EDGE_HASH(v0, v1) % eh->nbuckets;
-
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list