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