src/libudev/libudev-list.c

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