sparse_bsearch: new module
authorRusty Russell <rusty@rustcorp.com.au>
Wed, 30 Sep 2009 03:18:11 +0000 (12:48 +0930)
committerRusty Russell <rusty@rustcorp.com.au>
Wed, 30 Sep 2009 03:18:11 +0000 (12:48 +0930)
ccan/sparse_bsearch/_info [new file with mode: 0644]
ccan/sparse_bsearch/sparse_bsearch.c [new file with mode: 0644]
ccan/sparse_bsearch/sparse_bsearch.h [new file with mode: 0644]
ccan/sparse_bsearch/test/run.c [new file with mode: 0644]

diff --git a/ccan/sparse_bsearch/_info b/ccan/sparse_bsearch/_info
new file mode 100644 (file)
index 0000000..9c5e841
--- /dev/null
@@ -0,0 +1,66 @@
+#include <string.h>
+#include <stdio.h>
+#include "config.h"
+
+/**
+ * sparse_bsearch - search a sorted array with some invalid entries
+ *
+ * bsearch() is great for searching an array, but if you are deleting from
+ * the array, you then need to memmove() to keep it dense.
+ *
+ * Sometimes there is a useful invalid value which can be used to mark deleted
+ * entries, but such a "gappy" array breaks bsearch.  This function allows
+ * "invalid" entries in your array, which are ignored for the search.
+ * 
+ * Example:
+ *     #include <ccan/sparse_bsearch/sparse_bsearch.h>
+ *
+ *     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;
+ *             // We use 5 here, but ccan/array_size.h is better!
+ *             p = sparse_bsearch(&val, values, 5, val_cmp, val_valid);
+ *             if (!p)
+ *                     return false;
+ *             *p = 0;
+ *             return true;
+ *     }
+ *
+ *     int main(int argc, char *argv[])
+ *     {
+ *             int i, val;
+ *             for (i = 1; i < argc; i++) {
+ *                     val = atoi(argv[i]);
+ *                     if (remove_from_values(val))
+ *                             printf("%i removed.\n", val);
+ *                     else
+ *                             printf("%i wasn't there.\n", val);
+ *             }
+ *             return 0;
+ *     }
+ */
+int main(int argc, char *argv[])
+{
+       /* Expect exactly one argument */
+       if (argc != 2)
+               return 1;
+
+       if (strcmp(argv[1], "depends") == 0) {
+               printf("ccan/typesafe_cb\n"
+                      "ccan/check_type\n");
+               return 0;
+       }
+
+       return 1;
+}
diff --git a/ccan/sparse_bsearch/sparse_bsearch.c b/ccan/sparse_bsearch/sparse_bsearch.c
new file mode 100644 (file)
index 0000000..f0d58d2
--- /dev/null
@@ -0,0 +1,36 @@
+#include "sparse_bsearch.h"
+
+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 *))
+{
+       ssize_t start = 0, end = nmemb - 1;
+       const char *p = base;
+
+       while (start <= end) {
+               ssize_t next = (start + end) / 2;
+               int result;
+
+               while (!validfn(p + next * size)) {
+                       /* Try the next one along. */
+                       next++;
+                       if (next > end) {
+                               /* Hmm, none of these were valid. */
+                               next = (start + end) / 2;
+                               goto trim;
+                       }
+               }
+
+               result = cmpfn(key, p + next * size);
+               if (result == 0)
+                       return (void *)(p + next * size);
+               else if (result > 0)
+                       start = next + 1;
+               else {
+               trim:
+                       end = next - 1;
+               }
+       }
+       return NULL;
+}
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
@@ -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 */
diff --git a/ccan/sparse_bsearch/test/run.c b/ccan/sparse_bsearch/test/run.c
new file mode 100644 (file)
index 0000000..3acb3ad
--- /dev/null
@@ -0,0 +1,64 @@
+/* Include the main header first, to test it works */
+#include <ccan/sparse_bsearch/sparse_bsearch.h>
+/* Include the C files directly. */
+#include <ccan/sparse_bsearch/sparse_bsearch.c>
+#include <ccan/tap/tap.h>
+
+static int cmp(const unsigned int *a, const unsigned int *b)
+{
+       return (*a) - (*b);
+}
+
+static bool valid(const unsigned int *a)
+{
+       return *a != 0;
+}
+
+int main(void)
+{
+       unsigned int i, j, master[4] = { 1, 2, 3, 4 }, arr[4];
+
+       plan_tests((1 << 4) * 4+ (1 << 3) * 3);
+
+       /* We test all possibilities of an even and an odd array len. */
+       for (i = 0; i < (1 << 4); i++) {
+               /* Setup partial arr[] */
+               for (j = 0; j < 4; j++) {
+                       if (i & (1 << j))
+                               arr[j] = master[j];
+                       else
+                               arr[j] = 0;
+               }
+
+               for (j = 1; j <= 4; j++) {
+                       unsigned int *ptr;
+                       ptr = sparse_bsearch(&j, arr, 4, cmp, valid);
+                       if (i & (1 << (j-1)))
+                               ok1(ptr && *ptr == j);
+                       else
+                               ok1(!ptr);
+               }
+       }
+
+       for (i = 0; i < (1 << 3); i++) {
+               /* Setup partial arr[] */
+               for (j = 0; j < 3; j++) {
+                       if (i & (1 << j))
+                               arr[j] = master[j];
+                       else
+                               arr[j] = 0;
+               }
+
+               for (j = 1; j <= 3; j++) {
+                       unsigned int *ptr;
+                       ptr = sparse_bsearch(&j, arr, 3, cmp, valid);
+                       if (i & (1 << (j-1)))
+                               ok1(ptr && *ptr == j);
+                       else
+                               ok1(!ptr);
+               }
+       }
+
+       /* This exits depending on whether all tests passed */
+       return exit_status();
+}