/src/libxlsxwriter/src/hash_table.c

Source
/*****************************************************************************
 * hash_table - Hash table functions for libxlsxwriter.
 *
 * Used in conjunction with the libxlsxwriter library.
 *
 * SPDX-License-Identifier: BSD-2-Clause
 * Copyright 2014-2025, John McNamara, jmcnamara@cpan.org.
 *
 */

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdint.h>
#include "xlsxwriter/hash_table.h"

/*
 * Calculate the hash key using the FNV function. See:
 * http://en.wikipedia.org/wiki/Fowler-Noll-Vo_hash_function
 */
STATIC size_t
_generate_hash_key(void *data, size_t data_len, size_t num_buckets)
{
    unsigned char *p = data;
    size_t hash = 2166136261U;
    size_t i;

    for (i = 0; i < data_len; i++)
        hash = (hash * 16777619) ^ p[i];

    return hash % num_buckets;
}

/*
 * Check if an element exists in the hash table and return a pointer
 * to it if it does.
 */
lxw_hash_element *
lxw_hash_key_exists(lxw_hash_table *lxw_hash, void *key, size_t key_len)
{
    size_t hash_key = _generate_hash_key(key, key_len, lxw_hash->num_buckets);
    struct lxw_hash_bucket_list *list;
    lxw_hash_element *element;

    if (!lxw_hash->buckets[hash_key]) {
        /* The key isn't in the LXW_HASH hash table. */
        return NULL;
    }
    else {
        /* The key is already in the table or there is a hash collision. */
        list = lxw_hash->buckets[hash_key];

        /* Iterate over the keys in the bucket's linked list. */
        SLIST_FOREACH(element, list, lxw_hash_list_pointers) {
            if (memcmp(element->key, key, key_len) == 0) {
                /* The key already exists in the table. */
                return element;
            }
        }

        /* Key doesn't exist in the list so this is a hash collision. */
        return NULL;
    }
}

/*
 * Insert or update a value in the LXW_HASH table based on a key
 * and return a pointer to the new or updated element.
 */
lxw_hash_element *
lxw_insert_hash_element(lxw_hash_table *lxw_hash, void *key, void *value,
                        size_t key_len)
{
    size_t hash_key = _generate_hash_key(key, key_len, lxw_hash->num_buckets);
    struct lxw_hash_bucket_list *list = NULL;
    lxw_hash_element *element = NULL;

    if (!lxw_hash->buckets[hash_key]) {
        /* The key isn't in the LXW_HASH hash table. */

        /* Create a linked list in the bucket to hold the lxw_hash keys. */
        list = calloc(1, sizeof(struct lxw_hash_bucket_list));
        GOTO_LABEL_ON_MEM_ERROR(list, mem_error1);

        /* Initialize the bucket linked list. */
        SLIST_INIT(list);

        /* Create an lxw_hash element to add to the linked list. */
        element = calloc(1, sizeof(lxw_hash_element));
        GOTO_LABEL_ON_MEM_ERROR(element, mem_error1);

        /* Store the key and value. */
        element->key = key;
        element->value = value;

        /* Add the lxw_hash element to the bucket's linked list. */
        SLIST_INSERT_HEAD(list, element, lxw_hash_list_pointers);

        /* Also add it to the insertion order linked list. */
        STAILQ_INSERT_TAIL(lxw_hash->order_list, element,
                           lxw_hash_order_pointers);

        /* Store the bucket list at the hash index. */
        lxw_hash->buckets[hash_key] = list;

        lxw_hash->used_buckets++;
        lxw_hash->unique_count++;

        return element;
    }
    else {
        /* The key is already in the table or there is a hash collision. */
        list = lxw_hash->buckets[hash_key];

        /* Iterate over the keys in the bucket's linked list. */
        SLIST_FOREACH(element, list, lxw_hash_list_pointers) {
            if (memcmp(element->key, key, key_len) == 0) {
                /* The key already exists in the table. Update the value. */
                if (lxw_hash->free_value)
                    free(element->value);

                element->value = value;
                return element;
            }
        }

        /* Key doesn't exist in the list so this is a hash collision.
         * Create an lxw_hash element to add to the linked list. */
        element = calloc(1, sizeof(lxw_hash_element));
        GOTO_LABEL_ON_MEM_ERROR(element, mem_error2);

        /* Store the key and value. */
        element->key = key;
        element->value = value;

        /* Add the lxw_hash element to the bucket linked list. */
        SLIST_INSERT_HEAD(list, element, lxw_hash_list_pointers);

        /* Also add it to the insertion order linked list. */
        STAILQ_INSERT_TAIL(lxw_hash->order_list, element,
                           lxw_hash_order_pointers);

        lxw_hash->unique_count++;

        return element;
    }

mem_error1:
    free(list);

mem_error2:
    free(element);
    return NULL;
}

/*
 * Create a new LXW_HASH hash table object.
 */
lxw_hash_table *
lxw_hash_new(uint32_t num_buckets, uint8_t free_key, uint8_t free_value)
{
    /* Create the new hash table. */
    lxw_hash_table *lxw_hash = calloc(1, sizeof(lxw_hash_table));
    RETURN_ON_MEM_ERROR(lxw_hash, NULL);

    lxw_hash->free_key = free_key;
    lxw_hash->free_value = free_value;

    /* Add the lxw_hash element buckets. */
    lxw_hash->buckets =
        calloc(num_buckets, sizeof(struct lxw_hash_bucket_list *));
    GOTO_LABEL_ON_MEM_ERROR(lxw_hash->buckets, mem_error);

    /* Add a list for tracking the insertion order. */
    lxw_hash->order_list = calloc(1, sizeof(struct lxw_hash_order_list));
    GOTO_LABEL_ON_MEM_ERROR(lxw_hash->order_list, mem_error);

    /* Initialize the order list. */
    STAILQ_INIT(lxw_hash->order_list);

    /* Store the number of buckets to calculate the load factor. */
    lxw_hash->num_buckets = num_buckets;

    return lxw_hash;

mem_error:
    lxw_hash_free(lxw_hash);
    return NULL;
}

/*
 * Free the LXW_HASH hash table object.
 */
void
lxw_hash_free(lxw_hash_table *lxw_hash)
{
    size_t i;
    lxw_hash_element *element;
    lxw_hash_element *element_temp;

    if (!lxw_hash)
        return;

    /* Free the lxw_hash_elements and data using the ordered linked list. */
    if (lxw_hash->order_list) {
        STAILQ_FOREACH_SAFE(element, lxw_hash->order_list,
                            lxw_hash_order_pointers, element_temp) {
            if (lxw_hash->free_key)
                free(element->key);
            if (lxw_hash->free_value)
                free(element->value);
            free(element);
        }
    }

    /* Free the buckets from the hash table. */
    for (i = 0; i < lxw_hash->num_buckets; i++) {
        free(lxw_hash->buckets[i]);
    }

    free(lxw_hash->order_list);
    free(lxw_hash->buckets);
    free(lxw_hash);
}

Coverage Report

Created: 2025-10-28 06:57

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