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]);

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