lbbs/src/trie_dict.c

/* SPDX-License-Identifier: GPL-3.0-or-later */
/*
 * trie_dict
 *   - trie-tree based dict feature
 *
 * Copyright (C) 2004-2025  Leaflet <leaflet@leafok.com>
 */

#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#include "common.h"
#include "log.h"
#include "trie_dict.h"
#include <errno.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>
#include <sys/mman.h>
#include <sys/stat.h>

struct trie_node_pool_t
{
        size_t shm_size;
        int node_count_limit;
        int node_count;
        TRIE_NODE *p_node_free_list;
};
typedef struct trie_node_pool_t TRIE_NODE_POOL;

static char trie_node_shm_name[FILE_PATH_LEN];
static TRIE_NODE_POOL *p_trie_node_pool;

int trie_dict_init(const char *filename, int node_count_limit)
{
        char filepath[FILE_PATH_LEN];
        int fd;
        size_t size;
        void *p_shm;
        TRIE_NODE *p_trie_nodes;
        int i;

        if (filename == NULL)
        {
                log_error("NULL pointer error\n");
                return -1;
        }

        if (p_trie_node_pool != NULL)
        {
                log_error("trie_dict_pool already initialized\n");
                return -1;
        }

        if (node_count_limit <= 0 || node_count_limit > TRIE_NODE_PER_POOL)
        {
                log_error("trie_dict_init(%d) error: invalid node_count_limit\n", node_count_limit);
                return -1;
        }

        // Allocate shared memory
        size = sizeof(TRIE_NODE_POOL) + sizeof(TRIE_NODE) * (size_t)node_count_limit;

        strncpy(filepath, filename, sizeof(filepath) - 1);
        filepath[sizeof(filepath) - 1] = '\0';
        snprintf(trie_node_shm_name, sizeof(trie_node_shm_name), "/TRIE_DICT_SHM_%s", basename(filepath));

        if (shm_unlink(trie_node_shm_name) == -1 && errno != ENOENT)
        {
                log_error("shm_unlink(%s) error (%d)\n", trie_node_shm_name, errno);
                return -2;
        }

        if ((fd = shm_open(trie_node_shm_name, O_CREAT | O_EXCL | O_RDWR, 0600)) == -1)
        {
                log_error("shm_open(%s) error (%d)\n", trie_node_shm_name, errno);
                return -2;
        }
        if (ftruncate(fd, (off_t)size) == -1)
        {
                log_error("ftruncate(size=%d) error (%d)\n", size, errno);
                close(fd);
                return -2;
        }

        p_shm = mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0L);
        if (p_shm == MAP_FAILED)
        {
                log_error("mmap() error (%d)\n", errno);
                close(fd);
                return -2;
        }

        if (close(fd) < 0)
        {
                log_error("close(fd) error (%d)\n", errno);
                return -1;
        }

        p_trie_node_pool = p_shm;
        p_trie_node_pool->shm_size = size;
        p_trie_node_pool->node_count_limit = node_count_limit;
        p_trie_node_pool->node_count = 0;

        p_trie_nodes = (TRIE_NODE *)((char *)p_shm + sizeof(TRIE_NODE_POOL));
        p_trie_node_pool->p_node_free_list = &(p_trie_nodes[0]);
        for (i = 0; i < node_count_limit - 1; i++)
        {
                p_trie_nodes[i].p_nodes[0] = &(p_trie_nodes[i + 1]);
        }
        p_trie_nodes[node_count_limit - 1].p_nodes[0] = NULL;

        return 0;
}

int trie_dict_cleanup(void)
{
        if (p_trie_node_pool == NULL)
        {
                return -1;
        }

        detach_trie_dict_shm();

        if (shm_unlink(trie_node_shm_name) == -1 && errno != ENOENT)
        {
                log_error("shm_unlink(%s) error (%d)\n", trie_node_shm_name, errno);
                return -2;
        }

        trie_node_shm_name[0] = '\0';

        return 0;
}

