5 #include "yacjs_dict.h"
7 struct yacjs_dict_entry {
14 struct yacjs_dict_entry *entries;
19 static char *ystrdup(const char *string);
20 static uint64_t string_hash(const char *string);
21 static void resize(struct yacjs_dict *dict, int newsize);
22 static void insert_helper(struct yacjs_dict *dict, uint64_t hash,
23 const char *key, void *value);
25 struct yacjs_dict *yacjs_dict_make() {
26 struct yacjs_dict *result = malloc(sizeof(*result));
28 result->entries = NULL;
29 result->entries_size = 0;
30 result->entries_count = 0;
35 void yacjs_dict_destroy(struct yacjs_dict *dict, yacjs_dict_visitor visitor) {
37 for(int i = 0; i < dict->entries_size; i ++) {
38 if(dict->entries[i].key) {
39 visitor(dict->entries[i].value);
40 free(dict->entries[i].key);
48 void yacjs_dict_set(struct yacjs_dict *dict, const char *key,
51 if(dict->entries_size == dict->entries_count) {
52 resize(dict, dict->entries_size*2 + 1);
55 uint64_t hash = string_hash(key);
56 insert_helper(dict, hash, ystrdup(key), value);
59 void *yacjs_dict_get(struct yacjs_dict *dict, const char *key) {
60 uint64_t hash = string_hash(key);
61 for(int i = 0; i < dict->entries_size; i ++) {
62 int in = (i+hash) % dict->entries_size;
63 if(!dict->entries[in].key) return NULL;
64 if(dict->entries[in].key_hash == hash) return dict->entries[in].value;
69 static char *ystrdup(const char *string) {
70 return strcpy(malloc(strlen(string)+1), string);
73 static uint64_t string_hash(const char *string) {
74 uint64_t result = 14695981039346656037ULL;
78 result *= 1099511628211ULL;
85 static void resize(struct yacjs_dict *dict, int newsize) {
86 struct yacjs_dict_entry *oentries = dict->entries;
87 int osize = dict->entries_size;
88 dict->entries_size = newsize;
89 dict->entries_count = 0;
90 dict->entries = calloc(newsize, sizeof(oentries[0]));
92 for(int i = 0; i < osize; i ++) {
93 if(!oentries[i].key) continue;
94 insert_helper(dict, oentries[i].key_hash, oentries[i].key,
99 static void insert_helper(struct yacjs_dict *dict, uint64_t hash,
100 const char *key, void *value) {
101 for(int i = 0; i < dict->entries_size; i ++) {
102 int in = (i+hash) % dict->entries_size;
103 if(dict->entries[in].key) continue;
104 dict->entries[in].key = ystrdup(key);
105 dict->entries[in].key_hash = hash;
106 dict->entries[in].value = value;
109 dict->entries_count ++;