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 {
 145         struct udev_list_entry *entry;
 146         int i = 0;
 147
 148         if (list->unique) {
 149                 /* lookup existing name or insertion-index */
 150                 i = list_search(list, name);
 151                 if (i >= 0) {
 152                         entry = list->entries[i];
 153
 154                         free(entry->value);
 155                         if (value == NULL) {
 156                                 entry->value = NULL;
 157                                 return entry;
 158                         }
 159                         entry->value = strdup(value);
 160                         if (entry->value == NULL)
 161                                 return NULL;
 162                         return entry;
 163                 }
 164         }
 165
 166         /* add new name */
 167         entry = new0(struct udev_list_entry, 1);
 168         if (entry == NULL)
 169                 return NULL;
 170
 171         entry->name = strdup(name);
 172         if (entry->name == NULL)
 173                 return mfree(entry);
 174
 175         if (value != NULL) {
 176                 entry->value = strdup(value);
 177                 if (entry->value == NULL) {
 178                         free(entry->name);
 179                         return mfree(entry);
 180                 }
 181         }
 182
 183         if (list->unique) {
 184                 /* allocate or enlarge sorted array if needed */
 185                 if (list->entries_cur >= list->entries_max) {
 186                         struct udev_list_entry **entries;
 187                         unsigned int add;
 188
 189                         add = list->entries_max;
 190                         if (add < 1)
 191                                 add = 64;
 192                         entries = realloc(list->entries, (list->entries_max + add) * sizeof(struct udev_list_entry *));
 193                         if (entries == NULL) {
 194                                 free(entry->name);
 195                                 free(entry->value);
 196                                 return mfree(entry);
 197                         }
 198                         list->entries = entries;
 199                         list->entries_max += add;
 200                 }
 201
 202                 /* the negative i returned the insertion index */
 203                 i = (-i)-1;
 204
 205                 /* insert into sorted list */
 206                 if ((unsigned int)i < list->entries_cur)
 207                         udev_list_entry_insert_before(entry, list->entries[i]);
 208                 else
 209                         udev_list_entry_append(entry, list);
 210
 211                 /* insert into sorted array */
 212                 memmove(&list->entries[i+1], &list->entries[i],
 213                         (list->entries_cur - i) * sizeof(struct udev_list_entry *));
 214                 list->entries[i] = entry;
 215                 list->entries_cur++;
 216         } else {
 217                 udev_list_entry_append(entry, list);
 218         }
 219
 220         return entry;
 221 }
 222
 223 void udev_list_entry_delete(struct udev_list_entry *entry)
 224 {
 225         if (entry->list->entries != NULL) {
 226                 int i;
 227                 struct udev_list *list = entry->list;
 228
 229                 /* remove entry from sorted array */
 230                 i = list_search(list, entry->name);
 231                 if (i >= 0) {
 232                         memmove(&list->entries[i], &list->entries[i+1],
 233                                 ((list->entries_cur-1) - i) * sizeof(struct udev_list_entry *));
 234                         list->entries_cur--;
 235                 }
 236         }
 237
 238         udev_list_node_remove(&entry->node);
 239         free(entry->name);
 240         free(entry->value);
 241         free(entry);
 242 }
 243
 244 void udev_list_cleanup(struct udev_list *list)
 245 {
 246         struct udev_list_entry *entry_loop;
 247         struct udev_list_entry *entry_tmp;
 248
 249         list->entries = mfree(list->entries);
 250         list->entries_cur = 0;
 251         list->entries_max = 0;
 252         udev_list_entry_foreach_safe(entry_loop, entry_tmp, udev_list_get_entry(list))
 253                 udev_list_entry_delete(entry_loop);
 254 }
 255
 256 struct udev_list_entry *udev_list_get_entry(struct udev_list *list)
 257 {
 258         if (udev_list_node_is_empty(&list->node))
 259                 return NULL;
 260         return list_node_to_entry(list->node.next);
 261 }
 262
 263 /**
 264  * udev_list_entry_get_next:
 265  * @list_entry: current entry
 266  *
 267  * Get the next entry from the list.
 268  *
 269  * Returns: udev_list_entry, #NULL if no more entries are available.
 270  */
 271 _public_ struct udev_list_entry *udev_list_entry_get_next(struct udev_list_entry *list_entry)
 272 {
 273         struct udev_list_node *next;
 274
 275         if (list_entry == NULL)
 276                 return NULL;
 277         next = list_entry->node.next;
 278         /* empty list or no more entries */
 279         if (next == &list_entry->list->node)
 280                 return NULL;
 281         return list_node_to_entry(next);
 282 }
 283
 284 /**
 285  * udev_list_entry_get_by_name:
 286  * @list_entry: current entry
 287  * @name: name string to match
 288  *
 289  * Lookup an entry in the list with a certain name.
 290  *
 291  * Returns: udev_list_entry, #NULL if no matching entry is found.
 292  */
 293 _public_ struct udev_list_entry *udev_list_entry_get_by_name(struct udev_list_entry *list_entry, const char *name)
 294 {
 295         int i;
 296
 297         if (list_entry == NULL)
 298                 return NULL;
 299
 300         if (!list_entry->list->unique)
 301                 return NULL;
 302
 303         i = list_search(list_entry->list, name);
 304         if (i < 0)
 305                 return NULL;
 306         return list_entry->list->entries[i];
 307 }
 308
 309 /**
 310  * udev_list_entry_get_name:
 311  * @list_entry: current entry
 312  *
 313  * Get the name of a list entry.
 314  *
 315  * Returns: the name string of this entry.
 316  */
 317 _public_ const char *udev_list_entry_get_name(struct udev_list_entry *list_entry)
 318 {
 319         if (list_entry == NULL)
 320                 return NULL;
 321         return list_entry->name;
 322 }
 323
 324 /**
 325  * udev_list_entry_get_value:
 326  * @list_entry: current entry
 327  *
 328  * Get the value of list entry.
 329  *
 330  * Returns: the value string of this entry.
 331  */
 332 _public_ const char *udev_list_entry_get_value(struct udev_list_entry *list_entry)
 333 {
 334         if (list_entry == NULL)
 335                 return NULL;
 336         return list_entry->value;
 337 }
 338
 339 int udev_list_entry_get_num(struct udev_list_entry *list_entry)
 340 {
 341         if (list_entry == NULL)
 342                 return -EINVAL;
 343         return list_entry->num;
 344 }
 345
 346 void udev_list_entry_set_num(struct udev_list_entry *list_entry, int num)
 347 {
 348         if (list_entry == NULL)
 349                 return;
 350         list_entry->num = num;
 351 }