1 // SPDX-License-Identifier: GPL-2.0
21  * toptree_alloc - Allocate and initialize a new tree node.
22  * @level: The node's vertical level; level 0 contains the leaves.
23  * @id: ID number, explicitly not unique beyond scope of node's siblings
25  * Allocate a new tree node and initialize it.
28  * Pointer to the new tree node or NULL on error
41 	INIT_LIST_HEAD(&res->children);  in toptree_alloc()
42 	INIT_LIST_HEAD(&res->sibling);  in toptree_alloc()
43 	cpumask_clear(&res->mask);  in toptree_alloc()
44 	res->level = level;  in toptree_alloc()
45 	res->id = id;  in toptree_alloc()
50  * toptree_remove - Remove a tree node from a tree
51  * @cand: Pointer to the node to remove
53  * The node is detached from its parent node. The parent node's
54  * masks will be updated to reflect the loss of the child.
60 	list_del_init(&cand->sibling);  in toptree_remove()
61 	oldparent = cand->parent;  in toptree_remove()
62 	cand->parent = NULL;  in toptree_remove()
67  * toptree_free - discard a tree node
68  * @cand: Pointer to the tree node to discard
70  * Checks if @cand is attached to a parent node. Detaches it
76 	struct toptree *child, *tmp;  in toptree_free()  local
78 	if (cand->parent)  in toptree_free()
80 	toptree_for_each_child_safe(child, tmp, cand)  in toptree_free()
81 		toptree_free(child);  in toptree_free()
89  * toptree_update_mask - Update node bitmasks
90  * @cand: Pointer to a tree node
92  * The node's cpumask will be updated by combining all children's
102 	struct toptree *child;  in toptree_update_mask()  local
104 	cpumask_clear(&cand->mask);  in toptree_update_mask()
105 	list_for_each_entry(child, &cand->children, sibling)  in toptree_update_mask()
106 		cpumask_or(&cand->mask, &cand->mask, &child->mask);  in toptree_update_mask()
107 	if (cand->parent)  in toptree_update_mask()
108 		toptree_update_mask(cand->parent);  in toptree_update_mask()
112  * toptree_insert - Insert a tree node into tree
113  * @cand: Pointer to the node to insert
114  * @target: Pointer to the node to which @cand will added as a child
116  * Insert a tree node into a tree. Masks will be updated automatically.
119  * 0 on success, -1 if NULL is passed as argument or the node levels
125 		return -1;  in toptree_insert()
126 	if (target->level != (cand->level + 1))  in toptree_insert()
127 		return -1;  in toptree_insert()
128 	list_add_tail(&cand->sibling, &target->children);  in toptree_insert()
129 	cand->parent = target;  in toptree_insert()
135  * toptree_move_children - Move all child nodes of a node to a new place
136  * @cand: Pointer to the node whose children are to be moved
137  * @target: Pointer to the node to which @cand's children will be attached
139  * Take all child nodes of @cand and move them using toptree_move.
143 	struct toptree *child, *tmp;  in toptree_move_children()  local
145 	toptree_for_each_child_safe(child, tmp, cand)  in toptree_move_children()
146 		toptree_move(child, target);  in toptree_move_children()
150  * toptree_unify - Merge children with same ID
151  * @cand: Pointer to node whose direct children should be made unique
153  * When mangling the tree it is possible that a node has two or more children
155  * moves all children of the merged nodes into the unified node.
159 	struct toptree *child, *tmp, *cand_copy;  in toptree_unify()  local
162 	if (cand->level < 2)  in toptree_unify()
165 	cand_copy = toptree_alloc(cand->level, 0);  in toptree_unify()
166 	toptree_for_each_child_safe(child, tmp, cand) {  in toptree_unify()
169 		if (!cpumask_empty(&child->mask)) {  in toptree_unify()
170 			tmpchild = toptree_get_child(cand_copy, child->id);  in toptree_unify()
171 			toptree_move_children(child, tmpchild);  in toptree_unify()
173 		toptree_free(child);  in toptree_unify()
178 	toptree_for_each_child(child, cand)  in toptree_unify()
179 		toptree_unify(child);  in toptree_unify()
183  * toptree_move - Move a node to another context
184  * @cand: Pointer to the node to move
185  * @target: Pointer to the node where @cand should go
202 	if (cand->level + 1 == target->level) {  in toptree_move()
214 		stack_target = toptree_alloc(ptr->level + 1,  in toptree_move()
215 					     ptr->parent->id);  in toptree_move()
219 		ptr = ptr->parent;  in toptree_move()
220 	} while (stack_target->level < (target->level - 1));  in toptree_move()
228  * toptree_get_child - Access a tree node's child by its ID
229  * @cand: Pointer to tree node whose child is to access
230  * @id: The desired child's ID
232  * @cand's children are searched for a child with matching ID.
233  * If no match can be found, a new child with the desired ID
238 	struct toptree *child;  in toptree_get_child()  local
240 	toptree_for_each_child(child, cand)  in toptree_get_child()
241 		if (child->id == id)  in toptree_get_child()
242 			return child;  in toptree_get_child()
243 	child = toptree_alloc(cand->level-1, id);  in toptree_get_child()
244 	toptree_insert(child, cand);  in toptree_get_child()
245 	return child;  in toptree_get_child()
249  * toptree_first - Find the first descendant on specified level
250  * @context: Pointer to tree node whose descendants are to be used
259 	struct toptree *child, *tmp;  in toptree_first()  local
261 	if (context->level == level)  in toptree_first()
264 	if (!list_empty(&context->children)) {  in toptree_first()
265 		list_for_each_entry(child, &context->children, sibling) {  in toptree_first()
266 			tmp = toptree_first(child, level);  in toptree_first()
275  * toptree_next_sibling - Return next sibling
276  * @cur: Pointer to a tree node
284 	if (cur->parent == NULL)  in toptree_next_sibling()
287 	if (cur == list_last_entry(&cur->parent->children,  in toptree_next_sibling()
294  * toptree_next - Tree traversal function
296  * @context: Pointer to the root node of the tree or subtree to
301  * Pointer to the next node on level @level
302  * or NULL when there is no next node.
312 	if (context->level == level)  in toptree_next()
320 	while (cur_context->level < context->level - 1) {  in toptree_next()
322 		cur_context = cur_context->parent;  in toptree_next()
336  * toptree_count - Count descendants on specified level
337  * @context: Pointer to node whose descendants are to be considered