Blame view
include/linux/idr.h
7.79 KB
1da177e4c Linux-2.6.12-rc2 |
1 2 3 4 5 6 7 8 9 10 |
/* * include/linux/idr.h * * 2002-10-18 written by Jim Houston jim.houston@ccur.com * Copyright (C) 2002 by Concurrent Computer Corporation * Distributed under the GNU GPL license version 2. * * Small id to pointer translation service avoiding fixed sized * tables. */ |
f668ab1ac include/linux: en... |
11 12 13 |
#ifndef __IDR_H__ #define __IDR_H__ |
0a835c4f0 Reimplement IDR a... |
14 15 |
#include <linux/radix-tree.h> #include <linux/gfp.h> |
7ad3d4d85 ida: Move ida_bit... |
16 |
#include <linux/percpu.h> |
0a835c4f0 Reimplement IDR a... |
17 18 19 20 21 |
struct idr { struct radix_tree_root idr_rt; unsigned int idr_next; }; |
1da177e4c Linux-2.6.12-rc2 |
22 |
|
050a6b47d idr: make idr_lay... |
23 |
/* |
0a835c4f0 Reimplement IDR a... |
24 25 |
* The IDR API does not expose the tagging functionality of the radix tree * to users. Use tag 0 to track whether a node has free space below it. |
050a6b47d idr: make idr_lay... |
26 |
*/ |
0a835c4f0 Reimplement IDR a... |
27 |
#define IDR_FREE 0 |
1da177e4c Linux-2.6.12-rc2 |
28 |
|
0a835c4f0 Reimplement IDR a... |
29 30 |
/* Set the IDR flag and the IDR_FREE tag */ #define IDR_RT_MARKER ((__force gfp_t)(3 << __GFP_BITS_SHIFT)) |
1da177e4c Linux-2.6.12-rc2 |
31 |
|
0a835c4f0 Reimplement IDR a... |
32 |
#define IDR_INIT \ |
4106ecaf5 idr: cosmetic upd... |
33 |
{ \ |
0a835c4f0 Reimplement IDR a... |
34 |
.idr_rt = RADIX_TREE_INIT(IDR_RT_MARKER) \ |
1da177e4c Linux-2.6.12-rc2 |
35 |
} |
0a835c4f0 Reimplement IDR a... |
36 |
#define DEFINE_IDR(name) struct idr name = IDR_INIT |
1da177e4c Linux-2.6.12-rc2 |
37 |
|
f9c46d6ea idr: make idr_fin... |
38 |
/** |
444306129 rxrpc: abstract a... |
39 40 41 42 43 44 45 |
* idr_get_cursor - Return the current position of the cyclic allocator * @idr: idr handle * * The value returned is the value that will be next returned from * idr_alloc_cyclic() if it is free (otherwise the search will start from * this position). */ |
0a835c4f0 Reimplement IDR a... |
46 |
static inline unsigned int idr_get_cursor(const struct idr *idr) |
444306129 rxrpc: abstract a... |
47 |
{ |
0a835c4f0 Reimplement IDR a... |
48 |
return READ_ONCE(idr->idr_next); |
444306129 rxrpc: abstract a... |
49 50 51 52 53 54 55 56 57 58 59 60 |
} /** * idr_set_cursor - Set the current position of the cyclic allocator * @idr: idr handle * @val: new position * * The next call to idr_alloc_cyclic() will return @val if it is free * (otherwise the search will start from this position). */ static inline void idr_set_cursor(struct idr *idr, unsigned int val) { |
0a835c4f0 Reimplement IDR a... |
61 |
WRITE_ONCE(idr->idr_next, val); |
444306129 rxrpc: abstract a... |
62 63 64 |
} /** |
56083ab17 docbook: add idr/... |
65 |
* DOC: idr sync |
f9c46d6ea idr: make idr_fin... |
66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
* idr synchronization (stolen from radix-tree.h) * * idr_find() is able to be called locklessly, using RCU. The caller must * ensure calls to this function are made within rcu_read_lock() regions. * Other readers (lock-free or otherwise) and modifications may be running * concurrently. * * It is still required that the caller manage the synchronization and * lifetimes of the items. So if RCU lock-free lookups are used, typically * this would mean that the items have their own locks, or are amenable to * lock-free access; and that the items are freed by RCU (or only freed after * having been deleted from the idr tree *and* a synchronize_rcu() grace * period). */ |
d5c7409f7 idr: implement id... |
80 |
void idr_preload(gfp_t gfp_mask); |
388f79fda idr: Add new APIs... |
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 127 128 129 |
int idr_alloc_cmn(struct idr *idr, void *ptr, unsigned long *index, unsigned long start, unsigned long end, gfp_t gfp, bool ext); /** * idr_alloc - allocate an id * @idr: idr handle * @ptr: pointer to be associated with the new id * @start: the minimum id (inclusive) * @end: the maximum id (exclusive) * @gfp: memory allocation flags * * Allocates an unused ID in the range [start, end). Returns -ENOSPC * if there are no unused IDs in that range. * * Note that @end is treated as max when <= 0. This is to always allow * using @start + N as @end as long as N is inside integer range. * * Simultaneous modifications to the @idr are not allowed and should be * prevented by the user, usually with a lock. idr_alloc() may be called * concurrently with read-only accesses to the @idr, such as idr_find() and * idr_for_each_entry(). */ static inline int idr_alloc(struct idr *idr, void *ptr, int start, int end, gfp_t gfp) { unsigned long id; int ret; if (WARN_ON_ONCE(start < 0)) return -EINVAL; ret = idr_alloc_cmn(idr, ptr, &id, start, end, gfp, false); if (ret) return ret; return id; } static inline int idr_alloc_ext(struct idr *idr, void *ptr, unsigned long *index, unsigned long start, unsigned long end, gfp_t gfp) { return idr_alloc_cmn(idr, ptr, index, start, end, gfp, true); } |
0a835c4f0 Reimplement IDR a... |
130 131 |
int idr_alloc_cyclic(struct idr *, void *entry, int start, int end, gfp_t); int idr_for_each(const struct idr *, |
96d7fa421 lib: add idr_for_... |
132 |
int (*fn)(int id, void *p, void *data), void *data); |
0a835c4f0 Reimplement IDR a... |
133 |
void *idr_get_next(struct idr *, int *nextid); |
388f79fda idr: Add new APIs... |
134 |
void *idr_get_next_ext(struct idr *idr, unsigned long *nextid); |
0a835c4f0 Reimplement IDR a... |
135 |
void *idr_replace(struct idr *, void *, int id); |
388f79fda idr: Add new APIs... |
136 |
void *idr_replace_ext(struct idr *idr, void *ptr, unsigned long id); |
0a835c4f0 Reimplement IDR a... |
137 |
void idr_destroy(struct idr *); |
388f79fda idr: Add new APIs... |
138 |
static inline void *idr_remove_ext(struct idr *idr, unsigned long id) |
0a835c4f0 Reimplement IDR a... |
139 |
{ |
d3e709e63 idr: Return the d... |
140 |
return radix_tree_delete_item(&idr->idr_rt, id, NULL); |
0a835c4f0 Reimplement IDR a... |
141 |
} |
388f79fda idr: Add new APIs... |
142 143 144 145 |
static inline void *idr_remove(struct idr *idr, int id) { return idr_remove_ext(idr, id); } |
0a835c4f0 Reimplement IDR a... |
146 147 148 149 150 151 152 153 154 155 156 |
static inline void idr_init(struct idr *idr) { INIT_RADIX_TREE(&idr->idr_rt, IDR_RT_MARKER); idr->idr_next = 0; } static inline bool idr_is_empty(const struct idr *idr) { return radix_tree_empty(&idr->idr_rt) && radix_tree_tagged(&idr->idr_rt, IDR_FREE); } |
f668ab1ac include/linux: en... |
157 |
|
49038ef4f idr: relocate idr... |
158 |
/** |
d5c7409f7 idr: implement id... |
159 160 161 162 163 164 165 166 167 168 169 |
* idr_preload_end - end preload section started with idr_preload() * * Each idr_preload() should be matched with an invocation of this * function. See idr_preload() for details. */ static inline void idr_preload_end(void) { preempt_enable(); } /** |
0ffc2a9c8 idr: implement lo... |
170 |
* idr_find - return pointer for given id |
5857f70c8 idr: fix new kern... |
171 |
* @idr: idr handle |
0ffc2a9c8 idr: implement lo... |
172 173 174 175 176 177 178 179 180 |
* @id: lookup key * * Return the pointer given the id it has been registered with. A %NULL * return indicates that @id is not valid or you passed %NULL in * idr_get_new(). * * This function can be called under rcu_read_lock(), given that the leaf * pointers lifetimes are correctly managed. */ |
388f79fda idr: Add new APIs... |
181 |
static inline void *idr_find_ext(const struct idr *idr, unsigned long id) |
0ffc2a9c8 idr: implement lo... |
182 |
{ |
0a835c4f0 Reimplement IDR a... |
183 |
return radix_tree_lookup(&idr->idr_rt, id); |
0ffc2a9c8 idr: implement lo... |
184 |
} |
388f79fda idr: Add new APIs... |
185 186 187 188 |
static inline void *idr_find(const struct idr *idr, int id) { return idr_find_ext(idr, id); } |
0ffc2a9c8 idr: implement lo... |
189 |
/** |
49038ef4f idr: relocate idr... |
190 |
* idr_for_each_entry - iterate over an idr's elements of a given type |
0a835c4f0 Reimplement IDR a... |
191 |
* @idr: idr handle |
49038ef4f idr: relocate idr... |
192 193 |
* @entry: the type * to use as cursor * @id: id entry's key |
b949be585 idr: document exi... |
194 195 196 197 |
* * @entry and @id do not need to be initialized before the loop, and * after normal terminatinon @entry is left with the value NULL. This * is convenient for a "not found" value. |
49038ef4f idr: relocate idr... |
198 |
*/ |
0a835c4f0 Reimplement IDR a... |
199 200 |
#define idr_for_each_entry(idr, entry, id) \ for (id = 0; ((entry) = idr_get_next(idr, &(id))) != NULL; ++id) |
388f79fda idr: Add new APIs... |
201 202 |
#define idr_for_each_entry_ext(idr, entry, id) \ for (id = 0; ((entry) = idr_get_next_ext(idr, &(id))) != NULL; ++id) |
49038ef4f idr: relocate idr... |
203 |
|
a55bbd375 drbd: Backport th... |
204 |
/** |
0a835c4f0 Reimplement IDR a... |
205 206 |
* idr_for_each_entry_continue - continue iteration over an idr's elements of a given type * @idr: idr handle |
a55bbd375 drbd: Backport th... |
207 208 209 210 211 212 |
* @entry: the type * to use as cursor * @id: id entry's key * * Continue to iterate over list of given type, continuing after * the current position. */ |
0a835c4f0 Reimplement IDR a... |
213 214 |
#define idr_for_each_entry_continue(idr, entry, id) \ for ((entry) = idr_get_next((idr), &(id)); \ |
a55bbd375 drbd: Backport th... |
215 |
entry; \ |
0a835c4f0 Reimplement IDR a... |
216 |
++id, (entry) = idr_get_next((idr), &(id))) |
a55bbd375 drbd: Backport th... |
217 |
|
c8615d371 idr: deprecate id... |
218 |
/* |
72dba584b ida: implement id... |
219 220 221 222 |
* IDA - IDR based id allocator, use when translation from id to * pointer isn't necessary. */ #define IDA_CHUNK_SIZE 128 /* 128 bytes per chunk */ |
0a835c4f0 Reimplement IDR a... |
223 |
#define IDA_BITMAP_LONGS (IDA_CHUNK_SIZE / sizeof(long)) |
ed9f524ac ida: document IDA... |
224 |
#define IDA_BITMAP_BITS (IDA_BITMAP_LONGS * sizeof(long) * 8) |
72dba584b ida: implement id... |
225 226 |
struct ida_bitmap { |
72dba584b ida: implement id... |
227 228 |
unsigned long bitmap[IDA_BITMAP_LONGS]; }; |
7ad3d4d85 ida: Move ida_bit... |
229 |
DECLARE_PER_CPU(struct ida_bitmap *, ida_bitmap); |
72dba584b ida: implement id... |
230 |
struct ida { |
0a835c4f0 Reimplement IDR a... |
231 |
struct radix_tree_root ida_rt; |
72dba584b ida: implement id... |
232 |
}; |
0a835c4f0 Reimplement IDR a... |
233 234 235 236 |
#define IDA_INIT { \ .ida_rt = RADIX_TREE_INIT(IDR_RT_MARKER | GFP_NOWAIT), \ } #define DEFINE_IDA(name) struct ida name = IDA_INIT |
72dba584b ida: implement id... |
237 238 239 |
int ida_pre_get(struct ida *ida, gfp_t gfp_mask); int ida_get_new_above(struct ida *ida, int starting_id, int *p_id); |
72dba584b ida: implement id... |
240 241 |
void ida_remove(struct ida *ida, int id); void ida_destroy(struct ida *ida); |
72dba584b ida: implement id... |
242 |
|
88eca0207 ida: simplified f... |
243 244 245 |
int ida_simple_get(struct ida *ida, unsigned int start, unsigned int end, gfp_t gfp_mask); void ida_simple_remove(struct ida *ida, unsigned int id); |
0a835c4f0 Reimplement IDR a... |
246 247 248 |
static inline void ida_init(struct ida *ida) { INIT_RADIX_TREE(&ida->ida_rt, IDR_RT_MARKER | GFP_NOWAIT); |
0a835c4f0 Reimplement IDR a... |
249 |
} |
9749f30f1 idr: idr_for_each... |
250 |
/** |
49038ef4f idr: relocate idr... |
251 252 253 254 255 |
* ida_get_new - allocate new ID * @ida: idr handle * @p_id: pointer to the allocated handle * * Simple wrapper around ida_get_new_above() w/ @starting_id of zero. |
9749f30f1 idr: idr_for_each... |
256 |
*/ |
49038ef4f idr: relocate idr... |
257 258 259 260 |
static inline int ida_get_new(struct ida *ida, int *p_id) { return ida_get_new_above(ida, 0, p_id); } |
0a835c4f0 Reimplement IDR a... |
261 |
static inline bool ida_is_empty(const struct ida *ida) |
99c494077 idr: add ida_is_e... |
262 |
{ |
0a835c4f0 Reimplement IDR a... |
263 |
return radix_tree_empty(&ida->ida_rt); |
99c494077 idr: add ida_is_e... |
264 |
} |
f668ab1ac include/linux: en... |
265 |
#endif /* __IDR_H__ */ |