File udev-trigger-use-qsort of Package udev

diff --git a/udev/udevadm-trigger.c b/udev/udevadm-trigger.c
index f0535f5..71a1894 100644
--- a/udev/udevadm-trigger.c
+++ b/udev/udevadm-trigger.c
@@ -37,7 +37,6 @@
 
 static int verbose;
 static int dry_run;
-LIST_HEAD(device_list);
 LIST_HEAD(filter_subsystem_match_list);
 LIST_HEAD(filter_subsystem_nomatch_list);
 LIST_HEAD(filter_attr_match_list);
@@ -46,6 +45,75 @@ static int sock = -1;
 static struct sockaddr_un saddr;
 static socklen_t saddrlen;
 
+struct syspath {
+	char *syspath;
+	size_t len;
+};
+
+static struct syspath *devices;
+static unsigned int devices_cur;
+static unsigned int devices_max;
+
+static void syspath_cleanup(void)
+{
+	unsigned int i;
+
+	for (i = 0; i < devices_cur; i++)
+		free(devices[i].syspath);
+	free(devices);
+	devices = NULL;
+	devices_cur = 0;
+	devices_max = 0;
+}
+
+static int syspath_add(const char *syspath)
+{
+	char *path;
+	struct syspath *entry;
+
+	/* double array size if needed */
+	if (devices_cur >= devices_max) {
+		struct syspath *buf;
+		unsigned int add;
+
+		add = devices_max;
+		if (add < 1024)
+			add = 1024;
+		buf = realloc(devices, (devices_max + add) * sizeof(struct syspath));
+		if (buf == NULL)
+			return -ENOMEM;
+		devices = buf;
+		devices_max += add;
+	}
+
+	path = strdup(syspath);
+	if (path == NULL)
+		return -ENOMEM;
+	entry = &devices[devices_cur];
+	entry->syspath = path;
+	entry->len = strlen(path);
+	devices_cur++;
+	return 0;
+}
+
+static int syspath_cmp(const void *p1, const void *p2)
+{
+	const struct syspath *path1 = p1;
+	const struct syspath *path2 = p2;
+	size_t len;
+	int ret;
+
+	len = MIN(path1->len, path2->len);
+	ret = memcmp(path1->syspath, path2->syspath, len);
+	if (ret == 0) {
+		if (path1->len < path2->len)
+			ret = -1;
+		else if (path1->len > path2->len)
+			ret = 1;
+	}
+	return ret;
+}
+
 /* devices that should run last cause of their dependencies */
 static int delay_device(const char *devpath)
 {
@@ -87,7 +155,7 @@ static int device_list_insert(struct udev *udev, const char *path)
 		if (util_resolve_sys_link(udev, devpath, sizeof(devpath)) != 0)
 			return -1;
 
-	name_list_add(udev, &device_list, devpath, 1);
+	syspath_add(devpath);
 	return 0;
 }
 
@@ -238,29 +306,44 @@ static int pass_to_socket(struct udev *udev, const char *devpath, const char *ac
 
 static void exec_list(struct udev *udev, const char *action, const char *env)
 {
-	struct name_entry *loop_device;
-	struct name_entry *tmp_device;
+	unsigned int i;
+	unsigned int max;
+	struct syspath *prev = NULL;
+
+	qsort(devices, devices_cur, sizeof(struct syspath), syspath_cmp);
 
-	list_for_each_entry_safe(loop_device, tmp_device, &device_list, node) {
-		if (delay_device(loop_device->name))
+	max = devices_cur;
+	for (i = 0; i < max; i++) {
+		struct syspath *entry = &devices[i];
+
+		/* skip duplicated entries */
+		if (prev != NULL &&
+		    entry->len == prev->len &&
+		    memcmp(entry->syspath, prev->syspath, entry->len) == 0)
+			continue;
+		prev = entry;
+
+		/* skip to be delayed devices, and add them to the end of the list */
+		if (delay_device(entry->syspath)) {
+			syspath_add(entry->syspath);
 			continue;
+		}
+
 		if (sock >= 0)
-			pass_to_socket(udev, loop_device->name, action, env);
+			pass_to_socket(udev, entry->syspath, action, env);
 		else
-			trigger_uevent(udev, loop_device->name, action);
-		list_del(&loop_device->node);
-		free(loop_device);
+			trigger_uevent(udev, entry->syspath, action);
 	}
+	/* add and cleanup delayed devices from end of list */
+	for (i = max; i < devices_cur; i++) {
+		struct syspath *entry = &devices[i];
 
-	/* trigger remaining delayed devices */
-	list_for_each_entry_safe(loop_device, tmp_device, &device_list, node) {
 		if (sock >= 0)
-			pass_to_socket(udev, loop_device->name, action, env);
+			pass_to_socket(udev, entry->syspath, action, env);
 		else
-			trigger_uevent(udev, loop_device->name, action);
-		list_del(&loop_device->node);
-		free(loop_device);
+			trigger_uevent(udev, entry->syspath, action);
 	}
+	syspath_cleanup();
 }
 
 static int subsystem_filtered(const char *subsystem)