1 /*****************************************************************************
2 * hash_table - Hash table functions for libxlsxwriter.
3 *
4 * Used in conjunction with the libxlsxwriter library.
5 *
6 * Copyright 2014-2021, John McNamara, jmcnamara@cpan.org. See LICENSE.txt.
7 *
8 */
9
10 #include <stdlib.h>
11 #include <stdio.h>
12 #include <string.h>
13 #include <stdint.h>
14 #include "xlsxwriter/hash_table.h"
15
16 /*
17 * Calculate the hash key using the FNV function. See:
18 * http://en.wikipedia.org/wiki/Fowler-Noll-Vo_hash_function
19 */
20 STATIC size_t
_generate_hash_key(void * data,size_t data_len,size_t num_buckets)21 _generate_hash_key(void *data, size_t data_len, size_t num_buckets)
22 {
23 unsigned char *p = data;
24 size_t hash = 2166136261U;
25 size_t i;
26
27 for (i = 0; i < data_len; i++)
28 hash = (hash * 16777619) ^ p[i];
29
30 return hash % num_buckets;
31 }
32
33 /*
34 * Check if an element exists in the hash table and return a pointer
35 * to it if it does.
36 */
37 lxw_hash_element *
lxw_hash_key_exists(lxw_hash_table * lxw_hash,void * key,size_t key_len)38 lxw_hash_key_exists(lxw_hash_table *lxw_hash, void *key, size_t key_len)
39 {
40 size_t hash_key = _generate_hash_key(key, key_len, lxw_hash->num_buckets);
41 struct lxw_hash_bucket_list *list;
42 lxw_hash_element *element;
43
44 if (!lxw_hash->buckets[hash_key]) {
45 /* The key isn't in the LXW_HASH hash table. */
46 return NULL;
47 }
48 else {
49 /* The key is already in the table or there is a hash collision. */
50 list = lxw_hash->buckets[hash_key];
51
52 /* Iterate over the keys in the bucket's linked list. */
53 SLIST_FOREACH(element, list, lxw_hash_list_pointers) {
54 if (memcmp(element->key, key, key_len) == 0) {
55 /* The key already exists in the table. */
56 return element;
57 }
58 }
59
60 /* Key doesn't exist in the list so this is a hash collision. */
61 return NULL;
62 }
63 }
64
65 /*
66 * Insert or update a value in the LXW_HASH table based on a key
67 * and return a pointer to the new or updated element.
68 */
69 lxw_hash_element *
lxw_insert_hash_element(lxw_hash_table * lxw_hash,void * key,void * value,size_t key_len)70 lxw_insert_hash_element(lxw_hash_table *lxw_hash, void *key, void *value,
71 size_t key_len)
72 {
73 size_t hash_key = _generate_hash_key(key, key_len, lxw_hash->num_buckets);
74 struct lxw_hash_bucket_list *list = NULL;
75 lxw_hash_element *element = NULL;
76
77 if (!lxw_hash->buckets[hash_key]) {
78 /* The key isn't in the LXW_HASH hash table. */
79
80 /* Create a linked list in the bucket to hold the lxw_hash keys. */
81 list = calloc(1, sizeof(struct lxw_hash_bucket_list));
82 GOTO_LABEL_ON_MEM_ERROR(list, mem_error1);
83
84 /* Initialize the bucket linked list. */
85 SLIST_INIT(list);
86
87 /* Create an lxw_hash element to add to the linked list. */
88 element = calloc(1, sizeof(lxw_hash_element));
89 GOTO_LABEL_ON_MEM_ERROR(element, mem_error1);
90
91 /* Store the key and value. */
92 element->key = key;
93 element->value = value;
94
95 /* Add the lxw_hash element to the bucket's linked list. */
96 SLIST_INSERT_HEAD(list, element, lxw_hash_list_pointers);
97
98 /* Also add it to the insertion order linked list. */
99 STAILQ_INSERT_TAIL(lxw_hash->order_list, element,
100 lxw_hash_order_pointers);
101
102 /* Store the bucket list at the hash index. */
103 lxw_hash->buckets[hash_key] = list;
104
105 lxw_hash->used_buckets++;
106 lxw_hash->unique_count++;
107
108 return element;
109 }
110 else {
111 /* The key is already in the table or there is a hash collision. */
112 list = lxw_hash->buckets[hash_key];
113
114 /* Iterate over the keys in the bucket's linked list. */
115 SLIST_FOREACH(element, list, lxw_hash_list_pointers) {
116 if (memcmp(element->key, key, key_len) == 0) {
117 /* The key already exists in the table. Update the value. */
118 if (lxw_hash->free_value)
119 free(element->value);
120
121 element->value = value;
122 return element;
123 }
124 }
125
126 /* Key doesn't exist in the list so this is a hash collision.
127 * Create an lxw_hash element to add to the linked list. */
128 element = calloc(1, sizeof(lxw_hash_element));
129 GOTO_LABEL_ON_MEM_ERROR(element, mem_error2);
130
131 /* Store the key and value. */
132 element->key = key;
133 element->value = value;
134
135 /* Add the lxw_hash element to the bucket linked list. */
136 SLIST_INSERT_HEAD(list, element, lxw_hash_list_pointers);
137
138 /* Also add it to the insertion order linked list. */
139 STAILQ_INSERT_TAIL(lxw_hash->order_list, element,
140 lxw_hash_order_pointers);
141
142 lxw_hash->unique_count++;
143
144 return element;
145 }
146
147 mem_error1:
148 free(list);
149
150 mem_error2:
151 free(element);
152 return NULL;
153 }
154
155 /*
156 * Create a new LXW_HASH hash table object.
157 */
158 lxw_hash_table *
lxw_hash_new(uint32_t num_buckets,uint8_t free_key,uint8_t free_value)159 lxw_hash_new(uint32_t num_buckets, uint8_t free_key, uint8_t free_value)
160 {
161 /* Create the new hash table. */
162 lxw_hash_table *lxw_hash = calloc(1, sizeof(lxw_hash_table));
163 RETURN_ON_MEM_ERROR(lxw_hash, NULL);
164
165 lxw_hash->free_key = free_key;
166 lxw_hash->free_value = free_value;
167
168 /* Add the lxw_hash element buckets. */
169 lxw_hash->buckets =
170 calloc(num_buckets, sizeof(struct lxw_hash_bucket_list *));
171 GOTO_LABEL_ON_MEM_ERROR(lxw_hash->buckets, mem_error);
172
173 /* Add a list for tracking the insertion order. */
174 lxw_hash->order_list = calloc(1, sizeof(struct lxw_hash_order_list));
175 GOTO_LABEL_ON_MEM_ERROR(lxw_hash->order_list, mem_error);
176
177 /* Initialize the order list. */
178 STAILQ_INIT(lxw_hash->order_list);
179
180 /* Store the number of buckets to calculate the load factor. */
181 lxw_hash->num_buckets = num_buckets;
182
183 return lxw_hash;
184
185 mem_error:
186 lxw_hash_free(lxw_hash);
187 return NULL;
188 }
189
190 /*
191 * Free the LXW_HASH hash table object.
192 */
193 void
lxw_hash_free(lxw_hash_table * lxw_hash)194 lxw_hash_free(lxw_hash_table *lxw_hash)
195 {
196 size_t i;
197 lxw_hash_element *element;
198 lxw_hash_element *element_temp;
199
200 if (!lxw_hash)
201 return;
202
203 /* Free the lxw_hash_elements and data using the ordered linked list. */
204 if (lxw_hash->order_list) {
205 STAILQ_FOREACH_SAFE(element, lxw_hash->order_list,
206 lxw_hash_order_pointers, element_temp) {
207 if (lxw_hash->free_key)
208 free(element->key);
209 if (lxw_hash->free_value)
210 free(element->value);
211 free(element);
212 }
213 }
214
215 /* Free the buckets from the hash table. */
216 for (i = 0; i < lxw_hash->num_buckets; i++) {
217 free(lxw_hash->buckets[i]);
218 }
219
220 free(lxw_hash->order_list);
221 free(lxw_hash->buckets);
222 free(lxw_hash);
223 }
224