lib/nghttp2_map.c

   1 /*
   2  * nghttp2 - HTTP/2 C Library
   3  *
   4  * Copyright (c) 2012 Tatsuhiro Tsujikawa
   5  *
   6  * Permission is hereby granted, free of charge, to any person obtaining
   7  * a copy of this software and associated documentation files (the
   8  * "Software"), to deal in the Software without restriction, including
   9  * without limitation the rights to use, copy, modify, merge, publish,
  10  * distribute, sublicense, and/or sell copies of the Software, and to
  11  * permit persons to whom the Software is furnished to do so, subject to
  12  * the following conditions:
  13  *
  14  * The above copyright notice and this permission notice shall be
  15  * included in all copies or substantial portions of the Software.
  16  *
  17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  18  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  19  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  20  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  21  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  22  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  23  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  24  */
  25 #include "nghttp2_map.h"
  26
  27 #include <string.h>
  28
  29 #define INITIAL_TABLE_LENGTH 256
  30
  31 int nghttp2_map_init(nghttp2_map *map, nghttp2_mem *mem) {
  32   map->mem = mem;
  33   map->tablelen = INITIAL_TABLE_LENGTH;
  34   map->table =
  35       nghttp2_mem_calloc(mem, map->tablelen, sizeof(nghttp2_map_entry *));
  36   if (map->table == NULL) {
  37     return NGHTTP2_ERR_NOMEM;
  38   }
  39
  40   map->size = 0;
  41
  42   return 0;
  43 }
  44
  45 void nghttp2_map_free(nghttp2_map *map) {
  46   nghttp2_mem_free(map->mem, map->table);
  47 }
  48
  49 void nghttp2_map_each_free(nghttp2_map *map,
  50                            int (*func)(nghttp2_map_entry *entry, void *ptr),
  51                            void *ptr) {
  52   uint32_t i;
  53   for (i = 0; i < map->tablelen; ++i) {
  54     nghttp2_map_entry *entry;
  55     for (entry = map->table[i]; entry;) {
  56       nghttp2_map_entry *next = entry->next;
  57       func(entry, ptr);
  58       entry = next;
  59     }
  60     map->table[i] = NULL;
  61   }
  62 }
  63
  64 int nghttp2_map_each(nghttp2_map *map,
  65                      int (*func)(nghttp2_map_entry *entry, void *ptr),
  66                      void *ptr) {
  67   int rv;
  68   uint32_t i;
  69   for (i = 0; i < map->tablelen; ++i) {
  70     nghttp2_map_entry *entry;
  71     for (entry = map->table[i]; entry; entry = entry->next) {
  72       rv = func(entry, ptr);
  73       if (rv != 0) {
  74         return rv;
  75       }
  76     }
  77   }
  78   return 0;
  79 }
  80
  81 void nghttp2_map_entry_init(nghttp2_map_entry *entry, key_type key) {
  82   entry->key = key;
  83   entry->next = NULL;
  84 }
  85
  86 /* Same hash function in android HashMap source code. */
  87 /* The |mod| must be power of 2 */
  88 static uint32_t hash(int32_t key, uint32_t mod) {
  89   uint32_t h = (uint32_t)key;
  90   h ^= (h >> 20) ^ (h >> 12);
  91   h ^= (h >> 7) ^ (h >> 4);
  92   return h & (mod - 1);
  93 }
  94
  95 static int insert(nghttp2_map_entry **table, uint32_t tablelen,
  96                   nghttp2_map_entry *entry) {
  97   uint32_t h = hash(entry->key, tablelen);
  98   if (table[h] == NULL) {
  99     table[h] = entry;
 100   } else {
 101     nghttp2_map_entry *p;
 102     /* We won't allow duplicated key, so check it out. */
 103     for (p = table[h]; p; p = p->next) {
 104       if (p->key == entry->key) {
 105         return NGHTTP2_ERR_INVALID_ARGUMENT;
 106       }
 107     }
 108     entry->next = table[h];
 109     table[h] = entry;
 110   }
 111   return 0;
 112 }
 113
 114 /* new_tablelen must be power of 2 */
 115 static int resize(nghttp2_map *map, uint32_t new_tablelen) {
 116   uint32_t i;
 117   nghttp2_map_entry **new_table;
 118
 119   new_table =
 120       nghttp2_mem_calloc(map->mem, new_tablelen, sizeof(nghttp2_map_entry *));
 121   if (new_table == NULL) {
 122     return NGHTTP2_ERR_NOMEM;
 123   }
 124
 125   for (i = 0; i < map->tablelen; ++i) {
 126     nghttp2_map_entry *entry;
 127     for (entry = map->table[i]; entry;) {
 128       nghttp2_map_entry *next = entry->next;
 129       entry->next = NULL;
 130       /* This function must succeed */
 131       insert(new_table, new_tablelen, entry);
 132       entry = next;
 133     }
 134   }
 135   nghttp2_mem_free(map->mem, map->table);
 136   map->tablelen = new_tablelen;
 137   map->table = new_table;
 138
 139   return 0;
 140 }
 141
 142 int nghttp2_map_insert(nghttp2_map *map, nghttp2_map_entry *new_entry) {
 143   int rv;
 144   /* Load factor is 0.75 */
 145   if ((map->size + 1) * 4 > map->tablelen * 3) {
 146     rv = resize(map, map->tablelen * 2);
 147     if (rv != 0) {
 148       return rv;
 149     }
 150   }
 151   rv = insert(map->table, map->tablelen, new_entry);
 152   if (rv != 0) {
 153     return rv;
 154   }
 155   ++map->size;
 156   return 0;
 157 }
 158
 159 nghttp2_map_entry *nghttp2_map_find(nghttp2_map *map, key_type key) {
 160   uint32_t h;
 161   nghttp2_map_entry *entry;
 162   h = hash(key, map->tablelen);
 163   for (entry = map->table[h]; entry; entry = entry->next) {
 164     if (entry->key == key) {
 165       return entry;
 166     }
 167   }
 168   return NULL;
 169 }
 170
 171 int nghttp2_map_remove(nghttp2_map *map, key_type key) {
 172   uint32_t h;
 173   nghttp2_map_entry **dst;
 174
 175   h = hash(key, map->tablelen);
 176
 177   for (dst = &map->table[h]; *dst; dst = &(*dst)->next) {
 178     if ((*dst)->key != key) {
 179       continue;
 180     }
 181
 182     *dst = (*dst)->next;
 183     --map->size;
 184     return 0;
 185   }
 186   return NGHTTP2_ERR_INVALID_ARGUMENT;
 187 }
 188
 189 size_t nghttp2_map_size(nghttp2_map *map) { return map->size; }