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, 18 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);