/kernel/linux/linux-5.10/include/linux/ |
D | rbtree.h | 24 struct rb_node { struct 26 struct rb_node *rb_right; argument 27 struct rb_node *rb_left; argument 32 struct rb_node *rb_node; member 35 #define rb_parent(r) ((struct rb_node *)((r)->__rb_parent_color & ~3)) 40 #define RB_EMPTY_ROOT(root) (READ_ONCE((root)->rb_node) == NULL) 49 extern void rb_insert_color(struct rb_node *, struct rb_root *); 50 extern void rb_erase(struct rb_node *, struct rb_root *); 54 extern struct rb_node *rb_next(const struct rb_node *); 55 extern struct rb_node *rb_prev(const struct rb_node *); [all …]
|
D | rbtree_augmented.h | 28 void (*propagate)(struct rb_node *node, struct rb_node *stop); 29 void (*copy)(struct rb_node *old, struct rb_node *new); 30 void (*rotate)(struct rb_node *old, struct rb_node *new); 33 extern void __rb_insert_augmented(struct rb_node *node, struct rb_root *root, 34 void (*augment_rotate)(struct rb_node *old, struct rb_node *new)); 47 rb_insert_augmented(struct rb_node *node, struct rb_root *root, in rb_insert_augmented() 54 rb_insert_augmented_cached(struct rb_node *node, in rb_insert_augmented_cached() 77 RBNAME ## _propagate(struct rb_node *rb, struct rb_node *stop) \ 87 RBNAME ## _copy(struct rb_node *rb_old, struct rb_node *rb_new) \ 94 RBNAME ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new) \ [all …]
|
/kernel/linux/linux-5.10/tools/include/linux/ |
D | rbtree.h | 23 struct rb_node { struct 25 struct rb_node *rb_right; argument 26 struct rb_node *rb_left; argument 31 struct rb_node *rb_node; member 34 #define rb_parent(r) ((struct rb_node *)((r)->__rb_parent_color & ~3)) 39 #define RB_EMPTY_ROOT(root) (READ_ONCE((root)->rb_node) == NULL) 48 extern void rb_insert_color(struct rb_node *, struct rb_root *); 49 extern void rb_erase(struct rb_node *, struct rb_root *); 53 extern struct rb_node *rb_next(const struct rb_node *); 54 extern struct rb_node *rb_prev(const struct rb_node *); [all …]
|
D | rbtree_augmented.h | 30 void (*propagate)(struct rb_node *node, struct rb_node *stop); 31 void (*copy)(struct rb_node *old, struct rb_node *new); 32 void (*rotate)(struct rb_node *old, struct rb_node *new); 35 extern void __rb_insert_augmented(struct rb_node *node, struct rb_root *root, 36 void (*augment_rotate)(struct rb_node *old, struct rb_node *new)); 49 rb_insert_augmented(struct rb_node *node, struct rb_root *root, in rb_insert_augmented() 56 rb_insert_augmented_cached(struct rb_node *node, in rb_insert_augmented_cached() 79 RBNAME ## _propagate(struct rb_node *rb, struct rb_node *stop) \ 89 RBNAME ## _copy(struct rb_node *rb_old, struct rb_node *rb_new) \ 96 RBNAME ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new) \ [all …]
|
/kernel/linux/linux-5.10/tools/lib/ |
D | rbtree.c | 59 static inline void rb_set_black(struct rb_node *rb) in rb_set_black() 64 static inline struct rb_node *rb_red_parent(struct rb_node *red) in rb_red_parent() 66 return (struct rb_node *)red->__rb_parent_color; in rb_red_parent() 75 __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new, in __rb_rotate_set_parents() 78 struct rb_node *parent = rb_parent(old); in __rb_rotate_set_parents() 85 __rb_insert(struct rb_node *node, struct rb_root *root, in __rb_insert() 86 void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) in __rb_insert() 88 struct rb_node *parent = rb_red_parent(node), *gparent, *tmp; in __rb_insert() 227 ____rb_erase_color(struct rb_node *parent, struct rb_root *root, in ____rb_erase_color() 228 void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) in ____rb_erase_color() [all …]
|
/kernel/linux/linux-5.10/lib/ |
D | rbtree.c | 59 static inline void rb_set_black(struct rb_node *rb) in rb_set_black() 64 static inline struct rb_node *rb_red_parent(struct rb_node *red) in rb_red_parent() 66 return (struct rb_node *)red->__rb_parent_color; in rb_red_parent() 75 __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new, in __rb_rotate_set_parents() 78 struct rb_node *parent = rb_parent(old); in __rb_rotate_set_parents() 85 __rb_insert(struct rb_node *node, struct rb_root *root, in __rb_insert() 86 void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) in __rb_insert() 88 struct rb_node *parent = rb_red_parent(node), *gparent, *tmp; in __rb_insert() 227 ____rb_erase_color(struct rb_node *parent, struct rb_root *root, in ____rb_erase_color() 228 void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) in ____rb_erase_color() [all …]
|
/kernel/linux/linux-5.10/tools/perf/util/ |
D | intlist.c | 13 static struct rb_node *intlist__node_new(struct rblist *rblist __maybe_unused, in intlist__node_new() 17 struct rb_node *rc = NULL; in intlist__node_new() 23 rc = &node->rb_node; in intlist__node_new() 35 struct rb_node *rb_node) in intlist__node_delete() argument 37 struct int_node *node = container_of(rb_node, struct int_node, rb_node); in intlist__node_delete() 42 static int intlist__node_cmp(struct rb_node *rb_node, const void *entry) in intlist__node_cmp() argument 45 struct int_node *node = container_of(rb_node, struct int_node, rb_node); in intlist__node_cmp() 57 rblist__remove_node(&ilist->rblist, &node->rb_node); in intlist__remove() 64 struct rb_node *rb_node; in __intlist__findnew() local 70 rb_node = rblist__findnew(&ilist->rblist, (void *)((long)i)); in __intlist__findnew() [all …]
|
D | strlist.c | 15 struct rb_node *strlist__node_new(struct rblist *rblist, const void *entry) in strlist__node_new() 18 struct rb_node *rc = NULL; in strlist__node_new() 29 rc = &snode->rb_node; in strlist__node_new() 47 void strlist__node_delete(struct rblist *rblist, struct rb_node *rb_node) in strlist__node_delete() argument 50 struct str_node *snode = container_of(rb_node, struct str_node, rb_node); in strlist__node_delete() 55 static int strlist__node_cmp(struct rb_node *rb_node, const void *entry) in strlist__node_cmp() argument 58 struct str_node *snode = container_of(rb_node, struct str_node, rb_node); in strlist__node_cmp() 97 rblist__remove_node(&slist->rblist, &snode->rb_node); in strlist__remove() 103 struct rb_node *rb_node = rblist__find(&slist->rblist, entry); in strlist__find() local 105 if (rb_node) in strlist__find() [all …]
|
D | rblist.c | 15 struct rb_node **p = &rblist->entries.rb_root.rb_node; in rblist__add_node() 16 struct rb_node *parent = NULL, *new_node; in rblist__add_node() 46 void rblist__remove_node(struct rblist *rblist, struct rb_node *rb_node) in rblist__remove_node() argument 48 rb_erase_cached(rb_node, &rblist->entries); in rblist__remove_node() 50 rblist->node_delete(rblist, rb_node); in rblist__remove_node() 53 static struct rb_node *__rblist__findnew(struct rblist *rblist, in __rblist__findnew() 57 struct rb_node **p = &rblist->entries.rb_root.rb_node; in __rblist__findnew() 58 struct rb_node *parent = NULL, *new_node = NULL; in __rblist__findnew() 90 struct rb_node *rblist__find(struct rblist *rblist, const void *entry) in rblist__find() 95 struct rb_node *rblist__findnew(struct rblist *rblist, const void *entry) in rblist__findnew() [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 | 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 | env.c | 23 struct rb_node *parent = NULL; in perf_env__insert_bpf_prog_info() 24 struct rb_node **p; in perf_env__insert_bpf_prog_info() 27 p = &env->bpf_progs.infos.rb_node; in perf_env__insert_bpf_prog_info() 31 node = rb_entry(parent, struct bpf_prog_info_node, rb_node); in perf_env__insert_bpf_prog_info() 42 rb_link_node(&info_node->rb_node, parent, p); in perf_env__insert_bpf_prog_info() 43 rb_insert_color(&info_node->rb_node, &env->bpf_progs.infos); in perf_env__insert_bpf_prog_info() 53 struct rb_node *n; in perf_env__find_bpf_prog_info() 56 n = env->bpf_progs.infos.rb_node; in perf_env__find_bpf_prog_info() 59 node = rb_entry(n, struct bpf_prog_info_node, rb_node); in perf_env__find_bpf_prog_info() 76 struct rb_node *parent = NULL; in perf_env__insert_btf() [all …]
|
D | mem2node.c | 12 struct rb_node rb_node; member 20 struct rb_node **p = &root->rb_node; in phys_entry__insert() 21 struct rb_node *parent = NULL; in phys_entry__insert() 26 e = rb_entry(parent, struct phys_entry, rb_node); in phys_entry__insert() 34 rb_link_node(&entry->rb_node, parent, p); in phys_entry__insert() 35 rb_insert_color(&entry->rb_node, root); in phys_entry__insert() 44 RB_CLEAR_NODE(&entry->rb_node); in phys_entry__init() 120 struct rb_node **p, *parent = NULL; in mem2node__node() 123 p = &map->root.rb_node; in mem2node__node() 126 entry = rb_entry(parent, struct phys_entry, rb_node); in mem2node__node()
|
D | srcline.c | 611 struct rb_node rb_node; member 616 struct rb_node **p = &tree->rb_root.rb_node; in srcline__tree_insert() 617 struct rb_node *parent = NULL; in srcline__tree_insert() 632 i = rb_entry(parent, struct srcline_node, rb_node); in srcline__tree_insert() 640 rb_link_node(&node->rb_node, parent, p); in srcline__tree_insert() 641 rb_insert_color_cached(&node->rb_node, tree, leftmost); in srcline__tree_insert() 646 struct rb_node *n = tree->rb_root.rb_node; in srcline__tree_find() 650 rb_node); in srcline__tree_find() 666 struct rb_node *next = rb_first_cached(tree); in srcline__tree_delete() 669 pos = rb_entry(next, struct srcline_node, rb_node); in srcline__tree_delete() [all …]
|
D | comm.c | 14 struct rb_node rb_node; member 34 rb_erase(&cs->rb_node, &comm_str_root); in comm_str__put() 63 struct rb_node **p = &root->rb_node; in __comm_str__findnew() 64 struct rb_node *parent = NULL; in __comm_str__findnew() 70 iter = rb_entry(parent, struct comm_str, rb_node); in __comm_str__findnew() 91 rb_link_node(&new->rb_node, parent, p); in __comm_str__findnew() 92 rb_insert_color(&new->rb_node, root); in __comm_str__findnew()
|
D | intlist.h | 11 struct rb_node rb_node; member 48 struct rb_node *rn = rb_first_cached(&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_cached(&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()
|
/kernel/linux/linux-5.10/fs/btrfs/ |
D | extent_map.c | 56 RB_CLEAR_NODE(&em->rb_node); in alloc_extent_map() 96 struct rb_node **p = &root->rb_root.rb_node; in tree_insert() 97 struct rb_node *parent = NULL; in tree_insert() 99 struct rb_node *orig_parent = NULL; in tree_insert() 105 entry = rb_entry(parent, struct extent_map, rb_node); in tree_insert() 120 entry = rb_entry(parent, struct extent_map, rb_node); in tree_insert() 127 entry = rb_entry(parent, struct extent_map, rb_node); in tree_insert() 130 entry = rb_entry(parent, struct extent_map, rb_node); in tree_insert() 136 rb_link_node(&em->rb_node, orig_parent, p); in tree_insert() 137 rb_insert_color_cached(&em->rb_node, root, leftmost); in tree_insert() [all …]
|
D | misc.h | 69 struct rb_node rb_node; member 73 static inline struct rb_node *rb_simple_search(struct rb_root *root, u64 bytenr) in rb_simple_search() 75 struct rb_node *node = root->rb_node; in rb_simple_search() 79 entry = rb_entry(node, struct rb_simple_node, rb_node); in rb_simple_search() 91 static inline struct rb_node *rb_simple_insert(struct rb_root *root, u64 bytenr, in rb_simple_insert() 92 struct rb_node *node) in rb_simple_insert() 94 struct rb_node **p = &root->rb_node; in rb_simple_insert() 95 struct rb_node *parent = NULL; in rb_simple_insert() 100 entry = rb_entry(parent, struct rb_simple_node, rb_node); in rb_simple_insert()
|
/kernel/linux/linux-5.10/arch/powerpc/kernel/ |
D | eeh_cache.c | 41 struct rb_node rb_node; member 56 struct rb_node *n = pci_io_addr_cache_root.rb_root.rb_node; in __eeh_addr_cache_get_device() 60 piar = rb_entry(n, struct pci_io_addr_range, rb_node); in __eeh_addr_cache_get_device() 100 struct rb_node *n; in eeh_addr_cache_print() 106 piar = rb_entry(n, struct pci_io_addr_range, rb_node); in eeh_addr_cache_print() 121 struct rb_node **p = &pci_io_addr_cache_root.rb_root.rb_node; in eeh_addr_cache_insert() 122 struct rb_node *parent = NULL; in eeh_addr_cache_insert() 128 piar = rb_entry(parent, struct pci_io_addr_range, rb_node); in eeh_addr_cache_insert() 154 rb_link_node(&piar->rb_node, parent, p); in eeh_addr_cache_insert() 155 rb_insert_color(&piar->rb_node, &pci_io_addr_cache_root.rb_root); in eeh_addr_cache_insert() [all …]
|
/kernel/linux/linux-5.10/tools/perf/tests/ |
D | hists_output.c | 97 struct rb_node *node; in del_hist_entries() 109 he = rb_entry(node, struct hist_entry, rb_node); in del_hist_entries() 131 struct rb_node *node; in test1() 167 he = rb_entry(node, struct hist_entry, rb_node); in test1() 173 he = rb_entry(node, struct hist_entry, rb_node); in test1() 179 he = rb_entry(node, struct hist_entry, rb_node); in test1() 185 he = rb_entry(node, struct hist_entry, rb_node); in test1() 191 he = rb_entry(node, struct hist_entry, rb_node); in test1() 197 he = rb_entry(node, struct hist_entry, rb_node); in test1() 203 he = rb_entry(node, struct hist_entry, rb_node); in test1() [all …]
|
/kernel/linux/linux-5.10/arch/sh/kernel/ |
D | dwarf.c | 305 struct rb_node **rb_node = &cie_root.rb_node; in dwarf_lookup_cie() local 320 while (*rb_node) { in dwarf_lookup_cie() 323 cie_tmp = rb_entry(*rb_node, struct dwarf_cie, node); in dwarf_lookup_cie() 332 rb_node = &(*rb_node)->rb_left; in dwarf_lookup_cie() 334 rb_node = &(*rb_node)->rb_right; in dwarf_lookup_cie() 349 struct rb_node **rb_node = &fde_root.rb_node; in dwarf_lookup_fde() local 355 while (*rb_node) { in dwarf_lookup_fde() 359 fde_tmp = rb_entry(*rb_node, struct dwarf_fde, node); in dwarf_lookup_fde() 366 rb_node = &(*rb_node)->rb_left; in dwarf_lookup_fde() 372 rb_node = &(*rb_node)->rb_right; in dwarf_lookup_fde() [all …]
|
/kernel/linux/linux-5.10/fs/f2fs/ |
D | extent_cache.c | 33 struct rb_node *node = root->rb_root.rb_node; in __lookup_rb_tree_slow() 37 re = rb_entry(node, struct rb_entry, rb_node); in __lookup_rb_tree_slow() 61 struct rb_node **f2fs_lookup_rb_tree_ext(struct f2fs_sb_info *sbi, in f2fs_lookup_rb_tree_ext() 63 struct rb_node **parent, in f2fs_lookup_rb_tree_ext() 66 struct rb_node **p = &root->rb_root.rb_node; in f2fs_lookup_rb_tree_ext() 71 re = rb_entry(*parent, struct rb_entry, rb_node); in f2fs_lookup_rb_tree_ext() 84 struct rb_node **f2fs_lookup_rb_tree_for_insert(struct f2fs_sb_info *sbi, in f2fs_lookup_rb_tree_for_insert() 86 struct rb_node **parent, in f2fs_lookup_rb_tree_for_insert() 89 struct rb_node **p = &root->rb_root.rb_node; in f2fs_lookup_rb_tree_for_insert() 94 re = rb_entry(*parent, struct rb_entry, rb_node); in f2fs_lookup_rb_tree_for_insert() [all …]
|
/kernel/linux/linux-5.10/fs/ext4/ |
D | extents_status.c | 181 struct rb_node *node; in ext4_es_print_tree() 188 es = rb_entry(node, struct extent_status, rb_node); in ext4_es_print_tree() 213 struct rb_node *node = root->rb_node; in __es_tree_search() 217 es = rb_entry(node, struct extent_status, rb_node); in __es_tree_search() 230 node = rb_next(&es->rb_node); in __es_tree_search() 231 return node ? rb_entry(node, struct extent_status, rb_node) : in __es_tree_search() 263 struct rb_node *node; in __es_find_extent_range() 284 while ((node = rb_next(&es1->rb_node)) != NULL) { in __es_find_extent_range() 285 es1 = rb_entry(node, struct extent_status, rb_node); in __es_find_extent_range() 540 struct rb_node *node; in ext4_es_try_to_merge_left() [all …]
|
/kernel/linux/linux-5.10/security/keys/ |
D | proc.c | 64 static struct rb_node *key_serial_next(struct seq_file *p, struct rb_node *n) in key_serial_next() 81 struct rb_node *n = key_serial_tree.rb_node; in find_ge_key() 129 static inline key_serial_t key_node_serial(struct rb_node *n) in key_node_serial() 137 struct rb_node *n; in proc_keys_next() 155 struct rb_node *_p = v; in proc_keys_show() 252 static struct rb_node *__key_user_next(struct user_namespace *user_ns, struct rb_node *n) in __key_user_next() 263 static struct rb_node *key_user_next(struct user_namespace *user_ns, struct rb_node *n) in key_user_next() 268 static struct rb_node *key_user_first(struct user_namespace *user_ns, struct rb_root *r) in key_user_first() 270 struct rb_node *n = rb_first(r); in key_user_first() 277 struct rb_node *_p; in proc_key_users_start() [all …]
|