sphinx.addnodesdocument)}( rawsourcechildren]( translations LanguagesNode)}(hhh](h pending_xref)}(hhh]docutils.nodesTextChinese (Simplified)}parenthsba attributes}(ids]classes]names]dupnames]backrefs] refdomainstdreftypedoc reftarget(/translations/zh_CN/core-api/assoc_arraymodnameN classnameN refexplicitutagnamehhh ubh)}(hhh]hChinese (Traditional)}hh2sbah}(h]h ]h"]h$]h&] refdomainh)reftypeh+ reftarget(/translations/zh_TW/core-api/assoc_arraymodnameN classnameN refexplicituh1hhh ubh)}(hhh]hItalian}hhFsbah}(h]h ]h"]h$]h&] refdomainh)reftypeh+ reftarget(/translations/it_IT/core-api/assoc_arraymodnameN classnameN refexplicituh1hhh ubh)}(hhh]hJapanese}hhZsbah}(h]h ]h"]h$]h&] refdomainh)reftypeh+ reftarget(/translations/ja_JP/core-api/assoc_arraymodnameN classnameN refexplicituh1hhh ubh)}(hhh]hKorean}hhnsbah}(h]h ]h"]h$]h&] refdomainh)reftypeh+ reftarget(/translations/ko_KR/core-api/assoc_arraymodnameN classnameN refexplicituh1hhh ubh)}(hhh]hSpanish}hhsbah}(h]h ]h"]h$]h&] refdomainh)reftypeh+ reftarget(/translations/sp_SP/core-api/assoc_arraymodnameN classnameN refexplicituh1hhh ubeh}(h]h ]h"]h$]h&]current_languageEnglishuh1h hh _documenthsourceNlineNubhsection)}(hhh](htitle)}(h(Generic Associative Array Implementationh]h(Generic Associative Array Implementation}(hhhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhhhB/var/lib/git/docbuild/linux/Documentation/core-api/assoc_array.rsthKubh)}(hhh](h)}(hOverviewh]hOverview}(hhhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhhhhhKubh paragraph)}(h[This associative array implementation is an object container with the following properties:h]h[This associative array implementation is an object container with the following properties:}(hhhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhhhhubhenumerated_list)}(hhh](h list_item)}(hObjects are opaque pointers. The implementation does not care where they point (if anywhere) or what they point to (if anything). .. note:: Pointers to objects _must_ be zero in the least significant bit. h](h)}(hObjects are opaque pointers. The implementation does not care where they point (if anywhere) or what they point to (if anything).h]hObjects are opaque pointers. The implementation does not care where they point (if anywhere) or what they point to (if anything).}(hhhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK hhubhnote)}(h@Pointers to objects _must_ be zero in the least significant bit.h]h)}(hhh]h@Pointers to objects _must_ be zero in the least significant bit.}(hhhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhhubah}(h]h ]h"]h$]h&]uh1hhhubeh}(h]h ]h"]h$]h&]uh1hhhhhhNhNubh)}(hObjects do not need to contain linkage blocks for use by the array. This permits an object to be located in multiple arrays simultaneously. Rather, the array is made up of metadata blocks that point to objects. h]h)}(hObjects do not need to contain linkage blocks for use by the array. This permits an object to be located in multiple arrays simultaneously. Rather, the array is made up of metadata blocks that point to objects.h]hObjects do not need to contain linkage blocks for use by the array. This permits an object to be located in multiple arrays simultaneously. Rather, the array is made up of metadata blocks that point to objects.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjubah}(h]h ]h"]h$]h&]uh1hhhhhhhhNubh)}(h``. The associative array is rooted on the following structure::h](hThe public API can be found in }(hj2hhhNhNubhliteral)}(h````h]h}(hj<hhhNhNubah}(h]h ]h"]h$]h&]uh1j:hj2ubh>. The associative array is rooted on the following structure:}(hj2hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhK;hj!hhubh literal_block)}(h#struct assoc_array { ... };h]h#struct assoc_array { ... };}hjVsbah}(h]h ]h"]h$]h&] xml:spacepreserveuh1jThhhK>hj!hhubh)}(hDThe code is selected by enabling ``CONFIG_ASSOCIATIVE_ARRAY`` with::h](h!The code is selected by enabling }(hjfhhhNhNubj;)}(h``CONFIG_ASSOCIATIVE_ARRAY``h]hCONFIG_ASSOCIATIVE_ARRAY}(hjnhhhNhNubah}(h]h ]h"]h$]h&]uh1j:hjfubh with:}(hjfhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhKBhj!hhubjU)}(h$./script/config -e ASSOCIATIVE_ARRAYh]h$./script/config -e ASSOCIATIVE_ARRAY}hjsbah}(h]h ]h"]h$]h&]jdjeuh1jThhhKDhj!hhubh)}(hhh](h)}(h Edit Scripth]h Edit Script}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjhhhhhKHubh)}(hXIThe insertion and deletion functions produce an 'edit script' that can later be applied to effect the changes without risking ``ENOMEM``. This retains the preallocated metadata blocks that will be installed in the internal tree and keeps track of the metadata blocks that will be removed from the tree when the script is applied.h](hThe insertion and deletion functions produce an ‘edit script’ that can later be applied to effect the changes without risking }(hjhhhNhNubj;)}(h ``ENOMEM``h]hENOMEM}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1j:hjubh. This retains the preallocated metadata blocks that will be installed in the internal tree and keeps track of the metadata blocks that will be removed from the tree when the script is applied.}(hjhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhKJhjhhubh)}(hXThis is also used to keep track of dead blocks and dead objects after the script has been applied so that they can be freed later. The freeing is done after an RCU grace period has passed - thus allowing access functions to proceed under the RCU read lock.h]hXThis is also used to keep track of dead blocks and dead objects after the script has been applied so that they can be freed later. The freeing is done after an RCU grace period has passed - thus allowing access functions to proceed under the RCU read lock.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKPhjhhubh)}(hCThe script appears as outside of the API as a pointer of the type::h]hBThe script appears as outside of the API as a pointer of the type:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKUhjhhubjU)}(hstruct assoc_array_edit;h]hstruct assoc_array_edit;}hjsbah}(h]h ]h"]h$]h&]jdjeuh1jThhhKWhjhhubh)}(h4There are two functions for dealing with the script:h]h4There are two functions for dealing with the script:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKYhjhhubh)}(hhh]h)}(hUApply an edit script:: void assoc_array_apply_edit(struct assoc_array_edit *edit); h](h)}(hApply an edit script::h]hApply an edit script:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK[hjubjU)}(h;void assoc_array_apply_edit(struct assoc_array_edit *edit);h]h;void assoc_array_apply_edit(struct assoc_array_edit *edit);}hjsbah}(h]h ]h"]h$]h&]jdjeuh1jThhhK]hjubeh}(h]h ]h"]h$]h&]uh1hhjhhhhhNubah}(h]h ]h"]h$]h&]jjjhj j uh1hhjhhhhhK[ubh)}(hThis will perform the edit functions, interpolating various write barriers to permit accesses under the RCU read lock to continue. The edit script will then be passed to ``call_rcu()`` to free it and any dead stuff it points to.h](hThis will perform the edit functions, interpolating various write barriers to permit accesses under the RCU read lock to continue. The edit script will then be passed to }(hj,hhhNhNubj;)}(h``call_rcu()``h]h call_rcu()}(hj4hhhNhNubah}(h]h ]h"]h$]h&]uh1j:hj,ubh, to free it and any dead stuff it points to.}(hj,hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhK_hjhhubh)}(hhh]h)}(hWCancel an edit script:: void assoc_array_cancel_edit(struct assoc_array_edit *edit); h](h)}(hCancel an edit script::h]hCancel an edit script:}(hjShhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKdhjOubjU)}(h+---+ +------>+---+ +------>+---+ | | 0 | NODE A | | 0 | | | 0 | | +---+ +---+ | +---+ | +---+ | : : | 0 | | : : | : : | +---+ +---+ | +---+ | +---+ | | f | | 1 |---+ | 3 |---+ | 7 |---+ +---+ +---+ +---+ +---+ : : : : | 8 |---+ +---+ +---+ +---+ | NODE E | e |---+ | f | : : +------>+---+ +---+ | +---+ +---+ | 0 | | f | | | f | +---+ +---+ | +---+ : : | NODE F +---+ +------>+---+ | f | | 0 | NODE G +---+ +---+ +------>+---+ : : | | 0 | +---+ | +---+ | 6 |---+ : : +---+ +---+ : : | f | +---+ +---+ | f | +---+h]hX$Level: 0 1 2 3 =============== =============== =============== =============== NODE D NODE B NODE C +------>+---+ +------>+---+ +------>+---+ | | 0 | NODE A | | 0 | | | 0 | | +---+ +---+ | +---+ | +---+ | : : | 0 | | : : | : : | +---+ +---+ | +---+ | +---+ | | f | | 1 |---+ | 3 |---+ | 7 |---+ +---+ +---+ +---+ +---+ : : : : | 8 |---+ +---+ +---+ +---+ | NODE E | e |---+ | f | : : +------>+---+ +---+ | +---+ +---+ | 0 | | f | | | f | +---+ +---+ | +---+ : : | NODE F +---+ +------>+---+ | f | | 0 | NODE G +---+ +---+ +------>+---+ : : | | 0 | +---+ | +---+ | 6 |---+ : : +---+ +---+ : : | f | +---+ +---+ | f | +---+}hjY sbah}(h]h ]h"]h$]h&]jdjeuh1jThhhMrhj: hhubh)}(hIn the above example, there are 7 nodes (A-G), each with 16 slots (0-f). Assuming no other meta data nodes in the tree, the key space is divided thusly::h]hIn the above example, there are 7 nodes (A-G), each with 16 slots (0-f). Assuming no other meta data nodes in the tree, the key space is divided thusly:}(hjg hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj: hhubjU)}(hKEY PREFIX NODE ========== ==== 137* D 138* E 13[0-69-f]* C 1[0-24-f]* B e6* G e[0-57-f]* F [02-df]* Ah]hKEY PREFIX NODE ========== ==== 137* D 138* E 13[0-69-f]* C 1[0-24-f]* B e6* G e[0-57-f]* F [02-df]* A}hju sbah}(h]h ]h"]h$]h&]jdjeuh1jThhhMhj: hhubh)}(heSo, for instance, keys with the following example index keys will be found in the appropriate nodes::h]hdSo, for instance, keys with the following example index keys will be found in the appropriate nodes:}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj: hhubjU)}(hXqINDEX KEY PREFIX NODE =============== ======= ==== 13694892892489 13 C 13795289025897 137 D 13889dde88793 138 E 138bbb89003093 138 E 1394879524789 12 C 1458952489 1 B 9431809de993ba - A b4542910809cd - A e5284310def98 e F e68428974237 e6 G e7fffcbd443 e F f3842239082 - Ah]hXqINDEX KEY PREFIX NODE =============== ======= ==== 13694892892489 13 C 13795289025897 137 D 13889dde88793 138 E 138bbb89003093 138 E 1394879524789 12 C 1458952489 1 B 9431809de993ba - A b4542910809cd - A e5284310def98 e F e68428974237 e6 G e7fffcbd443 e F f3842239082 - A}hj sbah}(h]h ]h"]h$]h&]jdjeuh1jThhhMhj: hhubh)}(hTo save memory, if a node can hold all the leaves in its portion of keyspace, then the node will have all those leaves in it and will not have any metadata pointers - even if some of those leaves would like to be in the same slot.h]hTo save memory, if a node can hold all the leaves in its portion of keyspace, then the node will have all those leaves in it and will not have any metadata pointers - even if some of those leaves would like to be in the same slot.}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj: hhubh)}(hXA node can contain a heterogeneous mix of leaves and metadata pointers. Metadata pointers must be in the slots that match their subdivisions of key space. The leaves can be in any slot not occupied by a metadata pointer. It is guaranteed that none of the leaves in a node will match a slot occupied by a metadata pointer. If the metadata pointer is there, any leaf whose key matches the metadata key prefix must be in the subtree that the metadata pointer points to.h]hXA node can contain a heterogeneous mix of leaves and metadata pointers. Metadata pointers must be in the slots that match their subdivisions of key space. The leaves can be in any slot not occupied by a metadata pointer. It is guaranteed that none of the leaves in a node will match a slot occupied by a metadata pointer. If the metadata pointer is there, any leaf whose key matches the metadata key prefix must be in the subtree that the metadata pointer points to.}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj: hhubh)}(h>In the above example list of index keys, node A will contain::h]h=In the above example list of index keys, node A will contain:}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj: hhubjU)}(hSLOT CONTENT INDEX KEY (PREFIX) ==== =============== ================== 1 PTR TO NODE B 1* any LEAF 9431809de993ba any LEAF b4542910809cd e PTR TO NODE F e* any LEAF f3842239082h]hSLOT CONTENT INDEX KEY (PREFIX) ==== =============== ================== 1 PTR TO NODE B 1* any LEAF 9431809de993ba any LEAF b4542910809cd e PTR TO NODE F e* any LEAF f3842239082}hj sbah}(h]h ]h"]h$]h&]jdjeuh1jThhhMhj: hhubh)}(h and node B::h]h and node B:}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj: hhubjU)}(h63 PTR TO NODE C 13* any LEAF 1458952489h]h63 PTR TO NODE C 13* any LEAF 1458952489}hj sbah}(h]h ]h"]h$]h&]jdjeuh1jThhhMhj: hhubeh}(h]basic-internal-tree-layoutah ]h"]basic internal tree layoutah$]h&]uh1hhj hhhhhMlubh)}(hhh](h)}(h Shortcutsh]h Shortcuts}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhj hhhhhMubh)}(hShortcuts are metadata records that jump over a piece of keyspace. A shortcut is a replacement for a series of single-occupancy nodes ascending through the levels. Shortcuts exist to save memory and to speed up traversal.h]hShortcuts are metadata records that jump over a piece of keyspace. A shortcut is a replacement for a series of single-occupancy nodes ascending through the levels. Shortcuts exist to save memory and to speed up traversal.}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj hhubh)}(hX6It is possible for the root of the tree to be a shortcut - say, for example, the tree contains at least 17 nodes all with key prefix ``1111``. The insertion algorithm will insert a shortcut to skip over the ``1111`` keyspace in a single bound and get to the fourth level where these actually become different.h](hIt is possible for the root of the tree to be a shortcut - say, for example, the tree contains at least 17 nodes all with key prefix }(hj hhhNhNubj;)}(h``1111``h]h1111}(hj" hhhNhNubah}(h]h ]h"]h$]h&]uh1j:hj ubhC. The insertion algorithm will insert a shortcut to skip over the }(hj hhhNhNubj;)}(h``1111``h]h1111}(hj4 hhhNhNubah}(h]h ]h"]h$]h&]uh1j:hj ubh^ keyspace in a single bound and get to the fourth level where these actually become different.}(hj hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhMhj hhubeh}(h] shortcutsah ]h"] shortcutsah$]h&]uh1hhj hhhhhMubh)}(hhh](h)}(hSplitting And Collapsing Nodesh]hSplitting And Collapsing Nodes}(hjW hhhNhNubah}(h]h ]h"]h$]h&]uh1hhjT hhhhhMubh)}(hXKEach node has a maximum capacity of 16 leaves and metadata pointers. If the insertion algorithm finds that it is trying to insert a 17th object into a node, that node will be split such that at least two leaves that have a common key segment at that level end up in a separate node rooted on that slot for that common key segment.h]hXKEach node has a maximum capacity of 16 leaves and metadata pointers. If the insertion algorithm finds that it is trying to insert a 17th object into a node, that node will be split such that at least two leaves that have a common key segment at that level end up in a separate node rooted on that slot for that common key segment.}(hje hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjT hhubh)}(hIf the leaves in a full node and the leaf that is being inserted are sufficiently similar, then a shortcut will be inserted into the tree.h]hIf the leaves in a full node and the leaf that is being inserted are sufficiently similar, then a shortcut will be inserted into the tree.}(hjs hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjT hhubh)}(hWhen the number of objects in the subtree rooted at a node falls to 16 or fewer, then the subtree will be collapsed down to a single node - and this will ripple towards the root if possible.h]hWhen the number of objects in the subtree rooted at a node falls to 16 or fewer, then the subtree will be collapsed down to a single node - and this will ripple towards the root if possible.}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjT hhubeh}(h]splitting-and-collapsing-nodesah ]h"]splitting and collapsing nodesah$]h&]uh1hhj hhhhhMubh)}(hhh](h)}(hNon-Recursive Iterationh]hNon-Recursive Iteration}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhj hhhhhMubh)}(hX"Each node and shortcut contains a back pointer to its parent and the number of slot in that parent that points to it. None-recursive iteration uses these to proceed rootwards through the tree, going to the parent node, slot N + 1 to make sure progress is made without the need for a stack.h]hX"Each node and shortcut contains a back pointer to its parent and the number of slot in that parent that points to it. None-recursive iteration uses these to proceed rootwards through the tree, going to the parent node, slot N + 1 to make sure progress is made without the need for a stack.}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj hhubh)}(hMThe backpointers, however, make simultaneous alteration and iteration tricky.h]hMThe backpointers, however, make simultaneous alteration and iteration tricky.}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj hhubeh}(h]non-recursive-iterationah ]h"]non-recursive iterationah$]h&]uh1hhj hhhhhMubh)}(hhh](h)}(h%Simultaneous Alteration And Iterationh]h%Simultaneous Alteration And Iteration}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhj hhhhhMubh)}(h(There are a number of cases to consider:h]h(There are a number of cases to consider:}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj hhubh)}(hhh](h)}(hSimple insert/replace. This involves simply replacing a NULL or old matching leaf pointer with the pointer to the new leaf after a barrier. The metadata blocks don't change otherwise. An old leaf won't be freed until after the RCU grace period. h]h)}(hSimple insert/replace. This involves simply replacing a NULL or old matching leaf pointer with the pointer to the new leaf after a barrier. The metadata blocks don't change otherwise. An old leaf won't be freed until after the RCU grace period.h]hSimple insert/replace. This involves simply replacing a NULL or old matching leaf pointer with the pointer to the new leaf after a barrier. The metadata blocks don’t change otherwise. An old leaf won’t be freed until after the RCU grace period.}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj ubah}(h]h ]h"]h$]h&]uh1hhj hhhhhNubh)}(hSimple delete. This involves just clearing an old matching leaf. The metadata blocks don't change otherwise. The old leaf won't be freed until after the RCU grace period. h]h)}(hSimple delete. This involves just clearing an old matching leaf. The metadata blocks don't change otherwise. The old leaf won't be freed until after the RCU grace period.h]hSimple delete. This involves just clearing an old matching leaf. The metadata blocks don’t change otherwise. The old leaf won’t be freed until after the RCU grace period.}(hj hhhNhNubah}(h]h ]h"]h$]h&]uQ5h1hhhhMhj ubah}(h]h ]h"]h$]h&]uh1hhj hhhhhNubh)}(hXInsertion replacing part of a subtree that we haven't yet entered. This may involve replacement of part of that subtree - but that won't affect the iteration as we won't have reached the pointer to it yet and the ancestry blocks are not replaced (the layout of those does not change). h]h)}(hXInsertion replacing part of a subtree that we haven't yet entered. This may involve replacement of part of that subtree - but that won't affect the iteration as we won't have reached the pointer to it yet and the ancestry blocks are not replaced (the layout of those does not change).h]hX#Insertion replacing part of a subtree that we haven’t yet entered. This may involve replacement of part of that subtree - but that won’t affect the iteration as we won’t have reached the pointer to it yet and the ancestry blocks are not replaced (the layout of those does not change).}(hj" hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj ubah}(h]h ]h"]h$]h&]uh1hhj hhhhhNubh)}(hXInsertion replacing nodes that we're actively processing. This isn't a problem as we've passed the anchoring pointer and won't switch onto the new layout until we follow the back pointers - at which point we've already examined the leaves in the replaced node (we iterate over all the leaves in a node before following any of its metadata pointers). We might, however, re-see some leaves that have been split out into a new branch that's in a slot further along than we were at. h](h)}(hX^Insertion replacing nodes that we're actively processing. This isn't a problem as we've passed the anchoring pointer and won't switch onto the new layout until we follow the back pointers - at which point we've already examined the leaves in the replaced node (we iterate over all the leaves in a node before following any of its metadata pointers).h]hXhInsertion replacing nodes that we’re actively processing. This isn’t a problem as we’ve passed the anchoring pointer and won’t switch onto the new layout until we follow the back pointers - at which point we’ve already examined the leaves in the replaced node (we iterate over all the leaves in a node before following any of its metadata pointers).}(hj: hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhM hj6 ubh)}(hWe might, however, re-see some leaves that have been split out into a new branch that's in a slot further along than we were at.h]hWe might, however, re-see some leaves that have been split out into a new branch that’s in a slot further along than we were at.}(hjH hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj6 ubeh}(h]h ]h"]h$]h&]uh1hhj hhhhhNubh)}(hInsertion replacing nodes that we're processing a dependent branch of. This won't affect us until we follow the back pointers. Similar to (4). h]h)}(hInsertion replacing nodes that we're processing a dependent branch of. This won't affect us until we follow the back pointers. Similar to (4).h]hInsertion replacing nodes that we’re processing a dependent branch of. This won’t affect us until we follow the back pointers. Similar to (4).}(hj` hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj\ ubah}(h]h ]h"]h$]h&]uh1hhj hhhhhNubh)}(hXUDeletion collapsing a branch under us. This doesn't affect us because the back pointers will get us back to the parent of the new node before we could see the new node. The entire collapsed subtree is thrown away unchanged - and will still be rooted on the same slot, so we shouldn't process it a second time as we'll go back to slot + 1. h]h)}(hXTDeletion collapsing a branch under us. This doesn't affect us because the back pointers will get us back to the parent of the new node before we could see the new node. The entire collapsed subtree is thrown away unchanged - and will still be rooted on the same slot, so we shouldn't process it a second time as we'll go back to slot + 1.h]hXZDeletion collapsing a branch under us. This doesn’t affect us because the back pointers will get us back to the parent of the new node before we could see the new node. The entire collapsed subtree is thrown away unchanged - and will still be rooted on the same slot, so we shouldn’t process it a second time as we’ll go back to slot + 1.}(hjx hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjt ubah}(h]h ]h"]h$]h&]uh1hhj hhhhhNubeh}(h]h ]h"]h$]h&]jjjhj j uh1hhj hhhhhMubh)}(hXxUnder some circumstances, we need to simultaneously change the parent pointer and the parent slot pointer on a node (say, for example, we inserted another node before it and moved it up a level). We cannot do this without locking against a read - so we have to replace that node too. However, when we're changing a shortcut into a node this isn't a problem as shortcuts only have one slot and so the parent slot number isn't used when traversing backwards over one. This means that it's okay to change the slot number first - provided suitable barriers are used to make sure the parent slot number is read after the back pointer.h](h)}(hXUnder some circumstances, we need to simultaneously change the parent pointer and the parent slot pointer on a node (say, for example, we inserted another node before it and moved it up a level). We cannot do this without locking against a read - so we have to replace that node too.h]hXUnder some circumstances, we need to simultaneously change the parent pointer and the parent slot pointer on a node (say, for example, we inserted another node before it and moved it up a level). We cannot do this without locking against a read - so we have to replace that node too.}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj ubh)}(hXZHowever, when we're changing a shortcut into a node this isn't a problem as shortcuts only have one slot and so the parent slot number isn't used when traversing backwards over one. This means that it's okay to change the slot number first - provided suitable barriers are used to make sure the parent slot number is read after the back pointer.h]hXbHowever, when we’re changing a shortcut into a node this isn’t a problem as shortcuts only have one slot and so the parent slot number isn’t used when traversing backwards over one. This means that it’s okay to change the slot number first - provided suitable barriers are used to make sure the parent slot number is read after the back pointer.}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhM"hj ubeh}(h]h ]h"]h$]h&]uh1hhj hhhhhNubh)}(hObsolete blocks and leaves are freed up after an RCU grace period has passed, so as long as anyone doing walking or iteration holds the RCU read lock, the old superstructure should not go away on them.h]hObsolete blocks and leaves are freed up after an RCU grace period has passed, so as long as anyone doing walking or iteration holds the RCU read lock, the old superstructure should not go away on them.}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhM(hj hhubeh}(h]%simultaneous-alteration-and-iterationah ]h"]%simultaneous alteration and iterationah$]h&]uh1hhj hhhhhMubeh}(h]internal-workingsah ]h"]internal workingsah$]h&]uh1hhhhhhhhM^ubeh}(h](generic-associative-array-implementationah ]h"](generic associative array implementationah$]h&]uh1hhhhhhhhKubeh}(h]h ]h"]h$]h&]sourcehuh1hcurrent_sourceN current_lineNsettingsdocutils.frontendValues)}(hN generatorN datestampN source_linkN source_urlN toc_backlinksentryfootnote_backlinksK sectnum_xformKstrip_commentsNstrip_elements_with_classesN strip_classesN report_levelK halt_levelKexit_status_levelKdebugNwarning_streamN tracebackinput_encoding utf-8-siginput_encoding_error_handlerstrictoutput_encodingutf-8output_encoding_error_handlerjerror_encodingutf-8error_encoding_error_handlerbackslashreplace language_codeenrecord_dependenciesNconfigN id_prefixhauto_id_prefixid dump_settingsNdump_internalsNdump_transformsNdump_pseudo_xmlNexpose_internalsNstrict_visitorN_disable_configN_sourceh _destinationN _config_files]7/var/lib/git/docbuild/linux/Documentation/docutils.confafile_insertion_enabled raw_enabledKline_length_limitM'pep_referencesN pep_base_urlhttps://peps.python.org/pep_file_url_templatepep-%04drfc_referencesN rfc_base_url&https://datatracker.ietf.org/doc/html/ tab_widthKtrim_footnote_reference_spacesyntax_highlightlong smart_quotessmartquotes_locales]character_level_inline_markupdoctitle_xform docinfo_xformKsectsubtitle_xform image_loadinglinkembed_stylesheetcloak_email_addressessection_self_linkenvNubreporterNindirect_targets]substitution_defs}substitution_names}refnames}refids}nameids}(j j jjj j jjjjj j j+ j( j j j j j j jQ jN j j j j j j u nametypes}(j jj jjj j+ j j j jQ j j j uh}(j hjhj j!jjjjj jj( j j j. j j j j: jN j j jT j j j j u footnote_refs} citation_refs} autofootnotes]autofootnote_refs]symbol_footnotes]symbol_footnote_refs] footnotes] citations]autofootnote_startKsymbol_footnote_startK id_counter collectionsCounter}Rparse_messages](hsystem_message)}(hhh]h)}(h:Enumerated list start value not ordinal-1: "2" (ordinal 2)h]h>Enumerated list start value not ordinal-1: “2” (ordinal 2)}(hjhhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjeubah}(h]h ]h"]h$]h&]levelKtypeINFOsourcehlineKuh1jchjhhhhhKdubjd)}(hhh]h)}(h:Enumerated list start value not ordinal-1: "2" (ordinal 2)h]h>Enumerated list start value not ordinal-1: “2” (ordinal 2)}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjubah}(h]h ]h"]h$]h&]levelKtypej~sourcehlineKuh1jchjhhhhhKubjd)}(hhh]h)}(h:Enumerated list start value not ordinal-1: "3" (ordinal 3)h]h>Enumerated list start value not ordinal-1: “3” (ordinal 3)}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjubah}(h]h ]h"]h$]h&]levelKtypej~sourcehlineKuh1jchjhhhhhKubjd)}(hhh]h)}(h:Enumerated list start value not ordinal-1: "4" (ordinal 4)h]h>Enumerated list start value not ordinal-1: “4” (ordinal 4)}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjubah}(h]h ]h"]h$]h&]levelKtypej~sourcehlineKuh1jchjhhhhhKubjd)}(hhh]h)}(h:Enumerated list start value not ordinal-1: "5" (ordinal 5)h]h>Enumerated list start value not ordinal-1: “5” (ordinal 5)}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjubah}(h]h ]h"]h$]h&]levelKtypej~sourcehlineKuh1jchjhhhhhKubjd)}(hhh]h)}(h:Enumerated list start value not ordinal-1: "2" (ordinal 2)h]h>Enumerated list start value not ordinal-1: “2” (ordinal 2)}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjubah}(h]h ]h"]h$]h&]levelKtypej~sourcehlineKuh1jchjhhhhhKubjd)}(hhh]h)}(h:Enumerated list start value not ordinal-1: "3" (ordinal 3)h]h>Enumerated list start value not ordinal-1: “3” (ordinal 3)}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhjubah}(h]h ]h"]h$]h&]levelKtypej~sourcehlineKuh1jchjhhhhhKubjd)}(hhh]h)}(h:Enumerated list start value not ordinal-1: "4" (ordinal 4)h]h>Enumerated list start value not ordinal-1: “4” (ordinal 4)}(hj&hhhNhNubah}(h]h ]h"]h$]h&]uh1hhj#ubah}(h]h ]h"]h$]h&]levelKtypej~sourcehlineKuh1jchjhhhhhKubjd)}(hhh]h)}(h:Enumerated list start value not ordinal-1: "5" (ordinal 5)h]h>Enumerated list start value not ordinal-1: “5” (ordinal 5)}(hjAhhhNhNubah}(h]h ]h"]h$]h&]uh1hhj>ubah}(h]h ]h"]h$]h&]levelKtypej~sourcehlineKuh1jchjhhhhhKubjd)}(hhh]h)}(h:Enumerated list start value not ordinal-1: "6" (ordinal 6)h]h>Enumerated list start value not ordinal-1: “6” (ordinal 6)}(hj\hhhNhNubah}(h]h ]h"]h$]h&]uh1hhjYubah}(h]h ]h"]h$]h&]levelKtypej~sourcehlineKuh1jchjhhhhhKubjd)}(hhh]h)}(h:Enumerated list start value not ordinal-1: "2" (ordinal 2)h]h>Enumerated list start value not ordinal-1: “2” (ordinal 2)}(hjwhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjtubah}(h]h ]h"]h$]h&]levelKtypej~sourcehlineKuh1jchj hhhhhM3ubetransform_messages] transformerN include_log] decorationNhhub.