lbbs/src/hash_dict.c

/* SPDX-License-Identifier: GPL-3.0-or-later */
/*
 * hash_dict
 *   - hash-map based dict feature
 *
 * Copyright (C) 2004-2025  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]);

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

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

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

        p_dict->prime_index = hash_dict_prime_list_count - 1;
        for (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\n");
                free(p_dict);
                return NULL;
        }

        for (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\n", i);
                        for (j = i - 1; j >= 0; j--)
                        {
                                free(p_dict->buckets[j]);
                        }
                        free(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;
        unsigned int i;
        unsigned int j;

        if (p_dict == NULL)
        {
                return;
        }

        for (i = 0; i < p_dict->bucket_count; i++)
        {
                for (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\n");
                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\n");
                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\n");
                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\n");
                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\n");
                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-2025 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	HASH_DICT *hash_dict_create(int item_count_limit)
40	{
41	HASH_DICT *p_dict = NULL;
42	unsigned int i;
43	unsigned int j;
44
45	if (item_count_limit <= 0)
46	{
47	log_error("Invalid item_count_limit(%d)<=0\n", item_count_limit);
48	return NULL;
49	}
50
51	p_dict = (HASH_DICT *)malloc(sizeof(HASH_DICT));
52	if (p_dict == NULL)
53	{
54	log_error("malloc(HASH_DICT) error\n");
55	return NULL;
56	}
57
58	p_dict->prime_index = hash_dict_prime_list_count - 1;
59	for (i = 0; i < hash_dict_prime_list_count; i++)
60	{
61	if (item_count_limit < hash_dict_prime_list[i])
62	{
63	p_dict->prime_index = i;
64	break;
65	}
66	}
67
68	p_dict->bucket_count = (hash_dict_prime_list[p_dict->prime_index] + HASH_DICT_BUCKET_SIZE - 1) / HASH_DICT_BUCKET_SIZE;
69
70	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);
71	if (p_dict->p_item_pool == NULL)
72	{
73	log_error("memory_pool_init(HASH_ITEM) error\n");
74	free(p_dict);
75	return NULL;
76	}
77
78	for (i = 0; i < p_dict->bucket_count; i++)
79	{
80	p_dict->buckets[i] = calloc(HASH_DICT_BUCKET_SIZE, sizeof(HASH_ITEM *));
81	if (p_dict->buckets[i] == NULL)
82	{
83	log_error("calloc(HASH_DICT_BUCKET_SIZE, HASH_ITEM) error at bucket %d\n", i);
84	for (j = i - 1; j >= 0; j--)
85	{
86	free(p_dict->buckets[j]);
87	}
88	free(p_dict);
89	return NULL;
90	}
91	}
92
93	p_dict->item_count = 0;
94
95	return p_dict;
96	}
97
98	void hash_dict_destroy(HASH_DICT *p_dict)
99	{
100	HASH_ITEM *p_item;
101	HASH_ITEM *p_next;
102	unsigned int i;
103	unsigned int j;
104
105	if (p_dict == NULL)
106	{
107	return;
108	}
109
110	for (i = 0; i < p_dict->bucket_count; i++)
111	{
112	for (j = 0; j < HASH_DICT_BUCKET_SIZE; j++)
113	{
114	p_item = p_dict->buckets[i][j];
115	while (p_item != NULL)
116	{
117	p_next = p_item->p_next;
118	memory_pool_free(p_dict->p_item_pool, p_item);
119	p_item = p_next;
120	}
121	}
122	free(p_dict->buckets[i]);
123	}
124
125	memory_pool_cleanup(p_dict->p_item_pool);
126	free(p_dict);
127	}
128
129	int hash_dict_set(HASH_DICT *p_dict, uint64_t key, int64_t value)
130	{
131	uint64_t bucket_index;
132	uint64_t item_index_in_bucket;
133	HASH_ITEM *p_item;
134
135	if (p_dict == NULL)
136	{
137	log_error("NULL pointer error\n");
138	return -1;
139	}
140
141	bucket_index = (key % (HASH_DICT_BUCKET_SIZE * p_dict->bucket_count)) / HASH_DICT_BUCKET_SIZE;
142	item_index_in_bucket = key % HASH_DICT_BUCKET_SIZE;
143
144	p_item = p_dict->buckets[bucket_index][item_index_in_bucket];
145	while (p_item != NULL)
146	{
147	if (p_item->key == key)
148	{
149	p_item->value = value;
150	return 1;
151	}
152	p_item = p_item->p_next;
153	}
154
155	p_item = (HASH_ITEM *)memory_pool_alloc(p_dict->p_item_pool);
156	if (p_item == NULL)
157	{
158	log_error("memory_pool_alloc(HASH_ITEM) error\n");
159	return -1;
160	}
161
162	p_item->key = key;
163	p_item->value = value;
164	p_item->p_next = p_dict->buckets[bucket_index][item_index_in_bucket];
165	p_dict->buckets[bucket_index][item_index_in_bucket] = p_item;
166
167	(p_dict->item_count)++;
168
169	return 0;
170	}
171
172	int hash_dict_inc(HASH_DICT *p_dict, uint64_t key, int64_t value_inc)
173	{
174	uint64_t bucket_index;
175	uint64_t item_index_in_bucket;
176	HASH_ITEM *p_item;
177
178	if (p_dict == NULL)
179	{
180	log_error("NULL pointer error\n");
181	return -1;
182	}
183
184	bucket_index = (key % (HASH_DICT_BUCKET_SIZE * p_dict->bucket_count)) / HASH_DICT_BUCKET_SIZE;
185	item_index_in_bucket = key % HASH_DICT_BUCKET_SIZE;
186
187	p_item = p_dict->buckets[bucket_index][item_index_in_bucket];
188	while (p_item != NULL)
189	{
190	if (p_item->key == key)
191	{
192	p_item->value += value_inc;
193	return 1;
194	}
195	p_item = p_item->p_next;
196	}
197
198	return 0;
199	}
200
201	int hash_dict_get(HASH_DICT p_dict, uint64_t key, int64_t p_value)
202	{
203	uint64_t bucket_index;
204	uint64_t item_index_in_bucket;
205	HASH_ITEM *p_item;
206
207	if (p_dict == NULL \|\| p_value == NULL)
208	{
209	log_error("NULL pointer error\n");
210	return -1;
211	}
212
213	bucket_index = (key % (HASH_DICT_BUCKET_SIZE * p_dict->bucket_count)) / HASH_DICT_BUCKET_SIZE;
214	item_index_in_bucket = key % HASH_DICT_BUCKET_SIZE;
215
216	p_item = p_dict->buckets[bucket_index][item_index_in_bucket];
217	while (p_item != NULL)
218	{
219	if (p_item->key == key)
220	{
221	*p_value = p_item->value;
222	return 1;
223	}
224	p_item = p_item->p_next;
225	}
226
227	return 0;
228	}
229
230	int hash_dict_del(HASH_DICT *p_dict, uint64_t key)
231	{
232	uint64_t bucket_index;
233	uint64_t item_index_in_bucket;
234	HASH_ITEM *p_item;
235	HASH_ITEM *p_prior;
236
237	if (p_dict == NULL)
238	{
239	log_error("NULL pointer error\n");
240	return -1;
241	}
242
243	bucket_index = (key % (HASH_DICT_BUCKET_SIZE * p_dict->bucket_count)) / HASH_DICT_BUCKET_SIZE;
244	item_index_in_bucket = key % HASH_DICT_BUCKET_SIZE;
245
246	p_item = p_dict->buckets[bucket_index][item_index_in_bucket];
247	p_prior = NULL;
248	while (p_item != NULL)
249	{
250	if (p_item->key == key)
251	{
252	if (p_prior == NULL)
253	{
254	p_dict->buckets[bucket_index][item_index_in_bucket] = p_item->p_next;
255	}
256	else
257	{
258	p_prior->p_next = p_item->p_next;
259	}
260	memory_pool_free(p_dict->p_item_pool, p_item);
261	(p_dict->item_count)--;
262	return 1;
263	}
264	p_prior = p_item;
265	p_item = p_item->p_next;
266	}
267
268	return 0;
269	}
webmaster@leafok.com	ViewVC Help
Powered by ViewVC 1.3.0-beta1