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>
#include <stdio.h>

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

                p_dict->flags[i] = 0;
        }

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