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	/***************************************************************************
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	#include <stdio.h>
20
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	p_dict->p_nodes[i] = NULL;
43	}
44
45	p_dict->flags[i] = 0;
46	}
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	if (p_dict == NULL)
56	{
57	return -1;
58	}
59
60	while (key != NULL && *key != '\0')
61	{
62	offset = (256 + *key) % 256;
63	if (offset < 0 \|\| offset >= TRIE_CHILDREN) // incorrect key character
64	{
65	return -1;
66	}
67
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	if (p_dict == NULL)
100	{
101	return -1;
102	}
103
104	while (key != NULL && *key != '\0')
105	{
106	offset = (256 + *key) % 256;
107	if (offset < 0 \|\| offset >= TRIE_CHILDREN) // incorrect key character
108	{
109	return -1;
110	}
111
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	if (p_dict == NULL)
143	{
144	return -1;
145	}
146
147	while (key != NULL && *key != '\0')
148	{
149	offset = (256 + *key) % 256;
150	if (offset < 0 \|\| offset >= TRIE_CHILDREN) // incorrect key character
151	{
152	return -1;
153	}
154
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
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	key[depth] = (char)i;
194	key[depth + 1] = '\0';
195	(*cb)(key, p_dict->values[i]);
196	}
197
198	if (p_dict->p_nodes[i] != NULL && depth + 1 < TRIE_MAX_KEY_LEN)
199	{
200	key[depth] = (char)i;
201	_trie_dict_traverse(p_dict->p_nodes[i], cb, key, depth + 1);
202	}
203	}
204	}
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
210	if (p_dict == NULL)
211	{
212	return;
213	}
214
215	_trie_dict_traverse(p_dict, cb, key, 0);
216	}
webmaster@leafok.com	ViewVC Help
Powered by ViewVC 1.3.0-beta1