lib/sset.c

   1 /*
   2  * Copyright (c) 2011 Nicira, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include <config.h>
  18
  19 #include "sset.h"
  20
  21 #include <assert.h>
  22
  23 #include "hash.h"
  24
  25 static uint32_t
  26 hash_name__(const char *name, size_t length)
  27 {
  28     return hash_bytes(name, length, 0);
  29 }
  30
  31 static uint32_t
  32 hash_name(const char *name)
  33 {
  34     return hash_name__(name, strlen(name));
  35 }
  36
  37 static struct sset_node *
  38 sset_find__(const struct sset *set, const char *name, size_t hash)
  39 {
  40     struct sset_node *node;
  41
  42     HMAP_FOR_EACH_WITH_HASH (node, hmap_node, hash, &set->map) {
  43         if (!strcmp(node->name, name)) {
  44             return node;
  45         }
  46     }
  47     return NULL;
  48 }
  49
  50 static struct sset_node *
  51 sset_add__(struct sset *set, const char *name, size_t length, size_t hash)
  52 {
  53     struct sset_node *node = xmalloc(length + sizeof *node);
  54     memcpy(node->name, name, length + 1);
  55     hmap_insert(&set->map, &node->hmap_node, hash);
  56     return node;
  57 }
  58
  59 /* Initializes 'set' as an empty set of strings. */
  60 void
  61 sset_init(struct sset *set)
  62 {
  63     hmap_init(&set->map);
  64 }
  65
  66 /* Destroys 'sets'. */
  67 void
  68 sset_destroy(struct sset *set)
  69 {
  70     if (set) {
  71         sset_clear(set);
  72         hmap_destroy(&set->map);
  73     }
  74 }
  75
  76 /* Initializes 'set' to contain the same strings as 'orig'. */
  77 void
  78 sset_clone(struct sset *set, const struct sset *orig)
  79 {
  80     struct sset_node *node;
  81
  82     sset_init(set);
  83     HMAP_FOR_EACH (node, hmap_node, &orig->map) {
  84         sset_add__(set, node->name, strlen(node->name),
  85                    node->hmap_node.hash);
  86     }
  87 }
  88
  89 /* Exchanges the contents of 'a' and 'b'. */
  90 void
  91 sset_swap(struct sset *a, struct sset *b)
  92 {
  93     hmap_swap(&a->map, &b->map);
  94 }
  95
  96 /* Adjusts 'set' so that it is still valid after it has been moved around in
  97  * memory (e.g. due to realloc()). */
  98 void
  99 sset_moved(struct sset *set)
 100 {
 101     hmap_moved(&set->map);
 102 }
 103
 104 /* Returns true if 'set' contains no strings, false if it contains at least one
 105  * string. */
 106 bool
 107 sset_is_empty(const struct sset *set)
 108 {
 109     return hmap_is_empty(&set->map);
 110 }
 111
 112 /* Returns the number of strings in 'set'. */
 113 size_t
 114 sset_count(const struct sset *set)
 115 {
 116     return hmap_count(&set->map);
 117 }
 118
 119 /* Adds 'name' to 'set'.  If 'name' is new, returns the new sset_node;
 120  * otherwise (if a copy of 'name' already existed in 'set'), returns NULL. */
 121 struct sset_node *
 122 sset_add(struct sset *set, const char *name)
 123 {
 124     size_t length = strlen(name);
 125     uint32_t hash = hash_name__(name, length);
 126
 127     return (sset_find__(set, name, hash)
 128             ? NULL
 129             : sset_add__(set, name, length, hash));
 130 }
 131
 132 /* Adds a copy of 'name' to 'set' and frees 'name'.
 133  *
 134  * If 'name' is new, returns the new sset_node; otherwise (if a copy of 'name'
 135  * already existed in 'set'), returns NULL. */
 136 struct sset_node *
 137 sset_add_and_free(struct sset *set, char *name)
 138 {
 139     struct sset_node *node = sset_add(set, name);
 140     free(name);
 141     return node;
 142 }
 143
 144 /* Adds 'name' to 'set'.  Assert-fails if a copy of 'name' was already in
 145  * 'set'. */
 146 void
 147 sset_add_assert(struct sset *set, const char *name)
 148 {
 149     bool added OVS_UNUSED = sset_add(set, name);
 150     assert(added);
 151 }
 152
 153 /* Adds a copy of each of the 'n' names in 'names' to 'set'. */
 154 void
 155 sset_add_array(struct sset *set, char **names, size_t n)
 156 {
 157     size_t i;
 158
 159     for (i = 0; i < n; i++) {
 160         sset_add(set, names[i]);
 161     }
 162 }
 163
 164 /* Removes all of the strings from 'set'. */
 165 void
 166 sset_clear(struct sset *set)
 167 {
 168     const char *name, *next;
 169
 170     SSET_FOR_EACH_SAFE (name, next, set) {
 171         sset_delete(set, SSET_NODE_FROM_NAME(name));
 172     }
 173 }
 174
 175 /* Deletes 'node' from 'set' and frees 'node'. */
 176 void
 177 sset_delete(struct sset *set, struct sset_node *node)
 178 {
 179     hmap_remove(&set->map, &node->hmap_node);
 180     free(node);
 181 }
 182
 183 /* Searches for 'name' in 'set'.  If found, deletes it and returns true.  If
 184  * not found, returns false without modifying 'set'. */
 185 bool
 186 sset_find_and_delete(struct sset *set, const char *name)
 187 {
 188     struct sset_node *node = sset_find(set, name);
 189     if (node) {
 190         sset_delete(set, node);
 191     }
 192     return node != NULL;
 193 }
 194
 195 /* Searches for 'name' in 'set' and deletes it.  Assert-fails if 'name' is not
 196  * in 'set'. */
 197 void
 198 sset_find_and_delete_assert(struct sset *set, const char *name)
 199 {
 200     bool deleted OVS_UNUSED = sset_find_and_delete(set, name);
 201     assert(deleted);
 202 }
 203
 204 /* Removes a string from 'set' and returns a copy of it.  The caller must free
 205  * the returned string (with free()).
 206  *
 207  * 'set' must not be empty.
 208  *
 209  * This is not a very good way to iterate through an sset: it copies each name
 210  * and it takes O(n**2) time to remove all the names.  Use SSET_FOR_EACH_SAFE
 211  * instead, if you can. */
 212 char *
 213 sset_pop(struct sset *set)
 214 {
 215     const char *name = SSET_FIRST(set);
 216     char *copy = xstrdup(name);
 217     sset_delete(set, SSET_NODE_FROM_NAME(name));
 218     return copy;
 219 }
 220
 221 /* Searches for 'name' in 'set'.  Returns its node, if found, otherwise a null
 222  * pointer. */
 223 struct sset_node *
 224 sset_find(const struct sset *set, const char *name)
 225 {
 226     return sset_find__(set, name, hash_name(name));
 227 }
 228
 229 /* Returns true if 'set' contains a copy of 'name', false otherwise. */
 230 bool
 231 sset_contains(const struct sset *set, const char *name)
 232 {
 233     return sset_find(set, name) != NULL;
 234 }
 235
 236 /* Returns true if 'a' and 'b' contain the same strings, false otherwise. */
 237 bool
 238 sset_equals(const struct sset *a, const struct sset *b)
 239 {
 240     struct sset_node *node;
 241
 242     if (sset_count(a) != sset_count(b)) {
 243         return false;
 244     }
 245
 246     HMAP_FOR_EACH (node, hmap_node, &a->map) {
 247         if (!sset_find__(b, node->name, node->hmap_node.hash)) {
 248             return false;
 249         }
 250     }
 251
 252     return true;
 253 }
 254
 255 /* Returns the next node in 'set' in hash order, or NULL if no nodes remain in
 256  * 'set'.  Uses '*bucketp' and '*offsetp' to determine where to begin
 257  * iteration, and stores new values to pass on the next iteration into them
 258  * before returning.
 259  *
 260  * It's better to use plain SSET_FOR_EACH and related functions, since they are
 261  * faster and better at dealing with ssets that change during iteration.
 262  *
 263  * Before beginning iteration, store 0 into '*bucketp' and '*offsetp'.
 264  */
 265 struct sset_node *
 266 sset_at_position(const struct sset *set, uint32_t *bucketp, uint32_t *offsetp)
 267 {
 268     struct hmap_node *hmap_node;
 269
 270     hmap_node = hmap_at_position(&set->map, bucketp, offsetp);
 271     return SSET_NODE_FROM_HMAP_NODE(hmap_node);
 272 }