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

2 files changed, 57 insertions, 0 deletions

diff --git a/tests/gtests/blenlib/BLI_ghash_performance_test.cc b/tests/gtests/blenlib/BLI_ghash_performance_test.cc
index 817f0b3d10a..709302db021 100644
--- a/tests/gtests/blenlib/BLI_ghash_performance_test.cc
+++ b/tests/gtests/blenlib/BLI_ghash_performance_test.cc
@@ -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);
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);
+}