From f4e031c662a6b600b786c4849968a099c58fcce7 Mon Sep 17 00:00:00 2001
From: Tom Lane <tgl@sss.pgh.pa.us>
Date: Fri, 28 Nov 2014 13:37:25 -0500
Subject: Add bms_next_member(), and use it where appropriate.

This patch adds a way of iterating through the members of a bitmapset
nondestructively, unlike the old way with bms_first_member().  While
bms_next_member() is very slightly slower than bms_first_member()
(at least for typical-size bitmapsets), eliminating the need to palloc
and pfree a temporary copy of the target bitmapset is a significant win.
So this method should be preferred in all cases where a temporary copy
would be necessary.

Tom Lane, with suggestions from Dean Rasheed and David Rowley
---
 src/backend/nodes/bitmapset.c | 68 +++++++++++++++++++++++++++++++++++++++----
 1 file changed, 63 insertions(+), 5 deletions(-)

(limited to 'src/backend/nodes/bitmapset.c')

diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index c927b7891f..26a0f872b3 100644
--- a/src/backend/nodes/bitmapset.c
+++ b/src/backend/nodes/bitmapset.c
@@ -793,7 +793,7 @@ bms_join(Bitmapset *a, Bitmapset *b)
 	return result;
 }
 
-/*----------
+/*
  * bms_first_member - find and remove first member of a set
  *
  * Returns -1 if set is empty.  NB: set is destructively modified!
@@ -801,11 +801,11 @@ bms_join(Bitmapset *a, Bitmapset *b)
  * This is intended as support for iterating through the members of a set.
  * The typical pattern is
  *
- *			tmpset = bms_copy(inputset);
- *			while ((x = bms_first_member(tmpset)) >= 0)
+ *			while ((x = bms_first_member(inputset)) >= 0)
  *				process member x;
- *			bms_free(tmpset);
- *----------
+ *
+ * CAUTION: this destroys the content of "inputset".  If the set must
+ * not be modified, use bms_next_member instead.
  */
 int
 bms_first_member(Bitmapset *a)
@@ -840,6 +840,64 @@ bms_first_member(Bitmapset *a)
 	return -1;
 }
 
+/*
+ * bms_next_member - find next member of a set
+ *
+ * Returns smallest member greater than "prevbit", or -2 if there is none.
+ * "prevbit" must NOT be less than -1, or the behavior is unpredictable.
+ *
+ * This is intended as support for iterating through the members of a set.
+ * The typical pattern is
+ *
+ *			x = -1;
+ *			while ((x = bms_next_member(inputset, x)) >= 0)
+ *				process member x;
+ *
+ * Notice that when there are no more members, we return -2, not -1 as you
+ * might expect.  The rationale for that is to allow distinguishing the
+ * loop-not-started state (x == -1) from the loop-completed state (x == -2).
+ * It makes no difference in simple loop usage, but complex iteration logic
+ * might need such an ability.
+ */
+int
+bms_next_member(const Bitmapset *a, int prevbit)
+{
+	int			nwords;
+	int			wordnum;
+	bitmapword	mask;
+
+	if (a == NULL)
+		return -2;
+	nwords = a->nwords;
+	prevbit++;
+	mask = (~(bitmapword) 0) << BITNUM(prevbit);
+	for (wordnum = WORDNUM(prevbit); wordnum < nwords; wordnum++)
+	{
+		bitmapword	w = a->words[wordnum];
+
+		/* ignore bits before prevbit */
+		w &= mask;
+
+		if (w != 0)
+		{
+			int			result;
+
+			result = wordnum * BITS_PER_BITMAPWORD;
+			while ((w & 255) == 0)
+			{
+				w >>= 8;
+				result += 8;
+			}
+			result += rightmost_one_pos[w & 255];
+			return result;
+		}
+
+		/* in subsequent words, consider all bits */
+		mask = (~(bitmapword) 0);
+	}
+	return -2;
+}
+
 /*
  * bms_hash_value - compute a hash key for a Bitmapset
  *
-- 
cgit v1.2.1