X-Git-Url: http://www.project-moonshot.org/gitweb/?a=blobdiff_plain;f=src%2Fhashtable.c;h=dcba68aab7592327e1b7b571cd220552b48d7ff9;hb=b76c69de1b26b589551879d80ae582a5a3506cc0;hp=afb330432b4f33e1f60cf2bb2b3cb7b4b807bea6;hpb=61d0111323c7df3326d57856c7120c1af807a062;p=jansson.git diff --git a/src/hashtable.c b/src/hashtable.c index afb3304..dcba68a 100644 --- a/src/hashtable.c +++ b/src/hashtable.c @@ -1,10 +1,12 @@ /* - * Copyright (c) 2009 Petri Lehtinen + * Copyright (c) 2009, 2010 Petri Lehtinen * * 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 + #include #include "hashtable.h" @@ -57,22 +59,22 @@ static void insert_to_bucket(hashtable_t *hashtable, bucket_t *bucket, } } -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 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; @@ -98,11 +100,11 @@ 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, 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]; @@ -133,11 +135,28 @@ static int hashtable_do_del(hashtable_t *hashtable, 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; pair_t *pair; - unsigned int i, index, new_size; + size_t i, index, new_size; free(hashtable->buckets); @@ -194,7 +213,7 @@ 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; + size_t i; hashtable->size = 0; hashtable->num_buckets = 0; /* index to primes[] */ @@ -220,19 +239,7 @@ int hashtable_init(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); } @@ -240,40 +247,48 @@ 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); + 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); + + 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; - insert_to_bucket(hashtable, bucket, &pair->list); + 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); @@ -288,15 +303,47 @@ void *hashtable_get(hashtable_t *hashtable, const void *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) +{ + size_t 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; + size_t 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; @@ -316,3 +363,13 @@ 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) +{ + pair_t *pair = list_to_pair((list_t *)iter); + + if(hashtable->free_value) + hashtable->free_value(pair->value); + + pair->value = value; +}