5 #include "yacjs_dict.h"
7 struct YACJS_NAME(dict_entry) {
13 struct YACJS_NAME(dict) {
14 struct YACJS_NAME(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_NAME(dict) *dict, int newsize);
22 static void insert_helper(struct YACJS_NAME(dict) *dict, uint64_t hash,
23 const char *key, void *value);
25 struct YACJS_NAME(dict) *YACJS_NAME(dict_make)() {
26 struct YACJS_NAME(dict) *result = malloc(sizeof(*result));
28 result->entries = NULL;
29 result->entries_size = 0;
30 result->entries_count = 0;
35 void YACJS_NAME(dict_destroy)(struct YACJS_NAME(dict) *dict,
36 YACJS_NAME(dict_visitor) visitor) {
39 for(int i = 0; i < dict->entries_size; i ++) {
40 if(dict->entries[i].key) {
41 visitor(dict->entries[i].value);
42 free(dict->entries[i].key);
50 void YACJS_NAME(dict_set)(struct YACJS_NAME(dict) *dict, const char *key,
53 if(dict->entries_size == dict->entries_count) {
54 resize(dict, dict->entries_size*2 + 1);
57 uint64_t hash = string_hash(key);
58 insert_helper(dict, hash, ystrdup(key), value);
61 void *YACJS_NAME(dict_get)(struct YACJS_NAME(dict) *dict, const char *key) {
62 uint64_t hash = string_hash(key);
63 for(int i = 0; i < dict->entries_size; i ++) {
64 int in = (i+hash) % dict->entries_size;
65 if(!dict->entries[in].key) return NULL;
66 if(dict->entries[in].key_hash == hash) return dict->entries[in].value;
71 static char *ystrdup(const char *string) {
72 return strcpy(malloc(strlen(string)+1), string);
75 static uint64_t string_hash(const char *string) {
76 uint64_t result = 14695981039346656037ULL;
80 result *= 1099511628211ULL;
87 static void resize(struct YACJS_NAME(dict) *dict, int newsize) {
88 struct YACJS_NAME(dict_entry) *oentries = dict->entries;
89 int osize = dict->entries_size;
90 dict->entries_size = newsize;
91 dict->entries_count = 0;
92 dict->entries = calloc(newsize, sizeof(oentries[0]));
94 for(int i = 0; i < osize; i ++) {
95 if(!oentries[i].key) continue;
96 insert_helper(dict, oentries[i].key_hash, oentries[i].key,
101 static void insert_helper(struct YACJS_NAME(dict) *dict, uint64_t hash,
102 const char *key, void *value) {
103 for(int i = 0; i < dict->entries_size; i ++) {
104 int in = (i+hash) % dict->entries_size;
105 if(dict->entries[in].key) continue;
106 dict->entries[in].key = ystrdup(key);
107 dict->entries[in].key_hash = hash;
108 dict->entries[in].value = value;
111 dict->entries_count ++;