Lines Matching refs:root
107 static inline gfp_t root_gfp_mask(struct radix_tree_root *root) in root_gfp_mask() argument
109 return root->gfp_mask & __GFP_BITS_MASK; in root_gfp_mask()
130 static inline void root_tag_set(struct radix_tree_root *root, unsigned int tag) in root_tag_set() argument
132 root->gfp_mask |= (__force gfp_t)(1 << (tag + __GFP_BITS_SHIFT)); in root_tag_set()
135 static inline void root_tag_clear(struct radix_tree_root *root, unsigned int tag) in root_tag_clear() argument
137 root->gfp_mask &= (__force gfp_t)~(1 << (tag + __GFP_BITS_SHIFT)); in root_tag_clear()
140 static inline void root_tag_clear_all(struct radix_tree_root *root) in root_tag_clear_all() argument
142 root->gfp_mask &= __GFP_BITS_MASK; in root_tag_clear_all()
145 static inline int root_tag_get(struct radix_tree_root *root, unsigned int tag) in root_tag_get() argument
147 return (__force unsigned)root->gfp_mask & (1 << (tag + __GFP_BITS_SHIFT)); in root_tag_get()
205 radix_tree_node_alloc(struct radix_tree_root *root) in radix_tree_node_alloc() argument
208 gfp_t gfp_mask = root_gfp_mask(root); in radix_tree_node_alloc()
305 static int radix_tree_extend(struct radix_tree_root *root, unsigned long index) in radix_tree_extend() argument
313 height = root->height + 1; in radix_tree_extend()
317 if (root->rnode == NULL) { in radix_tree_extend()
318 root->height = height; in radix_tree_extend()
324 if (!(node = radix_tree_node_alloc(root))) in radix_tree_extend()
329 if (root_tag_get(root, tag)) in radix_tree_extend()
334 newheight = root->height+1; in radix_tree_extend()
338 slot = root->rnode; in radix_tree_extend()
345 rcu_assign_pointer(root->rnode, node); in radix_tree_extend()
346 root->height = newheight; in radix_tree_extend()
347 } while (height > root->height); in radix_tree_extend()
360 int radix_tree_insert(struct radix_tree_root *root, in radix_tree_insert() argument
371 if (index > radix_tree_maxindex(root->height)) { in radix_tree_insert()
372 error = radix_tree_extend(root, index); in radix_tree_insert()
377 slot = indirect_to_ptr(root->rnode); in radix_tree_insert()
379 height = root->height; in radix_tree_insert()
386 if (!(slot = radix_tree_node_alloc(root))) in radix_tree_insert()
394 rcu_assign_pointer(root->rnode, ptr_to_indirect(slot)); in radix_tree_insert()
414 rcu_assign_pointer(root->rnode, item); in radix_tree_insert()
415 BUG_ON(root_tag_get(root, 0)); in radix_tree_insert()
416 BUG_ON(root_tag_get(root, 1)); in radix_tree_insert()
427 static void *radix_tree_lookup_element(struct radix_tree_root *root, in radix_tree_lookup_element() argument
433 node = rcu_dereference_raw(root->rnode); in radix_tree_lookup_element()
440 return is_slot ? (void *)&root->rnode : node; in radix_tree_lookup_element()
477 void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index) in radix_tree_lookup_slot() argument
479 return (void **)radix_tree_lookup_element(root, index, 1); in radix_tree_lookup_slot()
495 void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index) in radix_tree_lookup() argument
497 return radix_tree_lookup_element(root, index, 0); in radix_tree_lookup()
514 void *radix_tree_tag_set(struct radix_tree_root *root, in radix_tree_tag_set() argument
520 height = root->height; in radix_tree_tag_set()
523 slot = indirect_to_ptr(root->rnode); in radix_tree_tag_set()
539 if (slot && !root_tag_get(root, tag)) in radix_tree_tag_set()
540 root_tag_set(root, tag); in radix_tree_tag_set()
560 void *radix_tree_tag_clear(struct radix_tree_root *root, in radix_tree_tag_clear() argument
568 height = root->height; in radix_tree_tag_clear()
573 slot = indirect_to_ptr(root->rnode); in radix_tree_tag_clear()
601 if (root_tag_get(root, tag)) in radix_tree_tag_clear()
602 root_tag_clear(root, tag); in radix_tree_tag_clear()
624 int radix_tree_tag_get(struct radix_tree_root *root, in radix_tree_tag_get() argument
631 if (!root_tag_get(root, tag)) in radix_tree_tag_get()
634 node = rcu_dereference_raw(root->rnode); in radix_tree_tag_get()
674 void **radix_tree_next_chunk(struct radix_tree_root *root, in radix_tree_next_chunk() argument
681 if ((flags & RADIX_TREE_ITER_TAGGED) && !root_tag_get(root, tag)) in radix_tree_next_chunk()
697 rnode = rcu_dereference_raw(root->rnode); in radix_tree_next_chunk()
705 return (void **)&root->rnode; in radix_tree_next_chunk()
809 unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root, in radix_tree_range_tag_if_tagged() argument
814 unsigned int height = root->height; in radix_tree_range_tag_if_tagged()
826 if (!root_tag_get(root, iftag)) { in radix_tree_range_tag_if_tagged()
832 root_tag_set(root, settag); in radix_tree_range_tag_if_tagged()
837 slot = indirect_to_ptr(root->rnode); in radix_tree_range_tag_if_tagged()
905 root_tag_set(root, settag); in radix_tree_range_tag_if_tagged()
933 unsigned long radix_tree_next_hole(struct radix_tree_root *root, in radix_tree_next_hole() argument
939 if (!radix_tree_lookup(root, index)) in radix_tree_next_hole()
970 unsigned long radix_tree_prev_hole(struct radix_tree_root *root, in radix_tree_prev_hole() argument
976 if (!radix_tree_lookup(root, index)) in radix_tree_prev_hole()
1007 radix_tree_gang_lookup(struct radix_tree_root *root, void **results, in radix_tree_gang_lookup() argument
1017 radix_tree_for_each_slot(slot, root, &iter, first_index) { in radix_tree_gang_lookup()
1048 radix_tree_gang_lookup_slot(struct radix_tree_root *root, in radix_tree_gang_lookup_slot() argument
1059 radix_tree_for_each_slot(slot, root, &iter, first_index) { in radix_tree_gang_lookup_slot()
1085 radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results, in radix_tree_gang_lookup_tag() argument
1096 radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) { in radix_tree_gang_lookup_tag()
1122 radix_tree_gang_lookup_tag_slot(struct radix_tree_root *root, void ***results, in radix_tree_gang_lookup_tag_slot() argument
1133 radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) { in radix_tree_gang_lookup_tag_slot()
1200 unsigned long radix_tree_locate_item(struct radix_tree_root *root, void *item) in radix_tree_locate_item() argument
1209 node = rcu_dereference_raw(root->rnode); in radix_tree_locate_item()
1230 unsigned long radix_tree_locate_item(struct radix_tree_root *root, void *item) in radix_tree_locate_item() argument
1240 static inline void radix_tree_shrink(struct radix_tree_root *root) in radix_tree_shrink() argument
1243 while (root->height > 0) { in radix_tree_shrink()
1244 struct radix_tree_node *to_free = root->rnode; in radix_tree_shrink()
1267 if (root->height > 1) { in radix_tree_shrink()
1271 root->rnode = slot; in radix_tree_shrink()
1272 root->height--; in radix_tree_shrink()
1292 if (root->height == 0) in radix_tree_shrink()
1309 void *radix_tree_delete(struct radix_tree_root *root, unsigned long index) in radix_tree_delete() argument
1318 height = root->height; in radix_tree_delete()
1322 slot = root->rnode; in radix_tree_delete()
1324 root_tag_clear_all(root); in radix_tree_delete()
1325 root->rnode = NULL; in radix_tree_delete()
1350 radix_tree_tag_clear(root, index, tag); in radix_tree_delete()
1366 if (node == indirect_to_ptr(root->rnode)) in radix_tree_delete()
1367 radix_tree_shrink(root); in radix_tree_delete()
1379 root_tag_clear_all(root); in radix_tree_delete()
1380 root->height = 0; in radix_tree_delete()
1381 root->rnode = NULL; in radix_tree_delete()
1395 int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag) in radix_tree_tagged() argument
1397 return root_tag_get(root, tag); in radix_tree_tagged()