lib/hmap.c

   1 /*
   2  * Copyright (c) 2008, 2009, 2010, 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 #include "hmap.h"
  19 #include <stdint.h>
  20 #include <string.h>
  21 #include "coverage.h"
  22 #include "random.h"
  23 #include "util.h"
  24 #include "openvswitch/vlog.h"
  25
  26 VLOG_DEFINE_THIS_MODULE(hmap);
  27
  28 COVERAGE_DEFINE(hmap_pathological);
  29 COVERAGE_DEFINE(hmap_expand);
  30 COVERAGE_DEFINE(hmap_shrink);
  31 COVERAGE_DEFINE(hmap_reserve);
  32
  33 /* Initializes 'hmap' as an empty hash table. */
  34 void
  35 hmap_init(struct hmap *hmap)
  36 {
  37     hmap->buckets = &hmap->one;
  38     hmap->one = NULL;
  39     hmap->mask = 0;
  40     hmap->n = 0;
  41 }
  42
  43 /* Frees memory reserved by 'hmap'.  It is the client's responsibility to free
  44  * the nodes themselves, if necessary. */
  45 void
  46 hmap_destroy(struct hmap *hmap)
  47 {
  48     if (hmap && hmap->buckets != &hmap->one) {
  49         free(hmap->buckets);
  50     }
  51 }
  52
  53 /* Removes all node from 'hmap', leaving it ready to accept more nodes.  Does
  54  * not free memory allocated for 'hmap'.
  55  *
  56  * This function is appropriate when 'hmap' will soon have about as many
  57  * elements as it did before.  If 'hmap' will likely have fewer elements than
  58  * before, use hmap_destroy() followed by hmap_init() to save memory and
  59  * iteration time. */
  60 void
  61 hmap_clear(struct hmap *hmap)
  62 {
  63     if (hmap->n > 0) {
  64         hmap->n = 0;
  65         memset(hmap->buckets, 0, (hmap->mask + 1) * sizeof *hmap->buckets);
  66     }
  67 }
  68
  69 /* Exchanges hash maps 'a' and 'b'. */
  70 void
  71 hmap_swap(struct hmap *a, struct hmap *b)
  72 {
  73     struct hmap tmp = *a;
  74     *a = *b;
  75     *b = tmp;
  76     hmap_moved(a);
  77     hmap_moved(b);
  78 }
  79
  80 /* Adjusts 'hmap' to compensate for having moved position in memory (e.g. due
  81  * to realloc()). */
  82 void
  83 hmap_moved(struct hmap *hmap)
  84 {
  85     if (!hmap->mask) {
  86         hmap->buckets = &hmap->one;
  87     }
  88 }
  89
  90 static void
  91 resize(struct hmap *hmap, size_t new_mask, const char *where)
  92 {
  93     struct hmap tmp;
  94     size_t i;
  95
  96     ovs_assert(is_pow2(new_mask + 1));
  97
  98     hmap_init(&tmp);
  99     if (new_mask) {
 100         tmp.buckets = xmalloc(sizeof *tmp.buckets * (new_mask + 1));
 101         tmp.mask = new_mask;
 102         for (i = 0; i <= tmp.mask; i++) {
 103             tmp.buckets[i] = NULL;
 104         }
 105     }
 106     for (i = 0; i <= hmap->mask; i++) {
 107         struct hmap_node *node, *next;
 108         int count = 0;
 109         for (node = hmap->buckets[i]; node; node = next) {
 110             next = node->next;
 111             hmap_insert_fast(&tmp, node, node->hash);
 112             count++;
 113         }
 114         if (count > 5) {
 115             static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(10, 10);
 116             COVERAGE_INC(hmap_pathological);
 117             VLOG_DBG_RL(&rl, "%s: %d nodes in bucket (%"PRIuSIZE" nodes, %"PRIuSIZE" buckets)",
 118                         where, count, hmap->n, hmap->mask + 1);
 119         }
 120     }
 121     hmap_swap(hmap, &tmp);
 122     hmap_destroy(&tmp);
 123 }
 124
 125 static size_t
 126 calc_mask(size_t capacity)
 127 {
 128     size_t mask = capacity / 2;
 129     mask |= mask >> 1;
 130     mask |= mask >> 2;
 131     mask |= mask >> 4;
 132     mask |= mask >> 8;
 133     mask |= mask >> 16;
 134 #if SIZE_MAX > UINT32_MAX
 135     mask |= mask >> 32;
 136 #endif
 137
 138     /* If we need to dynamically allocate buckets we might as well allocate at
 139      * least 4 of them. */
 140     mask |= (mask & 1) << 1;
 141
 142     return mask;
 143 }
 144
 145 /* Expands 'hmap', if necessary, to optimize the performance of searches.
 146  *
 147  * ('where' is used in debug logging.  Commonly one would use hmap_expand() to
 148  * automatically provide the caller's source file and line number for
 149  * 'where'.) */
 150 void
 151 hmap_expand_at(struct hmap *hmap, const char *where)
 152 {
 153     size_t new_mask = calc_mask(hmap->n);
 154     if (new_mask > hmap->mask) {
 155         COVERAGE_INC(hmap_expand);
 156         resize(hmap, new_mask, where);
 157     }
 158 }
 159
 160 /* Shrinks 'hmap', if necessary, to optimize the performance of iteration.
 161  *
 162  * ('where' is used in debug logging.  Commonly one would use hmap_shrink() to
 163  * automatically provide the caller's source file and line number for
 164  * 'where'.) */
 165 void
 166 hmap_shrink_at(struct hmap *hmap, const char *where)
 167 {
 168     size_t new_mask = calc_mask(hmap->n);
 169     if (new_mask < hmap->mask) {
 170         COVERAGE_INC(hmap_shrink);
 171         resize(hmap, new_mask, where);
 172     }
 173 }
 174
 175 /* Expands 'hmap', if necessary, to optimize the performance of searches when
 176  * it has up to 'n' elements.  (But iteration will be slow in a hash map whose
 177  * allocated capacity is much higher than its current number of nodes.)
 178  *
 179  * ('where' is used in debug logging.  Commonly one would use hmap_reserve() to
 180  * automatically provide the caller's source file and line number for
 181  * 'where'.) */
 182 void
 183 hmap_reserve_at(struct hmap *hmap, size_t n, const char *where)
 184 {
 185     size_t new_mask = calc_mask(n);
 186     if (new_mask > hmap->mask) {
 187         COVERAGE_INC(hmap_reserve);
 188         resize(hmap, new_mask, where);
 189     }
 190 }
 191
 192 /* Adjusts 'hmap' to compensate for 'old_node' having moved position in memory
 193  * to 'node' (e.g. due to realloc()). */
 194 void
 195 hmap_node_moved(struct hmap *hmap,
 196                 struct hmap_node *old_node, struct hmap_node *node)
 197 {
 198     struct hmap_node **bucket = &hmap->buckets[node->hash & hmap->mask];
 199     while (*bucket != old_node) {
 200         bucket = &(*bucket)->next;
 201     }
 202     *bucket = node;
 203 }
 204
 205 /* Chooses and returns a randomly selected node from 'hmap', which must not be
 206  * empty.
 207  *
 208  * I wouldn't depend on this algorithm to be fair, since I haven't analyzed it.
 209  * But it does at least ensure that any node in 'hmap' can be chosen. */
 210 struct hmap_node *
 211 hmap_random_node(const struct hmap *hmap)
 212 {
 213     struct hmap_node *bucket, *node;
 214     size_t n, i;
 215
 216     /* Choose a random non-empty bucket. */
 217     for (;;) {
 218         bucket = hmap->buckets[random_uint32() & hmap->mask];
 219         if (bucket) {
 220             break;
 221         }
 222     }
 223
 224     /* Count nodes in bucket. */
 225     n = 0;
 226     for (node = bucket; node; node = node->next) {
 227         n++;
 228     }
 229
 230     /* Choose random node from bucket. */
 231     i = random_range(n);
 232     for (node = bucket; i-- > 0; node = node->next) {
 233         continue;
 234     }
 235     return node;
 236 }
 237
 238 /* Returns the next node in 'hmap' in hash order, or NULL if no nodes remain in
 239  * 'hmap'.  Uses '*bucketp' and '*offsetp' to determine where to begin
 240  * iteration, and stores new values to pass on the next iteration into them
 241  * before returning.
 242  *
 243  * It's better to use plain HMAP_FOR_EACH and related functions, since they are
 244  * faster and better at dealing with hmaps that change during iteration.
 245  *
 246  * Before beginning iteration, store 0 into '*bucketp' and '*offsetp'.
 247  */
 248 struct hmap_node *
 249 hmap_at_position(const struct hmap *hmap,
 250                  uint32_t *bucketp, uint32_t *offsetp)
 251 {
 252     size_t offset;
 253     size_t b_idx;
 254
 255     offset = *offsetp;
 256     for (b_idx = *bucketp; b_idx <= hmap->mask; b_idx++) {
 257         struct hmap_node *node;
 258         size_t n_idx;
 259
 260         for (n_idx = 0, node = hmap->buckets[b_idx]; node != NULL;
 261              n_idx++, node = node->next) {
 262             if (n_idx == offset) {
 263                 if (node->next) {
 264                     *bucketp = node->hash & hmap->mask;
 265                     *offsetp = offset + 1;
 266                 } else {
 267                     *bucketp = (node->hash & hmap->mask) + 1;
 268                     *offsetp = 0;
 269                 }
 270                 return node;
 271             }
 272         }
 273         offset = 0;
 274     }
 275
 276     *bucketp = 0;
 277     *offsetp = 0;
 278     return NULL;
 279 }
 280
 281 /* Returns true if 'node' is in 'hmap', false otherwise. */
 282 bool
 283 hmap_contains(const struct hmap *hmap, const struct hmap_node *node)
 284 {
 285     struct hmap_node *p;
 286
 287     for (p = hmap_first_in_bucket(hmap, node->hash); p; p = p->next) {
 288         if (p == node) {
 289             return true;
 290         }
 291     }
 292
 293     return false;
 294 }