From 4166dd54ebb56083bf61f8d2d4b151c0e476e22c Mon Sep 17 00:00:00 2001 From: Stephen Gallagher Date: Mon, 16 Feb 2009 15:49:54 -0500 Subject: Enhancements and bugfixes to util/btreemap.c 1) Remove useless and unused btreemap_new() 2) Fix potentially serious memory allocation error. btreemap now requires a TALLOC_CTX to be passed in for assignment to the top node of the tree. Previously it was creating a new root TALLOC_CTX 3) Add new function btreemap_get_keys that will return a sorted array (newly allocated using talloc_realloc()) of keys (const void *) 4) Change the btreemap to use (const void *) keys instead of (void *) --- server/nss/nsssrv.c | 8 ++++---- server/util/btreemap.c | 46 ++++++++++++++++++++++++++++------------------ server/util/btreemap.h | 10 ++++++---- 3 files changed, 38 insertions(+), 26 deletions(-) diff --git a/server/nss/nsssrv.c b/server/nss/nsssrv.c index fa43f60f3..5a574b416 100644 --- a/server/nss/nsssrv.c +++ b/server/nss/nsssrv.c @@ -48,7 +48,7 @@ static int service_identity(DBusMessage *message, void *data, DBusMessage **r); static int service_pong(DBusMessage *message, void *data, DBusMessage **r); static int service_reload(DBusMessage *message, void *data, DBusMessage **r); static int nss_init_domains(struct nss_ctx *nctx); -static int _domain_comparator(void *key1, void *key2); +static int _domain_comparator(const void *key1, const void *key2); struct sbus_method nss_sbus_methods[] = { {SERVICE_METHOD_IDENTITY, service_identity}, @@ -381,9 +381,9 @@ failed: /* domain names are case insensitive for now * NOTE: this function is not utf-8 safe, * only ASCII names for now */ -static int _domain_comparator(void *key1, void *key2) +static int _domain_comparator(const void *key1, const void *key2) { - return strcasecmp((char *)key1, (char *)key2); + return strcasecmp((const char *)key1, (const char *)key2); } static int nss_init_domains(struct nss_ctx *nctx) @@ -407,7 +407,7 @@ static int nss_init_domains(struct nss_ctx *nctx) /* Look up the appropriate basedn for this domain */ ret = confdb_get_domain_basedn(nctx->cdb, tmp_ctx, domains[i], &basedn); DEBUG(3, ("BaseDN: %s\n", basedn)); - btreemap_set_value(&nctx->domain_map, domains[i], basedn, _domain_comparator); + btreemap_set_value(nctx, &nctx->domain_map, domains[i], basedn, _domain_comparator); i++; } if (i == 0) { diff --git a/server/util/btreemap.c b/server/util/btreemap.c index 15cf7b5a3..9eed2eb1f 100644 --- a/server/util/btreemap.c +++ b/server/util/btreemap.c @@ -26,7 +26,7 @@ struct btreemap { /* NULL keys are not allowed */ - void *key; + const void *key; /* NULL values are permitted */ void *value; @@ -50,7 +50,7 @@ struct btreemap * BTREEMAP_CREATE_LEFT: A new node created should use node->left * BTREEMAP_CREATE_RIGHT: A new node created should use node->right */ -int btreemap_search_key(struct btreemap *map, void *key, struct btreemap **node) +int btreemap_search_key(struct btreemap *map, const void *key, struct btreemap **node) { struct btreemap *tempnode; int result; @@ -92,7 +92,7 @@ int btreemap_search_key(struct btreemap *map, void *key, struct btreemap **node) return found; } -void *btreemap_get_value(struct btreemap *map, void *key) +void *btreemap_get_value(struct btreemap *map, const void *key) { struct btreemap *node; int found; @@ -113,7 +113,11 @@ void *btreemap_get_value(struct btreemap *map, void *key) return NULL; } -int btreemap_set_value(struct btreemap **map, void *key, void *value, +/* Keys and values must be talloc contexts + * comparator must return -1, 0 or 1 + */ +int btreemap_set_value(TALLOC_CTX *mem_ctx, + struct btreemap **map, const void *key, void *value, btreemap_comparison_fn comparator) { struct btreemap *node; @@ -127,6 +131,7 @@ int btreemap_set_value(struct btreemap **map, void *key, void *value, /* Search for the key */ found = btreemap_search_key(*map, key, &node); + if (found == BTREEMAP_FOUND) { /* Update existing value */ @@ -135,15 +140,17 @@ int btreemap_set_value(struct btreemap **map, void *key, void *value, } /* Need to add a value to the tree */ - new_node = talloc_zero(node, struct btreemap); + new_node = talloc_zero(mem_ctx, struct btreemap); + if (!new_node) { return ENOMEM; } - new_node->key = talloc_steal(*map, key); - new_node->value = talloc_steal(*map, value); + new_node->key = talloc_steal(new_node, key); + new_node->value = talloc_steal(new_node, value); new_node->comparator = comparator; + if (found == BTREEMAP_EMPTY) { *map = new_node; @@ -158,18 +165,21 @@ int btreemap_set_value(struct btreemap **map, void *key, void *value, return EOK; } -struct btreemap *btreemap_new(void *key, void *value, - btreemap_comparison_fn comparator) +/* Return an array of keys in sort order + * count should be initialized to zero before calling this function. + */ +void btreemap_get_keys(TALLOC_CTX *mem_ctx, struct btreemap *map, const void ***array, int *count) { - struct btreemap *map; - int result; + if (map == NULL) return; - map = NULL; - result = btreemap_set_value(&map, key, value, comparator); - if (result != EOK) - { - return NULL; - } + /* Left Node */ + btreemap_get_keys(mem_ctx, map->left, array, count); + + /* Current Node */ + (*count)++; + *array = talloc_realloc(mem_ctx, *array, const void *, *count); + (*array)[(*count)-1] = map->key; - return map; + /* Right Node */ + btreemap_get_keys(mem_ctx, map->right, array, count); } diff --git a/server/util/btreemap.h b/server/util/btreemap.h index 941e36e5b..c5c415075 100644 --- a/server/util/btreemap.h +++ b/server/util/btreemap.h @@ -28,12 +28,14 @@ enum { BTREEMAP_CREATE_RIGHT }; -typedef int (*btreemap_comparison_fn)(void *first, void *second); +typedef int (*btreemap_comparison_fn)(const void *first, const void *second); struct btreemap; -int btreemap_search_key(struct btreemap *map, void *key, struct btreemap **node); -void *btreemap_get_value(struct btreemap *map, void *key); -int btreemap_set_value(struct btreemap **map, void *key, void *value, +int btreemap_search_key(struct btreemap *map, const void *key, struct btreemap **node); +void *btreemap_get_value(struct btreemap *map, const void *key); +int btreemap_set_value(TALLOC_CTX *mem_ctx, + struct btreemap **map, const void *key, void *value, btreemap_comparison_fn comparator); +void btreemap_get_keys(TALLOC_CTX *mem_ctx, struct btreemap *map, const void ***array, int *count); #endif /*BTREEMAP_H_*/ -- cgit