From f6e83e64abbf76bbfddc90f885f7c3be379ecf2c Mon Sep 17 00:00:00 2001 From: Katharina Fey Date: Sun, 14 Jul 2019 18:41:07 +0100 Subject: Various improvements around HASH nodes The example previously would lead to corrupt memory when running for items that needed to re-hash the hash array. This has been fixed. Secondly, all HASH node memory leaks are now fixed, that resulted from badly tracking objects through the resize process. A new function `hash_free_shallow` was added to help with this. The function `array_free_shallow` is unused but might become useful in the future and so was not removed. The hash strategy is still garbage but this can be fixed later :) --- array.c | 15 ++++++++++++--- array.h | 4 +++- bowl.c | 5 +++-- hash.c | 55 ++++++++++++++++++++++++++++++++++++++++++++++++------- hash.h | 4 ++++ utils.c | 2 +- 6 files changed, 71 insertions(+), 14 deletions(-) diff --git a/array.c b/array.c index b0db3f5..78317e9 100644 --- a/array.c +++ b/array.c @@ -12,7 +12,7 @@ err_t array_malloc(struct bowl *self, size_t size) struct bowl_arr *arr = malloc(sizeof(struct bowl_arr)); CHECK(arr, MALLOC_FAILED) - arr->size = 2; + arr->size = size; arr->used = 0; struct bowl **ptr = calloc(sizeof(struct bowl *), arr->size); @@ -109,12 +109,21 @@ err_t array_free(struct bowl *self) struct bowl_arr *arr = self->_pl.array; CHECK(arr, INVALID_STATE) + err_t e; for(int i = 0; i < arr->used; i++) { - err_t e = bowl_free(arr->ptr[i]); + e = bowl_free(arr->ptr[i]); if(e) break; } + free(arr->ptr); + free(arr); + return e; +} + +err_t array_free_shallow(struct bowl_arr *arr) +{ + CHECK(arr, INVALID_STATE) free(arr->ptr); free(arr); return OK; -} \ No newline at end of file +} diff --git a/array.h b/array.h index d35a1f8..a1ac8c0 100644 --- a/array.h +++ b/array.h @@ -21,7 +21,9 @@ err_t array_remove_key(struct bowl *, size_t, struct bowl **); err_t array_free(struct bowl *); +err_t array_free_shallow(struct bowl_arr *); + #ifdef __cplusplus } #endif -#endif // _ARRAY_H_ \ No newline at end of file +#endif // _ARRAY_H_ diff --git a/bowl.c b/bowl.c index e515f6b..248ac37 100644 --- a/bowl.c +++ b/bowl.c @@ -31,7 +31,7 @@ err_t bowl_malloc(struct bowl **ptr, bowl_t type) switch((*ptr)->type) { case LEAF: return OK; // No further allocation needed - case ARRAY: return array_malloc(*ptr, ARRAY_START_SIZE); + case ARRAY | HASH: return array_malloc(*ptr, ARRAY_START_SIZE); default: return INVALID_STATE; } @@ -139,7 +139,8 @@ err_t bowl_free(struct bowl *self) err_t e; switch(self->type) { case LEAF: e = data_free(self->_pl.data); break; - case ARRAY | HASH: e = array_free(self); break; + case ARRAY: e = array_free(self); break; + case HASH: e = hash_free(self); break; default: e = INVALID_STATE; break; } if(e) return e; diff --git a/hash.c b/hash.c index 5ee4f90..f1abfb3 100644 --- a/hash.c +++ b/hash.c @@ -26,9 +26,9 @@ err_t hash_insert_key(struct bowl *self, char *key, struct bowl *child) // If the index is used, rescale and try again if(arr->ptr[idx] != NULL) { - struct bowl *prev = self; + struct bowl_arr *prev = arr; - // Allocate new array + // Allocate new hash array e = array_malloc(self, arr->size * 2); if(e) return e; @@ -41,12 +41,11 @@ err_t hash_insert_key(struct bowl *self, char *key, struct bowl *child) } } - e = array_free(prev); - if(e) return e; - e = hash_insert_key(self, key, child); if(e) return e; + hash_free_shallow(prev); + } else { hash_item *item = malloc(sizeof(hash_item)); CHECK(item, MALLOC_FAILED) @@ -58,6 +57,7 @@ err_t hash_insert_key(struct bowl *self, char *key, struct bowl *child) item->data = child; arr->ptr[idx] = (struct bowl*) item; + arr->used += 1; } return OK; @@ -65,7 +65,6 @@ err_t hash_insert_key(struct bowl *self, char *key, struct bowl *child) err_t hash_remove_key(struct bowl *self, char *key, struct bowl **child) { - CHECK(self, INVALID_STATE) CHECK(child, INVALID_STATE) CHECK(key, INVALID_STATE) @@ -79,7 +78,49 @@ err_t hash_remove_key(struct bowl *self, char *key, struct bowl **child) if(e) return e; (*child) = arr->ptr[idx]; + arr->used -= 1; arr->ptr[idx] = NULL; return OK; } - + +err_t hash_free(struct bowl *self) +{ + CHECK(self, INVALID_PARAMS) + struct bowl_arr *arr = self->_pl.array; + CHECK(arr, INVALID_PARAMS) + + err_t e = OK; + for(int i = 0; i < arr->size; i++) { + hash_item *item = (hash_item *) arr->ptr[i]; + if(item != NULL) { + CHECK(item->data, INVALID_STATE) + CHECK(item->key, INVALID_STATE) + + e = bowl_free(item->data); + if(e) break; + + free(item->key); + free(item); + } + } + + free(arr->ptr); + free(arr); + return e; +} + +err_t hash_free_shallow(struct bowl_arr *arr) +{ + CHECK(arr, INVALID_PARAMS); + for(int i = 0; i < arr->size; i++) { + hash_item *item = (hash_item *) arr->ptr[i]; + if(item != NULL) { + free(item->key); + free(item); + } + } + + free(arr->ptr); + free(arr); + return OK; +} diff --git a/hash.h b/hash.h index a5d763d..369d849 100644 --- a/hash.h +++ b/hash.h @@ -7,5 +7,9 @@ err_t hash_insert_key(struct bowl *, char *key, struct bowl *); err_t hash_remove_key(struct bowl *, char *key, struct bowl **); +err_t hash_free(struct bowl *); + +err_t hash_free_shallow(struct bowl_arr *); + #endif // HASH_H_ diff --git a/utils.c b/utils.c index f08c670..0979d07 100644 --- a/utils.c +++ b/utils.c @@ -49,7 +49,7 @@ err_t _array_remove(void **ptr, size_t idx, size_t len, void **out) err_t _hash(char *str, size_t len, size_t *out) { CHECK(str, INVALID_PARAMS) - CHECK((len < 0), INVALID_PARAMS) + CHECK((len > 0), INVALID_PARAMS) // Implements the "murmur" non-cryptographic hash -- cgit v1.2.3