lib/hmap.c

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