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