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