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	/* SPDX-License-Identifier: GPL-3.0-or-later */
2	/*
3	* hash_dict
4	* - hash-map based dict feature
5	*
6	* Copyright (C) 2004-2026 Leaflet <leaflet@leafok.com>
7	*/
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	static const unsigned int hash_dict_prime_list_count = sizeof(hash_dict_prime_list) / sizeof(hash_dict_prime_list[0]);
38
39	// External definition for inline function
40	extern inline unsigned int hash_dict_item_count(HASH_DICT *p_dict);
41
42	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	log_error("Invalid item_count_limit(%d)<=0", item_count_limit);
49	return NULL;
50	}
51
52	p_dict = (HASH_DICT *)malloc(sizeof(HASH_DICT));
53	if (p_dict == NULL)
54	{
55	log_error("malloc(HASH_DICT) error");
56	return NULL;
57	}
58
59	p_dict->prime_index = hash_dict_prime_list_count - 1;
60	for (unsigned int i = 0; i < hash_dict_prime_list_count; i++)
61	{
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	log_error("memory_pool_init(HASH_ITEM) error");
75	free(p_dict);
76	return NULL;
77	}
78
79	for (unsigned int i = 0; i < p_dict->bucket_count; i++)
80	{
81	p_dict->buckets[i] = calloc(HASH_DICT_BUCKET_SIZE, sizeof(HASH_ITEM *));
82	if (p_dict->buckets[i] == NULL)
83	{
84	log_error("calloc(HASH_DICT_BUCKET_SIZE, HASH_ITEM) error at bucket %d", i);
85	p_dict->bucket_count = i;
86	hash_dict_destroy(p_dict);
87	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	for (unsigned int i = 0; i < p_dict->bucket_count; i++)
107	{
108	for (unsigned int j = 0; j < HASH_DICT_BUCKET_SIZE; j++)
109	{
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	log_error("NULL pointer error");
134	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	return 1;
147	}
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	log_error("memory_pool_alloc(HASH_ITEM) error");
155	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	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	log_error("NULL pointer error");
177	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	return 1;
190	}
191	p_item = p_item->p_next;
192	}
193
194	return 0;
195	}
196
197	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	log_error("NULL pointer error");
206	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	log_error("NULL pointer error");
236	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