From 721603d976475e997a1be495d0fc2e42d3fda431 Mon Sep 17 00:00:00 2001 From: Nalin Dahyabhai Date: Wed, 30 Jul 2008 14:55:18 -0400 Subject: - learn to track multiple values for each entry --- src/map.c | 293 +++++++++++++++++++++++++++++++++++--------------------------- src/map.h | 2 +- 2 files changed, 167 insertions(+), 128 deletions(-) (limited to 'src') diff --git a/src/map.c b/src/map.c index 2fd3bb3..3f9d83f 100644 --- a/src/map.c +++ b/src/map.c @@ -68,8 +68,9 @@ static struct { unsigned int n_keys; char **keys; unsigned int *key_len; - char *value; - unsigned int value_len; + unsigned int n_values; + char **values; + unsigned int *value_len; /* Key index for comparison. Used by the * key_trees. */ int key_index; @@ -180,7 +181,8 @@ map_data_find_map(struct plugin_state *state, * domain. */ 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 *map, unsigned int key_len, const char *key, + unsigned int *key_index) { struct map_entry **entry, entry_template; unsigned int i; @@ -194,6 +196,9 @@ map_data_find_map_entry(struct plugin_state *state, entry = tfind(&entry_template, &map->key_trees[i], t_compare_entry_by_nth_key); if (entry != NULL) { + if (key_index != NULL) { + *key_index = i; + } return *entry; } } @@ -207,7 +212,7 @@ map_data_find_entry(struct plugin_state *state, { struct map *map; map = map_data_find_map(state, domain_name, map_name); - return map_data_find_map_entry(state, map, key_len, key); + return map_data_find_map_entry(state, map, key_len, key, NULL); } static struct map_entry * @@ -267,8 +272,8 @@ map_data_foreach_entry(struct plugin_state *state, map->secure, entry->keys[k], entry->key_len[k], - entry->value, - entry->value_len, + entry->values[k % entry->n_values], + entry->value_len[k % entry->n_values], entry->id, k, entry->backend_data, cbdata)) { @@ -429,17 +434,18 @@ map_match(struct plugin_state *state, { struct map *map; struct map_entry *entry; + unsigned int key_index; map = map_data_find_map(state, domain_name, map_name); if (map == NULL) { return FALSE; } - entry = map_data_find_map_entry(state, map, key_len, key); + entry = map_data_find_map_entry(state, map, key_len, key, &key_index); if (entry == NULL) { return FALSE; } *secure = map->secure; - *value_len = entry->value_len; - *value = entry->value; + *value_len = entry->value_len[key_index % entry->n_values]; + *value = entry->values[key_index % entry->n_values]; *id = entry->id; if (backend_data != NULL) { *backend_data = entry->backend_data; @@ -475,8 +481,8 @@ map_match_id(struct plugin_state *state, *secure = map->secure; *key_len = entry->key_len[in_key_index]; *key = entry->keys[in_key_index]; - *value_len = entry->value_len; - *value = entry->value; + *value_len = entry->value_len[in_key_index % entry->n_values]; + *value = entry->values[in_key_index % entry->n_values]; *id = entry->id; if (backend_data != NULL) { *backend_data = entry->backend_data; @@ -507,8 +513,8 @@ map_first(struct plugin_state *state, *secure = map->secure; *first_key_len = entry->key_len[0]; *first_key = entry->keys[0]; - *first_value_len = entry->value_len; - *first_value = entry->value; + *first_value_len = entry->value_len[0]; + *first_value = entry->values[0]; *first_id = entry->id; *first_key_index = 0; return TRUE; @@ -526,35 +532,30 @@ map_next(struct plugin_state *state, { struct map *map; struct map_entry *entry; - unsigned int i; + unsigned int key_index; map = map_data_find_map(state, domain_name, map_name); if (map == NULL) { return FALSE; } - entry = map_data_find_map_entry(state, map, prev_len, prev); + entry = map_data_find_map_entry(state, map, prev_len, prev, &key_index); if (entry == NULL) { return FALSE; } *secure = map->secure; - for (i = 0; i < entry->n_keys; i++) { - if ((prev_len == entry->key_len[i]) && - (memcmp(prev, entry->keys[i], prev_len) == 0)) { - break; - } - } - if (i + 1 < entry->n_keys) { - *next_key_len = entry->key_len[i + 1]; - *next_key = entry->keys[i + 1]; - *next_value_len = entry->value_len; - *next_value = entry->value; + if (key_index + 1 < entry->n_keys) { + *next_key_len = entry->key_len[key_index + 1]; + *next_key = entry->keys[key_index + 1]; + *next_value_len = entry->value_len[(key_index + 1) % + entry->n_values]; + *next_value = entry->values[(key_index + 1) % entry->n_values]; } else { if (entry->next == NULL) { return FALSE; } *next_key_len = entry->next->key_len[0]; *next_key = entry->next->keys[0]; - *next_value_len = entry->next->value_len; - *next_value = entry->next->value; + *next_value_len = entry->next->value_len[0]; + *next_value = entry->next->values[0]; } return TRUE; } @@ -580,8 +581,10 @@ map_next_id(struct plugin_state *state, if (prev_key_index + 1 < (int) entry->n_keys) { *next_key_len = entry->key_len[prev_key_index + 1]; *next_key = entry->keys[prev_key_index + 1]; - *next_value_len = entry->value_len; - *next_value = entry->value; + *next_value_len = entry->value_len[(prev_key_index + 1) % + entry->n_values]; + *next_value = entry->values[(prev_key_index + 1) % + entry->n_values]; *next_id = entry->id; *next_key_index = prev_key_index + 1; } else { @@ -590,8 +593,8 @@ map_next_id(struct plugin_state *state, } *next_key_len = entry->next->key_len[0]; *next_key = entry->next->keys[0]; - *next_value_len = entry->next->value_len; - *next_value = entry->next->value; + *next_value_len = entry->next->value_len[0]; + *next_value = entry->next->values[0]; *next_id = entry->next->id; *next_key_index = 0; } @@ -611,6 +614,67 @@ map_data_check_entry(struct plugin_state *state, id) != NULL); } +/* Utility function for creating/updating/clearing a list of length-counted + * values kept as parallel arrays. */ +static unsigned int +map_data_save_list(char ***saved_list, unsigned int **saved_lengths, + char **list, unsigned int *lengths) +{ + char **save_list; + unsigned int *save_lengths, length, i, n; + /* Delete the old list, if there is one. */ + if (*saved_list != NULL) { + for (i = 0; (*saved_list)[i] != NULL; i++) { + free((*saved_list)[i]); + } + free(*saved_list); + *saved_list = NULL; + } + if (*saved_lengths != NULL) { + free(*saved_lengths); + *saved_lengths = NULL; + } + /* Build a copy of the passed-in list. */ + if (list != NULL) { + for (i = 0; list[i] != NULL; i++) { + continue; + } + n = i; + } else { + n = 0; + } + save_list = NULL; + save_lengths = NULL; + if (n != 0) { + save_list = malloc((n + 1) * sizeof(char *)); + save_lengths = malloc(sizeof(save_lengths[0]) * n); + if ((save_list != NULL) && (save_lengths != NULL)) { + for (i = 0; i < n; i++) { + if (lengths != NULL) { + length = lengths[i]; + } else { + length = (unsigned int) -1; + } + if (length == (unsigned int) -1) { + length = strlen(list[i]); + } + save_list[i] = xmemdup(list[i], length); + save_lengths[i] = length; + } + save_list[i] = NULL; + } else { + free(save_list); + save_list = NULL; + free(save_lengths); + save_lengths = NULL; + n = 0; + } + } + *saved_list = save_list; + *saved_lengths = save_lengths; + return n; +} + /* Remove all of the entries in a map. */ static void map_data_clear_map_map(struct plugin_state *state, struct map *map) @@ -631,14 +695,10 @@ map_data_clear_map_map(struct plugin_state *state, struct map *map) } tdelete(entry, &map->id_tree, t_compare_entry_by_id); free(entry->id); - free(entry->key_len); - entry->key_len = 0; - for (i = 0; i < entry->n_keys; i++) { - free(entry->keys[i]); - } - free(entry->keys); - entry->value_len = 0; - free(entry->value); + map_data_save_list(&entry->keys, &entry->key_len, + NULL, NULL); + map_data_save_list(&entry->values, &entry->value_len, + NULL, NULL); if ((entry->free_backend_data != NULL) && (entry->backend_data != NULL)) { entry->free_backend_data(entry->backend_data); @@ -847,28 +907,34 @@ map_data_unset_map_entry(struct plugin_state *state, map->entries = next; } /* Remove every key for this entry from the applicable key - * trees, and then the ID tree. */ + * trees. */ for (i = 0; i < entry->n_keys; i++) { entry->key_index = i; tdelete(entry, &map->key_trees[i], t_compare_entry_by_nth_key); entry->key_index = -1; } + /* Remove the ID from the map's ID tree and free the ID. */ tdelete(entry, &map->id_tree, t_compare_entry_by_id); free(entry->id); + entry->id = NULL; /* Free the keys list. */ - for (i = 0; i < entry->n_keys; i++) { - free(entry->keys[i]); - } - free(entry->keys); - free(entry->key_len); - /* The value. */ - free(entry->value); + entry->n_keys = map_data_save_list(&entry->keys, + &entry->key_len, + NULL, + NULL); + /* Free the values list. */ + entry->n_values = map_data_save_list(&entry->values, + &entry->value_len, + NULL, + NULL); /* Backend data. */ if ((entry->free_backend_data != NULL) && (entry->backend_data != NULL)) { entry->free_backend_data(entry->backend_data); } + entry->free_backend_data = NULL; + entry->backend_data = NULL; /* The entry itself. */ free(entry); } @@ -897,22 +963,29 @@ map_data_set_entry(struct plugin_state *state, const char *id, unsigned int *key_lengths, char **keys, - unsigned int value_len, - char *value, + unsigned int *value_lengths, + char **values, void *backend_data, void (*free_backend_data)(void *p)) { struct map *map; struct map_entry *entry; - unsigned int i, key_len, n_keys; + unsigned int i, key_len, n_keys, n_values; void **key_trees; - map = map_data_find_map(state, domain_name, map_name); + /* Count the number of keys and values. */ for (n_keys = 0; keys[n_keys] != NULL; n_keys++) { continue; } - if (value_len == (unsigned int) -1) { - value_len = strlen(value); + for (n_values = 0; values[n_values] != NULL; n_values++) { + continue; } + /* No keys or no values means we should remove any matching entries. */ + if ((n_keys == 0) || (n_values == 0)) { + map_data_unset_entry(state, domain_name, map_name, id); + return; + } + /* Proceed with the add/update. */ + map = map_data_find_map(state, domain_name, map_name); if (map != NULL) { if (n_keys > map->n_key_trees) { /* Create enough trees to allow us to index for all of @@ -936,114 +1009,80 @@ map_data_set_entry(struct plugin_state *state, if (entry != NULL) { /* There's already an entry with this ID, so let's * replace its keys and value. */ + /* Clear the keys from the map's key index. */ for (i = 0; i < entry->n_keys; i++) { entry->key_index = i; tdelete(entry, &map->key_trees[i], t_compare_entry_by_nth_key); entry->key_index = -1; } + /* Clear the entry's ID from the map's ID index. */ tdelete(entry, &map->id_tree, t_compare_entry_by_id); - /* Free the keys. */ - for (i = 0; i < entry->n_keys; i++) { - free(entry->keys[i]); - } - free(entry->keys); - free(entry->key_len); - /* Create a new keys list. */ - entry->keys = malloc((n_keys + 1) * sizeof(char *)); - entry->key_len = malloc(sizeof(entry->key_len[0]) * - n_keys); - if ((entry->keys != NULL) && (entry->key_len != NULL)) { - for (i = 0; i < n_keys; i++) { - if (key_lengths != NULL) { - key_len = key_lengths[i]; - } else { - key_len = (unsigned int) -1; - } - if (key_len == (unsigned int) -1) { - key_len = strlen(keys[i]); - } - entry->keys[i] = xmemdup(keys[i], - key_len); - entry->key_len[i] = key_len; - } - entry->keys[i] = NULL; - entry->n_keys = n_keys; - } else { - free(entry->keys); - entry->keys = NULL; - free(entry->key_len); - entry->key_len = NULL; - } - /* Replace the value and ID. */ - free(entry->value); + /* Replace the keys and values. */ + entry->n_keys = map_data_save_list(&entry->keys, + &entry->key_len, + keys, + key_lengths); + entry->n_values = map_data_save_list(&entry->values, + &entry->value_len, + values, + value_lengths); + /* Replace the ID. */ free(entry->id); - entry->value = xmemdup(value, value_len); - entry->value_len = value_len; entry->id = strdup(id); - /* Reset the backend data. */ - if ((entry->free_backend_data != NULL) && - (entry->backend_data != NULL)) { - entry->free_backend_data(entry->backend_data); - } - entry->backend_data = backend_data; - entry->free_backend_data = free_backend_data; - /* Add the ID to the tree and all of the keys to their - * trees. */ + /* Add the ID to the map's ID index. */ tsearch(entry, &map->id_tree, t_compare_entry_by_id); + /* Add the keys to the map's key index. */ for (i = 0; i < n_keys; i++) { entry->key_index = i; tsearch(entry, &map->key_trees[i], t_compare_entry_by_nth_key); entry->key_index = -1; } + /* Reset the backend data. */ + if ((entry->free_backend_data != NULL) && + (entry->backend_data != NULL)) { + entry->free_backend_data(entry->backend_data); + } + entry->backend_data = backend_data; + entry->free_backend_data = free_backend_data; } else { /* There's no entry with this ID, so create one. */ entry = malloc(sizeof(*entry)); if (entry != NULL) { memset(entry, 0, sizeof(*entry)); - entry->keys = malloc((n_keys + 1) * - sizeof(char *)); - entry->key_len = malloc(n_keys * sizeof(int)); - if ((entry->keys != NULL) && - (entry->key_len != NULL)) { - for (i = 0; i < n_keys; i++) { - if (key_lengths != NULL) { - key_len = - key_lengths[i]; - } else { - key_len = -1; - } - if (key_len == (unsigned int) -1) { - key_len = - strlen(keys[i]); - } - entry->keys[i] = xmemdup(keys[i], - key_len); - entry->key_len[i] = key_len; - } - entry->keys[i] = NULL; - } - entry->n_keys = n_keys; - entry->key_index = -1; - entry->value = xmemdup(value, value_len); - entry->value_len = value_len; + /* Keys and values. */ + entry->n_keys = + map_data_save_list(&entry->keys, + &entry->key_len, + keys, + key_lengths); + entry->n_values = + map_data_save_list(&entry->values, + &entry->value_len, + values, + value_lengths); + /* The entry ID. */ entry->id = strdup(id); + /* Insert the entry into the map's list. */ entry->next = map->entries; if (map->entries != NULL) { map->entries->prev = entry; } map->entries = entry; + /* Index the keys. */ for (i = 0; i < entry->n_keys; i++) { entry->key_index = i; tsearch(entry, &map->key_trees[i], t_compare_entry_by_nth_key); entry->key_index = -1; } - entry->backend_data = backend_data; - entry->free_backend_data = free_backend_data; + /* Index the ID. */ tsearch(entry, &map->id_tree, t_compare_entry_by_id); + /* Store the backend data. */ + entry->backend_data = backend_data; + entry->free_backend_data = free_backend_data; } else { /* XXX */ } diff --git a/src/map.h b/src/map.h index 1f1d85d..379751e 100644 --- a/src/map.h +++ b/src/map.h @@ -82,7 +82,7 @@ void map_data_set_entry(struct plugin_state *state, const char *domain_name, const char *map_name, const char *id, unsigned int *key_lengths, char **keys, - unsigned int value_len, char *value, + unsigned int *value_lengths, char **values, void *backend_data, void (*free_backend_data)(void *p)); bool_t map_data_check_entry(struct plugin_state *state, const char *domain_name, const char *map_name, -- cgit