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