diff options
Diffstat (limited to 'deps/ngtcp2/lib/ngtcp2_map.c')
| -rw-r--r-- | deps/ngtcp2/lib/ngtcp2_map.c | 239 |
1 files changed, 181 insertions, 58 deletions
diff --git a/deps/ngtcp2/lib/ngtcp2_map.c b/deps/ngtcp2/lib/ngtcp2_map.c index bd214ff87b5..12a20283b4c 100644 --- a/deps/ngtcp2/lib/ngtcp2_map.c +++ b/deps/ngtcp2/lib/ngtcp2_map.c @@ -26,6 +26,7 @@ #include "ngtcp2_map.h" #include <string.h> +#include <assert.h> #include "ngtcp2_conv.h" @@ -34,8 +35,7 @@ int ngtcp2_map_init(ngtcp2_map *map, const ngtcp2_mem *mem) { map->mem = mem; map->tablelen = INITIAL_TABLE_LENGTH; - map->table = - ngtcp2_mem_calloc(mem, map->tablelen, sizeof(ngtcp2_map_entry *)); + map->table = ngtcp2_mem_calloc(mem, map->tablelen, sizeof(ngtcp2_map_bucket)); if (map->table == NULL) { return NGTCP2_ERR_NOMEM; } @@ -45,20 +45,52 @@ int ngtcp2_map_init(ngtcp2_map *map, const ngtcp2_mem *mem) { return 0; } -void ngtcp2_map_free(ngtcp2_map *map) { ngtcp2_mem_free(map->mem, map->table); } +void ngtcp2_map_free(ngtcp2_map *map) { + size_t i; + ngtcp2_map_bucket *bkt; + + if (!map) { + return; + } + + for (i = 0; i < map->tablelen; ++i) { + bkt = &map->table[i]; + if (bkt->ksl) { + ngtcp2_ksl_free(bkt->ksl); + ngtcp2_mem_free(map->mem, bkt->ksl); + } + } + + ngtcp2_mem_free(map->mem, map->table); +} void ngtcp2_map_each_free(ngtcp2_map *map, int (*func)(ngtcp2_map_entry *entry, void *ptr), void *ptr) { uint32_t i; + ngtcp2_map_bucket *bkt; + ngtcp2_ksl_it it; + for (i = 0; i < map->tablelen; ++i) { - ngtcp2_map_entry *entry; - for (entry = map->table[i]; entry;) { - ngtcp2_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 || ngtcp2_ksl_len(bkt->ksl) == 0); + continue; + } + + if (bkt->ksl) { + for (it = ngtcp2_ksl_begin(bkt->ksl); !ngtcp2_ksl_it_end(&it); + ngtcp2_ksl_it_next(&it)) { + func(ngtcp2_ksl_it_get(&it), ptr); + } + + ngtcp2_ksl_free(bkt->ksl); + ngtcp2_mem_free(map->mem, bkt->ksl); + bkt->ksl = NULL; } - map->table[i] = NULL; } } @@ -67,15 +99,29 @@ int ngtcp2_map_each(ngtcp2_map *map, void *ptr) { int rv; uint32_t i; + ngtcp2_map_bucket *bkt; + ngtcp2_ksl_it it; + for (i = 0; i < map->tablelen; ++i) { - ngtcp2_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 || ngtcp2_ksl_len(bkt->ksl) == 0); + continue; + } + + if (bkt->ksl) { + for (it = ngtcp2_ksl_begin(bkt->ksl); !ngtcp2_ksl_it_end(&it); + ngtcp2_ksl_it_next(&it)) { + rv = func(ngtcp2_ksl_it_get(&it), ptr); + if (rv != 0) { + return rv; + } + } } } return 0; @@ -95,71 +141,124 @@ 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(ngtcp2_map_entry **table, uint32_t tablelen, - ngtcp2_map_entry *entry) { +static int less(const ngtcp2_ksl_key *lhs, const ngtcp2_ksl_key *rhs) { + return *(key_type *)lhs < *(key_type *)rhs; +} + +static int map_insert(ngtcp2_map *map, ngtcp2_map_bucket *table, + uint32_t tablelen, ngtcp2_map_entry *entry) { uint32_t h = hash(entry->key, tablelen); - if (table[h] == NULL) { - table[h] = entry; - } else { - ngtcp2_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 NGTCP2_ERR_INVALID_ARGUMENT; - } + ngtcp2_map_bucket *bkt = &table[h]; + const ngtcp2_mem *mem = map->mem; + int rv; + + if (bkt->ptr == NULL && (bkt->ksl == NULL || ngtcp2_ksl_len(bkt->ksl) == 0)) { + bkt->ptr = entry; + return 0; + } + + if (!bkt->ksl) { + bkt->ksl = ngtcp2_mem_malloc(mem, sizeof(*bkt->ksl)); + if (bkt->ksl == NULL) { + return NGTCP2_ERR_NOMEM; } - entry->next = table[h]; - table[h] = entry; + ngtcp2_ksl_init(bkt->ksl, less, sizeof(key_type), mem); } - return 0; + + if (bkt->ptr) { + rv = ngtcp2_ksl_insert(bkt->ksl, NULL, &bkt->ptr->key, bkt->ptr); + if (rv != 0) { + return rv; + } + + bkt->ptr = NULL; + } + + return ngtcp2_ksl_insert(bkt->ksl, NULL, &entry->key, entry); } /* new_tablelen must be power of 2 */ -static int resize(ngtcp2_map *map, uint32_t new_tablelen) { +static int map_resize(ngtcp2_map *map, uint32_t new_tablelen) { uint32_t i; - ngtcp2_map_entry **new_table; + ngtcp2_map_bucket *new_table; + ngtcp2_map_bucket *bkt; + ngtcp2_ksl_it it; + int rv; new_table = - ngtcp2_mem_calloc(map->mem, new_tablelen, sizeof(ngtcp2_map_entry *)); + ngtcp2_mem_calloc(map->mem, new_tablelen, sizeof(ngtcp2_map_bucket)); if (new_table == NULL) { return NGTCP2_ERR_NOMEM; } for (i = 0; i < map->tablelen; ++i) { - ngtcp2_map_entry *entry; - for (entry = map->table[i]; entry;) { - ngtcp2_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 || ngtcp2_ksl_len(bkt->ksl) == 0); + continue; + } + + if (bkt->ksl) { + for (it = ngtcp2_ksl_begin(bkt->ksl); !ngtcp2_ksl_it_end(&it); + ngtcp2_ksl_it_next(&it)) { + rv = map_insert(map, new_table, new_tablelen, ngtcp2_ksl_it_get(&it)); + if (rv != 0) { + goto fail; + } + } + } + } + + for (i = 0; i < map->tablelen; ++i) { + bkt = &map->table[i]; + if (bkt->ksl) { + ngtcp2_ksl_free(bkt->ksl); + ngtcp2_mem_free(map->mem, bkt->ksl); } } + ngtcp2_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) { + ngtcp2_ksl_free(bkt->ksl); + ngtcp2_mem_free(map->mem, bkt->ksl); + } + } + + return rv; } int ngtcp2_map_insert(ngtcp2_map *map, ngtcp2_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; } @@ -168,40 +267,64 @@ int ngtcp2_map_insert(ngtcp2_map *map, ngtcp2_map_entry *new_entry) { } ngtcp2_map_entry *ngtcp2_map_find(ngtcp2_map *map, key_type key) { - uint32_t h; - ngtcp2_map_entry *entry; - h = hash(key, map->tablelen); - for (entry = map->table[h]; entry; entry = entry->next) { - if (entry->key == key) { - return entry; + ngtcp2_map_bucket *bkt = &map->table[hash(key, map->tablelen)]; + ngtcp2_ksl_it it; + + if (bkt->ptr) { + if (bkt->ptr->key == key) { + return bkt->ptr; } + return NULL; } + + if (bkt->ksl) { + it = ngtcp2_ksl_lower_bound(bkt->ksl, &key); + if (ngtcp2_ksl_it_end(&it) || *(key_type *)ngtcp2_ksl_it_key(&it) != key) { + return NULL; + } + return ngtcp2_ksl_it_get(&it); + } + return NULL; } int ngtcp2_map_remove(ngtcp2_map *map, key_type key) { - uint32_t h; - ngtcp2_map_entry **dst; - - h = hash(key, map->tablelen); + ngtcp2_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 NGTCP2_ERR_INVALID_ARGUMENT; + } - *dst = (*dst)->next; + if (bkt->ksl) { + rv = ngtcp2_ksl_remove(bkt->ksl, NULL, &key); + if (rv != 0) { + return rv; + } --map->size; return 0; } + return NGTCP2_ERR_INVALID_ARGUMENT; } void ngtcp2_map_clear(ngtcp2_map *map) { uint32_t i; + ngtcp2_map_bucket *bkt; for (i = 0; i < map->tablelen; ++i) { - map->table[i] = NULL; + bkt = &map->table[i]; + bkt->ptr = NULL; + if (bkt->ksl) { + ngtcp2_ksl_free(bkt->ksl); + ngtcp2_mem_free(map->mem, bkt->ksl); + bkt->ksl = NULL; + } } map->size = 0; |