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