lbbs/src/hash_dict.c

/* SPDX-License-Identifier: GPL-3.0-or-later */
/*
 * hash_dict
 *   - hash-map based dict feature
 *
 * Copyright (C) 2004-2026  Leaflet <leaflet@leafok.com>
 */

#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#include "hash_dict.h"
#include "log.h"
#include <stdlib.h>

enum _hash_dict_constant_t
{
        MP_NODE_COUNT_PER_CHUNK = 1000,
};

// HASH_DICT_BUCKET_SIZE * bucket_count should be a prime number
static const unsigned int hash_dict_prime_list[] = {
        49157,
        98317,
        196613,
        393241,
        786433,
        1572869,
        3145739,
        6291469,
        12582917,
        25165843,
        50331653,
};

static const unsigned int hash_dict_prime_list_count = sizeof(hash_dict_prime_list) / sizeof(hash_dict_prime_list[0]);

// External definition for inline function
extern inline unsigned int hash_dict_item_count(HASH_DICT *p_dict);

HASH_DICT *hash_dict_create(int item_count_limit)
{
        HASH_DICT *p_dict = NULL;

        if (item_count_limit <= 0)
        {
                log_error("Invalid item_count_limit(%d)<=0", item_count_limit);
                return NULL;
        }

        p_dict = (HASH_DICT *)malloc(sizeof(HASH_DICT));
        if (p_dict == NULL)
        {
                log_error("malloc(HASH_DICT) error");
                return NULL;
        }

        p_dict->prime_index = hash_dict_prime_list_count - 1;
        for (unsigned int i = 0; i < hash_dict_prime_list_count; i++)
        {
                if (item_count_limit < hash_dict_prime_list[i])
                {
                        p_dict->prime_index = i;
                        break;
                }
        }

        p_dict->bucket_count = (hash_dict_prime_list[p_dict->prime_index] + HASH_DICT_BUCKET_SIZE - 1) / HASH_DICT_BUCKET_SIZE;

        p_dict->p_item_pool = memory_pool_init(sizeof(HASH_ITEM), MP_NODE_COUNT_PER_CHUNK, item_count_limit / MP_NODE_COUNT_PER_CHUNK + 1);
        if (p_dict->p_item_pool == NULL)
        {
                log_error("memory_pool_init(HASH_ITEM) error");
                free(p_dict);
                return NULL;
        }

        for (unsigned int i = 0; i < p_dict->bucket_count; i++)
        {
                p_dict->buckets[i] = calloc(HASH_DICT_BUCKET_SIZE, sizeof(HASH_ITEM *));
                if (p_dict->buckets[i] == NULL)
                {
                        log_error("calloc(HASH_DICT_BUCKET_SIZE, HASH_ITEM) error at bucket %d", i);
                        p_dict->bucket_count = i;
                        hash_dict_destroy(p_dict);
                        return NULL;
                }
        }

        p_dict->item_count = 0;

        return p_dict;
}

void hash_dict_destroy(HASH_DICT *p_dict)
{
        HASH_ITEM *p_item;
        HASH_ITEM *p_next;

        if (p_dict == NULL)
        {
                return;
        }

        for (unsigned int i = 0; i < p_dict->bucket_count; i++)
        {
                for (unsigned int j = 0; j < HASH_DICT_BUCKET_SIZE; j++)
                {
                        p_item = p_dict->buckets[i][j];
                        while (p_item != NULL)
                        {
                                p_next = p_item->p_next;
                                memory_pool_free(p_dict->p_item_pool, p_item);
                                p_item = p_next;
                        }
                }
                free(p_dict->buckets[i]);
        }

        memory_pool_cleanup(p_dict->p_item_pool);
        free(p_dict);
}

int hash_dict_set(HASH_DICT *p_dict, uint64_t key, int64_t value)
{
        uint64_t bucket_index;
        uint64_t item_index_in_bucket;
        HASH_ITEM *p_item;

        if (p_dict == NULL)
        {
                log_error("NULL pointer error");
                return -1;
        }

        bucket_index = (key % (HASH_DICT_BUCKET_SIZE * p_dict->bucket_count)) / HASH_DICT_BUCKET_SIZE;
        item_index_in_bucket = key % HASH_DICT_BUCKET_SIZE;

        p_item = p_dict->buckets[bucket_index][item_index_in_bucket];
        while (p_item != NULL)
        {
                if (p_item->key == key)
                {
                        p_item->value = value;
                        return 1;
                }
                p_item = p_item->p_next;
        }

        p_item = (HASH_ITEM *)memory_pool_alloc(p_dict->p_item_pool);
        if (p_item == NULL)
        {
                log_error("memory_pool_alloc(HASH_ITEM) error");
                return -1;
        }

        p_item->key = key;
        p_item->value = value;
        p_item->p_next = p_dict->buckets[bucket_index][item_index_in_bucket];
        p_dict->buckets[bucket_index][item_index_in_bucket] = p_item;

        (p_dict->item_count)++;

        return 0;
}

