Add payload "_r" versions of bsearch and tsort

git__bsearch and git__tsort did not pass a payload through to the
comparison function.  This makes it impossible to implement sorted
lists where the sort order depends on external data (e.g. building
a secondary sort order for the entries in a tree).  This commit
adds git__bsearch_r and git__tsort_r versions that pass a third
parameter to the cmp function of a user payload.

1 files changed, 32 insertions, 1 deletions

diff --git a/src/util.c b/src/util.c
index 51173fa70..30c4dc6ce 100644
--- a/src/util.c
+++ b/src/util.c
@@ -462,7 +462,7 @@ uint32_t git__hash(const void *key, int len, uint32_t seed)
  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  * SUCH DAMAGE.
- */ 
+ */
 int git__bsearch(
 	void **array,
 	size_t array_len,
@@ -493,6 +493,37 @@ int git__bsearch(
 	return (cmp == 0) ? 0 : -1;
 }
 
+int git__bsearch_r(
+	void **array,
+	size_t array_len,
+	const void *key,
+	int (*compare_r)(const void *, const void *, void *),
+	void *payload,
+	size_t *position)
+{
+	unsigned int lim;
+	int cmp = -1;
+	void **part, **base = array;
+
+	for (lim = (unsigned int)array_len; lim != 0; lim >>= 1) {
+		part = base + (lim >> 1);
+		cmp = (*compare_r)(key, *part, payload);
+		if (cmp == 0) {
+			base = part;
+			break;
+		}
+		if (cmp > 0) { /* key > p; take right partition */
+			base = part + 1;
+			lim--;
+		} /* else take left partition */
+	}
+
+	if (position)
+		*position = (base - array);
+
+	return (cmp == 0) ? 0 : -1;
+}
+
 /**
  * A strcmp wrapper
  *