libudev: list - use binary search for list lookup

5 files changed, 25 insertions, 25 deletions

diff --git a/udev/udev-event.c b/udev/udev-event.c
index a4141e9c4b..823768a3e2 100644
--- a/udev/udev-event.c
+++ b/udev/udev-event.c
@@ -38,14 +38,15 @@
 
 struct udev_event *udev_event_new(struct udev_device *dev)
 {
+	struct udev *udev = udev_device_get_udev(dev);
 	struct udev_event *event;
 
 	event = calloc(1, sizeof(struct udev_event));
 	if (event == NULL)
 		return NULL;
 	event->dev = dev;
-	event->udev = udev_device_get_udev(dev);
-	udev_list_init(&event->run_list);
+	event->udev = udev;
+	udev_list_init(udev, &event->run_list, false);
 	event->fd_signal = -1;
 	event->birth_usec = now_usec();
 	event->timeout_usec = 60 * 1000 * 1000;
@@ -57,7 +58,7 @@ void udev_event_unref(struct udev_event *event)
 {
 	if (event == NULL)
 		return;
-	udev_list_cleanup_entries(event->udev, &event->run_list);
+	udev_list_cleanup(&event->run_list);
 	free(event->tmp_node);
 	free(event->program_result);
 	free(event->name);
diff --git a/udev/udev-rules.c b/udev/udev-rules.c
index 89d98248a1..f345e8977d 100644
--- a/udev/udev-rules.c
+++ b/udev/udev-rules.c
@@ -1749,7 +1749,7 @@ static int parse_file(struct udev_rules *rules, const char *filename, unsigned s
 	return 0;
 }
 
-static int add_matching_files(struct udev *udev, struct udev_list_node *file_list, const char *dirname, const char *suffix)
+static int add_matching_files(struct udev *udev, struct udev_list *file_list, const char *dirname, const char *suffix)
 {
 	DIR *dir;
 	struct dirent *dent;
@@ -1783,7 +1783,7 @@ static int add_matching_files(struct udev *udev, struct udev_list_node *file_lis
 		 * identical basenames from different directories overwrite each other
 		 * entries are sorted after basename
 		 */
-		udev_list_entry_add(udev, file_list, dent->d_name, filename, UDEV_LIST_UNIQUE|UDEV_LIST_SORT);
+		udev_list_entry_add(file_list, dent->d_name, filename);
 	}
 
 	closedir(dir);
@@ -1793,7 +1793,7 @@ static int add_matching_files(struct udev *udev, struct udev_list_node *file_lis
 struct udev_rules *udev_rules_new(struct udev *udev, int resolve_names)
 {
 	struct udev_rules *rules;
-	struct udev_list_node file_list;
+	struct udev_list file_list;
 	struct udev_list_entry *file_loop;
 	struct token end_token;
 
@@ -1802,7 +1802,7 @@ struct udev_rules *udev_rules_new(struct udev *udev, int resolve_names)
 		return NULL;
 	rules->udev = udev;
 	rules->resolve_names = resolve_names;
-	udev_list_init(&file_list);
+	udev_list_init(udev, &file_list, true);
 
 	/* init token array and string buffer */
 	rules->tokens = malloc(PREALLOC_TOKEN * sizeof(struct token));
@@ -1885,7 +1885,7 @@ struct udev_rules *udev_rules_new(struct udev *udev, int resolve_names)
 		}
 		parse_file(rules, filename, filename_off);
 	}
-	udev_list_cleanup_entries(udev, &file_list);
+	udev_list_cleanup(&file_list);
 
 	memset(&end_token, 0x00, sizeof(struct token));
 	end_token.type = TK_END;
@@ -2663,13 +2663,12 @@ int udev_rules_apply_to_event(struct udev_rules *rules, struct udev_event *event
 			struct udev_list_entry *list_entry;
 
 			if (cur->key.op == OP_ASSIGN || cur->key.op == OP_ASSIGN_FINAL)
-				udev_list_cleanup_entries(event->udev, &event->run_list);
+				udev_list_cleanup(&event->run_list);
 			info(event->udev, "RUN '%s' %s:%u\n",
 			     &rules->buf[cur->key.value_off],
 			     &rules->buf[rule->rule.filename_off],
 			     rule->rule.filename_line);
-			list_entry = udev_list_entry_add(event->udev, &event->run_list,
-							 &rules->buf[cur->key.value_off], NULL, UDEV_LIST_UNIQUE);
+			list_entry = udev_list_entry_add(&event->run_list, &rules->buf[cur->key.value_off], NULL);
 			if (cur->key.fail_on_error)
 				udev_list_entry_set_num(list_entry, true);
 			break;
diff --git a/udev/udev.h b/udev/udev.h
index 0c73b502cb..c1e2814504 100644
--- a/udev/udev.h
+++ b/udev/udev.h
@@ -39,7 +39,7 @@ struct udev_event {
 	mode_t mode;
 	uid_t uid;
 	gid_t gid;
-	struct udev_list_node run_list;
+	struct udev_list run_list;
 	int exec_delay;
 	unsigned long long birth_usec;
 	unsigned long long timeout_usec;
diff --git a/udev/udevadm-monitor.c b/udev/udevadm-monitor.c
index 7ea7aa0f70..64913dbd55 100644
--- a/udev/udevadm-monitor.c
+++ b/udev/udevadm-monitor.c
@@ -72,8 +72,8 @@ static int adm_monitor(struct udev *udev, int argc, char *argv[])
 	bool prop = false;
 	bool print_kernel = false;
 	bool print_udev = false;
-	struct udev_list_node subsystem_match_list;
-	struct udev_list_node tag_match_list;
+	struct udev_list subsystem_match_list;
+	struct udev_list tag_match_list;
 	struct udev_monitor *udev_monitor = NULL;
 	struct udev_monitor *kernel_monitor = NULL;
 	int fd_ep = -1;
@@ -92,8 +92,8 @@ static int adm_monitor(struct udev *udev, int argc, char *argv[])
 		{}
 	};
 
-	udev_list_init(&subsystem_match_list);
-	udev_list_init(&tag_match_list);
+	udev_list_init(udev, &subsystem_match_list, true);
+	udev_list_init(udev, &tag_match_list, true);
 
 	for (;;) {
 		option = getopt_long(argc, argv, "pekus:t:h", options, NULL);
@@ -122,11 +122,11 @@ static int adm_monitor(struct udev *udev, int argc, char *argv[])
 					devtype[0] = '\0';
 					devtype++;
 				}
-				udev_list_entry_add(udev, &subsystem_match_list, subsys, devtype, 0);
+				udev_list_entry_add(&subsystem_match_list, subsys, devtype);
 				break;
 			}
 		case 't':
-			udev_list_entry_add(udev, &tag_match_list, optarg, NULL, 0);
+			udev_list_entry_add(&tag_match_list, optarg, NULL);
 			break;
 		case 'h':
 			printf("Usage: udevadm monitor [--property] [--kernel] [--udev] [--help]\n"
@@ -285,8 +285,8 @@ out:
 		close(fd_ep);
 	udev_monitor_unref(udev_monitor);
 	udev_monitor_unref(kernel_monitor);
-	udev_list_cleanup_entries(udev, &subsystem_match_list);
-	udev_list_cleanup_entries(udev, &tag_match_list);
+	udev_list_cleanup(&subsystem_match_list);
+	udev_list_cleanup(&tag_match_list);
 	return rc;
 }
 
diff --git a/udev/udevd.c b/udev/udevd.c
index 2fa2a6a48a..1220deaaa6 100644
--- a/udev/udevd.c
+++ b/udev/udevd.c
@@ -1574,8 +1574,8 @@ int main(int argc, char *argv[])
 
 	udev_rules_apply_static_dev_perms(rules);
 
-	udev_list_init(&event_list);
-	udev_list_init(&worker_list);
+	udev_list_node_init(&event_list);
+	udev_list_node_init(&worker_list);
 
 	for (;;) {
 		struct epoll_event ev[8];
@@ -1606,12 +1606,12 @@ int main(int argc, char *argv[])
 			worker_kill(udev, 0);
 
 			/* exit after all has cleaned up */
-			if (udev_list_is_empty(&event_list) && udev_list_is_empty(&worker_list))
+			if (udev_list_node_is_empty(&event_list) && udev_list_node_is_empty(&worker_list))
 				break;
 
 			/* timeout at exit for workers to finish */
 			timeout = 60 * 1000;
-		} else if (udev_list_is_empty(&event_list) && children > 2) {
+		} else if (udev_list_node_is_empty(&event_list) && children > 2) {
 			/* set timeout to kill idle workers */
 			timeout = 3 * 1000;
 		} else {
@@ -1659,7 +1659,7 @@ int main(int argc, char *argv[])
 		}
 
 		/* start new events */
-		if (!udev_list_is_empty(&event_list) && !udev_exit && !stop_exec_queue)
+		if (!udev_list_node_is_empty(&event_list) && !udev_exit && !stop_exec_queue)
 			event_queue_start(udev);
 
 		if (is_signal) {