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>

inline int char_to_offset(char c)
{
        return (unsigned char)c;
}

char offset_to_char(int i)
{
        if (i > 255)
        {
                return '\0';
        }

        return (char)(i % 256 - 256);
}

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->flags[i] = 0;
        }

        free(p_dict);
        p_dict = NULL;
}

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

        while (key != NULL && *key != '\0')
        {
                offset = char_to_offset(*key);
                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;

        while (key != NULL && *key != '\0')
        {
                offset = char_to_offset(*key);
                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] = offset_to_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] = offset_to_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];
        key[0] = '\0';

        _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	sysadm	1.3	inline int char_to_offset(char c)
22	sysadm	1.1	{
23	sysadm	1.3	return (unsigned char)c;
24	sysadm	1.1	}
25
26	sysadm	1.2	char offset_to_char(int i)
27			{
28	sysadm	1.3	if (i > 255)
29	sysadm	1.2	{
30			return '\0';
31			}
32
33	sysadm	1.3	return (char)(i % 256 - 256);
34	sysadm	1.2	}
35
36	sysadm	1.1	TRIE_NODE *trie_dict_create(void)
37			{
38			TRIE_NODE *p_dict;
39
40			p_dict = (TRIE_NODE *)calloc(1, sizeof(TRIE_NODE));
41
42			return p_dict;
43			}
44
45			void trie_dict_destroy(TRIE_NODE *p_dict)
46			{
47			if (p_dict == NULL)
48			{
49			return;
50			}
51
52			for (int i = 0; i < TRIE_CHILDREN; i++)
53			{
54			if (p_dict->p_nodes[i] != NULL)
55			{
56			trie_dict_destroy(p_dict->p_nodes[i]);
57			}
58	sysadm	1.3
59			p_dict->flags[i] = 0;
60	sysadm	1.1	}
61
62			free(p_dict);
63	sysadm	1.4	p_dict = NULL;
64	sysadm	1.1	}
65
66			int trie_dict_set(TRIE_NODE p_dict, const char key, int64_t value)
67			{
68			int offset;
69
70			while (key != NULL && *key != '\0')
71			{
72			offset = char_to_offset(*key);
73	sysadm	1.3	if (offset < 0 \|\| offset >= TRIE_CHILDREN) // incorrect key character
74			{
75			return -1;
76			}
77	sysadm	1.1
78			if (*(key + 1) == '\0')
79			{
80			if (p_dict->flags[offset] == 0 \|\| p_dict->values[offset] != value)
81			{
82			p_dict->values[offset] = value;
83			p_dict->flags[offset] = 1;
84			return 1; // Set to new value
85			}
86			return 0; // Unchanged
87			}
88			else
89			{
90			if (p_dict->p_nodes[offset] == NULL)
91			{
92			if ((p_dict->p_nodes[offset] = trie_dict_create()) == NULL)
93			{
94			return -2; // OOM
95			}
96			}
97			p_dict = p_dict->p_nodes[offset];
98			key++;
99			}
100			}
101
102			return -1; // NULL key
103			}
104
105			int trie_dict_get(TRIE_NODE p_dict, const char key, int64_t *p_value)
106			{
107			int offset;
108
109			while (key != NULL && *key != '\0')
110			{
111			offset = char_to_offset(*key);
112	sysadm	1.3	if (offset < 0 \|\| offset >= TRIE_CHILDREN) // incorrect key character
113			{
114			return -1;
115			}
116	sysadm	1.1
117			if (*(key + 1) == '\0')
118			{
119			if (p_dict->flags[offset] != 0)
120			{
121			*p_value = p_dict->values[offset];
122			return 1; // Found
123			}
124			else
125			{
126			return 0; // Not exist
127			}
128			}
129			else if (p_dict->p_nodes[offset] == NULL)
130			{
131			return 0; // Not exist
132			}
133			else
134			{
135			p_dict = p_dict->p_nodes[offset];
136			key++;
137			}
138			}
139
140			return -1; // NULL key
141			}
142
143			int trie_dict_del(TRIE_NODE p_dict, const char key)
144			{
145			int offset;
146
147			while (key != NULL && *key != '\0')
148			{
149			offset = char_to_offset(*key);
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.3	key[depth] = offset_to_char(i);
194			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.3	key[depth] = offset_to_char(i);
201	sysadm	1.2	_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	sysadm	1.3	key[0] = '\0';
210	sysadm	1.2
211			_trie_dict_traverse(p_dict, cb, key, 0);
212			}
webmaster@leafok.com	ViewVC Help
Powered by ViewVC 1.3.0-beta1