Lines Matching +full:parent +full:- +full:locked
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
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
137 rather than from a caller-supplied index key.
153 differs from the given index key or -1 if they are the same.
166 ----------------------
186 significant bit of the pointer must be zero as it's used to type-mark
196 an edit script that must be applied. ``-ENOMEM`` is returned in the case of
197 an out-of-memory error.
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
232 an edit script that must be applied. ``-ENOMEM`` is returned in the case of
233 an out-of-memory error.
246 destroying it as no RCU deferral is performed on memory release -
272 The function will return ``0`` if successful and ``-ENOMEM`` if there wasn't
281 ----------------
298 this is a problem, then modification should be locked against. The
303 immediately if any call to the iteration function results in a non-zero
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
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 -----------------------
494 Each node and shortcut contains a back pointer to its parent and the number of
495 slot in that parent that points to it. None-recursive iteration uses these to
496 proceed rootwards through the tree, going to the parent node, slot N + 1 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
534 back pointers will get us back to the parent of the new node before we
536 unchanged - and will still be rooted on the same slot, so we shouldn't
541 Under some circumstances, we need to simultaneously change the parent
542 pointer and the parent slot pointer on a node (say, for example, we
544 this without locking against a read - so we have to replace that node too.
547 as shortcuts only have one slot and so the parent slot number isn't used
549 the slot number first - provided suitable barriers are used to make sure
550 the parent slot number is read after the back pointer.