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 <stdlib.h>

int char_to_offset(char c)
{
        if (c >= 'A' && c <= 'Z')
        {
                return (c - 'A');
        }
        else if (c >= 'a' && c <= 'z')
        {
                return (c - 'a' + 26);
        }
        else if (c >= '0' && c <= '9')
        {
                return (c - '0' + 52); // 26 * 2
        }
        else if (c == '_')
        {
                return 62; // (26 * 2 + 10)
        }

        return -1;
}

char offset_to_char(int i)
{
        if (i < 0)
        {
                return '\0';
        }
        else if (i < 26)
        {
                return (char)('A' + i);
        }
        else if (i < 52)
        {
                return (char)('a' + (i - 26));
        }
        else if (i < 62)
        {
                return (char)('0' + (i - 52));
        }
        else if (i == 62)
        {
                return '_';
        }

        return '\0';
}

TRIE_NODE *trie_dict_create(void)
{
        TRIE_NODE *p_dict;

        p_dict = (TRIE_NODE *)calloc(1, sizeof(TRIE_NODE));

        return p_dict;
}

void trie_dict_destroy(TRIE_NODE *p_dict)
{
        if (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]);
                        p_dict->p_nodes[i] = NULL;
                }
        }

        free(p_dict);
}

int trie_dict_set(TRIE_NODE *p_dict, const char *key, int64_t value)
{
        int offset;

        while (key != NULL && *key != '\0')
        {
                offset = char_to_offset(*key);

                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;

        while (key != NULL && *key != '\0')
        {
                offset = char_to_offset(*key);

                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;

        while (key != NULL && *key != '\0')
        {
                offset = char_to_offset(*key);

                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++)
        {
                key[depth] = offset_to_char(i);
                key[depth + 1] = '\0';

                if (p_dict->flags[i] != 0)
                {
                        (*cb)(key, p_dict->values[i]);
                }

                if (p_dict->p_nodes[i] != NULL && depth + 1 < TRIE_MAX_KEY_LEN)
                {
                        _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];

        _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			#include <stdlib.h>
19
20			int char_to_offset(char c)
21			{
22			if (c >= 'A' && c <= 'Z')
23			{
24			return (c - 'A');
25			}
26			else if (c >= 'a' && c <= 'z')
27			{
28			return (c - 'a' + 26);
29			}
30			else if (c >= '0' && c <= '9')
31			{
32			return (c - '0' + 52); // 26 * 2
33			}
34			else if (c == '_')
35			{
36			return 62; // (26 * 2 + 10)
37			}
38
39			return -1;
40			}
41
42	sysadm	1.2	char offset_to_char(int i)
43			{
44			if (i < 0)
45			{
46			return '\0';
47			}
48			else if (i < 26)
49			{
50			return (char)('A' + i);
51			}
52			else if (i < 52)
53			{
54			return (char)('a' + (i - 26));
55			}
56			else if (i < 62)
57			{
58			return (char)('0' + (i - 52));
59			}
60			else if (i == 62)
61			{
62			return '_';
63			}
64
65			return '\0';
66			}
67
68	sysadm	1.1	TRIE_NODE *trie_dict_create(void)
69			{
70			TRIE_NODE *p_dict;
71
72			p_dict = (TRIE_NODE *)calloc(1, sizeof(TRIE_NODE));
73
74			return p_dict;
75			}
76
77			void trie_dict_destroy(TRIE_NODE *p_dict)
78			{
79			if (p_dict == NULL)
80			{
81			return;
82			}
83
84			for (int i = 0; i < TRIE_CHILDREN; i++)
85			{
86			if (p_dict->p_nodes[i] != NULL)
87			{
88			trie_dict_destroy(p_dict->p_nodes[i]);
89			p_dict->p_nodes[i] = NULL;
90			}
91			}
92
93			free(p_dict);
94			}
95
96			int trie_dict_set(TRIE_NODE p_dict, const char key, int64_t value)
97			{
98			int offset;
99
100			while (key != NULL && *key != '\0')
101			{
102			offset = char_to_offset(*key);
103
104			if (*(key + 1) == '\0')
105			{
106			if (p_dict->flags[offset] == 0 \|\| p_dict->values[offset] != value)
107			{
108			p_dict->values[offset] = value;
109			p_dict->flags[offset] = 1;
110			return 1; // Set to new value
111			}
112			return 0; // Unchanged
113			}
114			else
115			{
116			if (p_dict->p_nodes[offset] == NULL)
117			{
118			if ((p_dict->p_nodes[offset] = trie_dict_create()) == NULL)
119			{
120			return -2; // OOM
121			}
122			}
123			p_dict = p_dict->p_nodes[offset];
124			key++;
125			}
126			}
127
128			return -1; // NULL key
129			}
130
131			int trie_dict_get(TRIE_NODE p_dict, const char key, int64_t *p_value)
132			{
133			int offset;
134
135			while (key != NULL && *key != '\0')
136			{
137			offset = char_to_offset(*key);
138
139			if (*(key + 1) == '\0')
140			{
141			if (p_dict->flags[offset] != 0)
142			{
143			*p_value = p_dict->values[offset];
144			return 1; // Found
145			}
146			else
147			{
148			return 0; // Not exist
149			}
150			}
151			else if (p_dict->p_nodes[offset] == NULL)
152			{
153			return 0; // Not exist
154			}
155			else
156			{
157			p_dict = p_dict->p_nodes[offset];
158			key++;
159			}
160			}
161
162			return -1; // NULL key
163			}
164
165			int trie_dict_del(TRIE_NODE p_dict, const char key)
166			{
167			int offset;
168
169			while (key != NULL && *key != '\0')
170			{
171			offset = char_to_offset(*key);
172
173			if (*(key + 1) == '\0')
174			{
175			if (p_dict->flags[offset] != 0)
176			{
177			p_dict->flags[offset] = 0;
178			p_dict->values[offset] = 0;
179			return 1; // Done
180			}
181			else
182			{
183			return 0; // Not exist
184			}
185			}
186			else if (p_dict->p_nodes[offset] == NULL)
187			{
188			return 0; // Not exist
189			}
190			else
191			{
192			p_dict = p_dict->p_nodes[offset];
193			key++;
194			}
195			}
196
197			return -1; // NULL key
198			}
199	sysadm	1.2
200			static void _trie_dict_traverse(TRIE_NODE p_dict, trie_dict_traverse_cb cb, char key, int depth)
201			{
202			if (p_dict == NULL \|\| depth >= TRIE_MAX_KEY_LEN)
203			{
204			return;
205			}
206
207			for (int i = 0; i < TRIE_CHILDREN; i++)
208			{
209			key[depth] = offset_to_char(i);
210			key[depth + 1] = '\0';
211
212			if (p_dict->flags[i] != 0)
213			{
214			(*cb)(key, p_dict->values[i]);
215			}
216
217			if (p_dict->p_nodes[i] != NULL && depth + 1 < TRIE_MAX_KEY_LEN)
218			{
219			_trie_dict_traverse(p_dict->p_nodes[i], cb, key, depth + 1);
220			}
221			}
222			}
223
224			void trie_dict_traverse(TRIE_NODE *p_dict, trie_dict_traverse_cb cb)
225			{
226			char key[TRIE_MAX_KEY_LEN + 1];
227
228			_trie_dict_traverse(p_dict, cb, key, 0);
229			}
webmaster@leafok.com	ViewVC Help
Powered by ViewVC 1.3.0-beta1