From d5e82ecc1467ae1fcabb72eea508b3cf6727d00a Mon Sep 17 00:00:00 2001
From: Karl Williamson <public@khwilliamson.com>
Date: Fri, 25 Nov 2011 12:49:02 -0700
Subject: [PATCH] regcomp.c: Add invlist_search()

This function does a binary search on an inversion list.  It will be
used in future commits
---
 embed.fnc |  1 +
 embed.h   |  1 +
 proto.h   |  6 ++++++
 regcomp.c | 42 ++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 50 insertions(+)

diff --git a/embed.fnc b/embed.fnc
index ce8e2e2..97b9d26 100644
--- a/embed.fnc
+++ b/embed.fnc
@@ -1372,6 +1372,7 @@ EiMR	|SV*	|invlist_clone	|NN SV* const invlist
 EiMR	|UV*	|get_invlist_iter_addr	|NN SV* invlist
 EiM	|void	|invlist_iterinit|NN SV* invlist
 EsMR	|bool	|invlist_iternext|NN SV* invlist|NN UV* start|NN UV* end
+EsMR	|IV	|invlist_search	|NN SV* const invlist|const UV cp
 #endif
 #if defined(PERL_IN_REGCOMP_C) || defined(PERL_IN_UTF8_C)
 EXpM	|void	|_invlist_intersection	|NN SV* const a|NN SV* const b|NN SV** i
diff --git a/embed.h b/embed.h
index 3bf886a..e245da5 100644
--- a/embed.h
+++ b/embed.h
@@ -915,6 +915,7 @@
 #define invlist_iternext(a,b,c)	S_invlist_iternext(aTHX_ a,b,c)
 #define invlist_len(a)		S_invlist_len(aTHX_ a)
 #define invlist_max(a)		S_invlist_max(aTHX_ a)
+#define invlist_search(a,b)	S_invlist_search(aTHX_ a,b)
 #define invlist_set_len(a,b)	S_invlist_set_len(aTHX_ a,b)
 #define invlist_trim(a)		S_invlist_trim(aTHX_ a)
 #define join_exact(a,b,c,d,e,f)	S_join_exact(aTHX_ a,b,c,d,e,f)
diff --git a/proto.h b/proto.h
index ed74a1f..e7ec154 100644
--- a/proto.h
+++ b/proto.h
@@ -6355,6 +6355,12 @@ PERL_STATIC_INLINE UV	S_invlist_max(pTHX_ SV* const invlist)
 #define PERL_ARGS_ASSERT_INVLIST_MAX	\
 	assert(invlist)
 
+STATIC IV	S_invlist_search(pTHX_ SV* const invlist, const UV cp)
+			__attribute__warn_unused_result__
+			__attribute__nonnull__(pTHX_1);
+#define PERL_ARGS_ASSERT_INVLIST_SEARCH	\
+	assert(invlist)
+
 PERL_STATIC_INLINE void	S_invlist_set_len(pTHX_ SV* const invlist, const UV len)
 			__attribute__nonnull__(pTHX_1);
 #define PERL_ARGS_ASSERT_INVLIST_SET_LEN	\
diff --git a/regcomp.c b/regcomp.c
index dc3b228..b8a4339 100644
--- a/regcomp.c
+++ b/regcomp.c
@@ -6142,6 +6142,48 @@ Perl__append_range_to_invlist(pTHX_ SV* const invlist, const UV start, const UV
     }
 }
 
+STATIC IV
+S_invlist_search(pTHX_ SV* const invlist, const UV cp)
+{
+    /* Searches the inversion list for the entry that contains the input code
+     * point <cp>.  If <cp> is not in the list, -1 is returned.  Otherwise, the
+     * return value is the index into the list's array of the range that
+     * contains <cp> */
+
+    IV low = 0;
+    IV high = invlist_len(invlist);
+    const UV * const array = invlist_array(invlist);
+
+    PERL_ARGS_ASSERT_INVLIST_SEARCH;
+
+    /* If list is empty or the code point is before the first element, return
+     * failure. */
+    if (high == 0 || cp < array[0]) {
+	return -1;
+    }
+
+    /* Binary search.  What we are looking for is <i> such that
+     *	array[i] <= cp < array[i+1]
+     * The loop below converges on the i+1. */
+    while (low < high) {
+	IV mid = (low + high) / 2;
+	if (array[mid] <= cp) {
+	    low = mid + 1;
+
+	    /* We could do this extra test to exit the loop early.
+	    if (cp < array[low]) {
+		return mid;
+	    }
+	    */
+	}
+	else { /* cp < array[mid] */
+	    high = mid;
+	}
+    }
+
+    return high - 1;
+}
+
 void
 Perl__invlist_union(pTHX_ SV* const a, SV* const b, SV** output)
 {
-- 
2.7.4