int hash_dict_inc(HASH_DICT *p_dict, uint64_t key, int64_t value_inc)
{
        uint64_t bucket_index;
        uint64_t item_index_in_bucket;
        HASH_ITEM *p_item;

        if (p_dict == NULL)
        {
                log_error("NULL pointer error");
                return -1;
        }

        bucket_index = (key % (HASH_DICT_BUCKET_SIZE * p_dict->bucket_count)) / HASH_DICT_BUCKET_SIZE;
        item_index_in_bucket = key % HASH_DICT_BUCKET_SIZE;

        p_item = p_dict->buckets[bucket_index][item_index_in_bucket];
        while (p_item != NULL)
        {
                if (p_item->key == key)
                {
                        p_item->value += value_inc;
                        return 1;
                }
                p_item = p_item->p_next;
        }

        return 0;
}

int hash_dict_get(HASH_DICT *p_dict, uint64_t key, int64_t *p_value)
{
        uint64_t bucket_index;
        uint64_t item_index_in_bucket;
        HASH_ITEM *p_item;

        if (p_dict == NULL || p_value == NULL)
        {
                log_error("NULL pointer error");
                return -1;
        }

        bucket_index = (key % (HASH_DICT_BUCKET_SIZE * p_dict->bucket_count)) / HASH_DICT_BUCKET_SIZE;
        item_index_in_bucket = key % HASH_DICT_BUCKET_SIZE;

        p_item = p_dict->buckets[bucket_index][item_index_in_bucket];
        while (p_item != NULL)
        {
                if (p_item->key == key)
                {
                        *p_value = p_item->value;
                        return 1;
                }
                p_item = p_item->p_next;
        }

        return 0;
}

