diff options
-rw-r--r-- | src/map.c | 73 |
1 files changed, 58 insertions, 15 deletions
@@ -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 */ } |