1 files changed, 52 insertions, 0 deletions
diff --git a/src/lib/bsearch-insert-pos.h b/src/lib/bsearch-insert-pos.h
new file mode 100644
index 0000000..320182b
--- /dev/null
+++ b/src/lib/bsearch-insert-pos.h
@@ -0,0 +1,52 @@
+#ifndef BSEARCH_INSERT_POS_H
+#define BSEARCH_INSERT_POS_H
+
+/* Binary search template - getdata must be the name of a pure function
+   or a function-like macro that takes the two obvious parameters. */
+#define BINARY_NUMERIC_SEARCH(getdata, data, count, value, idx_r)	\
+	unsigned int idx, left_idx, right_idx;        \
+						      \
+	i_assert((count) < INT_MAX);                  \
+	left_idx = 0; right_idx = (count);	      \
+	while (left_idx < right_idx) {                \
+		idx = (left_idx + right_idx) / 2;     \
+						      \
+		if (getdata(data, idx) < (value))     \
+			left_idx = idx+1;             \
+		else if (getdata(data, idx) > (value))\
+			right_idx = idx;              \
+		else {                                \
+			*(idx_r) = idx;               \
+			return TRUE;                  \
+		}                                     \
+	}                                             \
+	return FALSE
+
+#define BINARY_SEARCH_ARRAY_GET(array, index) ((array)[(index)])
+#define BINARY_NUMBER_SEARCH(data, count, value, idx_r)			\
+	BINARY_NUMERIC_SEARCH(BINARY_SEARCH_ARRAY_GET, data, count, value, idx_r);
+
+/* If key is found, returns TRUE and sets idx_r to the position where the key
+   was found. If key isn't found, returns FALSE and sets idx_r to the position
+   where the key should be inserted. */
+bool ATTR_NOWARN_UNUSED_RESULT
+bsearch_insert_pos(const void *key, const void *base, unsigned int nmemb,
+		   size_t size, int (*cmp)(const void *, const void *),
+		   unsigned int *idx_r);
+#define bsearch_insert_pos(key, base, nmemb, size, cmp, idx_r) \
+	bsearch_insert_pos(key, base, nmemb, size - \
+		CALLBACK_TYPECHECK(cmp, int (*)(typeof(const typeof(*key) *), \
+						typeof(const typeof(*base) *))), \
+		(int (*)(const void *, const void *))cmp, idx_r)
+
+bool ATTR_NOWARN_UNUSED_RESULT
+array_bsearch_insert_pos_i(const struct array *array, const void *key,
+			   int (*cmp)(const void *, const void *),
+			   unsigned int *idx_r);
+#define array_bsearch_insert_pos(array, key, cmp, idx_r) \
+	array_bsearch_insert_pos_i(&(array)->arr - \
+		CALLBACK_TYPECHECK(cmp, int (*)(typeof(const typeof(*key) *), \
+						typeof(*(array)->v))), \
+		(const void *)key, (int (*)(const void *, const void *))cmp, idx_r)
+
+#endif