]>
Commit | Line | Data |
---|---|---|
53e1b683 | 1 | /* SPDX-License-Identifier: LGPL-2.1+ */ |
e345e267 | 2 | |
e345e267 | 3 | #include <errno.h> |
b5efdb8a LP |
4 | #include <stddef.h> |
5 | #include <stdlib.h> | |
e345e267 KS |
6 | #include <string.h> |
7 | ||
b5efdb8a | 8 | #include "alloc-util.h" |
5ea78a39 | 9 | #include "libudev-list-internal.h" |
0a970718 | 10 | #include "memory-util.h" |
e345e267 | 11 | |
ce1d6d7f KS |
12 | /** |
13 | * SECTION:libudev-list | |
14 | * @short_description: list operation | |
15 | * | |
16 | * Libudev list operations. | |
17 | */ | |
18 | ||
dcf557f7 YW |
19 | struct udev_list_node { |
20 | struct udev_list_node *next, *prev; | |
21 | }; | |
22 | ||
1e511322 KS |
23 | /** |
24 | * udev_list_entry: | |
25 | * | |
ce1d6d7f KS |
26 | * Opaque object representing one entry in a list. An entry contains |
27 | * contains a name, and optionally a value. | |
1e511322 | 28 | */ |
0de33a61 | 29 | struct udev_list_entry { |
912541b0 KS |
30 | struct udev_list_node node; |
31 | struct udev_list *list; | |
32 | char *name; | |
33 | char *value; | |
e345e267 KS |
34 | }; |
35 | ||
dcf557f7 YW |
36 | struct udev_list { |
37 | struct udev_list_node node; | |
38 | struct udev_list_entry **entries; | |
39 | unsigned entries_cur; | |
40 | unsigned entries_max; | |
41 | bool unique; | |
42 | }; | |
43 | ||
8958da13 | 44 | /* the list's head points to itself if empty */ |
5ea78a39 | 45 | static void udev_list_node_init(struct udev_list_node *list) { |
912541b0 KS |
46 | list->next = list; |
47 | list->prev = list; | |
e345e267 KS |
48 | } |
49 | ||
5ea78a39 | 50 | static int udev_list_node_is_empty(struct udev_list_node *list) { |
912541b0 | 51 | return list->next == list; |
e345e267 KS |
52 | } |
53 | ||
3feeb77c | 54 | static void udev_list_node_insert_between(struct udev_list_node *new, |
912541b0 | 55 | struct udev_list_node *prev, |
5ea78a39 | 56 | struct udev_list_node *next) { |
912541b0 KS |
57 | next->prev = new; |
58 | new->next = next; | |
59 | new->prev = prev; | |
60 | prev->next = new; | |
e345e267 KS |
61 | } |
62 | ||
5ea78a39 | 63 | static void udev_list_node_remove(struct udev_list_node *entry) { |
912541b0 KS |
64 | struct udev_list_node *prev = entry->prev; |
65 | struct udev_list_node *next = entry->next; | |
e345e267 | 66 | |
912541b0 KS |
67 | next->prev = prev; |
68 | prev->next = next; | |
0de33a61 | 69 | |
912541b0 KS |
70 | entry->prev = NULL; |
71 | entry->next = NULL; | |
e345e267 KS |
72 | } |
73 | ||
0de33a61 | 74 | /* return list entry which embeds this node */ |
a1e92eee | 75 | static struct udev_list_entry *list_node_to_entry(struct udev_list_node *node) { |
b27ee00b | 76 | return container_of(node, struct udev_list_entry, node); |
0de33a61 KS |
77 | } |
78 | ||
dcf557f7 YW |
79 | struct udev_list *udev_list_new(bool unique) { |
80 | struct udev_list *list; | |
81 | ||
82 | list = new(struct udev_list, 1); | |
83 | if (!list) | |
84 | return NULL; | |
85 | ||
86 | *list = (struct udev_list) { | |
87 | .unique = unique, | |
88 | }; | |
89 | ||
912541b0 | 90 | udev_list_node_init(&list->node); |
dcf557f7 YW |
91 | |
92 | return list; | |
0de33a61 KS |
93 | } |
94 | ||
869c9031 | 95 | /* insert entry into a list as the last element */ |
5ea78a39 | 96 | static void udev_list_entry_append(struct udev_list_entry *new, struct udev_list *list) { |
912541b0 KS |
97 | /* inserting before the list head make the node the last node in the list */ |
98 | udev_list_node_insert_between(&new->node, list->node.prev, &list->node); | |
99 | new->list = list; | |
1e78dcbe KS |
100 | } |
101 | ||
0de33a61 | 102 | /* insert entry into a list, before a given existing entry */ |
5ea78a39 | 103 | static void udev_list_entry_insert_before(struct udev_list_entry *new, struct udev_list_entry *entry) { |
912541b0 KS |
104 | udev_list_node_insert_between(&new->node, entry->node.prev, &entry->node); |
105 | new->list = entry->list; | |
0de33a61 | 106 | } |
e345e267 | 107 | |
869c9031 | 108 | /* binary search in sorted array */ |
5ea78a39 | 109 | static int list_search(struct udev_list *list, const char *name) { |
14cb109d | 110 | unsigned first, last; |
912541b0 KS |
111 | |
112 | first = 0; | |
113 | last = list->entries_cur; | |
114 | while (first < last) { | |
14cb109d | 115 | unsigned i; |
912541b0 KS |
116 | int cmp; |
117 | ||
118 | i = (first + last)/2; | |
119 | cmp = strcmp(name, list->entries[i]->name); | |
120 | if (cmp < 0) | |
121 | last = i; | |
122 | else if (cmp > 0) | |
123 | first = i+1; | |
124 | else | |
125 | return i; | |
126 | } | |
127 | ||
128 | /* not found, return negative insertion-index+1 */ | |
129 | return -(first+1); | |
869c9031 KS |
130 | } |
131 | ||
62d74c78 | 132 | struct udev_list_entry *udev_list_entry_add(struct udev_list *list, const char *name, const char *value) { |
912541b0 KS |
133 | struct udev_list_entry *entry; |
134 | int i = 0; | |
135 | ||
136 | if (list->unique) { | |
137 | /* lookup existing name or insertion-index */ | |
138 | i = list_search(list, name); | |
139 | if (i >= 0) { | |
140 | entry = list->entries[i]; | |
141 | ||
912541b0 | 142 | free(entry->value); |
62d74c78 | 143 | if (!value) { |
912541b0 | 144 | entry->value = NULL; |
912541b0 KS |
145 | return entry; |
146 | } | |
147 | entry->value = strdup(value); | |
62d74c78 | 148 | if (!entry->value) |
912541b0 | 149 | return NULL; |
912541b0 KS |
150 | return entry; |
151 | } | |
152 | } | |
153 | ||
154 | /* add new name */ | |
955d98c9 | 155 | entry = new0(struct udev_list_entry, 1); |
62d74c78 | 156 | if (!entry) |
912541b0 | 157 | return NULL; |
6b430fdb | 158 | |
912541b0 | 159 | entry->name = strdup(name); |
62d74c78 | 160 | if (!entry->name) |
6b430fdb ZJS |
161 | return mfree(entry); |
162 | ||
62d74c78 | 163 | if (value) { |
912541b0 | 164 | entry->value = strdup(value); |
62d74c78 | 165 | if (!entry->value) { |
912541b0 | 166 | free(entry->name); |
6b430fdb | 167 | return mfree(entry); |
912541b0 KS |
168 | } |
169 | } | |
170 | ||
171 | if (list->unique) { | |
172 | /* allocate or enlarge sorted array if needed */ | |
173 | if (list->entries_cur >= list->entries_max) { | |
cf2292f5 | 174 | struct udev_list_entry **entries; |
14cb109d | 175 | unsigned add; |
912541b0 KS |
176 | |
177 | add = list->entries_max; | |
178 | if (add < 1) | |
179 | add = 64; | |
62d74c78 LP |
180 | entries = reallocarray(list->entries, list->entries_max + add, sizeof(struct udev_list_entry *)); |
181 | if (!entries) { | |
912541b0 KS |
182 | free(entry->name); |
183 | free(entry->value); | |
6b430fdb | 184 | return mfree(entry); |
912541b0 | 185 | } |
cf2292f5 | 186 | list->entries = entries; |
912541b0 KS |
187 | list->entries_max += add; |
188 | } | |
189 | ||
190 | /* the negative i returned the insertion index */ | |
191 | i = (-i)-1; | |
192 | ||
193 | /* insert into sorted list */ | |
14cb109d | 194 | if ((unsigned)i < list->entries_cur) |
912541b0 KS |
195 | udev_list_entry_insert_before(entry, list->entries[i]); |
196 | else | |
197 | udev_list_entry_append(entry, list); | |
198 | ||
199 | /* insert into sorted array */ | |
200 | memmove(&list->entries[i+1], &list->entries[i], | |
201 | (list->entries_cur - i) * sizeof(struct udev_list_entry *)); | |
202 | list->entries[i] = entry; | |
203 | list->entries_cur++; | |
62d74c78 | 204 | } else |
912541b0 | 205 | udev_list_entry_append(entry, list); |
912541b0 | 206 | |
912541b0 | 207 | return entry; |
e345e267 KS |
208 | } |
209 | ||
5ea78a39 | 210 | static void udev_list_entry_delete(struct udev_list_entry *entry) { |
f921b457 | 211 | if (entry->list->entries) { |
912541b0 KS |
212 | int i; |
213 | struct udev_list *list = entry->list; | |
214 | ||
215 | /* remove entry from sorted array */ | |
216 | i = list_search(list, entry->name); | |
217 | if (i >= 0) { | |
218 | memmove(&list->entries[i], &list->entries[i+1], | |
219 | ((list->entries_cur-1) - i) * sizeof(struct udev_list_entry *)); | |
220 | list->entries_cur--; | |
221 | } | |
222 | } | |
223 | ||
224 | udev_list_node_remove(&entry->node); | |
225 | free(entry->name); | |
226 | free(entry->value); | |
227 | free(entry); | |
e345e267 KS |
228 | } |
229 | ||
5ea78a39 YW |
230 | #define udev_list_entry_foreach_safe(entry, tmp, first) \ |
231 | for (entry = first, tmp = udev_list_entry_get_next(entry); \ | |
232 | entry; \ | |
233 | entry = tmp, tmp = udev_list_entry_get_next(tmp)) | |
234 | ||
235 | void udev_list_cleanup(struct udev_list *list) { | |
dcf557f7 | 236 | struct udev_list_entry *entry_loop, *entry_tmp; |
912541b0 | 237 | |
a1e58e8e | 238 | list->entries = mfree(list->entries); |
912541b0 KS |
239 | list->entries_cur = 0; |
240 | list->entries_max = 0; | |
241 | udev_list_entry_foreach_safe(entry_loop, entry_tmp, udev_list_get_entry(list)) | |
242 | udev_list_entry_delete(entry_loop); | |
be7f7f57 | 243 | } |
dcf557f7 YW |
244 | |
245 | struct udev_list *udev_list_free(struct udev_list *list) { | |
246 | if (!list) | |
247 | return NULL; | |
248 | ||
249 | udev_list_cleanup(list); | |
250 | ||
251 | return mfree(list); | |
252 | } | |
be7f7f57 | 253 | |
5ea78a39 | 254 | struct udev_list_entry *udev_list_get_entry(struct udev_list *list) { |
912541b0 KS |
255 | if (udev_list_node_is_empty(&list->node)) |
256 | return NULL; | |
257 | return list_node_to_entry(list->node.next); | |
e345e267 KS |
258 | } |
259 | ||
1e511322 KS |
260 | /** |
261 | * udev_list_entry_get_next: | |
262 | * @list_entry: current entry | |
263 | * | |
21dbe43a KS |
264 | * Get the next entry from the list. |
265 | * | |
266 | * Returns: udev_list_entry, #NULL if no more entries are available. | |
1e511322 | 267 | */ |
5ea78a39 | 268 | _public_ struct udev_list_entry *udev_list_entry_get_next(struct udev_list_entry *list_entry) { |
912541b0 KS |
269 | struct udev_list_node *next; |
270 | ||
f921b457 | 271 | if (!list_entry) |
912541b0 KS |
272 | return NULL; |
273 | next = list_entry->node.next; | |
274 | /* empty list or no more entries */ | |
275 | if (next == &list_entry->list->node) | |
276 | return NULL; | |
277 | return list_node_to_entry(next); | |
e345e267 KS |
278 | } |
279 | ||
1e511322 KS |
280 | /** |
281 | * udev_list_entry_get_by_name: | |
282 | * @list_entry: current entry | |
283 | * @name: name string to match | |
284 | * | |
21dbe43a KS |
285 | * Lookup an entry in the list with a certain name. |
286 | * | |
287 | * Returns: udev_list_entry, #NULL if no matching entry is found. | |
1e511322 | 288 | */ |
5ea78a39 | 289 | _public_ struct udev_list_entry *udev_list_entry_get_by_name(struct udev_list_entry *list_entry, const char *name) { |
912541b0 | 290 | int i; |
bc8184ed | 291 | |
f921b457 | 292 | if (!list_entry) |
912541b0 | 293 | return NULL; |
869c9031 | 294 | |
912541b0 KS |
295 | if (!list_entry->list->unique) |
296 | return NULL; | |
869c9031 | 297 | |
912541b0 KS |
298 | i = list_search(list_entry->list, name); |
299 | if (i < 0) | |
300 | return NULL; | |
301 | return list_entry->list->entries[i]; | |
bc8184ed KS |
302 | } |
303 | ||
1e511322 KS |
304 | /** |
305 | * udev_list_entry_get_name: | |
306 | * @list_entry: current entry | |
307 | * | |
21dbe43a KS |
308 | * Get the name of a list entry. |
309 | * | |
1e511322 KS |
310 | * Returns: the name string of this entry. |
311 | */ | |
5ea78a39 | 312 | _public_ const char *udev_list_entry_get_name(struct udev_list_entry *list_entry) { |
f921b457 | 313 | if (!list_entry) |
912541b0 KS |
314 | return NULL; |
315 | return list_entry->name; | |
e345e267 KS |
316 | } |
317 | ||
1e511322 KS |
318 | /** |
319 | * udev_list_entry_get_value: | |
320 | * @list_entry: current entry | |
321 | * | |
21dbe43a KS |
322 | * Get the value of list entry. |
323 | * | |
1e511322 KS |
324 | * Returns: the value string of this entry. |
325 | */ | |
5ea78a39 | 326 | _public_ const char *udev_list_entry_get_value(struct udev_list_entry *list_entry) { |
f921b457 | 327 | if (!list_entry) |
912541b0 KS |
328 | return NULL; |
329 | return list_entry->value; | |
e345e267 | 330 | } |