lib/simap.c

   1 /*
   2  * Copyright (c) 2009, 2010, 2011, 2012, 2017, 2019 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 #include "simap.h"
  19 #include "hash.h"
  20
  21 static size_t hash_name(const char *, size_t length);
  22 static struct simap_node *simap_find__(const struct simap *,
  23                                        const char *name, size_t name_len,
  24                                        size_t hash);
  25 static struct simap_node *simap_add_nocopy__(struct simap *,
  26                                              char *name, unsigned int data,
  27                                              size_t hash);
  28 static int compare_nodes_by_name(const void *a_, const void *b_);
  29
  30 /* Initializes 'simap' as an empty string-to-integer map. */
  31 void
  32 simap_init(struct simap *simap)
  33 {
  34     hmap_init(&simap->map);
  35 }
  36
  37 /* Frees all the data that 'simap' contains. */
  38 void
  39 simap_destroy(struct simap *simap)
  40 {
  41     if (simap) {
  42         simap_clear(simap);
  43         hmap_destroy(&simap->map);
  44     }
  45 }
  46
  47 /* Exchanges the contents of 'a' and 'b'. */
  48 void
  49 simap_swap(struct simap *a, struct simap *b)
  50 {
  51     hmap_swap(&a->map, &b->map);
  52 }
  53
  54 /* Adjusts 'simap' so that it is still valid after it has been moved around in
  55  * memory (e.g. due to realloc()). */
  56 void
  57 simap_moved(struct simap *simap)
  58 {
  59     hmap_moved(&simap->map);
  60 }
  61
  62 /* Removes all of the mappings from 'simap' and frees them. */
  63 void
  64 simap_clear(struct simap *simap)
  65 {
  66     struct simap_node *node, *next;
  67
  68     SIMAP_FOR_EACH_SAFE (node, next, simap) {
  69         hmap_remove(&simap->map, &node->node);
  70         free(node->name);
  71         free(node);
  72     }
  73 }
  74
  75 /* Returns true if 'simap' contains no mappings, false if it contains at least
  76  * one. */
  77 bool
  78 simap_is_empty(const struct simap *simap)
  79 {
  80     return hmap_is_empty(&simap->map);
  81 }
  82
  83 /* Returns the number of mappings in 'simap'. */
  84 size_t
  85 simap_count(const struct simap *simap)
  86 {
  87     return hmap_count(&simap->map);
  88 }
  89
  90 /* Inserts a mapping from 'name' to 'data' into 'simap', replacing any
  91  * existing mapping for 'name'.  Returns true if a new mapping was added,
  92  * false if an existing mapping's value was replaced.
  93  *
  94  * The caller retains ownership of 'name'. */
  95 bool
  96 simap_put(struct simap *simap, const char *name, unsigned int data)
  97 {
  98     size_t length = strlen(name);
  99     size_t hash = hash_name(name, length);
 100     struct simap_node *node;
 101
 102     node = simap_find__(simap, name, length, hash);
 103     if (node) {
 104         node->data = data;
 105         return false;
 106     } else {
 107         simap_add_nocopy__(simap, xmemdup0(name, length), data, hash);
 108         return true;
 109     }
 110 }
 111
 112 /* Increases the data value in the mapping for 'name' by 'amt', or inserts a
 113  * mapping from 'name' to 'amt' if no such mapping exists.  Returns the
 114  * new total data value for the mapping.
 115  *
 116  * If 'amt' is zero, this function does nothing and returns 0.  That is, this
 117  * function won't create a mapping with a initial value of 0.
 118  *
 119  * The caller retains ownership of 'name'. */
 120 unsigned int
 121 simap_increase(struct simap *simap, const char *name, unsigned int amt)
 122 {
 123     if (amt) {
 124         size_t length = strlen(name);
 125         size_t hash = hash_name(name, length);
 126         struct simap_node *node;
 127
 128         node = simap_find__(simap, name, length, hash);
 129         if (node) {
 130             node->data += amt;
 131         } else {
 132             node = simap_add_nocopy__(simap, xmemdup0(name, length),
 133                                       amt, hash);
 134         }
 135         return node->data;
 136     } else {
 137         return 0;
 138     }
 139 }
 140
 141 /* Deletes 'node' from 'simap' and frees its associated memory. */
 142 void
 143 simap_delete(struct simap *simap, struct simap_node *node)
 144 {
 145     hmap_remove(&simap->map, &node->node);
 146     free(node->name);
 147     free(node);
 148 }
 149
 150 /* Searches for 'name' in 'simap'.  If found, deletes it and returns true.  If
 151  * not found, returns false without modifying 'simap'. */
 152 bool
 153 simap_find_and_delete(struct simap *simap, const char *name)
 154 {
 155     struct simap_node *node = simap_find(simap, name);
 156     if (node) {
 157         simap_delete(simap, node);
 158         return true;
 159     }
 160     return false;
 161 }
 162
 163 /* Searches 'simap' for a mapping with the given 'name'.  Returns it, if found,
 164  * or a null pointer if not. */
 165 struct simap_node *
 166 simap_find(const struct simap *simap, const char *name)
 167 {
 168     return simap_find_len(simap, name, strlen(name));
 169 }
 170
 171 /* Searches 'simap' for a mapping whose name is the first 'name_len' bytes
 172  * starting at 'name'.  Returns it, if found, or a null pointer if not. */
 173 struct simap_node *
 174 simap_find_len(const struct simap *simap, const char *name, size_t len)
 175 {
 176     return simap_find__(simap, name, len, hash_name(name, len));
 177 }
 178
 179 /* Searches 'simap' for a mapping with the given 'name'.  Returns the
 180  * associated data value, if found, otherwise zero. */
 181 unsigned int
 182 simap_get(const struct simap *simap, const char *name)
 183 {
 184     struct simap_node *node = simap_find(simap, name);
 185     return node ? node->data : 0;
 186 }
 187
 188 /* Returns true if 'simap' contains a copy of 'name', false otherwise. */
 189 bool
 190 simap_contains(const struct simap *simap, const char *name)
 191 {
 192     return simap_find(simap, name) != NULL;
 193 }
 194
 195 /* Returns an array that contains a pointer to each mapping in 'simap',
 196  * ordered alphabetically by name.  The returned array has simap_count(simap)
 197  * elements.
 198  *
 199  * The caller is responsible for freeing the returned array (with free()).  It
 200  * should not free the individual "simap_node"s in the array, because they are
 201  * still part of 'simap'. */
 202 const struct simap_node **
 203 simap_sort(const struct simap *simap)
 204 {
 205     if (simap_is_empty(simap)) {
 206         return NULL;
 207     } else {
 208         const struct simap_node **nodes;
 209         struct simap_node *node;
 210         size_t i, n;
 211
 212         n = simap_count(simap);
 213         nodes = xmalloc(n * sizeof *nodes);
 214         i = 0;
 215         SIMAP_FOR_EACH (node, simap) {
 216             nodes[i++] = node;
 217         }
 218         ovs_assert(i == n);
 219
 220         qsort(nodes, n, sizeof *nodes, compare_nodes_by_name);
 221
 222         return nodes;
 223     }
 224 }
 225
 226 /* Returns true if the two maps are equal, meaning that they have the same set
 227  * of key-value pairs, otherwise false. */
 228 bool
 229 simap_equal(const struct simap *a, const struct simap *b)
 230 {
 231     if (simap_count(a) != simap_count(b)) {
 232         return false;
 233     }
 234
 235     const struct simap_node *an;
 236     SIMAP_FOR_EACH (an, a) {
 237         const struct simap_node *bn = simap_find(b, an->name);
 238         if (!bn || an->data != bn->data) {
 239             return false;
 240         }
 241     }
 242     return true;
 243 }
 244
 245 uint32_t
 246 simap_hash(const struct simap *simap)
 247 {
 248     uint32_t hash = 0;
 249
 250     const struct simap_node *node;
 251     SIMAP_FOR_EACH (node, simap) {
 252         hash ^= hash_int(node->data,
 253                          hash_name(node->name, strlen(node->name)));
 254     }
 255     return hash;
 256 }
 257
 258 static size_t
 259 hash_name(const char *name, size_t length)
 260 {
 261     return hash_bytes(name, length, 0);
 262 }
 263
 264 static struct simap_node *
 265 simap_find__(const struct simap *simap, const char *name, size_t name_len,
 266              size_t hash)
 267 {
 268     struct simap_node *node;
 269
 270     HMAP_FOR_EACH_WITH_HASH (node, node, hash, &simap->map) {
 271         if (!strncmp(node->name, name, name_len) && !node->name[name_len]) {
 272             return node;
 273         }
 274     }
 275     return NULL;
 276 }
 277
 278 static struct simap_node *
 279 simap_add_nocopy__(struct simap *simap, char *name, unsigned int data,
 280                    size_t hash)
 281 {
 282     struct simap_node *node = xmalloc(sizeof *node);
 283     node->name = name;
 284     node->data = data;
 285     hmap_insert(&simap->map, &node->node, hash);
 286     return node;
 287 }
 288
 289 static int
 290 compare_nodes_by_name(const void *a_, const void *b_)
 291 {
 292     const struct simap_node *const *a = a_;
 293     const struct simap_node *const *b = b_;
 294     return strcmp((*a)->name, (*b)->name);
 295 }