lib/nghttp2_map.c

   1 /*
   2  * nghttp2 - HTTP/2 C Library
   3  *
   4  * Copyright (c) 2017 ngtcp2 contributors
   5  * Copyright (c) 2012 nghttp2 contributors
   6  *
   7  * Permission is hereby granted, free of charge, to any person obtaining
   8  * a copy of this software and associated documentation files (the
   9  * "Software"), to deal in the Software without restriction, including
  10  * without limitation the rights to use, copy, modify, merge, publish,
  11  * distribute, sublicense, and/or sell copies of the Software, and to
  12  * permit persons to whom the Software is furnished to do so, subject to
  13  * the following conditions:
  14  *
  15  * The above copyright notice and this permission notice shall be
  16  * included in all copies or substantial portions of the Software.
  17  *
  18  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  19  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  20  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  21  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  22  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  23  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  24  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  25  */
  26 #include "nghttp2_map.h"
  27
  28 #include <string.h>
  29 #include <assert.h>
  30 #include <stdio.h>
  31
  32 #include "nghttp2_helper.h"
  33
  34 #define NGHTTP2_INITIAL_TABLE_LENBITS 8
  35
  36 int nghttp2_map_init(nghttp2_map *map, nghttp2_mem *mem) {
  37   map->mem = mem;
  38   map->tablelen = 1 << NGHTTP2_INITIAL_TABLE_LENBITS;
  39   map->tablelenbits = NGHTTP2_INITIAL_TABLE_LENBITS;
  40   map->table =
  41       nghttp2_mem_calloc(mem, map->tablelen, sizeof(nghttp2_map_bucket));
  42   if (map->table == NULL) {
  43     return NGHTTP2_ERR_NOMEM;
  44   }
  45
  46   map->size = 0;
  47
  48   return 0;
  49 }
  50
  51 void nghttp2_map_free(nghttp2_map *map) {
  52   if (!map) {
  53     return;
  54   }
  55
  56   nghttp2_mem_free(map->mem, map->table);
  57 }
  58
  59 void nghttp2_map_each_free(nghttp2_map *map, int (*func)(void *data, void *ptr),
  60                            void *ptr) {
  61   uint32_t i;
  62   nghttp2_map_bucket *bkt;
  63
  64   for (i = 0; i < map->tablelen; ++i) {
  65     bkt = &map->table[i];
  66
  67     if (bkt->data == NULL) {
  68       continue;
  69     }
  70
  71     func(bkt->data, ptr);
  72   }
  73 }
  74
  75 int nghttp2_map_each(nghttp2_map *map, int (*func)(void *data, void *ptr),
  76                      void *ptr) {
  77   int rv;
  78   uint32_t i;
  79   nghttp2_map_bucket *bkt;
  80
  81   for (i = 0; i < map->tablelen; ++i) {
  82     bkt = &map->table[i];
  83
  84     if (bkt->data == NULL) {
  85       continue;
  86     }
  87
  88     rv = func(bkt->data, ptr);
  89     if (rv != 0) {
  90       return rv;
  91     }
  92   }
  93
  94   return 0;
  95 }
  96
  97 static uint32_t hash(nghttp2_map_key_type key) {
  98   return (uint32_t)key * 2654435769u;
  99 }
 100
 101 static size_t h2idx(uint32_t hash, uint32_t bits) {
 102   return hash >> (32 - bits);
 103 }
 104
 105 static size_t distance(uint32_t tablelen, uint32_t tablelenbits,
 106                        nghttp2_map_bucket *bkt, size_t idx) {
 107   return (idx - h2idx(bkt->hash, tablelenbits)) & (tablelen - 1);
 108 }
 109
 110 static void map_bucket_swap(nghttp2_map_bucket *bkt, uint32_t *phash,
 111                             nghttp2_map_key_type *pkey, void **pdata) {
 112   uint32_t h = bkt->hash;
 113   nghttp2_map_key_type key = bkt->key;
 114   void *data = bkt->data;
 115
 116   bkt->hash = *phash;
 117   bkt->key = *pkey;
 118   bkt->data = *pdata;
 119
 120   *phash = h;
 121   *pkey = key;
 122   *pdata = data;
 123 }
 124
 125 static void map_bucket_set_data(nghttp2_map_bucket *bkt, uint32_t hash,
 126                                 nghttp2_map_key_type key, void *data) {
 127   bkt->hash = hash;
 128   bkt->key = key;
 129   bkt->data = data;
 130 }
 131
 132 void nghttp2_map_print_distance(nghttp2_map *map) {
 133   uint32_t i;
 134   size_t idx;
 135   nghttp2_map_bucket *bkt;
 136
 137   for (i = 0; i < map->tablelen; ++i) {
 138     bkt = &map->table[i];
 139
 140     if (bkt->data == NULL) {
 141       fprintf(stderr, "@%u <EMPTY>\n", i);
 142       continue;
 143     }
 144
 145     idx = h2idx(bkt->hash, map->tablelenbits);
 146     fprintf(stderr, "@%u hash=%08x key=%d base=%zu distance=%zu\n", i,
 147             bkt->hash, bkt->key, idx,
 148             distance(map->tablelen, map->tablelenbits, bkt, idx));
 149   }
 150 }
 151
 152 static int insert(nghttp2_map_bucket *table, uint32_t tablelen,
 153                   uint32_t tablelenbits, uint32_t hash,
 154                   nghttp2_map_key_type key, void *data) {
 155   size_t idx = h2idx(hash, tablelenbits);
 156   size_t d = 0, dd;
 157   nghttp2_map_bucket *bkt;
 158
 159   for (;;) {
 160     bkt = &table[idx];
 161
 162     if (bkt->data == NULL) {
 163       map_bucket_set_data(bkt, hash, key, data);
 164       return 0;
 165     }
 166
 167     dd = distance(tablelen, tablelenbits, bkt, idx);
 168     if (d > dd) {
 169       map_bucket_swap(bkt, &hash, &key, &data);
 170       d = dd;
 171     } else if (bkt->key == key) {
 172       /* TODO This check is just a waste after first swap or if this
 173          function is called from map_resize.  That said, there is no
 174          difference with or without this conditional in performance
 175          wise. */
 176       return NGHTTP2_ERR_INVALID_ARGUMENT;
 177     }
 178
 179     ++d;
 180     idx = (idx + 1) & (tablelen - 1);
 181   }
 182 }
 183
 184 /* new_tablelen must be power of 2 and new_tablelen == (1 <<
 185    new_tablelenbits) must hold. */
 186 static int map_resize(nghttp2_map *map, uint32_t new_tablelen,
 187                       uint32_t new_tablelenbits) {
 188   uint32_t i;
 189   nghttp2_map_bucket *new_table;
 190   nghttp2_map_bucket *bkt;
 191   int rv;
 192   (void)rv;
 193
 194   new_table =
 195       nghttp2_mem_calloc(map->mem, new_tablelen, sizeof(nghttp2_map_bucket));
 196   if (new_table == NULL) {
 197     return NGHTTP2_ERR_NOMEM;
 198   }
 199
 200   for (i = 0; i < map->tablelen; ++i) {
 201     bkt = &map->table[i];
 202     if (bkt->data == NULL) {
 203       continue;
 204     }
 205     rv = insert(new_table, new_tablelen, new_tablelenbits, bkt->hash, bkt->key,
 206                 bkt->data);
 207
 208     assert(0 == rv);
 209   }
 210
 211   nghttp2_mem_free(map->mem, map->table);
 212   map->tablelen = new_tablelen;
 213   map->tablelenbits = new_tablelenbits;
 214   map->table = new_table;
 215
 216   return 0;
 217 }
 218
 219 int nghttp2_map_insert(nghttp2_map *map, nghttp2_map_key_type key, void *data) {
 220   int rv;
 221
 222   assert(data);
 223
 224   /* Load factor is 0.75 */
 225   if ((map->size + 1) * 4 > map->tablelen * 3) {
 226     rv = map_resize(map, map->tablelen * 2, map->tablelenbits + 1);
 227     if (rv != 0) {
 228       return rv;
 229     }
 230   }
 231
 232   rv = insert(map->table, map->tablelen, map->tablelenbits, hash(key), key,
 233               data);
 234   if (rv != 0) {
 235     return rv;
 236   }
 237   ++map->size;
 238   return 0;
 239 }
 240
 241 void *nghttp2_map_find(nghttp2_map *map, nghttp2_map_key_type key) {
 242   uint32_t h = hash(key);
 243   size_t idx = h2idx(h, map->tablelenbits);
 244   nghttp2_map_bucket *bkt;
 245   size_t d = 0;
 246
 247   for (;;) {
 248     bkt = &map->table[idx];
 249
 250     if (bkt->data == NULL ||
 251         d > distance(map->tablelen, map->tablelenbits, bkt, idx)) {
 252       return NULL;
 253     }
 254
 255     if (bkt->key == key) {
 256       return bkt->data;
 257     }
 258
 259     ++d;
 260     idx = (idx + 1) & (map->tablelen - 1);
 261   }
 262 }
 263
 264 int nghttp2_map_remove(nghttp2_map *map, nghttp2_map_key_type key) {
 265   uint32_t h = hash(key);
 266   size_t idx = h2idx(h, map->tablelenbits), didx;
 267   nghttp2_map_bucket *bkt;
 268   size_t d = 0;
 269
 270   for (;;) {
 271     bkt = &map->table[idx];
 272
 273     if (bkt->data == NULL ||
 274         d > distance(map->tablelen, map->tablelenbits, bkt, idx)) {
 275       return NGHTTP2_ERR_INVALID_ARGUMENT;
 276     }
 277
 278     if (bkt->key == key) {
 279       map_bucket_set_data(bkt, 0, 0, NULL);
 280
 281       didx = idx;
 282       idx = (idx + 1) & (map->tablelen - 1);
 283
 284       for (;;) {
 285         bkt = &map->table[idx];
 286         if (bkt->data == NULL ||
 287             distance(map->tablelen, map->tablelenbits, bkt, idx) == 0) {
 288           break;
 289         }
 290
 291         map->table[didx] = *bkt;
 292         map_bucket_set_data(bkt, 0, 0, NULL);
 293         didx = idx;
 294
 295         idx = (idx + 1) & (map->tablelen - 1);
 296       }
 297
 298       --map->size;
 299
 300       return 0;
 301     }
 302
 303     ++d;
 304     idx = (idx + 1) & (map->tablelen - 1);
 305   }
 306 }
 307
 308 void nghttp2_map_clear(nghttp2_map *map) {
 309   memset(map->table, 0, sizeof(*map->table) * map->tablelen);
 310   map->size = 0;
 311 }
 312
 313 size_t nghttp2_map_size(nghttp2_map *map) { return map->size; }