lib/assoc_array.c

Source file repositories/reference/linux-study-clean/lib/assoc_array.c

File Facts

System
Linux kernel
Corpus path
lib/assoc_array.c
Extension
.c
Size
52883 bytes
Lines
1724
Domain
Kernel Services
Bucket
lib
Inferred role
Kernel Services: implementation source
Status
source implementation candidate

Why This File Exists

Shared kernel service surface used by multiple subsystems, including helpers, cryptography, virtualization support, and async I/O infrastructure.

Dependency Surface

Detected Declarations

Annotated Snippet

struct assoc_array_walk_result {
	struct {
		struct assoc_array_node	*node;	/* Node in which leaf might be found */
		int		level;
		int		slot;
	} terminal_node;
	struct {
		struct assoc_array_shortcut *shortcut;
		int		level;
		int		sc_level;
		unsigned long	sc_segments;
		unsigned long	dissimilarity;
	} wrong_shortcut;
};

/*
 * Navigate through the internal tree looking for the closest node to the key.
 */
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)
{
	struct assoc_array_shortcut *shortcut;
	struct assoc_array_node *node;
	struct assoc_array_ptr *cursor, *ptr;
	unsigned long sc_segments, dissimilarity;
	unsigned long segments;
	int level, sc_level, next_sc_level;
	int slot;

	pr_devel("-->%s()\n", __func__);

	cursor = READ_ONCE(array->root);  /* Address dependency. */
	if (!cursor)
		return assoc_array_walk_tree_empty;

	level = 0;

	/* Use segments from the key for the new leaf to navigate through the
	 * internal tree, skipping through nodes and shortcuts that are on
	 * route to the destination.  Eventually we'll come to a slot that is
	 * either empty or contains a leaf at which point we've found a node in
	 * which the leaf we're looking for might be found or into which it
	 * should be inserted.
	 */
jumped:
	segments = ops->get_key_chunk(index_key, level);
	pr_devel("segments[%d]: %lx\n", level, segments);

	if (assoc_array_ptr_is_shortcut(cursor))
		goto follow_shortcut;

consider_node:
	node = assoc_array_ptr_to_node(cursor);
	slot = segments >> (level & ASSOC_ARRAY_KEY_CHUNK_MASK);
	slot &= ASSOC_ARRAY_FAN_MASK;
	ptr = READ_ONCE(node->slots[slot]); /* Address dependency. */

	pr_devel("consider slot %x [ix=%d type=%lu]\n",
		 slot, level, (unsigned long)ptr & 3);

	if (!assoc_array_ptr_is_meta(ptr)) {
		/* The node doesn't have a node/shortcut pointer in the slot
		 * corresponding to the index key that we have to follow.
		 */
		result->terminal_node.node = node;
		result->terminal_node.level = level;
		result->terminal_node.slot = slot;
		pr_devel("<--%s() = terminal_node\n", __func__);
		return assoc_array_walk_found_terminal_node;
	}

	if (assoc_array_ptr_is_node(ptr)) {
		/* There is a pointer to a node in the slot corresponding to
		 * this index key segment, so we need to follow it.
		 */
		cursor = ptr;
		level += ASSOC_ARRAY_LEVEL_STEP;
		if ((level & ASSOC_ARRAY_KEY_CHUNK_MASK) != 0)
			goto consider_node;
		goto jumped;
	}

	/* There is a shortcut in the slot corresponding to the index key
	 * segment.  We follow the shortcut if its partial index key matches
	 * this leaf's.  Otherwise we need to split the shortcut.
	 */
	cursor = ptr;

Annotation

Implementation Notes