Lines Matching +full:indexed +full:- +full:array
2 Generic Associative Array Implementation
8 This associative array implementation is an object container with the following
18 2. Objects do not need to contain linkage blocks for use by the array. This
20 Rather, the array is made up of metadata blocks that point to objects.
22 3. Objects require index keys to locate them within the array.
25 already in the array will replace the old object.
32 7. Index keys can include a hash to scatter objects throughout the array.
34 8. The array can iterated over. The objects will not necessarily come out in
37 9. The array can be iterated over while it is being modified, provided the
43 10. Objects in the array can be looked up by means of their index key.
45 11. Objects can be looked up while the array is being modified, provided the
48 The implementation uses a tree of 16-pointer nodes internally that are indexed
51 what would otherwise be a series of single-occupancy nodes. Further, nodes
60 array is rooted on the following structure::
68 ./script/config -e ASSOCIATIVE_ARRAY
72 -----------
82 after an RCU grace period has passed - thus allowing access functions to
112 ----------------
126 This should return a chunk of caller-supplied index key starting at the
136 As the previous function, but gets its data from an object in the array
137 rather than from a caller-supplied index key.
153 differs from the given index key or -1 if they are the same.
166 ----------------------
168 There are a number of functions for manipulating an associative array:
170 1. Initialise an associative array::
172 void assoc_array_init(struct assoc_array *array);
174 This initialises the base structure for an associative array. It can't fail.
177 2. Insert/replace an object in an associative array::
180 assoc_array_insert(struct assoc_array *array,
185 This inserts the given object into the array. Note that the least
186 significant bit of the pointer must be zero as it's used to type-mark
195 This function makes no alteration to the array itself, but rather returns
196 an edit script that must be applied. ``-ENOMEM`` is returned in the case of
197 an out-of-memory error.
199 The caller should lock exclusively against other modifiers of the array.
202 3. Delete an object from an associative array::
205 assoc_array_delete(struct assoc_array *array,
209 This deletes an object that matches the specified data from the array.
214 This function makes no alteration to the array itself, but rather returns
215 an edit script that must be applied. ``-ENOMEM`` is returned in the case of
216 an out-of-memory error. ``NULL`` will be returned if the specified object is
217 not found within the array.
219 The caller should lock exclusively against other modifiers of the array.
222 4. Delete all objects from an associative array::
225 assoc_array_clear(struct assoc_array *array,
228 This deletes all the objects from an associative array and leaves it
231 This function makes no alteration to the array itself, but rather returns
232 an edit script that must be applied. ``-ENOMEM`` is returned in the case of
233 an out-of-memory error.
235 The caller should lock exclusively against other modifiers of the array.
238 5. Destroy an associative array, deleting all objects::
240 void assoc_array_destroy(struct assoc_array *array,
243 This destroys the contents of the associative array and leaves it
245 the array under the RCU read lock at the same time as this function is
246 destroying it as no RCU deferral is performed on memory release -
250 of the array.
253 6. Garbage collect an associative array::
255 int assoc_array_gc(struct assoc_array *array,
260 This iterates over the objects in an associative array and passes each one to
272 The function will return ``0`` if successful and ``-ENOMEM`` if there wasn't
275 It is possible for other threads to iterate over or search the array under
277 lock exclusively against other modifiers of the array.
281 ----------------
283 There are two functions for accessing an associative array:
285 1. Iterate over all the objects in an associative array::
287 int assoc_array_iterate(const struct assoc_array *array,
292 This passes each object in the array to the iterator callback function.
295 This may be used on an array at the same time as the array is being
301 The function will return ``0`` if no objects were in the array or else it will
303 immediately if any call to the iteration function results in a non-zero
307 2. Find an object in an associative array::
309 void *assoc_array_find(const struct assoc_array *array,
313 This walks through the array's internal tree directly to the object
316 This may be used on an array at the same time as the array is being
324 --------------
332 other - and those with the same length keys to cluster together.
343 one nibble (4 bits) per level, so on a 32-bit CPU this is good for 8 levels and
344 on a 64-bit CPU, 16 levels. Unless the scattering is really poor, it is
352 The associative array data structure has an internal tree. This tree is
355 A node is an array of slots. Each slot can contain one of four things:
364 --------------------------
373 NODE B NODE C +------>+---+
374 +------>+---+ +------>+---+ | | 0 |
375 NODE A | | 0 | | | 0 | | +---+
376 +---+ | +---+ | +---+ | : :
377 | 0 | | : : | : : | +---+
378 +---+ | +---+ | +---+ | | f |
379 | 1 |---+ | 3 |---+ | 7 |---+ +---+
380 +---+ +---+ +---+
381 : : : : | 8 |---+
382 +---+ +---+ +---+ | NODE E
383 | e |---+ | f | : : +------>+---+
384 +---+ | +---+ +---+ | 0 |
385 | f | | | f | +---+
386 +---+ | +---+ : :
387 | NODE F +---+
388 +------>+---+ | f |
389 | 0 | NODE G +---+
390 +---+ +------>+---+
392 +---+ | +---+
393 | 6 |---+ : :
394 +---+ +---+
396 +---+ +---+
398 +---+
400 In the above example, there are 7 nodes (A-G), each with 16 slots (0-f).
408 13[0-69-f]* C
409 1[0-24-f]* B
411 e[0-57-f]* F
412 [02-df]* A
425 9431809de993ba - A
426 b4542910809cd - A
430 f3842239082 - A
434 pointers - even if some of those leaves would like to be in the same slot.
461 ---------
464 is a replacement for a series of single-occupancy nodes ascending through the
467 It is possible for the root of the tree to be a shortcut - say, for example,
475 ------------------------------
487 fewer, then the subtree will be collapsed down to a single node - and this will
491 Non-Recursive Iteration
492 -----------------------
495 slot in that parent that points to it. None-recursive iteration uses these to
503 -------------------------------------
517 may involve replacement of part of that subtree - but that won't affect
523 new layout until we follow the back pointers - at which point we've
527 We might, however, re-see some leaves that have been split out into a new
536 unchanged - and will still be rooted on the same slot, so we shouldn't
544 this without locking against a read - so we have to replace that node too.
549 the slot number first - provided suitable barriers are used to make sure