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