X-Git-Url: http://www.project-moonshot.org/gitweb/?a=blobdiff_plain;f=src%2Fhashtable.c;h=77d2b80f7d5394cbf2cab5299efba8f3eb6d9600;hb=bb5d4efb2ef9609bcd1163238bccd11a1df28095;hp=05dc16794a2eb7ddba7fe3fc1e9f94e76ad07e2c;hpb=2ad4634de51bd06c03d1ba5831247ed865c03506;p=jansson.git diff --git a/src/hashtable.c b/src/hashtable.c index 05dc167..77d2b80 100644 --- a/src/hashtable.c +++ b/src/hashtable.c @@ -1,29 +1,28 @@ /* - * 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 /* 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; @@ -31,13 +30,13 @@ static inline void list_insert(list_t *list, list_t *node) 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; } @@ -57,22 +56,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 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; @@ -98,11 +97,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]; @@ -154,7 +153,7 @@ 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); @@ -211,7 +210,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[] */ @@ -245,40 +244,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); - 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); @@ -293,13 +300,13 @@ 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) { - unsigned int i; + size_t i; hashtable_do_clear(hashtable); @@ -318,6 +325,22 @@ 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; @@ -337,3 +360,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; +}