libudev: list - use binary search for list lookup

7 files changed, 235 insertions, 190 deletions

diff --git a/libudev/libudev-device.c b/libudev/libudev-device.c
index 025527bb8a..76354dc7a7 100644
--- a/libudev/libudev-device.c
+++ b/libudev/libudev-device.c
@@ -62,11 +62,11 @@ struct udev_device {
 	char **envp;
 	char *monitor_buf;
 	size_t monitor_buf_len;
-	struct udev_list_node devlinks_list;
-	struct udev_list_node properties_list;
-	struct udev_list_node sysattr_value_list;
-	struct udev_list_node sysattr_list;
-	struct udev_list_node tags_list;
+	struct udev_list devlinks_list;
+	struct udev_list properties_list;
+	struct udev_list sysattr_value_list;
+	struct udev_list sysattr_list;
+	struct udev_list tags_list;
 	unsigned long long int seqnum;
 	unsigned long long int usec_initialized;
 	int timeout;
@@ -357,7 +357,7 @@ struct udev_list_entry *udev_device_add_property(struct udev_device *udev_device
 			udev_list_entry_delete(list_entry);
 		return NULL;
 	}
-	return udev_list_entry_add(udev_device->udev, &udev_device->properties_list, key, value, UDEV_LIST_UNIQUE);
+	return udev_list_entry_add(&udev_device->properties_list, key, value);
 }
 
 static struct udev_list_entry *udev_device_add_property_from_string(struct udev_device *udev_device, const char *property)
@@ -489,7 +489,7 @@ UDEV_EXPORT const char *udev_device_get_property_value(struct udev_device *udev_
 		return NULL;
 
 	list_entry = udev_device_get_properties_list_entry(udev_device);
-	list_entry =  udev_list_entry_get_by_name(list_entry, key);
+	list_entry = udev_list_entry_get_by_name(list_entry, key);
 	return udev_list_entry_get_value(list_entry);
 }
 
@@ -628,11 +628,11 @@ struct udev_device *udev_device_new(struct udev *udev)
 		return NULL;
 	udev_device->refcount = 1;
 	udev_device->udev = udev;
-	udev_list_init(&udev_device->devlinks_list);
-	udev_list_init(&udev_device->properties_list);
-	udev_list_init(&udev_device->sysattr_value_list);
-	udev_list_init(&udev_device->sysattr_list);
-	udev_list_init(&udev_device->tags_list);
+	udev_list_init(udev, &udev_device->devlinks_list, true);
+	udev_list_init(udev, &udev_device->properties_list, true);
+	udev_list_init(udev, &udev_device->sysattr_value_list, true);
+	udev_list_init(udev, &udev_device->sysattr_list, false);
+	udev_list_init(udev, &udev_device->tags_list, true);
 	udev_device->timeout = -1;
 	udev_device->watch_handle = -1;
 	/* copy global properties */
@@ -1082,11 +1082,11 @@ UDEV_EXPORT void udev_device_unref(struct udev_device *udev_device)
 	free(udev_device->devnode);
 	free(udev_device->subsystem);
 	free(udev_device->devtype);
-	udev_list_cleanup_entries(udev_device->udev, &udev_device->devlinks_list);
-	udev_list_cleanup_entries(udev_device->udev, &udev_device->properties_list);
-	udev_list_cleanup_entries(udev_device->udev, &udev_device->sysattr_value_list);
-	udev_list_cleanup_entries(udev_device->udev, &udev_device->sysattr_list);
-	udev_list_cleanup_entries(udev_device->udev, &udev_device->tags_list);
+	udev_list_cleanup(&udev_device->devlinks_list);
+	udev_list_cleanup(&udev_device->properties_list);
+	udev_list_cleanup(&udev_device->sysattr_value_list);
+	udev_list_cleanup(&udev_device->sysattr_list);
+	udev_list_cleanup(&udev_device->tags_list);
 	free(udev_device->action);
 	free(udev_device->driver);
 	free(udev_device->devpath_old);
