lib/sset.c

   1 /*
   2  * Copyright (c) 2011, 2012, 2013, 2015 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 /* Returns true if 'set' contains no strings, false if it contains at least one
 103  * string. */
 104 bool
 105 sset_is_empty(const struct sset *set)
 106 {
 107     return hmap_is_empty(&set->map);
 108 }
 109
 110 /* Returns the number of strings in 'set'. */
 111 size_t
 112 sset_count(const struct sset *set)
 113 {
 114     return hmap_count(&set->map);
 115 }
 116
 117 /* Adds 'name' to 'set'.  If 'name' is new, returns the new sset_node;
 118  * otherwise (if a copy of 'name' already existed in 'set'), returns NULL. */
 119 struct sset_node *
 120 sset_add(struct sset *set, const char *name)
 121 {
 122     size_t length = strlen(name);
 123     uint32_t hash = hash_name__(name, length);
 124
 125     return (sset_find__(set, name, hash)
 126             ? NULL
 127             : sset_add__(set, name, length, hash));
 128 }
 129
 130 /* Adds a copy of 'name' to 'set' and frees 'name'.
 131  *
 132  * If 'name' is new, returns the new sset_node; otherwise (if a copy of 'name'
 133  * already existed in 'set'), returns NULL. */
 134 struct sset_node *
 135 sset_add_and_free(struct sset *set, char *name)
 136 {
 137     struct sset_node *node = sset_add(set, name);
 138     free(name);
 139     return node;
 140 }
 141
 142 /* Adds 'name' to 'set'.  Assert-fails if a copy of 'name' was already in
 143  * 'set'. */
 144 void
 145 sset_add_assert(struct sset *set, const char *name)
 146 {
 147     bool added OVS_UNUSED = sset_add(set, name);
 148     ovs_assert(added);
 149 }
 150
 151 /* Adds a copy of each of the 'n' names in 'names' to 'set'. */
 152 void
 153 sset_add_array(struct sset *set, char **names, size_t n)
 154 {
 155     size_t i;
 156
 157     for (i = 0; i < n; i++) {
 158         sset_add(set, names[i]);
 159     }
 160 }
 161
 162 /* Removes all of the strings from 'set'. */
 163 void
 164 sset_clear(struct sset *set)
 165 {
 166     const char *name, *next;
 167
 168     SSET_FOR_EACH_SAFE (name, next, set) {
 169         sset_delete(set, SSET_NODE_FROM_NAME(name));
 170     }
 171 }
 172
 173 /* Deletes 'node' from 'set' and frees 'node'. */
 174 void
 175 sset_delete(struct sset *set, struct sset_node *node)
 176 {
 177     hmap_remove(&set->map, &node->hmap_node);
 178     free(node);
 179 }
 180
 181 /* Searches for 'name' in 'set'.  If found, deletes it and returns true.  If
 182  * not found, returns false without modifying 'set'. */
 183 bool
 184 sset_find_and_delete(struct sset *set, const char *name)
 185 {
 186     struct sset_node *node = sset_find(set, name);
 187     if (node) {
 188         sset_delete(set, node);
 189     }
 190     return node != NULL;
 191 }
 192
 193 /* Searches for 'name' in 'set' and deletes it.  Assert-fails if 'name' is not
 194  * in 'set'. */
 195 void
 196 sset_find_and_delete_assert(struct sset *set, const char *name)
 197 {
 198     bool deleted OVS_UNUSED = sset_find_and_delete(set, name);
 199     ovs_assert(deleted);
 200 }
 201
 202 /* Removes a string from 'set' and returns a copy of it.  The caller must free
 203  * the returned string (with free()).
 204  *
 205  * 'set' must not be empty.
 206  *
 207  * This is not a very good way to iterate through an sset: it copies each name
 208  * and it takes O(n**2) time to remove all the names.  Use SSET_FOR_EACH_SAFE
 209  * instead, if you can. */
 210 char *
 211 sset_pop(struct sset *set)
 212 {
 213     const char *name = SSET_FIRST(set);
 214     char *copy = xstrdup(name);
 215     sset_delete(set, SSET_NODE_FROM_NAME(name));
 216     return copy;
 217 }
 218
 219 /* Searches for 'name' in 'set'.  Returns its node, if found, otherwise a null
 220  * pointer. */
 221 struct sset_node *
 222 sset_find(const struct sset *set, const char *name)
 223 {
 224     return sset_find__(set, name, hash_name(name));
 225 }
 226
 227 /* Returns true if 'set' contains a copy of 'name', false otherwise. */
 228 bool
 229 sset_contains(const struct sset *set, const char *name)
 230 {
 231     return sset_find(set, name) != NULL;
 232 }
 233
 234 /* Returns true if 'a' and 'b' contain the same strings, false otherwise. */
 235 bool
 236 sset_equals(const struct sset *a, const struct sset *b)
 237 {
 238     struct sset_node *node;
 239
 240     if (sset_count(a) != sset_count(b)) {
 241         return false;
 242     }
 243
 244     HMAP_FOR_EACH (node, hmap_node, &a->map) {
 245         if (!sset_find__(b, node->name, node->hmap_node.hash)) {
 246             return false;
 247         }
 248     }
 249
 250     return true;
 251 }
 252
 253 /* Returns the next node in 'set' in hash order, or NULL if no nodes remain in
 254  * 'set'.  Uses '*bucketp' and '*offsetp' to determine where to begin
 255  * iteration, and stores new values to pass on the next iteration into them
 256  * before returning.
 257  *
 258  * It's better to use plain SSET_FOR_EACH and related functions, since they are
 259  * faster and better at dealing with ssets that change during iteration.
 260  *
 261  * Before beginning iteration, store 0 into '*bucketp' and '*offsetp'.
 262  */
 263 struct sset_node *
 264 sset_at_position(const struct sset *set, uint32_t *bucketp, uint32_t *offsetp)
 265 {
 266     struct hmap_node *hmap_node;
 267
 268     hmap_node = hmap_at_position(&set->map, bucketp, offsetp);
 269     return SSET_NODE_FROM_HMAP_NODE(hmap_node);
 270 }
 271
 272 /* Replaces 'a' by the intersection of 'a' and 'b'.  That is, removes from 'a'
 273  * all of the strings that are not also in 'b'. */
 274 void
 275 sset_intersect(struct sset *a, const struct sset *b)
 276 {
 277     const char *name, *next;
 278
 279     SSET_FOR_EACH_SAFE (name, next, a) {
 280         if (!sset_contains(b, name)) {
 281             sset_delete(a, SSET_NODE_FROM_NAME(name));
 282         }
 283     }
 284 }
 285
 286 /* Returns a null-terminated array of pointers to the strings in 'set', in no
 287  * particular order.  The caller must free the returned array when it is no
 288  * longer needed, but the strings in the array belong to 'set' and thus must
 289  * not be modified or freed. */
 290 const char **
 291 sset_array(const struct sset *set)
 292 {
 293     size_t n = sset_count(set);
 294     const char **array;
 295     const char *s;
 296     size_t i;
 297
 298     array = xmalloc(sizeof *array * (n + 1));
 299     i = 0;
 300     SSET_FOR_EACH (s, set) {
 301         array[i++] = s;
 302     }
 303     ovs_assert(i == n);
 304     array[n] = NULL;
 305
 306     return array;
 307 }
 308
 309 static int
 310 compare_string_pointers(const void *a_, const void *b_)
 311 {
 312     const char *const *a = a_;
 313     const char *const *b = b_;
 314
 315     return strcmp(*a, *b);
 316 }
 317
 318 /* Returns a null-terminated array of pointers to the strings in 'set', sorted
 319  * alphabetically.  The caller must free the returned array when it is no
 320  * longer needed, but the strings in the array belong to 'set' and thus must
 321  * not be modified or freed. */
 322 const char **
 323 sset_sort(const struct sset *set)
 324 {
 325     const char **array = sset_array(set);
 326     qsort(array, sset_count(set), sizeof *array, compare_string_pointers);
 327     return array;
 328 }