[thirdparty/systemd.git] / src / libudev / libudev-list.c

/* SPDX-License-Identifier: LGPL-2.1+ */

#include <errno.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>

#include "alloc-util.h"
#include "libudev-list-internal.h"
#include "util.h"

/**
 * SECTION:libudev-list
 * @short_description: list operation
 *
 * Libudev list operations.
 */

/**
 * udev_list_entry:
 *
 * Opaque object representing one entry in a list. An entry contains
 * contains a name, and optionally a value.
 */
struct udev_list_entry {
        struct udev_list_node node;
        struct udev_list *list;
        char *name;
        char *value;
        int num;
};

/* the list's head points to itself if empty */
static void udev_list_node_init(struct udev_list_node *list) {
        list->next = list;
        list->prev = list;
}

static int udev_list_node_is_empty(struct udev_list_node *list) {
        return list->next == list;
}

static void udev_list_node_insert_between(struct udev_list_node *new,
                                          struct udev_list_node *prev,
                                          struct udev_list_node *next) {
        next->prev = new;
        new->next = next;
        new->prev = prev;
        prev->next = new;
}

static void udev_list_node_remove(struct udev_list_node *entry) {
        struct udev_list_node *prev = entry->prev;
        struct udev_list_node *next = entry->next;

        next->prev = prev;
        prev->next = next;

        entry->prev = NULL;
        entry->next = NULL;
}

/* return list entry which embeds this node */
static inline struct udev_list_entry *list_node_to_entry(struct udev_list_node *node) {
        return container_of(node, struct udev_list_entry, node);
}

void udev_list_init(struct udev *udev, struct udev_list *list, bool unique) {
        memzero(list, sizeof(struct udev_list));
        list->udev = udev;
        list->unique = unique;
        udev_list_node_init(&list->node);
}

/* insert entry into a list as the last element  */
static void udev_list_entry_append(struct udev_list_entry *new, struct udev_list *list) {
        /* inserting before the list head make the node the last node in the list */
        udev_list_node_insert_between(&new->node, list->node.prev, &list->node);
        new->list = list;
}

/* insert entry into a list, before a given existing entry */
static void udev_list_entry_insert_before(struct udev_list_entry *new, struct udev_list_entry *entry) {
        udev_list_node_insert_between(&new->node, entry->node.prev, &entry->node);
        new->list = entry->list;
}

/* binary search in sorted array */
static int list_search(struct udev_list *list, const char *name) {
        unsigned first, last;

        first = 0;
        last = list->entries_cur;
        while (first < last) {
                unsigned i;
                int cmp;

                i = (first + last)/2;
                cmp = strcmp(name, list->entries[i]->name);
                if (cmp < 0)
                        last = i;
                else if (cmp > 0)
                        first = i+1;
                else
                        return i;
        }

        /* not found, return negative insertion-index+1 */
        return -(first+1);
}

struct udev_list_entry *udev_list_entry_add(struct udev_list *list, const char *name, const char *value) {
        struct udev_list_entry *entry;
        int i = 0;

        if (list->unique) {
                /* lookup existing name or insertion-index */
                i = list_search(list, name);
                if (i >= 0) {
                        entry = list->entries[i];

                        free(entry->value);
                        if (!value) {
                                entry->value = NULL;
                                return entry;
                        }
                        entry->value = strdup(value);
                        if (!entry->value)
                                return NULL;
                        return entry;
                }
        }

        /* add new name */
        entry = new0(struct udev_list_entry, 1);
        if (!entry)
                return NULL;

        entry->name = strdup(name);
        if (!entry->name)
                return mfree(entry);

        if (value) {
                entry->value = strdup(value);
                if (!entry->value) {
                        free(entry->name);
                        return mfree(entry);
                }
        }

