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

1 files changed, 102 insertions, 0 deletions

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)
 {