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