diff options
author | Vsevolod Stakhov <vsevolod@rambler-co.ru> | 2009-09-07 20:11:48 +0400 |
---|---|---|
committer | Vsevolod Stakhov <vsevolod@rambler-co.ru> | 2009-09-07 20:11:48 +0400 |
commit | 9af09b7467a4b9b7b2c9fbf1390b481e71bb07c6 (patch) | |
tree | 79c72ede24341ad6f47b63df0521ba3ff6591d65 /src/json/hashtable.c | |
parent | d1b63d4cff12936a5ea4380bccadcc77b7c3ed3f (diff) | |
download | rspamd-9af09b7467a4b9b7b2c9fbf1390b481e71bb07c6.tar.gz rspamd-9af09b7467a4b9b7b2c9fbf1390b481e71bb07c6.zip |
* Add JSON settings parser
Diffstat (limited to 'src/json/hashtable.c')
-rw-r--r-- | src/json/hashtable.c | 330 |
1 files changed, 330 insertions, 0 deletions
diff --git a/src/json/hashtable.c b/src/json/hashtable.c new file mode 100644 index 000000000..b3ea0d62a --- /dev/null +++ b/src/json/hashtable.c @@ -0,0 +1,330 @@ +/* + * Copyright (c) 2009 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 "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) +{ + list->next = list; + list->prev = list; +} + +static inline void +list_insert (list_t * list, list_t * node) +{ + node->next = list; + node->prev = list->prev; + list->prev->next = node; + list->prev = node; +} + +static 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) +{ + return bucket->first == &hashtable->list && bucket->first == bucket->last; +} + +static void +insert_to_bucket (hashtable_t * hashtable, bucket_t * bucket, list_t * list) +{ + if (bucket_is_empty (hashtable, bucket)) { + list_insert (&hashtable->list, list); + bucket->first = bucket->last = list; + } + else { + list_insert (bucket->first, list); + bucket->first = list; + } +} + +static unsigned int 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 inline unsigned int +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) +{ + list_t *list; + pair_t *pair; + + if (bucket_is_empty (hashtable, bucket)) + return NULL; + + list = bucket->first; + while (1) { + pair = list_to_pair (list); + if (pair->hash == hash && hashtable->cmp_keys (pair->key, key)) + return pair; + + if (list == bucket->last) + break; + + list = list->next; + } + + return NULL; +} + +/* returns 0 on success, -1 if key was not found */ +static int +hashtable_do_del (hashtable_t * hashtable, const void *key, unsigned int hash) +{ + pair_t *pair; + bucket_t *bucket; + unsigned int index; + + index = hash % num_buckets (hashtable); + bucket = &hashtable->buckets[index]; + + pair = hashtable_find_pair (hashtable, bucket, key, hash); + if (!pair) + return -1; + + if (&pair->list == bucket->first && &pair->list == bucket->last) + bucket->first = bucket->last = &hashtable->list; + + else if (&pair->list == bucket->first) + bucket->first = pair->list.next; + + else if (&pair->list == bucket->last) + 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); + + g_free (pair); + hashtable->size--; + + return 0; +} + +static int +hashtable_do_rehash (hashtable_t * hashtable) +{ + list_t *list, *next; + pair_t *pair; + unsigned int i, index, new_size; + + g_free (hashtable->buckets); + + hashtable->num_buckets++; + new_size = num_buckets (hashtable); + + hashtable->buckets = g_malloc (new_size * sizeof (bucket_t)); + if (!hashtable->buckets) + return -1; + + for (i = 0; i < num_buckets (hashtable); i++) { + hashtable->buckets[i].first = hashtable->buckets[i].last = + &hashtable->list; + } + + list = hashtable->list.next; + list_init (&hashtable->list); + + for (; list != &hashtable->list; list = next) { + next = list->next; + pair = list_to_pair (list); + index = pair->hash % new_size; + insert_to_bucket (hashtable, &hashtable->buckets[index], &pair->list); + } + + return 0; +} + + +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 = g_malloc (sizeof (hashtable_t)); + if (!hashtable) + return NULL; + + if (hashtable_init (hashtable, hash_key, cmp_keys, free_key, free_value)) { + g_free (hashtable); + return NULL; + } + + return hashtable; +} + +void +hashtable_destroy (hashtable_t * hashtable) +{ + hashtable_close (hashtable); + g_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 = g_malloc (num_buckets (hashtable) * sizeof (bucket_t)); + if (!hashtable->buckets) + return -1; + + 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 = + &hashtable->list; + } + + return 0; +} + +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); + g_free (pair); + } + + g_free (hashtable->buckets); +} + +int +hashtable_set (hashtable_t * hashtable, void *key, void *value) +{ + 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); + + /* rehash if the load ratio exceeds 1 */ + if (hashtable->size >= num_buckets (hashtable)) + if (hashtable_do_rehash (hashtable)) + return -1; + + pair = g_malloc (sizeof (pair_t)); + if (!pair) + return -1; + + pair->key = key; + pair->value = value; + pair->hash = hash; + list_init (&pair->list); + + index = hash % num_buckets (hashtable); + bucket = &hashtable->buckets[index]; + + 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; + 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->value; +} + +int +hashtable_del (hashtable_t * hashtable, const void *key) +{ + unsigned int hash = hashtable->hash_key (key); + return hashtable_do_del (hashtable, key, hash); +} + +void * +hashtable_iter (hashtable_t * hashtable) +{ + return hashtable_iter_next (hashtable, &hashtable->list); +} + +void * +hashtable_iter_next (hashtable_t * hashtable, void *iter) +{ + list_t *list = (list_t *) iter; + if (list->next == &hashtable->list) + return NULL; + return list->next; +} + +void * +hashtable_iter_key (void *iter) +{ + pair_t *pair = list_to_pair ((list_t *) iter); + return pair->key; +} + +void * +hashtable_iter_value (void *iter) +{ + pair_t *pair = list_to_pair ((list_t *) iter); + return pair->value; +} |