Lines Matching refs:of
38 Rather, the array is made up of metadata blocks that point to objects.
45 (5) Index keys can be of any length and can be of different lengths.
61 (10) Objects in the array can be looked up by means of their index key.
66 The implementation uses a tree of 16-pointer nodes internally that are indexed
69 what would otherwise be a series of single-occupancy nodes. Further, nodes
94 keeps track of the metadata blocks that will be removed from the tree when the
97 This is also used to keep track of dead blocks and dead objects after the
102 The script appears as outside of the API as a pointer of the type:
131 Various functions take a table of operations:
137 This points to a number of methods, all of which need to be provided:
139 (1) Get a chunk of index key from caller data:
143 This should return a chunk of caller-supplied index key starting at the
145 multiple of ASSOC_ARRAY_KEY_CHUNK_SIZE and the function should return
149 (2) Get a chunk of an object's index key.
165 (4) Diff the index keys of two objects.
169 Return the bit position at which the index key of the specified object
185 There are a number of functions for manipulating an associative array:
204 significant bit of the pointer must be zero as it's used to type-mark
214 an edit script that must be applied. -ENOMEM is returned in the case of
215 an out-of-memory error.
217 The caller should lock exclusively against other modifiers of the array.
233 an edit script that must be applied. -ENOMEM is returned in the case of
234 an out-of-memory error. NULL will be returned if the specified object is
237 The caller should lock exclusively against other modifiers of the array.
250 an edit script that must be applied. -ENOMEM is returned in the case of
251 an out-of-memory error.
253 The caller should lock exclusively against other modifiers of the array.
261 This destroys the contents of the associative array and leaves it
268 of the array.
284 The internal tree will be packed down if possible as part of the iteration
285 to reduce the number of nodes in it.
295 lock exclusively against other modifiers of the array.
320 return the result of the last iterator function called. Iteration stops
344 The index key can be of any form, but since the algorithms aren't told how long
352 It is also recommended that the index key begin with a hash of the rest of the
357 Poor scattering isn't too much of a problem as there are shortcuts and nodes
358 can contain mixtures of leaves and metadata pointers.
360 The index key is read in chunks of machine word. Each chunk is subdivided into
363 unlikely that more than one word of any particular index key will have to be
372 constructed of two types of metadata blocks: nodes and shortcuts.
374 A node is an array of slots. Each slot can contain one of four things:
453 To save memory, if a node can hold all the leaves in its portion of keyspace,
455 pointers - even if some of those leaves would like to be in the same slot.
457 A node can contain a heterogeneous mix of leaves and metadata pointers.
458 Metadata pointers must be in the slots that match their subdivisions of key
460 is guaranteed that none of the leaves in a node will match a slot occupied by a
465 In the above example list of index keys, node A will contain:
484 Shortcuts are metadata records that jump over a piece of keyspace. A shortcut
485 is a replacement for a series of single-occupancy nodes ascending through the
488 It is possible for the root of the tree to be a shortcut - say, for example,
497 Each node has a maximum capacity of 16 leaves and metadata pointers. If the
506 When the number of objects in the subtree rooted at a node falls to 16 or
514 Each node and shortcut contains a back pointer to its parent and the number of
525 There are a number of cases to consider:
536 (3) Insertion replacing part of a subtree that we haven't yet entered. This
537 may involve replacement of part of that subtree - but that won't affect
539 ancestry blocks are not replaced (the layout of those does not change).
545 leaves in a node before following any of its metadata pointers).
550 (5) Insertion replacing nodes that we're processing a dependent branch of.
554 back pointers will get us back to the parent of the new node before we