#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)
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;
}
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++;
}
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);
*/
#include <stdlib.h>
+#include <string.h>
#include <jansson_config.h> /* for JSON_INLINE */
#include "jansson_private.h" /* for container_of() */
#include "hashtable.h"
#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;
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;
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)
/* 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;
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--;
{
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);
}
}
}
-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;
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 =
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;
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);
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);
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);
}
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);
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;
}
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 {
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
*
* @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
*
* 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
*
* 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
* 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
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
* @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
#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,
*/
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, "<internal>", "Out of memory");
return -1;
}
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);
}
/*** 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));
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;
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;
}
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;
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)
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)
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)
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;
}
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");
}