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 "log.h"
#include "trie_dict.h"
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>
#include <sys/ipc.h>
#include <sys/shm.h>

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

static TRIE_NODE_POOL *p_trie_node_pool;

int trie_dict_init(const char *filename, int node_count_limit)
{
        int shmid;
        int proj_id;
        key_t key;
        size_t size;
        void *p_shm;
        TRIE_NODE *p_trie_nodes;
        int i;

        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
        proj_id = (int)(time(NULL) % getpid());
        key = ftok(filename, proj_id);
        if (key == -1)
        {
                log_error("ftok(%s, %d) error (%d)\n", filename, proj_id, errno);
                return -2;
        }

        size = sizeof(TRIE_NODE_POOL) + sizeof(TRIE_NODE) * (size_t)node_count_limit;
        shmid = shmget(key, size, IPC_CREAT | IPC_EXCL | 0600);
        if (shmid == -1)
        {
                log_error("shmget(size = %d) error (%d)\n", size, errno);
                return -3;
        }
        p_shm = shmat(shmid, NULL, 0);
        if (p_shm == (void *)-1)
        {
                log_error("shmat(shmid = %d) error (%d)\n", shmid, errno);
                return -3;
        }

        p_trie_node_pool = p_shm;
        p_trie_node_pool->shmid = shmid;
        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;
}

void trie_dict_cleanup(void)
{
        int shmid;

        if (p_trie_node_pool == NULL)
        {
                return;
        }

        shmid = p_trie_node_pool->shmid;

        detach_trie_dict_shm();

        if (shmid != 0 && shmctl(shmid, IPC_RMID, NULL) == -1)
        {
                log_error("shmctl(shmid = %d, IPC_RMID) error (%d)\n", shmid, errno);
        }
}

int set_trie_dict_shm_readonly(void)
{
#ifndef __CYGWIN__
        int shmid;
        void *p_shm;

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

        shmid = p_trie_node_pool->shmid;

        // Remap shared memory in read-only mode
        p_shm = shmat(shmid, p_trie_node_pool, SHM_RDONLY | SHM_REMAP);
        if (p_shm == (void *)-1)
        {
                log_error("shmat(trie_node_pool shmid=%d) error (%d)\n", shmid, errno);
                return -1;
        }

        p_trie_node_pool = p_shm;
#endif

        return 0;
}

