sparse_bsearch: new module

[ccan] / ccan / sparse_bsearch / sparse_bsearch.h

diff --git a/ccan/sparse_bsearch/sparse_bsearch.h b/ccan/sparse_bsearch/sparse_bsearch.h
new file mode 100644 (file)
index 0000000..5317dbf
--- /dev/null
+++ b/ccan/sparse_bsearch/sparse_bsearch.h
@@ -0,0 +1,50 @@
+#ifndef SPARSE_BSEARCH_H
+#define SPARSE_BSEARCH_H
+#include <stdbool.h>
+#include <stdlib.h>
+#include <ccan/typesafe_cb/typesafe_cb.h>
+#include <ccan/check_type/check_type.h>
+
+/**
+ * sparse_bsearch - binary search of a sorted array with gaps.
+ * @key: the key to search for
+ * @base: the head of the array
+ * @nmemb: the number of elements in the array
+ * @cmpfn: the compare function (qsort/bsearch style)
+ * @validfn: whether this element is valid.
+ *
+ * Binary search of a sorted array, which may have some invalid entries.
+ *
+ * Example:
+ *     static bool val_valid(unsigned int *val)
+ *     {
+ *             return *val != 0;
+ *     }
+ *     static int val_cmp(const unsigned int *a, const unsigned int *b)
+ *     {
+ *             return (int)((*a) - (*b));
+ *     }
+ *     static unsigned int values[] = { 1, 7, 11, 1235, 99999 };
+ *
+ *     // Return true if this value is in set, and remove it.
+ *     bool remove_from_values(unsigned int val)
+ *     {
+ *             unsigned int *p;
+ *             p = sparse_bsearch(&val, values, 5, val_cmp, val_valid);
+ *             if (!p)
+ *                     return false;
+ *             *p = 0;
+ *             return true;
+ *     }
+ */
+#define sparse_bsearch(key, base, nmemb, cmpfn, validfn)               \
+       _sparse_bsearch((key)+check_types_match((key), &(base)[0]),     \
+                       (base), (nmemb), sizeof((base)[0]),             \
+                       typesafe_cb_cmp(int, (cmpfn), (base)),          \
+                       typesafe_cb_const(bool, (validfn), (base)))
+
+void *_sparse_bsearch(const void *key, const void *base,
+                     size_t nmemb, size_t size,
+                     int (*cmpfn)(const void *, const void *),
+                     bool (*validfn)(const void *));
+#endif /* SPARSE_BSEARCH_H */