Lines Matching +full:key +full:- +full:up
20 Rather, the array is made up of metadata blocks that point to objects.
24 4. Index keys must be unique. Inserting an object with the same key as one
35 key order.
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
46 RCU readlock is being held by the thread doing the look up.
48 The implementation uses a tree of 16-pointer nodes internally that are indexed
49 on each level by nibbles from the index key in the same manner as in a radix
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 ----------------
122 1. Get a chunk of index key from caller data::
126 This should return a chunk of caller-supplied index key starting at the
132 2. Get a chunk of an object's index key::
137 rather than from a caller-supplied index key.
144 Compare the object against an index key and return ``true`` if it matches and
152 Return the bit position at which the index key of the specified object
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
189 If an object already exists for that key then it will be replaced with the
192 The ``index_key`` argument should hold index key information and is
196 an edit script that must be applied. ``-ENOMEM`` is returned in the case of
197 an out-of-memory error.
211 The ``index_key`` argument should hold index key information and is
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 ----------------
303 immediately if any call to the iteration function results in a non-zero
314 specified by the index key..
323 Index Key Form
324 --------------
326 The index key can be of any form, but since the algorithms aren't told how long
327 the key is, it is strongly recommended that the index key includes its length
332 other - and those with the same length keys to cluster together.
334 It is also recommended that the index key begin with a hash of the rest of the
335 key to maximise scattering throughout keyspace.
342 The index key is read in chunks of machine word. Each chunk is subdivided into
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
345 unlikely that more than one word of any particular index key will have to be
364 --------------------------
367 key space is strictly subdivided by the nodes in the tree and nodes occur on
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).
401 Assuming no other meta data nodes in the tree, the key space is divided
404 KEY PREFIX NODE
408 13[0-69-f]* C
409 1[0-24-f]* B
411 e[0-57-f]* F
412 [02-df]* A
417 INDEX KEY PREFIX NODE
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.
437 Metadata pointers must be in the slots that match their subdivisions of key
440 metadata pointer. If the metadata pointer is there, any leaf whose key matches
441 the metadata key prefix must be in the subtree that the metadata pointer points
446 SLOT CONTENT INDEX KEY (PREFIX)
461 ---------
464 is a replacement for a series of single-occupancy nodes ascending through the
465 levels. Shortcuts exist to save memory and to speed up traversal.
467 It is possible for the root of the tree to be a shortcut - say, for example,
468 the tree contains at least 17 nodes all with key prefix ``1111``. The
475 ------------------------------
480 key segment at that level end up in a separate node rooted on that slot for
481 that common key segment.
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
543 inserted another node before it and moved it up a level). We cannot do
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
552 Obsolete blocks and leaves are freed up after an RCU grace period has passed,