From 164a35fbd7d04f3bb384ba6cb5510ee43c41a4a2 Mon Sep 17 00:00:00 2001 From: Stephen Seo Date: Mon, 11 Feb 2019 11:23:08 +0900 Subject: [PATCH] Add HashMap realloc/clear, fixes --- src/UDPC_HashMap.c | 99 ++++++++++++++++++++++++++++++++++++++++++++-- src/UDPC_HashMap.h | 32 +++++++++++---- 2 files changed, 120 insertions(+), 11 deletions(-) diff --git a/src/UDPC_HashMap.c b/src/UDPC_HashMap.c index e039612..8533037 100644 --- a/src/UDPC_HashMap.c +++ b/src/UDPC_HashMap.c @@ -13,7 +13,7 @@ UDPC_HashMap* UDPC_HashMap_init(uint32_t capacity, uint32_t unitSize) int fail = 0; m->size = 0; - m->capacity = (capacity > 10 ? capacity : 10); + m->capacity = (capacity > UDPC_HASHMAP_INIT_CAPACITY ? capacity : UDPC_HASHMAP_INIT_CAPACITY); m->unitSize = unitSize; m->buckets = malloc(sizeof(UDPC_Deque*) * m->capacity); @@ -30,7 +30,7 @@ UDPC_HashMap* UDPC_HashMap_init(uint32_t capacity, uint32_t unitSize) m->buckets[x] = NULL; continue; } - m->buckets[x] = UDPC_Deque_init(unitSize * UDPC_HASHMAP_BUCKET_SIZE); + m->buckets[x] = UDPC_Deque_init(UDPC_HASHMAP_BUCKET_SIZE * (sizeof(uint32_t) + unitSize)); if(!m->buckets[x]) { fail = 1; @@ -51,7 +51,7 @@ UDPC_HashMap* UDPC_HashMap_init(uint32_t capacity, uint32_t unitSize) return NULL; } - m->overflow = UDPC_Deque_init(unitSize * UDPC_HASHMAP_BUCKET_SIZE); + m->overflow = UDPC_Deque_init(UDPC_HASHMAP_BUCKET_SIZE * (sizeof(uint32_t) + unitSize)); if(!m->overflow) { for(int x = 0; x < m->capacity; ++x) @@ -82,6 +82,14 @@ void UDPC_HashMap_destroy(UDPC_HashMap *hashMap) void* UDPC_HashMap_insert(UDPC_HashMap *hm, uint32_t key, void *data) { + if(hm->capacity <= hm->size) + { + if(UDPC_HashMap_realloc(hm, hm->capacity * 2) == 0) + { + return NULL; + } + } + uint32_t hash = UDPC_HASH32(key) % hm->capacity; char *temp = malloc(sizeof(uint32_t) + hm->unitSize); @@ -195,3 +203,88 @@ void* UDPC_HashMap_get(UDPC_HashMap *hm, uint32_t key) return NULL; } + +int UDPC_HashMap_realloc(UDPC_HashMap *hm, uint32_t newCapacity) +{ + if(hm->size > newCapacity) + { + return 0; + } + + UDPC_Deque **newBuckets = malloc(sizeof(UDPC_Deque*) * newCapacity); + UDPC_Deque *newOverflow = UDPC_Deque_init(UDPC_HASHMAP_BUCKET_SIZE + * (sizeof(uint32_t) + hm->unitSize)); + for(int x = 0; x < newCapacity; ++x) + { + *newBuckets = UDPC_Deque_init(UDPC_HASHMAP_BUCKET_SIZE + * (sizeof(uint32_t) + hm->unitSize)); + } + + uint32_t hash; + char *data; + int fail = 0; + for(int x = 0; x < hm->capacity; ++x) + { + for(int y = 0; y * (sizeof(uint32_t) + hm->unitSize) < hm->buckets[x]->size; ++y) + { + data = UDPC_Deque_index_ptr(hm->buckets[x], sizeof(uint32_t) + hm->unitSize, y); + hash = UDPC_HASH32(*((uint32_t*)data)) % newCapacity; + if(newBuckets[hash]->size < newBuckets[hash]->alloc_size) + { + if(UDPC_Deque_push_back(newBuckets[hash], data, sizeof(uint32_t) + hm->unitSize) == 0) + { + fail = 1; + break; + } + } + else + { + if(UDPC_Deque_push_back(newOverflow, data, sizeof(uint32_t) + hm->unitSize) == 0) + { + fail = 1; + break; + } + } + } + if(fail != 0) + { + break; + } + } + + if(fail != 0) + { + for(int x = 0; x < newCapacity; ++x) + { + UDPC_Deque_destroy(newBuckets[x]); + } + free(newBuckets); + UDPC_Deque_destroy(newOverflow); + return 0; + } + else + { + for(int x = 0; x < hm->capacity; ++x) + { + UDPC_Deque_destroy(hm->buckets[x]); + } + free(hm->buckets); + UDPC_Deque_destroy(hm->overflow); + + hm->buckets = newBuckets; + hm->overflow = newOverflow; + + hm->capacity = newCapacity; + return 1; + } +} + +void UDPC_HashMap_clear(UDPC_HashMap *hm) +{ + for(int x = 0; x < hm->capacity; ++x) + { + UDPC_Deque_clear(hm->buckets[x]); + } + UDPC_Deque_clear(hm->overflow); + hm->size = 0; +} diff --git a/src/UDPC_HashMap.h b/src/UDPC_HashMap.h index 73103ae..9739b89 100644 --- a/src/UDPC_HashMap.h +++ b/src/UDPC_HashMap.h @@ -5,16 +5,17 @@ // 3 2 5 1 8 7 6 #define UDPC_HASH32(x) ( \ ( \ - ((x & 0xF8000000) >> 5) | \ - ((x & 0x07F80000) >> 6) | \ - ((x & 0x00060000) << 10) | \ - ((x & 0x0001FC00) >> 4) | \ - ((x & 0x00000380) << 22) | \ - ((x & 0x0000007E) >> 1) | \ - ((x & 0x00000001) << 21) \ + (((x) & 0xF8000000) >> 5) | \ + (((x) & 0x07F80000) >> 6) | \ + (((x) & 0x00060000) << 10) | \ + (((x) & 0x0001FC00) >> 4) | \ + (((x) & 0x00000380) << 22) | \ + (((x) & 0x0000007E) >> 1) | \ + (((x) & 0x00000001) << 21) \ ) ^ 0x96969696 \ ) +#define UDPC_HASHMAP_INIT_CAPACITY 8 #define UDPC_HASHMAP_BUCKET_SIZE 4 #include "UDPC_Deque.h" @@ -42,7 +43,10 @@ void UDPC_HashMap_destroy(UDPC_HashMap *hashMap); /*! * \brief Inserts a copy of data pointed to by given pointer - * \return Internally managed pointer to inserted data + * Note if size already equals capacity, the hash map's capacity is doubled + * with UDPC_HashMap_realloc(). realloc requires rehashing of all items which + * may be costly. + * \return Internally managed pointer to inserted data, NULL on fail */ void* UDPC_HashMap_insert(UDPC_HashMap *hm, uint32_t key, void *data); @@ -58,4 +62,16 @@ int UDPC_HashMap_remove(UDPC_HashMap *hm, uint32_t key); */ void* UDPC_HashMap_get(UDPC_HashMap *hm, uint32_t key); +/*! + * \brief Resizes the maximum capacity of a hash map + * Note on fail, the hash map is unchanged. + * \return non-zero if resizing was successful + */ +int UDPC_HashMap_realloc(UDPC_HashMap *hm, uint32_t newCapacity); + +/*! + * \brief Empties the hash map + */ +void UDPC_HashMap_clear(UDPC_HashMap *hm); + #endif -- 2.49.0