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