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                         unsigned int add;
 189
 190                         add = list->entries_max;
 191                         if (add < 1)
 192                                 add = 64;
 193                         list->entries = realloc(list->entries, (list->entries_max + add) * sizeof(struct udev_list_entry *));
 194                         if (list->entries == NULL) {
 195                                 free(entry->name);
 196                                 free(entry->value);
 197                                 free(entry);
 198                                 return NULL;
 199                         }
 200                         list->entries_max += add;
 201                 }
 202
 203                 /* the negative i returned the insertion index */
 204                 i = (-i)-1;
 205
 206                 /* insert into sorted list */
 207                 if ((unsigned int)i < list->entries_cur)
 208                         udev_list_entry_insert_before(entry, list->entries[i]);
 209                 else
 210                         udev_list_entry_append(entry, list);
 211
 212                 /* insert into sorted array */
 213                 memmove(&list->entries[i+1], &list->entries[i],
 214                         (list->entries_cur - i) * sizeof(struct udev_list_entry *));
 215                 list->entries[i] = entry;
 216                 list->entries_cur++;
 217         } else {
 218                 udev_list_entry_append(entry, list);
 219         }
 220
 221         return entry;
 222 }
 223
 224 void udev_list_entry_delete(struct udev_list_entry *entry)
 225 {
 226         if (entry->list->entries != NULL) {
 227                 int i;
 228                 struct udev_list *list = entry->list;
 229
 230                 /* remove entry from sorted array */
 231                 i = list_search(list, entry->name);
 232                 if (i >= 0) {
 233                         memmove(&list->entries[i], &list->entries[i+1],
 234                                 ((list->entries_cur-1) - i) * sizeof(struct udev_list_entry *));
 235                         list->entries_cur--;
 236                 }
 237         }
 238
 239         udev_list_node_remove(&entry->node);
 240         free(entry->name);
 241         free(entry->value);
 242         free(entry);
 243 }
 244
 245 void udev_list_cleanup(struct udev_list *list)
 246 {
 247         struct udev_list_entry *entry_loop;
 248         struct udev_list_entry *entry_tmp;
 249
 250         free(list->entries);
 251         list->entries = NULL;
 252         list->entries_cur = 0;
 253         list->entries_max = 0;
 254         udev_list_entry_foreach_safe(entry_loop, entry_tmp, udev_list_get_entry(list))
 255                 udev_list_entry_delete(entry_loop);
 256 }
 257
 258 struct udev_list_entry *udev_list_get_entry(struct udev_list *list)
 259 {
 260         if (udev_list_node_is_empty(&list->node))
 261                 return NULL;
 262         return list_node_to_entry(list->node.next);
 263 }
 264
 265 /**
 266  * udev_list_entry_get_next:
 267  * @list_entry: current entry
 268  *
 269  * Get the next entry from the list.
 270  *
 271  * Returns: udev_list_entry, #NULL if no more entries are available.
 272  */
 273 _public_ struct udev_list_entry *udev_list_entry_get_next(struct udev_list_entry *list_entry)
 274 {
 275         struct udev_list_node *next;
 276
 277         if (list_entry == NULL)
 278                 return NULL;
 279         next = list_entry->node.next;
 280         /* empty list or no more entries */
 281         if (next == &list_entry->list->node)
 282                 return NULL;
 283         return list_node_to_entry(next);
 284 }
 285
 286 /**
 287  * udev_list_entry_get_by_name:
 288  * @list_entry: current entry
 289  * @name: name string to match
 290  *
 291  * Lookup an entry in the list with a certain name.
 292  *
 293  * Returns: udev_list_entry, #NULL if no matching entry is found.
 294  */
 295 _public_ struct udev_list_entry *udev_list_entry_get_by_name(struct udev_list_entry *list_entry, const char *name)
 296 {
 297         int i;
 298
 299         if (list_entry == NULL)
 300                 return NULL;
 301
 302         if (!list_entry->list->unique)
 303                 return NULL;
 304
 305         i = list_search(list_entry->list, name);
 306         if (i < 0)
 307                 return NULL;
 308         return list_entry->list->entries[i];
 309 }
 310
 311 /**
 312  * udev_list_entry_get_name:
 313  * @list_entry: current entry
 314  *
 315  * Get the name of a list entry.
 316  *
 317  * Returns: the name string of this entry.
 318  */
 319 _public_ const char *udev_list_entry_get_name(struct udev_list_entry *list_entry)
 320 {
 321         if (list_entry == NULL)
 322                 return NULL;
 323         return list_entry->name;
 324 }
 325
 326 /**
 327  * udev_list_entry_get_value:
 328  * @list_entry: current entry
 329  *
 330  * Get the value of list entry.
 331  *
 332  * Returns: the value string of this entry.
 333  */
 334 _public_ const char *udev_list_entry_get_value(struct udev_list_entry *list_entry)
 335 {
 336         if (list_entry == NULL)
 337                 return NULL;
 338         return list_entry->value;
 339 }
 340
 341 int udev_list_entry_get_num(struct udev_list_entry *list_entry)
 342 {
 343         if (list_entry == NULL)
 344                 return -EINVAL;
 345         return list_entry->num;
 346 }
 347
 348 void udev_list_entry_set_num(struct udev_list_entry *list_entry, int num)
 349 {
 350         if (list_entry == NULL)
 351                 return;
 352         list_entry->num = num;
 353 }