libudev: hide definition of struct udev_list from other libudev components
[thirdparty/systemd.git] / src / libudev / libudev-list.c
1 /* SPDX-License-Identifier: LGPL-2.1+ */
2
3 #include <errno.h>
4 #include <stddef.h>
5 #include <stdlib.h>
6 #include <string.h>
7
8 #include "alloc-util.h"
9 #include "libudev-list-internal.h"
10 #include "memory-util.h"
11
12 /**
13  * SECTION:libudev-list
14  * @short_description: list operation
15  *
16  * Libudev list operations.
17  */
18
19 struct udev_list_node {
20         struct udev_list_node *next, *prev;
21 };
22
23 /**
24  * udev_list_entry:
25  *
26  * Opaque object representing one entry in a list. An entry contains
27  * contains a name, and optionally a value.
28  */
29 struct udev_list_entry {
30         struct udev_list_node node;
31         struct udev_list *list;
32         char *name;
33         char *value;
34 };
35
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
44 /* the list's head points to itself if empty */
45 static void udev_list_node_init(struct udev_list_node *list) {
46         list->next = list;
47         list->prev = list;
48 }
49
50 static int udev_list_node_is_empty(struct udev_list_node *list) {
51         return list->next == list;
52 }
53
54 static void udev_list_node_insert_between(struct udev_list_node *new,
55                                           struct udev_list_node *prev,
56                                           struct udev_list_node *next) {
57         next->prev = new;
58         new->next = next;
59         new->prev = prev;
60         prev->next = new;
61 }
62
63 static void udev_list_node_remove(struct udev_list_node *entry) {
64         struct udev_list_node *prev = entry->prev;
65         struct udev_list_node *next = entry->next;
66
67         next->prev = prev;
68         prev->next = next;
69
70         entry->prev = NULL;
71         entry->next = NULL;
72 }
73
74 /* return list entry which embeds this node */
75 static struct udev_list_entry *list_node_to_entry(struct udev_list_node *node) {
76         return container_of(node, struct udev_list_entry, node);
77 }
78
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
90         udev_list_node_init(&list->node);
91
92         return list;
93 }
94
95 /* insert entry into a list as the last element  */
96 static void udev_list_entry_append(struct udev_list_entry *new, struct udev_list *list) {
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;
100 }
101
102 /* insert entry into a list, before a given existing entry */
103 static void udev_list_entry_insert_before(struct udev_list_entry *new, struct udev_list_entry *entry) {
104         udev_list_node_insert_between(&new->node, entry->node.prev, &entry->node);
105         new->list = entry->list;
106 }
107
108 /* binary search in sorted array */
109 static int list_search(struct udev_list *list, const char *name) {
110         unsigned first, last;
111
112         first = 0;
113         last = list->entries_cur;
114         while (first < last) {
115                 unsigned i;
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);
130 }
131
132 struct udev_list_entry *udev_list_entry_add(struct udev_list *list, const char *name, const char *value) {
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
142                         free(entry->value);
143                         if (!value) {
144                                 entry->value = NULL;
145                                 return entry;
146                         }
147                         entry->value = strdup(value);
148                         if (!entry->value)
149                                 return NULL;
150                         return entry;
151                 }
152         }
153
154         /* add new name */
155         entry = new0(struct udev_list_entry, 1);
156         if (!entry)
157                 return NULL;
158
159         entry->name = strdup(name);
160         if (!entry->name)
161                 return mfree(entry);
162
163         if (value) {
164                 entry->value = strdup(value);
165                 if (!entry->value) {
166                         free(entry->name);
167                         return mfree(entry);
168                 }
169         }
170
171         if (list->unique) {
172                 /* allocate or enlarge sorted array if needed */
173                 if (list->entries_cur >= list->entries_max) {
174                         struct udev_list_entry **entries;
175                         unsigned add;
176
177                         add = list->entries_max;
178                         if (add < 1)
179                                 add = 64;
180                         entries = reallocarray(list->entries, list->entries_max + add, sizeof(struct udev_list_entry *));
181                         if (!entries) {
182                                 free(entry->name);
183                                 free(entry->value);
184                                 return mfree(entry);
185                         }
186                         list->entries = entries;
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 */
194                 if ((unsigned)i < list->entries_cur)
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++;
204         } else
205                 udev_list_entry_append(entry, list);
206
207         return entry;
208 }
209
210 static void udev_list_entry_delete(struct udev_list_entry *entry) {
211         if (entry->list->entries) {
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);
228 }
229
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) {
236         struct udev_list_entry *entry_loop, *entry_tmp;
237
238         list->entries = mfree(list->entries);
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);
243 }
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 }
253
254 struct udev_list_entry *udev_list_get_entry(struct udev_list *list) {
255         if (udev_list_node_is_empty(&list->node))
256                 return NULL;
257         return list_node_to_entry(list->node.next);
258 }
259
260 /**
261  * udev_list_entry_get_next:
262  * @list_entry: current entry
263  *
264  * Get the next entry from the list.
265  *
266  * Returns: udev_list_entry, #NULL if no more entries are available.
267  */
268 _public_ struct udev_list_entry *udev_list_entry_get_next(struct udev_list_entry *list_entry) {
269         struct udev_list_node *next;
270
271         if (!list_entry)
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);
278 }
279
280 /**
281  * udev_list_entry_get_by_name:
282  * @list_entry: current entry
283  * @name: name string to match
284  *
285  * Lookup an entry in the list with a certain name.
286  *
287  * Returns: udev_list_entry, #NULL if no matching entry is found.
288  */
289 _public_ struct udev_list_entry *udev_list_entry_get_by_name(struct udev_list_entry *list_entry, const char *name) {
290         int i;
291
292         if (!list_entry)
293                 return NULL;
294
295         if (!list_entry->list->unique)
296                 return NULL;
297
298         i = list_search(list_entry->list, name);
299         if (i < 0)
300                 return NULL;
301         return list_entry->list->entries[i];
302 }
303
304 /**
305  * udev_list_entry_get_name:
306  * @list_entry: current entry
307  *
308  * Get the name of a list entry.
309  *
310  * Returns: the name string of this entry.
311  */
312 _public_ const char *udev_list_entry_get_name(struct udev_list_entry *list_entry) {
313         if (!list_entry)
314                 return NULL;
315         return list_entry->name;
316 }
317
318 /**
319  * udev_list_entry_get_value:
320  * @list_entry: current entry
321  *
322  * Get the value of list entry.
323  *
324  * Returns: the value string of this entry.
325  */
326 _public_ const char *udev_list_entry_get_value(struct udev_list_entry *list_entry) {
327         if (!list_entry)
328                 return NULL;
329         return list_entry->value;
330 }