From 61d0111323c7df3326d57856c7120c1af807a062 Mon Sep 17 00:00:00 2001 From: Petri Lehtinen Date: Thu, 30 Apr 2009 16:38:39 +0300 Subject: [PATCH] Bump hashtable, allocate object->hashtable statically Hashtable code from git://github.com/akheron/hashtable.git commit 7331ba6acdb415a2af62ae3e93fdd39c2a83b768 --- src/hashtable.c | 72 +++++++++++++++++++++++++------------------------------ src/hashtable.h | 74 ++++++++++++++++++++++++++++++++++++++++++++++++++------- src/value.c | 19 +++++++-------- 3 files changed, 107 insertions(+), 58 deletions(-) diff --git a/src/hashtable.c b/src/hashtable.c index f95c849..afb3304 100644 --- a/src/hashtable.c +++ b/src/hashtable.c @@ -8,40 +8,15 @@ #include #include "hashtable.h" +typedef struct hashtable_list list_t; +typedef struct hashtable_pair pair_t; +typedef struct hashtable_bucket bucket_t; + #define container_of(ptr_, type_, member_) \ ((type_ *)((char *)ptr_ - (size_t)&((type_ *)0)->member_)) -typedef struct list_t { - struct list_t *prev; - struct list_t *next; -} list_t; - -typedef struct { - void *key; - void *value; - unsigned int hash; - list_t list; -} pair_t; - #define list_to_pair(list_) container_of(list_, pair_t, list) -typedef struct { - list_t *first; - list_t *last; -} bucket_t; - -struct hashtable { - unsigned int size; - bucket_t *buckets; - unsigned int num_buckets; /* index to primes[] */ - list_t list; - - key_hash_fn hash_key; - key_cmp_fn cmp_keys; /* returns non-zero for equal keys */ - free_fn free_key; - free_fn free_value; -}; - static inline void list_init(list_t *list) { list->next = list; @@ -193,22 +168,40 @@ static int hashtable_do_rehash(hashtable_t *hashtable) } -hashtable_t *hashtable_new(key_hash_fn hash_key, key_cmp_fn cmp_keys, - free_fn free_key, free_fn free_value) +hashtable_t *hashtable_create(key_hash_fn hash_key, key_cmp_fn cmp_keys, + free_fn free_key, free_fn free_value) { - unsigned int i; hashtable_t *hashtable = malloc(sizeof(hashtable_t)); if(!hashtable) return NULL; - hashtable->size = 0; - hashtable->num_buckets = 0; /* index to primes[] */ - hashtable->buckets = malloc(num_buckets(hashtable) * sizeof(bucket_t)); - if(!hashtable->buckets) + if(hashtable_init(hashtable, hash_key, cmp_keys, free_key, free_value)) { free(hashtable); return NULL; } + + return hashtable; +} + +void hashtable_destroy(hashtable_t *hashtable) +{ + hashtable_close(hashtable); + free(hashtable); +} + +int hashtable_init(hashtable_t *hashtable, + key_hash_fn hash_key, key_cmp_fn cmp_keys, + free_fn free_key, free_fn free_value) +{ + unsigned int i; + + hashtable->size = 0; + hashtable->num_buckets = 0; /* index to primes[] */ + hashtable->buckets = malloc(num_buckets(hashtable) * sizeof(bucket_t)); + if(!hashtable->buckets) + return -1; + list_init(&hashtable->list); hashtable->hash_key = hash_key; @@ -222,10 +215,10 @@ hashtable_t *hashtable_new(key_hash_fn hash_key, key_cmp_fn cmp_keys, &hashtable->list; } - return hashtable; + return 0; } -void hashtable_free(hashtable_t *hashtable) +void hashtable_close(hashtable_t *hashtable) { list_t *list, *next; pair_t *pair; @@ -241,7 +234,6 @@ void hashtable_free(hashtable_t *hashtable) } free(hashtable->buckets); - free(hashtable); } int hashtable_set(hashtable_t *hashtable, void *key, void *value) @@ -267,11 +259,11 @@ int hashtable_set(hashtable_t *hashtable, void *key, void *value) pair->key = key; pair->value = value; pair->hash = hash; + list_init(&pair->list); index = hash % num_buckets(hashtable); bucket = &hashtable->buckets[index]; - list_init(&pair->list); insert_to_bucket(hashtable, bucket, &pair->list); hashtable->size++; diff --git a/src/hashtable.h b/src/hashtable.h index 6d66383..76666a4 100644 --- a/src/hashtable.h +++ b/src/hashtable.h @@ -8,14 +8,41 @@ #ifndef HASHTABLE_H #define HASHTABLE_H -typedef struct hashtable hashtable_t; - typedef unsigned int (*key_hash_fn)(const void *key); typedef int (*key_cmp_fn)(const void *key1, const void *key2); typedef void (*free_fn)(void *key); +struct hashtable_list { + struct hashtable_list *prev; + struct hashtable_list *next; +}; + +struct hashtable_pair { + void *key; + void *value; + unsigned int hash; + struct hashtable_list list; +}; + +struct hashtable_bucket { + struct hashtable_list *first; + struct hashtable_list *last; +}; + +typedef struct hashtable { + unsigned int size; + struct hashtable_bucket *buckets; + unsigned int num_buckets; /* index to primes[] */ + struct hashtable_list list; + + key_hash_fn hash_key; + key_cmp_fn cmp_keys; /* returns non-zero for equal keys */ + free_fn free_key; + free_fn free_value; +} hashtable_t; + /** - * hashtable_new - Create a hashtable object + * hashtable_create - Create a hashtable object * * @hash_key: The key hashing function * @cmp_keys: The key compare function. Returns non-zero for equal and @@ -24,17 +51,48 @@ typedef void (*free_fn)(void *key); * @free_value: If non-NULL, called for a value that is no longer referenced. * * Returns a new hashtable object that should be freed with - * hashtable_free when it's no longer used. + * hashtable_destroy when it's no longer used, or NULL on failure (out + * of memory). + */ +hashtable_t *hashtable_create(key_hash_fn hash_key, key_cmp_fn cmp_keys, + free_fn free_key, free_fn free_value); + +/** + * hashtable_destroy - Destroy a hashtable object + * + * @hashtable: The hashtable + * + * Destroys a hashtable created with hashtable_create(). */ -hashtable_t *hashtable_new(key_hash_fn hash_key, key_cmp_fn cmp_keys, - free_fn free_key, free_fn free_value); +void hashtable_destroy(hashtable_t *hashtable); /** - * hashtable_free - Destroy a hashtable object + * hashtable_init - Initialize a hashtable object + * + * @hashtable: The (statically allocated) hashtable object + * @hash_key: The key hashing function + * @cmp_keys: The key compare function. Returns non-zero for equal and + * zero for unequal unequal keys + * @free_key: If non-NULL, called for a key that is no longer referenced. + * @free_value: If non-NULL, called for a value that is no longer referenced. + * + * Initializes a statically allocated hashtable object. The object + * should be cleared with hashtable_close when it's no longer used. + * + * Returns 0 on success, -1 on error (out of memory). + */ +int hashtable_init(hashtable_t *hashtable, + key_hash_fn hash_key, key_cmp_fn cmp_keys, + free_fn free_key, free_fn free_value); + +/** + * hashtable_close - Release all resources used by a hashtable object * * @hashtable: The hashtable + * + * Destroys a statically allocated hashtable object. */ -void hashtable_free(hashtable_t *hashtable); +void hashtable_close(hashtable_t *hashtable); /** * hashtable_set - Add/modify value in hashtable diff --git a/src/value.c b/src/value.c index d330203..514faac 100644 --- a/src/value.c +++ b/src/value.c @@ -12,7 +12,7 @@ typedef struct { json_t json; - hashtable_t *hashtable; + hashtable_t hashtable; } json_object_t; typedef struct { @@ -78,9 +78,8 @@ json_t *json_object(void) return NULL; json_init(&object->json, JSON_OBJECT); - object->hashtable = - hashtable_new(hash_string, string_equal, free, value_decref); - if(!object->hashtable) + if(hashtable_init(&object->hashtable, hash_string, string_equal, + free, value_decref)) { free(object); return NULL; @@ -90,7 +89,7 @@ json_t *json_object(void) static void json_delete_object(json_object_t *object) { - hashtable_free(object->hashtable); + hashtable_close(&object->hashtable); free(object); } @@ -101,7 +100,7 @@ json_t *json_object_get(const json_t *json, const char *key) if(!json_is_object(json)) return NULL; - return hashtable_get(object->hashtable, key); + return hashtable_get(&object->hashtable, key); } int json_object_set(json_t *json, const char *key, json_t *value) @@ -112,7 +111,7 @@ int json_object_set(json_t *json, const char *key, json_t *value) return -1; object = json_to_object(json); - return hashtable_set(object->hashtable, strdup(key), json_incref(value)); + return hashtable_set(&object->hashtable, strdup(key), json_incref(value)); } int json_object_del(json_t *json, const char *key) @@ -123,7 +122,7 @@ int json_object_del(json_t *json, const char *key) return -1; object = json_to_object(json); - return hashtable_del(object->hashtable, key); + return hashtable_del(&object->hashtable, key); } void *json_object_iter(json_t *json) @@ -134,7 +133,7 @@ void *json_object_iter(json_t *json) return NULL; object = json_to_object(json); - return hashtable_iter(object->hashtable); + return hashtable_iter(&object->hashtable); } void *json_object_iter_next(json_t *json, void *iter) @@ -145,7 +144,7 @@ void *json_object_iter_next(json_t *json, void *iter) return NULL; object = json_to_object(json); - return hashtable_iter_next(object->hashtable, iter); + return hashtable_iter_next(&object->hashtable, iter); } const char *json_object_iter_key(void *iter) -- 2.1.4