lbbs/src/trie_dict.c

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

#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
        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;

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