Home
last modified time | relevance | path

Searched refs:rb_node (Results 1 – 25 of 175) sorted by relevance

1234567

/linux-4.19.296/include/linux/
Drbtree.h36 struct rb_node { struct
38 struct rb_node *rb_right; argument
39 struct rb_node *rb_left; argument
44 struct rb_node *rb_node; member
59 struct rb_node *rb_leftmost;
62 #define rb_parent(r) ((struct rb_node *)((r)->__rb_parent_color & ~3))
68 #define RB_EMPTY_ROOT(root) (READ_ONCE((root)->rb_node) == NULL)
77 extern void rb_insert_color(struct rb_node *, struct rb_root *);
78 extern void rb_erase(struct rb_node *, struct rb_root *);
82 extern struct rb_node *rb_next(const struct rb_node *);
[all …]
Drbtree_augmented.h40 void (*propagate)(struct rb_node *node, struct rb_node *stop);
41 void (*copy)(struct rb_node *old, struct rb_node *new);
42 void (*rotate)(struct rb_node *old, struct rb_node *new);
45 extern void __rb_insert_augmented(struct rb_node *node,
47 bool newleft, struct rb_node **leftmost,
48 void (*augment_rotate)(struct rb_node *old, struct rb_node *new));
60 rb_insert_augmented(struct rb_node *node, struct rb_root *root, in rb_insert_augmented()
67 rb_insert_augmented_cached(struct rb_node *node, in rb_insert_augmented_cached()
78 rbname ## _propagate(struct rb_node *rb, struct rb_node *stop) \
90 rbname ## _copy(struct rb_node *rb_old, struct rb_node *rb_new) \
[all …]
Drbtree_latch.h41 struct rb_node node[2];
70 __lt_from_rb(struct rb_node *node, int idx) in __lt_from_rb()
80 struct rb_node **link = &root->rb_node; in __lt_insert()
81 struct rb_node *node = &ltn->node[idx]; in __lt_insert()
82 struct rb_node *parent = NULL; in __lt_insert()
109 struct rb_node *node = rcu_dereference_raw(ltr->tree[idx].rb_node); in __lt_find()
Dinterval_tree_generic.h71 struct rb_node **link = &root->rb_root.rb_node, *rb_parent = NULL; \
154 if (!root->rb_root.rb_node) \
170 node = rb_entry(root->rb_root.rb_node, ITSTRUCT, ITRB); \
184 struct rb_node *rb = node->ITRB.rb_right, *prev; \
Dtimerqueue.h10 struct rb_node node;
36 struct rb_node *leftmost = rb_first_cached(&head->rb_root); in timerqueue_getnext()
/linux-4.19.296/lib/
Drbtree.c71 static inline void rb_set_black(struct rb_node *rb) in rb_set_black()
76 static inline struct rb_node *rb_red_parent(struct rb_node *red) in rb_red_parent()
78 return (struct rb_node *)red->__rb_parent_color; in rb_red_parent()
87 __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new, in __rb_rotate_set_parents()
90 struct rb_node *parent = rb_parent(old); in __rb_rotate_set_parents()
97 __rb_insert(struct rb_node *node, struct rb_root *root, in __rb_insert()
98 bool newleft, struct rb_node **leftmost, in __rb_insert()
99 void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) in __rb_insert()
101 struct rb_node *parent = rb_red_parent(node), *gparent, *tmp; in __rb_insert()
243 ____rb_erase_color(struct rb_node *parent, struct rb_root *root, in ____rb_erase_color()
[all …]
Drbtree_test.c19 struct rb_node rb;
33 struct rb_node **new = &root->rb_root.rb_node, *parent = NULL; in insert()
50 struct rb_node **new = &root->rb_root.rb_node, *parent = NULL; in insert_cached()
103 struct rb_node **new = &root->rb_root.rb_node, *rb_parent = NULL; in RB_DECLARE_CALLBACKS()
127 struct rb_node **new = &root->rb_root.rb_node, *rb_parent = NULL; in insert_augmented_cached()
173 static bool is_red(struct rb_node *rb) in is_red()
178 static int black_path_count(struct rb_node *rb) in black_path_count()
198 struct rb_node *rb; in check_postorder()
208 struct rb_node *rb; in check()
235 struct rb_node *rb; in check_augmented()
[all …]
Dtimerqueue.c42 struct rb_node **p = &head->rb_root.rb_root.rb_node; in timerqueue_add()
43 struct rb_node *parent = NULL; in timerqueue_add()
98 struct rb_node *next; in timerqueue_iterate_next()
/linux-4.19.296/fs/btrfs/
Dextent_map.c55 RB_CLEAR_NODE(&em->rb_node); in alloc_extent_map()
95 struct rb_node **p = &root->rb_node; in tree_insert()
96 struct rb_node *parent = NULL; in tree_insert()
98 struct rb_node *orig_parent = NULL; in tree_insert()
103 entry = rb_entry(parent, struct extent_map, rb_node); in tree_insert()
116 entry = rb_entry(parent, struct extent_map, rb_node); in tree_insert()
123 entry = rb_entry(parent, struct extent_map, rb_node); in tree_insert()
126 entry = rb_entry(parent, struct extent_map, rb_node); in tree_insert()
132 rb_link_node(&em->rb_node, orig_parent, p); in tree_insert()
133 rb_insert_color(&em->rb_node, root); in tree_insert()
[all …]
Dordered-data.c28 static struct rb_node *tree_insert(struct rb_root *root, u64 file_offset, in tree_insert()
29 struct rb_node *node) in tree_insert()
31 struct rb_node **p = &root->rb_node; in tree_insert()
32 struct rb_node *parent = NULL; in tree_insert()
37 entry = rb_entry(parent, struct btrfs_ordered_extent, rb_node); in tree_insert()
64 static struct rb_node *__tree_search(struct rb_root *root, u64 file_offset, in __tree_search()
65 struct rb_node **prev_ret) in __tree_search()
67 struct rb_node *n = root->rb_node; in __tree_search()
68 struct rb_node *prev = NULL; in __tree_search()
69 struct rb_node *test; in __tree_search()
[all …]
Dulist.c120 struct rb_node *n = ulist->root.rb_node; in ulist_rbtree_search()
124 u = rb_entry(n, struct ulist_node, rb_node); in ulist_rbtree_search()
137 rb_erase(&node->rb_node, &ulist->root); in ulist_rbtree_erase()
146 struct rb_node **p = &ulist->root.rb_node; in ulist_rbtree_insert()
147 struct rb_node *parent = NULL; in ulist_rbtree_insert()
152 cur = rb_entry(parent, struct ulist_node, rb_node); in ulist_rbtree_insert()
161 rb_link_node(&ins->rb_node, parent, p); in ulist_rbtree_insert()
162 rb_insert_color(&ins->rb_node, &ulist->root); in ulist_rbtree_insert()
Drelocation.c28 struct rb_node rb_node; member
36 struct rb_node rb_node; member
116 struct rb_node rb_node; member
130 struct rb_node rb_node; member
244 RB_CLEAR_NODE(&node->rb_node); in alloc_backref_node()
278 static struct rb_node *tree_insert(struct rb_root *root, u64 bytenr, in tree_insert()
279 struct rb_node *node) in tree_insert()
281 struct rb_node **p = &root->rb_node; in tree_insert()
282 struct rb_node *parent = NULL; in tree_insert()
287 entry = rb_entry(parent, struct tree_entry, rb_node); in tree_insert()
[all …]
Dref-verify.c22 struct rb_node node;
36 struct rb_node node;
71 struct rb_node node;
78 struct rb_node **p = &root->rb_node; in insert_block_entry()
79 struct rb_node *parent_node = NULL; in insert_block_entry()
100 struct rb_node *n; in lookup_block_entry()
103 n = root->rb_node; in lookup_block_entry()
119 struct rb_node **p = &root->rb_node; in insert_root_entry()
120 struct rb_node *parent_node = NULL; in insert_root_entry()
164 struct rb_node **p = &root->rb_node; in insert_ref_entry()
[all …]
Dextent_map.h23 struct rb_node rb_node; member
59 return !RB_EMPTY_NODE(&em->rb_node); in extent_map_in_tree()
Dextent_io.c33 return !RB_EMPTY_NODE(&state->rb_node); in extent_state_in_tree()
108 struct rb_node rb_node; member
272 RB_CLEAR_NODE(&state->rb_node); in alloc_extent_state()
292 static struct rb_node *tree_insert(struct rb_root *root, in tree_insert()
293 struct rb_node *search_start, in tree_insert()
295 struct rb_node *node, in tree_insert()
296 struct rb_node ***p_in, in tree_insert()
297 struct rb_node **parent_in) in tree_insert()
299 struct rb_node **p; in tree_insert()
300 struct rb_node *parent = NULL; in tree_insert()
[all …]
/linux-4.19.296/fs/f2fs/
Dextent_cache.c36 struct rb_node *node = root->rb_node; in __lookup_rb_tree_slow()
40 re = rb_entry(node, struct rb_entry, rb_node); in __lookup_rb_tree_slow()
64 struct rb_node **f2fs_lookup_rb_tree_for_insert(struct f2fs_sb_info *sbi, in f2fs_lookup_rb_tree_for_insert()
65 struct rb_root *root, struct rb_node **parent, in f2fs_lookup_rb_tree_for_insert()
68 struct rb_node **p = &root->rb_node; in f2fs_lookup_rb_tree_for_insert()
73 re = rb_entry(*parent, struct rb_entry, rb_node); in f2fs_lookup_rb_tree_for_insert()
100 struct rb_node ***insert_p, in f2fs_lookup_rb_tree_ret()
101 struct rb_node **insert_parent, in f2fs_lookup_rb_tree_ret()
104 struct rb_node **pnode = &root->rb_node; in f2fs_lookup_rb_tree_ret()
105 struct rb_node *parent = NULL, *tmp_node; in f2fs_lookup_rb_tree_ret()
[all …]
/linux-4.19.296/fs/xfs/
Dxfs_extent_busy.c33 struct rb_node **rbp; in xfs_extent_busy_insert()
34 struct rb_node *parent = NULL; in xfs_extent_busy_insert()
48 rbp = &pag->pagb_tree.rb_node; in xfs_extent_busy_insert()
51 busyp = rb_entry(parent, struct xfs_extent_busy, rb_node); in xfs_extent_busy_insert()
64 rb_link_node(&new->rb_node, parent, rbp); in xfs_extent_busy_insert()
65 rb_insert_color(&new->rb_node, &pag->pagb_tree); in xfs_extent_busy_insert()
89 struct rb_node *rbp; in xfs_extent_busy_search()
96 rbp = pag->pagb_tree.rb_node; in xfs_extent_busy_search()
100 busyp = rb_entry(rbp, struct xfs_extent_busy, rb_node); in xfs_extent_busy_search()
228 rb_erase(&busyp->rb_node, &pag->pagb_tree); in xfs_extent_busy_update_extent()
[all …]
/linux-4.19.296/fs/ext4/
Dextents_status.c178 struct rb_node *node; in ext4_es_print_tree()
185 es = rb_entry(node, struct extent_status, rb_node); in ext4_es_print_tree()
210 struct rb_node *node = root->rb_node; in __es_tree_search()
214 es = rb_entry(node, struct extent_status, rb_node); in __es_tree_search()
227 node = rb_next(&es->rb_node); in __es_tree_search()
228 return node ? rb_entry(node, struct extent_status, rb_node) : in __es_tree_search()
250 struct rb_node *node; in ext4_es_find_delayed_extent_range()
275 while ((node = rb_next(&es1->rb_node)) != NULL) { in ext4_es_find_delayed_extent_range()
276 es1 = rb_entry(node, struct extent_status, rb_node); in ext4_es_find_delayed_extent_range()
417 struct rb_node *node; in ext4_es_try_to_merge_left()
[all …]
Dblock_validity.c24 struct rb_node node;
74 struct rb_node **n = &system_blks->root.rb_node, *node; in add_system_zone()
75 struct rb_node *parent = NULL, *new_node = NULL; in add_system_zone()
127 struct rb_node *node; in debug_print_tree()
154 struct rb_node *n; in ext4_data_block_valid_rcu()
166 n = system_blks->root.rb_node; in ext4_data_block_valid_rcu()
/linux-4.19.296/block/
Dbfq-wf2q.c34 struct rb_node *node = tree->rb_node; in bfq_root_active_entity()
36 return rb_entry(node, struct bfq_entity, rb_node); in bfq_root_active_entity()
321 struct bfq_entity *bfq_entity_of(struct rb_node *node) in bfq_entity_of()
326 entity = rb_entry(node, struct bfq_entity, rb_node); in bfq_entity_of()
339 rb_erase(&entity->rb_node, root); in bfq_extract()
351 struct rb_node *next; in bfq_idle_extract()
354 next = rb_next(&entity->rb_node); in bfq_idle_extract()
359 next = rb_prev(&entity->rb_node); in bfq_idle_extract()
380 struct rb_node **node = &root->rb_node; in bfq_insert()
381 struct rb_node *parent = NULL; in bfq_insert()
[all …]
/linux-4.19.296/drivers/base/regmap/
Dregcache-rbtree.c35 struct rb_node node;
70 struct rb_node *node; in regcache_rbtree_lookup()
82 node = rbtree_ctx->root.rb_node; in regcache_rbtree_lookup()
103 struct rb_node **new, *parent; in regcache_rbtree_insert()
109 new = &root->rb_node; in regcache_rbtree_insert()
141 struct rb_node *node; in rbtree_show()
229 struct rb_node *next; in regcache_rbtree_exit()
387 struct rb_node *node; in regcache_rbtree_write()
416 node = rbtree_ctx->root.rb_node; in regcache_rbtree_write()
483 struct rb_node *node; in regcache_rbtree_sync()
[all …]
/linux-4.19.296/fs/proc/
Dnommu.c80 struct rb_node *p = _p; in nommu_region_list_show()
87 struct rb_node *p; in nommu_region_list_start()
106 return rb_next((struct rb_node *) v); in nommu_region_list_next()
Dtask_nommu.c25 struct rb_node *p; in task_mem()
86 struct rb_node *p; in task_vsize()
104 struct rb_node *p; in task_statm()
193 struct rb_node *p = _p; in show_map()
202 struct rb_node *p; in m_start()
245 struct rb_node *p = _p; in m_next()
/linux-4.19.296/include/linux/ceph/
Dosd_client.h37 struct rb_node o_node;
171 struct rb_node r_node;
172 struct rb_node r_mc_node; /* map check */
260 struct rb_node node; /* osd */
261 struct rb_node osdc_node; /* osdc */
262 struct rb_node mc_node; /* map check */
289 struct rb_node node;
321 struct rb_node spg_node;
322 struct rb_node id_node;
/linux-4.19.296/fs/ubifs/
Dlog.c44 struct rb_node *p; in ubifs_search_bud()
48 p = c->buds.rb_node; in ubifs_search_bud()
73 struct rb_node *p; in ubifs_get_wbuf()
81 p = c->buds.rb_node; in ubifs_get_wbuf()
126 struct rb_node **p, *parent = NULL; in ubifs_add_bud()
131 p = &c->buds.rb_node; in ubifs_add_bud()
302 struct rb_node *p; in remove_buds()
309 struct rb_node *p1 = p; in remove_buds()
540 struct rb_node rb;
554 struct rb_node **p = &done_tree->rb_node, *parent = NULL; in done_already()

1234567