lib/hmap.c

   1 /*
   2  * Copyright (c) 2008, 2009, 2010 Nicira Networks.
   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 <assert.h>
  20 #include <stdint.h>
  21 #include "coverage.h"
  22 #include "random.h"
  23 #include "util.h"
  24
  25 /* Initializes 'hmap' as an empty hash table. */
  26 void
  27 hmap_init(struct hmap *hmap)
  28 {
  29     hmap->buckets = &hmap->one;
  30     hmap->one = NULL;
  31     hmap->mask = 0;
  32     hmap->n = 0;
  33 }
  34
  35 /* Frees memory reserved by 'hmap'.  It is the client's responsibility to free
  36  * the nodes themselves, if necessary. */
  37 void
  38 hmap_destroy(struct hmap *hmap)
  39 {
  40     if (hmap && hmap->buckets != &hmap->one) {
  41         free(hmap->buckets);
  42     }
  43 }
  44
  45 /* Exchanges hash maps 'a' and 'b'. */
  46 void
  47 hmap_swap(struct hmap *a, struct hmap *b)
  48 {
  49     struct hmap tmp = *a;
  50     *a = *b;
  51     *b = tmp;
  52     hmap_moved(a);
  53     hmap_moved(b);
  54 }
  55
  56 /* Adjusts 'hmap' to compensate for having moved position in memory (e.g. due
  57  * to realloc()). */
  58 void
  59 hmap_moved(struct hmap *hmap)
  60 {
  61     if (!hmap->mask) {
  62         hmap->buckets = &hmap->one;
  63     }
  64 }
  65
  66 static void
  67 resize(struct hmap *hmap, size_t new_mask)
  68 {
  69     struct hmap tmp;
  70     size_t i;
  71
  72     assert(!(new_mask & (new_mask + 1)));
  73     assert(new_mask != SIZE_MAX);
  74
  75     hmap_init(&tmp);
  76     if (new_mask) {
  77         tmp.buckets = xmalloc(sizeof *tmp.buckets * (new_mask + 1));
  78         tmp.mask = new_mask;
  79         for (i = 0; i <= tmp.mask; i++) {
  80             tmp.buckets[i] = NULL;
  81         }
  82     }
  83     for (i = 0; i <= hmap->mask; i++) {
  84         struct hmap_node *node, *next;
  85         int count = 0;
  86         for (node = hmap->buckets[i]; node; node = next) {
  87             next = node->next;
  88             hmap_insert_fast(&tmp, node, node->hash);
  89             count++;
  90         }
  91         if (count > 5) {
  92             COVERAGE_INC(hmap_pathological);
  93         }
  94     }
  95     hmap_swap(hmap, &tmp);
  96     hmap_destroy(&tmp);
  97 }
  98
  99 static size_t
 100 calc_mask(size_t capacity)
 101 {
 102     size_t mask = capacity / 2;
 103     mask |= mask >> 1;
 104     mask |= mask >> 2;
 105     mask |= mask >> 4;
 106     mask |= mask >> 8;
 107     mask |= mask >> 16;
 108 #if SIZE_MAX > UINT32_MAX
 109     mask |= mask >> 32;
 110 #endif
 111
 112     /* If we need to dynamically allocate buckets we might as well allocate at
 113      * least 4 of them. */
 114     mask |= (mask & 1) << 1;
 115
 116     return mask;
 117 }
 118
 119 /* Expands 'hmap', if necessary, to optimize the performance of searches. */
 120 void
 121 hmap_expand(struct hmap *hmap)
 122 {
 123     size_t new_mask = calc_mask(hmap->n);
 124     if (new_mask > hmap->mask) {
 125         COVERAGE_INC(hmap_expand);
 126         resize(hmap, new_mask);
 127     }
 128 }
 129
 130 /* Shrinks 'hmap', if necessary, to optimize the performance of iteration. */
 131 void
 132 hmap_shrink(struct hmap *hmap)
 133 {
 134     size_t new_mask = calc_mask(hmap->n);
 135     if (new_mask < hmap->mask) {
 136         COVERAGE_INC(hmap_shrink);
 137         resize(hmap, new_mask);
 138     }
 139 }
 140
 141 /* Expands 'hmap', if necessary, to optimize the performance of searches when
 142  * it has up to 'n' elements.  (But iteration will be slow in a hash map whose
 143  * allocated capacity is much higher than its current number of nodes.)  */
 144 void
 145 hmap_reserve(struct hmap *hmap, size_t n)
 146 {
 147     size_t new_mask = calc_mask(n);
 148     if (new_mask > hmap->mask) {
 149         COVERAGE_INC(hmap_reserve);
 150         resize(hmap, new_mask);
 151     }
 152 }
 153
 154 /* Adjusts 'hmap' to compensate for 'old_node' having moved position in memory
 155  * to 'node' (e.g. due to realloc()). */
 156 void
 157 hmap_node_moved(struct hmap *hmap,
 158                 struct hmap_node *old_node, struct hmap_node *node)
 159 {
 160     struct hmap_node **bucket = &hmap->buckets[node->hash & hmap->mask];
 161     while (*bucket != old_node) {
 162         bucket = &(*bucket)->next;
 163     }
 164     *bucket = node;
 165 }
 166
 167 /* Chooses and returns a randomly selected node from 'hmap', which must not be
 168  * empty.
 169  *
 170  * I wouldn't depend on this algorithm to be fair, since I haven't analyzed it.
 171  * But it does at least ensure that any node in 'hmap' can be chosen. */
 172 struct hmap_node *
 173 hmap_random_node(const struct hmap *hmap)
 174 {
 175     struct hmap_node *bucket, *node;
 176     size_t n, i;
 177
 178     /* Choose a random non-empty bucket. */
 179     for (i = random_uint32(); ; i++) {
 180         bucket = hmap->buckets[i & hmap->mask];
 181         if (bucket) {
 182             break;
 183         }
 184     }
 185
 186     /* Count nodes in bucket. */
 187     n = 0;
 188     for (node = bucket; node; node = node->next) {
 189         n++;
 190     }
 191
 192     /* Choose random node from bucket. */
 193     i = random_range(n);
 194     for (node = bucket; i-- > 0; node = node->next) {
 195         continue;
 196     }
 197     return node;
 198 }