Fixed several memory leaks.
[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     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
47     free(dict->entries);
48     free(dict);
49 }
50
51 void YACJS_NAME(dict_set)(struct YACJS_NAME(dict) *dict, const char *key,
52     void *value) {
53
54     if(dict->entries_size == dict->entries_count) {
55         resize(dict, dict->entries_size*2 + 1);
56     }
57
58     uint64_t hash = string_hash(key);
59     insert_helper(dict, hash, ystrdup(key), value);
60 }
61
62 void *YACJS_NAME(dict_get)(struct YACJS_NAME(dict) *dict, const char *key) {
63     uint64_t hash = string_hash(key);
64     for(int i = 0; i < dict->entries_size; i ++) {
65         int in = (i+hash) % dict->entries_size;
66         if(!dict->entries[in].key) return NULL;
67         if(dict->entries[in].key_hash == hash) return dict->entries[in].value;
68     }
69     return NULL;
70 }
71
72 static char *ystrdup(const char *string) {
73     return strcpy(malloc(strlen(string)+1), string);
74 }
75
76 static uint64_t string_hash(const char *string) {
77     uint64_t result = 14695981039346656037ULL; 
78
79     while(*string) {
80         result ^= *string;
81         result *= 1099511628211ULL;
82         string ++;
83     }
84
85     return result;
86 }
87
88 static void resize(struct YACJS_NAME(dict) *dict, int newsize) {
89     struct YACJS_NAME(dict_entry) *oentries = dict->entries;
90     int osize = dict->entries_size;
91     dict->entries_size = newsize;
92     dict->entries_count = 0;
93     dict->entries = calloc(newsize, sizeof(oentries[0]));
94
95     for(int i = 0; i < osize; i ++) {
96         if(!oentries[i].key) continue;
97         insert_helper(dict, oentries[i].key_hash, oentries[i].key,
98             oentries[i].value);
99     }
100     free(oentries);
101 }
102
103 static void insert_helper(struct YACJS_NAME(dict) *dict, uint64_t hash,
104     char *key, void *value) {
105     for(int i = 0; i < dict->entries_size; i ++) {
106         int in = (i+hash) % dict->entries_size;
107         if(dict->entries[in].key) continue;
108         dict->entries[in].key = key;
109         dict->entries[in].key_hash = hash;
110         dict->entries[in].value = value;
111         break;
112     }
113     dict->entries_count ++;
114 }