- use binary trees to cut down on the time it takes to traverse maps

1 files changed, 58 insertions, 15 deletions

diff --git a/src/map.c b/src/map.c
index 1d193c0..377faeb 100644
--- a/src/map.c
+++ b/src/map.c
@@ -35,6 +35,8 @@ struct {
 				char *value;
 				unsigned int value_len;
 			} *entries;
+			void *key_tree;
+			void *id_tree;
 			void *backend_data;
 			void (*free_backend_data)(void *backend_data);
 		} *maps;
@@ -43,6 +45,37 @@ struct {
 	int n_domains;
 } map_data;
 
+/* Comparison functions used by the tree storage facility. */
+static int
+t_compare_entry_by_id(const void *p1, const void *p2)
+{
+	const struct map_entry *e1, *e2;
+	e1 = p1;
+	e2 = p2;
+	return strcmp(e1->id, e2->id);
+}
+static int
+t_compare_entry_by_key(const void *p1, const void *p2)
+{
+	const struct map_entry *e1, *e2;
+	unsigned int key_len;
+	int eq;
+	e1 = p1;
+	e2 = p2;
+	if (e1->key_len == e2->key_len) {
+		return memcmp(e1->key, e2->key, e1->key_len);
+	} else {
+		key_len = (e1->key_len < e2->key_len) ?
+			   e1->key_len : e2->key_len;
+		eq = memcmp(e1->key, e2->key, key_len);
+		if (eq != 0) {
+			return eq;
+		} else {
+			return (e1->key_len < e2->key_len) ? -1 : 1;
+		}
+	}
+}
+
 /* Utility function - find the domain record for the named domain. */
 static struct domain *
 map_data_find_domain(struct plugin_state *state, const char *domain_name)
@@ -81,17 +114,15 @@ static struct map_entry *
 map_data_find_map_entry(struct plugin_state *state,
 			struct map *map, unsigned int key_len, const char *key)
 {
-	struct map_entry *entry;
+	struct map_entry **entry, entry_template;
+	void **p;
 	if (map == NULL) {
 		return NULL;
 	}
-	for (entry = map->entries; entry != NULL; entry = entry->next) {
-		if ((entry->key_len == key_len) &&
-		    (memcmp(entry->key, key, key_len) == 0)) {
-			return entry;
-		}
-	}
-	return NULL;
+	entry_template.key = (char *) key;
+	entry_template.key_len = key_len;
+	entry = tfind(&entry_template, &map->key_tree, t_compare_entry_by_key);
+	return entry ? *entry : NULL;
 }
 
 static struct map_entry *
@@ -111,16 +142,14 @@ static struct map_entry *
 map_data_find_map_entry_id(struct plugin_state *state,
 			   struct map *map, const char *id)
 {
-	struct map_entry *entry;
+	struct map_entry **entry, entry_template;
+	void **p;
 	if (map == NULL) {
 		return NULL;
 	}
-	for (entry = map->entries; entry != NULL; entry = entry->next) {
-		if (strcmp(entry->id, id) == 0) {
-			return entry;
-		}
-	}
-	return NULL;
+	entry_template.id = (char *) id;
+	entry = tfind(&entry_template, &map->id_tree, t_compare_entry_by_id);
+	return entry ? *entry : NULL;
 }
 
 /* Handlers for the list of related IDs.  On this side we actually store them
@@ -407,6 +436,8 @@ map_data_clear_map_map(struct plugin_state *state, struct map *map)
 	/* Clear the entries list. */
 	if (map != NULL) {
 		for (entry = map->entries; entry != NULL; entry = next) {
+			tdelete(entry, &map->id_tree, t_compare_entry_by_id);
+			tdelete(entry, &map->key_tree, t_compare_entry_by_key);
 			next = entry->next;
 			free(entry->id);
 			entry->key_len = 0;
@@ -416,6 +447,8 @@ map_data_clear_map_map(struct plugin_state *state, struct map *map)
 			free(entry);
 		}
 		map->entries = NULL;
+		map->key_tree = NULL;
+		map->id_tree = NULL;
 	}
 }
 
@@ -592,6 +625,8 @@ map_data_unset_map_entry(struct plugin_state *state,
 		if (map->entries == entry) {
 			map->entries = next;
 		}
+		tdelete(entry, &map->key_tree, t_compare_entry_by_key);
+		tdelete(entry, &map->id_tree, t_compare_entry_by_id);
 		map_id_free_id_list(entry->related_ids);
 		free(entry->id);
 		free(entry->key);
@@ -657,6 +692,8 @@ map_data_set_entry(struct plugin_state *state,
 		if (entry != NULL) {
 			/* There's already an entry with this ID, so let's
 			 * replace its key and value. */
+			tdelete(entry, &map->key_tree, t_compare_entry_by_key);
+			tdelete(entry, &map->id_tree, t_compare_entry_by_id);
 			free(entry->key);
 			entry->key = xmemdup(key, key_len);
 			entry->key_len = key_len;
@@ -667,6 +704,8 @@ map_data_set_entry(struct plugin_state *state,
 			entry->id = strdup(id);
 			map_id_free_id_list(entry->related_ids);
 			entry->related_ids = map_id_dup_id_list(related_ids);
+			tsearch(entry, &map->key_tree, t_compare_entry_by_key);
+			tsearch(entry, &map->id_tree, t_compare_entry_by_id);
 		} else {
 			/* There's no entry with this ID, so create one. */
 			entry = malloc(sizeof(*entry));
@@ -683,6 +722,10 @@ map_data_set_entry(struct plugin_state *state,
 					map->entries->prev = entry;
 				}
 				map->entries = entry;
+				tsearch(entry, &map->key_tree,
+					t_compare_entry_by_key);
+				tsearch(entry, &map->id_tree,
+					t_compare_entry_by_id);
 			} else {
 				/* XXX */
 			}