1 | // SPDX-License-Identifier: GPL-2.0-only |
2 | /* |
3 | * Based on strlist.c by: |
4 | * (c) 2009 Arnaldo Carvalho de Melo <acme@redhat.com> |
5 | */ |
6 | |
7 | #include <errno.h> |
8 | #include <stdio.h> |
9 | #include <stdlib.h> |
10 | |
11 | #include "rblist.h" |
12 | |
13 | int rblist__add_node(struct rblist *rblist, const void *new_entry) |
14 | { |
15 | struct rb_node **p = &rblist->entries.rb_root.rb_node; |
16 | struct rb_node *parent = NULL, *new_node; |
17 | bool leftmost = true; |
18 | |
19 | while (*p != NULL) { |
20 | int rc; |
21 | |
22 | parent = *p; |
23 | |
24 | rc = rblist->node_cmp(parent, new_entry); |
25 | if (rc > 0) |
26 | p = &(*p)->rb_left; |
27 | else if (rc < 0) { |
28 | p = &(*p)->rb_right; |
29 | leftmost = false; |
30 | } |
31 | else |
32 | return -EEXIST; |
33 | } |
34 | |
35 | new_node = rblist->node_new(rblist, new_entry); |
36 | if (new_node == NULL) |
37 | return -ENOMEM; |
38 | |
39 | rb_link_node(node: new_node, parent, rb_link: p); |
40 | rb_insert_color_cached(node: new_node, root: &rblist->entries, leftmost); |
41 | ++rblist->nr_entries; |
42 | |
43 | return 0; |
44 | } |
45 | |
46 | void rblist__remove_node(struct rblist *rblist, struct rb_node *rb_node) |
47 | { |
48 | rb_erase_cached(node: rb_node, root: &rblist->entries); |
49 | --rblist->nr_entries; |
50 | rblist->node_delete(rblist, rb_node); |
51 | } |
52 | |
53 | static struct rb_node *__rblist__findnew(struct rblist *rblist, |
54 | const void *entry, |
55 | bool create) |
56 | { |
57 | struct rb_node **p = &rblist->entries.rb_root.rb_node; |
58 | struct rb_node *parent = NULL, *new_node = NULL; |
59 | bool leftmost = true; |
60 | |
61 | while (*p != NULL) { |
62 | int rc; |
63 | |
64 | parent = *p; |
65 | |
66 | rc = rblist->node_cmp(parent, entry); |
67 | if (rc > 0) |
68 | p = &(*p)->rb_left; |
69 | else if (rc < 0) { |
70 | p = &(*p)->rb_right; |
71 | leftmost = false; |
72 | } |
73 | else |
74 | return parent; |
75 | } |
76 | |
77 | if (create) { |
78 | new_node = rblist->node_new(rblist, entry); |
79 | if (new_node) { |
80 | rb_link_node(node: new_node, parent, rb_link: p); |
81 | rb_insert_color_cached(node: new_node, |
82 | root: &rblist->entries, leftmost); |
83 | ++rblist->nr_entries; |
84 | } |
85 | } |
86 | |
87 | return new_node; |
88 | } |
89 | |
90 | struct rb_node *rblist__find(struct rblist *rblist, const void *entry) |
91 | { |
92 | return __rblist__findnew(rblist, entry, create: false); |
93 | } |
94 | |
95 | struct rb_node *rblist__findnew(struct rblist *rblist, const void *entry) |
96 | { |
97 | return __rblist__findnew(rblist, entry, create: true); |
98 | } |
99 | |
100 | void rblist__init(struct rblist *rblist) |
101 | { |
102 | if (rblist != NULL) { |
103 | rblist->entries = RB_ROOT_CACHED; |
104 | rblist->nr_entries = 0; |
105 | } |
106 | |
107 | return; |
108 | } |
109 | |
110 | void rblist__exit(struct rblist *rblist) |
111 | { |
112 | struct rb_node *pos, *next = rb_first_cached(&rblist->entries); |
113 | |
114 | while (next) { |
115 | pos = next; |
116 | next = rb_next(pos); |
117 | rblist__remove_node(rblist, rb_node: pos); |
118 | } |
119 | } |
120 | |
121 | void rblist__delete(struct rblist *rblist) |
122 | { |
123 | if (rblist != NULL) { |
124 | rblist__exit(rblist); |
125 | free(rblist); |
126 | } |
127 | } |
128 | |
129 | struct rb_node *rblist__entry(const struct rblist *rblist, unsigned int idx) |
130 | { |
131 | struct rb_node *node; |
132 | |
133 | for (node = rb_first_cached(&rblist->entries); node; |
134 | node = rb_next(node)) { |
135 | if (!idx--) |
136 | return node; |
137 | } |
138 | |
139 | return NULL; |
140 | } |
141 | |