git.ozlabs.org Git - ccan/blob - ccan/idtree/idtree.h

   1 /* Licensed under GPLv2+ - see LICENSE file for details */
   2 #ifndef CCAN_IDTREE_H
   3 #define CCAN_IDTREE_H
   4 #include <stdbool.h>
   5
   6 /**
   7  * idtree_new - create an idr_context
   8  * @mem_ctx: talloc parent to allocate from (may be NULL).
   9  *
  10  * Allocate an empty id tree.  You can free it with talloc_free().
  11  *
  12  * Example:
  13  *      static struct idtree *ids;
  14  *
  15  *      static void init(void)
  16  *      {
  17  *              ids = idtree_new(NULL);
  18  *              if (!ids)
  19  *                      err(1, "Failed to allocate idtree");
  20  *      }
  21  */
  22 struct idtree *idtree_new(void *mem_ctx);
  23
  24 /**
  25  * idtree_add - get lowest available id, and assign a pointer to it.
  26  * @idtree: the tree to allocate from
  27  * @ptr: the non-NULL pointer to associate with the id
  28  * @limit: the maximum id to allocate (ie. INT_MAX means no limit).
  29  *
  30  * This returns a non-negative id number, or -1 if all are taken.
  31  *
  32  * Example:
  33  *      struct foo {
  34  *              unsigned int id;
  35  *              // ...
  36  *      };
  37  *
  38  *      // Create a new foo, assigning an id.
  39  *      static struct foo *new_foo(void)
  40  *      {
  41  *              int id;
  42  *              struct foo *foo = malloc(sizeof(*foo));
  43  *              if (!foo)
  44  *                      return NULL;
  45  *
  46  *              id = idtree_add(ids, foo, INT_MAX);
  47  *              if (id < 0) {
  48  *                      free(foo);
  49  *                      return NULL;
  50  *              }
  51  *              foo->id = id;
  52  *              return foo;
  53  *      }
  54  */
  55 int idtree_add(struct idtree *idtree, const void *ptr, int limit);
  56
  57 /**
  58  * idtree_add_above - get lowest available id, starting at a given value.
  59  * @idtree: the tree to allocate from
  60  * @ptr: the non-NULL pointer to associate with the id
  61  * @starting_id: the minimum id value to consider.
  62  * @limit: the maximum id to allocate (ie. INT_MAX means no limit).
  63  *
  64  * Example:
  65  *      static int last_id = -1;
  66  *
  67  *      // Create a new foo, assigning a consecutive id.
  68  *      // This maximizes the time before ids roll.
  69  *      static struct foo *new_foo_inc_id(void)
  70  *      {
  71  *              int id;
  72  *              struct foo *foo = malloc(sizeof(*foo));
  73  *              if (!foo)
  74  *                      return NULL;
  75  *
  76  *              id = idtree_add_above(ids, foo, last_id+1, INT_MAX);
  77  *              if (id < 0) {
  78  *                      id = idtree_add(ids, foo, INT_MAX);
  79  *                      if (id < 0) {
  80  *                              free(foo);
  81  *                              return NULL;
  82  *                      }
  83  *              }
  84  *              last_id = id;
  85  *              foo->id = id;
  86  *              return foo;
  87  *      }
  88  */
  89 int idtree_add_above(struct idtree *idtree, const void *ptr,
  90                      int starting_id, int limit);
  91
  92 /**
  93  * idtree_lookup - look up a given id
  94  * @idtree: the tree to look in
  95  * @id: the id to look up
  96  *
  97  * Returns NULL if the value is not found, otherwise the pointer value
  98  * set with the idtree_add()/idtree_add_above().
  99  *
 100  * Example:
 101  *      // Look up a foo for a given ID.
 102  *      static struct foo *find_foo(unsigned int id)
 103  *      {
 104  *              return idtree_lookup(ids, id);
 105  *      }
 106  */
 107 void *idtree_lookup(const struct idtree *idtree, int id);
 108
 109 /**
 110  * idtree_remove - remove a given id.
 111  * @idtree: the tree to remove from
 112  * @id: the id to remove.
 113  *
 114  * Returns false if the id was not in the tree.
 115  *
 116  * Example:
 117  *      // Look up a foo for a given ID.
 118  *      static void free_foo(struct foo *foo)
 119  *      {
 120  *              bool exists = idtree_remove(ids, foo->id);
 121  *              assert(exists);
 122  *              free(foo);
 123  *      }
 124  */
 125 bool idtree_remove(struct idtree *idtree, int id);
 126 #endif /* CCAN_IDTREE_H */