int hash_dict_del(HASH_DICT *p_dict, uint64_t key)
{
        uint64_t bucket_index;
        uint64_t item_index_in_bucket;
        HASH_ITEM *p_item;
        HASH_ITEM *p_prior;

        if (p_dict == NULL)
        {
                log_error("NULL pointer error");
                return -1;
        }

        bucket_index = (key % (HASH_DICT_BUCKET_SIZE * p_dict->bucket_count)) / HASH_DICT_BUCKET_SIZE;
        item_index_in_bucket = key % HASH_DICT_BUCKET_SIZE;

        p_item = p_dict->buckets[bucket_index][item_index_in_bucket];
        p_prior = NULL;
        while (p_item != NULL)
        {
                if (p_item->key == key)
                {
                        if (p_prior == NULL)
                        {
                                p_dict->buckets[bucket_index][item_index_in_bucket] = p_item->p_next;
                        }
                        else
                        {
                                p_prior->p_next = p_item->p_next;
                        }
                        memory_pool_free(p_dict->p_item_pool, p_item);
                        (p_dict->item_count)--;
                        return 1;
                }
                p_prior = p_item;
                p_item = p_item->p_next;
        }

        return 0;
}
1	sysadm	1.1	/* SPDX-License-Identifier: GPL-3.0-or-later */
2			/*
3			* hash_dict
4			* - hash-map based dict feature
5			*
6	sysadm	1.7	* Copyright (C) 2004-2026 Leaflet <leaflet@leafok.com>
7	sysadm	1.1	*/
8
9			#ifdef HAVE_CONFIG_H
10			#include "config.h"
11			#endif
12
13			#include "hash_dict.h"
14			#include "log.h"
15			#include <stdlib.h>
16
17			enum _hash_dict_constant_t
18			{
19			MP_NODE_COUNT_PER_CHUNK = 1000,
20			};
21
22			// HASH_DICT_BUCKET_SIZE * bucket_count should be a prime number
23			static const unsigned int hash_dict_prime_list[] = {
24			49157,
25			98317,
26			196613,
27			393241,
28			786433,
29			1572869,
30			3145739,
31			6291469,
32			12582917,
33			25165843,
34			50331653,
35			};
36
37	sysadm	1.4	static const unsigned int hash_dict_prime_list_count = sizeof(hash_dict_prime_list) / sizeof(hash_dict_prime_list[0]);
38	sysadm	1.1
39	sysadm	1.8	// External definition for inline function
40			extern inline unsigned int hash_dict_item_count(HASH_DICT *p_dict);
41
42	sysadm	1.1	HASH_DICT *hash_dict_create(int item_count_limit)
43			{
44			HASH_DICT *p_dict = NULL;
45
46			if (item_count_limit <= 0)
47			{
48	sysadm	1.6	log_error("Invalid item_count_limit(%d)<=0", item_count_limit);
49	sysadm	1.1	return NULL;
50			}
51
52			p_dict = (HASH_DICT *)malloc(sizeof(HASH_DICT));
53			if (p_dict == NULL)
54			{
55	sysadm	1.6	log_error("malloc(HASH_DICT) error");
56	sysadm	1.1	return NULL;
57			}
58
59			p_dict->prime_index = hash_dict_prime_list_count - 1;
60	sysadm	1.5	for (unsigned int i = 0; i < hash_dict_prime_list_count; i++)
61	sysadm	1.1	{
62			if (item_count_limit < hash_dict_prime_list[i])
63			{
64			p_dict->prime_index = i;
65			break;
66			}
67			}
68
69			p_dict->bucket_count = (hash_dict_prime_list[p_dict->prime_index] + HASH_DICT_BUCKET_SIZE - 1) / HASH_DICT_BUCKET_SIZE;
70
71			p_dict->p_item_pool = memory_pool_init(sizeof(HASH_ITEM), MP_NODE_COUNT_PER_CHUNK, item_count_limit / MP_NODE_COUNT_PER_CHUNK + 1);
72			if (p_dict->p_item_pool == NULL)
73			{
74	sysadm	1.6	log_error("memory_pool_init(HASH_ITEM) error");
75	sysadm	1.1	free(p_dict);
76			return NULL;
77			}
78
79	sysadm	1.5	for (unsigned int i = 0; i < p_dict->bucket_count; i++)
80	sysadm	1.1	{
81			p_dict->buckets[i] = calloc(HASH_DICT_BUCKET_SIZE, sizeof(HASH_ITEM *));
82			if (p_dict->buckets[i] == NULL)
83			{
84	sysadm	1.6	log_error("calloc(HASH_DICT_BUCKET_SIZE, HASH_ITEM) error at bucket %d", i);
85	sysadm	1.5	p_dict->bucket_count = i;
86			hash_dict_destroy(p_dict);
87	sysadm	1.1	return NULL;
88			}
89			}
90
91			p_dict->item_count = 0;
92
93			return p_dict;
94			}
95
96			void hash_dict_destroy(HASH_DICT *p_dict)
97			{
98			HASH_ITEM *p_item;
99			HASH_ITEM *p_next;
100
101			if (p_dict == NULL)
102			{
103			return;
104			}
105
106	sysadm	1.5	for (unsigned int i = 0; i < p_dict->bucket_count; i++)
107	sysadm	1.1	{
108	sysadm	1.5	for (unsigned int j = 0; j < HASH_DICT_BUCKET_SIZE; j++)
109	sysadm	1.1	{
110			p_item = p_dict->buckets[i][j];
111			while (p_item != NULL)
112			{
113			p_next = p_item->p_next;
114			memory_pool_free(p_dict->p_item_pool, p_item);
115			p_item = p_next;
116			}
117			}
118			free(p_dict->buckets[i]);
119			}
120
121			memory_pool_cleanup(p_dict->p_item_pool);
122			free(p_dict);
123			}
124
125			int hash_dict_set(HASH_DICT *p_dict, uint64_t key, int64_t value)
126			{
127			uint64_t bucket_index;
128			uint64_t item_index_in_bucket;
129			HASH_ITEM *p_item;
130
131			if (p_dict == NULL)
132			{
133	sysadm	1.6	log_error("NULL pointer error");
134	sysadm	1.1	return -1;
135			}
136
137			bucket_index = (key % (HASH_DICT_BUCKET_SIZE * p_dict->bucket_count)) / HASH_DICT_BUCKET_SIZE;
138			item_index_in_bucket = key % HASH_DICT_BUCKET_SIZE;
139
140			p_item = p_dict->buckets[bucket_index][item_index_in_bucket];
141			while (p_item != NULL)
142			{
143			if (p_item->key == key)
144			{
145			p_item->value = value;
146	sysadm	1.3	return 1;
147	sysadm	1.1	}
148			p_item = p_item->p_next;
149			}
150
151			p_item = (HASH_ITEM *)memory_pool_alloc(p_dict->p_item_pool);
152			if (p_item == NULL)
153			{
154	sysadm	1.6	log_error("memory_pool_alloc(HASH_ITEM) error");
155	sysadm	1.1	return -1;
156			}
157
158			p_item->key = key;
159			p_item->value = value;
160			p_item->p_next = p_dict->buckets[bucket_index][item_index_in_bucket];
161			p_dict->buckets[bucket_index][item_index_in_bucket] = p_item;
162
163			(p_dict->item_count)++;
164
165			return 0;
166			}
167
168	sysadm	1.2	int hash_dict_inc(HASH_DICT *p_dict, uint64_t key, int64_t value_inc)
169			{
170			uint64_t bucket_index;
171			uint64_t item_index_in_bucket;
172			HASH_ITEM *p_item;
173
174			if (p_dict == NULL)
175			{
176	sysadm	1.6	log_error("NULL pointer error");
177	sysadm	1.2	return -1;
178			}
179
180			bucket_index = (key % (HASH_DICT_BUCKET_SIZE * p_dict->bucket_count)) / HASH_DICT_BUCKET_SIZE;
181			item_index_in_bucket = key % HASH_DICT_BUCKET_SIZE;
182
183			p_item = p_dict->buckets[bucket_index][item_index_in_bucket];
184			while (p_item != NULL)
185			{
186			if (p_item->key == key)
187			{
188			p_item->value += value_inc;
189	sysadm	1.3	return 1;
190	sysadm	1.2	}
191			p_item = p_item->p_next;
192			}
193
194			return 0;
195			}
196
197	sysadm	1.1	int hash_dict_get(HASH_DICT p_dict, uint64_t key, int64_t p_value)
198			{
199			uint64_t bucket_index;
200			uint64_t item_index_in_bucket;
201			HASH_ITEM *p_item;
202
203			if (p_dict == NULL \|\| p_value == NULL)
204			{
205	sysadm	1.6	log_error("NULL pointer error");
206	sysadm	1.1	return -1;
207			}
208
209			bucket_index = (key % (HASH_DICT_BUCKET_SIZE * p_dict->bucket_count)) / HASH_DICT_BUCKET_SIZE;
210			item_index_in_bucket = key % HASH_DICT_BUCKET_SIZE;
211
212			p_item = p_dict->buckets[bucket_index][item_index_in_bucket];
213			while (p_item != NULL)
214			{
215			if (p_item->key == key)
216			{
217			*p_value = p_item->value;
218			return 1;
219			}
220			p_item = p_item->p_next;
221			}
222
223			return 0;
224			}
225
226			int hash_dict_del(HASH_DICT *p_dict, uint64_t key)
227			{
228			uint64_t bucket_index;
229			uint64_t item_index_in_bucket;
230			HASH_ITEM *p_item;
231			HASH_ITEM *p_prior;
232
233			if (p_dict == NULL)
234			{
235	sysadm	1.6	log_error("NULL pointer error");
236	sysadm	1.1	return -1;
237			}
238
239			bucket_index = (key % (HASH_DICT_BUCKET_SIZE * p_dict->bucket_count)) / HASH_DICT_BUCKET_SIZE;
240			item_index_in_bucket = key % HASH_DICT_BUCKET_SIZE;
241
242			p_item = p_dict->buckets[bucket_index][item_index_in_bucket];
243			p_prior = NULL;
244			while (p_item != NULL)
245			{
246			if (p_item->key == key)
247			{
248			if (p_prior == NULL)
249			{
250			p_dict->buckets[bucket_index][item_index_in_bucket] = p_item->p_next;
251			}
252			else
253			{
254			p_prior->p_next = p_item->p_next;
255			}
256			memory_pool_free(p_dict->p_item_pool, p_item);
257			(p_dict->item_count)--;
258			return 1;
259			}
260			p_prior = p_item;
261			p_item = p_item->p_next;
262			}
263
264			return 0;
265			}
webmaster@leafok.com	ViewVC Help
Powered by ViewVC 1.3.0-beta1