lib/sset.c

   1 /*
   2  * Copyright (c) 2011, 2012, 2013, 2015, 2016 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 "hash.h"
  22
  23 static uint32_t
  24 hash_name__(const char *name, size_t length)
  25 {
  26     return hash_bytes(name, length, 0);
  27 }
  28
  29 static uint32_t
  30 hash_name(const char *name)
  31 {
  32     return hash_name__(name, strlen(name));
  33 }
  34
  35 static struct sset_node *
  36 sset_find__(const struct sset *set, const char *name, size_t hash)
  37 {
  38     struct sset_node *node;
  39
  40     HMAP_FOR_EACH_WITH_HASH (node, hmap_node, hash, &set->map) {
  41         if (!strcmp(node->name, name)) {
  42             return node;
  43         }
  44     }
  45     return NULL;
  46 }
  47
  48 static struct sset_node *
  49 sset_add__(struct sset *set, const char *name, size_t length, size_t hash)
  50 {
  51     struct sset_node *node = xmalloc(length + sizeof *node);
  52     memcpy(node->name, name, length + 1);
  53     hmap_insert(&set->map, &node->hmap_node, hash);
  54     return node;
  55 }
  56
  57 /* Initializes 'set' as an empty set of strings. */
  58 void
  59 sset_init(struct sset *set)
  60 {
  61     hmap_init(&set->map);
  62 }
  63
  64 /* Destroys 'sets'. */
  65 void
  66 sset_destroy(struct sset *set)
  67 {
  68     if (set) {
  69         sset_clear(set);
  70         hmap_destroy(&set->map);
  71     }
  72 }
  73
  74 /* Initializes 'set' to contain the same strings as 'orig'. */
  75 void
  76 sset_clone(struct sset *set, const struct sset *orig)
  77 {
  78     struct sset_node *node;
  79
  80     sset_init(set);
  81     HMAP_FOR_EACH (node, hmap_node, &orig->map) {
  82         sset_add__(set, node->name, strlen(node->name),
  83                    node->hmap_node.hash);
  84     }
  85 }
  86
  87 /* Exchanges the contents of 'a' and 'b'. */
  88 void
  89 sset_swap(struct sset *a, struct sset *b)
  90 {
  91     hmap_swap(&a->map, &b->map);
  92 }
  93
  94 /* Adjusts 'set' so that it is still valid after it has been moved around in
  95  * memory (e.g. due to realloc()). */
  96 void
  97 sset_moved(struct sset *set)
  98 {
  99     hmap_moved(&set->map);
 100 }
 101
 102 /* Initializes 'set' with substrings of 's' that are delimited by any of the
 103  * characters in 'delimiters'.  For example,
 104  *     sset_from_delimited_string(&set, "a b,c", " ,");
 105  * initializes 'set' with three strings "a", "b", and "c". */
 106 void
 107 sset_from_delimited_string(struct sset *set, const char *s_,
 108                            const char *delimiters)
 109 {
 110     sset_init(set);
 111
 112     char *s = xstrdup(s_);
 113     char *token, *save_ptr = NULL;
 114     for (token = strtok_r(s, delimiters, &save_ptr); token != NULL;
 115          token = strtok_r(NULL, delimiters, &save_ptr)) {
 116         sset_add(set, token);
 117     }
 118     free(s);
 119 }
 120
 121 /* Returns true if 'set' contains no strings, false if it contains at least one
 122  * string. */
 123 bool
 124 sset_is_empty(const struct sset *set)
 125 {
 126     return hmap_is_empty(&set->map);
 127 }
 128
 129 /* Returns the number of strings in 'set'. */
 130 size_t
 131 sset_count(const struct sset *set)
 132 {
 133     return hmap_count(&set->map);
 134 }
 135
 136 /* Adds 'name' to 'set'.  If 'name' is new, returns the new sset_node;
 137  * otherwise (if a copy of 'name' already existed in 'set'), returns NULL. */
 138 struct sset_node *
 139 sset_add(struct sset *set, const char *name)
 140 {
 141     size_t length = strlen(name);
 142     uint32_t hash = hash_name__(name, length);
 143
 144     return (sset_find__(set, name, hash)
 145             ? NULL
 146             : sset_add__(set, name, length, hash));
 147 }
 148
 149 /* Adds a copy of 'name' to 'set' and frees 'name'.
 150  *
 151  * If 'name' is new, returns the new sset_node; otherwise (if a copy of 'name'
 152  * already existed in 'set'), returns NULL. */
 153 struct sset_node *
 154 sset_add_and_free(struct sset *set, char *name)
 155 {
 156     struct sset_node *node = sset_add(set, name);
 157     free(name);
 158     return node;
 159 }
 160
 161 /* Adds 'name' to 'set'.  Assert-fails if a copy of 'name' was already in
 162  * 'set'. */
 163 void
 164 sset_add_assert(struct sset *set, const char *name)
 165 {
 166     bool added OVS_UNUSED = sset_add(set, name);
 167     ovs_assert(added);
 168 }
 169
 170 /* Adds a copy of each of the 'n' names in 'names' to 'set'. */
 171 void
 172 sset_add_array(struct sset *set, char **names, size_t n)
 173 {
 174     size_t i;
 175
 176     for (i = 0; i < n; i++) {
 177         sset_add(set, names[i]);
 178     }
 179 }
 180
 181 /* Removes all of the strings from 'set'. */
 182 void
 183 sset_clear(struct sset *set)
 184 {
 185     const char *name, *next;
 186
 187     SSET_FOR_EACH_SAFE (name, next, set) {
 188         sset_delete(set, SSET_NODE_FROM_NAME(name));
 189     }
 190 }
 191
 192 /* Deletes 'node' from 'set' and frees 'node'. */
 193 void
 194 sset_delete(struct sset *set, struct sset_node *node)
 195 {
 196     hmap_remove(&set->map, &node->hmap_node);
 197     free(node);
 198 }
 199
 200 /* Searches for 'name' in 'set'.  If found, deletes it and returns true.  If
 201  * not found, returns false without modifying 'set'. */
 202 bool
 203 sset_find_and_delete(struct sset *set, const char *name)
 204 {
 205     struct sset_node *node = sset_find(set, name);
 206     if (node) {
 207         sset_delete(set, node);
 208     }
 209     return node != NULL;
 210 }
 211
 212 /* Searches for 'name' in 'set' and deletes it.  Assert-fails if 'name' is not
 213  * in 'set'. */
 214 void
 215 sset_find_and_delete_assert(struct sset *set, const char *name)
 216 {
 217     bool deleted OVS_UNUSED = sset_find_and_delete(set, name);
 218     ovs_assert(deleted);
 219 }
 220
 221 /* Removes a string from 'set' and returns a copy of it.  The caller must free
 222  * the returned string (with free()).
 223  *
 224  * 'set' must not be empty.
 225  *
 226  * This is not a very good way to iterate through an sset: it copies each name
 227  * and it takes O(n**2) time to remove all the names.  Use SSET_FOR_EACH_SAFE
 228  * instead, if you can. */
 229 char *
 230 sset_pop(struct sset *set)
 231 {
 232     const char *name = SSET_FIRST(set);
 233     char *copy = xstrdup(name);
 234     sset_delete(set, SSET_NODE_FROM_NAME(name));
 235     return copy;
 236 }
 237
 238 /* Searches for 'name' in 'set'.  Returns its node, if found, otherwise a null
 239  * pointer. */
 240 struct sset_node *
 241 sset_find(const struct sset *set, const char *name)
 242 {
 243     return sset_find__(set, name, hash_name(name));
 244 }
 245
 246 /* Returns true if 'set' contains a copy of 'name', false otherwise. */
 247 bool
 248 sset_contains(const struct sset *set, const char *name)
 249 {
 250     return sset_find(set, name) != NULL;
 251 }
 252
 253 /* Returns true if 'a' and 'b' contain the same strings, false otherwise. */
 254 bool
 255 sset_equals(const struct sset *a, const struct sset *b)
 256 {
 257     struct sset_node *node;
 258
 259     if (sset_count(a) != sset_count(b)) {
 260         return false;
 261     }
 262
 263     HMAP_FOR_EACH (node, hmap_node, &a->map) {
 264         if (!sset_find__(b, node->name, node->hmap_node.hash)) {
 265             return false;
 266         }
 267     }
 268
 269     return true;
 270 }
 271
 272 /* Returns the next node in 'set' in hash order, or NULL if no nodes remain in
 273  * 'set'.  Uses '*pos' to determine where to begin iteration, and updates
 274  * '*pos' to pass on the next iteration into them before returning.
 275  *
 276  * It's better to use plain SSET_FOR_EACH and related functions, since they are
 277  * faster and better at dealing with ssets that change during iteration.
 278  *
 279  * Before beginning iteration, set '*pos' to all zeros. */
 280 struct sset_node *
 281 sset_at_position(const struct sset *set, struct sset_position *pos)
 282 {
 283     struct hmap_node *hmap_node;
 284
 285     hmap_node = hmap_at_position(&set->map, &pos->pos);
 286     return SSET_NODE_FROM_HMAP_NODE(hmap_node);
 287 }
 288
 289 /* Replaces 'a' by the intersection of 'a' and 'b'.  That is, removes from 'a'
 290  * all of the strings that are not also in 'b'. */
 291 void
 292 sset_intersect(struct sset *a, const struct sset *b)
 293 {
 294     const char *name, *next;
 295
 296     SSET_FOR_EACH_SAFE (name, next, a) {
 297         if (!sset_contains(b, name)) {
 298             sset_delete(a, SSET_NODE_FROM_NAME(name));
 299         }
 300     }
 301 }
 302
 303 /* Returns a null-terminated array of pointers to the strings in 'set', in no
 304  * particular order.  The caller must free the returned array when it is no
 305  * longer needed, but the strings in the array belong to 'set' and thus must
 306  * not be modified or freed. */
 307 const char **
 308 sset_array(const struct sset *set)
 309 {
 310     size_t n = sset_count(set);
 311     const char **array;
 312     const char *s;
 313     size_t i;
 314
 315     array = xmalloc(sizeof *array * (n + 1));
 316     i = 0;
 317     SSET_FOR_EACH (s, set) {
 318         array[i++] = s;
 319     }
 320     ovs_assert(i == n);
 321     array[n] = NULL;
 322
 323     return array;
 324 }
 325
 326 static int
 327 compare_string_pointers(const void *a_, const void *b_)
 328 {
 329     const char *const *a = a_;
 330     const char *const *b = b_;
 331
 332     return strcmp(*a, *b);
 333 }
 334
 335 /* Returns a null-terminated array of pointers to the strings in 'set', sorted
 336  * alphabetically.  The caller must free the returned array when it is no
 337  * longer needed, but the strings in the array belong to 'set' and thus must
 338  * not be modified or freed. */
 339 const char **
 340 sset_sort(const struct sset *set)
 341 {
 342     const char **array = sset_array(set);
 343     qsort(array, sset_count(set), sizeof *array, compare_string_pointers);
 344     return array;
 345 }