Path: blob/master/compat/jansson/hashtable.c
1298 views
/*1* Copyright (c) 2009-2013 Petri Lehtinen <[email protected]>2*3* This library is free software; you can redistribute it and/or modify4* it under the terms of the MIT license. See LICENSE for details.5*/67#include <stdlib.h>8#include <string.h>9#include <jansson_config.h> /* for JSON_INLINE */10#include "jansson_private.h" /* for container_of() */11#include "hashtable.h"1213typedef struct hashtable_list list_t;14typedef struct hashtable_pair pair_t;15typedef struct hashtable_bucket bucket_t;1617#define list_to_pair(list_) container_of(list_, pair_t, list)1819/* From http://www.cse.yorku.ca/~oz/hash.html */20static size_t hash_str(const void *ptr)21{22const char *str = (const char *)ptr;2324size_t hash = 5381;25size_t c;2627while((c = (size_t)*str))28{29hash = ((hash << 5) + hash) + c;30str++;31}3233return hash;34}3536static JSON_INLINE void list_init(list_t *list)37{38list->next = list;39list->prev = list;40}4142static JSON_INLINE void list_insert(list_t *list, list_t *node)43{44node->next = list;45node->prev = list->prev;46list->prev->next = node;47list->prev = node;48}4950static JSON_INLINE void list_remove(list_t *list)51{52list->prev->next = list->next;53list->next->prev = list->prev;54}5556static JSON_INLINE int bucket_is_empty(hashtable_t *hashtable, bucket_t *bucket)57{58return bucket->first == &hashtable->list && bucket->first == bucket->last;59}6061static void insert_to_bucket(hashtable_t *hashtable, bucket_t *bucket,62list_t *list)63{64if(bucket_is_empty(hashtable, bucket))65{66list_insert(&hashtable->list, list);67bucket->first = bucket->last = list;68}69else70{71list_insert(bucket->first, list);72bucket->first = list;73}74}7576static const size_t primes[] = {775, 13, 23, 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,7849157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469,7912582917, 25165843, 50331653, 100663319, 201326611, 402653189,80805306457, 161061274181};8283static JSON_INLINE size_t num_buckets(hashtable_t *hashtable)84{85return primes[hashtable->num_buckets];86}878889static pair_t *hashtable_find_pair(hashtable_t *hashtable, bucket_t *bucket,90const char *key, size_t hash)91{92list_t *list;93pair_t *pair;9495if(bucket_is_empty(hashtable, bucket))96return NULL;9798list = bucket->first;99while(1)100{101pair = list_to_pair(list);102if(pair->hash == hash && strcmp(pair->key, key) == 0)103return pair;104105if(list == bucket->last)106break;107108list = list->next;109}110111return NULL;112}113114/* returns 0 on success, -1 if key was not found */115static int hashtable_do_del(hashtable_t *hashtable,116const char *key, size_t hash)117{118pair_t *pair;119bucket_t *bucket;120size_t index;121122index = hash % num_buckets(hashtable);123bucket = &hashtable->buckets[index];124125pair = hashtable_find_pair(hashtable, bucket, key, hash);126if(!pair)127return -1;128129if(&pair->list == bucket->first && &pair->list == bucket->last)130bucket->first = bucket->last = &hashtable->list;131132else if(&pair->list == bucket->first)133bucket->first = pair->list.next;134135else if(&pair->list == bucket->last)136bucket->last = pair->list.prev;137138list_remove(&pair->list);139json_decref(pair->value);140141jsonp_free(pair);142hashtable->size--;143144return 0;145}146147static void hashtable_do_clear(hashtable_t *hashtable)148{149list_t *list, *next;150pair_t *pair;151152for(list = hashtable->list.next; list != &hashtable->list; list = next)153{154next = list->next;155pair = list_to_pair(list);156json_decref(pair->value);157jsonp_free(pair);158}159}160161static int hashtable_do_rehash(hashtable_t *hashtable)162{163list_t *list, *next;164pair_t *pair;165size_t i, index, new_size;166167jsonp_free(hashtable->buckets);168169hashtable->num_buckets++;170new_size = num_buckets(hashtable);171172hashtable->buckets = jsonp_malloc(new_size * sizeof(bucket_t));173if(!hashtable->buckets)174return -1;175176for(i = 0; i < num_buckets(hashtable); i++)177{178hashtable->buckets[i].first = hashtable->buckets[i].last =179&hashtable->list;180}181182list = hashtable->list.next;183list_init(&hashtable->list);184185for(; list != &hashtable->list; list = next) {186next = list->next;187pair = list_to_pair(list);188index = pair->hash % new_size;189insert_to_bucket(hashtable, &hashtable->buckets[index], &pair->list);190}191192return 0;193}194195196int hashtable_init(hashtable_t *hashtable)197{198size_t i;199200hashtable->size = 0;201hashtable->num_buckets = 0; /* index to primes[] */202hashtable->buckets = jsonp_malloc(num_buckets(hashtable) * sizeof(bucket_t));203if(!hashtable->buckets)204return -1;205206list_init(&hashtable->list);207208for(i = 0; i < num_buckets(hashtable); i++)209{210hashtable->buckets[i].first = hashtable->buckets[i].last =211&hashtable->list;212}213214return 0;215}216217void hashtable_close(hashtable_t *hashtable)218{219hashtable_do_clear(hashtable);220jsonp_free(hashtable->buckets);221}222223int hashtable_set(hashtable_t *hashtable,224const char *key, size_t serial,225json_t *value)226{227pair_t *pair;228bucket_t *bucket;229size_t hash, index;230231/* rehash if the load ratio exceeds 1 */232if(hashtable->size >= num_buckets(hashtable))233if(hashtable_do_rehash(hashtable))234return -1;235236hash = hash_str(key);237index = hash % num_buckets(hashtable);238bucket = &hashtable->buckets[index];239pair = hashtable_find_pair(hashtable, bucket, key, hash);240241if(pair)242{243json_decref(pair->value);244pair->value = value;245}246else247{248/* offsetof(...) returns the size of pair_t without the last,249flexible member. This way, the correct amount is250allocated. */251pair = jsonp_malloc(offsetof(pair_t, key) + strlen(key) + 1);252if(!pair)253return -1;254255pair->hash = hash;256pair->serial = serial;257strcpy(pair->key, key);258pair->value = value;259list_init(&pair->list);260261insert_to_bucket(hashtable, bucket, &pair->list);262263hashtable->size++;264}265return 0;266}267268void *hashtable_get(hashtable_t *hashtable, const char *key)269{270pair_t *pair;271size_t hash;272bucket_t *bucket;273274hash = hash_str(key);275bucket = &hashtable->buckets[hash % num_buckets(hashtable)];276277pair = hashtable_find_pair(hashtable, bucket, key, hash);278if(!pair)279return NULL;280281return pair->value;282}283284int hashtable_del(hashtable_t *hashtable, const char *key)285{286size_t hash = hash_str(key);287return hashtable_do_del(hashtable, key, hash);288}289290void hashtable_clear(hashtable_t *hashtable)291{292size_t i;293294hashtable_do_clear(hashtable);295296for(i = 0; i < num_buckets(hashtable); i++)297{298hashtable->buckets[i].first = hashtable->buckets[i].last =299&hashtable->list;300}301302list_init(&hashtable->list);303hashtable->size = 0;304}305306void *hashtable_iter(hashtable_t *hashtable)307{308return hashtable_iter_next(hashtable, &hashtable->list);309}310311void *hashtable_iter_at(hashtable_t *hashtable, const char *key)312{313pair_t *pair;314size_t hash;315bucket_t *bucket;316317hash = hash_str(key);318bucket = &hashtable->buckets[hash % num_buckets(hashtable)];319320pair = hashtable_find_pair(hashtable, bucket, key, hash);321if(!pair)322return NULL;323324return &pair->list;325}326327void *hashtable_iter_next(hashtable_t *hashtable, void *iter)328{329list_t *list = (list_t *)iter;330if(list->next == &hashtable->list)331return NULL;332return list->next;333}334335void *hashtable_iter_key(void *iter)336{337pair_t *pair = list_to_pair((list_t *)iter);338return pair->key;339}340341size_t hashtable_iter_serial(void *iter)342{343pair_t *pair = list_to_pair((list_t *)iter);344return pair->serial;345}346347void *hashtable_iter_value(void *iter)348{349pair_t *pair = list_to_pair((list_t *)iter);350return pair->value;351}352353void hashtable_iter_set(void *iter, json_t *value)354{355pair_t *pair = list_to_pair((list_t *)iter);356357json_decref(pair->value);358pair->value = value;359}360361362