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     ovs_assert(sset_add(set, name));
 167 }
 168
 169 /* Adds a copy of each of the 'n' names in 'names' to 'set'. */
 170 void
 171 sset_add_array(struct sset *set, char **names, size_t n)
 172 {
 173     size_t i;
 174
 175     for (i = 0; i < n; i++) {
 176         sset_add(set, names[i]);
 177     }
 178 }
 179
 180 /* Removes all of the strings from 'set'. */
 181 void
 182 sset_clear(struct sset *set)
 183 {
 184     const char *name, *next;
 185
 186     SSET_FOR_EACH_SAFE (name, next, set) {
 187         sset_delete(set, SSET_NODE_FROM_NAME(name));
 188     }
 189 }
 190
 191 /* Deletes 'node' from 'set' and frees 'node'. */
 192 void
 193 sset_delete(struct sset *set, struct sset_node *node)
 194 {
 195     hmap_remove(&set->map, &node->hmap_node);
 196     free(node);
 197 }
 198
 199 /* Searches for 'name' in 'set'.  If found, deletes it and returns true.  If
 200  * not found, returns false without modifying 'set'. */
 201 bool
 202 sset_find_and_delete(struct sset *set, const char *name)
 203 {
 204     struct sset_node *node = sset_find(set, name);
 205     if (node) {
 206         sset_delete(set, node);
 207     }
 208     return node != NULL;
 209 }
 210
 211 /* Searches for 'name' in 'set' and deletes it.  Assert-fails if 'name' is not
 212  * in 'set'. */
 213 void
 214 sset_find_and_delete_assert(struct sset *set, const char *name)
 215 {
 216     ovs_assert(sset_find_and_delete(set, name));
 217 }
 218
 219 /* Removes a string from 'set' and returns a copy of it.  The caller must free
 220  * the returned string (with free()).
 221  *
 222  * 'set' must not be empty.
 223  *
 224  * This is not a very good way to iterate through an sset: it copies each name
 225  * and it takes O(n**2) time to remove all the names.  Use SSET_FOR_EACH_SAFE
 226  * instead, if you can. */
 227 char *
 228 sset_pop(struct sset *set)
 229 {
 230     const char *name = SSET_FIRST(set);
 231     char *copy = xstrdup(name);
 232     sset_delete(set, SSET_NODE_FROM_NAME(name));
 233     return copy;
 234 }
 235
 236 /* Searches for 'name' in 'set'.  Returns its node, if found, otherwise a null
 237  * pointer. */
 238 struct sset_node *
 239 sset_find(const struct sset *set, const char *name)
 240 {
 241     return sset_find__(set, name, hash_name(name));
 242 }
 243
 244 /* Returns true if 'set' contains a copy of 'name', false otherwise. */
 245 bool
 246 sset_contains(const struct sset *set, const char *name)
 247 {
 248     return sset_find(set, name) != NULL;
 249 }
 250
 251 /* Returns true if 'a' and 'b' contain the same strings, false otherwise. */
 252 bool
 253 sset_equals(const struct sset *a, const struct sset *b)
 254 {
 255     struct sset_node *node;
 256
 257     if (sset_count(a) != sset_count(b)) {
 258         return false;
 259     }
 260
 261     HMAP_FOR_EACH (node, hmap_node, &a->map) {
 262         if (!sset_find__(b, node->name, node->hmap_node.hash)) {
 263             return false;
 264         }
 265     }
 266
 267     return true;
 268 }
 269
 270 /* Returns the next node in 'set' in hash order, or NULL if no nodes remain in
 271  * 'set'.  Uses '*pos' to determine where to begin iteration, and updates
 272  * '*pos' to pass on the next iteration into them before returning.
 273  *
 274  * It's better to use plain SSET_FOR_EACH and related functions, since they are
 275  * faster and better at dealing with ssets that change during iteration.
 276  *
 277  * Before beginning iteration, set '*pos' to all zeros. */
 278 struct sset_node *
 279 sset_at_position(const struct sset *set, struct sset_position *pos)
 280 {
 281     struct hmap_node *hmap_node;
 282
 283     hmap_node = hmap_at_position(&set->map, &pos->pos);
 284     return SSET_NODE_FROM_HMAP_NODE(hmap_node);
 285 }
 286
 287 /* Replaces 'a' by the intersection of 'a' and 'b'.  That is, removes from 'a'
 288  * all of the strings that are not also in 'b'. */
 289 void
 290 sset_intersect(struct sset *a, const struct sset *b)
 291 {
 292     const char *name, *next;
 293
 294     SSET_FOR_EACH_SAFE (name, next, a) {
 295         if (!sset_contains(b, name)) {
 296             sset_delete(a, SSET_NODE_FROM_NAME(name));
 297         }
 298     }
 299 }
 300
 301 /* Returns a null-terminated array of pointers to the strings in 'set', in no
 302  * particular order.  The caller must free the returned array when it is no
 303  * longer needed, but the strings in the array belong to 'set' and thus must
 304  * not be modified or freed. */
 305 const char **
 306 sset_array(const struct sset *set)
 307 {
 308     size_t n = sset_count(set);
 309     const char **array;
 310     const char *s;
 311     size_t i;
 312
 313     array = xmalloc(sizeof *array * (n + 1));
 314     i = 0;
 315     SSET_FOR_EACH (s, set) {
 316         array[i++] = s;
 317     }
 318     ovs_assert(i == n);
 319     array[n] = NULL;
 320
 321     return array;
 322 }
 323
 324 static int
 325 compare_string_pointers(const void *a_, const void *b_)
 326 {
 327     const char *const *a = a_;
 328     const char *const *b = b_;
 329
 330     return strcmp(*a, *b);
 331 }
 332
 333 /* Returns a null-terminated array of pointers to the strings in 'set', sorted
 334  * alphabetically.  The caller must free the returned array when it is no
 335  * longer needed, but the strings in the array belong to 'set' and thus must
 336  * not be modified or freed. */
 337 const char **
 338 sset_sort(const struct sset *set)
 339 {
 340     const char **array = sset_array(set);
 341     qsort(array, sset_count(set), sizeof *array, compare_string_pointers);
 342     return array;
 343 }