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)
{
        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
#if defined(__CYGWIN__)
        if (shmdt(p_trie_node_pool) == -1)
        {
                log_error("shmdt(trie_node_pool) error (%d)\n", errno);
                return -1;
        }
        p_shm = shmat(shmid, p_trie_node_pool, SHM_RDONLY);
#else
        p_shm = shmat(shmid, p_trie_node_pool, SHM_RDONLY | SHM_REMAP);
#endif
        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;

        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	/* 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 "log.h"
14	#include "trie_dict.h"
15	#include <errno.h>
16	#include <stdio.h>
17	#include <stdlib.h>
18	#include <string.h>
19	#include <time.h>
20	#include <unistd.h>
21	#include <sys/ipc.h>
22	#include <sys/shm.h>
23
24	struct trie_node_pool_t
25	{
26	int shmid;
27	int node_count_limit;
28	int node_count;
29	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	int trie_dict_init(const char *filename, int node_count_limit)
36	{
37	int shmid;
38	int proj_id;
39	key_t key;
40	size_t size;
41	void *p_shm;
42	TRIE_NODE *p_trie_nodes;
43	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	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	// 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	size = sizeof(TRIE_NODE_POOL) + sizeof(TRIE_NODE) * (size_t)node_count_limit;
67	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	p_trie_node_pool->node_count_limit = node_count_limit;
83	p_trie_node_pool->node_count = 0;
84
85	p_trie_nodes = (TRIE_NODE )((char )p_shm + sizeof(TRIE_NODE_POOL));
86	p_trie_node_pool->p_node_free_list = &(p_trie_nodes[0]);
87	for (i = 0; i < node_count_limit - 1; i++)
88	{
89	p_trie_nodes[i].p_nodes[0] = &(p_trie_nodes[i + 1]);
90	}
91	p_trie_nodes[node_count_limit - 1].p_nodes[0] = NULL;
92
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	if (shmid != 0 && shmctl(shmid, IPC_RMID, NULL) == -1)
110	{
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	int shmid;
118	void *p_shm;
119
120	if (p_trie_node_pool == NULL)
121	{
122	log_error("trie_dict_pool not initialized\n");
123	return -1;
124	}
125
126	shmid = p_trie_node_pool->shmid;
127
128	// Remap shared memory in read-only mode
129	#if defined(__CYGWIN__)
130	if (shmdt(p_trie_node_pool) == -1)
131	{
132	log_error("shmdt(trie_node_pool) error (%d)\n", errno);
133	return -1;
134	}
135	p_shm = shmat(shmid, p_trie_node_pool, SHM_RDONLY);
136	#else
137	p_shm = shmat(shmid, p_trie_node_pool, SHM_RDONLY \| SHM_REMAP);
138	#endif
139	if (p_shm == (void *)-1)
140	{
141	log_error("shmat(trie_node_pool shmid=%d) error (%d)\n", shmid, errno);
142	return -1;
143	}
144
145	p_trie_node_pool = p_shm;
146
147	return 0;
148	}
149
150	int detach_trie_dict_shm(void)
151	{
152	if (p_trie_node_pool != NULL && shmdt(p_trie_node_pool) == -1)
153	{
154	log_error("shmdt(trie_node_pool) error (%d)\n", errno);
155	return -1;
156	}
157
158	p_trie_node_pool = NULL;
159
160	return 0;
161	}
162
163	TRIE_NODE *trie_dict_create(void)
164	{
165	TRIE_NODE *p_dict = NULL;
166
167	if (p_trie_node_pool != NULL && p_trie_node_pool->p_node_free_list != NULL)
168	{
169	p_dict = p_trie_node_pool->p_node_free_list;
170	p_trie_node_pool->p_node_free_list = p_dict->p_nodes[0];
171
172	memset(p_dict, 0, sizeof(*p_dict));
173
174	p_trie_node_pool->node_count++;
175	}
176	else if (p_trie_node_pool != NULL)
177	{
178	log_error("trie_dict_create() error: node depleted %d >= %d\n", p_trie_node_pool->node_count, p_trie_node_pool->node_count_limit);
179	}
180
181	return p_dict;
182	}
183
184	void trie_dict_destroy(TRIE_NODE *p_dict)
185	{
186	if (p_trie_node_pool == NULL \|\| p_dict == NULL)
187	{
188	return;
189	}
190
191	for (int i = 0; i < TRIE_CHILDREN; i++)
192	{
193	if (p_dict->p_nodes[i] != NULL)
194	{
195	trie_dict_destroy(p_dict->p_nodes[i]);
196	}
197	}
198
199	memset(p_dict, 0, sizeof(*p_dict));
200
201	p_dict->p_nodes[0] = p_trie_node_pool->p_node_free_list;
202	p_trie_node_pool->p_node_free_list = p_dict;
203
204	p_trie_node_pool->node_count--;
205	}
206
207	int trie_dict_set(TRIE_NODE p_dict, const char key, int64_t value)
208	{
209	int offset;
210
211	if (p_dict == NULL)
212	{
213	return -1;
214	}
215
216	while (key != NULL && *key != '\0')
217	{
218	offset = (256 + *key) % 256;
219	if (offset < 0 \|\| offset >= TRIE_CHILDREN) // incorrect key character
220	{
221	return -1;
222	}
223
224	if (*(key + 1) == '\0')
225	{
226	if (p_dict->flags[offset] == 0 \|\| p_dict->values[offset] != value)
227	{
228	p_dict->values[offset] = value;
229	p_dict->flags[offset] = 1;
230	return 1; // Set to new value
231	}
232	return 0; // Unchanged
233	}
234	else
235	{
236	if (p_dict->p_nodes[offset] == NULL)
237	{
238	if ((p_dict->p_nodes[offset] = trie_dict_create()) == NULL)
239	{
240	return -2; // OOM
241	}
242	}
243	p_dict = p_dict->p_nodes[offset];
244	key++;
245	}
246	}
247
248	return -1; // NULL key
249	}
250
251	int trie_dict_get(TRIE_NODE p_dict, const char key, int64_t *p_value)
252	{
253	int offset;
254
255	if (p_dict == NULL)
256	{
257	return -1;
258	}
259
260	while (key != NULL && *key != '\0')
261	{
262	offset = (256 + *key) % 256;
263	if (offset < 0 \|\| offset >= TRIE_CHILDREN) // incorrect key character
264	{
265	return -1;
266	}
267
268	if (*(key + 1) == '\0')
269	{
270	if (p_dict->flags[offset] != 0)
271	{
272	*p_value = p_dict->values[offset];
273	return 1; // Found
274	}
275	else
276	{
277	return 0; // Not exist
278	}
279	}
280	else if (p_dict->p_nodes[offset] == NULL)
281	{
282	return 0; // Not exist
283	}
284	else
285	{
286	p_dict = p_dict->p_nodes[offset];
287	key++;
288	}
289	}
290
291	return -1; // NULL key
292	}
293
294	int trie_dict_del(TRIE_NODE p_dict, const char key)
295	{
296	int offset;
297
298	if (p_dict == NULL)
299	{
300	return -1;
301	}
302
303	while (key != NULL && *key != '\0')
304	{
305	offset = (256 + *key) % 256;
306	if (offset < 0 \|\| offset >= TRIE_CHILDREN) // incorrect key character
307	{
308	return -1;
309	}
310
311	if (*(key + 1) == '\0')
312	{
313	if (p_dict->flags[offset] != 0)
314	{
315	p_dict->flags[offset] = 0;
316	p_dict->values[offset] = 0;
317	return 1; // Done
318	}
319	else
320	{
321	return 0; // Not exist
322	}
323	}
324	else if (p_dict->p_nodes[offset] == NULL)
325	{
326	return 0; // Not exist
327	}
328	else
329	{
330	p_dict = p_dict->p_nodes[offset];
331	key++;
332	}
333	}
334
335	return -1; // NULL key
336	}
337
338	static void _trie_dict_traverse(TRIE_NODE p_dict, trie_dict_traverse_cb cb, char key, int depth)
339	{
340	if (p_dict == NULL \|\| depth >= TRIE_MAX_KEY_LEN)
341	{
342	return;
343	}
344
345	for (int i = 0; i < TRIE_CHILDREN; i++)
346	{
347	if (p_dict->flags[i] != 0)
348	{
349	key[depth] = (char)i;
350	key[depth + 1] = '\0';
351	(*cb)(key, p_dict->values[i]);
352	}
353
354	if (p_dict->p_nodes[i] != NULL && depth + 1 < TRIE_MAX_KEY_LEN)
355	{
356	key[depth] = (char)i;
357	_trie_dict_traverse(p_dict->p_nodes[i], cb, key, depth + 1);
358	}
359	}
360	}
361
362	void trie_dict_traverse(TRIE_NODE *p_dict, trie_dict_traverse_cb cb)
363	{
364	char key[TRIE_MAX_KEY_LEN + 1];
365
366	if (p_dict == NULL)
367	{
368	return;
369	}
370
371	_trie_dict_traverse(p_dict, cb, key, 0);
372	}
373
374	int trie_dict_used_nodes(void)
375	{
376	return (p_trie_node_pool == NULL ? -1 : p_trie_node_pool->node_count);
377	}
webmaster@leafok.com	ViewVC Help
Powered by ViewVC 1.3.0-beta1