/*
- * Copyright (c) 2009 Petri Lehtinen <petri@digip.org>
+ * Copyright (c) 2009
, 2010 Petri Lehtinen <petri@digip.org>
*
* This library is free software; you can redistribute it and/or modify
* it under the terms of the MIT license. See LICENSE for details.
*/
+#include <config.h>
+
#include <stdlib.h>
#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;
return 0;
}
+static void hashtable_do_clear(hashtable_t *hashtable)
+{
+ list_t *list, *next;
+ pair_t *pair;
+
+ for(list = hashtable->list.next; list != &hashtable->list; list = next)
+ {
+ 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);
+ free(pair);
+ }
+}
+
static int hashtable_do_rehash(hashtable_t *hashtable)
{
list_t *list, *next;
}
-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;
&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;
- for(list = hashtable->list.next; list != &hashtable->list; list = next)
- {
- 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);
- free(pair);
- }
-
+ hashtable_do_clear(hashtable);
free(hashtable->buckets);
- free(hashtable);
}
int hashtable_set(hashtable_t *hashtable, void *key, void *value)
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);
-
/* 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;
-
+ hash = hashtable->hash_key(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);
+ 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);
- list_init(&pair->list);
- insert_to_bucket(hashtable, bucket, &pair->list);
+ insert_to_bucket(hashtable, bucket, &pair->list);
- hashtable->size++;
+ hashtable->size++;
+ }
return 0;
}
return hashtable_do_del(hashtable, key, hash);
}
+void hashtable_clear(hashtable_t *hashtable)
+{
+ unsigned int i;
+
+ hashtable_do_clear(hashtable);
+
+ for(i = 0; i < num_buckets(hashtable); i++)
+ {
+ hashtable->buckets[i].first = hashtable->buckets[i].last =
+ &hashtable->list;
+ }
+
+ list_init(&hashtable->list);
+ hashtable->size = 0;
+}
+
void *hashtable_iter(hashtable_t *hashtable)
{
return hashtable_iter_next(hashtable, &hashtable->list);
}
+void *hashtable_iter_at(hashtable_t *hashtable, const void *key)
+{
+ pair_t *pair;
+ unsigned int hash;
+ bucket_t *bucket;
+
+ hash = hashtable->hash_key(key);
+ bucket = &hashtable->buckets[hash % num_buckets(hashtable)];
+
+ pair = hashtable_find_pair(hashtable, bucket, key, hash);
+ if(!pair)
+ return NULL;
+
+ return &pair->list;
+}
+
void *hashtable_iter_next(hashtable_t *hashtable, void *iter)
{
list_t *list = (list_t *)iter;
pair_t *pair = list_to_pair((list_t *)iter);
return pair->value;
}
+
+void hashtable_iter_set(hashtable_t *hashtable, void *iter, void *value)
+{
+ pair_t *pair = list_to_pair((list_t *)iter);
+
+ if(hashtable->free_value)
+ hashtable->free_value(pair->value);
+
+ pair->value = value;
+}
projects / jansson.git / blobdiff