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

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
}
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			TRIE_NODE *trie_dict_create(void)
43			{
44			TRIE_NODE *p_dict;
45
46			p_dict = (TRIE_NODE *)calloc(1, sizeof(TRIE_NODE));
47
48			return p_dict;
49			}
50
51			void trie_dict_destroy(TRIE_NODE *p_dict)
52			{
53			if (p_dict == NULL)
54			{
55			return;
56			}
57
58			for (int i = 0; i < TRIE_CHILDREN; i++)
59			{
60			if (p_dict->p_nodes[i] != NULL)
61			{
62			trie_dict_destroy(p_dict->p_nodes[i]);
63			p_dict->p_nodes[i] = NULL;
64			}
65			}
66
67			free(p_dict);
68			}
69
70			int trie_dict_set(TRIE_NODE p_dict, const char key, int64_t value)
71			{
72			int offset;
73
74			while (key != NULL && *key != '\0')
75			{
76			offset = char_to_offset(*key);
77
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
113			if (*(key + 1) == '\0')
114			{
115			if (p_dict->flags[offset] != 0)
116			{
117			*p_value = p_dict->values[offset];
118			return 1; // Found
119			}
120			else
121			{
122			return 0; // Not exist
123			}
124			}
125			else if (p_dict->p_nodes[offset] == NULL)
126			{
127			return 0; // Not exist
128			}
129			else
130			{
131			p_dict = p_dict->p_nodes[offset];
132			key++;
133			}
134			}
135
136			return -1; // NULL key
137			}
138
139			int trie_dict_del(TRIE_NODE p_dict, const char key)
140			{
141			int offset;
142
143			while (key != NULL && *key != '\0')
144			{
145			offset = char_to_offset(*key);
146
147			if (*(key + 1) == '\0')
148			{
149			if (p_dict->flags[offset] != 0)
150			{
151			p_dict->flags[offset] = 0;
152			p_dict->values[offset] = 0;
153			return 1; // Done
154			}
155			else
156			{
157			return 0; // Not exist
158			}
159			}
160			else if (p_dict->p_nodes[offset] == NULL)
161			{
162			return 0; // Not exist
163			}
164			else
165			{
166			p_dict = p_dict->p_nodes[offset];
167			key++;
168			}
169			}
170
171			return -1; // NULL key
172			}
webmaster@leafok.com	ViewVC Help
Powered by ViewVC 1.3.0-beta1