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