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 "common.h"
#include "log.h"
#include "trie_dict.h"
#include <errno.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>
#include <sys/mman.h>
#include <sys/stat.h>

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

static char trie_node_shm_name[FILE_PATH_LEN];
static TRIE_NODE_POOL *p_trie_node_pool;

int trie_dict_init(const char *filename, int node_count_limit)
{
        char filepath[FILE_PATH_LEN];
        int fd;
        size_t size;
        void *p_shm;
        TRIE_NODE *p_trie_nodes;
        int i;

        if (filename == NULL)
        {
                log_error("NULL pointer error\n");
                return -1;
        }

        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
        size = sizeof(TRIE_NODE_POOL) + sizeof(TRIE_NODE) * (size_t)node_count_limit;

        strncpy(filepath, filename, sizeof(filepath) - 1);
        filepath[sizeof(filepath) - 1] = '\0';
        snprintf(trie_node_shm_name, sizeof(trie_node_shm_name), "/TRIE_DICT_SHM_%s", basename(filepath));

        if (shm_unlink(trie_node_shm_name) == -1 && errno != ENOENT)
        {
                log_error("shm_unlink(%s) error (%d)\n", trie_node_shm_name, errno);
                return -2;
        }

        if ((fd = shm_open(trie_node_shm_name, O_CREAT | O_EXCL | O_RDWR, 0600)) == -1)
        {
                log_error("shm_open(%s) error (%d)\n", trie_node_shm_name, errno);
                return -2;
        }
        if (ftruncate(fd, (off_t)size) == -1)
        {
                log_error("ftruncate(size=%d) error (%d)\n", size, errno);
                close(fd);
                return -2;
        }

        p_shm = mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0L);
        if (p_shm == MAP_FAILED)
        {
                log_error("mmap() error (%d)\n", errno);
                close(fd);
                return -2;
        }

        if (close(fd) < 0)
        {
                log_error("close(fd) error (%d)\n", errno);
                return -1;
        }

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

int trie_dict_cleanup(void)
{
        if (p_trie_node_pool == NULL)
        {
                return -1;
        }

        detach_trie_dict_shm();

        if (shm_unlink(trie_node_shm_name) == -1 && errno != ENOENT)
        {
                log_error("shm_unlink(%s) error (%d)\n", trie_node_shm_name, errno);
                return -2;
        }

        trie_node_shm_name[0] = '\0';

        return 0;
}

int get_trie_dict_shm_readonly(void)
{
        int fd;
        struct stat sb;
        size_t size;
        void *p_shm;

        if ((fd = shm_open(trie_node_shm_name, O_RDONLY, 0600)) == -1)
        {
                log_error("shm_open(%s) error (%d)\n", trie_node_shm_name, errno);
                return -2;
        }

        if (fstat(fd, &sb) < 0)
        {
                log_error("fstat(fd) error (%d)\n", errno);
                close(fd);
                return -2;
        }

        size = (size_t)sb.st_size;

        p_shm = mmap(NULL, size, PROT_READ, MAP_SHARED, fd, 0L);
        if (p_shm == MAP_FAILED)
        {
                log_error("mmap() error (%d)\n", errno);
                close(fd);
                return -2;
        }

        if (close(fd) < 0)
        {
                log_error("close(fd) error (%d)\n", errno);
                return -1;
        }

        if (p_trie_node_pool->shm_size != size)
        {
                log_error("Shared memory size mismatch (%ld != %ld)\n", p_trie_node_pool->shm_size, size);
                munmap(p_shm, size);
                return -3;
        }

        p_trie_node_pool = p_shm;

        return 0;
}

int set_trie_dict_shm_readonly(void)
{
        if (p_trie_node_pool != NULL && munmap(p_trie_node_pool, p_trie_node_pool->shm_size) < 0)
        {
                log_error("munmap() error (%d)\n", errno);
                return -2;
        }

        if (get_trie_dict_shm_readonly() < 0)
        {
                log_error("get_trie_dict_shm_readonly() error\n");
                return -3;
        }

        return 0;
}

