diff options
author | Campbell Barton <ideasman42@gmail.com> | 2013-08-18 07:41:39 +0400 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2013-08-18 07:41:39 +0400 |
commit | 754b4ab3bcbc92df0bcdff4848ef5ffc9410dce2 (patch) | |
tree | fa1dd64c56c0822962369d2d095f66b76f758e3a /source | |
parent | 7cce5563445a5363f9d125bf8c3cb30734cabdfe (diff) |
add hash function BLI_ghash_assign, BLI_edgehash_assign
avoids remove,insert and only hashes the key once.
Diffstat (limited to 'source')
-rw-r--r-- | source/blender/blenkernel/intern/object_deform.c | 6 | ||||
-rw-r--r-- | source/blender/blenkernel/intern/pbvh_bmesh.c | 6 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_edgehash.h | 1 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_ghash.h | 1 | ||||
-rw-r--r-- | source/blender/blenlib/intern/BLI_ghash.c | 97 | ||||
-rw-r--r-- | source/blender/blenlib/intern/edgehash.c | 99 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_log.c | 14 | ||||
-rw-r--r-- | source/blender/makesrna/intern/rna_define.c | 3 |
8 files changed, 157 insertions, 70 deletions
diff --git a/source/blender/blenkernel/intern/object_deform.c b/source/blender/blenkernel/intern/object_deform.c index bfec38419f1..ca38aa42928 100644 --- a/source/blender/blenkernel/intern/object_deform.c +++ b/source/blender/blenkernel/intern/object_deform.c @@ -100,11 +100,13 @@ bool *BKE_objdef_validmap_get(Object *ob, const int defbase_tot) 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); } } } diff --git a/source/blender/blenkernel/intern/pbvh_bmesh.c b/source/blender/blenkernel/intern/pbvh_bmesh.c index e19b71c14ed..0e2e2bcfe19 100644 --- a/source/blender/blenkernel/intern/pbvh_bmesh.c +++ b/source/blender/blenkernel/intern/pbvh_bmesh.c @@ -367,12 +367,12 @@ static void pbvh_bmesh_vert_ownership_transfer(PBVH *bvh, PBVHNode *new_owner, 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)); diff --git a/source/blender/blenlib/BLI_edgehash.h b/source/blender/blenlib/BLI_edgehash.h index 094a10eb25f..1962201c8d2 100644 --- a/source/blender/blenlib/BLI_edgehash.h +++ b/source/blender/blenlib/BLI_edgehash.h @@ -43,6 +43,7 @@ enum { 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); diff --git a/source/blender/blenlib/BLI_ghash.h b/source/blender/blenlib/BLI_ghash.h index 235afb7c8fe..97dbcc051c4 100644 --- a/source/blender/blenlib/BLI_ghash.h +++ b/source/blender/blenlib/BLI_ghash.h @@ -59,6 +59,7 @@ enum { 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); diff --git a/source/blender/blenlib/intern/BLI_ghash.c b/source/blender/blenlib/intern/BLI_ghash.c index da886e59c21..8221393d4d5 100644 --- a/source/blender/blenlib/intern/BLI_ghash.c +++ b/source/blender/blenlib/intern/BLI_ghash.c @@ -84,30 +84,35 @@ typedef struct GHash { /* -------------------------------------------------------------------- */ /* GHash API */ -GHash *BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info) -{ - GHash *gh = MEM_mallocN(sizeof(*gh), info); - gh->hashfp = hashfp; - gh->cmpfp = cmpfp; - gh->entrypool = BLI_mempool_create(sizeof(Entry), 64, 64, 0); +/* internal utility API */ - gh->cursize = 0; - gh->nentries = 0; - gh->nbuckets = hashsizes[gh->cursize]; +BLI_INLINE unsigned int ghash_keyhash(GHash *gh, const void *key) +{ + return gh->hashfp(key) % gh->nbuckets; +} - gh->buckets = MEM_callocN(gh->nbuckets * sizeof(*gh->buckets), "buckets"); +BLI_INLINE Entry *ghash_lookup_entry_ex(GHash *gh, const void *key, + const unsigned int hash) +{ + Entry *e; - 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 @@ void BLI_ghash_insert(GHash *gh, void *key, void *val) 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 @@ void BLI_ghash_insert(GHash *gh, void *key, void *val) } } -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; + } + else { + ghash_insert_ex(gh, key, val, hash); } - return NULL; } void *BLI_ghash_lookup(GHash *gh, const void *key) @@ -166,7 +211,7 @@ void **BLI_ghash_lookup_p(GHash *gh, const void *key) 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 @@ bool BLI_ghash_remove(GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFr * 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; diff --git a/source/blender/blenlib/intern/edgehash.c b/source/blender/blenlib/intern/edgehash.c index cad6271aa68..bac69183f0c 100644 --- a/source/blender/blenlib/intern/edgehash.c +++ b/source/blender/blenlib/intern/edgehash.c @@ -55,8 +55,6 @@ static const unsigned int _ehash_hashsizes[] = { 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 @@ struct EdgeHash { /* -------------------------------------------------------------------- */ /* 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; - e->next = eh->buckets[hash]; e->v0 = v0; e->v1 = v1; @@ -133,7 +142,7 @@ void BLI_edgehash_insert(EdgeHash *eh, unsigned int v0, unsigned int v1, void *v EdgeEntry *e_next; for (e = old[i]; e; e = e_next) { e_next = e->next; - hash = EDGE_HASH(e->v0, e->v1) % eh->nbuckets; + hash = edgehash_keyhash(eh, e->v0, e->v1); e->next = eh->buckets[hash]; eh->buckets[hash] = e; } @@ -143,20 +152,54 @@ void BLI_edgehash_insert(EdgeHash *eh, unsigned int v0, unsigned int v1, void *v } } -BLI_INLINE EdgeEntry *edgehash_lookup_entry(EdgeHash *eh, unsigned int v0, unsigned int v1) +#undef EDGE_HASH + + +/* Public API */ + +EdgeHash *BLI_edgehash_new(void) +{ + 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); + + return eh; +} + +/** + * 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) +{ + unsigned int hash; + EDGE_ORD(v0, v1); /* ensure v0 is smaller */ + hash = edgehash_keyhash(eh, v0, v1); + edgehash_insert_ex(eh, v0, v1, val, hash); +} + +/** + * Assign a new value to a key that may already be in edgehash. + */ +void BLI_edgehash_assign(EdgeHash *eh, unsigned int v0, unsigned int v1, void *val) { unsigned int hash; EdgeEntry *e; EDGE_ORD(v0, v1); /* ensure v0 is smaller */ + hash = edgehash_keyhash(eh, v0, v1); - hash = EDGE_HASH(v0, v1) % eh->nbuckets; - for (e = eh->buckets[hash]; e; e = e->next) { - if (v0 == e->v0 && v1 == e->v1) { - return e; - } + e = edgehash_lookup_entry_ex(eh, v0, v1, hash); + if (e) { + e->val = val; + } + else { + edgehash_insert_ex(eh, v0, v1, val, hash); } - return NULL; } /** diff --git a/source/blender/bmesh/intern/bmesh_log.c b/source/blender/bmesh/intern/bmesh_log.c index c7be4424a21..b50f35be4f3 100644 --- a/source/blender/bmesh/intern/bmesh_log.c +++ b/source/blender/bmesh/intern/bmesh_log.c @@ -117,10 +117,8 @@ static void bm_log_vert_id_set(BMLog *log, BMVert *v, unsigned int id) { void *vid = SET_INT_IN_POINTER(id); - BLI_ghash_remove(log->id_to_elem, vid, NULL, NULL); - BLI_ghash_insert(log->id_to_elem, vid, v); - BLI_ghash_remove(log->elem_to_id, v, NULL, NULL); - BLI_ghash_insert(log->elem_to_id, v, vid); + BLI_ghash_assign(log->id_to_elem, vid, v, NULL, NULL); + BLI_ghash_assign(log->elem_to_id, v, vid, NULL, NULL); } /* Get a vertex from its unique ID */ @@ -142,11 +140,9 @@ static unsigned int bm_log_face_id_get(BMLog *log, BMFace *f) static void bm_log_face_id_set(BMLog *log, BMFace *f, unsigned int id) { void *fid = SET_INT_IN_POINTER(id); - - BLI_ghash_remove(log->id_to_elem, fid, NULL, NULL); - BLI_ghash_insert(log->id_to_elem, fid, f); - BLI_ghash_remove(log->elem_to_id, f, NULL, NULL); - BLI_ghash_insert(log->elem_to_id, f, fid); + + BLI_ghash_assign(log->id_to_elem, fid, f, NULL, NULL); + BLI_ghash_assign(log->elem_to_id, f, fid, NULL, NULL); } /* Get a face from its unique ID */ diff --git a/source/blender/makesrna/intern/rna_define.c b/source/blender/makesrna/intern/rna_define.c index 723f158bb50..287d7ee2ed3 100644 --- a/source/blender/makesrna/intern/rna_define.c +++ b/source/blender/makesrna/intern/rna_define.c @@ -3207,9 +3207,8 @@ void RNA_def_property_duplicate_pointers(StructOrFunctionRNA *cont_, PropertyRNA * in the first place */ if (prop->identifier) { if (cont->prophash) { - BLI_ghash_remove(cont->prophash, (void *)prop->identifier, NULL, NULL); prop->identifier = BLI_strdup(prop->identifier); - BLI_ghash_insert(cont->prophash, (void *)prop->identifier, prop); + BLI_ghash_assign(cont->prophash, (void *)prop->identifier, prop, NULL, NULL); } else { prop->identifier = BLI_strdup(prop->identifier); |