lbbs/src/trie_dict.c

/***************************************************************************
                                                 trie_dict.c  -  description
                                                         -------------------
        Copyright            : (C) 2004-2025 by Leaflet
        Email                : leaflet@leafok.com
 ***************************************************************************/

/***************************************************************************
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 3 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 ***************************************************************************/

#include "trie_dict.h"
#include "log.h"
#include <errno.h>
#include <stdlib.h>
#include <strings.h>
#include <stdio.h>
#include <time.h>
#include <unistd.h>
#include <sys/shm.h>
#include <sys/ipc.h>

#define TRIE_NODE_PER_POOL 10000

struct trie_node_pool_t
{
        int shmid;
        TRIE_NODE trie_nodes[TRIE_NODE_PER_POOL];
        TRIE_NODE *p_node_free_list;
        int node_count;
};
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 shmid;
        int proj_id;
        key_t key;
        size_t size;
        void *p_shm;
        int i;

        if (p_trie_node_pool != NULL)
        {
                log_error("trie_dict_pool already initialized\n");
                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);
        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 = 0;

        p_trie_node_pool->p_node_free_list = &(p_trie_node_pool->trie_nodes[0]);
        for (i = 0; i < TRIE_NODE_PER_POOL - 1; i++)
        {
                p_trie_node_pool->trie_nodes[i].p_nodes[0] = &(p_trie_node_pool->trie_nodes[i + 1]);
        }
        p_trie_node_pool->trie_nodes[TRIE_NODE_PER_POOL - 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 (shmctl(shmid, IPC_RMID, NULL) == -1)
        {
                log_error("shmctl(shmid = %d, IPC_RMID) error (%d)\n", shmid, errno);
        }

        p_trie_node_pool = NULL;
}

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() error (%d)\n", 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() 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];

                bzero(p_dict, sizeof(*p_dict));
        }

        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]);
                }
        }

        bzero(p_dict, 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;
}

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