int detach_trie_dict_shm(void)
{
        if (p_trie_node_pool != NULL && shmdt(p_trie_node_pool) == -1)
        {
                log_error("shmdt(trie_node_pool) 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	sysadm	1.13	/* SPDX-License-Identifier: GPL-3.0-or-later */
2			/*
3			* trie_dict
4			* - trie-tree based dict feature
5			*
6	sysadm	1.15	* Copyright (C) 2004-2025 Leaflet <leaflet@leafok.com>
7	sysadm	1.13	*/
8	sysadm	1.1
9	sysadm	1.16	#ifdef HAVE_CONFIG_H
10			#include "config.h"
11			#endif
12
13	sysadm	1.11	#include "log.h"
14	sysadm	1.1	#include "trie_dict.h"
15	sysadm	1.7	#include <errno.h>
16	sysadm	1.10	#include <stdio.h>
17	sysadm	1.1	#include <stdlib.h>
18	sysadm	1.10	#include <string.h>
19	sysadm	1.7	#include <time.h>
20			#include <unistd.h>
21	sysadm	1.11	#include <sys/ipc.h>
22	sysadm	1.7	#include <sys/shm.h>
23
24			struct trie_node_pool_t
25			{
26			int shmid;
27	sysadm	1.8	int node_count_limit;
28			int node_count;
29	sysadm	1.7	TRIE_NODE *p_node_free_list;
30			};
31			typedef struct trie_node_pool_t TRIE_NODE_POOL;
32
33			static TRIE_NODE_POOL *p_trie_node_pool;
34
35	sysadm	1.8	int trie_dict_init(const char *filename, int node_count_limit)
36	sysadm	1.7	{
37			int shmid;
38			int proj_id;
39			key_t key;
40			size_t size;
41			void *p_shm;
42	sysadm	1.8	TRIE_NODE *p_trie_nodes;
43	sysadm	1.7	int i;
44
45			if (p_trie_node_pool != NULL)
46			{
47			log_error("trie_dict_pool already initialized\n");
48			return -1;
49			}
50
51	sysadm	1.8	if (node_count_limit <= 0 \|\| node_count_limit > TRIE_NODE_PER_POOL)
52			{
53			log_error("trie_dict_init(%d) error: invalid node_count_limit\n", node_count_limit);
54			return -1;
55			}
56
57	sysadm	1.7	// Allocate shared memory
58			proj_id = (int)(time(NULL) % getpid());
59			key = ftok(filename, proj_id);
60			if (key == -1)
61			{
62			log_error("ftok(%s, %d) error (%d)\n", filename, proj_id, errno);
63			return -2;
64			}
65
66	sysadm	1.8	size = sizeof(TRIE_NODE_POOL) + sizeof(TRIE_NODE) * (size_t)node_count_limit;
67	sysadm	1.7	shmid = shmget(key, size, IPC_CREAT \| IPC_EXCL \| 0600);
68			if (shmid == -1)
69			{
70			log_error("shmget(size = %d) error (%d)\n", size, errno);
71			return -3;
72			}
73			p_shm = shmat(shmid, NULL, 0);
74			if (p_shm == (void *)-1)
75			{
76			log_error("shmat(shmid = %d) error (%d)\n", shmid, errno);
77			return -3;
78			}
79
80			p_trie_node_pool = p_shm;
81			p_trie_node_pool->shmid = shmid;
82	sysadm	1.8	p_trie_node_pool->node_count_limit = node_count_limit;
83	sysadm	1.7	p_trie_node_pool->node_count = 0;
84
85	sysadm	1.12	p_trie_nodes = (TRIE_NODE )((char )p_shm + sizeof(TRIE_NODE_POOL));
86	sysadm	1.8	p_trie_node_pool->p_node_free_list = &(p_trie_nodes[0]);
87			for (i = 0; i < node_count_limit - 1; i++)
88	sysadm	1.7	{
89	sysadm	1.8	p_trie_nodes[i].p_nodes[0] = &(p_trie_nodes[i + 1]);
90	sysadm	1.7	}
91	sysadm	1.8	p_trie_nodes[node_count_limit - 1].p_nodes[0] = NULL;
92	sysadm	1.7
93			return 0;
94			}
95
96			void trie_dict_cleanup(void)
97			{
98			int shmid;
99
100			if (p_trie_node_pool == NULL)
101			{
102			return;
103			}
104
105			shmid = p_trie_node_pool->shmid;
106
107			detach_trie_dict_shm();
108
109	sysadm	1.14	if (shmid != 0 && shmctl(shmid, IPC_RMID, NULL) == -1)
110	sysadm	1.7	{
111			log_error("shmctl(shmid = %d, IPC_RMID) error (%d)\n", shmid, errno);
112			}
113			}
114
115			int set_trie_dict_shm_readonly(void)
116			{
117	sysadm	1.19	#ifndef __CYGWIN__
118	sysadm	1.7	int shmid;
119			void *p_shm;
120
121			if (p_trie_node_pool == NULL)
122			{
123			log_error("trie_dict_pool not initialized\n");
124			return -1;
125			}
126
127			shmid = p_trie_node_pool->shmid;
128
129			// Remap shared memory in read-only mode
130			p_shm = shmat(shmid, p_trie_node_pool, SHM_RDONLY \| SHM_REMAP);
131			if (p_shm == (void *)-1)
132			{
133	sysadm	1.9	log_error("shmat(trie_node_pool shmid=%d) error (%d)\n", shmid, errno);
134	sysadm	1.7	return -1;
135			}
136
137			p_trie_node_pool = p_shm;
138	sysadm	1.19	#endif
139	sysadm	1.7
140			return 0;
141			}
142
143			int detach_trie_dict_shm(void)
144			{
145			if (p_trie_node_pool != NULL && shmdt(p_trie_node_pool) == -1)
146			{
147	sysadm	1.9	log_error("shmdt(trie_node_pool) error (%d)\n", errno);
148	sysadm	1.7	return -1;
149			}
150	sysadm	1.8
151	sysadm	1.7	p_trie_node_pool = NULL;
152
153			return 0;
154			}
155	sysadm	1.1
156			TRIE_NODE *trie_dict_create(void)
157			{
158	sysadm	1.7	TRIE_NODE *p_dict = NULL;
159
160			if (p_trie_node_pool != NULL && p_trie_node_pool->p_node_free_list != NULL)
161			{
162			p_dict = p_trie_node_pool->p_node_free_list;
163			p_trie_node_pool->p_node_free_list = p_dict->p_nodes[0];
164	sysadm	1.1
165	sysadm	1.10	memset(p_dict, 0, sizeof(*p_dict));
166	sysadm	1.8
167			p_trie_node_pool->node_count++;
168			}
169			else if (p_trie_node_pool != NULL)
170			{
171			log_error("trie_dict_create() error: node depleted %d >= %d\n", p_trie_node_pool->node_count, p_trie_node_pool->node_count_limit);
172	sysadm	1.7	}
173	sysadm	1.1
174			return p_dict;
175			}
176
177			void trie_dict_destroy(TRIE_NODE *p_dict)
178			{
179	sysadm	1.7	if (p_trie_node_pool == NULL \|\| p_dict == NULL)
180	sysadm	1.1	{
181			return;
182			}
183
184			for (int i = 0; i < TRIE_CHILDREN; i++)
185			{
186			if (p_dict->p_nodes[i] != NULL)
187			{
188			trie_dict_destroy(p_dict->p_nodes[i]);
189			}
190	sysadm	1.7	}
191	sysadm	1.3
192	sysadm	1.10	memset(p_dict, 0, sizeof(*p_dict));
193	sysadm	1.1
194	sysadm	1.7	p_dict->p_nodes[0] = p_trie_node_pool->p_node_free_list;
195			p_trie_node_pool->p_node_free_list = p_dict;
196	sysadm	1.8
197			p_trie_node_pool->node_count--;
198	sysadm	1.1	}
199
200			int trie_dict_set(TRIE_NODE p_dict, const char key, int64_t value)
201			{
202			int offset;
203
204	sysadm	1.5	if (p_dict == NULL)
205			{
206			return -1;
207			}
208
209	sysadm	1.1	while (key != NULL && *key != '\0')
210			{
211	sysadm	1.6	offset = (256 + *key) % 256;
212	sysadm	1.3	if (offset < 0 \|\| offset >= TRIE_CHILDREN) // incorrect key character
213			{
214			return -1;
215			}
216	sysadm	1.1
217			if (*(key + 1) == '\0')
218			{
219			if (p_dict->flags[offset] == 0 \|\| p_dict->values[offset] != value)
220			{
221			p_dict->values[offset] = value;
222			p_dict->flags[offset] = 1;
223			return 1; // Set to new value
224			}
225			return 0; // Unchanged
226			}
227			else
228			{
229			if (p_dict->p_nodes[offset] == NULL)
230			{
231			if ((p_dict->p_nodes[offset] = trie_dict_create()) == NULL)
232			{
233			return -2; // OOM
234			}
235			}
236			p_dict = p_dict->p_nodes[offset];
237			key++;
238			}
239			}
240
241			return -1; // NULL key
242			}
243
244			int trie_dict_get(TRIE_NODE p_dict, const char key, int64_t *p_value)
245			{
246			int offset;
247
248	sysadm	1.5	if (p_dict == NULL)
249			{
250			return -1;
251			}
252
253	sysadm	1.1	while (key != NULL && *key != '\0')
254			{
255	sysadm	1.6	offset = (256 + *key) % 256;
256	sysadm	1.3	if (offset < 0 \|\| offset >= TRIE_CHILDREN) // incorrect key character
257			{
258			return -1;
259			}
260	sysadm	1.1
261			if (*(key + 1) == '\0')
262			{
263			if (p_dict->flags[offset] != 0)
264			{
265			*p_value = p_dict->values[offset];
266			return 1; // Found
267			}
268			else
269			{
270			return 0; // Not exist
271			}
272			}
273			else if (p_dict->p_nodes[offset] == NULL)
274			{
275			return 0; // Not exist
276			}
277			else
278			{
279			p_dict = p_dict->p_nodes[offset];
280			key++;
281			}
282			}
283
284			return -1; // NULL key
285			}
286
287			int trie_dict_del(TRIE_NODE p_dict, const char key)
288			{
289			int offset;
290
291	sysadm	1.5	if (p_dict == NULL)
292			{
293			return -1;
294			}
295
296	sysadm	1.1	while (key != NULL && *key != '\0')
297			{
298	sysadm	1.6	offset = (256 + *key) % 256;
299	sysadm	1.3	if (offset < 0 \|\| offset >= TRIE_CHILDREN) // incorrect key character
300			{
301			return -1;
302			}
303	sysadm	1.1
304			if (*(key + 1) == '\0')
305			{
306			if (p_dict->flags[offset] != 0)
307			{
308			p_dict->flags[offset] = 0;
309			p_dict->values[offset] = 0;
310			return 1; // Done
311			}
312			else
313			{
314			return 0; // Not exist
315			}
316			}
317			else if (p_dict->p_nodes[offset] == NULL)
318			{
319			return 0; // Not exist
320			}
321			else
322			{
323			p_dict = p_dict->p_nodes[offset];
324			key++;
325			}
326			}
327
328			return -1; // NULL key
329			}
330	sysadm	1.2
331			static void _trie_dict_traverse(TRIE_NODE p_dict, trie_dict_traverse_cb cb, char key, int depth)
332			{
333			if (p_dict == NULL \|\| depth >= TRIE_MAX_KEY_LEN)
334			{
335			return;
336			}
337
338			for (int i = 0; i < TRIE_CHILDREN; i++)
339			{
340			if (p_dict->flags[i] != 0)
341			{
342	sysadm	1.5	key[depth] = (char)i;
343	sysadm	1.3	key[depth + 1] = '\0';
344	sysadm	1.2	(*cb)(key, p_dict->values[i]);
345			}
346
347			if (p_dict->p_nodes[i] != NULL && depth + 1 < TRIE_MAX_KEY_LEN)
348			{
349	sysadm	1.5	key[depth] = (char)i;
350	sysadm	1.2	_trie_dict_traverse(p_dict->p_nodes[i], cb, key, depth + 1);
351			}
352	sysadm	1.5	}
353	sysadm	1.2	}
354
355			void trie_dict_traverse(TRIE_NODE *p_dict, trie_dict_traverse_cb cb)
356			{
357			char key[TRIE_MAX_KEY_LEN + 1];
358	sysadm	1.5
359			if (p_dict == NULL)
360			{
361			return;
362			}
363	sysadm	1.2
364			_trie_dict_traverse(p_dict, cb, key, 0);
365			}
366	sysadm	1.8
367			int trie_dict_used_nodes(void)
368			{
369			return (p_trie_node_pool == NULL ? -1 : p_trie_node_pool->node_count);
370			}
webmaster@leafok.com	ViewVC Help
Powered by ViewVC 1.3.0-beta1