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;

        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			* 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	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			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	sysadm	1.6	log_error("Invalid item_count_limit(%d)<=0", item_count_limit);
46	sysadm	1.1	return NULL;
47			}
48
49			p_dict = (HASH_DICT *)malloc(sizeof(HASH_DICT));
50			if (p_dict == NULL)
51			{
52	sysadm	1.6	log_error("malloc(HASH_DICT) error");
53	sysadm	1.1	return NULL;
54			}
55
56			p_dict->prime_index = hash_dict_prime_list_count - 1;
57	sysadm	1.5	for (unsigned int i = 0; i < hash_dict_prime_list_count; i++)
58	sysadm	1.1	{
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	sysadm	1.6	log_error("memory_pool_init(HASH_ITEM) error");
72	sysadm	1.1	free(p_dict);
73			return NULL;
74			}
75
76	sysadm	1.5	for (unsigned int i = 0; i < p_dict->bucket_count; i++)
77	sysadm	1.1	{
78			p_dict->buckets[i] = calloc(HASH_DICT_BUCKET_SIZE, sizeof(HASH_ITEM *));
79			if (p_dict->buckets[i] == NULL)
80			{
81	sysadm	1.6	log_error("calloc(HASH_DICT_BUCKET_SIZE, HASH_ITEM) error at bucket %d", i);
82	sysadm	1.5	p_dict->bucket_count = i;
83			hash_dict_destroy(p_dict);
84	sysadm	1.1	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	sysadm	1.5	for (unsigned int i = 0; i < p_dict->bucket_count; i++)
104	sysadm	1.1	{
105	sysadm	1.5	for (unsigned int j = 0; j < HASH_DICT_BUCKET_SIZE; j++)
106	sysadm	1.1	{
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	sysadm	1.6	log_error("NULL pointer error");
131	sysadm	1.1	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	sysadm	1.3	return 1;
144	sysadm	1.1	}
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	sysadm	1.6	log_error("memory_pool_alloc(HASH_ITEM) error");
152	sysadm	1.1	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	sysadm	1.2	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	sysadm	1.6	log_error("NULL pointer error");
174	sysadm	1.2	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	sysadm	1.3	return 1;
187	sysadm	1.2	}
188			p_item = p_item->p_next;
189			}
190
191			return 0;
192			}
193
194	sysadm	1.1	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	sysadm	1.6	log_error("NULL pointer error");
203	sysadm	1.1	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	sysadm	1.6	log_error("NULL pointer error");
233	sysadm	1.1	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