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>

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 = 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 (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() 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));

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

        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;

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