src/libudev/libudev-list.c

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