diff options
author | Campbell Barton <ideasman42@gmail.com> | 2015-04-07 03:53:20 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2015-04-07 03:53:20 +0300 |
commit | 808de65d9124d54ce82bcb1a4d84a78b3be7288c (patch) | |
tree | 68d8d97f48e4f4ff80d760d1ce826f69d84d7f16 | |
parent | 1b9f1519bc5c8d1739371f417cc8b23a8d483c8e (diff) |
EdgeHash: ensure function, avoids multiple lookups
-rw-r--r-- | source/blender/blenlib/BLI_edgehash.h | 1 | ||||
-rw-r--r-- | source/blender/blenlib/intern/edgehash.c | 59 |
2 files changed, 60 insertions, 0 deletions
diff --git a/source/blender/blenlib/BLI_edgehash.h b/source/blender/blenlib/BLI_edgehash.h index ded4b163f71..20272dd97cd 100644 --- a/source/blender/blenlib/BLI_edgehash.h +++ b/source/blender/blenlib/BLI_edgehash.h @@ -54,6 +54,7 @@ bool BLI_edgehash_reinsert(EdgeHash *eh, unsigned int v0, unsigned in void *BLI_edgehash_lookup(EdgeHash *eh, unsigned int v0, unsigned int v1) ATTR_WARN_UNUSED_RESULT; void *BLI_edgehash_lookup_default(EdgeHash *eh, unsigned int v0, unsigned int v1, void *val_default) ATTR_WARN_UNUSED_RESULT; void **BLI_edgehash_lookup_p(EdgeHash *eh, unsigned int v0, unsigned int v1) ATTR_WARN_UNUSED_RESULT; +bool BLI_edgehash_ensure_p(EdgeHash *eh, unsigned int v0, unsigned int v1, void ***r_val) ATTR_WARN_UNUSED_RESULT; bool BLI_edgehash_remove(EdgeHash *eh, unsigned int v0, unsigned int v1, EdgeHashFreeFP valfreefp); void *BLI_edgehash_popkey(EdgeHash *eh, unsigned int v0, unsigned int v1) ATTR_WARN_UNUSED_RESULT; diff --git a/source/blender/blenlib/intern/edgehash.c b/source/blender/blenlib/intern/edgehash.c index 82d57dad753..fd7ad4db44b 100644 --- a/source/blender/blenlib/intern/edgehash.c +++ b/source/blender/blenlib/intern/edgehash.c @@ -232,6 +232,31 @@ BLI_INLINE void edgehash_insert_ex_keyonly(EdgeHash *eh, unsigned int v0, unsign EdgeEntry *e = BLI_mempool_alloc(eh->epool); BLI_assert((eh->flag & EDGEHASH_FLAG_ALLOW_DUPES) || (BLI_edgehash_haskey(eh, v0, v1) == 0)); + IS_EDGEHASH_ASSERT(eh); + + /* this helps to track down errors with bad edge data */ + BLI_assert(v0 < v1); + BLI_assert(v0 != v1); + + e->next = eh->buckets[hash]; + e->v0 = v0; + e->v1 = v1; + eh->buckets[hash] = e; + + if (UNLIKELY(edgehash_test_expand_buckets(++eh->nentries, eh->nbuckets))) { + edgehash_resize_buckets(eh, _ehash_hashsizes[++eh->cursize]); + } +} + +/** + * Insert function that doesn't set the value (use for EdgeSet) + */ +BLI_INLINE void edgehash_insert_ex_keyonly_entry( + EdgeHash *eh, unsigned int v0, unsigned int v1, + unsigned int hash, + EdgeEntry *e) +{ + 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); @@ -373,6 +398,40 @@ void **BLI_edgehash_lookup_p(EdgeHash *eh, unsigned int v0, unsigned int v1) } /** + * Ensure \a (v0, v1) is exists in \a eh. + * + * This handles the common situation where the caller needs ensure a key is added to \a eh, + * constructing a new value in the case the key isn't found. + * Otherwise use the existing value. + * + * Such situations typically incur multiple lookups, however this function + * avoids them by ensuring the key is added, + * returning a pointer to the value so it can be used or initialized by the caller. + * + * \returns true when the value didn't need to be added. + * (when false, the caller _must_ initialize the value). + */ +bool BLI_edgehash_ensure_p(EdgeHash *eh, unsigned int v0, unsigned int v1, void ***r_val) +{ + unsigned int hash; + EdgeEntry *e; + bool haskey; + + EDGE_ORD(v0, v1); /* ensure v0 is smaller */ + hash = edgehash_keyhash(eh, v0, v1); + e = edgehash_lookup_entry_ex(eh, v0, v1, hash); + haskey = (e != NULL); + + if (!haskey) { + e = BLI_mempool_alloc(eh->epool); + edgehash_insert_ex_keyonly_entry(eh, v0, v1, hash, e); + } + + *r_val = &e->val; + return haskey; +} + +/** * Return value for given edge (\a v0, \a v1), or NULL if * if key does not exist in hash. (If need exists * to differentiate between key-value being NULL and |