Welcome to mirror list, hosted at ThFree Co, Russian Federation.

git.blender.org/blender.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
path: root/source/blender/blenlib/intern/edgehash.c
diff options
context:
space:
mode:
Diffstat (limited to 'source/blender/blenlib/intern/edgehash.c')
-rw-r--r--source/blender/blenlib/intern/edgehash.c180
1 files changed, 94 insertions, 86 deletions
diff --git a/source/blender/blenlib/intern/edgehash.c b/source/blender/blenlib/intern/edgehash.c
index cde4a8bf59d..358b5b5696f 100644
--- a/source/blender/blenlib/intern/edgehash.c
+++ b/source/blender/blenlib/intern/edgehash.c
@@ -88,9 +88,9 @@ struct EdgeHash {
* \{ */
/**
- * Get the hash for a key.
+ * Compute the hash and get the bucket-index.
*/
-BLI_INLINE unsigned int edgehash_keyhash(EdgeHash *eh, unsigned int v0, unsigned int v1)
+BLI_INLINE unsigned int edgehash_bucket_index(EdgeHash *eh, unsigned int v0, unsigned int v1)
{
BLI_assert(v0 < v1);
@@ -114,7 +114,6 @@ BLI_INLINE void edgehash_resize_buckets(EdgeHash *eh, const unsigned int nbucket
EdgeEntry **buckets_new;
const unsigned int nbuckets_old = eh->nbuckets;
unsigned int i;
- EdgeEntry *e;
BLI_assert(eh->nbuckets != nbuckets);
@@ -122,12 +121,11 @@ BLI_INLINE void edgehash_resize_buckets(EdgeHash *eh, const unsigned int nbucket
buckets_new = MEM_callocN(eh->nbuckets * sizeof(*eh->buckets), "eh buckets");
for (i = 0; i < nbuckets_old; i++) {
- EdgeEntry *e_next;
- for (e = buckets_old[i]; e; e = e_next) {
- const unsigned hash = edgehash_keyhash(eh, e->v0, e->v1);
+ for (EdgeEntry *e = buckets_old[i], *e_next; e; e = e_next) {
+ const unsigned bucket_index = edgehash_bucket_index(eh, e->v0, e->v1);
e_next = e->next;
- e->next = buckets_new[hash];
- buckets_new[hash] = e;
+ e->next = buckets_new[bucket_index];
+ buckets_new[bucket_index] = e;
}
}
@@ -147,14 +145,15 @@ BLI_INLINE void edgehash_buckets_reserve(EdgeHash *eh, const unsigned int nentri
/**
* Internal lookup function.
- * Takes a hash argument to avoid calling #edgehash_keyhash multiple times.
+ * Takes a \a bucket_index argument to avoid calling #edgehash_bucket_index multiple times.
*/
-BLI_INLINE EdgeEntry *edgehash_lookup_entry_ex(EdgeHash *eh, unsigned int v0, unsigned int v1,
- const unsigned int hash)
+BLI_INLINE EdgeEntry *edgehash_lookup_entry_ex(
+ EdgeHash *eh, unsigned int v0, unsigned int v1,
+ const unsigned int bucket_index)
{
EdgeEntry *e;
BLI_assert(v0 < v1);
- for (e = eh->buckets[hash]; e; e = e->next) {
+ for (e = eh->buckets[bucket_index]; e; e = e->next) {
if (UNLIKELY(v0 == e->v0 && v1 == e->v1)) {
return e;
}
@@ -163,14 +162,34 @@ BLI_INLINE EdgeEntry *edgehash_lookup_entry_ex(EdgeHash *eh, unsigned int v0, un
}
/**
+ * Internal lookup function, returns previous entry of target one too.
+ * Takes bucket_index argument to avoid calling #edgehash_bucket_index multiple times.
+ * Useful when modifying buckets somehow (like removing an entry...).
+ */
+BLI_INLINE EdgeEntry *edgehash_lookup_entry_prev_ex(
+ EdgeHash *eh, unsigned int v0, unsigned int v1,
+ EdgeEntry **r_e_prev, const unsigned int bucket_index)
+{
+ BLI_assert(v0 < v1);
+ for (EdgeEntry *e_prev = NULL, *e = eh->buckets[bucket_index]; e; e_prev = e, e = e->next) {
+ if (UNLIKELY(v0 == e->v0 && v1 == e->v1)) {
+ *r_e_prev = e_prev;
+ return e;
+ }
+ }
+
+ *r_e_prev = NULL;
+ return NULL;
+}
+
+/**
* Internal lookup function. Only wraps #edgehash_lookup_entry_ex
*/
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);
+ EDGE_ORD(v0, v1);
+ const unsigned int bucket_index = edgehash_bucket_index(eh, v0, v1);
+ return edgehash_lookup_entry_ex(eh, v0, v1, bucket_index);
}
@@ -198,10 +217,11 @@ static EdgeHash *edgehash_new(const char *info,
/**
* Internal insert function.
- * Takes a hash argument to avoid calling #edgehash_keyhash multiple times.
+ * Takes a \a bucket_index argument to avoid calling #edgehash_bucket_index multiple times.
*/
-BLI_INLINE void edgehash_insert_ex(EdgeHash *eh, unsigned int v0, unsigned int v1, void *val,
- unsigned int hash)
+BLI_INLINE void edgehash_insert_ex(
+ EdgeHash *eh, unsigned int v0, unsigned int v1, void *val,
+ const unsigned int bucket_index)
{
EdgeEntry *e = BLI_mempool_alloc(eh->epool);
@@ -212,11 +232,11 @@ BLI_INLINE void edgehash_insert_ex(EdgeHash *eh, unsigned int v0, unsigned int v
BLI_assert(v0 < v1);
BLI_assert(v0 != v1);
- e->next = eh->buckets[hash];
+ e->next = eh->buckets[bucket_index];
e->v0 = v0;
e->v1 = v1;
e->val = val;
- eh->buckets[hash] = e;
+ eh->buckets[bucket_index] = e;
if (UNLIKELY(edgehash_test_expand_buckets(++eh->nentries, eh->nbuckets))) {
edgehash_resize_buckets(eh, _ehash_hashsizes[++eh->cursize]);
@@ -226,8 +246,9 @@ BLI_INLINE void edgehash_insert_ex(EdgeHash *eh, unsigned int v0, unsigned int v
/**
* Insert function that doesn't set the value (use for EdgeSet)
*/
-BLI_INLINE void edgehash_insert_ex_keyonly(EdgeHash *eh, unsigned int v0, unsigned int v1,
- unsigned int hash)
+BLI_INLINE void edgehash_insert_ex_keyonly(
+ EdgeHash *eh, unsigned int v0, unsigned int v1,
+ const unsigned int bucket_index)
{
EdgeEntry *e = BLI_mempool_alloc(eh->epool);
@@ -237,10 +258,10 @@ BLI_INLINE void edgehash_insert_ex_keyonly(EdgeHash *eh, unsigned int v0, unsign
BLI_assert(v0 < v1);
BLI_assert(v0 != v1);
- e->next = eh->buckets[hash];
+ e->next = eh->buckets[bucket_index];
e->v0 = v0;
e->v1 = v1;
- eh->buckets[hash] = e;
+ eh->buckets[bucket_index] = e;
if (UNLIKELY(edgehash_test_expand_buckets(++eh->nentries, eh->nbuckets))) {
edgehash_resize_buckets(eh, _ehash_hashsizes[++eh->cursize]);
@@ -252,7 +273,7 @@ BLI_INLINE void edgehash_insert_ex_keyonly(EdgeHash *eh, unsigned int v0, unsign
*/
BLI_INLINE void edgehash_insert_ex_keyonly_entry(
EdgeHash *eh, unsigned int v0, unsigned int v1,
- unsigned int hash,
+ const unsigned int bucket_index,
EdgeEntry *e)
{
BLI_assert((eh->flag & EDGEHASH_FLAG_ALLOW_DUPES) || (BLI_edgehash_haskey(eh, v0, v1) == 0));
@@ -261,11 +282,11 @@ BLI_INLINE void edgehash_insert_ex_keyonly_entry(
BLI_assert(v0 < v1);
BLI_assert(v0 != v1);
- e->next = eh->buckets[hash];
+ e->next = eh->buckets[bucket_index];
e->v0 = v0;
e->v1 = v1;
/* intentionally leave value unset */
- eh->buckets[hash] = e;
+ eh->buckets[bucket_index] = e;
if (UNLIKELY(edgehash_test_expand_buckets(++eh->nentries, eh->nbuckets))) {
edgehash_resize_buckets(eh, _ehash_hashsizes[++eh->cursize]);
@@ -274,39 +295,43 @@ BLI_INLINE void edgehash_insert_ex_keyonly_entry(
BLI_INLINE void 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);
+ EDGE_ORD(v0, v1);
+ const unsigned int bucket_index = edgehash_bucket_index(eh, v0, v1);
+ edgehash_insert_ex(eh, v0, v1, val, bucket_index);
}
/**
* Remove the entry and return it, caller must free from eh->epool.
*/
-static EdgeEntry *edgehash_remove_ex(EdgeHash *eh, unsigned int v0, unsigned int v1, EdgeHashFreeFP valfreefp,
- unsigned int hash)
+BLI_INLINE EdgeEntry *edgehash_remove_ex(
+ EdgeHash *eh, unsigned int v0, unsigned int v1,
+ EdgeHashFreeFP valfreefp,
+ const unsigned int bucket_index)
{
- EdgeEntry *e;
- EdgeEntry *e_prev = NULL;
+ EdgeEntry *e_prev;
+ EdgeEntry *e = edgehash_lookup_entry_prev_ex(eh, v0, v1, &e_prev, bucket_index);
BLI_assert(v0 < v1);
- for (e = eh->buckets[hash]; e; e = e->next) {
- if (UNLIKELY(v0 == e->v0 && v1 == e->v1)) {
- EdgeEntry *e_next = e->next;
-
- if (valfreefp) valfreefp(e->val);
+ if (e) {
+ EdgeEntry *e_next = e->next;
- if (e_prev) e_prev->next = e_next;
- else eh->buckets[hash] = e_next;
+ if (valfreefp) {
+ valfreefp(e->val);
+ }
- eh->nentries--;
- return e;
+ if (e_prev) {
+ e_prev->next = e_next;
+ }
+ else {
+ eh->buckets[bucket_index] = e_next;
}
- e_prev = e;
+
+ eh->nentries--;
+ return e;
}
- return NULL;
+ return e;
}
/**
@@ -366,21 +391,18 @@ void BLI_edgehash_insert(EdgeHash *eh, unsigned int v0, unsigned int v1, void *v
*/
bool BLI_edgehash_reinsert(EdgeHash *eh, unsigned int v0, unsigned int v1, void *val)
{
- unsigned int hash;
- EdgeEntry *e;
-
IS_EDGEHASH_ASSERT(eh);
- EDGE_ORD(v0, v1); /* ensure v0 is smaller */
- hash = edgehash_keyhash(eh, v0, v1);
+ EDGE_ORD(v0, v1);
+ const unsigned int bucket_index = edgehash_bucket_index(eh, v0, v1);
- e = edgehash_lookup_entry_ex(eh, v0, v1, hash);
+ EdgeEntry *e = edgehash_lookup_entry_ex(eh, v0, v1, bucket_index);
if (e) {
e->val = val;
return false;
}
else {
- edgehash_insert_ex(eh, v0, v1, val, hash);
+ edgehash_insert_ex(eh, v0, v1, val, bucket_index);
return true;
}
}
@@ -412,18 +434,14 @@ void **BLI_edgehash_lookup_p(EdgeHash *eh, unsigned int v0, unsigned int v1)
*/
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);
+ EDGE_ORD(v0, v1);
+ const unsigned int bucket_index = edgehash_bucket_index(eh, v0, v1);
+ EdgeEntry *e = edgehash_lookup_entry_ex(eh, v0, v1, bucket_index);
+ const bool haskey = (e != NULL);
if (!haskey) {
e = BLI_mempool_alloc(eh->epool);
- edgehash_insert_ex_keyonly_entry(eh, v0, v1, hash, e);
+ edgehash_insert_ex_keyonly_entry(eh, v0, v1, bucket_index, e);
}
*r_val = &e->val;
@@ -462,12 +480,9 @@ void *BLI_edgehash_lookup_default(EdgeHash *eh, unsigned int v0, unsigned int v1
*/
bool BLI_edgehash_remove(EdgeHash *eh, unsigned int v0, unsigned int v1, EdgeHashFreeFP valfreefp)
{
- unsigned int hash;
- EdgeEntry *e;
-
- EDGE_ORD(v0, v1); /* ensure v0 is smaller */
- hash = edgehash_keyhash(eh, v0, v1);
- e = edgehash_remove_ex(eh, v0, v1, valfreefp, hash);
+ EDGE_ORD(v0, v1);
+ const unsigned int bucket_index = edgehash_bucket_index(eh, v0, v1);
+ EdgeEntry *e = edgehash_remove_ex(eh, v0, v1, valfreefp, bucket_index);
if (e) {
BLI_mempool_free(eh->epool, e);
return true;
@@ -487,12 +502,9 @@ bool BLI_edgehash_remove(EdgeHash *eh, unsigned int v0, unsigned int v1, EdgeHas
*/
void *BLI_edgehash_popkey(EdgeHash *eh, unsigned int v0, unsigned int v1)
{
- unsigned int hash;
- EdgeEntry *e;
-
- EDGE_ORD(v0, v1); /* ensure v0 is smaller */
- hash = edgehash_keyhash(eh, v0, v1);
- e = edgehash_remove_ex(eh, v0, v1, NULL, hash);
+ EDGE_ORD(v0, v1);
+ const unsigned int bucket_index = edgehash_bucket_index(eh, v0, v1);
+ EdgeEntry *e = edgehash_remove_ex(eh, v0, v1, NULL, bucket_index);
IS_EDGEHASH_ASSERT(eh);
if (e) {
void *val = e->val;
@@ -728,10 +740,9 @@ int BLI_edgeset_size(EdgeSet *es)
*/
void BLI_edgeset_insert(EdgeSet *es, unsigned int v0, unsigned int v1)
{
- unsigned int hash;
- EDGE_ORD(v0, v1); /* ensure v0 is smaller */
- hash = edgehash_keyhash((EdgeHash *)es, v0, v1);
- edgehash_insert_ex_keyonly((EdgeHash *)es, v0, v1, hash);
+ EDGE_ORD(v0, v1);
+ const unsigned int bucket_index = edgehash_bucket_index((EdgeHash *)es, v0, v1);
+ edgehash_insert_ex_keyonly((EdgeHash *)es, v0, v1, bucket_index);
}
/**
@@ -742,18 +753,15 @@ void BLI_edgeset_insert(EdgeSet *es, unsigned int v0, unsigned int v1)
*/
bool BLI_edgeset_add(EdgeSet *es, unsigned int v0, unsigned int v1)
{
- unsigned int hash;
- EdgeEntry *e;
-
- EDGE_ORD(v0, v1); /* ensure v0 is smaller */
- hash = edgehash_keyhash((EdgeHash *)es, v0, v1);
+ EDGE_ORD(v0, v1);
+ const unsigned int bucket_index = edgehash_bucket_index((EdgeHash *)es, v0, v1);
- e = edgehash_lookup_entry_ex((EdgeHash *)es, v0, v1, hash);
+ EdgeEntry *e = edgehash_lookup_entry_ex((EdgeHash *)es, v0, v1, bucket_index);
if (e) {
return false;
}
else {
- edgehash_insert_ex_keyonly((EdgeHash *)es, v0, v1, hash);
+ edgehash_insert_ex_keyonly((EdgeHash *)es, v0, v1, bucket_index);
return true;
}
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-15 12:02:23 +0300