int get_trie_dict_shm_readonly(void)
{
        int fd;
        struct stat sb;
        size_t size;
        void *p_shm;

        if ((fd = shm_open(trie_node_shm_name, O_RDONLY, 0600)) == -1)
        {
                log_error("shm_open(%s) error (%d)\n", trie_node_shm_name, errno);
                return -2;
        }

        if (fstat(fd, &sb) < 0)
        {
                log_error("fstat(fd) error (%d)\n", errno);
                close(fd);
                return -2;
        }

        size = (size_t)sb.st_size;

        p_shm = mmap(NULL, size, PROT_READ, MAP_SHARED, fd, 0L);
        if (p_shm == MAP_FAILED)
        {
                log_error("mmap() error (%d)\n", errno);
                close(fd);
                return -2;
        }

        if (close(fd) < 0)
        {
                log_error("close(fd) error (%d)\n", errno);
                return -1;
        }

        if (p_trie_node_pool->shm_size != size)
        {
                log_error("Shared memory size mismatch (%ld != %ld)\n", p_trie_node_pool->shm_size, size);
                munmap(p_shm, size);
                return -3;
        }

        p_trie_node_pool = p_shm;

        return 0;
}

int set_trie_dict_shm_readonly(void)
{
        if (p_trie_node_pool != NULL && mprotect(p_trie_node_pool, p_trie_node_pool->shm_size, PROT_READ) < 0)
        {
                log_error("mprotect() error (%d)\n", errno);
                return -1;
        }

        return 0;
}

int detach_trie_dict_shm(void)
{
        if (p_trie_node_pool != NULL && munmap(p_trie_node_pool, p_trie_node_pool->shm_size) < 0)
        {
                log_error("munmap() error (%d)\n", errno);
                return -1;
        }

        p_trie_node_pool = NULL;

        return 0;
}

TRIE_NODE *trie_dict_create(void)
{
        TRIE_NODE *p_dict = NULL;

        if (p_trie_node_pool != NULL && p_trie_node_pool->p_node_free_list != NULL)
        {
                p_dict = p_trie_node_pool->p_node_free_list;
                p_trie_node_pool->p_node_free_list = p_dict->p_nodes[0];

                memset(p_dict, 0, sizeof(*p_dict));

                p_trie_node_pool->node_count++;
        }
        else if (p_trie_node_pool != NULL)
        {
                log_error("trie_dict_create() error: node depleted %d >= %d\n", p_trie_node_pool->node_count, p_trie_node_pool->node_count_limit);
        }

        return p_dict;
}

void trie_dict_destroy(TRIE_NODE *p_dict)
{
        if (p_trie_node_pool == NULL || p_dict == NULL)
        {
                return;
        }

        for (int i = 0; i < TRIE_CHILDREN; i++)
        {
                if (p_dict->p_nodes[i] != NULL)
                {
                        trie_dict_destroy(p_dict->p_nodes[i]);
                }
        }

        memset(p_dict, 0, sizeof(*p_dict));

        p_dict->p_nodes[0] = p_trie_node_pool->p_node_free_list;
        p_trie_node_pool->p_node_free_list = p_dict;

        p_trie_node_pool->node_count--;
}

int trie_dict_set(TRIE_NODE *p_dict, const char *key, int64_t value)
{
        int offset;

        if (p_dict == NULL)
        {
                return -1;
        }

        while (key != NULL && *key != '\0')
        {
                offset = (256 + *key) % 256;
                if (offset < 0 || offset >= TRIE_CHILDREN) // incorrect key character
                {
                        return -1;
                }

                if (*(key + 1) == '\0')
                {
                        if (p_dict->flags[offset] == 0 || p_dict->values[offset] != value)
                        {
                                p_dict->values[offset] = value;
                                p_dict->flags[offset] = 1;
                                return 1; // Set to new value
                        }
                        return 0; // Unchanged
                }
                else
                {
                        if (p_dict->p_nodes[offset] == NULL)
                        {
                                if ((p_dict->p_nodes[offset] = trie_dict_create()) == NULL)
                                {
                                        return -2; // OOM
                                }
                        }
                        p_dict = p_dict->p_nodes[offset];
                        key++;
                }
        }

        return -1; // NULL key
}