@@ -1212,7 +1212,7 @@ UDEV_EXPORT struct udev_list_entry *udev_device_get_devlinks_list_entry(struct u
 void udev_device_cleanup_devlinks_list(struct udev_device *udev_device)
 {
 	udev_device->devlinks_uptodate = false;
-	udev_list_cleanup_entries(udev_device->udev, &udev_device->devlinks_list);
+	udev_list_cleanup(&udev_device->devlinks_list);
 }
 
 /**
@@ -1351,18 +1351,18 @@ UDEV_EXPORT const char *udev_device_get_sysattr_value(struct udev_device *udev_d
 		return NULL;
 
 	/* look for possibly already cached result */
-	udev_list_entry_foreach(list_entry, udev_list_get_entry(&udev_device->sysattr_value_list)) {
-		if (strcmp(udev_list_entry_get_name(list_entry), sysattr) == 0) {
-			dbg(udev_device->udev, "got '%s' (%s) from cache\n",
-			    sysattr, udev_list_entry_get_value(list_entry));
-			return udev_list_entry_get_value(list_entry);
-		}
+	list_entry = udev_list_get_entry(&udev_device->sysattr_value_list);
+	list_entry = udev_list_entry_get_by_name(list_entry, sysattr);
+	if (list_entry != NULL) {
+		dbg(udev_device->udev, "got '%s' (%s) from cache\n",
+		    sysattr, udev_list_entry_get_value(list_entry));
+		return udev_list_entry_get_value(list_entry);
 	}
 
 	util_strscpyl(path, sizeof(path), udev_device_get_syspath(udev_device), "/", sysattr, NULL);
 	if (lstat(path, &statbuf) != 0) {
 		dbg(udev_device->udev, "no attribute '%s', keep negative entry\n", path);
-		udev_list_entry_add(udev_device->udev, &udev_device->sysattr_value_list, sysattr, NULL, 0);
+		udev_list_entry_add(&udev_device->sysattr_value_list, sysattr, NULL);
 		goto out;
 	}
 
@@ -1386,7 +1386,7 @@ UDEV_EXPORT const char *udev_device_get_sysattr_value(struct udev_device *udev_d
 		if (pos != NULL) {
 			pos = &pos[1];
 			dbg(udev_device->udev, "cache '%s' with link value '%s'\n", sysattr, pos);
-			list_entry = udev_list_entry_add(udev_device->udev, &udev_device->sysattr_value_list, sysattr, pos, 0);
+			list_entry = udev_list_entry_add(&udev_device->sysattr_value_list, sysattr, pos);
 			val = udev_list_entry_get_value(list_entry);
 		}
 
@@ -1418,7 +1418,7 @@ UDEV_EXPORT const char *udev_device_get_sysattr_value(struct udev_device *udev_d
 	value[size] = '\0';
 	util_remove_trailing_chars(value, '\n');
 	dbg(udev_device->udev, "'%s' has attribute value '%s'\n", path, value);
-	list_entry = udev_list_entry_add(udev_device->udev, &udev_device->sysattr_value_list, sysattr, value, 0);
+	list_entry = udev_list_entry_add(&udev_device->sysattr_value_list, sysattr, value);
 	val = udev_list_entry_get_value(list_entry);
 out:
 	return val;
@@ -1456,8 +1456,7 @@ static int udev_device_sysattr_list_read(struct udev_device *udev_device)
 		if ((statbuf.st_mode & S_IRUSR) == 0)
 			continue;
 
-		udev_list_entry_add(udev_device->udev, &udev_device->sysattr_list,
-				    dent->d_name, NULL, 0);
+		udev_list_entry_add(&udev_device->sysattr_list, dent->d_name, NULL);
 		num++;
 	}
 
@@ -1543,7 +1542,7 @@ int udev_device_add_devlink(struct udev_device *udev_device, const char *devlink
 	struct udev_list_entry *list_entry;
 
 	udev_device->devlinks_uptodate = false;
-	list_entry = udev_list_entry_add(udev_device->udev, &udev_device->devlinks_list, devlink, NULL, UDEV_LIST_UNIQUE);
+	list_entry = udev_list_entry_add(&udev_device->devlinks_list, devlink, NULL);
 	if (list_entry == NULL)
 		return -ENOMEM;
 	if (unique)
@@ -1615,7 +1614,7 @@ int udev_device_add_tag(struct udev_device *udev_device, const char *tag)
 	if (strchr(tag, ':') != NULL || strchr(tag, ' ') != NULL)
 		return -EINVAL;
 	udev_device->tags_uptodate = false;
-	if (udev_list_entry_add(udev_device->udev, &udev_device->tags_list, tag, NULL, UDEV_LIST_UNIQUE) != NULL)
+	if (udev_list_entry_add(&udev_device->tags_list, tag, NULL) != NULL)
 		return 0;
 	return -ENOMEM;
 }
@@ -1623,7 +1622,7 @@ int udev_device_add_tag(struct udev_device *udev_device, const char *tag)
 void udev_device_cleanup_tags_list(struct udev_device *udev_device)
 {
 	udev_device->tags_uptodate = false;
-	udev_list_cleanup_entries(udev_device->udev, &udev_device->tags_list);
+	udev_list_cleanup(&udev_device->tags_list);
 }
 
 /**
diff --git a/libudev/libudev-enumerate.c b/libudev/libudev-enumerate.c
index b332ecdae1..f14d5c8f57 100644
--- a/libudev/libudev-enumerate.c
+++ b/libudev/libudev-enumerate.c
@@ -45,15 +45,15 @@ struct syspath {
 struct udev_enumerate {
 	struct udev *udev;
 	int refcount;
-	struct udev_list_node sysattr_match_list;
-	struct udev_list_node sysattr_nomatch_list;
-	struct udev_list_node subsystem_match_list;
-	struct udev_list_node subsystem_nomatch_list;
-	struct udev_list_node sysname_match_list;
-	struct udev_list_node properties_match_list;
-	struct udev_list_node tags_match_list;
+	struct udev_list sysattr_match_list;
+	struct udev_list sysattr_nomatch_list;
+	struct udev_list subsystem_match_list;
+	struct udev_list subsystem_nomatch_list;
+	struct udev_list sysname_match_list;
+	struct udev_list properties_match_list;
+	struct udev_list tags_match_list;
 	struct udev_device *parent_match;
-	struct udev_list_node devices_list;
+	struct udev_list devices_list;
 	struct syspath *devices;
 	unsigned int devices_cur;
 	unsigned int devices_max;
@@ -76,14 +76,14 @@ UDEV_EXPORT struct udev_enumerate *udev_enumerate_new(struct udev *udev)
 		return NULL;
 	udev_enumerate->refcount = 1;
 	udev_enumerate->udev = udev;
-	udev_list_init(&udev_enumerate->sysattr_match_list);
-	udev_list_init(&udev_enumerate->sysattr_nomatch_list);
-	udev_list_init(&udev_enumerate->subsystem_match_list);
-	udev_list_init(&udev_enumerate->subsystem_nomatch_list);
-	udev_list_init(&udev_enumerate->sysname_match_list);
-	udev_list_init(&udev_enumerate->properties_match_list);
-	udev_list_init(&udev_enumerate->tags_match_list);
-	udev_list_init(&udev_enumerate->devices_list);
+	udev_list_init(udev, &udev_enumerate->sysattr_match_list, false);
+	udev_list_init(udev, &udev_enumerate->sysattr_nomatch_list, false);
+	udev_list_init(udev, &udev_enumerate->subsystem_match_list, true);
+	udev_list_init(udev, &udev_enumerate->subsystem_nomatch_list, true);
+	udev_list_init(udev, &udev_enumerate->sysname_match_list, true);
+	udev_list_init(udev, &udev_enumerate->properties_match_list, false);
+	udev_list_init(udev, &udev_enumerate->tags_match_list, true);
+	udev_list_init(udev, &udev_enumerate->devices_list, false);
 	return udev_enumerate;
 }
 
@@ -119,15 +119,15 @@ UDEV_EXPORT void udev_enumerate_unref(struct udev_enumerate *udev_enumerate)
 	udev_enumerate->refcount--;
 	if (udev_enumerate->refcount > 0)
 		return;
-	udev_list_cleanup_entries(udev_enumerate->udev, &udev_enumerate->sysattr_match_list);
-	udev_list_cleanup_entries(udev_enumerate->udev, &udev_enumerate->sysattr_nomatch_list);
-	udev_list_cleanup_entries(udev_enumerate->udev, &udev_enumerate->subsystem_match_list);
-	udev_list_cleanup_entries(udev_enumerate->udev, &udev_enumerate->subsystem_nomatch_list);
-	udev_list_cleanup_entries(udev_enumerate->udev, &udev_enumerate->sysname_match_list);
-	udev_list_cleanup_entries(udev_enumerate->udev, &udev_enumerate->properties_match_list);
-	udev_list_cleanup_entries(udev_enumerate->udev, &udev_enumerate->tags_match_list);
+	udev_list_cleanup(&udev_enumerate->sysattr_match_list);
+	udev_list_cleanup(&udev_enumerate->sysattr_nomatch_list);
+	udev_list_cleanup(&udev_enumerate->subsystem_match_list);
+	udev_list_cleanup(&udev_enumerate->subsystem_nomatch_list);
+	udev_list_cleanup(&udev_enumerate->sysname_match_list);
+	udev_list_cleanup(&udev_enumerate->properties_match_list);
+	udev_list_cleanup(&udev_enumerate->tags_match_list);
 	udev_device_unref(udev_enumerate->parent_match);
-	udev_list_cleanup_entries(udev_enumerate->udev, &udev_enumerate->devices_list);
+	udev_list_cleanup(&udev_enumerate->devices_list);
 	for (i = 0; i < udev_enumerate->devices_cur; i++)
 		free(udev_enumerate->devices[i].syspath);
 	free(udev_enumerate->devices);
@@ -259,7 +259,7 @@ UDEV_EXPORT struct udev_list_entry *udev_enumerate_get_list_entry(struct udev_en
 		struct syspath *prev = NULL, *move_later = NULL;
 		size_t move_later_prefix = 0;
 
-		udev_list_cleanup_entries(udev_enumerate->udev, &udev_enumerate->devices_list);
+		udev_list_cleanup(&udev_enumerate->devices_list);
 		qsort(udev_enumerate->devices, udev_enumerate->devices_cur, sizeof(struct syspath), syspath_cmp);
 
 		max = udev_enumerate->devices_cur;
@@ -296,25 +296,21 @@ UDEV_EXPORT struct udev_list_entry *udev_enumerate_get_list_entry(struct udev_en
 			if (move_later &&
 			    strncmp(entry->syspath, move_later->syspath, move_later_prefix) != 0) {
 
-				udev_list_entry_add(udev_enumerate->udev, &udev_enumerate->devices_list,
-					    move_later->syspath, NULL, 0);
+				udev_list_entry_add(&udev_enumerate->devices_list, move_later->syspath, NULL);
 				move_later = NULL;
 			}
 
-			udev_list_entry_add(udev_enumerate->udev, &udev_enumerate->devices_list,
-					    entry->syspath, NULL, 0);
+			udev_list_entry_add(&udev_enumerate->devices_list, entry->syspath, NULL);
 		}
 
 		if (move_later)
-			udev_list_entry_add(udev_enumerate->udev, &udev_enumerate->devices_list,
-					    move_later->syspath, NULL, 0);
+			udev_list_entry_add(&udev_enumerate->devices_list, move_later->syspath, NULL);
 
 		/* add and cleanup delayed devices from end of list */
 		for (i = max; i < udev_enumerate->devices_cur; i++) {
 			struct syspath *entry = &udev_enumerate->devices[i];
 
-			udev_list_entry_add(udev_enumerate->udev, &udev_enumerate->devices_list,
-					    entry->syspath, NULL, 0);
+			udev_list_entry_add(&udev_enumerate->devices_list, entry->syspath, NULL);
 			free(entry->syspath);
 		}
 		udev_enumerate->devices_cur = max;
@@ -337,8 +333,7 @@ UDEV_EXPORT int udev_enumerate_add_match_subsystem(struct udev_enumerate *udev_e
 		return -EINVAL;
 	if (subsystem == NULL)
 		return 0;
-	if (udev_list_entry_add(udev_enumerate_get_udev(udev_enumerate),
-				&udev_enumerate->subsystem_match_list, subsystem, NULL, UDEV_LIST_UNIQUE) == NULL)
+	if (udev_list_entry_add(&udev_enumerate->subsystem_match_list, subsystem, NULL) == NULL)
 		return -ENOMEM;
 	return 0;
 }
@@ -356,8 +351,7 @@ UDEV_EXPORT int udev_enumerate_add_nomatch_subsystem(struct udev_enumerate *udev
 		return -EINVAL;
 	if (subsystem == NULL)
 		return 0;
-	if (udev_list_entry_add(udev_enumerate_get_udev(udev_enumerate),
-				&udev_enumerate->subsystem_nomatch_list, subsystem, NULL, UDEV_LIST_UNIQUE) == NULL)
+	if (udev_list_entry_add(&udev_enumerate->subsystem_nomatch_list, subsystem, NULL) == NULL)
 		return -ENOMEM;
 	return 0;
 }
@@ -376,8 +370,7 @@ UDEV_EXPORT int udev_enumerate_add_match_sysattr(struct udev_enumerate *udev_enu
 		return -EINVAL;
 	if (sysattr == NULL)
 		return 0;
-	if (udev_list_entry_add(udev_enumerate_get_udev(udev_enumerate),
-				&udev_enumerate->sysattr_match_list, sysattr, value, 0) == NULL)
+	if (udev_list_entry_add(&udev_enumerate->sysattr_match_list, sysattr, value) == NULL)
 		return -ENOMEM;
 	return 0;
 }
@@ -396,8 +389,7 @@ UDEV_EXPORT int udev_enumerate_add_nomatch_sysattr(struct udev_enumerate *udev_e
 		return -EINVAL;
 	if (sysattr == NULL)
 		return 0;
-	if (udev_list_entry_add(udev_enumerate_get_udev(udev_enumerate),
-			   &udev_enumerate->sysattr_nomatch_list, sysattr, value, 0) == NULL)
+	if (udev_list_entry_add(&udev_enumerate->sysattr_nomatch_list, sysattr, value) == NULL)
 		return -ENOMEM;
 	return 0;
 }
@@ -436,8 +428,7 @@ UDEV_EXPORT int udev_enumerate_add_match_property(struct udev_enumerate *udev_en
 		return -EINVAL;
 	if (property == NULL)
 		return 0;
-	if (udev_list_entry_add(udev_enumerate_get_udev(udev_enumerate),
-				&udev_enumerate->properties_match_list, property, value, 0) == NULL)
+	if (udev_list_entry_add(&udev_enumerate->properties_match_list, property, value) == NULL)
 		return -ENOMEM;
 	return 0;
 }
@@ -455,8 +446,7 @@ UDEV_EXPORT int udev_enumerate_add_match_tag(struct udev_enumerate *udev_enumera
 		return -EINVAL;
 	if (tag == NULL)
 		return 0;
-	if (udev_list_entry_add(udev_enumerate_get_udev(udev_enumerate),
-				&udev_enumerate->tags_match_list, tag, NULL, UDEV_LIST_UNIQUE) == NULL)
+	if (udev_list_entry_add(&udev_enumerate->tags_match_list, tag, NULL) == NULL)
 		return -ENOMEM;
 	return 0;
 }
@@ -525,8 +515,7 @@ UDEV_EXPORT int udev_enumerate_add_match_sysname(struct udev_enumerate *udev_enu
 		return -EINVAL;
 	if (sysname == NULL)
 		return 0;
-	if (udev_list_entry_add(udev_enumerate_get_udev(udev_enumerate),
-				&udev_enumerate->sysname_match_list, sysname, NULL, UDEV_LIST_UNIQUE) == NULL)
+	if (udev_list_entry_add(&udev_enumerate->sysname_match_list, sysname, NULL) == NULL)
 		return -ENOMEM;
 	return 0;
 }
diff --git a/libudev/libudev-list.c b/libudev/libudev-list.c
index e828a4e4c6..295ee682bc 100644
--- a/libudev/libudev-list.c
+++ b/libudev/libudev-list.c
@@ -34,21 +34,20 @@
  */
 struct udev_list_entry {
 	struct udev_list_node node;
-	struct udev *udev;
-	struct udev_list_node *list;
+	struct udev_list *list;
 	char *name;
 	char *value;
 	int num;
 };
 
 /* the list's head points to itself if empty */
-void udev_list_init(struct udev_list_node *list)
+void udev_list_node_init(struct udev_list_node *list)
 {
 	list->next = list;
 	list->prev = list;
 }
 
-int udev_list_is_empty(struct udev_list_node *list)
+int udev_list_node_is_empty(struct udev_list_node *list)
 {
 	return list->next == list;
 }
@@ -90,19 +89,20 @@ static struct udev_list_entry *list_node_to_entry(struct udev_list_node *node)
 	return (struct udev_list_entry *)list;
 }
 
-/* insert entry into a list as the last element  */
-void udev_list_entry_append(struct udev_list_entry *new, struct udev_list_node *list)
+void udev_list_init(struct udev *udev, struct udev_list *list, bool unique)
 {
-	/* inserting before the list head make the node the last node in the list */
-	udev_list_node_insert_between(&new->node, list->prev, list);
-	new->list = list;
+	memset(list, 0x00, sizeof(struct udev_list));
+	list->udev = udev;
+	list->unique = unique;
+	udev_list_node_init(&list->node);
 }
 
-/* remove entry from a list */
-void udev_list_entry_remove(struct udev_list_entry *entry)
+/* insert entry into a list as the last element  */
+void udev_list_entry_append(struct udev_list_entry *new, struct udev_list *list)
 {
-	udev_list_node_remove(&entry->node);
-	entry->list = NULL;
+	/* 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 */
@@ -112,90 +112,144 @@ void udev_list_entry_insert_before(struct udev_list_entry *new, struct udev_list
 	new->list = entry->list;
 }
 
-struct udev_list_entry *udev_list_entry_add(struct udev *udev, struct udev_list_node *list,
-					    const char *name, const char *value,
-					    unsigned int flags)
+/* binary search in sorted array */
+static int list_search(struct udev_list *list, const char *name)
 {
-	struct udev_list_entry *entry_loop = NULL;
-	struct udev_list_entry *entry_new;
-
-	if (flags & UDEV_LIST_UNIQUE) {
-		udev_list_entry_foreach(entry_loop, udev_list_get_entry(list)) {
-			if (strcmp(entry_loop->name, name) == 0) {
-				dbg(udev, "'%s' is already in the list\n", name);
-				free(entry_loop->value);
-				if (value == NULL) {
-					entry_loop->value = NULL;
-					dbg(udev, "'%s' value unset\n", name);
-					return entry_loop;
-				}
-				entry_loop->value = strdup(value);
-				if (entry_loop->value == NULL)
-					return NULL;
-				dbg(udev, "'%s' value replaced with '%s'\n", name, value);
-				return entry_loop;
-			}
-		}
+	unsigned int first, last;
+
+	first = 0;
+	last = list->entries_cur;
+	while (first < last) {
+		unsigned int 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;
 	}
 
-	if (flags & UDEV_LIST_SORT) {
-		udev_list_entry_foreach(entry_loop, udev_list_get_entry(list)) {
-			if (strcmp(entry_loop->name, name) > 0)
-				break;
+	/* 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];
+
+			dbg(list->udev, "'%s' is already in the list\n", name);
+			free(entry->value);
+			if (value == NULL) {
+				entry->value = NULL;
+				dbg(list->udev, "'%s' value unset\n", name);
+				return entry;
+			}
+			entry->value = strdup(value);
+			if (entry->value == NULL)
+				return NULL;
+			dbg(list->udev, "'%s' value replaced with '%s'\n", name, value);
+			return entry;
 		}
 	}
 
-	entry_new = malloc(sizeof(struct udev_list_entry));
-	if (entry_new == NULL)
+	/* add new name */
+	entry = calloc(1, sizeof(struct udev_list_entry));
+	if (entry == NULL)
 		return NULL;
-	memset(entry_new, 0x00, sizeof(struct udev_list_entry));
-	entry_new->udev = udev;
-	entry_new->name = strdup(name);
-	if (entry_new->name == NULL) {
-		free(entry_new);
+	entry->name = strdup(name);
+	if (entry->name == NULL) {
+		free(entry);
 		return NULL;
 	}
-
 	if (value != NULL) {
-		entry_new->value = strdup(value);
-		if (entry_new->value == NULL) {
-			free(entry_new->name);
-			free(entry_new);
+		entry->value = strdup(value);
+		if (entry->value == NULL) {
+			free(entry->name);
+			free(entry);
 			return NULL;
 		}
 	}
+	udev_list_entry_append(entry, list);
+
+	if (list->unique) {
+		/* allocate or enlarge sorted array if needed */
+		if (list->entries_cur >= list->entries_max) {
+			unsigned int add;
+
+			add = list->entries_max;
+			if (add < 1)
+				add = 64;
+			list->entries = realloc(list->entries, (list->entries_max + add) * sizeof(struct udev_list_entry *));
+			if (list->entries == NULL) {
+				free(entry->name);
+				free(entry->value);
+				return NULL;
+			}
+			list->entries_max += add;
+		}
 
-	if (entry_loop != NULL)
-		udev_list_entry_insert_before(entry_new, entry_loop);
-	else
-		udev_list_entry_append(entry_new, list);
+		/* insert into sorted array */
+		i = (-i)-1;
+		memmove(&list->entries[i+1], &list->entries[i],
+		        (list->entries_cur - i) * sizeof(struct udev_list_entry *));
+		list->entries[i] = entry;
+		list->entries_cur++;
+	}
 
-	dbg(udev, "'%s=%s' added\n", entry_new->name, entry_new->value);
-	return entry_new;
+	dbg(list->udev, "'%s=%s' added\n", entry->name, entry->value);
+	return entry;
 }
 
 void udev_list_entry_delete(struct udev_list_entry *entry)
 {
+	if (entry->list->entries != NULL) {
+		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);
 }
 
-void udev_list_cleanup_entries(struct udev *udev, struct udev_list_node *list)
+void udev_list_cleanup(struct udev_list *list)
 {
 	struct udev_list_entry *entry_loop;
 	struct udev_list_entry *entry_tmp;
 
+	free(list->entries);
+	list->entries = NULL;
+	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_node *list)
+struct udev_list_entry *udev_list_get_entry(struct udev_list *list)
 {
-	if (udev_list_is_empty(list))
+	if (udev_list_node_is_empty(&list->node))
 		return NULL;
-	return list_node_to_entry(list->next);
+	return list_node_to_entry(list->node.next);
 }
 
 /**
@@ -212,7 +266,7 @@ UDEV_EXPORT struct udev_list_entry *udev_list_entry_get_next(struct udev_list_en
 		return NULL;
 	next = list_entry->node.next;
 	/* empty list or no more entries */
-	if (next == list_entry->list)
+	if (next == &list_entry->list->node)
 		return NULL;
 	return list_node_to_entry(next);
 }
@@ -226,15 +280,18 @@ UDEV_EXPORT struct udev_list_entry *udev_list_entry_get_next(struct udev_list_en
  */
 UDEV_EXPORT struct udev_list_entry *udev_list_entry_get_by_name(struct udev_list_entry *list_entry, const char *name)
 {
-	struct udev_list_entry *entry;
+	int i;
 
-	udev_list_entry_foreach(entry, list_entry) {
-		if (strcmp(udev_list_entry_get_name(entry), name) == 0) {
-			dbg(entry->udev, "found '%s=%s'\n", entry->name, entry->value);
-			return entry;
-		}
-	}
-	return NULL;
+	if (list_entry == NULL)
+		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];
 }
 
 /**
diff --git a/libudev/libudev-monitor.c b/libudev/libudev-monitor.c
index 31dd66827c..f2f39f9582 100644
--- a/libudev/libudev-monitor.c
+++ b/libudev/libudev-monitor.c
@@ -48,8 +48,8 @@ struct udev_monitor {
 	struct sockaddr_nl snl_destination;
 	struct sockaddr_un sun;
 	socklen_t addrlen;
-	struct udev_list_node filter_subsystem_list;
-	struct udev_list_node filter_tag_list;
+	struct udev_list filter_subsystem_list;
+	struct udev_list filter_tag_list;
 	bool bound;
 };
 
@@ -92,8 +92,8 @@ static struct udev_monitor *udev_monitor_new(struct udev *udev)
 		return NULL;
 	udev_monitor->refcount = 1;
 	udev_monitor->udev = udev;
-	udev_list_init(&udev_monitor->filter_subsystem_list);
-	udev_list_init(&udev_monitor->filter_tag_list);
+	udev_list_init(udev, &udev_monitor->filter_subsystem_list, false);
+	udev_list_init(udev, &udev_monitor->filter_tag_list, true);
 	return udev_monitor;
 }
 
@@ -483,8 +483,8 @@ UDEV_EXPORT void udev_monitor_unref(struct udev_monitor *udev_monitor)
 		return;
 	if (udev_monitor->sock >= 0)
 		close(udev_monitor->sock);
-	udev_list_cleanup_entries(udev_monitor->udev, &udev_monitor->filter_subsystem_list);
-	udev_list_cleanup_entries(udev_monitor->udev, &udev_monitor->filter_tag_list);
+	udev_list_cleanup(&udev_monitor->filter_subsystem_list);
+	udev_list_cleanup(&udev_monitor->filter_tag_list);
 	dbg(udev_monitor->udev, "monitor %p released\n", udev_monitor);
 	free(udev_monitor);
 }
@@ -647,7 +647,7 @@ retry:
 		/* udev message needs proper version magic */
 		nlh = (struct udev_monitor_netlink_header *) buf;
 		if (nlh->magic != htonl(UDEV_MONITOR_MAGIC)) {
-			err(udev_monitor->udev, "ignored a message from an invalid release of udevadm (%x != %x)\n",
+			err(udev_monitor->udev, "unrecognized message signature (%x != %x)\n",
 			    nlh->magic, htonl(UDEV_MONITOR_MAGIC));
 			return NULL;
 		}
@@ -830,8 +830,7 @@ UDEV_EXPORT int udev_monitor_filter_add_match_subsystem_devtype(struct udev_moni
 		return -EINVAL;
 	if (subsystem == NULL)
 		return -EINVAL;
-	if (udev_list_entry_add(udev_monitor->udev,
-				&udev_monitor->filter_subsystem_list, subsystem, devtype, 0) == NULL)
+	if (udev_list_entry_add(&udev_monitor->filter_subsystem_list, subsystem, devtype) == NULL)
 		return -ENOMEM;
 	return 0;
 }
@@ -854,8 +853,7 @@ UDEV_EXPORT int udev_monitor_filter_add_match_tag(struct udev_monitor *udev_moni
 		return -EINVAL;
 	if (tag == NULL)
 		return -EINVAL;
-	if (udev_list_entry_add(udev_monitor->udev,
-				&udev_monitor->filter_tag_list, tag, NULL, 0) == NULL)
+	if (udev_list_entry_add(&udev_monitor->filter_tag_list, tag, NULL) == NULL)
 		return -ENOMEM;
 	return 0;
 }
@@ -872,6 +870,6 @@ UDEV_EXPORT int udev_monitor_filter_remove(struct udev_monitor *udev_monitor)
 {
 	static struct sock_fprog filter = { 0, NULL };
 
-	udev_list_cleanup_entries(udev_monitor->udev, &udev_monitor->filter_subsystem_list);
+	udev_list_cleanup(&udev_monitor->filter_subsystem_list);
 	return setsockopt(udev_monitor->sock, SOL_SOCKET, SO_ATTACH_FILTER, &filter, sizeof(filter));
 }
diff --git a/libudev/libudev-private.h b/libudev/libudev-private.h
index 0c17c45744..157575c1ff 100644
--- a/libudev/libudev-private.h
+++ b/libudev/libudev-private.h
@@ -115,17 +115,20 @@ int udev_monitor_send_device(struct udev_monitor *udev_monitor,
 struct udev_monitor *udev_monitor_new_from_netlink_fd(struct udev *udev, const char *name, int fd);
 
 /* libudev-list.c */
-enum udev_list_flags {
-	UDEV_LIST_NONE =        0,
-	UDEV_LIST_UNIQUE =      1,
-	UDEV_LIST_SORT =        1 << 1,
-};
 struct udev_list_node {
 	struct udev_list_node *next, *prev;
 };
+struct udev_list {
+	struct udev *udev;
+	struct udev_list_node node;
+	struct udev_list_entry **entries;
+	unsigned int entries_cur;
+	unsigned int entries_max;
+	bool unique;
+};
 #define UDEV_LIST(list) struct udev_list_node list = { &(list), &(list) }
-void udev_list_init(struct udev_list_node *list);
-int udev_list_is_empty(struct udev_list_node *list);
+void udev_list_node_init(struct udev_list_node *list);
+int udev_list_node_is_empty(struct udev_list_node *list);
 void udev_list_node_append(struct udev_list_node *new, struct udev_list_node *list);
 void udev_list_node_remove(struct udev_list_node *entry);
 #define udev_list_node_foreach(node, list) \
@@ -136,14 +139,13 @@ void udev_list_node_remove(struct udev_list_node *entry);
 	for (node = (list)->next, tmp = (node)->next; \
 	     node != list; \
 	     node = tmp, tmp = (tmp)->next)
-struct udev_list_entry *udev_list_entry_add(struct udev *udev, struct udev_list_node *list,
-						   const char *name, const char *value, unsigned int flags);
+void udev_list_init(struct udev *udev, struct udev_list *list, bool unique);
+void udev_list_cleanup(struct udev_list *list);
+struct udev_list_entry *udev_list_get_entry(struct udev_list *list);
+struct udev_list_entry *udev_list_entry_add(struct udev_list *list, const char *name, const char *value);
 void udev_list_entry_delete(struct udev_list_entry *entry);
-void udev_list_entry_remove(struct udev_list_entry *entry);
 void udev_list_entry_insert_before(struct udev_list_entry *new, struct udev_list_entry *entry);
-void udev_list_entry_append(struct udev_list_entry *new, struct udev_list_node *list);
-void udev_list_cleanup_entries(struct udev *udev, struct udev_list_node *name_list);
-struct udev_list_entry *udev_list_get_entry(struct udev_list_node *list);
+void udev_list_entry_append(struct udev_list_entry *new, struct udev_list *list);
 int udev_list_entry_get_num(struct udev_list_entry *list_entry);
 void udev_list_entry_set_num(struct udev_list_entry *list_entry, int num);
 #define udev_list_entry_foreach_safe(entry, tmp, first) \
diff --git a/libudev/libudev-queue.c b/libudev/libudev-queue.c
index 73e7fb23aa..744696df2b 100644
--- a/libudev/libudev-queue.c
+++ b/libudev/libudev-queue.c
@@ -42,8 +42,8 @@
 struct udev_queue {
 	struct udev *udev;
 	int refcount;
-	struct udev_list_node queue_list;
-	struct udev_list_node failed_list;
+	struct udev_list queue_list;
+	struct udev_list failed_list;
 };
 
 /**
@@ -67,8 +67,8 @@ UDEV_EXPORT struct udev_queue *udev_queue_new(struct udev *udev)
 		return NULL;
 	udev_queue->refcount = 1;
 	udev_queue->udev = udev;
-	udev_list_init(&udev_queue->queue_list);
-	udev_list_init(&udev_queue->failed_list);
+	udev_list_init(udev, &udev_queue->queue_list, false);
+	udev_list_init(udev, &udev_queue->failed_list, false);
 	return udev_queue;
 }
 
@@ -102,8 +102,8 @@ UDEV_EXPORT void udev_queue_unref(struct udev_queue *udev_queue)
 	udev_queue->refcount--;
 	if (udev_queue->refcount > 0)
 		return;
-	udev_list_cleanup_entries(udev_queue->udev, &udev_queue->queue_list);
-	udev_list_cleanup_entries(udev_queue->udev, &udev_queue->failed_list);
+	udev_list_cleanup(&udev_queue->queue_list);
+	udev_list_cleanup(&udev_queue->failed_list);
 	free(udev_queue);
 }
 
@@ -429,7 +429,7 @@ UDEV_EXPORT struct udev_list_entry *udev_queue_get_queued_list_entry(struct udev
 
 	if (udev_queue == NULL)
 		return NULL;
-	udev_list_cleanup_entries(udev_queue->udev, &udev_queue->queue_list);
+	udev_list_cleanup(&udev_queue->queue_list);
 
 	queue_file = open_queue_file(udev_queue, &seqnum);
 	if (queue_file == NULL)
@@ -454,7 +454,7 @@ UDEV_EXPORT struct udev_list_entry *udev_queue_get_queued_list_entry(struct udev
 			break;
 
 		if (len > 0) {
-			udev_list_entry_add(udev_queue->udev, &udev_queue->queue_list, syspath, seqnum_str, 0);
+			udev_list_entry_add(&udev_queue->queue_list, syspath, seqnum_str);
 		} else {
 			udev_list_entry_foreach(list_entry, udev_list_get_entry(&udev_queue->queue_list)) {
 				if (strcmp(seqnum_str, udev_list_entry_get_value(list_entry)) == 0) {
@@ -483,7 +483,7 @@ UDEV_EXPORT struct udev_list_entry *udev_queue_get_failed_list_entry(struct udev
 
 	if (udev_queue == NULL)
 		return NULL;
-	udev_list_cleanup_entries(udev_queue->udev, &udev_queue->failed_list);
+	udev_list_cleanup(&udev_queue->failed_list);
 	util_strscpyl(path, sizeof(path), udev_get_run_path(udev_queue->udev), "/failed", NULL);
 	dir = opendir(path);
 	if (dir == NULL)
@@ -508,7 +508,7 @@ UDEV_EXPORT struct udev_list_entry *udev_queue_get_failed_list_entry(struct udev
 		util_strscpyl(filename, sizeof(filename), syspath, "/uevent", NULL);
 		if (stat(filename, &statbuf) != 0)
 			continue;
-		udev_list_entry_add(udev_queue->udev, &udev_queue->failed_list, syspath, NULL, 0);
+		udev_list_entry_add(&udev_queue->failed_list, syspath, NULL);
 	}
 	closedir(dir);
 	return udev_list_get_entry(&udev_queue->failed_list);
diff --git a/libudev/libudev.c b/libudev/libudev.c
index ad8c914e84..165c36984e 100644
--- a/libudev/libudev.c
+++ b/libudev/libudev.c
@@ -45,7 +45,7 @@ struct udev {
 	char *rules_path;
 	char *run_config_path;
 	char *run_path;
-	struct udev_list_node properties_list;
+	struct udev_list properties_list;
 	int log_priority;
 };
 
@@ -130,14 +130,14 @@ UDEV_EXPORT struct udev *udev_new(void)
 	udev->refcount = 1;
 	udev->log_fn = log_stderr;
 	udev->log_priority = LOG_ERR;
-	udev_list_init(&udev->properties_list);
+	udev_list_init(udev, &udev->properties_list, true);
 
 	/* custom config file */
 	env = getenv("UDEV_CONFIG_FILE");
 	if (env != NULL) {
-		udev_add_property(udev, "UDEV_CONFIG_FILE", udev->dev_path);
 		if (set_value(&config_file, env) == NULL)
 			goto err;
+		udev_add_property(udev, "UDEV_CONFIG_FILE", config_file);
 	}
 
 	/* default config file */
@@ -307,7 +307,7 @@ UDEV_EXPORT void udev_unref(struct udev *udev)
 	udev->refcount--;
 	if (udev->refcount > 0)
 		return;
-	udev_list_cleanup_entries(udev, &udev->properties_list);
+	udev_list_cleanup(&udev->properties_list);
 	free(udev->dev_path);
 	free(udev->sys_path);
 	free(udev->rules_path);
@@ -458,7 +458,7 @@ struct udev_list_entry *udev_add_property(struct udev *udev, const char *key, co
 			udev_list_entry_delete(list_entry);
 		return NULL;
 	}
-	return udev_list_entry_add(udev, &udev->properties_list, key, value, UDEV_LIST_UNIQUE);
+	return udev_list_entry_add(&udev->properties_list, key, value);
 }
 
 struct udev_list_entry *udev_get_properties_list_entry(struct udev *udev)