Lines Matching refs:node
109 static inline void tag_set(struct radix_tree_node *node, unsigned int tag, in tag_set() argument
112 __set_bit(offset, node->tags[tag]); in tag_set()
115 static inline void tag_clear(struct radix_tree_node *node, unsigned int tag, in tag_clear() argument
118 __clear_bit(offset, node->tags[tag]); in tag_clear()
121 static inline int tag_get(const struct radix_tree_node *node, unsigned int tag, in tag_get() argument
124 return test_bit(offset, node->tags[tag]); in tag_get()
161 static inline int any_tag_set(const struct radix_tree_node *node, in any_tag_set() argument
166 if (node->tags[tag][idx]) in any_tag_set()
172 static inline void all_tag_set(struct radix_tree_node *node, unsigned int tag) in all_tag_set() argument
174 bitmap_fill(node->tags[tag], RADIX_TREE_MAP_SIZE); in all_tag_set()
189 radix_tree_find_next_bit(struct radix_tree_node *node, unsigned int tag, in radix_tree_find_next_bit() argument
192 const unsigned long *addr = node->tags[tag]; in radix_tree_find_next_bit()
225 static inline unsigned long node_maxindex(const struct radix_tree_node *node) in node_maxindex() argument
227 return shift_maxindex(node->shift); in node_maxindex()
231 const struct radix_tree_node *node, in next_index() argument
234 return (index & ~node_maxindex(node)) + (offset << node->shift); in next_index()
301 struct radix_tree_node *node = in radix_tree_node_rcu_free() local
309 memset(node->slots, 0, sizeof(node->slots)); in radix_tree_node_rcu_free()
310 memset(node->tags, 0, sizeof(node->tags)); in radix_tree_node_rcu_free()
311 INIT_LIST_HEAD(&node->private_list); in radix_tree_node_rcu_free()
313 kmem_cache_free(radix_tree_node_cachep, node); in radix_tree_node_rcu_free()
317 radix_tree_node_free(struct radix_tree_node *node) in radix_tree_node_free() argument
319 call_rcu(&node->rcu_head, radix_tree_node_rcu_free); in radix_tree_node_free()
334 struct radix_tree_node *node; in __radix_tree_preload() local
347 node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask); in __radix_tree_preload()
348 if (node == NULL) in __radix_tree_preload()
353 node->parent = rtp->nodes; in __radix_tree_preload()
354 rtp->nodes = node; in __radix_tree_preload()
357 kmem_cache_free(radix_tree_node_cachep, node); in __radix_tree_preload()
400 struct radix_tree_node *node = rcu_dereference_raw(root->xa_head); in radix_tree_load_root() local
402 *nodep = node; in radix_tree_load_root()
404 if (likely(radix_tree_is_internal_node(node))) { in radix_tree_load_root()
405 node = entry_to_node(node); in radix_tree_load_root()
406 *maxindex = node_maxindex(node); in radix_tree_load_root()
407 return node->shift + RADIX_TREE_MAP_SHIFT; in radix_tree_load_root()
434 struct radix_tree_node *node = radix_tree_node_alloc(gfp, NULL, in radix_tree_extend() local
436 if (!node) in radix_tree_extend()
440 all_tag_set(node, IDR_FREE); in radix_tree_extend()
442 tag_clear(node, IDR_FREE, 0); in radix_tree_extend()
449 tag_set(node, tag, 0); in radix_tree_extend()
455 entry_to_node(entry)->parent = node; in radix_tree_extend()
458 node->nr_values = 1; in radix_tree_extend()
464 node->slots[0] = (void __rcu *)entry; in radix_tree_extend()
465 entry = node_to_entry(node); in radix_tree_extend()
482 struct radix_tree_node *node = rcu_dereference_raw(root->xa_head); in radix_tree_shrink() local
485 if (!radix_tree_is_internal_node(node)) in radix_tree_shrink()
487 node = entry_to_node(node); in radix_tree_shrink()
493 if (node->count != 1) in radix_tree_shrink()
495 child = rcu_dereference_raw(node->slots[0]); in radix_tree_shrink()
504 if (!node->shift && is_idr(root)) in radix_tree_shrink()
518 if (is_idr(root) && !tag_get(node, IDR_FREE, 0)) in radix_tree_shrink()
539 node->count = 0; in radix_tree_shrink()
541 node->slots[0] = (void __rcu *)RADIX_TREE_RETRY; in radix_tree_shrink()
544 WARN_ON_ONCE(!list_empty(&node->private_list)); in radix_tree_shrink()
545 radix_tree_node_free(node); in radix_tree_shrink()
553 struct radix_tree_node *node) in delete_node() argument
560 if (node->count) { in delete_node()
561 if (node_to_entry(node) == in delete_node()
567 parent = node->parent; in delete_node()
569 parent->slots[node->offset] = NULL; in delete_node()
581 WARN_ON_ONCE(!list_empty(&node->private_list)); in delete_node()
582 radix_tree_node_free(node); in delete_node()
585 node = parent; in delete_node()
586 } while (node); in delete_node()
611 struct radix_tree_node *node = NULL, *child; in __radix_tree_create() local
633 child = radix_tree_node_alloc(gfp, node, root, shift, in __radix_tree_create()
638 if (node) in __radix_tree_create()
639 node->count++; in __radix_tree_create()
644 node = entry_to_node(child); in __radix_tree_create()
645 offset = radix_tree_descend(node, &child, index); in __radix_tree_create()
646 slot = &node->slots[offset]; in __radix_tree_create()
650 *nodep = node; in __radix_tree_create()
665 static void radix_tree_free_nodes(struct radix_tree_node *node) in radix_tree_free_nodes() argument
668 struct radix_tree_node *child = entry_to_node(node); in radix_tree_free_nodes()
684 if (old == entry_to_node(node)) in radix_tree_free_nodes()
690 static inline int insert_entries(struct radix_tree_node *node, in insert_entries() argument
696 if (node) { in insert_entries()
697 node->count++; in insert_entries()
699 node->nr_values++; in insert_entries()
715 struct radix_tree_node *node; in radix_tree_insert() local
721 error = __radix_tree_create(root, index, &node, &slot); in radix_tree_insert()
725 error = insert_entries(node, slot, item, false); in radix_tree_insert()
729 if (node) { in radix_tree_insert()
730 unsigned offset = get_slot_offset(node, slot); in radix_tree_insert()
731 BUG_ON(tag_get(node, 0, offset)); in radix_tree_insert()
732 BUG_ON(tag_get(node, 1, offset)); in radix_tree_insert()
733 BUG_ON(tag_get(node, 2, offset)); in radix_tree_insert()
760 struct radix_tree_node *node, *parent; in __radix_tree_lookup() local
767 radix_tree_load_root(root, &node, &maxindex); in __radix_tree_lookup()
771 while (radix_tree_is_internal_node(node)) { in __radix_tree_lookup()
774 parent = entry_to_node(node); in __radix_tree_lookup()
775 offset = radix_tree_descend(parent, &node, index); in __radix_tree_lookup()
777 if (node == RADIX_TREE_RETRY) in __radix_tree_lookup()
787 return node; in __radix_tree_lookup()
833 struct radix_tree_node *node, int count, int values) in replace_slot() argument
835 if (node && (count || values)) { in replace_slot()
836 node->count += count; in replace_slot()
837 node->nr_values += values; in replace_slot()
844 const struct radix_tree_node *node, in node_tag_get() argument
847 if (node) in node_tag_get()
848 return tag_get(node, tag, offset); in node_tag_get()
860 struct radix_tree_node *node, void __rcu **slot, in calculate_count() argument
864 unsigned offset = get_slot_offset(node, slot); in calculate_count()
865 bool free = node_tag_get(root, node, IDR_FREE, offset); in calculate_count()
885 struct radix_tree_node *node, in __radix_tree_replace() argument
890 int count = calculate_count(root, node, slot, item, old); in __radix_tree_replace()
897 WARN_ON_ONCE(!node && (slot != (void __rcu **)&root->xa_head) && in __radix_tree_replace()
899 replace_slot(slot, item, node, count, values); in __radix_tree_replace()
901 if (!node) in __radix_tree_replace()
904 delete_node(root, node); in __radix_tree_replace()
943 __radix_tree_replace(root, iter->node, slot, item); in radix_tree_iter_replace()
947 struct radix_tree_node *node, in node_tag_set() argument
950 while (node) { in node_tag_set()
951 if (tag_get(node, tag, offset)) in node_tag_set()
953 tag_set(node, tag, offset); in node_tag_set()
954 offset = node->offset; in node_tag_set()
955 node = node->parent; in node_tag_set()
978 struct radix_tree_node *node, *parent; in radix_tree_tag_set() local
981 radix_tree_load_root(root, &node, &maxindex); in radix_tree_tag_set()
984 while (radix_tree_is_internal_node(node)) { in radix_tree_tag_set()
987 parent = entry_to_node(node); in radix_tree_tag_set()
988 offset = radix_tree_descend(parent, &node, index); in radix_tree_tag_set()
989 BUG_ON(!node); in radix_tree_tag_set()
999 return node; in radix_tree_tag_set()
1004 struct radix_tree_node *node, in node_tag_clear() argument
1007 while (node) { in node_tag_clear()
1008 if (!tag_get(node, tag, offset)) in node_tag_clear()
1010 tag_clear(node, tag, offset); in node_tag_clear()
1011 if (any_tag_set(node, tag)) in node_tag_clear()
1014 offset = node->offset; in node_tag_clear()
1015 node = node->parent; in node_tag_clear()
1040 struct radix_tree_node *node, *parent; in radix_tree_tag_clear() local
1044 radix_tree_load_root(root, &node, &maxindex); in radix_tree_tag_clear()
1050 while (radix_tree_is_internal_node(node)) { in radix_tree_tag_clear()
1051 parent = entry_to_node(node); in radix_tree_tag_clear()
1052 offset = radix_tree_descend(parent, &node, index); in radix_tree_tag_clear()
1055 if (node) in radix_tree_tag_clear()
1058 return node; in radix_tree_tag_clear()
1071 node_tag_clear(root, iter->node, tag, iter_offset(iter)); in radix_tree_iter_tag_clear()
1092 struct radix_tree_node *node, *parent; in radix_tree_tag_get() local
1098 radix_tree_load_root(root, &node, &maxindex); in radix_tree_tag_get()
1102 while (radix_tree_is_internal_node(node)) { in radix_tree_tag_get()
1105 parent = entry_to_node(node); in radix_tree_tag_get()
1106 offset = radix_tree_descend(parent, &node, index); in radix_tree_tag_get()
1110 if (node == RADIX_TREE_RETRY) in radix_tree_tag_get()
1120 struct radix_tree_node *node, unsigned offset, in set_iter_tags() argument
1126 if (!node) { in set_iter_tags()
1131 iter->tags = node->tags[tag][tag_long] >> tag_bit; in set_iter_tags()
1137 iter->tags |= node->tags[tag][tag_long + 1] << in set_iter_tags()
1167 struct radix_tree_node *node, *child; in radix_tree_next_chunk() local
1198 iter->node = NULL; in radix_tree_next_chunk()
1203 node = entry_to_node(child); in radix_tree_next_chunk()
1204 offset = radix_tree_descend(node, &child, index); in radix_tree_next_chunk()
1207 !tag_get(node, tag, offset) : !child) { in radix_tree_next_chunk()
1213 offset = radix_tree_find_next_bit(node, tag, in radix_tree_next_chunk()
1218 node->slots[offset]); in radix_tree_next_chunk()
1222 index &= ~node_maxindex(node); in radix_tree_next_chunk()
1223 index += offset << node->shift; in radix_tree_next_chunk()
1229 child = rcu_dereference_raw(node->slots[offset]); in radix_tree_next_chunk()
1236 } while (node->shift && radix_tree_is_internal_node(child)); in radix_tree_next_chunk()
1239 iter->index = (index &~ node_maxindex(node)) | offset; in radix_tree_next_chunk()
1240 iter->next_index = (index | node_maxindex(node)) + 1; in radix_tree_next_chunk()
1241 iter->node = node; in radix_tree_next_chunk()
1244 set_iter_tags(iter, node, offset, tag); in radix_tree_next_chunk()
1246 return node->slots + offset; in radix_tree_next_chunk()
1374 struct radix_tree_node *node, void __rcu **slot) in __radix_tree_delete() argument
1378 unsigned offset = get_slot_offset(node, slot); in __radix_tree_delete()
1382 node_tag_set(root, node, IDR_FREE, offset); in __radix_tree_delete()
1385 node_tag_clear(root, node, tag, offset); in __radix_tree_delete()
1387 replace_slot(slot, NULL, node, -1, values); in __radix_tree_delete()
1388 return node && delete_node(root, node); in __radix_tree_delete()
1406 if (__radix_tree_delete(root, iter->node, slot)) in radix_tree_iter_delete()
1425 struct radix_tree_node *node = NULL; in radix_tree_delete_item() local
1429 entry = __radix_tree_lookup(root, index, &node, &slot); in radix_tree_delete_item()
1432 if (!entry && (!is_idr(root) || node_tag_get(root, node, IDR_FREE, in radix_tree_delete_item()
1433 get_slot_offset(node, slot)))) in radix_tree_delete_item()
1439 __radix_tree_delete(root, node, slot); in radix_tree_delete_item()
1489 struct radix_tree_node *node = NULL, *child; in idr_get_free() local
1515 child = radix_tree_node_alloc(gfp, node, root, shift, in idr_get_free()
1521 if (node) in idr_get_free()
1522 node->count++; in idr_get_free()
1526 node = entry_to_node(child); in idr_get_free()
1527 offset = radix_tree_descend(node, &child, start); in idr_get_free()
1528 if (!tag_get(node, IDR_FREE, offset)) { in idr_get_free()
1529 offset = radix_tree_find_next_bit(node, IDR_FREE, in idr_get_free()
1531 start = next_index(start, node, offset); in idr_get_free()
1535 offset = node->offset + 1; in idr_get_free()
1536 node = node->parent; in idr_get_free()
1537 if (!node) in idr_get_free()
1539 shift = node->shift; in idr_get_free()
1541 child = rcu_dereference_raw(node->slots[offset]); in idr_get_free()
1543 slot = &node->slots[offset]; in idr_get_free()
1547 if (node) in idr_get_free()
1548 iter->next_index = 1 + min(max, (start | node_maxindex(node))); in idr_get_free()
1551 iter->node = node; in idr_get_free()
1552 set_iter_tags(iter, node, offset, IDR_FREE); in idr_get_free()
1570 struct radix_tree_node *node = rcu_dereference_raw(idr->idr_rt.xa_head); in idr_destroy() local
1571 if (radix_tree_is_internal_node(node)) in idr_destroy()
1572 radix_tree_free_nodes(node); in idr_destroy()
1581 struct radix_tree_node *node = arg; in radix_tree_node_ctor() local
1583 memset(node, 0, sizeof(*node)); in radix_tree_node_ctor()
1584 INIT_LIST_HEAD(&node->private_list); in radix_tree_node_ctor()
1590 struct radix_tree_node *node; in radix_tree_cpu_dead() local
1595 node = rtp->nodes; in radix_tree_cpu_dead()
1596 rtp->nodes = node->parent; in radix_tree_cpu_dead()
1597 kmem_cache_free(radix_tree_node_cachep, node); in radix_tree_cpu_dead()