int trie_dict_get(TRIE_NODE *p_dict, const char *key, int64_t *p_value)
{
        int offset;

        if (p_dict == NULL)
        {
                return -1;
        }

        while (key != NULL && *key != '\0')
        {
                offset = (256 + *key) % 256;
                if (offset < 0 || offset >= TRIE_CHILDREN) // incorrect key character
                {
                        return -1;
                }

                if (*(key + 1) == '\0')
                {
                        if (p_dict->flags[offset] != 0)
                        {
                                *p_value = p_dict->values[offset];
                                return 1; // Found
                        }
                        else
                        {
                                return 0; // Not exist
                        }
                }
                else if (p_dict->p_nodes[offset] == NULL)
                {
                        return 0; // Not exist
                }
                else
                {
                        p_dict = p_dict->p_nodes[offset];
                        key++;
                }
        }

        return -1; // NULL key
}

int trie_dict_del(TRIE_NODE *p_dict, const char *key)
{
        int offset;

        if (p_dict == NULL)
        {
                return -1;
        }

        while (key != NULL && *key != '\0')
        {
                offset = (256 + *key) % 256;
                if (offset < 0 || offset >= TRIE_CHILDREN) // incorrect key character
                {
                        return -1;
                }

                if (*(key + 1) == '\0')
                {
                        if (p_dict->flags[offset] != 0)
                        {
                                p_dict->flags[offset] = 0;
                                p_dict->values[offset] = 0;
                                return 1; // Done
                        }
                        else
                        {
                                return 0; // Not exist
                        }
                }
                else if (p_dict->p_nodes[offset] == NULL)
                {
                        return 0; // Not exist
                }
                else
                {
                        p_dict = p_dict->p_nodes[offset];
                        key++;
                }
        }

        return -1; // NULL key
}

static void _trie_dict_traverse(TRIE_NODE *p_dict, trie_dict_traverse_cb cb, char *key, int depth)
{
        if (p_dict == NULL || depth >= TRIE_MAX_KEY_LEN)
        {
                return;
        }

        for (int i = 0; i < TRIE_CHILDREN; i++)
        {
                if (p_dict->flags[i] != 0)
                {
                        key[depth] = (char)i;
                        key[depth + 1] = '\0';
                        (*cb)(key, p_dict->values[i]);
                }

                if (p_dict->p_nodes[i] != NULL && depth + 1 < TRIE_MAX_KEY_LEN)
                {
                        key[depth] = (char)i;
                        _trie_dict_traverse(p_dict->p_nodes[i], cb, key, depth + 1);
                }
        }
}

void trie_dict_traverse(TRIE_NODE *p_dict, trie_dict_traverse_cb cb)
{
        char key[TRIE_MAX_KEY_LEN + 1];

        if (p_dict == NULL)
        {
                return;
        }

        _trie_dict_traverse(p_dict, cb, key, 0);
}

