Boost Unordered Translation (zh_Hans)/Doc / Modules / Root / Pages / Structures (adoc)

Exit Zen

25 :106

	English - If the bit in the position _h_ mod 8 is zero, lookup terminates (and the element is not present). - If the bit is set to 1 (the group has been _overflowed_), further groups are checked using https://en.wikipedia.org/wiki/Quadratic_probing[_quadratic probing_], and the process is repeated. 291/10000 · 291
26 :112

	English Insertion is algorithmically similar: empty buckets are located using SIMD, and when going past a full group its corresponding overflow bit is set to 1. 152/10000 · 152
27 :115

	English In architectures without SIMD support, the logical layout stays the same, but the metadata word is codified using a technique we call _bit interleaving_: this layout allows us to emulate SIMD with reasonably good performance using only standard arithmetic and logical operations. 279/10000 · 279
28 :122

	English image::foa-metadata-interleaving.png[align=center] 50/10000 · 50
29 :124

	English A more detailed description of Boost.Unordered's open-addressing implementation is given in an https://bannalia.blogspot.com/2022/11/inside-boostunorderedflatmap.html[external article]. For more information on implementation rationale, read the xref:rationale.adoc#rationale_open_addresing_containers[corresponding section]. 324/10000 · 324
30 :130

	English Concurrent Containers 21/10000 · 21
31 :132

	English `boost::concurrent_flat_set`/`boost::concurrent_node_set` and `boost::concurrent_flat_map`/`boost::concurrent_node_map` use the basic xref:structures.adoc#structures_open_addressing_containers[open-addressing layout] described above augmented with synchronization mechanisms. 275/10000 · 275
32 :140

	English image::cfoa.png[align=center] 29/10000 · 29
33 :142

	English Two levels of synchronization are used: 39/10000 · 39
34 :144

	English Container level: A read-write mutex is used to control access from any operation 80/10000 · 80
35 :145

	English to the container. Typically, such access is in read mode (that is, concurrent) even for modifying operations, so for most practical purposes there is no thread contention at this level. Access is only in write mode (blocking) when rehashing or performing container-wide operations such as swapping or assignment. 312/10000 · 312
36 :149

	English Group level: Each 15-slot group is equipped with an 8-byte word containing: 75/10000 · 75
37 :150

	English A read-write spinlock for synchronized access to any element in the group. An atomic _insertion counter_ used for optimistic insertion as described below. 160/10000 · 160
38 :154

	English By using atomic operations to access the group metadata, lookup is (group-level) lock-free up to the point where an actual comparison needs to be done with an element that has been previously SIMD-matched: only then is the group's spinlock used. 245/10000 · 245
39 :158

	English Insertion uses the following _optimistic algorithm_: 52/10000 · 52
40 :160

	English The value of the insertion counter for the initial group in the probe 69/10000 · 69
41 :161

	English sequence is locally recorded (let's call this value `c0`). 58/10000 · 58
42 :162

	English Lookup is as described above. If lookup finds no equivalent element, 68/10000 · 68
43 :163

	English search for an available slot for insertion successively locks/unlocks each group in the probing sequence. 105/10000 · 105
44 :165

	English When an available slot is located, it is preemptively occupied (its 67/10000 · 67

Shortcut	Action
`?`	Open available keyboard shortcuts.
`Alt` + `Home`	Navigate to the first translation in the current search.
`Alt` + `End`	Navigate to the last translation in the current search.
`Alt` + `PageUp` or `Ctrl` + `↑` or `Alt` + `↑` or `Cmd` + `↑` or	Navigate to the previous translation in the current search.
`Alt` + `PageDown` or `Ctrl` + `↓` or `Alt` + `↓` or `Cmd` + `↓` or	Navigate to the next translation in the current search.
`Ctrl` + `Enter` or `Cmd` + `Enter`	Submit current form; this works the same as pressing Save and continue while editing translation.
`Ctrl` + `Shift` + `Enter` or `Cmd` + `Shift` +`Enter`	Unmark translation as Needing edit and submit it.
`Alt` + `Enter` or `Option` + `Enter`	Submit the string as a suggestion; this works the same as pressing Suggest while editing translation.
`Ctrl` + `E` or `Cmd` + `E`	Focus on translation editor.
`Ctrl` + `U` or `Cmd` + `U`	Focus on comment editor.
`Ctrl` + `M` or `Cmd` + `M`	Shows Automatic suggestions tab.
`Ctrl` + `1` to `Ctrl` + `9` or `Cmd` + `1` to `Cmd` + `9`	Copies placeable of a given number from source string.
`Ctrl` + `M` followed by `1` to `9` or `Cmd` + `M` followed by `1` to `9`	Copy the machine translation of a given number to current translation.
`Ctrl` + `I` followed by `1` to `9` or `Cmd` + `I` followed by `1` to `9`	Ignore one item in the list of failing checks.
`Ctrl` + `J` or `Cmd` + `J`	Shows the Nearby strings tab.
`Ctrl` + `S` or `Cmd` + `S`	Focus on search field.
`Ctrl` + `O` or `Cmd` + `O`	Copy the source string.
`Ctrl` + `Y` or `Cmd` + `Y`	Toggle the Needs editing checkbox.
`→`	Browse the next translation string.
`←`	Browse the previous translation string.