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   size_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   size_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 int32_t hash(int32_t h, size_t mod) {
  89   h ^= (h >> 20) ^ (h >> 12);
  90   h ^= (h >> 7) ^ (h >> 4);
  91   return h & (mod - 1);
  92 }
  93
  94 static int insert(nghttp2_map_entry **table, size_t tablelen,
  95                   nghttp2_map_entry *entry) {
  96   int32_t h = hash(entry->key, tablelen);
  97   if (table[h] == NULL) {
  98     table[h] = entry;
  99   } else {
 100     nghttp2_map_entry *p;
 101     /* We won't allow duplicated key, so check it out. */
 102     for (p = table[h]; p; p = p->next) {
 103       if (p->key == entry->key) {
 104         return NGHTTP2_ERR_INVALID_ARGUMENT;
 105       }
 106     }
 107     entry->next = table[h];
 108     table[h] = entry;
 109   }
 110   return 0;
 111 }
 112
 113 /* new_tablelen must be power of 2 */
 114 static int resize(nghttp2_map *map, size_t new_tablelen) {
 115   size_t i;
 116   nghttp2_map_entry **new_table;
 117
 118   new_table =
 119       nghttp2_mem_calloc(map->mem, new_tablelen, sizeof(nghttp2_map_entry *));
 120   if (new_table == NULL) {
 121     return NGHTTP2_ERR_NOMEM;
 122   }
 123
 124   for (i = 0; i < map->tablelen; ++i) {
 125     nghttp2_map_entry *entry;
 126     for (entry = map->table[i]; entry;) {
 127       nghttp2_map_entry *next = entry->next;
 128       entry->next = NULL;
 129       /* This function must succeed */
 130       insert(new_table, new_tablelen, entry);
 131       entry = next;
 132     }
 133   }
 134   nghttp2_mem_free(map->mem, map->table);
 135   map->tablelen = new_tablelen;
 136   map->table = new_table;
 137
 138   return 0;
 139 }
 140
 141 int nghttp2_map_insert(nghttp2_map *map, nghttp2_map_entry *new_entry) {
 142   int rv;
 143   /* Load factor is 0.75 */
 144   if ((map->size + 1) * 4 > map->tablelen * 3) {
 145     rv = resize(map, map->tablelen * 2);
 146     if (rv != 0) {
 147       return rv;
 148     }
 149   }
 150   rv = insert(map->table, map->tablelen, new_entry);
 151   if (rv != 0) {
 152     return rv;
 153   }
 154   ++map->size;
 155   return 0;
 156 }
 157
 158 nghttp2_map_entry *nghttp2_map_find(nghttp2_map *map, key_type key) {
 159   int32_t h;
 160   nghttp2_map_entry *entry;
 161   h = hash(key, map->tablelen);
 162   for (entry = map->table[h]; entry; entry = entry->next) {
 163     if (entry->key == key) {
 164       return entry;
 165     }
 166   }
 167   return NULL;
 168 }
 169
 170 int nghttp2_map_remove(nghttp2_map *map, key_type key) {
 171   int32_t h;
 172   nghttp2_map_entry *entry, *prev;
 173   h = hash(key, map->tablelen);
 174   prev = NULL;
 175   for (entry = map->table[h]; entry; entry = entry->next) {
 176     if (entry->key == key) {
 177       if (prev == NULL) {
 178         map->table[h] = entry->next;
 179       } else {
 180         prev->next = entry->next;
 181       }
 182       --map->size;
 183       return 0;
 184     }
 185     prev = entry;
 186   }
 187   return NGHTTP2_ERR_INVALID_ARGUMENT;
 188 }
 189
 190 size_t nghttp2_map_size(nghttp2_map *map) { return map->size; }