Implemented booleans, swapped to YACJS_NAME macro.
[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_NAME(dict_entry) {
8     char *key;
9     void *value;
10     uint64_t key_hash;
11 };
12
13 struct YACJS_NAME(dict) {
14     struct YACJS_NAME(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_NAME(dict) *dict, int newsize);
22 static void insert_helper(struct YACJS_NAME(dict) *dict, uint64_t hash,
23     const char *key, void *value);
24
25 struct YACJS_NAME(dict) *YACJS_NAME(dict_make)() {
26     struct YACJS_NAME(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_NAME(dict_destroy)(struct YACJS_NAME(dict) *dict,
36     YACJS_NAME(dict_visitor) visitor) {
37
38     if(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);
43             }
44         }
45     }
46     free(dict->entries);
47     free(dict);
48 }
49
50 void YACJS_NAME(dict_set)(struct YACJS_NAME(dict) *dict, const char *key,
51     void *value) {
52
53     if(dict->entries_size == dict->entries_count) {
54         resize(dict, dict->entries_size*2 + 1);
55     }
56
57     uint64_t hash = string_hash(key);
58     insert_helper(dict, hash, ystrdup(key), value);
59 }
60
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;
67     }
68     return NULL;
69 }
70
71 static char *ystrdup(const char *string) {
72     return strcpy(malloc(strlen(string)+1), string);
73 }
74
75 static uint64_t string_hash(const char *string) {
76     uint64_t result = 14695981039346656037ULL; 
77
78     while(*string) {
79         result ^= *string;
80         result *= 1099511628211ULL;
81         string ++;
82     }
83
84     return result;
85 }
86
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]));
93
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,
97             oentries[i].value);
98     }
99 }
100
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;
109         break;
110     }
111     dict->entries_count ++;
112 }