| /* |
| * nghttp2 - HTTP/2 C Library |
| * |
| * Copyright (c) 2012 Tatsuhiro Tsujikawa |
| * |
| * Permission is hereby granted, free of charge, to any person obtaining |
| * a copy of this software and associated documentation files (the |
| * "Software"), to deal in the Software without restriction, including |
| * without limitation the rights to use, copy, modify, merge, publish, |
| * distribute, sublicense, and/or sell copies of the Software, and to |
| * permit persons to whom the Software is furnished to do so, subject to |
| * the following conditions: |
| * |
| * The above copyright notice and this permission notice shall be |
| * included in all copies or substantial portions of the Software. |
| * |
| * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, |
| * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF |
| * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND |
| * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE |
| * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION |
| * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION |
| * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. |
| */ |
| #include "nghttp2_map.h" |
| |
| #include <string.h> |
| |
| #define INITIAL_TABLE_LENGTH 256 |
| |
| int nghttp2_map_init(nghttp2_map *map, nghttp2_mem *mem) { |
| map->mem = mem; |
| map->tablelen = INITIAL_TABLE_LENGTH; |
| map->table = |
| nghttp2_mem_calloc(mem, map->tablelen, sizeof(nghttp2_map_entry *)); |
| if (map->table == NULL) { |
| return NGHTTP2_ERR_NOMEM; |
| } |
| |
| map->size = 0; |
| |
| return 0; |
| } |
| |
| void nghttp2_map_free(nghttp2_map *map) { |
| nghttp2_mem_free(map->mem, map->table); |
| } |
| |
| void nghttp2_map_each_free(nghttp2_map *map, |
| int (*func)(nghttp2_map_entry *entry, void *ptr), |
| void *ptr) { |
| uint32_t i; |
| for (i = 0; i < map->tablelen; ++i) { |
| nghttp2_map_entry *entry; |
| for (entry = map->table[i]; entry;) { |
| nghttp2_map_entry *next = entry->next; |
| func(entry, ptr); |
| entry = next; |
| } |
| map->table[i] = NULL; |
| } |
| } |
| |
| int nghttp2_map_each(nghttp2_map *map, |
| int (*func)(nghttp2_map_entry *entry, void *ptr), |
| void *ptr) { |
| int rv; |
| uint32_t i; |
| for (i = 0; i < map->tablelen; ++i) { |
| nghttp2_map_entry *entry; |
| for (entry = map->table[i]; entry; entry = entry->next) { |
| rv = func(entry, ptr); |
| if (rv != 0) { |
| return rv; |
| } |
| } |
| } |
| return 0; |
| } |
| |
| void nghttp2_map_entry_init(nghttp2_map_entry *entry, key_type key) { |
| entry->key = key; |
| entry->next = NULL; |
| } |
| |
| /* Same hash function in android HashMap source code. */ |
| /* The |mod| must be power of 2 */ |
| static uint32_t hash(int32_t key, uint32_t mod) { |
| uint32_t h = (uint32_t)key; |
| h ^= (h >> 20) ^ (h >> 12); |
| h ^= (h >> 7) ^ (h >> 4); |
| return h & (mod - 1); |
| } |
| |
| static int insert(nghttp2_map_entry **table, uint32_t tablelen, |
| nghttp2_map_entry *entry) { |
| uint32_t h = hash(entry->key, tablelen); |
| if (table[h] == NULL) { |
| table[h] = entry; |
| } else { |
| nghttp2_map_entry *p; |
| /* We won't allow duplicated key, so check it out. */ |
| for (p = table[h]; p; p = p->next) { |
| if (p->key == entry->key) { |
| return NGHTTP2_ERR_INVALID_ARGUMENT; |
| } |
| } |
| entry->next = table[h]; |
| table[h] = entry; |
| } |
| return 0; |
| } |
| |
| /* new_tablelen must be power of 2 */ |
| static int resize(nghttp2_map *map, uint32_t new_tablelen) { |
| uint32_t i; |
| nghttp2_map_entry **new_table; |
| |
| new_table = |
| nghttp2_mem_calloc(map->mem, new_tablelen, sizeof(nghttp2_map_entry *)); |
| if (new_table == NULL) { |
| return NGHTTP2_ERR_NOMEM; |
| } |
| |
| for (i = 0; i < map->tablelen; ++i) { |
| nghttp2_map_entry *entry; |
| for (entry = map->table[i]; entry;) { |
| nghttp2_map_entry *next = entry->next; |
| entry->next = NULL; |
| /* This function must succeed */ |
| insert(new_table, new_tablelen, entry); |
| entry = next; |
| } |
| } |
| nghttp2_mem_free(map->mem, map->table); |
| map->tablelen = new_tablelen; |
| map->table = new_table; |
| |
| return 0; |
| } |
| |
| int nghttp2_map_insert(nghttp2_map *map, nghttp2_map_entry *new_entry) { |
| int rv; |
| /* Load factor is 0.75 */ |
| if ((map->size + 1) * 4 > map->tablelen * 3) { |
| rv = resize(map, map->tablelen * 2); |
| if (rv != 0) { |
| return rv; |
| } |
| } |
| rv = insert(map->table, map->tablelen, new_entry); |
| if (rv != 0) { |
| return rv; |
| } |
| ++map->size; |
| return 0; |
| } |
| |
| nghttp2_map_entry *nghttp2_map_find(nghttp2_map *map, key_type key) { |
| uint32_t h; |
| nghttp2_map_entry *entry; |
| h = hash(key, map->tablelen); |
| for (entry = map->table[h]; entry; entry = entry->next) { |
| if (entry->key == key) { |
| return entry; |
| } |
| } |
| return NULL; |
| } |
| |
| int nghttp2_map_remove(nghttp2_map *map, key_type key) { |
| uint32_t h; |
| nghttp2_map_entry **dst; |
| |
| h = hash(key, map->tablelen); |
| |
| for (dst = &map->table[h]; *dst; dst = &(*dst)->next) { |
| if ((*dst)->key != key) { |
| continue; |
| } |
| |
| *dst = (*dst)->next; |
| --map->size; |
| return 0; |
| } |
| return NGHTTP2_ERR_INVALID_ARGUMENT; |
| } |
| |
| size_t nghttp2_map_size(nghttp2_map *map) { return map->size; } |