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	/***************************************************************************
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