*/
#include <stdlib.h>
+#include <jansson_config.h> /* for JSON_INLINE */
+#include "jansson_private.h" /* for container_of() */
#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_))
-
#define list_to_pair(list_) container_of(list_, pair_t, list)
-static inline void list_init(list_t *list)
+static JSON_INLINE void list_init(list_t *list)
{
list->next = list;
list->prev = list;
}
-static inline void list_insert(list_t *list, list_t *node)
+static JSON_INLINE void list_insert(list_t *list, list_t *node)
{
node->next = list;
node->prev = list->prev;
list->prev = node;
}
-static inline void list_remove(list_t *list)
+static JSON_INLINE void list_remove(list_t *list)
{
list->prev->next = list->next;
list->next->prev = list->prev;
}
-static inline int bucket_is_empty(hashtable_t *hashtable, bucket_t *bucket)
+static JSON_INLINE int bucket_is_empty(hashtable_t *hashtable, bucket_t *bucket)
{
return bucket->first == &hashtable->list && bucket->first == bucket->last;
}
}
}
-static unsigned int primes[] = {
+static size_t primes[] = {
5, 13, 23, 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469,
12582917, 25165843, 50331653, 100663319, 201326611, 402653189,
805306457, 1610612741
};
-static const unsigned int num_primes = sizeof(primes) / sizeof(unsigned int);
+static const size_t num_primes = sizeof(primes) / sizeof(size_t);
-static inline unsigned int num_buckets(hashtable_t *hashtable)
+static JSON_INLINE size_t num_buckets(hashtable_t *hashtable)
{
return primes[hashtable->num_buckets];
}
static pair_t *hashtable_find_pair(hashtable_t *hashtable, bucket_t *bucket,
- const void *key, unsigned int hash)
+ const void *key, size_t hash)
{
list_t *list;
pair_t *pair;
/* returns 0 on success, -1 if key was not found */
static int hashtable_do_del(hashtable_t *hashtable,
- const void *key, unsigned int hash)
+ const void *key, size_t hash)
{
pair_t *pair;
bucket_t *bucket;
- unsigned int index;
+ size_t index;
index = hash % num_buckets(hashtable);
bucket = &hashtable->buckets[index];
{
list_t *list, *next;
pair_t *pair;
- unsigned int i, index, new_size;
+ size_t i, index, new_size;
free(hashtable->buckets);
key_hash_fn hash_key, key_cmp_fn cmp_keys,
free_fn free_key, free_fn free_value)
{
- unsigned int i;
+ size_t i;
hashtable->size = 0;
hashtable->num_buckets = 0; /* index to primes[] */
{
pair_t *pair;
bucket_t *bucket;
- unsigned int hash, index;
-
- hash = hashtable->hash_key(key);
-
- /* if the key already exists, delete it */
- hashtable_do_del(hashtable, key, hash);
+ size_t hash, index;
/* rehash if the load ratio exceeds 1 */
if(hashtable->size >= num_buckets(hashtable))
if(hashtable_do_rehash(hashtable))
return -1;
- pair = malloc(sizeof(pair_t));
- if(!pair)
- return -1;
-
- pair->key = key;
- pair->value = value;
- pair->hash = hash;
- list_init(&pair->list);
-
+ hash = hashtable->hash_key(key);
index = hash % num_buckets(hashtable);
bucket = &hashtable->buckets[index];
+ pair = hashtable_find_pair(hashtable, bucket, key, hash);
- insert_to_bucket(hashtable, bucket, &pair->list);
+ if(pair)
+ {
+ if(hashtable->free_key)
+ hashtable->free_key(key);
+ if(hashtable->free_value)
+ hashtable->free_value(pair->value);
+ pair->value = value;
+ }
+ else
+ {
+ pair = malloc(sizeof(pair_t));
+ if(!pair)
+ return -1;
+
+ pair->key = key;
+ pair->value = value;
+ pair->hash = hash;
+ list_init(&pair->list);
- hashtable->size++;
+ insert_to_bucket(hashtable, bucket, &pair->list);
+
+ hashtable->size++;
+ }
return 0;
}
void *hashtable_get(hashtable_t *hashtable, const void *key)
{
pair_t *pair;
- unsigned int hash;
+ size_t hash;
bucket_t *bucket;
hash = hashtable->hash_key(key);
int hashtable_del(hashtable_t *hashtable, const void *key)
{
- unsigned int hash = hashtable->hash_key(key);
+ size_t hash = hashtable->hash_key(key);
return hashtable_do_del(hashtable, key, hash);
}
void hashtable_clear(hashtable_t *hashtable)
{
- unsigned int i;
+ size_t i;
hashtable_do_clear(hashtable);
void *hashtable_iter_at(hashtable_t *hashtable, const void *key)
{
pair_t *pair;
- unsigned int hash;
+ size_t hash;
bucket_t *bucket;
hash = hashtable->hash_key(key);