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