src/libudev/libudev-list.c

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