diff options
Diffstat (limited to 'deps/nghttp3/lib/nghttp3_map.c')
-rw-r--r-- | deps/nghttp3/lib/nghttp3_map.c | 244 |
1 files changed, 184 insertions, 60 deletions
diff --git a/deps/nghttp3/lib/nghttp3_map.c b/deps/nghttp3/lib/nghttp3_map.c index e383d2b0b8a..e8eb811566d 100644 --- a/deps/nghttp3/lib/nghttp3_map.c +++ b/deps/nghttp3/lib/nghttp3_map.c @@ -27,6 +27,7 @@ #include "nghttp3_map.h" #include <string.h> +#include <assert.h> #include "nghttp3_conv.h" @@ -36,7 +37,7 @@ int nghttp3_map_init(nghttp3_map *map, const nghttp3_mem *mem) { map->mem = mem; map->tablelen = INITIAL_TABLE_LENGTH; map->table = - nghttp3_mem_calloc(mem, map->tablelen, sizeof(nghttp3_map_entry *)); + nghttp3_mem_calloc(mem, map->tablelen, sizeof(nghttp3_map_bucket)); if (map->table == NULL) { return NGHTTP3_ERR_NOMEM; } @@ -47,38 +48,82 @@ int nghttp3_map_init(nghttp3_map *map, const nghttp3_mem *mem) { } void nghttp3_map_free(nghttp3_map *map) { + size_t i; + nghttp3_map_bucket *bkt; + + if (!map) { + return; + } + + for (i = 0; i < map->tablelen; ++i) { + bkt = &map->table[i]; + if (bkt->ksl) { + nghttp3_ksl_free(bkt->ksl); + nghttp3_mem_free(map->mem, bkt->ksl); + } + } + nghttp3_mem_free(map->mem, map->table); } -void nghttp3_map_each_free(const nghttp3_map *map, +void nghttp3_map_each_free(nghttp3_map *map, int (*func)(nghttp3_map_entry *entry, void *ptr), void *ptr) { uint32_t i; + nghttp3_map_bucket *bkt; + nghttp3_ksl_it it; + for (i = 0; i < map->tablelen; ++i) { - nghttp3_map_entry *entry; - for (entry = map->table[i]; entry;) { - nghttp3_map_entry *next = entry->next; - func(entry, ptr); - entry = next; + bkt = &map->table[i]; + + if (bkt->ptr) { + func(bkt->ptr, ptr); + bkt->ptr = NULL; + assert(bkt->ksl == NULL || nghttp3_ksl_len(bkt->ksl) == 0); + continue; + } + + if (bkt->ksl) { + for (it = nghttp3_ksl_begin(bkt->ksl); !nghttp3_ksl_it_end(&it); + nghttp3_ksl_it_next(&it)) { + func(nghttp3_ksl_it_get(&it), ptr); + } + + nghttp3_ksl_free(bkt->ksl); + nghttp3_mem_free(map->mem, bkt->ksl); + bkt->ksl = NULL; } - map->table[i] = NULL; } } -int nghttp3_map_each(const nghttp3_map *map, +int nghttp3_map_each(nghttp3_map *map, int (*func)(nghttp3_map_entry *entry, void *ptr), void *ptr) { int rv; uint32_t i; + nghttp3_map_bucket *bkt; + nghttp3_ksl_it it; + for (i = 0; i < map->tablelen; ++i) { - nghttp3_map_entry *entry, *next; - for (entry = map->table[i]; entry;) { - next = entry->next; - rv = func(entry, ptr); + bkt = &map->table[i]; + + if (bkt->ptr) { + rv = func(bkt->ptr, ptr); if (rv != 0) { return rv; } - entry = next; + assert(bkt->ksl == NULL || nghttp3_ksl_len(bkt->ksl) == 0); + continue; + } + + if (bkt->ksl) { + for (it = nghttp3_ksl_begin(bkt->ksl); !nghttp3_ksl_it_end(&it); + nghttp3_ksl_it_next(&it)) { + rv = func(nghttp3_ksl_it_get(&it), ptr); + if (rv != 0) { + return rv; + } + } } } return 0; @@ -98,71 +143,125 @@ static uint32_t hash(key_type key, uint32_t mod) { p = (uint8_t *)&key; end = p + sizeof(key_type); - for (; p != end; ++p) { - h ^= *p; - h *= 0x01000193u; + for (; p != end;) { + h ^= *p++; + h += (h << 1) + (h << 4) + (h << 7) + (h << 8) + (h << 24); } return h & (mod - 1); } -static int insert(nghttp3_map_entry **table, uint32_t tablelen, - nghttp3_map_entry *entry) { +static int less(const nghttp3_ksl_key *lhs, const nghttp3_ksl_key *rhs) { + return *(key_type *)lhs < *(key_type *)rhs; +} + +static int map_insert(nghttp3_map *map, nghttp3_map_bucket *table, + uint32_t tablelen, nghttp3_map_entry *entry) { uint32_t h = hash(entry->key, tablelen); - if (table[h] == NULL) { - table[h] = entry; - } else { - nghttp3_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 NGHTTP3_ERR_INVALID_ARGUMENT; - } + nghttp3_map_bucket *bkt = &table[h]; + const nghttp3_mem *mem = map->mem; + int rv; + + if (bkt->ptr == NULL && + (bkt->ksl == NULL || nghttp3_ksl_len(bkt->ksl) == 0)) { + bkt->ptr = entry; + return 0; + } + + if (!bkt->ksl) { + bkt->ksl = nghttp3_mem_malloc(mem, sizeof(*bkt->ksl)); + if (bkt->ksl == NULL) { + return NGHTTP3_ERR_NOMEM; } - entry->next = table[h]; - table[h] = entry; + nghttp3_ksl_init(bkt->ksl, less, sizeof(key_type), mem); } - return 0; + + if (bkt->ptr) { + rv = nghttp3_ksl_insert(bkt->ksl, NULL, &bkt->ptr->key, bkt->ptr); + if (rv != 0) { + return rv; + } + + bkt->ptr = NULL; + } + + return nghttp3_ksl_insert(bkt->ksl, NULL, &entry->key, entry); } /* new_tablelen must be power of 2 */ -static int resize(nghttp3_map *map, uint32_t new_tablelen) { +static int map_resize(nghttp3_map *map, uint32_t new_tablelen) { uint32_t i; - nghttp3_map_entry **new_table; + nghttp3_map_bucket *new_table; + nghttp3_map_bucket *bkt; + nghttp3_ksl_it it; + int rv; new_table = - nghttp3_mem_calloc(map->mem, new_tablelen, sizeof(nghttp3_map_entry *)); + nghttp3_mem_calloc(map->mem, new_tablelen, sizeof(nghttp3_map_bucket)); if (new_table == NULL) { return NGHTTP3_ERR_NOMEM; } for (i = 0; i < map->tablelen; ++i) { - nghttp3_map_entry *entry; - for (entry = map->table[i]; entry;) { - nghttp3_map_entry *next = entry->next; - entry->next = NULL; - /* This function must succeed */ - insert(new_table, new_tablelen, entry); - entry = next; + bkt = &map->table[i]; + + if (bkt->ptr) { + rv = map_insert(map, new_table, new_tablelen, bkt->ptr); + if (rv != 0) { + goto fail; + } + assert(bkt->ksl == NULL || nghttp3_ksl_len(bkt->ksl) == 0); + continue; + } + + if (bkt->ksl) { + for (it = nghttp3_ksl_begin(bkt->ksl); !nghttp3_ksl_it_end(&it); + nghttp3_ksl_it_next(&it)) { + rv = map_insert(map, new_table, new_tablelen, nghttp3_ksl_it_get(&it)); + if (rv != 0) { + goto fail; + } + } + } + } + + for (i = 0; i < map->tablelen; ++i) { + bkt = &map->table[i]; + if (bkt->ksl) { + nghttp3_ksl_free(bkt->ksl); + nghttp3_mem_free(map->mem, bkt->ksl); } } + nghttp3_mem_free(map->mem, map->table); map->tablelen = new_tablelen; map->table = new_table; return 0; + +fail: + for (i = 0; i < new_tablelen; ++i) { + bkt = &new_table[i]; + if (bkt->ksl) { + nghttp3_ksl_free(bkt->ksl); + nghttp3_mem_free(map->mem, bkt->ksl); + } + } + + return rv; } int nghttp3_map_insert(nghttp3_map *map, nghttp3_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); + rv = map_resize(map, map->tablelen * 2); if (rv != 0) { return rv; } } - rv = insert(map->table, map->tablelen, new_entry); + rv = map_insert(map, map->table, map->tablelen, new_entry); if (rv != 0) { return rv; } @@ -170,44 +269,69 @@ int nghttp3_map_insert(nghttp3_map *map, nghttp3_map_entry *new_entry) { return 0; } -nghttp3_map_entry *nghttp3_map_find(const nghttp3_map *map, key_type key) { - uint32_t h; - nghttp3_map_entry *entry; - h = hash(key, map->tablelen); - for (entry = map->table[h]; entry; entry = entry->next) { - if (entry->key == key) { - return entry; +nghttp3_map_entry *nghttp3_map_find(nghttp3_map *map, key_type key) { + nghttp3_map_bucket *bkt = &map->table[hash(key, map->tablelen)]; + nghttp3_ksl_it it; + + if (bkt->ptr) { + if (bkt->ptr->key == key) { + return bkt->ptr; } + return NULL; } + + if (bkt->ksl) { + it = nghttp3_ksl_lower_bound(bkt->ksl, &key); + if (nghttp3_ksl_it_end(&it) || + *(key_type *)nghttp3_ksl_it_key(&it) != key) { + return NULL; + } + return nghttp3_ksl_it_get(&it); + } + return NULL; } int nghttp3_map_remove(nghttp3_map *map, key_type key) { - uint32_t h; - nghttp3_map_entry **dst; - - h = hash(key, map->tablelen); + nghttp3_map_bucket *bkt = &map->table[hash(key, map->tablelen)]; + int rv; - for (dst = &map->table[h]; *dst; dst = &(*dst)->next) { - if ((*dst)->key != key) { - continue; + if (bkt->ptr) { + if (bkt->ptr->key == key) { + bkt->ptr = NULL; + --map->size; + return 0; } + return NGHTTP3_ERR_INVALID_ARGUMENT; + } - *dst = (*dst)->next; + if (bkt->ksl) { + rv = nghttp3_ksl_remove(bkt->ksl, NULL, &key); + if (rv != 0) { + return rv; + } --map->size; return 0; } + return NGHTTP3_ERR_INVALID_ARGUMENT; } void nghttp3_map_clear(nghttp3_map *map) { uint32_t i; + nghttp3_map_bucket *bkt; for (i = 0; i < map->tablelen; ++i) { - map->table[i] = NULL; + bkt = &map->table[i]; + bkt->ptr = NULL; + if (bkt->ksl) { + nghttp3_ksl_free(bkt->ksl); + nghttp3_mem_free(map->mem, bkt->ksl); + bkt->ksl = NULL; + } } map->size = 0; } -size_t nghttp3_map_size(const nghttp3_map *map) { return map->size; } +size_t nghttp3_map_size(nghttp3_map *map) { return map->size; } |