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 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 0;
                }
                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_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	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			static const 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 0;
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_get(HASH_DICT p_dict, uint64_t key, int64_t p_value)
173			{
174			uint64_t bucket_index;
175			uint64_t item_index_in_bucket;
176			HASH_ITEM *p_item;
177
178			if (p_dict == NULL \|\| p_value == 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_value = p_item->value;
193			return 1;
194			}
195			p_item = p_item->p_next;
196			}
197
198			return 0;
199			}
200
201			int hash_dict_del(HASH_DICT *p_dict, uint64_t key)
202			{
203			uint64_t bucket_index;
204			uint64_t item_index_in_bucket;
205			HASH_ITEM *p_item;
206			HASH_ITEM *p_prior;
207
208			if (p_dict == NULL)
209			{
210			log_error("NULL pointer error\n");
211			return -1;
212			}
213
214			bucket_index = (key % (HASH_DICT_BUCKET_SIZE * p_dict->bucket_count)) / HASH_DICT_BUCKET_SIZE;
215			item_index_in_bucket = key % HASH_DICT_BUCKET_SIZE;
216
217			p_item = p_dict->buckets[bucket_index][item_index_in_bucket];
218			p_prior = NULL;
219			while (p_item != NULL)
220			{
221			if (p_item->key == key)
222			{
223			if (p_prior == NULL)
224			{
225			p_dict->buckets[bucket_index][item_index_in_bucket] = p_item->p_next;
226			}
227			else
228			{
229			p_prior->p_next = p_item->p_next;
230			}
231			memory_pool_free(p_dict->p_item_pool, p_item);
232			(p_dict->item_count)--;
233			return 1;
234			}
235			p_prior = p_item;
236			p_item = p_item->p_next;
237			}
238
239			return 0;
240			}
webmaster@leafok.com	ViewVC Help
Powered by ViewVC 1.3.0-beta1