int trie_dict_used_nodes(void)
{
        return (p_trie_node_pool == NULL ? -1 : p_trie_node_pool->node_count);
}
1	/* SPDX-License-Identifier: GPL-3.0-or-later */
2	/*
3	* trie_dict
4	* - trie-tree 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 "common.h"
14	#include "log.h"
15	#include "trie_dict.h"
16	#include <errno.h>
17	#include <fcntl.h>
18	#include <stdio.h>
19	#include <stdlib.h>
20	#include <string.h>
21	#include <time.h>
22	#include <unistd.h>
23	#include <sys/mman.h>
24	#include <sys/stat.h>
25
26	struct trie_node_pool_t
27	{
28	size_t shm_size;
29	int node_count_limit;
30	int node_count;
31	TRIE_NODE *p_node_free_list;
32	};
33	typedef struct trie_node_pool_t TRIE_NODE_POOL;
34
35	static char trie_node_shm_name[FILE_PATH_LEN];
36	static TRIE_NODE_POOL *p_trie_node_pool;
37
38	int trie_dict_init(const char *filename, int node_count_limit)
39	{
40	char filepath[FILE_PATH_LEN];
41	int fd;
42	size_t size;
43	void *p_shm;
44	TRIE_NODE *p_trie_nodes;
45	int i;
46
47	if (filename == NULL)
48	{
49	log_error("NULL pointer error\n");
50	return -1;
51	}
52
53	if (p_trie_node_pool != NULL)
54	{
55	log_error("trie_dict_pool already initialized\n");
56	return -1;
57	}
58
59	if (node_count_limit <= 0 \|\| node_count_limit > TRIE_NODE_PER_POOL)
60	{
61	log_error("trie_dict_init(%d) error: invalid node_count_limit\n", node_count_limit);
62	return -1;
63	}
64
65	// Allocate shared memory
66	size = sizeof(TRIE_NODE_POOL) + sizeof(TRIE_NODE) * (size_t)node_count_limit;
67
68	strncpy(filepath, filename, sizeof(filepath) - 1);
69	filepath[sizeof(filepath) - 1] = '\0';
70	snprintf(trie_node_shm_name, sizeof(trie_node_shm_name), "/TRIE_DICT_SHM_%s", basename(filepath));
71
72	if (shm_unlink(trie_node_shm_name) == -1 && errno != ENOENT)
73	{
74	log_error("shm_unlink(%s) error (%d)\n", trie_node_shm_name, errno);
75	return -2;
76	}
77
78	if ((fd = shm_open(trie_node_shm_name, O_CREAT \| O_EXCL \| O_RDWR, 0600)) == -1)
79	{
80	log_error("shm_open(%s) error (%d)\n", trie_node_shm_name, errno);
81	return -2;
82	}
83	if (ftruncate(fd, (off_t)size) == -1)
84	{
85	log_error("ftruncate(size=%d) error (%d)\n", size, errno);
86	close(fd);
87	return -2;
88	}
89
90	p_shm = mmap(NULL, size, PROT_READ \| PROT_WRITE, MAP_SHARED, fd, 0L);
91	if (p_shm == MAP_FAILED)
92	{
93	log_error("mmap() error (%d)\n", errno);
94	close(fd);
95	return -2;
96	}
97
98	if (close(fd) < 0)
99	{
100	log_error("close(fd) error (%d)\n", errno);
101	return -1;
102	}
103
104	p_trie_node_pool = p_shm;
105	p_trie_node_pool->shm_size = size;
106	p_trie_node_pool->node_count_limit = node_count_limit;
107	p_trie_node_pool->node_count = 0;
108
109	p_trie_nodes = (TRIE_NODE )((char )p_shm + sizeof(TRIE_NODE_POOL));
110	p_trie_node_pool->p_node_free_list = &(p_trie_nodes[0]);
111	for (i = 0; i < node_count_limit - 1; i++)
112	{
113	p_trie_nodes[i].p_nodes[0] = &(p_trie_nodes[i + 1]);
114	}
115	p_trie_nodes[node_count_limit - 1].p_nodes[0] = NULL;
116
117	return 0;
118	}
119
120	int trie_dict_cleanup(void)
121	{
122	if (p_trie_node_pool == NULL)
123	{
124	return -1;
125	}
126
127	detach_trie_dict_shm();
128
129	if (shm_unlink(trie_node_shm_name) == -1 && errno != ENOENT)
130	{
131	log_error("shm_unlink(%s) error (%d)\n", trie_node_shm_name, errno);
132	return -2;
133	}
134
135	trie_node_shm_name[0] = '\0';
136
137	return 0;
138	}
139
140	int get_trie_dict_shm_readonly(void)
141	{
142	int fd;
143	struct stat sb;
144	size_t size;
145	void *p_shm;
146
147	if ((fd = shm_open(trie_node_shm_name, O_RDONLY, 0600)) == -1)
148	{
149	log_error("shm_open(%s) error (%d)\n", trie_node_shm_name, errno);
150	return -2;
151	}
152
153	if (fstat(fd, &sb) < 0)
154	{
155	log_error("fstat(fd) error (%d)\n", errno);
156	close(fd);
157	return -2;
158	}
159
160	size = (size_t)sb.st_size;
161
162	p_shm = mmap(NULL, size, PROT_READ, MAP_SHARED, fd, 0L);
163	if (p_shm == MAP_FAILED)
164	{
165	log_error("mmap() error (%d)\n", errno);
166	close(fd);
167	return -2;
168	}
169
170	if (close(fd) < 0)
171	{
172	log_error("close(fd) error (%d)\n", errno);
173	return -1;
174	}
175
176	if (p_trie_node_pool->shm_size != size)
177	{
178	log_error("Shared memory size mismatch (%ld != %ld)\n", p_trie_node_pool->shm_size, size);
179	munmap(p_shm, size);
180	return -3;
181	}
182
183	p_trie_node_pool = p_shm;
184
185	return 0;
186	}
187
188	int set_trie_dict_shm_readonly(void)
189	{
190	if (p_trie_node_pool != NULL && mprotect(p_trie_node_pool, p_trie_node_pool->shm_size, PROT_READ) < 0)
191	{
192	log_error("mprotect() error (%d)\n", errno);
193	return -1;
194	}
195
196	return 0;
197	}
198
199	int detach_trie_dict_shm(void)
200	{
201	if (p_trie_node_pool != NULL && munmap(p_trie_node_pool, p_trie_node_pool->shm_size) < 0)
202	{
203	log_error("munmap() error (%d)\n", errno);
204	return -1;
205	}
206
207	p_trie_node_pool = NULL;
208
209	return 0;
210	}
211
212	TRIE_NODE *trie_dict_create(void)
213	{
214	TRIE_NODE *p_dict = NULL;
215
216	if (p_trie_node_pool != NULL && p_trie_node_pool->p_node_free_list != NULL)
217	{
218	p_dict = p_trie_node_pool->p_node_free_list;
219	p_trie_node_pool->p_node_free_list = p_dict->p_nodes[0];
220
221	memset(p_dict, 0, sizeof(*p_dict));
222
223	p_trie_node_pool->node_count++;
224	}
225	else if (p_trie_node_pool != NULL)
226	{
227	log_error("trie_dict_create() error: node depleted %d >= %d\n", p_trie_node_pool->node_count, p_trie_node_pool->node_count_limit);
228	}
229
230	return p_dict;
231	}
232
233	void trie_dict_destroy(TRIE_NODE *p_dict)
234	{
235	if (p_trie_node_pool == NULL \|\| p_dict == NULL)
236	{
237	return;
238	}
239
240	for (int i = 0; i < TRIE_CHILDREN; i++)
241	{
242	if (p_dict->p_nodes[i] != NULL)
243	{
244	trie_dict_destroy(p_dict->p_nodes[i]);
245	}
246	}
247
248	memset(p_dict, 0, sizeof(*p_dict));
249
250	p_dict->p_nodes[0] = p_trie_node_pool->p_node_free_list;
251	p_trie_node_pool->p_node_free_list = p_dict;
252
253	p_trie_node_pool->node_count--;
254	}
255
256	int trie_dict_set(TRIE_NODE p_dict, const char key, int64_t value)
257	{
258	int offset;
259
260	if (p_dict == NULL)
261	{
262	return -1;
263	}
264
265	while (key != NULL && *key != '\0')
266	{
267	offset = (256 + *key) % 256;
268	if (offset < 0 \|\| offset >= TRIE_CHILDREN) // incorrect key character
269	{
270	return -1;
271	}
272
273	if (*(key + 1) == '\0')
274	{
275	if (p_dict->flags[offset] == 0 \|\| p_dict->values[offset] != value)
276	{
277	p_dict->values[offset] = value;
278	p_dict->flags[offset] = 1;
279	return 1; // Set to new value
280	}
281	return 0; // Unchanged
282	}
283	else
284	{
285	if (p_dict->p_nodes[offset] == NULL)
286	{
287	if ((p_dict->p_nodes[offset] = trie_dict_create()) == NULL)
288	{
289	return -2; // OOM
290	}
291	}
292	p_dict = p_dict->p_nodes[offset];
293	key++;
294	}
295	}
296
297	return -1; // NULL key
298	}
299
300	int trie_dict_get(TRIE_NODE p_dict, const char key, int64_t *p_value)
301	{
302	int offset;
303
304	if (p_dict == NULL)
305	{
306	return -1;
307	}
308
309	while (key != NULL && *key != '\0')
310	{
311	offset = (256 + *key) % 256;
312	if (offset < 0 \|\| offset >= TRIE_CHILDREN) // incorrect key character
313	{
314	return -1;
315	}
316
317	if (*(key + 1) == '\0')
318	{
319	if (p_dict->flags[offset] != 0)
320	{
321	*p_value = p_dict->values[offset];
322	return 1; // Found
323	}
324	else
325	{
326	return 0; // Not exist
327	}
328	}
329	else if (p_dict->p_nodes[offset] == NULL)
330	{
331	return 0; // Not exist
332	}
333	else
334	{
335	p_dict = p_dict->p_nodes[offset];
336	key++;
337	}
338	}
339
340	return -1; // NULL key
341	}
342
343	int trie_dict_del(TRIE_NODE p_dict, const char key)
344	{
345	int offset;
346
347	if (p_dict == NULL)
348	{
349	return -1;
350	}
351
352	while (key != NULL && *key != '\0')
353	{
354	offset = (256 + *key) % 256;
355	if (offset < 0 \|\| offset >= TRIE_CHILDREN) // incorrect key character
356	{
357	return -1;
358	}
359
360	if (*(key + 1) == '\0')
361	{
362	if (p_dict->flags[offset] != 0)
363	{
364	p_dict->flags[offset] = 0;
365	p_dict->values[offset] = 0;
366	return 1; // Done
367	}
368	else
369	{
370	return 0; // Not exist
371	}
372	}
373	else if (p_dict->p_nodes[offset] == NULL)
374	{
375	return 0; // Not exist
376	}
377	else
378	{
379	p_dict = p_dict->p_nodes[offset];
380	key++;
381	}
382	}
383
384	return -1; // NULL key
385	}
386
387	static void _trie_dict_traverse(TRIE_NODE p_dict, trie_dict_traverse_cb cb, char key, int depth)
388	{
389	if (p_dict == NULL \|\| depth >= TRIE_MAX_KEY_LEN)
390	{
391	return;
392	}
393
394	for (int i = 0; i < TRIE_CHILDREN; i++)
395	{
396	if (p_dict->flags[i] != 0)
397	{
398	key[depth] = (char)i;
399	key[depth + 1] = '\0';
400	(*cb)(key, p_dict->values[i]);
401	}
402
403	if (p_dict->p_nodes[i] != NULL && depth + 1 < TRIE_MAX_KEY_LEN)
404	{
405	key[depth] = (char)i;
406	_trie_dict_traverse(p_dict->p_nodes[i], cb, key, depth + 1);
407	}
408	}
409	}
410
411	void trie_dict_traverse(TRIE_NODE *p_dict, trie_dict_traverse_cb cb)
412	{
413	char key[TRIE_MAX_KEY_LEN + 1];
414
415	if (p_dict == NULL)
416	{
417	return;
418	}
419
420	_trie_dict_traverse(p_dict, cb, key, 0);
421	}
422
423	int trie_dict_used_nodes(void)
424	{
425	return (p_trie_node_pool == NULL ? -1 : p_trie_node_pool->node_count);
426	}
webmaster@leafok.com	ViewVC Help
Powered by ViewVC 1.3.0-beta1