From 23ac1f4f98accc3bb84e81be264d8408be372028 Mon Sep 17 00:00:00 2001 From: Nicholas Noll Date: Sun, 17 May 2020 18:28:05 -0700 Subject: fix: bugs associated to map reallocating --- include/libn.h | 5 +++++ include/libn/macro/map.h | 23 +++++++++++++---------- 2 files changed, 18 insertions(+), 10 deletions(-) (limited to 'include') diff --git a/include/libn.h b/include/libn.h index 87c993c..8e21056 100644 --- a/include/libn.h +++ b/include/libn.h @@ -76,6 +76,11 @@ void *·alloc(void* _, uint n, ulong size) { return malloc(n*size); } +static +void *·calloc(void* _, uint n, ulong size) { + return calloc(n, size); +} + // TODO(nnoll): Allow for nil iterfaces? static mem·Allocator mem·sys = { diff --git a/include/libn/macro/map.h b/include/libn/macro/map.h index 45eb745..bbd4a91 100644 --- a/include/libn/macro/map.h +++ b/include/libn/macro/map.h @@ -62,10 +62,12 @@ static const double __ac_HASH_UPPER = 0.77; while (!__ac_isempty(map->flags, i) && \ (__ac_isdel(map->flags, i) || !equalfunc(map->keys[i], key))) { \ i = (i + (++step)) & mask; \ - if (i == last) \ + if (i == last) { \ i = map->n_buckets; \ + break; \ + } \ } \ - if (__ac_iseither(map->flags, i)) \ + if (i < map->n_buckets && __ac_iseither(map->flags, i)) \ i = map->n_buckets; \ } else \ i = 0; @@ -80,25 +82,24 @@ static const double __ac_HASH_UPPER = 0.77; if (map->size >= (int32)(new_n_buckets * __ac_HASH_UPPER + 0.5)) \ j = 0; \ else { \ - new_flags = \ - alloc(h, __ac_fsize(new_n_buckets), sizeof(int32)); \ + new_flags = alloc(h, __ac_fsize(new_n_buckets), sizeof(int32)); \ if (!new_flags) return -1; \ memset(new_flags, 0xaa, __ac_fsize(new_n_buckets) * sizeof(int32)); \ if (map->n_buckets < new_n_buckets) { /* expand */ \ - key_t *new_keys = \ - alloc(h, new_n_buckets, sizeof(key_t)); \ + key_t *new_keys = alloc(h, new_n_buckets, sizeof(key_t)); \ if (!new_keys) { \ free(h, new_flags); \ return -1; \ } \ + memcpy(new_keys, map->keys, sizeof(key_t) * map->n_buckets); \ free(h, map->keys); \ map->keys = new_keys; \ - val_t *new_vals = \ - alloc(h, new_n_buckets, sizeof(val_t)); \ + val_t *new_vals = alloc(h, new_n_buckets, sizeof(val_t)); \ if (!new_vals) { \ free(h, new_flags); \ return -1; \ } \ + memcpy(new_vals, map->vals, sizeof(val_t) * map->n_buckets); \ free(h, map->vals); \ map->vals = new_vals; \ } \ @@ -142,16 +143,18 @@ static const double __ac_HASH_UPPER = 0.77; } \ if (map->n_buckets > new_n_buckets) { /* shrink the hash table */ \ key_t *new_keys = alloc(h, new_n_buckets, sizeof(key_t)); \ + memcpy(new_keys, map->keys, sizeof(key_t) * map->n_buckets); \ free(h, map->keys); \ map->keys = new_keys; \ \ val_t *new_vals = alloc(h, new_n_buckets, sizeof(val_t)); \ + memcpy(new_vals, map->vals, sizeof(val_t) * map->n_buckets); \ free(h, map->vals); \ map->vals = new_vals; \ } \ free(h, map->flags); /* free the working space */ \ - map->flags = new_flags; \ - map->n_buckets = new_n_buckets; \ + map->flags = new_flags; \ + map->n_buckets = new_n_buckets; \ map->n_occupied = map->size; \ map->upper_bound = (int32)(map->n_buckets * __ac_HASH_UPPER + 0.5); \ } \ -- cgit v1.2.1