lib/simap.c

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