git.ozlabs.org Git - ccan/blob - ccan/sparse_bsearch/_info

   1 #include <string.h>
   2 #include <stdio.h>
   3 #include "config.h"
   4
   5 /**
   6  * sparse_bsearch - search a sorted array with some invalid entries
   7  *
   8  * bsearch() is great for searching an array, but if you are deleting from
   9  * the array, you then need to memmove() to keep it dense.
  10  *
  11  * Sometimes there is a useful invalid value which can be used to mark deleted
  12  * entries, but such a "gappy" array breaks bsearch.  This function allows
  13  * "invalid" entries in your array, which are ignored for the search.
  14  *
  15  * Example:
  16  *      #include <ccan/sparse_bsearch/sparse_bsearch.h>
  17  *
  18  *      static bool val_valid(const unsigned int *val)
  19  *      {
  20  *              return *val != 0;
  21  *      }
  22  *      static int val_cmp(const unsigned int *a, const unsigned int *b)
  23  *      {
  24  *              return (int)((*a) - (*b));
  25  *      }
  26  *      static unsigned int values[] = { 1, 7, 11, 1235, 99999 };
  27  *
  28  *      // Return true if this value is in set, and remove it.
  29  *      static bool remove_from_values(unsigned int val)
  30  *      {
  31  *              unsigned int *p;
  32  *              // We use 5 here, but ccan/array_size.h is better!
  33  *              p = sparse_bsearch(&val, values, 5, val_cmp, val_valid);
  34  *              if (!p)
  35  *                      return false;
  36  *              *p = 0;
  37  *              return true;
  38  *      }
  39  *
  40  *      int main(int argc, char *argv[])
  41  *      {
  42  *              int i, val;
  43  *              for (i = 1; i < argc; i++) {
  44  *                      val = atoi(argv[i]);
  45  *                      if (remove_from_values(val))
  46  *                              printf("%i removed.\n", val);
  47  *                      else
  48  *                              printf("%i wasn't there.\n", val);
  49  *              }
  50  *              return 0;
  51  *      }
  52  *
  53  * License: LGPL (2 or any later version)
  54  * Author: Rusty Russell <rusty@rustcorp.com.au>
  55  */
  56 int main(int argc, char *argv[])
  57 {
  58         /* Expect exactly one argument */
  59         if (argc != 2)
  60                 return 1;
  61
  62         if (strcmp(argv[1], "depends") == 0) {
  63                 printf("ccan/typesafe_cb\n"
  64                        "ccan/check_type\n");
  65                 return 0;
  66         }
  67
  68         return 1;
  69 }