Lines Matching refs:node
26 * @node refers to an xa_node; usually the primary one being operated on by
29 * @parent refers to the @xa_node closer to the head than @node.
80 static inline unsigned long *node_marks(struct xa_node *node, xa_mark_t mark)
82 return node->marks[(__force unsigned)mark];
85 static inline bool node_get_mark(struct xa_node *node,
88 return test_bit(offset, node_marks(node, mark));
92 static inline bool node_set_mark(struct xa_node *node, unsigned int offset,
95 return __test_and_set_bit(offset, node_marks(node, mark));
99 static inline bool node_clear_mark(struct xa_node *node, unsigned int offset,
102 return __test_and_clear_bit(offset, node_marks(node, mark));
105 static inline bool node_any_mark(struct xa_node *node, xa_mark_t mark)
107 return !bitmap_empty(node_marks(node, mark), XA_CHUNK_SIZE);
110 static inline void node_mark_all(struct xa_node *node, xa_mark_t mark)
112 bitmap_fill(node_marks(node, mark), XA_CHUNK_SIZE);
143 /* extracts the offset within this node from the index */
144 static unsigned int get_offset(unsigned long index, struct xa_node *node)
146 return (index >> node->shift) & XA_CHUNK_MASK;
203 static void *xas_descend(struct xa_state *xas, struct xa_node *node)
205 unsigned int offset = get_offset(xas->xa_index, node);
206 void *entry = xa_entry(xas->xa, node, offset);
208 xas->xa_node = node;
211 entry = xa_entry(xas->xa, node, offset);
212 if (node->shift && xa_is_node(entry))
240 struct xa_node *node = xa_to_node(entry);
242 if (xas->xa_shift > node->shift)
244 entry = xas_descend(xas, node);
245 if (node->shift == 0)
254 static void xa_node_free(struct xa_node *node)
256 XA_NODE_BUG_ON(node, !list_empty(&node->private_list));
257 node->array = XA_RCU_FREE;
258 call_rcu(&node->rcu_head, radix_tree_node_rcu_free);
270 struct xa_node *next, *node = xas->xa_alloc;
272 while (node) {
273 XA_NODE_BUG_ON(node, !list_empty(&node->private_list));
274 next = rcu_dereference_raw(node->parent);
275 radix_tree_node_rcu_free(&node->rcu_head);
276 xas->xa_alloc = node = next;
291 * Forward progress is guaranteed as one node is allocated here and
351 static void xas_update(struct xa_state *xas, struct xa_node *node)
354 xas->xa_update(node);
356 XA_NODE_BUG_ON(node, !list_empty(&node->private_list));
362 struct xa_node *node = xas->xa_alloc;
367 if (node) {
375 node = kmem_cache_alloc_lru(radix_tree_node_cachep, xas->xa_lru, gfp);
376 if (!node) {
383 node->offset = xas->xa_offset;
385 XA_NODE_BUG_ON(node, parent->count > XA_CHUNK_SIZE);
388 XA_NODE_BUG_ON(node, shift > BITS_PER_LONG);
389 XA_NODE_BUG_ON(node, !list_empty(&node->private_list));
390 node->shift = shift;
391 node->count = 0;
392 node->nr_values = 0;
393 RCU_INIT_POINTER(node->parent, xas->xa_node);
394 node->array = xas->xa;
396 return node;
440 struct xa_node *node = xas->xa_node;
445 XA_NODE_BUG_ON(node, node->count > XA_CHUNK_SIZE);
446 if (node->count != 1)
448 entry = xa_entry_locked(xa, node, 0);
451 if (!xa_is_node(entry) && node->shift)
458 if (xa_track_free(xa) && !node_get_mark(node, 0, XA_FREE_MARK))
461 node->count = 0;
462 node->nr_values = 0;
464 RCU_INIT_POINTER(node->slots[0], XA_RETRY_ENTRY);
465 xas_update(xas, node);
466 xa_node_free(node);
469 node = xa_to_node(entry);
470 node->parent = NULL;
478 * Attempts to delete the @xas->xa_node. This will fail if xa->node has
483 struct xa_node *node = xas->xa_node;
488 XA_NODE_BUG_ON(node, node->count > XA_CHUNK_SIZE);
489 if (node->count)
492 parent = xa_parent_locked(xas->xa, node);
494 xas->xa_offset = node->offset;
495 xa_node_free(node);
506 node = parent;
507 xas_update(xas, node);
510 if (!node->parent)
515 * xas_free_nodes() - Free this node and all nodes that it references
519 * This node has been removed from the tree. We must now free it and all
526 struct xa_node *node = top;
529 void *entry = xa_entry_locked(xas->xa, node, offset);
531 if (node->shift && xa_is_node(entry)) {
532 node = xa_to_node(entry);
537 RCU_INIT_POINTER(node->slots[offset], XA_RETRY_ENTRY);
542 parent = xa_parent_locked(xas->xa, node);
543 offset = node->offset + 1;
544 node->count = 0;
545 node->nr_values = 0;
546 xas_update(xas, node);
547 xa_node_free(node);
548 if (node == top)
550 node = parent;
562 struct xa_node *node = NULL;
573 node = xa_to_node(head);
574 shift = node->shift + XA_CHUNK_SHIFT;
581 XA_NODE_BUG_ON(node, shift > BITS_PER_LONG);
582 node = xas_alloc(xas, shift);
583 if (!node)
586 node->count = 1;
588 node->nr_values = 1;
589 RCU_INIT_POINTER(node->slots[0], head);
594 node_mark_all(node, XA_FREE_MARK);
596 node_clear_mark(node, 0, XA_FREE_MARK);
600 node_set_mark(node, 0, mark);
608 * Now that the new node is fully initialised, we can add
613 rcu_assign_pointer(xa_to_node(head)->parent, node);
615 head = xa_mk_node(node);
617 xas_update(xas, node);
622 xas->xa_node = node;
644 struct xa_node *node = xas->xa_node;
648 if (xas_top(node)) {
662 } else if (node) {
665 shift = node->shift;
666 entry = xa_entry_locked(xa, node, offset);
667 slot = &node->slots[offset];
677 node = xas_alloc(xas, shift);
678 if (!node)
681 node_mark_all(node, XA_FREE_MARK);
682 rcu_assign_pointer(*slot, xa_mk_node(node));
684 node = xa_to_node(entry);
688 entry = xas_descend(xas, node);
689 slot = &node->slots[xas->xa_offset];
725 struct xa_node *node = xas->xa_node;
726 if (node->shift >= shift)
728 xas->xa_node = xa_parent_locked(xas->xa, node);
729 xas->xa_offset = node->offset - 1;
730 if (node->offset != 0)
747 static void update_node(struct xa_state *xas, struct xa_node *node,
750 if (!node || (!count && !values))
753 node->count += count;
754 node->nr_values += values;
755 XA_NODE_BUG_ON(node, node->count > XA_CHUNK_SIZE);
756 XA_NODE_BUG_ON(node, node->nr_values > XA_CHUNK_SIZE);
757 xas_update(xas, node);
777 struct xa_node *node;
794 node = xas->xa_node;
795 if (node && (xas->xa_shift < node->shift))
803 if (node) {
804 slot = &node->slots[offset];
820 if (xa_is_node(next) && (!node || node->shift))
822 if (!node)
835 next = xa_entry_locked(xas->xa, node, ++offset);
844 update_node(xas, node, count, values);
878 struct xa_node *node = xas->xa_node;
884 while (node) {
885 if (node_set_mark(node, offset, mark))
887 offset = node->offset;
888 node = xa_parent_locked(xas->xa, node);
907 struct xa_node *node = xas->xa_node;
913 while (node) {
914 if (!node_clear_mark(node, offset, mark))
916 if (node_any_mark(node, mark))
919 offset = node->offset;
920 node = xa_parent_locked(xas->xa, node);
956 static unsigned int node_get_marks(struct xa_node *node, unsigned int offset)
962 if (node_get_mark(node, offset, mark))
972 static void node_set_marks(struct xa_node *node, unsigned int offset,
979 node_set_mark(node, offset, mark);
1018 struct xa_node *node;
1020 node = kmem_cache_alloc_lru(radix_tree_node_cachep, xas->xa_lru, gfp);
1021 if (!node)
1023 node->array = xas->xa;
1026 RCU_INIT_POINTER(node->slots[i], entry);
1029 RCU_INIT_POINTER(node->slots[i], sibling);
1032 RCU_INIT_POINTER(node->parent, xas->xa_alloc);
1033 xas->xa_alloc = node;
1058 struct xa_node *node;
1062 node = xas->xa_node;
1063 if (xas_top(node))
1066 marks = node_get_marks(node, xas->xa_offset);
1070 if (xas->xa_shift < node->shift) {
1074 child->shift = node->shift - XA_CHUNK_SHIFT;
1079 RCU_INIT_POINTER(child->parent, node);
1080 node_set_marks(node, offset, child, marks);
1081 rcu_assign_pointer(node->slots[offset],
1089 node_set_marks(node, canon, NULL, marks);
1090 rcu_assign_pointer(node->slots[canon], entry);
1092 rcu_assign_pointer(node->slots[offset--],
1099 node->nr_values += values;
1100 xas_update(xas, node);
1122 struct xa_node *node = xas->xa_node;
1128 if (node) {
1131 if (!xa_is_sibling(xa_entry(xas->xa, node, offset)))
1134 xas->xa_index += (offset - xas->xa_offset) << node->shift;
1409 struct xa_node *node = xa_to_node(curr);
1410 curr = xas_descend(xas, node);
2040 struct xa_node *node = xas->xa_node;
2043 if (!IS_ENABLED(CONFIG_XARRAY_MULTI) || !node)
2045 mask = (XA_CHUNK_SIZE << node->shift) - 1;
2047 ((unsigned long)xas->xa_offset << node->shift);
2180 * @node: Node to be removed from the tree.
2185 void xa_delete_node(struct xa_node *node, xa_update_node_t update)
2188 .xa = node->array,
2189 .xa_index = (unsigned long)node->offset <<
2190 (node->shift + XA_CHUNK_SHIFT),
2191 .xa_shift = node->shift + XA_CHUNK_SHIFT,
2192 .xa_offset = node->offset,
2193 .xa_node = xa_parent_locked(node->array, node),
2232 void xa_dump_node(const struct xa_node *node)
2236 if (!node)
2238 if ((unsigned long)node & 3) {
2239 pr_cont("node %px\n", node);
2243 pr_cont("node %px %s %d parent %px shift %d count %d values %d "
2245 node, node->parent ? "offset" : "max", node->offset,
2246 node->parent, node->shift, node->count, node->nr_values,
2247 node->array, node->private_list.prev, node->private_list.next);
2250 pr_cont(" %lx", node->marks[i][j]);
2276 struct xa_node *node = xa_to_node(entry);
2277 xa_dump_node(node);
2279 xa_dump_entry(node->slots[i],
2280 index + (i << node->shift), node->shift);