blender
/
blender
129
398
Fork 572
Code Issues 6.2k Pull Requests 747 Projects 19 Wiki Activity

Add GHash/GSet pop() feature. 

Behavior is similar to python's set.pop(), it removes and returns a 'random' entry from the hash.

Notes:
* Popping will return items in same order as ghash/gset iterators (i.e. increasing
  order in internal buckets-based storage), unless ghash/gset is modified in between.
* We are keeping a track of the latest bucket we popped out (through a 'state' parameter),
  this allows for similar performances to iterators when iteratively popping a whole hash
  (without it, we are roughly O(n!), with it we are roughly O(n)...).

Reviewers: campbellbarton

Differential Revision: https://developer.blender.org/D1808
This commit is contained in:
Bastien Montagne 2016-02-20 15:17:40 +01:00
parent 90e77c871b
commit fe9b21a44a
4 changed files with 177 additions and 0 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

18
source/blender/blenlib/BLI_ghash.h
View File

@ -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);

102
source/blender/blenlib/intern/BLI_ghash.c
View File

@ -166,6 +166,31 @@ BLI_INLINE unsigned int ghash_bucket_index(GHash *gh, const unsigned int hash)
#endif
}
/**
* 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.
*/
@ -571,6 +596,29 @@ static Entry *ghash_remove_ex(
return e;
}
/**
* 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.
*/
@ -864,6 +912,35 @@ bool BLI_ghash_haskey(GHash *gh, const void *key)
return (ghash_lookup_entry(gh, key) != NULL);
}
/**
* 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.
*
@ -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)
{

15
tests/gtests/blenlib/BLI_ghash_performance_test.cc
View File

@ -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);

42
tests/gtests/blenlib/BLI_ghash_test.cc
View File

@ -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);
}