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