| /Linux-v4.19/include/linux/ |
| D | rbtree.h | 36 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 …]
|
| D | rbtree_augmented.h | 40 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 …]
|
| /Linux-v4.19/tools/include/linux/ |
| D | rbtree.h | 35 struct rb_node { struct
37 struct rb_node *rb_right; argument
38 struct rb_node *rb_left; argument
43 struct rb_node *rb_node; member
47 #define rb_parent(r) ((struct rb_node *)((r)->__rb_parent_color & ~3))
52 #define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL)
61 extern void rb_insert_color(struct rb_node *, struct rb_root *);
62 extern void rb_erase(struct rb_node *, struct rb_root *);
66 extern struct rb_node *rb_next(const struct rb_node *);
67 extern struct rb_node *rb_prev(const struct rb_node *);
[all …]
|
| D | rbtree_augmented.h | 42 void (*propagate)(struct rb_node *node, struct rb_node *stop);
43 void (*copy)(struct rb_node *old, struct rb_node *new);
44 void (*rotate)(struct rb_node *old, struct rb_node *new);
47 extern void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
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()
69 rbname ## _propagate(struct rb_node *rb, struct rb_node *stop) \
81 rbname ## _copy(struct rb_node *rb_old, struct rb_node *rb_new) \
88 rbname ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new) \
103 #define __rb_parent(pc) ((struct rb_node *)(pc & ~3))
[all …]
|
| /Linux-v4.19/lib/ |
| D | rbtree.c | 71 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 …]
|
| /Linux-v4.19/tools/lib/ |
| D | rbtree.c | 46 static inline void rb_set_black(struct rb_node *rb) in rb_set_black()
51 static inline struct rb_node *rb_red_parent(struct rb_node *red) in rb_red_parent()
53 return (struct rb_node *)red->__rb_parent_color; in rb_red_parent()
62 __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new, in __rb_rotate_set_parents()
65 struct rb_node *parent = rb_parent(old); in __rb_rotate_set_parents()
72 __rb_insert(struct rb_node *node, struct rb_root *root, in __rb_insert()
73 void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) in __rb_insert()
75 struct rb_node *parent = rb_red_parent(node), *gparent, *tmp; in __rb_insert()
201 ____rb_erase_color(struct rb_node *parent, struct rb_root *root, in ____rb_erase_color()
202 void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) in ____rb_erase_color()
[all …]
|
| /Linux-v4.19/tools/perf/util/ |
| D | intlist.c | 14 static struct rb_node *intlist__node_new(struct rblist *rblist __maybe_unused, in intlist__node_new()
18 struct rb_node *rc = NULL; in intlist__node_new()
24 rc = &node->rb_node; in intlist__node_new()
36 struct rb_node *rb_node) in intlist__node_delete() argument
38 struct int_node *node = container_of(rb_node, struct int_node, rb_node); in intlist__node_delete()
43 static int intlist__node_cmp(struct rb_node *rb_node, const void *entry) in intlist__node_cmp() argument
46 struct int_node *node = container_of(rb_node, struct int_node, rb_node); in intlist__node_cmp()
58 rblist__remove_node(&ilist->rblist, &node->rb_node); in intlist__remove()
65 struct rb_node *rb_node; in __intlist__findnew() local
71 rb_node = rblist__findnew(&ilist->rblist, (void *)((long)i)); in __intlist__findnew()
[all …]
|
| D | strlist.c | 16 struct rb_node *strlist__node_new(struct rblist *rblist, const void *entry) in strlist__node_new()
19 struct rb_node *rc = NULL; in strlist__node_new()
30 rc = &snode->rb_node; in strlist__node_new()
48 void strlist__node_delete(struct rblist *rblist, struct rb_node *rb_node) in strlist__node_delete() argument
51 struct str_node *snode = container_of(rb_node, struct str_node, rb_node); in strlist__node_delete()
56 static int strlist__node_cmp(struct rb_node *rb_node, const void *entry) in strlist__node_cmp() argument
59 struct str_node *snode = container_of(rb_node, struct str_node, rb_node); in strlist__node_cmp()
98 rblist__remove_node(&slist->rblist, &snode->rb_node); in strlist__remove()
104 struct rb_node *rb_node = rblist__find(&slist->rblist, entry); in strlist__find() local
106 if (rb_node) in strlist__find()
[all …]
|
| D | rblist.c | 16 struct rb_node **p = &rblist->entries.rb_node; in rblist__add_node()
17 struct rb_node *parent = NULL, *new_node; in rblist__add_node()
44 void rblist__remove_node(struct rblist *rblist, struct rb_node *rb_node) in rblist__remove_node() argument
46 rb_erase(rb_node, &rblist->entries); in rblist__remove_node()
48 rblist->node_delete(rblist, rb_node); in rblist__remove_node()
51 static struct rb_node *__rblist__findnew(struct rblist *rblist, in __rblist__findnew()
55 struct rb_node **p = &rblist->entries.rb_node; in __rblist__findnew()
56 struct rb_node *parent = NULL, *new_node = NULL; in __rblist__findnew()
84 struct rb_node *rblist__find(struct rblist *rblist, const void *entry) in rblist__find()
89 struct rb_node *rblist__findnew(struct rblist *rblist, const void *entry) in rblist__findnew()
[all …]
|
| D | rb_resort.h | 57 struct rb_node rb_node; \
60 static void __name##_sorted__init_entry(struct rb_node *nd, \
63 static int __name##_sorted__cmp(struct rb_node *nda, struct rb_node *ndb) \
66 a = rb_entry(nda, struct __name##_sorted_entry, rb_node); \
67 b = rb_entry(ndb, struct __name##_sorted_entry, rb_node); \
77 struct rb_node *sorted_nd) \
79 struct rb_node **p = &sorted->entries.rb_node, *parent = NULL; \
94 struct rb_node *nd; \
99 __name##_sorted__insert(sorted, &snd->rb_node); \
120 static void __name##_sorted__init_entry(struct rb_node *nd, \
[all …]
|
| D | rblist.h | 26 int (*node_cmp)(struct rb_node *rbn, const void *entry);
27 struct rb_node *(*node_new)(struct rblist *rlist, const void *new_entry);
28 void (*node_delete)(struct rblist *rblist, struct rb_node *rb_node);
35 void rblist__remove_node(struct rblist *rblist, struct rb_node *rb_node);
36 struct rb_node *rblist__find(struct rblist *rblist, const void *entry);
37 struct rb_node *rblist__findnew(struct rblist *rblist, const void *entry);
38 struct rb_node *rblist__entry(const struct rblist *rblist, unsigned int idx);
|
| D | mem2node.c | 8 struct rb_node rb_node; member
16 struct rb_node **p = &root->rb_node; in phys_entry__insert()
17 struct rb_node *parent = NULL; in phys_entry__insert()
22 e = rb_entry(parent, struct phys_entry, rb_node); in phys_entry__insert()
30 rb_link_node(&entry->rb_node, parent, p); in phys_entry__insert()
31 rb_insert_color(&entry->rb_node, root); in phys_entry__insert()
40 RB_CLEAR_NODE(&entry->rb_node); in phys_entry__init()
116 struct rb_node **p, *parent = NULL; in mem2node__node()
119 p = &map->root.rb_node; in mem2node__node()
122 entry = rb_entry(parent, struct phys_entry, rb_node); in mem2node__node()
|
| D | srcline.c | 566 struct rb_node rb_node; member
571 struct rb_node **p = &tree->rb_node; in srcline__tree_insert()
572 struct rb_node *parent = NULL; in srcline__tree_insert()
586 i = rb_entry(parent, struct srcline_node, rb_node); in srcline__tree_insert()
592 rb_link_node(&node->rb_node, parent, p); in srcline__tree_insert()
593 rb_insert_color(&node->rb_node, tree); in srcline__tree_insert()
598 struct rb_node *n = tree->rb_node; in srcline__tree_find()
602 rb_node); in srcline__tree_find()
618 struct rb_node *next = rb_first(tree); in srcline__tree_delete()
621 pos = rb_entry(next, struct srcline_node, rb_node); in srcline__tree_delete()
[all …]
|
| D | comm.c | 13 struct rb_node rb_node; member
33 rb_erase(&cs->rb_node, &comm_str_root); in comm_str__put()
62 struct rb_node **p = &root->rb_node; in __comm_str__findnew()
63 struct rb_node *parent = NULL; in __comm_str__findnew()
69 iter = rb_entry(parent, struct comm_str, rb_node); in __comm_str__findnew()
90 rb_link_node(&new->rb_node, parent, p); in __comm_str__findnew()
91 rb_insert_color(&new->rb_node, root); in __comm_str__findnew()
|
| D | map.c | 136 RB_CLEAR_NODE(&map->rb_node); in map__init()
269 BUG_ON(!RB_EMPTY_NODE(&map->rb_node)); in map__exit()
288 struct rb_node *nd = rb_first(symbols); in map__fixup_start()
290 struct symbol *sym = rb_entry(nd, struct symbol, rb_node); in map__fixup_start()
298 struct rb_node *nd = rb_last(symbols); in map__fixup_end()
300 struct symbol *sym = rb_entry(nd, struct symbol, rb_node); in map__fixup_end()
376 RB_CLEAR_NODE(&map->rb_node); in map__clone()
514 struct rb_node *next = rb_first(root); in __maps__purge()
517 struct map *pos = rb_entry(next, struct map, rb_node); in __maps__purge()
519 next = rb_next(&pos->rb_node); in __maps__purge()
[all …]
|
| D | symbol.c | 168 struct rb_node *nd; in symbols__fixup_duplicate()
177 curr = rb_entry(nd, struct symbol, rb_node); in symbols__fixup_duplicate()
179 nd = rb_next(&curr->rb_node); in symbols__fixup_duplicate()
180 next = rb_entry(nd, struct symbol, rb_node); in symbols__fixup_duplicate()
189 rb_erase(&next->rb_node, symbols); in symbols__fixup_duplicate()
193 nd = rb_next(&curr->rb_node); in symbols__fixup_duplicate()
194 rb_erase(&curr->rb_node, symbols); in symbols__fixup_duplicate()
202 struct rb_node *nd, *prevnd = rb_first(symbols); in symbols__fixup_end()
208 curr = rb_entry(prevnd, struct symbol, rb_node); in symbols__fixup_end()
212 curr = rb_entry(nd, struct symbol, rb_node); in symbols__fixup_end()
[all …]
|
| D | intlist.h | 11 struct rb_node rb_node; member
48 struct rb_node *rn = rb_first(&ilist->rblist.entries); in intlist__first()
49 return rn ? rb_entry(rn, struct int_node, rb_node) : NULL; in intlist__first()
53 struct rb_node *rn; in intlist__next()
56 rn = rb_next(&in->rb_node); in intlist__next()
57 return rn ? rb_entry(rn, struct int_node, rb_node) : NULL; in intlist__next()
|
| D | strlist.h | 11 struct rb_node rb_node; member
60 struct rb_node *rn = rb_first(&slist->rblist.entries); in strlist__first()
61 return rn ? rb_entry(rn, struct str_node, rb_node) : NULL; in strlist__first()
65 struct rb_node *rn; in strlist__next()
68 rn = rb_next(&sn->rb_node); in strlist__next()
69 return rn ? rb_entry(rn, struct str_node, rb_node) : NULL; in strlist__next()
|
| /Linux-v4.19/fs/btrfs/ |
| D | extent_map.c | 55 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 …]
|
| D | ordered-data.c | 28 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 …]
|
| /Linux-v4.19/tools/perf/tests/ |
| D | hists_output.c | 96 struct rb_node *node; in del_hist_entries()
108 he = rb_entry(node, struct hist_entry, rb_node); in del_hist_entries()
130 struct rb_node *node; in test1()
166 he = rb_entry(node, struct hist_entry, rb_node); in test1()
172 he = rb_entry(node, struct hist_entry, rb_node); in test1()
178 he = rb_entry(node, struct hist_entry, rb_node); in test1()
184 he = rb_entry(node, struct hist_entry, rb_node); in test1()
190 he = rb_entry(node, struct hist_entry, rb_node); in test1()
196 he = rb_entry(node, struct hist_entry, rb_node); in test1()
202 he = rb_entry(node, struct hist_entry, rb_node); in test1()
[all …]
|
| /Linux-v4.19/arch/powerpc/kernel/ |
| D | eeh_cache.c | 50 struct rb_node rb_node; member
65 struct rb_node *n = pci_io_addr_cache_root.rb_root.rb_node; in __eeh_addr_cache_get_device()
69 piar = rb_entry(n, struct pci_io_addr_range, rb_node); in __eeh_addr_cache_get_device()
109 struct rb_node *n; in eeh_addr_cache_print()
115 piar = rb_entry(n, struct pci_io_addr_range, rb_node); in eeh_addr_cache_print()
130 struct rb_node **p = &pci_io_addr_cache_root.rb_root.rb_node; in eeh_addr_cache_insert()
131 struct rb_node *parent = NULL; in eeh_addr_cache_insert()
137 piar = rb_entry(parent, struct pci_io_addr_range, rb_node); in eeh_addr_cache_insert()
165 rb_link_node(&piar->rb_node, parent, p); in eeh_addr_cache_insert()
166 rb_insert_color(&piar->rb_node, &pci_io_addr_cache_root.rb_root); in eeh_addr_cache_insert()
[all …]
|
| /Linux-v4.19/arch/sh/kernel/ |
| D | dwarf.c | 308 struct rb_node **rb_node = &cie_root.rb_node; in dwarf_lookup_cie() local
323 while (*rb_node) { in dwarf_lookup_cie()
326 cie_tmp = rb_entry(*rb_node, struct dwarf_cie, node); in dwarf_lookup_cie()
335 rb_node = &(*rb_node)->rb_left; in dwarf_lookup_cie()
337 rb_node = &(*rb_node)->rb_right; in dwarf_lookup_cie()
352 struct rb_node **rb_node = &fde_root.rb_node; in dwarf_lookup_fde() local
358 while (*rb_node) { in dwarf_lookup_fde()
362 fde_tmp = rb_entry(*rb_node, struct dwarf_fde, node); in dwarf_lookup_fde()
369 rb_node = &(*rb_node)->rb_left; in dwarf_lookup_fde()
375 rb_node = &(*rb_node)->rb_right; in dwarf_lookup_fde()
[all …]
|
| /Linux-v4.19/fs/f2fs/ |
| D | extent_cache.c | 36 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-v4.19/security/keys/ |
| D | proc.c | 69 static struct rb_node *key_serial_next(struct seq_file *p, struct rb_node *n) in key_serial_next()
86 struct rb_node *n = key_serial_tree.rb_node; in find_ge_key()
134 static inline key_serial_t key_node_serial(struct rb_node *n) in key_node_serial()
142 struct rb_node *n; in proc_keys_next()
158 struct rb_node *_p = v; in proc_keys_show()
253 static struct rb_node *__key_user_next(struct user_namespace *user_ns, struct rb_node *n) in __key_user_next()
264 static struct rb_node *key_user_next(struct user_namespace *user_ns, struct rb_node *n) in key_user_next()
269 static struct rb_node *key_user_first(struct user_namespace *user_ns, struct rb_root *r) in key_user_first()
271 struct rb_node *n = rb_first(r); in key_user_first()
278 struct rb_node *_p; in proc_key_users_start()
[all …]
|
