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