diff options
author | Bastien Montagne <montagne29@wanadoo.fr> | 2016-02-20 17:17:40 +0300 |
---|---|---|
committer | Bastien Montagne <montagne29@wanadoo.fr> | 2016-02-20 17:28:25 +0300 |
commit | fe9b21a44ad25f068da88f6e12b60c1486be3605 (patch) | |
tree | f2ff785c3a59efa3f756ba0042262b332a0930d9 /tests/gtests/blenlib/BLI_ghash_test.cc | |
parent | 90e77c871b771ad9df23c3e3c9b255d75c409b60 (diff) |
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
Diffstat (limited to 'tests/gtests/blenlib/BLI_ghash_test.cc')
-rw-r--r-- | tests/gtests/blenlib/BLI_ghash_test.cc | 42 |
1 files changed, 42 insertions, 0 deletions
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); +} |