sphinx.addnodesdocument)}( rawsourcechildren]( translations LanguagesNode)}(hhh](h pending_xref)}(hhh]docutils.nodesTextEnglish}parenthsba attributes}(ids]classes]names]dupnames]backrefs] refdomainstdreftypedoc reftarget/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_languageChinese (Simplified)uh1h hh _documenthsourceNlineNubhnote)}(hX{此文件的目的是为让中文读者更容易阅读和理解，而不是作为一个分支。 因此， 如果您对此文件有任何意见或更新，请先尝试更新原始英文文件。 如果您发现本文档与原始文件有任何不同或者有翻译问题，请发建议或者补丁给 该文件的译者，或者请求中文文档维护者和审阅者的帮助。h]h paragraph)}(hX{此文件的目的是为让中文读者更容易阅读和理解，而不是作为一个分支。 因此， 如果您对此文件有任何意见或更新，请先尝试更新原始英文文件。 如果您发现本文档与原始文件有任何不同或者有翻译问题，请发建议或者补丁给 该文件的译者，或者请求中文文档维护者和审阅者的帮助。h]hX{此文件的目的是为让中文读者更容易阅读和理解，而不是作为一个分支。 因此， 如果您对此文件有任何意见或更新，请先尝试更新原始英文文件。 如果您发现本文档与原始文件有任何不同或者有翻译问题，请发建议或者补丁给 该文件的译者，或者请求中文文档维护者和审阅者的帮助。}(hhhhhNhNubah}(h]h ]h"]h$]h&]uh1hh5Documentation/translations/zh_CN/disclaimer-zh_CN.rsthKhhubah}(h]h ]h"]h$]h&]uh1hhhhhhhhNubh field_list)}(hhh](hfield)}(hhh](h field_name)}(hOriginalh]hOriginal}(hhhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhU/var/lib/git/docbuild/linux/Documentation/translations/zh_CN/core-api/assoc_array.rsthKubh field_body)}(h'Documentation/core-api/assoc_array.rst h]h)}(h&Documentation/core-api/assoc_array.rsth]h&Documentation/core-api/assoc_array.rst}(hhhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhhubah}(h]h ]h"]h$]h&]uh1hhhubeh}(h]h ]h"]h$]h&]uh1hhhhKhhhhubh)}(hhh](h)}(h翻译h]h翻译}(hhhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhhhKubh)}(h-司延腾 Yanteng Si h]h)}(h,司延腾 Yanteng Si h](h司延腾 Yanteng Si <}(hjhhhNhNubh reference)}(hsiyanteng@loongson.cnh]hsiyanteng@loongson.cn}(hjhhhNhNubah}(h]h ]h"]h$]h&]refurimailto:siyanteng@loongson.cnuh1jhjubh>}(hjhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhKhj ubah}(h]h ]h"]h$]h&]uh1hhhubeh}(h]h ]h"]h$]h&]uh1hhhhKhhhhubh)}(hhh](h)}(h校译h]h校译}(hjAhhhNhNubah}(h]h ]h"]h$]h&]uh1hhj>hhhKubh)}(hhh]h}(h]h ]h"]h$]h&]uh1hhj>ubeh}(h]h ]h"]h$]h&]uh1hhhhK hhhhubeh}(h]h ]h"]h$]h&]uh1hhhhhhhhKubhtarget)}(h.. _cn_core-api_assoc_array:h]h}(h]h ]h"]h$]h&]refidcn-core-api-assoc-arrayuh1jdhKhhhhhhubhsection)}(hhh](htitle)}(h通用关联数组的实现h]h通用关联数组的实现}(hjyhhhNhNubah}(h]h ]h"]h$]h&]uh1jwhjthhhhhKubjs)}(hhh](jx)}(h简介h]h简介}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jwhjhhhhhKubh)}(hF这个关联数组的实现是一个具有以下属性的对象容器:h]hF这个关联数组的实现是一个具有以下属性的对象容器:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjhhubhenumerated_list)}(hhh](h list_item)}(h对象是不透明的指针。该实现不关心它们指向哪里（如果有的话）或它们指向什么（如果有的 话）。 .. note:: 指向对象的指针 *必须* 在最小有效位为零。 h](h)}(h对象是不透明的指针。该实现不关心它们指向哪里（如果有的话）或它们指向什么（如果有的 话）。h]h对象是不透明的指针。该实现不关心它们指向哪里（如果有的话）或它们指向什么（如果有的 话）。}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjubh)}(h:指向对象的指针 *必须* 在最小有效位为零。h]h)}(hjh](h指向对象的指针 }(hjhhhNhNubhemphasis)}(h*必须*h]h必须}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh 在最小有效位为零。}(hjhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhKhjubah}(h]h ]h"]h$]h&]uh1hhjubeh}(h]h ]h"]h$]h&]uh1jhjhhhNhNubj)}(h对象不需要包含供数组使用的链接块。这允许一个对象同时位于多个数组中。相反，数组是 由指向对象的元数据块组成的。 h]h)}(h对象不需要包含供数组使用的链接块。这允许一个对象同时位于多个数组中。相反，数组是 由指向对象的元数据块组成的。h]h对象不需要包含供数组使用的链接块。这允许一个对象同时位于多个数组中。相反，数组是 由指向对象的元数据块组成的。}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjubah}(h]h ]h"]h$]h&]uh1jhjhhhhhNubj)}(h=对象需要索引键来定位它们在阵列中的位置。 h]h)}(h<对象需要索引键来定位它们在阵列中的位置。h]h<对象需要索引键来定位它们在阵列中的位置。}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK"hjubah}(h]h ]h"]h$]h&]uh1jhjhhhhhNubj)}(hy索引键必须是唯一的。插入一个与已经在数组中的且具有相同键值的对象将取代旧的对象。 h]h)}(hx索引键必须是唯一的。插入一个与已经在数组中的且具有相同键值的对象将取代旧的对象。h]hx索引键必须是唯一的。插入一个与已经在数组中的且具有相同键值的对象将取代旧的对象。}(hj$hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK$hj ubah}(h]h ]h"]h$]h&]uh1jhjhhhhhNubj)}(h@索引键可以是任何长度，也可以是不同的长度。 h]h)}(h?索引键可以是任何长度，也可以是不同的长度。h]h?索引键可以是任何长度，也可以是不同的长度。}(hj<hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK&hj8ubah}(h]h ]h"]h$]h&]uh1jhjhhhhhNubj)}(hj索引键应该在早期就对长度进行编码，即在任何由于长度引起的变化出现之前。 h]h)}(hi索引键应该在早期就对长度进行编码，即在任何由于长度引起的变化出现之前。h]hi索引键应该在早期就对长度进行编码，即在任何由于长度引起的变化出现之前。}(hjThhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK(hjPubah}(h]h ]h"]h$]h&]uh1jhjhhhhhNubj)}(hR索引键可以包括一个哈希值，以便将对象分散到整个数组中。 h]h)}(hQ索引键可以包括一个哈希值，以便将对象分散到整个数组中。h]hQ索引键可以包括一个哈希值，以便将对象分散到整个数组中。}(hjlhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK*hjhubah}(h]h ]h"]h$]h&]uh1jhjhhhhhNubj)}(hI该数组可以迭代。对象不一定会按索引键的顺序出现。 h]h)}(hH该数组可以迭代。对象不一定会按索引键的顺序出现。h]hH该数组可以迭代。对象不一定会按索引键的顺序出现。}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK,hjubah}(h]h ]h"]h$]h&]uh1jhjhhhhhNubj)}(hX&数组可以在被修改的时候进行迭代，只要RCU的读锁被迭代器持有。然而，请注意，在这种情 况下，一些对象可能会被看到不止一次。如果这是个问题，迭代器应该锁定以防止修改。然 而，除非删除，否则对象不会被错过。 h]h)}(hX%数组可以在被修改的时候进行迭代，只要RCU的读锁被迭代器持有。然而，请注意，在这种情 况下，一些对象可能会被看到不止一次。如果这是个问题，迭代器应该锁定以防止修改。然 而，除非删除，否则对象不会被错过。h]hX%数组可以在被修改的时候进行迭代，只要RCU的读锁被迭代器持有。然而，请注意，在这种情 况下，一些对象可能会被看到不止一次。如果这是个问题，迭代器应该锁定以防止修改。然 而，除非删除，否则对象不会被错过。}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK.hjubah}(h]h ]h"]h$]h&]uh1jhjhhhhhNubj)}(h:数组中的对象可以通过其索引键进行查询。 h]h)}(h9数组中的对象可以通过其索引键进行查询。h]h9数组中的对象可以通过其索引键进行查询。}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK2hjubah}(h]h ]h"]h$]h&]uh1jhjhhhhhNubj)}(hd当数组被修改时，对象可以被查询，前提是进行查询的线程持有RCU的读锁。 h]h)}(hc当数组被修改时，对象可以被查询，前提是进行查询的线程持有RCU的读锁。h]hc当数组被修改时，对象可以被查询，前提是进行查询的线程持有RCU的读锁。}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK4hjubah}(h]h ]h"]h$]h&]uh1jhjhhhhhNubeh}(h]h ]h"]h$]h&]enumtypearabicprefixhsuffix.uh1jhjhhhhhKubh)}(hX该实现在内部使用了一棵由16个指针节点组成的树，这些节点在每一层都由索引键的小数点进行索 引，其方式与基数树相同。为了提高内存效率，可以放置快捷键，以跳过本来是一系列单占节点的地 方。此外，节点将叶子对象指针打包到节点的空闲空间中，而不是做一个额外的分支，直到有对象 需要被添加到一个完整的节点中。h]hX该实现在内部使用了一棵由16个指针节点组成的树，这些节点在每一层都由索引键的小数点进行索 引，其方式与基数树相同。为了提高内存效率，可以放置快捷键，以跳过本来是一系列单占节点的地 方。此外，节点将叶子对象指针打包到节点的空闲空间中，而不是做一个额外的分支，直到有对象 需要被添加到一个完整的节点中。}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK6hjhhubeh}(h]id2ah ]h"]简介ah$]h&]uh1jrhjthhhhhKubjs)}(hhh](jx)}(h 公用APIh]h 公用API}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jwhjhhhhhK`` 中找到。关联数组的根是以下结构::h](h公用API可以在 }(hjhhhNhNubhliteral)}(h````h]h}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh/ 中找到。关联数组的根是以下结构:}(hjhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhK>hjhhubh literal_block)}(h#struct assoc_array { ... };h]h#struct assoc_array { ... };}hj6sbah}(h]h ]h"]h$]h&] xml:spacepreserveuh1j4hhhK@hjhhubh)}(hJ该代码是通过启用 ``CONFIG_ASSOCIATIVE_ARRAY`` 来选择的，以::h](h该代码是通过启用 }(hjFhhhNhNubj)}(h``CONFIG_ASSOCIATIVE_ARRAY``h]hCONFIG_ASSOCIATIVE_ARRAY}(hjNhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjFubh 来选择的，以:}(hjFhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhKDhjhhubj5)}(h$./script/config -e ASSOCIATIVE_ARRAYh]h$./script/config -e ASSOCIATIVE_ARRAY}hjfsbah}(h]h ]h"]h$]h&]jDjEuh1j4hhhKFhjhhubjs)}(hhh](jx)}(h 编辑脚本h]h 编辑脚本}(hjwhhhNhNubah}(h]h ]h"]h$]h&]uh1jwhjthhhhhKJubh)}(hX插入和删除功能会产生一个“编辑脚本”，以后可以应用这个脚本来实现更改，而不会造成 ``ENOMEM`` 风险。这保留了将被安装在内部树中的预分配的元数据块，并跟踪应用脚本时将从树中删除的元数 据块。h](hy插入和删除功能会产生一个“编辑脚本”，以后可以应用这个脚本来实现更改，而不会造成 }(hjhhhNhNubj)}(h ``ENOMEM``h]hENOMEM}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh 风险。这保留了将被安装在内部树中的预分配的元数据块，并跟踪应用脚本时将从树中删除的元数 据块。}(hjhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhKLhjthhubh)}(h在脚本应用后，这也被用来跟踪死块和死对象，以便以后可以释放它们。释放是在RCU宽限期过后 进行的--因此允许访问功能在RCU读锁下进行。h]h在脚本应用后，这也被用来跟踪死块和死对象，以便以后可以释放它们。释放是在RCU宽限期过后 进行的--因此允许访问功能在RCU读锁下进行。}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKPhjthhubh)}(h,脚本在API之外显示为一个类型为::h]h+脚本在API之外显示为一个类型为:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKShjthhubj5)}(hstruct assoc_array_edit;h]hstruct assoc_array_edit;}hjsbah}(h]h ]h"]h$]h&]jDjEuh1j4hhhKUhjthhubh)}(h有两个处理脚本的功能:h]h有两个处理脚本的功能:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKWhjthhubj)}(hhh]j)}(hY应用一个编辑脚本:: void assoc_array_apply_edit(struct assoc_array_edit *edit); h](h)}(h应用一个编辑脚本::h]h应用一个编辑脚本:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKYhjubj5)}(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&]jDjEuh1j4hhhK[hjubeh}(h]h ]h"]h$]h&]uh1jhjhhhhhNubah}(h]h ]h"]h$]h&]jjjhjjuh1jhjthhhhhKYubh)}(h这将执行编辑功能，插值各种写屏障，以允许在RCU读锁下的访问继续进行。然后，编辑脚本将被 传递给 ``call_rcu()`` ，以释放它和它所指向的任何死的东西。h](h这将执行编辑功能，插值各种写屏障，以允许在RCU读锁下的访问继续进行。然后，编辑脚本将被 传递给 }(hj hhhNhNubj)}(h``call_rcu()``h]h call_rcu()}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhj ubh7 ，以释放它和它所指向的任何死的东西。}(hj hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhK]hjthhubj)}(hhh]j)}(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:}(hj3hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK`hj/ubj5)}(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 | +---+}hj+ sbah}(h]h ]h"]h$]h&]jDjEuh1j4hhhMAhj hhubh)}(h在上述例子中，有7个节点（A-G），每个节点有16个槽（0-f）。假设树上没有其他元数据节点，那么密钥空间 是这样划分的::h]h在上述例子中，有7个节点（A-G），每个节点有16个槽（0-f）。假设树上没有其他元数据节点，那么密钥空间 是这样划分的:}(hj9 hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhM_hj hhubj5)}(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}hjG sbah}(h]h ]h"]h$]h&]jDjEuh1j4hhhMbhj hhubh)}(hV因此，例如，具有以下示例索引键的键将在适当的节点中被找到::h]hU因此，例如，具有以下示例索引键的键将在适当的节点中被找到:}(hjU hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMlhj hhubj5)}(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}hjc sbah}(h]h ]h"]h$]h&]jDjEuh1j4hhhMnhj hhubh)}(h为了节省内存，如果一个节点可以容纳它的那部分键空间中的所有叶子，那么这个节点将有所有这些叶子，而不 会有任何元数据指针——即使其中一些叶子想在同一个槽中。h]h为了节省内存，如果一个节点可以容纳它的那部分键空间中的所有叶子，那么这个节点将有所有这些叶子，而不 会有任何元数据指针——即使其中一些叶子想在同一个槽中。}(hjq hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhM}hj hhubh)}(hX一个节点可以包含叶子和元数据指针的异质性混合。元数据指针必须在与它们的关键空间的细分相匹配的槽中。 叶子可以在任何没有被元数据指针占据的槽中。保证一个节点中没有一个叶子会与元数据指针占据的槽相匹配。 如果元数据指针在那里，任何键与元数据键前缀相匹配的叶必须在元数据指针指向的子树中。h]hX一个节点可以包含叶子和元数据指针的异质性混合。元数据指针必须在与它们的关键空间的细分相匹配的槽中。 叶子可以在任何没有被元数据指针占据的槽中。保证一个节点中没有一个叶子会与元数据指针占据的槽相匹配。 如果元数据指针在那里，任何键与元数据键前缀相匹配的叶必须在元数据指针指向的子树中。}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj hhubh)}(h<在上面的索引键的例子列表中，节点A将包含::h]h;在上面的索引键的例子列表中，节点A将包含:}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj hhubj5)}(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&]jDjEuh1j4hhhMhj hhubh)}(h 和节点B::h]h 和节点B:}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj hhubj5)}(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&]jDjEuh1j4hhhMhj hhubeh}(h]id9ah ]h"]基本的内部树形布局ah$]h&]uh1jrhju hhhhhM=ubjs)}(hhh](jx)}(h 快捷键h]h 快捷键}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1jwhj hhhhhMubh)}(h快捷键是跳过一块键空间的元数据记录。快捷键是一系列通过层次上升的单占节点的替代物。快捷键的存在是 为了节省内存和加快遍历速度。h]h快捷键是跳过一块键空间的元数据记录。快捷键是一系列通过层次上升的单占节点的替代物。快捷键的存在是 为了节省内存和加快遍历速度。}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj hhubh)}(hX树的根部有可能是一个快捷键——比如说，树至少包含17个节点，都有键前缀 ``1111`` 。插入算法将插入一个快捷键， 以单次跳过 ``1111`` 的键位，并到达第四层，在这里，这些键位实际上变得不同。h](hf树的根部有可能是一个快捷键——比如说，树至少包含17个节点，都有键前缀 }(hj hhhNhNubj)}(h``1111``h]h1111}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1jhj ubh< 。插入算法将插入一个快捷键， 以单次跳过 }(hj hhhNhNubj)}(h``1111``h]h1111}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1jhj ubhR 的键位，并到达第四层，在这里，这些键位实际上变得不同。}(hj hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhMhj hhubeh}(h]id10ah ]h"] 快捷键ah$]h&]uh1jrhju hhhhhMubjs)}(hhh](jx)}(h拆分和合并节点h]h拆分和合并节点}(hj) hhhNhNubah}(h]h ]h"]h$]h&]uh1jwhj& hhhhhMubh)}(hX;每个节点的最大容量为16个叶子和元数据指针。如果插入算法发现它正试图将一个第17个对象插入到一个节点中， 该节点将被拆分，使得至少两个在该层有一个共同的关键段的叶子最终在一个单独的节点中，该共同的关键段的根 在该槽上。h]hX;每个节点的最大容量为16个叶子和元数据指针。如果插入算法发现它正试图将一个第17个对象插入到一个节点中， 该节点将被拆分，使得至少两个在该层有一个共同的关键段的叶子最终在一个单独的节点中，该共同的关键段的根 在该槽上。}(hj7 hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj& hhubh)}(hx如果一个完整的节点中的叶子和被插入的叶子足够相似，那么就会在树中插入一个快捷键。h]hx如果一个完整的节点中的叶子和被插入的叶子足够相似，那么就会在树中插入一个快捷键。}(hjE hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj& hhubh)}(h当根植于某个节点的子树中的对象数量下降到16个或更少时，那么该子树将被合并成一个单独的节点——如果可能的 话，这将向根部扩散。h]h当根植于某个节点的子树中的对象数量下降到16个或更少时，那么该子树将被合并成一个单独的节点——如果可能的 话，这将向根部扩散。}(hjS hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj& hhubeh}(h]id11ah ]h"]拆分和合并节点ah$]h&]uh1jrhju hhhhhMubjs)}(hhh](jx)}(h非递归式迭代h]h非递归式迭代}(hjl hhhNhNubah}(h]h ]h"]h$]h&]uh1jwhji hhhhhMubh)}(h每个节点和快捷键都包含一个指向其父节点的后置指针，以及该父节点中指向它的槽数。非递归迭代使用这些来 通过树的根部进行，前往父节点，槽N+1，以确保在没有堆栈的情况下取得进展。h]h每个节点和快捷键都包含一个指向其父节点的后置指针，以及该父节点中指向它的槽数。非递归迭代使用这些来 通过树的根部进行，前往父节点，槽N+1，以确保在没有堆栈的情况下取得进展。}(hjz hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhji hhubh)}(hB然而，反向指针使得同时改变和迭代变得很棘手。h]hB然而，反向指针使得同时改变和迭代变得很棘手。}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhji hhubeh}(h]id12ah ]h"]非递归式迭代ah$]h&]uh1jrhju hhhhhMubjs)}(hhh](jx)}(h同时改变和迭代h]h同时改变和迭代}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1jwhj hhhhhMubh)}(h有一些情况需要考虑:h]h有一些情况需要考虑:}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj hhubj)}(hhh](j)}(h简单的插入/替换。这涉及到简单地将一个NULL或旧的匹配叶子的指针替换为屏障后的新叶子的指针。否则元数 据块不会改变。一个旧的叶子直到RCU宽限期过后才会被释放。 h]h)}(h简单的插入/替换。这涉及到简单地将一个NULL或旧的匹配叶子的指针替换为屏障后的新叶子的指针。否则元数 据块不会改变。一个旧的叶子直到RCU宽限期过后才会被释放。h]h简单的插入/替换。这涉及到简单地将一个NULL或旧的匹配叶子的指针替换为屏障后的新叶子的指针。否则元数 据块不会改变。一个旧的叶子直到RCU宽限期过后才会被释放。}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj ubah}(h]h ]h"]h$]h&]uh1jhj hhhhhNubj)}(h简单删除。这只是涉及到清除一个旧的匹配叶子。元数据块不会有其他变化。旧的叶子直到RCU宽限期之后才会 被释放。 h]h)}(h简单删除。这只是涉及到清除一个旧的匹配叶子。元数据块不会有其他变化。旧的叶子直到RCU宽限期之后才会 被释放。h]h简单删除。这只是涉及到清除一个旧的匹配叶子。元数据块不会有其他变化。旧的叶子直到RCU宽限期之后才会 被释放。}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj ubah}(h]h ]h"]h$]h&]uh1jhj hhhhhNubj)}(/5h插入，替换我们还没有进入的子树的一部分。这可能涉及到替换该子树的一部分——但这不会影响迭代，因为我们 还没有到达它的指针，而且祖先块也不会被替换（这些块的布局不会改变）。 h]h)}(h插入，替换我们还没有进入的子树的一部分。这可能涉及到替换该子树的一部分——但这不会影响迭代，因为我们 还没有到达它的指针，而且祖先块也不会被替换（这些块的布局不会改变）。h]h插入，替换我们还没有进入的子树的一部分。这可能涉及到替换该子树的一部分——但这不会影响迭代，因为我们 还没有到达它的指针，而且祖先块也不会被替换（这些块的布局不会改变）。}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj ubah}(h]h ]h"]h$]h&]uh1jhj hhhhhNubj)}(hX插入替换了我们正在处理的节点。这不是一个问题，因为我们已经通过了锚定指针，直到我们跟随后面的指针才 会切换到新的布局上——这时我们已经检查了被替换节点的叶子（在跟随任何元数据指针之前，我们会迭代一个节 点的所有叶子）。 然而，我们可能会重新看到一些叶子，这些叶子已经被分割成一个新的分支，而这个分支的位置比我们之前的位 置更远。 h](h)}(hXC插入替换了我们正在处理的节点。这不是一个问题，因为我们已经通过了锚定指针，直到我们跟随后面的指针才 会切换到新的布局上——这时我们已经检查了被替换节点的叶子（在跟随任何元数据指针之前，我们会迭代一个节 点的所有叶子）。h]hXC插入替换了我们正在处理的节点。这不是一个问题，因为我们已经通过了锚定指针，直到我们跟随后面的指针才 会切换到新的布局上——这时我们已经检查了被替换节点的叶子（在跟随任何元数据指针之前，我们会迭代一个节 点的所有叶子）。}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjubh)}(h然而，我们可能会重新看到一些叶子，这些叶子已经被分割成一个新的分支，而这个分支的位置比我们之前的位 置更远。h]h然而，我们可能会重新看到一些叶子，这些叶子已经被分割成一个新的分支，而这个分支的位置比我们之前的位 置更远。}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjubeh}(h]h ]h"]h$]h&]uh1jhj hhhhhNubj)}(h插入替换了我们正在处理的依赖分支的节点。这不会影响到我们，直到我们跟随后面的指针。与（4）类似。 h]h)}(h插入替换了我们正在处理的依赖分支的节点。这不会影响到我们，直到我们跟随后面的指针。与（4）类似。h]h插入替换了我们正在处理的依赖分支的节点。这不会影响到我们，直到我们跟随后面的指针。与（4）类似。}(hj2hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj.ubah}(h]h ]h"]h$]h&]uh1jhj hhhhhNubj)}(hXI删掉我们下面的一个分支。这不会影响我们，因为在我们看到新节点之前，回溯指针会让我们回到新节点的父节 点。整个崩溃的子树被扔掉了，没有任何变化——而且仍然会在同一个槽上生根，所以我们不应该第二次处理它， 因为我们会回到槽+1。 h]h)}(hXH删掉我们下面的一个分支。这不会影响我们，因为在我们看到新节点之前，回溯指针会让我们回到新节点的父节 点。整个崩溃的子树被扔掉了，没有任何变化——而且仍然会在同一个槽上生根，所以我们不应该第二次处理它， 因为我们会回到槽+1。h]hXH删掉我们下面的一个分支。这不会影响我们，因为在我们看到新节点之前，回溯指针会让我们回到新节点的父节 点。整个崩溃的子树被扔掉了，没有任何变化——而且仍然会在同一个槽上生根，所以我们不应该第二次处理它， 因为我们会回到槽+1。}(hjJhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjFubah}(h]h ]h"]h$]h&]uh1jhj hhhhhNubeh}(h]h ]h"]h$]h&]jjjhjjuh1jhj hhhhhMubh)}(hXK在某些情况下，我们需要同时改变一个节点的父指针和父槽指针（比如说，我们在它之前插入了另一个节点， 并把它往上移了一层）。我们不能在不锁定读取的情况下这样做——所以我们必须同时替换该节点。 然而，当我们把一个快捷键改成一个节点时，这不是一个问题，因为快捷键只有一个槽，所以当向后遍 历一个槽时，不会使用父槽号。这意味着先改变槽位号是可以的——只要使用适当的屏障来确保父槽位号在后 退指针之后被读取。h](h)}(hX在某些情况下，我们需要同时改变一个节点的父指针和父槽指针（比如说，我们在它之前插入了另一个节点， 并把它往上移了一层）。我们不能在不锁定读取的情况下这样做——所以我们必须同时替换该节点。h]hX在某些情况下，我们需要同时改变一个节点的父指针和父槽指针（比如说，我们在它之前插入了另一个节点， 并把它往上移了一层）。我们不能在不锁定读取的情况下这样做——所以我们必须同时替换该节点。}(hjhhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjdubh)}(hX4然而，当我们把一个快捷键改成一个节点时，这不是一个问题，因为快捷键只有一个槽，所以当向后遍 历一个槽时，不会使用父槽号。这意味着先改变槽位号是可以的——只要使用适当的屏障来确保父槽位号在后 退指针之后被读取。h]hX4然而，当我们把一个快捷键改成一个节点时，这不是一个问题，因为快捷键只有一个槽，所以当向后遍 历一个槽时，不会使用父槽号。这意味着先改变槽位号是可以的——只要使用适当的屏障来确保父槽位号在后 退指针之后被读取。}(hjvhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjdubeh}(h]h ]h"]h$]h&]uh1hhj hhhhhNubh)}(h过时的块和叶子在RCU宽限期过后会被释放，所以只要任何进行遍历或迭代的人持有RCU读锁，旧的上层建筑就不 应该在他们身上消失。h]h过时的块和叶子在RCU宽限期过后会被释放，所以只要任何进行遍历或迭代的人持有RCU读锁，旧的上层建筑就不 应该在他们身上消失。}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj hhubeh}(h]id13ah ]h"]同时改变和迭代ah$]h&]uh1jrhju hhhhhMubeh}(h]id8ah ]h"]内部工作机制ah$]h&]uh1jrhjthhhhhM0ubeh}(h](jqid1eh ]h"](通用关联数组的实现cn_core-api_assoc_arrayeh$]h&]uh1jrhhhhhhhKexpect_referenced_by_name}jjfsexpect_referenced_by_id}jqjfsubeh}(h]h ]h"]h$]h&]sourcehuh1hcurrent_sourceN current_lineNsettingsdocutils.frontendValues)}(jwN 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}jq]jfasnameids}(jjqjjjjjr jo j}jzjojlj j j j jj jg jjj j j# j jf jc j j jju nametypes}(jjjjr j}joj j jj jj j# jf j juh}(jqjtjjtjjjo jjzjtjljj jrj j jg j jju j j j j jc j& j ji jj u footnote_refs} citation_refs} autofootnotes]autofootnote_refs]symbol_footnotes]symbol_footnote_refs] footnotes] citations]autofootnote_startKsymbol_footnote_startK id_counter collectionsCounter}jK sRparse_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)}(hj@hhhNhNubah}(h]h ]h"]h$]h&]uh1hhj=ubah}(h]h ]h"]h$]h&]levelKtypeINFOsourceh،lineKuh1j;hjthhhhhK`ubj<)}(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)}(hj\hhhNhNubah}(h]h ]h"]h$]h&]uh1hhjYubah}(h]h ]h"]h$]h&]levelKtypejVsourceh،lineKuh1j;hjhhhhhK~ubj<)}(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)}(hjwhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjtubah}(h]h ]h"]h$]h&]levelKtypejVsourceh،lineKuh1j;hjhhhhhKubj<)}(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&]levelKtypejVsourceh،lineKuh1j;hjhhhhhKubj<)}(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&]levelKtypejVsourceh،lineKuh1j;hjhhhhhKubj<)}(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&]levelKtypejVsourceh،lineKuh1j;hjrhhhhhKubj<)}(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&]levelKtypejVsourceh،lineKuh1j;hjrhhhhhKubj<)}(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&]levelKtypejVsourceh،lineKuh1j;hjrhhhhhKubj<)}(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&]levelKtypejVsourceh،lineKuh1j;hjrhhhhhKubj<)}(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)}(hj4hhhNhNubah}(h]h ]h"]h$]h&]uh1hhj1ubah}(h]h ]h"]h$]h&]levelKtypejVsourceh،lineKuh1j;hjrhhhhhKubj<)}(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)}(hjOhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjLubah}(h]h ]h"]h$]h&]levelKtypejVsourceh،lineKuh1j;hj hhhhhMubetransform_messages]j<)}(hhh]h)}(hhh]h=Hyperlink target "cn-core-api-assoc-array" is not referenced.}hjlsbah}(h]h ]h"]h$]h&]uh1hhjiubah}(h]h ]h"]h$]h&]levelKtypejVsourceh،lineKuh1j;uba transformerN include_log]9Documentation/translations/zh_CN/core-api/assoc_array.rst(NNNNta decorationNhhub.