Blame view
include/linux/radix-tree.h
15.9 KB
de6cc6515 treewide: Replace... |
1 |
/* SPDX-License-Identifier: GPL-2.0-or-later */ |
1da177e4c Linux-2.6.12-rc2 |
2 3 4 |
/* * Copyright (C) 2001 Momchil Velikov * Portions Copyright (C) 2001 Christoph Hellwig |
7cf9c2c76 [PATCH] radix-tre... |
5 |
* Copyright (C) 2006 Nick Piggin |
78c1d7848 radix-tree: intro... |
6 |
* Copyright (C) 2012 Konstantin Khlebnikov |
1da177e4c Linux-2.6.12-rc2 |
7 8 9 |
*/ #ifndef _LINUX_RADIX_TREE_H #define _LINUX_RADIX_TREE_H |
f67c07f07 radix-tree: add a... |
10 |
#include <linux/bitops.h> |
7cf9c2c76 [PATCH] radix-tre... |
11 |
#include <linux/kernel.h> |
15f2e88dd radix tree: Add s... |
12 |
#include <linux/list.h> |
dd841a749 radix tree test s... |
13 |
#include <linux/percpu.h> |
15f2e88dd radix tree: Add s... |
14 |
#include <linux/preempt.h> |
7cf9c2c76 [PATCH] radix-tre... |
15 |
#include <linux/rcupdate.h> |
15f2e88dd radix tree: Add s... |
16 17 |
#include <linux/spinlock.h> #include <linux/types.h> |
3159f943a xarray: Replace e... |
18 |
#include <linux/xarray.h> |
cfa6705d8 radix-tree: Use l... |
19 |
#include <linux/local_lock.h> |
7cf9c2c76 [PATCH] radix-tre... |
20 |
|
f8d5d0cc1 xarray: Add defin... |
21 22 |
/* Keep unconverted code working */ #define radix_tree_root xarray |
01959dfe7 xarray: Define st... |
23 |
#define radix_tree_node xa_node |
f8d5d0cc1 xarray: Add defin... |
24 |
|
cfa6705d8 radix-tree: Use l... |
25 26 27 28 29 30 31 |
struct radix_tree_preload { local_lock_t lock; unsigned nr; /* nodes->parent points to next preallocated node */ struct radix_tree_node *nodes; }; DECLARE_PER_CPU(struct radix_tree_preload, radix_tree_preloads); |
7cf9c2c76 [PATCH] radix-tre... |
32 |
/* |
3bcadd6fa radix-tree: free ... |
33 34 |
* The bottom two bits of the slot determine how the remaining bits in the * slot are interpreted: |
7cf9c2c76 [PATCH] radix-tre... |
35 |
* |
3bcadd6fa radix-tree: free ... |
36 |
* 00 - data pointer |
3159f943a xarray: Replace e... |
37 38 |
* 10 - internal entry * x1 - value entry |
3bcadd6fa radix-tree: free ... |
39 40 41 42 43 44 |
* * The internal entry may be a pointer to the next level in the tree, a * sibling entry, or an indicator that the entry in this slot has been moved * to another location in the tree and the lookup should be restarted. While * NULL fits the 'data pointer' pattern, it means that there is no entry in * the tree for this index (no matter what level of the tree it is found at). |
3159f943a xarray: Replace e... |
45 46 |
* This means that storing a NULL entry in the tree is the same as deleting * the entry from the tree. |
7cf9c2c76 [PATCH] radix-tre... |
47 |
*/ |
3bcadd6fa radix-tree: free ... |
48 |
#define RADIX_TREE_ENTRY_MASK 3UL |
3159f943a xarray: Replace e... |
49 |
#define RADIX_TREE_INTERNAL_NODE 2UL |
7cf9c2c76 [PATCH] radix-tre... |
50 |
|
3bcadd6fa radix-tree: free ... |
51 |
static inline bool radix_tree_is_internal_node(void *ptr) |
7cf9c2c76 [PATCH] radix-tre... |
52 |
{ |
3bcadd6fa radix-tree: free ... |
53 54 |
return ((unsigned long)ptr & RADIX_TREE_ENTRY_MASK) == RADIX_TREE_INTERNAL_NODE; |
7cf9c2c76 [PATCH] radix-tre... |
55 56 57 |
} /*** radix-tree API starts here ***/ |
1da177e4c Linux-2.6.12-rc2 |
58 |
|
02c02bf12 xarray: Change de... |
59 |
#define RADIX_TREE_MAP_SHIFT XA_CHUNK_SHIFT |
139e56166 lib: radix_tree: ... |
60 61 |
#define RADIX_TREE_MAP_SIZE (1UL << RADIX_TREE_MAP_SHIFT) #define RADIX_TREE_MAP_MASK (RADIX_TREE_MAP_SIZE-1) |
01959dfe7 xarray: Define st... |
62 63 |
#define RADIX_TREE_MAX_TAGS XA_MAX_MARKS #define RADIX_TREE_TAG_LONGS XA_MARK_LONGS |
139e56166 lib: radix_tree: ... |
64 |
|
449dd6984 mm: keep page cac... |
65 66 67 |
#define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long)) #define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \ RADIX_TREE_MAP_SHIFT)) |
f8d5d0cc1 xarray: Add defin... |
68 |
/* The IDR tag is stored in the low bits of xa_flags */ |
fa290cda1 radix tree: use G... |
69 |
#define ROOT_IS_IDR ((__force gfp_t)4) |
f8d5d0cc1 xarray: Add defin... |
70 |
/* The top bits of xa_flags are used to store the root tags */ |
fa290cda1 radix tree: use G... |
71 |
#define ROOT_TAG_SHIFT (__GFP_BITS_SHIFT) |
0a835c4f0 Reimplement IDR a... |
72 |
|
f8d5d0cc1 xarray: Add defin... |
73 |
#define RADIX_TREE_INIT(name, mask) XARRAY_INIT(name, mask) |
1da177e4c Linux-2.6.12-rc2 |
74 75 |
#define RADIX_TREE(name, mask) \ |
f6bb2a2c0 xarray: add the x... |
76 |
struct radix_tree_root name = RADIX_TREE_INIT(name, mask) |
1da177e4c Linux-2.6.12-rc2 |
77 |
|
f8d5d0cc1 xarray: Add defin... |
78 |
#define INIT_RADIX_TREE(root, mask) xa_init_flags(root, mask) |
1da177e4c Linux-2.6.12-rc2 |
79 |
|
35534c869 radix tree: const... |
80 |
static inline bool radix_tree_empty(const struct radix_tree_root *root) |
e9256efcc radix-tree: intro... |
81 |
{ |
f8d5d0cc1 xarray: Add defin... |
82 |
return root->xa_head == NULL; |
e9256efcc radix-tree: intro... |
83 |
} |
7cf9c2c76 [PATCH] radix-tre... |
84 |
/** |
268f42de7 radix-tree: delet... |
85 86 87 88 89 90 |
* struct radix_tree_iter - radix tree iterator state * * @index: index of current slot * @next_index: one beyond the last index for this chunk * @tags: bit-mask for tag-iterating * @node: node that contains current slot |
268f42de7 radix-tree: delet... |
91 92 93 94 95 96 97 98 99 100 101 102 103 |
* * This radix tree iterator works in terms of "chunks" of slots. A chunk is a * subinterval of slots contained within one radix tree leaf node. It is * described by a pointer to its first slot and a struct radix_tree_iter * which holds the chunk's position in the tree and its size. For tagged * iteration radix_tree_iter also holds the slots' bit-mask for one chosen * radix tree tag. */ struct radix_tree_iter { unsigned long index; unsigned long next_index; unsigned long tags; struct radix_tree_node *node; |
268f42de7 radix-tree: delet... |
104 |
}; |
268f42de7 radix-tree: delet... |
105 |
/** |
7cf9c2c76 [PATCH] radix-tre... |
106 107 108 109 110 111 112 113 114 |
* Radix-tree synchronization * * The radix-tree API requires that users provide all synchronisation (with * specific exceptions, noted below). * * Synchronization of access to the data items being stored in the tree, and * management of their lifetimes must be completely managed by API users. * * For API usage, in general, |
59c51591a Fix occurrences o... |
115 |
* - any function _modifying_ the tree or tags (inserting or deleting |
eb8dc5e7b radix_tree.h triv... |
116 |
* items, setting or clearing tags) must exclude other modifications, and |
7cf9c2c76 [PATCH] radix-tre... |
117 |
* exclude any functions reading the tree. |
59c51591a Fix occurrences o... |
118 |
* - any function _reading_ the tree or tags (looking up items or tags, |
7cf9c2c76 [PATCH] radix-tre... |
119 120 121 122 |
* gang lookups) must exclude modifications to the tree, but may occur * concurrently with other readers. * * The notable exceptions to this rule are the following functions: |
139e56166 lib: radix_tree: ... |
123 |
* __radix_tree_lookup |
7cf9c2c76 [PATCH] radix-tre... |
124 |
* radix_tree_lookup |
47feff2c8 radix-tree: add g... |
125 |
* radix_tree_lookup_slot |
7cf9c2c76 [PATCH] radix-tre... |
126 127 128 |
* radix_tree_tag_get * radix_tree_gang_lookup * radix_tree_gang_lookup_tag |
47feff2c8 radix-tree: add g... |
129 |
* radix_tree_gang_lookup_tag_slot |
7cf9c2c76 [PATCH] radix-tre... |
130 131 |
* radix_tree_tagged * |
7b8d046fb shmem: Convert sh... |
132 |
* The first 7 functions are able to be called locklessly, using RCU. The |
7cf9c2c76 [PATCH] radix-tre... |
133 134 135 136 137 138 139 140 141 142 143 144 145 |
* caller must ensure calls to these functions 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 radix tree *and* a synchronize_rcu() grace period). * * (Note, rcu_assign_pointer and rcu_dereference are not needed to control * access to data items when inserting into or looking up from the radix tree) * |
ce82653d6 radix_tree_tag_ge... |
146 147 148 149 150 151 152 |
* Note that the value returned by radix_tree_tag_get() may not be relied upon * if only the RCU read lock is held. Functions to set/clear tags and to * delete nodes running concurrently with it may affect its result such that * two consecutive reads in the same locked section may return different * values. If reliability is required, modification functions must also be * excluded from concurrency. * |
7cf9c2c76 [PATCH] radix-tre... |
153 154 155 156 |
* radix_tree_tagged is able to be called without locking or RCU. */ /** |
d7b627277 radix-tree: Fix _... |
157 158 |
* radix_tree_deref_slot - dereference a slot * @slot: slot pointer, returned by radix_tree_lookup_slot |
7cf9c2c76 [PATCH] radix-tre... |
159 160 |
* * For use with radix_tree_lookup_slot(). Caller must hold tree at least read |
27d20fddc radix-tree: fix R... |
161 162 163 164 165 |
* locked across slot lookup and dereference. Not required if write lock is * held (ie. items cannot be concurrently inserted). * * radix_tree_deref_retry must be used to confirm validity of the pointer if * only the read lock is held. |
d7b627277 radix-tree: Fix _... |
166 167 |
* * Return: entry stored in that slot. |
7cf9c2c76 [PATCH] radix-tre... |
168 |
*/ |
d7b627277 radix-tree: Fix _... |
169 |
static inline void *radix_tree_deref_slot(void __rcu **slot) |
7cf9c2c76 [PATCH] radix-tre... |
170 |
{ |
d7b627277 radix-tree: Fix _... |
171 |
return rcu_dereference(*slot); |
7cf9c2c76 [PATCH] radix-tre... |
172 |
} |
27d20fddc radix-tree: fix R... |
173 174 |
/** |
d7b627277 radix-tree: Fix _... |
175 176 177 178 179 |
* radix_tree_deref_slot_protected - dereference a slot with tree lock held * @slot: slot pointer, returned by radix_tree_lookup_slot * * Similar to radix_tree_deref_slot. The caller does not hold the RCU read * lock but it must hold the tree lock to prevent parallel updates. |
29c1f677d mm: migration: us... |
180 |
* |
d7b627277 radix-tree: Fix _... |
181 |
* Return: entry stored in that slot. |
29c1f677d mm: migration: us... |
182 |
*/ |
d7b627277 radix-tree: Fix _... |
183 |
static inline void *radix_tree_deref_slot_protected(void __rcu **slot, |
29c1f677d mm: migration: us... |
184 185 |
spinlock_t *treelock) { |
d7b627277 radix-tree: Fix _... |
186 |
return rcu_dereference_protected(*slot, lockdep_is_held(treelock)); |
29c1f677d mm: migration: us... |
187 188 189 |
} /** |
27d20fddc radix-tree: fix R... |
190 191 192 193 194 195 196 197 |
* radix_tree_deref_retry - check radix_tree_deref_slot * @arg: pointer returned by radix_tree_deref_slot * Returns: 0 if retry is not required, otherwise retry is required * * radix_tree_deref_retry must be used with radix_tree_deref_slot. */ static inline int radix_tree_deref_retry(void *arg) { |
b194d16c2 radix-tree: renam... |
198 |
return unlikely(radix_tree_is_internal_node(arg)); |
27d20fddc radix-tree: fix R... |
199 |
} |
7cf9c2c76 [PATCH] radix-tre... |
200 |
/** |
6328650bb radix_tree: excep... |
201 202 203 204 205 206 |
* radix_tree_exception - radix_tree_deref_slot returned either exception? * @arg: value returned by radix_tree_deref_slot * Returns: 0 if well-aligned pointer, non-0 if either kind of exception. */ static inline int radix_tree_exception(void *arg) { |
3bcadd6fa radix-tree: free ... |
207 |
return unlikely((unsigned long)arg & RADIX_TREE_ENTRY_MASK); |
6328650bb radix_tree: excep... |
208 |
} |
3a08cd52c radix tree: Remov... |
209 210 |
int radix_tree_insert(struct radix_tree_root *, unsigned long index, void *); |
35534c869 radix tree: const... |
211 |
void *__radix_tree_lookup(const struct radix_tree_root *, unsigned long index, |
d7b627277 radix-tree: Fix _... |
212 |
struct radix_tree_node **nodep, void __rcu ***slotp); |
35534c869 radix tree: const... |
213 |
void *radix_tree_lookup(const struct radix_tree_root *, unsigned long); |
d7b627277 radix-tree: Fix _... |
214 215 |
void __rcu **radix_tree_lookup_slot(const struct radix_tree_root *, unsigned long index); |
d7b627277 radix-tree: Fix _... |
216 |
void __radix_tree_replace(struct radix_tree_root *, struct radix_tree_node *, |
1cf56f9d6 radix tree: Remov... |
217 |
void __rcu **slot, void *entry); |
e157b5559 radix-tree: add r... |
218 |
void radix_tree_iter_replace(struct radix_tree_root *, |
d7b627277 radix-tree: Fix _... |
219 220 221 |
const struct radix_tree_iter *, void __rcu **slot, void *entry); void radix_tree_replace_slot(struct radix_tree_root *, void __rcu **slot, void *entry); |
0ac398ef3 radix-tree: Add r... |
222 |
void radix_tree_iter_delete(struct radix_tree_root *, |
d7b627277 radix-tree: Fix _... |
223 |
struct radix_tree_iter *iter, void __rcu **slot); |
53c59f262 lib: radix-tree: ... |
224 |
void *radix_tree_delete_item(struct radix_tree_root *, unsigned long, void *); |
1da177e4c Linux-2.6.12-rc2 |
225 |
void *radix_tree_delete(struct radix_tree_root *, unsigned long); |
35534c869 radix tree: const... |
226 |
unsigned int radix_tree_gang_lookup(const struct radix_tree_root *, |
d604c3245 radix-tree: intro... |
227 228 |
void **results, unsigned long first_index, unsigned int max_items); |
dd0fc66fb [PATCH] gfp flags... |
229 |
int radix_tree_preload(gfp_t gfp_mask); |
5e4c0d974 lib/radix-tree.c:... |
230 |
int radix_tree_maybe_preload(gfp_t gfp_mask); |
1da177e4c Linux-2.6.12-rc2 |
231 |
void radix_tree_init(void); |
d7b627277 radix-tree: Fix _... |
232 |
void *radix_tree_tag_set(struct radix_tree_root *, |
daff89f32 [PATCH] radix-tre... |
233 |
unsigned long index, unsigned int tag); |
d7b627277 radix-tree: Fix _... |
234 |
void *radix_tree_tag_clear(struct radix_tree_root *, |
daff89f32 [PATCH] radix-tre... |
235 |
unsigned long index, unsigned int tag); |
35534c869 radix tree: const... |
236 |
int radix_tree_tag_get(const struct radix_tree_root *, |
daff89f32 [PATCH] radix-tre... |
237 |
unsigned long index, unsigned int tag); |
30b888ba9 radix-tree: Add r... |
238 |
void radix_tree_iter_tag_clear(struct radix_tree_root *, |
268f42de7 radix-tree: delet... |
239 |
const struct radix_tree_iter *iter, unsigned int tag); |
d7b627277 radix-tree: Fix _... |
240 241 242 243 244 245 246 |
unsigned int radix_tree_gang_lookup_tag(const struct radix_tree_root *, void **results, unsigned long first_index, unsigned int max_items, unsigned int tag); unsigned int radix_tree_gang_lookup_tag_slot(const struct radix_tree_root *, void __rcu ***results, unsigned long first_index, unsigned int max_items, unsigned int tag); int radix_tree_tagged(const struct radix_tree_root *, unsigned int tag); |
1da177e4c Linux-2.6.12-rc2 |
247 248 249 |
static inline void radix_tree_preload_end(void) { |
cfa6705d8 radix-tree: Use l... |
250 |
local_unlock(&radix_tree_preloads.lock); |
1da177e4c Linux-2.6.12-rc2 |
251 |
} |
460488c58 idr: Remove idr_a... |
252 |
void __rcu **idr_get_free(struct radix_tree_root *root, |
388f79fda idr: Add new APIs... |
253 254 |
struct radix_tree_iter *iter, gfp_t gfp, unsigned long max); |
175542f57 radix-tree: add r... |
255 |
|
0a835c4f0 Reimplement IDR a... |
256 257 258 259 260 |
enum { RADIX_TREE_ITER_TAG_MASK = 0x0f, /* tag index in lower nybble */ RADIX_TREE_ITER_TAGGED = 0x10, /* lookup tagged slots */ RADIX_TREE_ITER_CONTIG = 0x20, /* stop at first hole */ }; |
78c1d7848 radix-tree: intro... |
261 262 263 264 265 266 267 268 |
/** * radix_tree_iter_init - initialize radix tree iterator * * @iter: pointer to iterator state * @start: iteration starting index * Returns: NULL */ |
d7b627277 radix-tree: Fix _... |
269 |
static __always_inline void __rcu ** |
78c1d7848 radix-tree: intro... |
270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 |
radix_tree_iter_init(struct radix_tree_iter *iter, unsigned long start) { /* * Leave iter->tags uninitialized. radix_tree_next_chunk() will fill it * in the case of a successful tagged chunk lookup. If the lookup was * unsuccessful or non-tagged then nobody cares about ->tags. * * Set index to zero to bypass next_index overflow protection. * See the comment in radix_tree_next_chunk() for details. */ iter->index = 0; iter->next_index = start; return NULL; } /** * radix_tree_next_chunk - find next chunk of slots for iteration * * @root: radix tree root * @iter: iterator state * @flags: RADIX_TREE_ITER_* flags and tag index * Returns: pointer to chunk first slot, or NULL if there no more left * * This function looks up the next chunk in the radix tree starting from * @iter->next_index. It returns a pointer to the chunk's first slot. * Also it fills @iter with data about chunk: position in the tree (index), * its end (next_index), and constructs a bit mask for tagged iterating (tags). */ |
d7b627277 radix-tree: Fix _... |
298 |
void __rcu **radix_tree_next_chunk(const struct radix_tree_root *, |
78c1d7848 radix-tree: intro... |
299 300 301 |
struct radix_tree_iter *iter, unsigned flags); /** |
0a835c4f0 Reimplement IDR a... |
302 303 304 305 306 307 308 309 310 |
* radix_tree_iter_lookup - look up an index in the radix tree * @root: radix tree root * @iter: iterator state * @index: key to look up * * If @index is present in the radix tree, this function returns the slot * containing it and updates @iter to describe the entry. If @index is not * present, it returns NULL. */ |
d7b627277 radix-tree: Fix _... |
311 312 |
static inline void __rcu ** radix_tree_iter_lookup(const struct radix_tree_root *root, |
0a835c4f0 Reimplement IDR a... |
313 314 315 316 317 318 319 |
struct radix_tree_iter *iter, unsigned long index) { radix_tree_iter_init(iter, index); return radix_tree_next_chunk(root, iter, RADIX_TREE_ITER_CONTIG); } /** |
46437f9a5 radix-tree: fix r... |
320 321 322 323 324 325 326 327 328 |
* radix_tree_iter_retry - retry this chunk of the iteration * @iter: iterator state * * If we iterate over a tree protected only by the RCU lock, a race * against deletion or creation may result in seeing a slot for which * radix_tree_deref_retry() returns true. If so, call this function * and continue the iteration. */ static inline __must_check |
d7b627277 radix-tree: Fix _... |
329 |
void __rcu **radix_tree_iter_retry(struct radix_tree_iter *iter) |
46437f9a5 radix-tree: fix r... |
330 331 |
{ iter->next_index = iter->index; |
3cb9185c6 radix-tree: fix r... |
332 |
iter->tags = 0; |
46437f9a5 radix-tree: fix r... |
333 334 |
return NULL; } |
21ef53393 radix-tree: add s... |
335 336 337 |
static inline unsigned long __radix_tree_iter_add(struct radix_tree_iter *iter, unsigned long slots) { |
3a08cd52c radix tree: Remov... |
338 |
return iter->index + slots; |
21ef53393 radix-tree: add s... |
339 |
} |
46437f9a5 radix-tree: fix r... |
340 |
/** |
148deab22 radix-tree: impro... |
341 342 343 344 |
* radix_tree_iter_resume - resume iterating when the chunk may be invalid * @slot: pointer to current slot * @iter: iterator state * Returns: New slot pointer |
7165092fe radix-tree,shmem:... |
345 346 347 |
* * If the iterator needs to release then reacquire a lock, the chunk may * have been invalidated by an insertion or deletion. Call this function |
148deab22 radix-tree: impro... |
348 |
* before releasing the lock to continue the iteration from the next index. |
7165092fe radix-tree,shmem:... |
349 |
*/ |
d7b627277 radix-tree: Fix _... |
350 |
void __rcu **__must_check radix_tree_iter_resume(void __rcu **slot, |
148deab22 radix-tree: impro... |
351 |
struct radix_tree_iter *iter); |
7165092fe radix-tree,shmem:... |
352 353 |
/** |
78c1d7848 radix-tree: intro... |
354 355 356 357 358 |
* radix_tree_chunk_size - get current chunk size * * @iter: pointer to radix tree iterator * Returns: current chunk size */ |
732042821 radix-tree: fix o... |
359 |
static __always_inline long |
78c1d7848 radix-tree: intro... |
360 361 |
radix_tree_chunk_size(struct radix_tree_iter *iter) { |
3a08cd52c radix tree: Remov... |
362 |
return iter->next_index - iter->index; |
78c1d7848 radix-tree: intro... |
363 364 365 366 367 368 |
} /** * radix_tree_next_slot - find next slot in chunk * * @slot: pointer to current slot |
f78b8250a radix-tree: fix t... |
369 |
* @iter: pointer to iterator state |
78c1d7848 radix-tree: intro... |
370 371 372 373 374 |
* @flags: RADIX_TREE_ITER_*, should be constant * Returns: pointer to next slot, or NULL if there no more left * * This function updates @iter->index in the case of a successful lookup. * For tagged lookup it also eats @iter->tags. |
915045fe1 radix-tree: 'slot... |
375 376 |
* * There are several cases where 'slot' can be passed in as NULL to this |
148deab22 radix-tree: impro... |
377 |
* function. These cases result from the use of radix_tree_iter_resume() or |
915045fe1 radix-tree: 'slot... |
378 379 380 381 382 |
* radix_tree_iter_retry(). In these cases we don't end up dereferencing * 'slot' because either: * a) we are doing tagged iteration and iter->tags has been set to 0, or * b) we are doing non-tagged iteration, and iter->index and iter->next_index * have been set up so that radix_tree_chunk_size() returns 1 or 0. |
78c1d7848 radix-tree: intro... |
383 |
*/ |
d7b627277 radix-tree: Fix _... |
384 385 |
static __always_inline void __rcu **radix_tree_next_slot(void __rcu **slot, struct radix_tree_iter *iter, unsigned flags) |
78c1d7848 radix-tree: intro... |
386 387 388 |
{ if (flags & RADIX_TREE_ITER_TAGGED) { iter->tags >>= 1; |
21ef53393 radix-tree: add s... |
389 390 |
if (unlikely(!iter->tags)) return NULL; |
78c1d7848 radix-tree: intro... |
391 |
if (likely(iter->tags & 1ul)) { |
21ef53393 radix-tree: add s... |
392 |
iter->index = __radix_tree_iter_add(iter, 1); |
148deab22 radix-tree: impro... |
393 394 |
slot++; goto found; |
78c1d7848 radix-tree: intro... |
395 |
} |
21ef53393 radix-tree: add s... |
396 |
if (!(flags & RADIX_TREE_ITER_CONTIG)) { |
78c1d7848 radix-tree: intro... |
397 |
unsigned offset = __ffs(iter->tags); |
148deab22 radix-tree: impro... |
398 399 400 401 |
iter->tags >>= offset++; iter->index = __radix_tree_iter_add(iter, offset); slot += offset; goto found; |
78c1d7848 radix-tree: intro... |
402 403 |
} } else { |
21ef53393 radix-tree: add s... |
404 |
long count = radix_tree_chunk_size(iter); |
78c1d7848 radix-tree: intro... |
405 |
|
21ef53393 radix-tree: add s... |
406 |
while (--count > 0) { |
78c1d7848 radix-tree: intro... |
407 |
slot++; |
21ef53393 radix-tree: add s... |
408 |
iter->index = __radix_tree_iter_add(iter, 1); |
78c1d7848 radix-tree: intro... |
409 |
if (likely(*slot)) |
148deab22 radix-tree: impro... |
410 |
goto found; |
fffaee365 radix-tree: fix c... |
411 412 413 |
if (flags & RADIX_TREE_ITER_CONTIG) { /* forbid switching to the next chunk */ iter->next_index = 0; |
78c1d7848 radix-tree: intro... |
414 |
break; |
fffaee365 radix-tree: fix c... |
415 |
} |
78c1d7848 radix-tree: intro... |
416 417 418 |
} } return NULL; |
148deab22 radix-tree: impro... |
419 420 |
found: |
148deab22 radix-tree: impro... |
421 |
return slot; |
78c1d7848 radix-tree: intro... |
422 423 424 |
} /** |
78c1d7848 radix-tree: intro... |
425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 |
* radix_tree_for_each_slot - iterate over non-empty slots * * @slot: the void** variable for pointer to slot * @root: the struct radix_tree_root pointer * @iter: the struct radix_tree_iter pointer * @start: iteration starting index * * @slot points to radix tree slot, @iter->index contains its index. */ #define radix_tree_for_each_slot(slot, root, iter, start) \ for (slot = radix_tree_iter_init(iter, start) ; \ slot || (slot = radix_tree_next_chunk(root, iter, 0)) ; \ slot = radix_tree_next_slot(slot, iter, 0)) /** |
78c1d7848 radix-tree: intro... |
440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 |
* radix_tree_for_each_tagged - iterate over tagged slots * * @slot: the void** variable for pointer to slot * @root: the struct radix_tree_root pointer * @iter: the struct radix_tree_iter pointer * @start: iteration starting index * @tag: tag index * * @slot points to radix tree slot, @iter->index contains its index. */ #define radix_tree_for_each_tagged(slot, root, iter, start, tag) \ for (slot = radix_tree_iter_init(iter, start) ; \ slot || (slot = radix_tree_next_chunk(root, iter, \ RADIX_TREE_ITER_TAGGED | tag)) ; \ slot = radix_tree_next_slot(slot, iter, \ |
148deab22 radix-tree: impro... |
455 |
RADIX_TREE_ITER_TAGGED | tag)) |
78c1d7848 radix-tree: intro... |
456 |
|
1da177e4c Linux-2.6.12-rc2 |
457 |
#endif /* _LINUX_RADIX_TREE_H */ |