| /linux/include/linux/ |
| H A D | rbtree.h | 26 #define rb_parent(r) ((struct rb_node *)((r)->__rb_parent_color & ~3))
30 #define RB_EMPTY_ROOT(root) (READ_ONCE((root)->rb_node) == NULL)
39 extern void rb_insert_color(struct rb_node *, struct rb_root *);
40 extern void rb_erase(struct rb_node *, struct rb_root *);
44 extern struct rb_node *rb_next(const struct rb_node *);
45 extern struct rb_node *rb_prev(const struct rb_node *);
46 extern struct rb_node *rb_first(const struct rb_root *);
47 extern struct rb_node *rb_las
166 rb_add_cached(struct rb_node * node,struct rb_root_cached * tree,bool (* less)(struct rb_node *,const struct rb_node *)) rb_add_cached() argument
196 rb_add(struct rb_node * node,struct rb_root * tree,bool (* less)(struct rb_node *,const struct rb_node *)) rb_add() argument
261 rb_find_add(struct rb_node * node,struct rb_root * tree,int (* cmp)(struct rb_node *,const struct rb_node *)) rb_find_add() argument
297 rb_find_add_rcu(struct rb_node * node,struct rb_root * tree,int (* cmp)(struct rb_node *,const struct rb_node *)) rb_find_add_rcu() argument
330 rb_find(const void * key,const struct rb_root * tree,int (* cmp)(const void * key,const struct rb_node *)) rb_find() argument
361 rb_find_rcu(const void * key,const struct rb_root * tree,int (* cmp)(const void * key,const struct rb_node *)) rb_find_rcu() argument
389 rb_find_first(const void * key,const struct rb_root * tree,int (* cmp)(const void * key,const struct rb_node *)) rb_find_first() argument
419 rb_next_match(const void * key,struct rb_node * node,int (* cmp)(const void * key,const struct rb_node *)) rb_next_match() argument
[all...] |
| H A 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 *nod
65 rb_add_augmented_cached(struct rb_node * node,struct rb_root_cached * tree,bool (* less)(struct rb_node *,const struct rb_node *),const struct rb_augment_callbacks * augment) rb_add_augmented_cached() argument
[all...] |
| H A D | rbtree_types.h | 5 struct rb_node { struct
7 struct rb_node *rb_right; argument
8 struct rb_node *rb_left; argument
13 struct rb_node *rb_node; member
28 struct rb_node *rb_leftmost;
|
| /linux/tools/include/linux/ |
| H A 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_nex
179 rb_add_cached(struct rb_node * node,struct rb_root_cached * tree,bool (* less)(struct rb_node *,const struct rb_node *)) rb_add_cached() argument
207 rb_add(struct rb_node * node,struct rb_root * tree,bool (* less)(struct rb_node *,const struct rb_node *)) rb_add() argument
235 rb_find_add(struct rb_node * node,struct rb_root * tree,int (* cmp)(struct rb_node *,const struct rb_node *)) rb_find_add() argument
268 rb_find(const void * key,const struct rb_root * tree,int (* cmp)(const void * key,const struct rb_node *)) rb_find() argument
296 rb_find_first(const void * key,const struct rb_root * tree,int (* cmp)(const void * key,const struct rb_node *)) rb_find_first() argument
326 rb_next_match(const void * key,struct rb_node * node,int (* cmp)(const void * key,const struct rb_node *)) rb_next_match() argument
[all...] |
| H A 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 *nod
[all...] |
| /linux/tools/lib/ |
| H A 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 *ne in __rb_insert()
[all...] |
| /linux/lib/ |
| H A 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 *ne in __rb_insert()
[all...] |
| /linux/tools/perf/util/ |
| H A 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, struc in intlist__node_cmp()
69 struct rb_node *rb_node; __intlist__findnew() local
143 struct rb_node *rb_node; intlist__entry() local
[all...] |
| H A 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, struc in strlist__node_cmp()
103 struct rb_node *rb_node = rblist__find(&slist->rblist, entry); strlist__find() local
201 struct rb_node *rb_node; strlist__entry() local
[all...] |
| H A 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()
[all...] |
| H A D | rblist.h | 11 * struct rb_node rb_node;
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__findne
[all...] |
| H A 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()
121 struct rb_node ** in mem2node__node()
[all...] |
| H A 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()
|
| H A 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()
|
| /linux/Documentation/translations/zh_CN/core-api/ |
| H A D | rbtree.rst | 60 struct rb_node node;
81 struct rb_node *node = root->rb_node;
112 struct rb_node **new = &(root->rb_node), *parent = NULL;
140 void rb_erase(struct rb_node *victim, struct rb_root *tree);
153 void rb_replace_node(struct rb_node *old, struct rb_node *new,
165 struct rb_node *rb_first(struct rb_root *tree);
166 struct rb_node *rb_las
[all...] |
| /linux/fs/btrfs/ |
| H A D | misc.h | 67 struct rb_node rb_node; member
71 static inline struct rb_node *rb_simple_search(const struct rb_root *root, u64 bytenr) in rb_simple_search()
73 struct rb_node *node = root->rb_node; in rb_simple_search()
77 entry = rb_entry(node, struct rb_simple_node, rb_node); in rb_simple_search()
95 * Return the rb_node that start at or after @bytenr. If there is no entry at
98 static inline struct rb_node *rb_simple_search_first(const struct rb_root *root, in rb_simple_search_first()
101 struct rb_node *node = root->rb_node, *re in rb_simple_search_first()
[all...] |
| H A D | extent_map.c | 51 RB_CLEAR_NODE(&em->rb_node); in btrfs_alloc_extent_map()
84 rb_erase(&em->rb_node, &inode->extent_tree.root); in remove_em()
85 RB_CLEAR_NODE(&em->rb_node); in remove_em()
93 struct rb_node **p = &root->rb_node; in tree_insert()
94 struct rb_node *parent = NULL; in tree_insert()
96 struct rb_node *orig_parent = NULL; in tree_insert()
101 entry = rb_entry(parent, struct extent_map, rb_node); in tree_insert()
114 entry = rb_entry(parent, struct extent_map, rb_node); in tree_insert()
121 entry = rb_entry(parent, struct extent_map, rb_node); in tree_insert()
515 struct rb_node *rb_node; lookup_extent_mapping() local
[all...] |
| H A D | ordered-data.c | 36 static struct rb_node *tree_insert(struct rb_root *root, u64 file_offset, in tree_insert()
37 struct rb_node *node) in tree_insert()
39 struct rb_node **p = &root->rb_node; in tree_insert()
40 struct rb_node *parent = NULL; in tree_insert()
45 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()
[all...] |
| /linux/arch/powerpc/kernel/ |
| H A 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 *paren in eeh_addr_cache_insert()
[all...] |
| /linux/tools/perf/tests/ |
| H A D | hists_output.c | 100 struct rb_node *node; in del_hist_entries()
112 he = rb_entry(node, struct hist_entry, rb_node); in del_hist_entries()
144 struct rb_node *node; in test1()
180 he = rb_entry(node, struct hist_entry, rb_node); in test1()
186 he = rb_entry(node, struct hist_entry, rb_node); in test1()
192 he = rb_entry(node, struct hist_entry, rb_node); in test1()
198 he = rb_entry(node, struct hist_entry, rb_node); in test1()
204 he = rb_entry(node, struct hist_entry, rb_node); in test1()
210 he = rb_entry(node, struct hist_entry, rb_node); in test1()
216 he = rb_entry(node, struct hist_entry, rb_node); in test1()
[all...] |
| /linux/arch/sh/kernel/ |
| H A 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_nod in dwarf_lookup_fde() local
738 struct rb_node **rb_node = &cie_root.rb_node; dwarf_parse_cie() local
869 struct rb_node **rb_node = &fde_root.rb_node; dwarf_parse_fde() local
[all...] |
| /linux/net/bridge/ |
| H A D | br_multicast_eht.c | 47 struct rb_node *node = pg->eht_host_tree.rb_node; in br_multicast_eht_host_lookup()
54 rb_node); in br_multicast_eht_host_lookup()
83 struct rb_node *node = eht_set->entry_tree.rb_node; in br_multicast_eht_set_entry_lookup()
90 rb_node); in br_multicast_eht_set_entry_lookup()
107 struct rb_node *node = pg->eht_set_tree.rb_node; in br_multicast_eht_set_lookup()
114 rb_node); in br_multicast_eht_set_lookup()
133 rb_erase(&eht_host->rb_node, in __eht_destroy_host()
[all...] |
| /linux/fs/ext4/ |
| H A D | extents_status.c | 213 struct rb_node *node; in ext4_es_print_tree()
220 es = rb_entry(node, struct extent_status, rb_node); in ext4_es_print_tree()
245 struct rb_node *node = root->rb_node; in __es_tree_search()
249 es = rb_entry(node, struct extent_status, rb_node); in __es_tree_search()
262 node = rb_next(&es->rb_node); in __es_tree_search()
263 return node ? rb_entry(node, struct extent_status, rb_node) : in __es_tree_search()
295 struct rb_node *node; in __es_find_extent_range()
316 while ((node = rb_next(&es1->rb_node)) != NULL) { in __es_find_extent_range()
317 es1 = rb_entry(node, struct extent_status, rb_node); in __es_find_extent_range()
[all...] |
| /linux/security/keys/ |
| H A 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_nex
[all...] |
| /linux/net/ipv4/ |
| H A D | inetpeer.c | 49 * rb_node: pool lock
93 struct rb_node **parent_p, in lookup()
94 struct rb_node ***pp_p) in lookup()
96 struct rb_node **pp, *parent, *next; in lookup()
100 pp = &base->rb_root.rb_node; in lookup()
109 p = rb_entry(parent, struct inet_peer, rb_node); in lookup()
163 rb_erase(&p->rb_node, &base->rb_root); in inet_peer_gc()
175 struct rb_node **pp, *parent; in inet_getpeer()
210 rb_link_node(&p->rb_node, parent, pp); in inet_getpeer()
211 rb_insert_color(&p->rb_node, in inet_getpeer()
[all...] |