Function report

Linux Kernel

v5.5.9

Brick Technologies Co., Ltd

Source Code:lib\assoc_array.c Create Date:2022-07-28 06:54:13
Last Modify:2020-03-12 14:18:49 Copyright©Brick
home page Tree
Annotation kernel can get tool activityDownload SCCTChinese

Name:Navigate through the internal tree looking for the closest node to the key.

Proto:static enum assoc_array_walk_status assoc_array_walk(const struct assoc_array *array, const struct assoc_array_ops *ops, const void *index_key, struct assoc_array_walk_result *result)

Type:enum assoc_array_walk_status

Parameter:

TypeParameterName
const struct assoc_array *array
const struct assoc_array_ops *ops
const void *index_key
struct assoc_array_walk_result *result
183  pr_devel("-->%s()\n", __func__)
185  cursor = READ_ONCE(The node at the root of the tree )
186  If Not cursor Then Return assoc_array_walk_tree_empty
189  level = 0
198  jumped :
199  segments = get_key_chunk(index_key, level)
200  pr_devel("segments[%d]: %lx\n", level, segments)
202  If assoc_array_ptr_is_shortcut(cursor) Then Go to follow_shortcut
205  consider_node :
206  node = assoc_array_ptr_to_node(cursor)
207  slot = segments >> (level & ASSOC_ARRAY_KEY_CHUNK_MASK)
208  slot &= ASSOC_ARRAY_FAN_MASK
209  ptr = READ_ONCE(slots[slot])
211  pr_devel("consider slot %x [ix=%d type=%lu]\n", slot, level, (unsignedlong)ptr & 3)
214  If Not assoc_array_ptr_is_meta(ptr) Then
218  Node in which leaf might be found = node
219  level = level
220  slot = slot
221  pr_devel("<--%s() = terminal_node\n", __func__)
222  Return assoc_array_walk_found_terminal_node
225  If assoc_array_ptr_is_node(ptr) Then
229  cursor = ptr
230  level += ASSOC_ARRAY_LEVEL_STEP
231  If (level & ASSOC_ARRAY_KEY_CHUNK_MASK) != 0 Then Go to consider_node
233  Go to jumped
240  cursor = ptr
241  follow_shortcut :
242  shortcut = assoc_array_ptr_to_shortcut(cursor)
243  pr_devel("shortcut to %d\n", skip_to_level)
244  sc_level = level + ASSOC_ARRAY_LEVEL_STEP
245  BUG_ON(sc_level > skip_to_level)
247  Do
252  If (sc_level & ASSOC_ARRAY_KEY_CHUNK_MASK) == 0 Then segments = get_key_chunk(index_key, sc_level)
255  sc_segments = index_key[sc_level >> ASSOC_ARRAY_KEY_CHUNK_SHIFT]
256  dissimilarity = segments ^ sc_segments
258  If und_up - round up to next specified power of 2*@x: the value to round*@y: multiple to round up to (must be a power of 2)* Rounds @x up to next multiple of @y (which must be a power of 2).* To perform arbitrary rounding up, use roundup() below.(sc_level, Key data retrieved in chunks of this size ) > skip_to_level Then
260  shift = skip_to_level & ASSOC_ARRAY_KEY_CHUNK_MASK
261  dissimilarity &= ~(ULONG_MAX << shift)
262  next_sc_level = skip_to_level
263  Else
264  next_sc_level = sc_level + Key data retrieved in chunks of this size
265  next_sc_level = und_down - round down to next specified power of 2*@x: the value to round*@y: multiple to round down to (must be a power of 2)* Rounds @x down to next multiple of @y (which must be a power of 2).* To perform arbitrary rounding down, use rounddown() below.(next_sc_level, Key data retrieved in chunks of this size )
268  If dissimilarity != 0 Then
270  shortcut = shortcut
271  level = level
272  sc_level = sc_level
273  sc_segments = sc_segments
274  dissimilarity = dissimilarity
275  Return assoc_array_walk_found_wrong_shortcut
278  sc_level = next_sc_level
279  When sc_level < skip_to_level cycle
282  cursor = READ_ONCE(next_node)
283  If ((level ^ sc_level) & ~ASSOC_ARRAY_KEY_CHUNK_MASK) != 0 Then
284  level = sc_level
285  Go to jumped
286  Else
287  level = sc_level
288  Go to consider_node
Caller
NameDescribe
assoc_array_findassoc_array_find - Find an object by index key*@array: The associative array to search
assoc_array_insertassoc_array_insert - Script insertion of an object into an associative array*@array: The array to insert into
assoc_array_deleteassoc_array_delete - Script deletion of an object from an associative array*@array: The array to search.*@ops: The operations to use.*@index_key: The key to the object.* Precalculate and preallocate a script for the deletion of an object from an