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 }