int detach_trie_dict_shm(void)
{
        if (p_trie_node_pool != NULL && munmap(p_trie_node_pool, p_trie_node_pool->shm_size) < 0)
        {
                log_error("munmap() 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.20	#include "common.h"
14	sysadm	1.11	#include "log.h"
15	sysadm	1.1	#include "trie_dict.h"
16	sysadm	1.7	#include <errno.h>
17	sysadm	1.20	#include <fcntl.h>
18	sysadm	1.10	#include <stdio.h>
19	sysadm	1.1	#include <stdlib.h>
20	sysadm	1.10	#include <string.h>
21	sysadm	1.7	#include <time.h>
22			#include <unistd.h>
23	sysadm	1.20	#include <sys/mman.h>
24			#include <sys/stat.h>
25	sysadm	1.7
26			struct trie_node_pool_t
27			{
28	sysadm	1.20	size_t shm_size;
29	sysadm	1.8	int node_count_limit;
30			int node_count;
31	sysadm	1.7	TRIE_NODE *p_node_free_list;
32			};
33			typedef struct trie_node_pool_t TRIE_NODE_POOL;
34
35	sysadm	1.20	static char trie_node_shm_name[FILE_PATH_LEN];
36	sysadm	1.7	static TRIE_NODE_POOL *p_trie_node_pool;
37
38	sysadm	1.8	int trie_dict_init(const char *filename, int node_count_limit)
39	sysadm	1.7	{
40	sysadm	1.20	char filepath[FILE_PATH_LEN];
41			int fd;
42	sysadm	1.7	size_t size;
43			void *p_shm;
44	sysadm	1.8	TRIE_NODE *p_trie_nodes;
45	sysadm	1.7	int i;
46
47	sysadm	1.20	if (filename == NULL)
48			{
49			log_error("NULL pointer error\n");
50			return -1;
51			}
52
53	sysadm	1.7	if (p_trie_node_pool != NULL)
54			{
55			log_error("trie_dict_pool already initialized\n");
56			return -1;
57			}
58
59	sysadm	1.8	if (node_count_limit <= 0 \|\| node_count_limit > TRIE_NODE_PER_POOL)
60			{
61			log_error("trie_dict_init(%d) error: invalid node_count_limit\n", node_count_limit);
62			return -1;
63			}
64
65	sysadm	1.7	// Allocate shared memory
66	sysadm	1.20	size = sizeof(TRIE_NODE_POOL) + sizeof(TRIE_NODE) * (size_t)node_count_limit;
67
68			strncpy(filepath, filename, sizeof(filepath) - 1);
69			filepath[sizeof(filepath) - 1] = '\0';
70			snprintf(trie_node_shm_name, sizeof(trie_node_shm_name), "/TRIE_DICT_SHM_%s", basename(filepath));
71
72			if (shm_unlink(trie_node_shm_name) == -1 && errno != ENOENT)
73	sysadm	1.7	{
74	sysadm	1.20	log_error("shm_unlink(%s) error (%d)\n", trie_node_shm_name, errno);
75	sysadm	1.7	return -2;
76			}
77
78	sysadm	1.20	if ((fd = shm_open(trie_node_shm_name, O_CREAT \| O_EXCL \| O_RDWR, 0600)) == -1)
79			{
80			log_error("shm_open(%s) error (%d)\n", trie_node_shm_name, errno);
81			return -2;
82			}
83			if (ftruncate(fd, (off_t)size) == -1)
84			{
85			log_error("ftruncate(size=%d) error (%d)\n", size, errno);
86			close(fd);
87			return -2;
88			}
89
90			p_shm = mmap(NULL, size, PROT_READ \| PROT_WRITE, MAP_SHARED, fd, 0L);
91			if (p_shm == MAP_FAILED)
92	sysadm	1.7	{
93	sysadm	1.20	log_error("mmap() error (%d)\n", errno);
94			close(fd);
95			return -2;
96	sysadm	1.7	}
97	sysadm	1.20
98			if (close(fd) < 0)
99	sysadm	1.7	{
100	sysadm	1.20	log_error("close(fd) error (%d)\n", errno);
101			return -1;
102	sysadm	1.7	}
103
104			p_trie_node_pool = p_shm;
105	sysadm	1.20	p_trie_node_pool->shm_size = size;
106	sysadm	1.8	p_trie_node_pool->node_count_limit = node_count_limit;
107	sysadm	1.7	p_trie_node_pool->node_count = 0;
108
109	sysadm	1.12	p_trie_nodes = (TRIE_NODE )((char )p_shm + sizeof(TRIE_NODE_POOL));
110	sysadm	1.8	p_trie_node_pool->p_node_free_list = &(p_trie_nodes[0]);
111			for (i = 0; i < node_count_limit - 1; i++)
112	sysadm	1.7	{
113	sysadm	1.8	p_trie_nodes[i].p_nodes[0] = &(p_trie_nodes[i + 1]);
114	sysadm	1.7	}
115	sysadm	1.8	p_trie_nodes[node_count_limit - 1].p_nodes[0] = NULL;
116	sysadm	1.7
117			return 0;
118			}
119
120	sysadm	1.20	int trie_dict_cleanup(void)
121	sysadm	1.7	{
122			if (p_trie_node_pool == NULL)
123			{
124	sysadm	1.20	return -1;
125	sysadm	1.7	}
126
127			detach_trie_dict_shm();
128
129	sysadm	1.20	if (shm_unlink(trie_node_shm_name) == -1 && errno != ENOENT)
130	sysadm	1.7	{
131	sysadm	1.20	log_error("shm_unlink(%s) error (%d)\n", trie_node_shm_name, errno);
132			return -2;
133	sysadm	1.7	}
134	sysadm	1.20
135			trie_node_shm_name[0] = '\0';
136
137			return 0;
138	sysadm	1.7	}
139
140	sysadm	1.20	int get_trie_dict_shm_readonly(void)
141	sysadm	1.7	{
142	sysadm	1.20	int fd;
143			struct stat sb;
144			size_t size;
145	sysadm	1.7	void *p_shm;
146
147	sysadm	1.20	if ((fd = shm_open(trie_node_shm_name, O_RDONLY, 0600)) == -1)
148			{
149			log_error("shm_open(%s) error (%d)\n", trie_node_shm_name, errno);
150			return -2;
151			}
152
153			if (fstat(fd, &sb) < 0)
154	sysadm	1.7	{
155	sysadm	1.20	log_error("fstat(fd) error (%d)\n", errno);
156			close(fd);
157			return -2;
158	sysadm	1.7	}
159
160	sysadm	1.20	size = (size_t)sb.st_size;
161	sysadm	1.7
162	sysadm	1.20	p_shm = mmap(NULL, size, PROT_READ, MAP_SHARED, fd, 0L);
163			if (p_shm == MAP_FAILED)
164	sysadm	1.7	{
165	sysadm	1.20	log_error("mmap() error (%d)\n", errno);
166			close(fd);
167			return -2;
168			}
169
170			if (close(fd) < 0)
171			{
172			log_error("close(fd) error (%d)\n", errno);
173	sysadm	1.7	return -1;
174			}
175
176	sysadm	1.20	if (p_trie_node_pool->shm_size != size)
177			{
178			log_error("Shared memory size mismatch (%ld != %ld)\n", p_trie_node_pool->shm_size, size);
179			munmap(p_shm, size);
180			return -3;
181			}
182
183	sysadm	1.7	p_trie_node_pool = p_shm;
184	sysadm	1.20
185			return 0;
186			}
187
188			int set_trie_dict_shm_readonly(void)
189			{
190			if (p_trie_node_pool != NULL && munmap(p_trie_node_pool, p_trie_node_pool->shm_size) < 0)
191			{
192			log_error("munmap() error (%d)\n", errno);
193			return -2;
194			}
195
196			if (get_trie_dict_shm_readonly() < 0)
197			{
198			log_error("get_trie_dict_shm_readonly() error\n");
199			return -3;
200			}
201	sysadm	1.7
202			return 0;
203			}
204
205			int detach_trie_dict_shm(void)
206			{
207	sysadm	1.20	if (p_trie_node_pool != NULL && munmap(p_trie_node_pool, p_trie_node_pool->shm_size) < 0)
208	sysadm	1.7	{
209	sysadm	1.20	log_error("munmap() error (%d)\n", errno);
210	sysadm	1.7	return -1;
211			}
212	sysadm	1.8
213	sysadm	1.7	p_trie_node_pool = NULL;
214
215			return 0;
216			}
217	sysadm	1.1
218			TRIE_NODE *trie_dict_create(void)
219			{
220	sysadm	1.7	TRIE_NODE *p_dict = NULL;
221
222			if (p_trie_node_pool != NULL && p_trie_node_pool->p_node_free_list != NULL)
223			{
224			p_dict = p_trie_node_pool->p_node_free_list;
225			p_trie_node_pool->p_node_free_list = p_dict->p_nodes[0];
226	sysadm	1.1
227	sysadm	1.10	memset(p_dict, 0, sizeof(*p_dict));
228	sysadm	1.8
229			p_trie_node_pool->node_count++;
230			}
231			else if (p_trie_node_pool != NULL)
232			{
233			log_error("trie_dict_create() error: node depleted %d >= %d\n", p_trie_node_pool->node_count, p_trie_node_pool->node_count_limit);
234	sysadm	1.7	}
235	sysadm	1.1
236			return p_dict;
237			}
238
239			void trie_dict_destroy(TRIE_NODE *p_dict)
240			{
241	sysadm	1.7	if (p_trie_node_pool == NULL \|\| p_dict == NULL)
242	sysadm	1.1	{
243			return;
244			}
245
246			for (int i = 0; i < TRIE_CHILDREN; i++)
247			{
248			if (p_dict->p_nodes[i] != NULL)
249			{
250			trie_dict_destroy(p_dict->p_nodes[i]);
251			}
252	sysadm	1.7	}
253	sysadm	1.3
254	sysadm	1.10	memset(p_dict, 0, sizeof(*p_dict));
255	sysadm	1.1
256	sysadm	1.7	p_dict->p_nodes[0] = p_trie_node_pool->p_node_free_list;
257			p_trie_node_pool->p_node_free_list = p_dict;
258	sysadm	1.8
259			p_trie_node_pool->node_count--;
260	sysadm	1.1	}
261
262			int trie_dict_set(TRIE_NODE p_dict, const char key, int64_t value)
263			{
264			int offset;
265
266	sysadm	1.5	if (p_dict == NULL)
267			{
268			return -1;
269			}
270
271	sysadm	1.1	while (key != NULL && *key != '\0')
272			{
273	sysadm	1.6	offset = (256 + *key) % 256;
274	sysadm	1.3	if (offset < 0 \|\| offset >= TRIE_CHILDREN) // incorrect key character
275			{
276			return -1;
277			}
278	sysadm	1.1
279			if (*(key + 1) == '\0')
280			{
281			if (p_dict->flags[offset] == 0 \|\| p_dict->values[offset] != value)
282			{
283			p_dict->values[offset] = value;
284			p_dict->flags[offset] = 1;
285			return 1; // Set to new value
286			}
287			return 0; // Unchanged
288			}
289			else
290			{
291			if (p_dict->p_nodes[offset] == NULL)
292			{
293			if ((p_dict->p_nodes[offset] = trie_dict_create()) == NULL)
294			{
295			return -2; // OOM
296			}
297			}
298			p_dict = p_dict->p_nodes[offset];
299			key++;
300			}
301			}
302
303			return -1; // NULL key
304			}
305
306			int trie_dict_get(TRIE_NODE p_dict, const char key, int64_t *p_value)
307			{
308			int offset;
309
310	sysadm	1.5	if (p_dict == NULL)
311			{
312			return -1;
313			}
314
315	sysadm	1.1	while (key != NULL && *key != '\0')
316			{
317	sysadm	1.6	offset = (256 + *key) % 256;
318	sysadm	1.3	if (offset < 0 \|\| offset >= TRIE_CHILDREN) // incorrect key character
319			{
320			return -1;
321			}
322	sysadm	1.1
323			if (*(key + 1) == '\0')
324			{
325			if (p_dict->flags[offset] != 0)
326			{
327			*p_value = p_dict->values[offset];
328			return 1; // Found
329			}
330			else
331			{
332			return 0; // Not exist
333			}
334			}
335			else if (p_dict->p_nodes[offset] == NULL)
336			{
337			return 0; // Not exist
338			}
339			else
340			{
341			p_dict = p_dict->p_nodes[offset];
342			key++;
343			}
344			}
345
346			return -1; // NULL key
347			}
348
349			int trie_dict_del(TRIE_NODE p_dict, const char key)
350			{
351			int offset;
352
353	sysadm	1.5	if (p_dict == NULL)
354			{
355			return -1;
356			}
357
358	sysadm	1.1	while (key != NULL && *key != '\0')
359			{
360	sysadm	1.6	offset = (256 + *key) % 256;
361	sysadm	1.3	if (offset < 0 \|\| offset >= TRIE_CHILDREN) // incorrect key character
362			{
363			return -1;
364			}
365	sysadm	1.1
366			if (*(key + 1) == '\0')
367			{
368			if (p_dict->flags[offset] != 0)
369			{
370			p_dict->flags[offset] = 0;
371			p_dict->values[offset] = 0;
372			return 1; // Done
373			}
374			else
375			{
376			return 0; // Not exist
377			}
378			}
379			else if (p_dict->p_nodes[offset] == NULL)
380			{
381			return 0; // Not exist
382			}
383			else
384			{
385			p_dict = p_dict->p_nodes[offset];
386			key++;
387			}
388			}
389
390			return -1; // NULL key
391			}
392	sysadm	1.2
393			static void _trie_dict_traverse(TRIE_NODE p_dict, trie_dict_traverse_cb cb, char key, int depth)
394			{
395			if (p_dict == NULL \|\| depth >= TRIE_MAX_KEY_LEN)
396			{
397			return;
398			}
399
400			for (int i = 0; i < TRIE_CHILDREN; i++)
401			{
402			if (p_dict->flags[i] != 0)
403			{
404	sysadm	1.5	key[depth] = (char)i;
405	sysadm	1.3	key[depth + 1] = '\0';
406	sysadm	1.2	(*cb)(key, p_dict->values[i]);
407			}
408
409			if (p_dict->p_nodes[i] != NULL && depth + 1 < TRIE_MAX_KEY_LEN)
410			{
411	sysadm	1.5	key[depth] = (char)i;
412	sysadm	1.2	_trie_dict_traverse(p_dict->p_nodes[i], cb, key, depth + 1);
413			}
414	sysadm	1.5	}
415	sysadm	1.2	}
416
417			void trie_dict_traverse(TRIE_NODE *p_dict, trie_dict_traverse_cb cb)
418			{
419			char key[TRIE_MAX_KEY_LEN + 1];
420	sysadm	1.5
421			if (p_dict == NULL)
422			{
423			return;
424			}
425	sysadm	1.2
426			_trie_dict_traverse(p_dict, cb, key, 0);
427			}
428	sysadm	1.8
429			int trie_dict_used_nodes(void)
430			{
431			return (p_trie_node_pool == NULL ? -1 : p_trie_node_pool->node_count);
432			}
webmaster@leafok.com	ViewVC Help
Powered by ViewVC 1.3.0-beta1