Add GHash/GSet pop() feature.
authorBastien Montagne <montagne29@wanadoo.fr>
Sat, 20 Feb 2016 14:17:40 +0000 (15:17 +0100)
committerBastien Montagne <montagne29@wanadoo.fr>
Sat, 20 Feb 2016 14:28:25 +0000 (15:28 +0100)
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

source/blender/blenlib/BLI_ghash.h
source/blender/blenlib/intern/BLI_ghash.c
tests/gtests/blenlib/BLI_ghash_performance_test.cc
tests/gtests/blenlib/BLI_ghash_test.cc

index 9503da6e53e4764b72c73d753db454dc57636456..f13e8cb2ae8b1faeea74f77baa981e32276cda59 100644 (file)
 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);
index 29b07b3793289c16b43c84483d4f7d17024dec36..21b0a5860afda548d33594c3108f7989e08721d1 100644 (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)
 {
index 817f0b3d10a9d41d4b9691e2da9959d961302816..709302db021e629c505b5d0c355b339774d94a30 100644 (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);
index 5fe43d14cbedfaf3f25e04b71f699eeb701f7f28..ffbe5f5547f98b1375958e4e757965a8f51d408e 100644 (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);
+}