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 */
43struct 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 */
52void udev_list_node_init(struct udev_list_node *list)
53{
54        list->next = list;
55        list->prev = list;
56}
57
58int udev_list_node_is_empty(struct udev_list_node *list)
59{
60        return list->next == list;
61}
62
63static 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
73void 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
78void 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 */
91static 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
96void udev_list_init(struct udev *udev, struct udev_list *list, bool unique)
97{
98        memzero(list, 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  */
105static 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 */
113static 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 */
120static 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
144struct 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 = new0(struct udev_list_entry, 1);
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
226void 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
247void 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
260struct 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
343int 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
350void 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}
356