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