d3d87db309bb654193ec7699ad09dd115fb54024
[yacjs.git] / src / yacjs_dict.c
1 #include <stdlib.h>
2 #include <stdint.h>
3 #include <string.h>
4
5 #include "yacjs_dict.h"
6
7 struct yacjs_dict_entry {
8     char *key;
9     void *value;
10     uint64_t key_hash;
11 };
12
13 struct yacjs_dict {
14     struct yacjs_dict_entry *entries;
15     int entries_size;
16     int entries_count;
17 };
18
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);
24
25 struct yacjs_dict *yacjs_dict_make() {
26     struct yacjs_dict *result = malloc(sizeof(*result));
27
28     result->entries = NULL;
29     result->entries_size = 0;
30     result->entries_count = 0;
31
32     return result;
33 }
34
35 void yacjs_dict_destroy(struct yacjs_dict *dict, yacjs_dict_visitor visitor) {
36     if(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);
41             }
42         }
43     }
44     free(dict->entries);
45     free(dict);
46 }
47
48 void yacjs_dict_set(struct yacjs_dict *dict, const char *key,
49     void *value) {
50
51     if(dict->entries_size == dict->entries_count) {
52         resize(dict, dict->entries_size*2 + 1);
53     }
54
55     uint64_t hash = string_hash(key);
56     insert_helper(dict, hash, ystrdup(key), value);
57 }
58
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;
65     }
66     return NULL;
67 }
68
69 static char *ystrdup(const char *string) {
70     return strcpy(malloc(strlen(string)+1), string);
71 }
72
73 static uint64_t string_hash(const char *string) {
74     uint64_t result = 14695981039346656037ULL; 
75
76     while(*string) {
77         result ^= *string;
78         result *= 1099511628211ULL;
79         string ++;
80     }
81
82     return result;
83 }
84
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]));
91
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,
95             oentries[i].value);
96     }
97 }
98
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;
107         break;
108     }
109     dict->entries_count ++;
110 }