X-Git-Url: http://git.onelab.eu/?a=blobdiff_plain;f=lib%2Fshash.c;h=3269a4108c38474dd703f34580a7fd2ec749255a;hb=6da1e8091eb2e19de7ba5e0c73ac3e7dd437743d;hp=caac460e9da9fb185be66194f61f894ce1a5ab67;hpb=4a1ee6ae821f73c877af1548d6db9a0e04ad8eaf;p=sliver-openvswitch.git diff --git a/lib/shash.c b/lib/shash.c index caac460e9..3269a4108 100644 --- a/lib/shash.c +++ b/lib/shash.c @@ -19,6 +19,9 @@ #include #include "hash.h" +static struct shash_node *shash_find__(const struct shash *, + const char *name, size_t hash); + static size_t hash_name(const char *name) { @@ -40,6 +43,16 @@ shash_destroy(struct shash *sh) } } +/* Like shash_destroy(), but also free() each node's 'data'. */ +void +shash_destroy_free_data(struct shash *sh) +{ + if (sh) { + shash_clear_free_data(sh); + hmap_destroy(&sh->map); + } +} + void shash_swap(struct shash *a, struct shash *b) { @@ -64,6 +77,20 @@ shash_clear(struct shash *sh) } } +/* Like shash_clear(), but also free() each node's 'data'. */ +void +shash_clear_free_data(struct shash *sh) +{ + struct shash_node *node, *next; + + SHASH_FOR_EACH_SAFE (node, next, sh) { + hmap_remove(&sh->map, &node->node); + free(node->data); + free(node->name); + free(node); + } +} + bool shash_is_empty(const struct shash *shash) { @@ -76,16 +103,30 @@ shash_count(const struct shash *shash) return hmap_count(&shash->map); } +static struct shash_node * +shash_add_nocopy__(struct shash *sh, char *name, const void *data, size_t hash) +{ + struct shash_node *node = xmalloc(sizeof *node); + node->name = name; + node->data = (void *) data; + hmap_insert(&sh->map, &node->node, hash); + return node; +} + +/* It is the caller's responsibility to avoid duplicate names, if that is + * desirable. */ +struct shash_node * +shash_add_nocopy(struct shash *sh, char *name, const void *data) +{ + return shash_add_nocopy__(sh, name, data, hash_name(name)); +} + /* It is the caller's responsibility to avoid duplicate names, if that is * desirable. */ struct shash_node * shash_add(struct shash *sh, const char *name, const void *data) { - struct shash_node *node = xmalloc(sizeof *node); - node->name = xstrdup(name); - node->data = (void *) data; - hmap_insert(&sh->map, &node->node, hash_name(name)); - return node; + return shash_add_nocopy(sh, xstrdup(name), data); } bool @@ -106,22 +147,53 @@ shash_add_assert(struct shash *sh, const char *name, const void *data) assert(added); } +/* Searches for 'name' in 'sh'. If it does not already exist, adds it along + * with 'data' and returns NULL. If it does already exist, replaces its data + * by 'data' and returns the data that it formerly contained. */ +void * +shash_replace(struct shash *sh, const char *name, const void *data) +{ + size_t hash = hash_name(name); + struct shash_node *node; + + node = shash_find__(sh, name, hash); + if (!node) { + shash_add_nocopy__(sh, xstrdup(name), data, hash); + return NULL; + } else { + void *old_data = node->data; + node->data = (void *) data; + return old_data; + } +} + +/* Deletes 'node' from 'sh' and frees the node's name. The caller is still + * responsible for freeing the node's data, if necessary. */ void shash_delete(struct shash *sh, struct shash_node *node) { + free(shash_steal(sh, node)); +} + +/* Deletes 'node' from 'sh'. Neither the node's name nor its data is freed; + * instead, ownership is transferred to the caller. Returns the node's + * name. */ +char * +shash_steal(struct shash *sh, struct shash_node *node) +{ + char *name = node->name; + hmap_remove(&sh->map, &node->node); - free(node->name); free(node); + return name; } -/* If there are duplicates, returns a random element. */ -struct shash_node * -shash_find(const struct shash *sh, const char *name) +static struct shash_node * +shash_find__(const struct shash *sh, const char *name, size_t hash) { struct shash_node *node; - HMAP_FOR_EACH_WITH_HASH (node, struct shash_node, node, - hash_name(name), &sh->map) { + HMAP_FOR_EACH_WITH_HASH (node, node, hash, &sh->map) { if (!strcmp(node->name, name)) { return node; } @@ -129,6 +201,13 @@ shash_find(const struct shash *sh, const char *name) return NULL; } +/* If there are duplicates, returns a random element. */ +struct shash_node * +shash_find(const struct shash *sh, const char *name) +{ + return shash_find__(sh, name, hash_name(name)); +} + void * shash_find_data(const struct shash *sh, const char *name) { @@ -213,3 +292,68 @@ shash_equal_keys(const struct shash *a, const struct shash *b) } return true; } + +/* Chooses and returns a randomly selected node from 'sh', which must not be + * empty. + * + * I wouldn't depend on this algorithm to be fair, since I haven't analyzed it. + * But it does at least ensure that any node in 'sh' can be chosen. */ +struct shash_node * +shash_random_node(struct shash *sh) +{ + return CONTAINER_OF(hmap_random_node(&sh->map), struct shash_node, node); +} + +/* String-to-string maps (smaps). */ + +/* Frees 'smap', including its keys and string values. */ +void +smap_destroy(struct shash *smap) +{ + shash_destroy_free_data(smap); +} + +/* Returns true if string-to-string maps 'a' and 'b' contain the same keys and + * values, false otherwise. */ +bool +smap_equal(const struct shash *a, const struct shash *b) +{ + struct shash_node *a_node; + + if (shash_count(a) != shash_count(b)) { + return false; + } + + SHASH_FOR_EACH (a_node, a) { + uint32_t hash = a_node->node.hash; + struct shash_node *b_node = shash_find__(b, a_node->name, hash); + if (!b_node || strcmp(a_node->data, b_node->data)) { + return false; + } + } + + return true; +} + +/* Initializes 'dst' as a clone of 'src'. */ +void +smap_clone(struct shash *dst, const struct shash *src) +{ + struct shash_node *node; + + shash_init(dst); + SHASH_FOR_EACH (node, src) { + shash_add_nocopy__(dst, xstrdup(node->name), xstrdup(node->data), + node->node.hash); + } +} + +/* Adds 'key' with string 'value' to 'smap', making a copy of each. + * + * It is the caller's responsibility to avoid duplicate names, if that is + * desirable. */ +void +smap_add(struct shash *smap, const char *key, const char *value) +{ + shash_add(smap, key, xstrdup(value)); +}