From a2381948bb7871aee7c55c6918953bfbdf9c3eb1 Mon Sep 17 00:00:00 2001 From: Petri Lehtinen Date: Tue, 24 Jan 2012 20:36:31 +0200 Subject: [PATCH] Make hashtable less generic This will make it possible to implement json_object_foreach(). It should also have some (positive) effect on speed. --- src/dump.c | 27 +++++---- src/hashtable.c | 111 ++++++++++++++++-------------------- src/hashtable.h | 77 ++++++++----------------- src/jansson_private.h | 10 ---- src/pack_unpack.c | 4 +- src/value.c | 86 +++------------------------- test/suites/api/test_memory_funcs.c | 2 +- 7 files changed, 98 insertions(+), 219 deletions(-) diff --git a/src/dump.c b/src/dump.c index 37f5a40..aec535b 100644 --- a/src/dump.c +++ b/src/dump.c @@ -19,11 +19,9 @@ #define MAX_INTEGER_STR_LENGTH 100 #define MAX_REAL_STR_LENGTH 100 -struct string -{ - char *buffer; - int length; - int size; +struct object_key { + size_t serial; + const char *key; }; static int dump_to_strbuffer(const char *buffer, size_t size, void *data) @@ -153,14 +151,14 @@ static int dump_string(const char *str, int ascii, json_dump_callback_t dump, vo static int object_key_compare_keys(const void *key1, const void *key2) { - return strcmp((*(const object_key_t **)key1)->key, - (*(const object_key_t **)key2)->key); + return strcmp(((const struct object_key *)key1)->key, + ((const struct object_key *)key2)->key); } static int object_key_compare_serials(const void *key1, const void *key2) { - size_t a = (*(const object_key_t **)key1)->serial; - size_t b = (*(const object_key_t **)key2)->serial; + size_t a = ((const struct object_key *)key1)->serial; + size_t b = ((const struct object_key *)key2)->serial; return a < b ? -1 : a == b ? 0 : 1; } @@ -294,19 +292,20 @@ static int do_dump(const json_t *json, size_t flags, int depth, if(flags & JSON_SORT_KEYS || flags & JSON_PRESERVE_ORDER) { - const object_key_t **keys; + struct object_key *keys; size_t size, i; int (*cmp_func)(const void *, const void *); size = json_object_size(json); - keys = jsonp_malloc(size * sizeof(object_key_t *)); + keys = jsonp_malloc(size * sizeof(struct object_key)); if(!keys) goto object_error; i = 0; while(iter) { - keys[i] = jsonp_object_iter_fullkey(iter); + keys[i].serial = hashtable_iter_serial(iter); + keys[i].key = json_object_iter_key(iter); iter = json_object_iter_next((json_t *)json, iter); i++; } @@ -317,14 +316,14 @@ static int do_dump(const json_t *json, size_t flags, int depth, else cmp_func = object_key_compare_serials; - qsort(keys, size, sizeof(object_key_t *), cmp_func); + qsort(keys, size, sizeof(struct object_key), cmp_func); for(i = 0; i < size; i++) { const char *key; json_t *value; - key = keys[i]->key; + key = keys[i].key; value = json_object_get(json, key); assert(value); diff --git a/src/hashtable.c b/src/hashtable.c index 1b0cd6c..f1f1f1e 100644 --- a/src/hashtable.c +++ b/src/hashtable.c @@ -6,6 +6,7 @@ */ #include +#include #include /* for JSON_INLINE */ #include "jansson_private.h" /* for container_of() */ #include "hashtable.h" @@ -16,6 +17,23 @@ typedef struct hashtable_bucket bucket_t; #define list_to_pair(list_) container_of(list_, pair_t, list) +/* From http://www.cse.yorku.ca/~oz/hash.html */ +static size_t hash_str(const void *ptr) +{ + const char *str = (const char *)ptr; + + size_t hash = 5381; + size_t c; + + while((c = (size_t)*str)) + { + hash = ((hash << 5) + hash) + c; + str++; + } + + return hash; +} + static JSON_INLINE void list_init(list_t *list) { list->next = list; @@ -70,7 +88,7 @@ static JSON_INLINE size_t num_buckets(hashtable_t *hashtable) static pair_t *hashtable_find_pair(hashtable_t *hashtable, bucket_t *bucket, - const void *key, size_t hash) + const char *key, size_t hash) { list_t *list; pair_t *pair; @@ -82,7 +100,7 @@ static pair_t *hashtable_find_pair(hashtable_t *hashtable, bucket_t *bucket, while(1) { pair = list_to_pair(list); - if(pair->hash == hash && hashtable->cmp_keys(pair->key, key)) + if(pair->hash == hash && strcmp(pair->key, key) == 0) return pair; if(list == bucket->last) @@ -96,7 +114,7 @@ static pair_t *hashtable_find_pair(hashtable_t *hashtable, bucket_t *bucket, /* returns 0 on success, -1 if key was not found */ static int hashtable_do_del(hashtable_t *hashtable, - const void *key, size_t hash) + const char *key, size_t hash) { pair_t *pair; bucket_t *bucket; @@ -119,11 +137,7 @@ static int hashtable_do_del(hashtable_t *hashtable, bucket->last = pair->list.prev; list_remove(&pair->list); - - if(hashtable->free_key) - hashtable->free_key(pair->key); - if(hashtable->free_value) - hashtable->free_value(pair->value); + json_decref(pair->value); jsonp_free(pair); hashtable->size--; @@ -140,10 +154,7 @@ static void hashtable_do_clear(hashtable_t *hashtable) { next = list->next; pair = list_to_pair(list); - if(hashtable->free_key) - hashtable->free_key(pair->key); - if(hashtable->free_value) - hashtable->free_value(pair->value); + json_decref(pair->value); jsonp_free(pair); } } @@ -183,31 +194,7 @@ static int hashtable_do_rehash(hashtable_t *hashtable) } -hashtable_t *hashtable_create(key_hash_fn hash_key, key_cmp_fn cmp_keys, - free_fn free_key, free_fn free_value) -{ - hashtable_t *hashtable = jsonp_malloc(sizeof(hashtable_t)); - if(!hashtable) - return NULL; - - if(hashtable_init(hashtable, hash_key, cmp_keys, free_key, free_value)) - { - jsonp_free(hashtable); - return NULL; - } - - return hashtable; -} - -void hashtable_destroy(hashtable_t *hashtable) -{ - hashtable_close(hashtable); - jsonp_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) +int hashtable_init(hashtable_t *hashtable) { size_t i; @@ -219,11 +206,6 @@ int hashtable_init(hashtable_t *hashtable, list_init(&hashtable->list); - hashtable->hash_key = hash_key; - hashtable->cmp_keys = cmp_keys; - hashtable->free_key = free_key; - hashtable->free_value = free_value; - for(i = 0; i < num_buckets(hashtable); i++) { hashtable->buckets[i].first = hashtable->buckets[i].last = @@ -239,7 +221,9 @@ void hashtable_close(hashtable_t *hashtable) jsonp_free(hashtable->buckets); } -int hashtable_set(hashtable_t *hashtable, void *key, void *value) +int hashtable_set(hashtable_t *hashtable, + const char *key, size_t serial, + json_t *value) { pair_t *pair; bucket_t *bucket; @@ -250,28 +234,29 @@ int hashtable_set(hashtable_t *hashtable, void *key, void *value) if(hashtable_do_rehash(hashtable)) return -1; - hash = hashtable->hash_key(key); + hash = hash_str(key); index = hash % num_buckets(hashtable); bucket = &hashtable->buckets[index]; pair = hashtable_find_pair(hashtable, bucket, key, hash); if(pair) { - if(hashtable->free_key) - hashtable->free_key(key); - if(hashtable->free_value) - hashtable->free_value(pair->value); + json_decref(pair->value); pair->value = value; } else { - pair = jsonp_malloc(sizeof(pair_t)); + /* offsetof(...) returns the size of pair_t without the last, + flexible member. This way, the correct amount is + allocated. */ + pair = jsonp_malloc(offsetof(pair_t, key) + strlen(key) + 1); if(!pair) return -1; - pair->key = key; - pair->value = value; pair->hash = hash; + pair->serial = serial; + strcpy(pair->key, key); + pair->value = value; list_init(&pair->list); insert_to_bucket(hashtable, bucket, &pair->list); @@ -281,13 +266,13 @@ int hashtable_set(hashtable_t *hashtable, void *key, void *value) return 0; } -void *hashtable_get(hashtable_t *hashtable, const void *key) +void *hashtable_get(hashtable_t *hashtable, const char *key) { pair_t *pair; size_t hash; bucket_t *bucket; - hash = hashtable->hash_key(key); + hash = hash_str(key); bucket = &hashtable->buckets[hash % num_buckets(hashtable)]; pair = hashtable_find_pair(hashtable, bucket, key, hash); @@ -297,9 +282,9 @@ void *hashtable_get(hashtable_t *hashtable, const void *key) return pair->value; } -int hashtable_del(hashtable_t *hashtable, const void *key) +int hashtable_del(hashtable_t *hashtable, const char *key) { - size_t hash = hashtable->hash_key(key); + size_t hash = hash_str(key); return hashtable_do_del(hashtable, key, hash); } @@ -324,13 +309,13 @@ void *hashtable_iter(hashtable_t *hashtable) return hashtable_iter_next(hashtable, &hashtable->list); } -void *hashtable_iter_at(hashtable_t *hashtable, const void *key) +void *hashtable_iter_at(hashtable_t *hashtable, const char *key) { pair_t *pair; size_t hash; bucket_t *bucket; - hash = hashtable->hash_key(key); + hash = hash_str(key); bucket = &hashtable->buckets[hash % num_buckets(hashtable)]; pair = hashtable_find_pair(hashtable, bucket, key, hash); @@ -354,18 +339,22 @@ void *hashtable_iter_key(void *iter) return pair->key; } +size_t hashtable_iter_serial(void *iter) +{ + pair_t *pair = list_to_pair((list_t *)iter); + return pair->serial; +} + void *hashtable_iter_value(void *iter) { pair_t *pair = list_to_pair((list_t *)iter); return pair->value; } -void hashtable_iter_set(hashtable_t *hashtable, void *iter, void *value) +void hashtable_iter_set(void *iter, json_t *value) { pair_t *pair = list_to_pair((list_t *)iter); - if(hashtable->free_value) - hashtable->free_value(pair->value); - + json_decref(pair->value); pair->value = value; } diff --git a/src/hashtable.h b/src/hashtable.h index 5aed14f..e8d5ccb 100644 --- a/src/hashtable.h +++ b/src/hashtable.h @@ -17,11 +17,15 @@ struct hashtable_list { struct hashtable_list *next; }; +/* "pair" may be a bit confusing a name, but think of it as a + key-value pair. In this case, it just encodes some extra data, + too */ struct hashtable_pair { - void *key; - void *value; size_t hash; struct hashtable_list list; + json_t *value; + size_t serial; + char key[1]; }; struct hashtable_bucket { @@ -34,56 +38,19 @@ typedef struct hashtable { struct hashtable_bucket *buckets; size_t 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_create - Create a 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. - * - * Returns a new hashtable object that should be freed with - * 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(). - */ -void hashtable_destroy(hashtable_t *hashtable); - -/** * 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); +int hashtable_init(hashtable_t *hashtable); /** * hashtable_close - Release all resources used by a hashtable object @@ -99,20 +66,19 @@ void hashtable_close(hashtable_t *hashtable); * * @hashtable: The hashtable object * @key: The key + * @serial: For addition order of keys * @value: The value * * If a value with the given key already exists, its value is replaced - * with the new value. - * - * Key and value are "stealed" in the sense that hashtable frees them - * automatically when they are no longer used. The freeing is - * accomplished by calling free_key and free_value functions that were - * supplied to hashtable_new. In case one or both of the free - * functions is NULL, the corresponding item is not "stealed". + * with the new value. Value is "stealed" in the sense that hashtable + * doesn't increment its refcount but decreases the refcount when the + * value is no longer needed. * * Returns 0 on success, -1 on failure (out of memory). */ -int hashtable_set(hashtable_t *hashtable, void *key, void *value); +int hashtable_set(hashtable_t *hashtable, + const char *key, size_t serial, + json_t *value); /** * hashtable_get - Get a value associated with a key @@ -122,7 +88,7 @@ int hashtable_set(hashtable_t *hashtable, void *key, void *value); * * Returns value if it is found, or NULL otherwise. */ -void *hashtable_get(hashtable_t *hashtable, const void *key); +void *hashtable_get(hashtable_t *hashtable, const char *key); /** * hashtable_del - Remove a value from the hashtable @@ -132,7 +98,7 @@ void *hashtable_get(hashtable_t *hashtable, const void *key); * * Returns 0 on success, or -1 if the key was not found. */ -int hashtable_del(hashtable_t *hashtable, const void *key); +int hashtable_del(hashtable_t *hashtable, const char *key); /** * hashtable_clear - Clear hashtable @@ -169,7 +135,7 @@ void *hashtable_iter(hashtable_t *hashtable); * Like hashtable_iter() but returns an iterator pointing to a * specific key. */ -void *hashtable_iter_at(hashtable_t *hashtable, const void *key); +void *hashtable_iter_at(hashtable_t *hashtable, const char *key); /** * hashtable_iter_next - Advance an iterator @@ -190,6 +156,13 @@ void *hashtable_iter_next(hashtable_t *hashtable, void *iter); void *hashtable_iter_key(void *iter); /** + * hashtable_iter_serial - Retrieve the serial number pointed to by an iterator + * + * @iter: The iterator + */ +size_t hashtable_iter_serial(void *iter); + +/** * hashtable_iter_value - Retrieve the value pointed by an iterator * * @iter: The iterator @@ -202,6 +175,6 @@ void *hashtable_iter_value(void *iter); * @iter: The iterator * @value: The value to set */ -void hashtable_iter_set(hashtable_t *hashtable, void *iter, void *value); +void hashtable_iter_set(void *iter, json_t *value); #endif diff --git a/src/jansson_private.h b/src/jansson_private.h index dbe9760..c851540 100644 --- a/src/jansson_private.h +++ b/src/jansson_private.h @@ -67,16 +67,6 @@ typedef struct { #define json_to_real(json_) container_of(json_, json_real_t, json) #define json_to_integer(json_) container_of(json_, json_integer_t, json) -size_t jsonp_hash_str(const void *ptr); -int jsonp_str_equal(const void *ptr1, const void *ptr2); - -typedef struct { - size_t serial; - char key[1]; -} object_key_t; - -const object_key_t *jsonp_object_iter_fullkey(void *iter); - void jsonp_error_init(json_error_t *error, const char *source); void jsonp_error_set_source(json_error_t *error, const char *source); void jsonp_error_set(json_error_t *error, int line, int column, diff --git a/src/pack_unpack.c b/src/pack_unpack.c index 20d540b..981a216 100644 --- a/src/pack_unpack.c +++ b/src/pack_unpack.c @@ -233,7 +233,7 @@ static int unpack_object(scanner_t *s, json_t *root, va_list *ap) */ hashtable_t key_set; - if(hashtable_init(&key_set, jsonp_hash_str, jsonp_str_equal, NULL, NULL)) { + if(hashtable_init(&key_set)) { set_error(s, "", "Out of memory"); return -1; } @@ -288,7 +288,7 @@ static int unpack_object(scanner_t *s, json_t *root, va_list *ap) if(unpack(s, value, ap)) goto out; - hashtable_set(&key_set, (void *)key, NULL); + hashtable_set(&key_set, key, 0, json_null()); next_token(s); } diff --git a/src/value.c b/src/value.c index e0e21cb..c728427 100644 --- a/src/value.c +++ b/src/value.c @@ -26,50 +26,6 @@ static JSON_INLINE void json_init(json_t *json, json_type type) /*** object ***/ -/* From http://www.cse.yorku.ca/~oz/hash.html */ -size_t jsonp_hash_str(const void *ptr) -{ - const char *str = (const char *)ptr; - - size_t hash = 5381; - size_t c; - - while((c = (size_t)*str)) - { - hash = ((hash << 5) + hash) + c; - str++; - } - - return hash; -} - -int jsonp_str_equal(const void *ptr1, const void *ptr2) -{ - return strcmp((const char *)ptr1, (const char *)ptr2) == 0; -} - -/* This macro just returns a pointer that's a few bytes backwards from - string. This makes it possible to pass a pointer to object_key_t - when only the string inside it is used, without actually creating - an object_key_t instance. */ -#define string_to_key(string) container_of(string, object_key_t, key) - -static size_t hash_key(const void *ptr) -{ - return jsonp_hash_str(((const object_key_t *)ptr)->key); -} - -static int key_equal(const void *ptr1, const void *ptr2) -{ - return jsonp_str_equal(((const object_key_t *)ptr1)->key, - ((const object_key_t *)ptr2)->key); -} - -static void value_decref(void *value) -{ - json_decref((json_t *)value); -} - json_t *json_object(void) { json_object_t *object = jsonp_malloc(sizeof(json_object_t)); @@ -77,9 +33,7 @@ json_t *json_object(void) return NULL; json_init(&object->json, JSON_OBJECT); - if(hashtable_init(&object->hashtable, - hash_key, key_equal, - jsonp_free, value_decref)) + if(hashtable_init(&object->hashtable)) { jsonp_free(object); return NULL; @@ -116,13 +70,12 @@ json_t *json_object_get(const json_t *json, const char *key) return NULL; object = json_to_object(json); - return hashtable_get(&object->hashtable, string_to_key(key)); + return hashtable_get(&object->hashtable, key); } int json_object_set_new_nocheck(json_t *json, const char *key, json_t *value) { json_object_t *object; - object_key_t *k; if(!value) return -1; @@ -134,20 +87,7 @@ int json_object_set_new_nocheck(json_t *json, const char *key, json_t *value) } object = json_to_object(json); - /* offsetof(...) returns the size of object_key_t without the - last, flexible member. This way, the correct amount is - allocated. */ - k = jsonp_malloc(offsetof(object_key_t, key) + strlen(key) + 1); - if(!k) - { - json_decref(value); - return -1; - } - - k->serial = object->serial++; - strcpy(k->key, key); - - if(hashtable_set(&object->hashtable, k, value)) + if(hashtable_set(&object->hashtable, key, object->serial++, value)) { json_decref(value); return -1; @@ -175,7 +115,7 @@ int json_object_del(json_t *json, const char *key) return -1; object = json_to_object(json); - return hashtable_del(&object->hashtable, string_to_key(key)); + return hashtable_del(&object->hashtable, key); } int json_object_clear(json_t *json) @@ -236,7 +176,7 @@ void *json_object_iter_at(json_t *json, const char *key) return NULL; object = json_to_object(json); - return hashtable_iter_at(&object->hashtable, string_to_key(key)); + return hashtable_iter_at(&object->hashtable, key); } void *json_object_iter_next(json_t *json, void *iter) @@ -250,20 +190,12 @@ void *json_object_iter_next(json_t *json, void *iter) return hashtable_iter_next(&object->hashtable, iter); } -const object_key_t *jsonp_object_iter_fullkey(void *iter) -{ - if(!iter) - return NULL; - - return hashtable_iter_key(iter); -} - const char *json_object_iter_key(void *iter) { if(!iter) return NULL; - return jsonp_object_iter_fullkey(iter)->key; + return hashtable_iter_key(iter); } json_t *json_object_iter_value(void *iter) @@ -276,14 +208,10 @@ json_t *json_object_iter_value(void *iter) int json_object_iter_set_new(json_t *json, void *iter, json_t *value) { - json_object_t *object; - if(!json_is_object(json) || !iter || !value) return -1; - object = json_to_object(json); - hashtable_iter_set(&object->hashtable, iter, value); - + hashtable_iter_set(iter, value); return 0; } diff --git a/test/suites/api/test_memory_funcs.c b/test/suites/api/test_memory_funcs.c index abecac6..ed18ded 100644 --- a/test/suites/api/test_memory_funcs.c +++ b/test/suites/api/test_memory_funcs.c @@ -39,7 +39,7 @@ static void test_simple() json_set_alloc_funcs(my_malloc, my_free); create_and_free_complex_object(); - if(malloc_called != 27 || free_called != 27) + if(malloc_called != 20 || free_called != 20) fail("Custom allocation failed"); } -- 2.1.4