diff options
| -rw-r--r-- | source/blender/blenlib/BLI_ghash.h | 18 | ||||
| -rw-r--r-- | source/blender/blenlib/intern/BLI_ghash.c | 102 | ||||
| -rw-r--r-- | tests/gtests/blenlib/BLI_ghash_performance_test.cc | 15 | ||||
| -rw-r--r-- | tests/gtests/blenlib/BLI_ghash_test.cc | 42 |
4 files changed, 177 insertions, 0 deletions
diff --git a/source/blender/blenlib/BLI_ghash.h b/source/blender/blenlib/BLI_ghash.h index 9503da6e53e..f13e8cb2ae8 100644 --- a/source/blender/blenlib/BLI_ghash.h +++ b/source/blender/blenlib/BLI_ghash.h @@ -39,6 +39,14 @@ extern "C" { #endif +#define _GHASH_INTERNAL_ATTR +#ifndef GHASH_INTERNAL_API +# ifdef __GNUC__ +# undef _GHASH_INTERNAL_ATTR +# define _GHASH_INTERNAL_ATTR __attribute__ ((deprecated)) +# endif +#endif + typedef unsigned int (*GHashHashFP) (const void *key); /** returns false when equal */ typedef bool (*GHashCmpFP) (const void *a, const void *b); @@ -55,6 +63,12 @@ typedef struct GHashIterator { unsigned int curBucket; } GHashIterator; +typedef struct GHashIterState { + unsigned int curr_bucket _GHASH_INTERNAL_ATTR; +} GHashIterState; + + + enum { GHASH_FLAG_ALLOW_DUPES = (1 << 0), /* Only checked for in debug mode */ GHASH_FLAG_ALLOW_SHRINK = (1 << 1), /* Allow to shrink buckets' size. */ @@ -87,6 +101,7 @@ void BLI_ghash_clear_ex(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP va const unsigned int nentries_reserve); void *BLI_ghash_popkey(GHash *gh, const void *key, GHashKeyFreeFP keyfreefp) ATTR_WARN_UNUSED_RESULT; bool BLI_ghash_haskey(GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT; +bool BLI_ghash_pop(GHash *gh, GHashIterState *state, void **r_key, void **r_val) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); unsigned int BLI_ghash_size(GHash *gh) ATTR_WARN_UNUSED_RESULT; void BLI_ghash_flag_set(GHash *gh, unsigned int flag); void BLI_ghash_flag_clear(GHash *gh, unsigned int flag); @@ -208,6 +223,8 @@ typedef GHashCmpFP GSetCmpFP; typedef GHashKeyFreeFP GSetKeyFreeFP; typedef GHashKeyCopyFP GSetKeyCopyFP; +typedef GHashIterState GSetIterState; + /* so we can cast but compiler sees as different */ typedef struct GSetIterator { GHashIterator _ghi @@ -229,6 +246,7 @@ void BLI_gset_insert(GSet *gh, void *key); bool BLI_gset_add(GSet *gs, void *key); bool BLI_gset_reinsert(GSet *gh, void *key, GSetKeyFreeFP keyfreefp); bool BLI_gset_haskey(GSet *gs, const void *key) ATTR_WARN_UNUSED_RESULT; +bool BLI_gset_pop(GSet *gs, GSetIterState *state, void **r_key) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); bool BLI_gset_remove(GSet *gs, const void *key, GSetKeyFreeFP keyfreefp); void BLI_gset_clear_ex(GSet *gs, GSetKeyFreeFP keyfreefp, const unsigned int nentries_reserve); diff --git a/source/blender/blenlib/intern/BLI_ghash.c b/source/blender/blenlib/intern/BLI_ghash.c index 29b07b37932..21b0a5860af 100644 --- a/source/blender/blenlib/intern/BLI_ghash.c +++ b/source/blender/blenlib/intern/BLI_ghash.c @@ -167,6 +167,31 @@ BLI_INLINE unsigned int ghash_bucket_index(GHash *gh, const unsigned int hash) } /** + * Find the index of next used bucket, starting from \a curr_bucket (\a gh is assumed non-empty). + */ +BLI_INLINE unsigned int ghash_find_next_bucket_index(GHash *gh, unsigned int curr_bucket) +{ + if (curr_bucket >= gh->nbuckets) { + curr_bucket = 0; + } + if (gh->buckets[curr_bucket]) { + return curr_bucket; + } + for (; curr_bucket < gh->nbuckets; curr_bucket++) { + if (gh->buckets[curr_bucket]) { + return curr_bucket; + } + } + for (curr_bucket = 0; curr_bucket < gh->nbuckets; curr_bucket++) { + if (gh->buckets[curr_bucket]) { + return curr_bucket; + } + } + BLI_assert(0); + return 0; +} + +/** * Expand buckets to the next size up or down. */ static void ghash_buckets_resize(GHash *gh, const unsigned int nbuckets) @@ -572,6 +597,29 @@ static Entry *ghash_remove_ex( } /** + * Remove a random entry and return it (or NULL if empty), caller must free from gh->entrypool. + */ +static Entry *ghash_pop(GHash *gh, GHashIterState *state) +{ + unsigned int curr_bucket = state->curr_bucket; + if (gh->nentries == 0) { + return NULL; + } + + /* Note: using first_bucket_index here allows us to avoid potential huge number of loops over buckets, + * in case we are poping from a large ghash with few items in it... */ + curr_bucket = ghash_find_next_bucket_index(gh, curr_bucket); + + Entry *e = gh->buckets[curr_bucket]; + BLI_assert(e); + + ghash_remove_ex(gh, e->key, NULL, NULL, curr_bucket); + + state->curr_bucket = curr_bucket; + return e; +} + +/** * Run free callbacks for freeing entries. */ static void ghash_free_cb( @@ -865,6 +913,35 @@ bool BLI_ghash_haskey(GHash *gh, const void *key) } /** + * Remove a random entry from \a ghp, returning true if a key/value pair could be removed, false otherwise. + * + * \param r_key: The removed key. + * \param r_val: The removed value. + * \param state: Used for efficient removal. + * \return true if there was somethjing to pop, false if ghash was already empty. + */ +bool BLI_ghash_pop( + GHash *gh, GHashIterState *state, + void **r_key, void **r_val) +{ + GHashEntry *e = (GHashEntry *)ghash_pop(gh, state); + + BLI_assert(!(gh->flag & GHASH_FLAG_IS_GSET)); + + if (e) { + *r_key = e->e.key; + *r_val = e->val; + + BLI_mempool_free(gh->entrypool, e); + return true; + } + else { + *r_key = *r_val = NULL; + return false; + } +} + +/** * Reset \a gh clearing all entries. * * \param keyfreefp Optional callback to free the key. @@ -1335,6 +1412,31 @@ bool BLI_gset_haskey(GSet *gs, const void *key) return (ghash_lookup_entry((GHash *)gs, key) != NULL); } +/** + * Remove a random entry from \a gsp, returning true if a key could be removed, false otherwise. + * + * \param r_key: The removed key. + * \param state: Used for efficient removal. + * \return true if there was somethjing to pop, false if gset was already empty. + */ +bool BLI_gset_pop( + GSet *gs, GSetIterState *state, + void **r_key) +{ + GSetEntry *e = (GSetEntry *)ghash_pop((GHash *)gs, (GHashIterState *)state); + + if (e) { + *r_key = e->key; + + BLI_mempool_free(((GHash *)gs)->entrypool, e); + return true; + } + else { + *r_key = NULL; + return false; + } +} + void BLI_gset_clear_ex(GSet *gs, GSetKeyFreeFP keyfreefp, const unsigned int nentries_reserve) { diff --git a/tests/gtests/blenlib/BLI_ghash_performance_test.cc b/tests/gtests/blenlib/BLI_ghash_performance_test.cc index 817f0b3d10a..709302db021 100644 --- a/tests/gtests/blenlib/BLI_ghash_performance_test.cc +++ b/tests/gtests/blenlib/BLI_ghash_performance_test.cc @@ -196,6 +196,21 @@ static void int_ghash_tests(GHash *ghash, const char *id, const unsigned int nbr TIMEIT_END(int_lookup); } + { + void *k, *v; + + TIMEIT_START(int_pop); + + GHashIterState pop_state = {0}; + + while (BLI_ghash_pop(ghash, &pop_state, &k, &v)) { + EXPECT_EQ(k, v); + } + + TIMEIT_END(int_pop); + } + EXPECT_EQ(0, BLI_ghash_size(ghash)); + BLI_ghash_free(ghash, NULL, NULL); printf("========== ENDED %s ==========\n\n", id); diff --git a/tests/gtests/blenlib/BLI_ghash_test.cc b/tests/gtests/blenlib/BLI_ghash_test.cc index 5fe43d14cbe..ffbe5f5547f 100644 --- a/tests/gtests/blenlib/BLI_ghash_test.cc +++ b/tests/gtests/blenlib/BLI_ghash_test.cc @@ -156,3 +156,45 @@ TEST(ghash, Copy) BLI_ghash_free(ghash, NULL, NULL); BLI_ghash_free(ghash_copy, NULL, NULL); } + +/* Check pop. */ +TEST(ghash, Pop) +{ + GHash *ghash = BLI_ghash_new(BLI_ghashutil_inthash_p, BLI_ghashutil_intcmp, __func__); + unsigned int keys[TESTCASE_SIZE], *k; + int i; + + BLI_ghash_flag_set(ghash, GHASH_FLAG_ALLOW_SHRINK); + init_keys(keys, 30); + + for (i = TESTCASE_SIZE, k = keys; i--; k++) { + BLI_ghash_insert(ghash, SET_UINT_IN_POINTER(*k), SET_UINT_IN_POINTER(*k)); + } + + EXPECT_EQ(TESTCASE_SIZE, BLI_ghash_size(ghash)); + + GHashIterState pop_state = {0}; + + for (i = TESTCASE_SIZE / 2; i--; ) { + void *k, *v; + bool success = BLI_ghash_pop(ghash, &pop_state, &k, &v); + EXPECT_EQ(k, v); + EXPECT_EQ(success, true); + + if (i % 2) { + BLI_ghash_insert(ghash, SET_UINT_IN_POINTER(i * 4), SET_UINT_IN_POINTER(i * 4)); + } + } + + EXPECT_EQ((TESTCASE_SIZE - TESTCASE_SIZE / 2 + TESTCASE_SIZE / 4), BLI_ghash_size(ghash)); + + { + void *k, *v; + while (BLI_ghash_pop(ghash, &pop_state, &k, &v)) { + EXPECT_EQ(k, v); + } + } + EXPECT_EQ(0, BLI_ghash_size(ghash)); + + BLI_ghash_free(ghash, NULL, NULL); +} |