        if (list->unique) {
                /* allocate or enlarge sorted array if needed */
                if (list->entries_cur >= list->entries_max) {
                        struct udev_list_entry **entries;
                        unsigned add;

                        add = list->entries_max;
                        if (add < 1)
                                add = 64;
                        entries = reallocarray(list->entries, list->entries_max + add, sizeof(struct udev_list_entry *));
                        if (!entries) {
                                free(entry->name);
                                free(entry->value);
                                return mfree(entry);
                        }
                        list->entries = entries;
                        list->entries_max += add;
                }

                /* the negative i returned the insertion index */
                i = (-i)-1;

                /* insert into sorted list */
                if ((unsigned)i < list->entries_cur)
                        udev_list_entry_insert_before(entry, list->entries[i]);
                else
                        udev_list_entry_append(entry, list);

                /* insert into sorted array */
                memmove(&list->entries[i+1], &list->entries[i],
                        (list->entries_cur - i) * sizeof(struct udev_list_entry *));
                list->entries[i] = entry;
                list->entries_cur++;
        } else
                udev_list_entry_append(entry, list);

        return entry;
}

static void udev_list_entry_delete(struct udev_list_entry *entry) {
        if (entry->list->entries) {
                int i;
                struct udev_list *list = entry->list;

                /* remove entry from sorted array */
                i = list_search(list, entry->name);
                if (i >= 0) {
                        memmove(&list->entries[i], &list->entries[i+1],
                                ((list->entries_cur-1) - i) * sizeof(struct udev_list_entry *));
                        list->entries_cur--;
                }
        }

        udev_list_node_remove(&entry->node);
        free(entry->name);
        free(entry->value);
        free(entry);
}

#define udev_list_entry_foreach_safe(entry, tmp, first) \
        for (entry = first, tmp = udev_list_entry_get_next(entry); \
             entry; \
             entry = tmp, tmp = udev_list_entry_get_next(tmp))

void udev_list_cleanup(struct udev_list *list) {
        struct udev_list_entry *entry_loop;
        struct udev_list_entry *entry_tmp;

        list->entries = mfree(list->entries);
        list->entries_cur = 0;
        list->entries_max = 0;
        udev_list_entry_foreach_safe(entry_loop, entry_tmp, udev_list_get_entry(list))
                udev_list_entry_delete(entry_loop);
}

struct udev_list_entry *udev_list_get_entry(struct udev_list *list) {
        if (udev_list_node_is_empty(&list->node))
                return NULL;
        return list_node_to_entry(list->node.next);
}

/**
 * udev_list_entry_get_next:
 * @list_entry: current entry
 *
 * Get the next entry from the list.
 *
 * Returns: udev_list_entry, #NULL if no more entries are available.
 */
_public_ struct udev_list_entry *udev_list_entry_get_next(struct udev_list_entry *list_entry) {
        struct udev_list_node *next;

        if (!list_entry)
                return NULL;
        next = list_entry->node.next;
        /* empty list or no more entries */
        if (next == &list_entry->list->node)
                return NULL;
        return list_node_to_entry(next);
}

/**
 * udev_list_entry_get_by_name:
 * @list_entry: current entry
 * @name: name string to match
 *
 * Lookup an entry in the list with a certain name.
 *
 * Returns: udev_list_entry, #NULL if no matching entry is found.
 */
_public_ struct udev_list_entry *udev_list_entry_get_by_name(struct udev_list_entry *list_entry, const char *name) {
        int i;

        if (!list_entry)
                return NULL;

        if (!list_entry->list->unique)
                return NULL;

        i = list_search(list_entry->list, name);
        if (i < 0)
                return NULL;
        return list_entry->list->entries[i];
}

/**
 * udev_list_entry_get_name:
 * @list_entry: current entry
 *
 * Get the name of a list entry.
 *
 * Returns: the name string of this entry.
 */
_public_ const char *udev_list_entry_get_name(struct udev_list_entry *list_entry) {
        if (!list_entry)
                return NULL;
        return list_entry->name;
}

/**
 * udev_list_entry_get_value:
 * @list_entry: current entry
 *
 * Get the value of list entry.
 *
 * Returns: the value string of this entry.
 */
_public_ const char *udev_list_entry_get_value(struct udev_list_entry *list_entry) {
        if (!list_entry)
                return NULL;
        return list_entry->value;
}

int udev_list_entry_get_num(struct udev_list_entry *list_entry) {
        if (!list_entry)
                return -EINVAL;
        return list_entry->num;
}

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