1 /*
2 * Copyright 2015 Rockchip Electronics Co. LTD
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #define MODULE_TAG "mpp_trie"
18
19 #include <string.h>
20
21 #include "mpp_env.h"
22 #include "mpp_log.h"
23 #include "mpp_mem.h"
24 #include "mpp_time.h"
25 #include "mpp_common.h"
26
27 #include "mpp_trie.h"
28
29 #define MPP_TRIE_DBG_FUNC (0x00000001)
30 #define MPP_TRIE_DBG_SET (0x00000002)
31 #define MPP_TRIE_DBG_GET (0x00000004)
32 #define MPP_TRIE_DBG_CNT (0x00000008)
33
34 #define trie_dbg(flag, fmt, ...) _mpp_dbg_f(mpp_trie_debug, flag, fmt, ## __VA_ARGS__)
35 #define trie_dbg_func(fmt, ...) trie_dbg(MPP_TRIE_DBG_FUNC, fmt, ## __VA_ARGS__)
36 #define trie_dbg_set(fmt, ...) trie_dbg(MPP_TRIE_DBG_SET, fmt, ## __VA_ARGS__)
37 #define trie_dbg_get(fmt, ...) trie_dbg(MPP_TRIE_DBG_GET, fmt, ## __VA_ARGS__)
38 #define trie_dbg_cnt(fmt, ...) trie_dbg(MPP_TRIE_DBG_CNT, fmt, ## __VA_ARGS__)
39
40 #define DEFAULT_NODE_COUNT 900
41 #define DEFAULT_INFO_COUNT 80
42 #define INVALID_NODE_ID (-1)
43
44 typedef struct MppAcImpl_t {
45 RK_S32 info_count;
46 RK_S32 info_used;
47 const char ***info;
48 RK_S32 node_count;
49 RK_S32 node_used;
50 MppTrieNode *nodes;
51 } MppTrieImpl;
52
53 RK_U32 mpp_trie_debug = 0;
54
trie_get_node(MppTrieImpl * trie)55 static RK_S32 trie_get_node(MppTrieImpl *trie)
56 {
57 if (trie->node_used >= trie->node_count) {
58 RK_S32 old_count = trie->node_count;
59 RK_S32 new_count = old_count * 2;
60 MppTrieNode *new_nodes = mpp_realloc(trie->nodes, MppTrieNode, new_count);
61
62 if (NULL == new_nodes) {
63 mpp_err_f("failed to realloc new nodes %d\n", new_count);
64 return -1;
65 }
66
67 /* NOTE: new memory should be memset to zero */
68 memset(new_nodes + old_count, 0, sizeof(*new_nodes) * old_count);
69
70 trie_dbg_cnt("trie %p enlarge node %p:%d -> %p:%d\n",
71 trie, trie->nodes, trie->node_count, new_nodes, new_count);
72
73 trie->nodes = new_nodes;
74 trie->node_count = new_count;
75 }
76
77 RK_S32 idx = trie->node_used++;
78 MppTrieNode *n = &trie->nodes[idx];
79
80 n->idx = idx;
81 n->id = INVALID_NODE_ID;
82
83 trie_dbg_cnt("get node %d\n", idx);
84
85 return idx;
86 }
87
mpp_trie_init(MppTrie * trie,RK_S32 node_count,RK_S32 info_count)88 MPP_RET mpp_trie_init(MppTrie *trie, RK_S32 node_count, RK_S32 info_count)
89 {
90 if (NULL == trie) {
91 mpp_err_f("invalid NULL input trie automation\n");
92 return MPP_ERR_NULL_PTR;
93 }
94
95 mpp_env_get_u32("mpp_trie_debug", &mpp_trie_debug, 0);
96
97 MPP_RET ret = MPP_ERR_NOMEM;
98 MppTrieImpl *p = mpp_calloc(MppTrieImpl, 1);
99 if (NULL == p) {
100 mpp_err_f("create trie impl failed\n");
101 goto DONE;
102 }
103
104 p->node_count = node_count ? node_count : DEFAULT_NODE_COUNT;
105 if (p->node_count) {
106 p->nodes = mpp_calloc(MppTrieNode, p->node_count);
107 if (NULL == p->nodes) {
108 mpp_err_f("create %d nodes failed\n", p->node_count);
109 goto DONE;
110 }
111 }
112
113 p->info_count = info_count ? info_count : DEFAULT_INFO_COUNT;
114 p->info = mpp_calloc(const char **, p->info_count);
115 if (NULL == p->info) {
116 mpp_err_f("failed to alloc %d storage\n", p->info_count);
117 goto DONE;
118 }
119
120 /* get node 0 as root node*/
121 trie_get_node(p);
122 ret = MPP_OK;
123
124 DONE:
125 if (ret && p) {
126 MPP_FREE(p->info);
127 MPP_FREE(p->nodes);
128 MPP_FREE(p);
129 }
130
131 *trie = p;
132 return ret;
133 }
134
mpp_trie_deinit(MppTrie trie)135 MPP_RET mpp_trie_deinit(MppTrie trie)
136 {
137 if (NULL == trie) {
138 mpp_err_f("invalid NULL input trie automation\n");
139 return MPP_ERR_NULL_PTR;
140 }
141
142 MppTrieImpl *p = (MppTrieImpl *)trie;
143
144 MPP_FREE(p->nodes);
145 MPP_FREE(p->info);
146 MPP_FREE(p);
147
148 return MPP_OK;
149 }
150
mpp_trie_add_info(MppTrie trie,const char ** info)151 MPP_RET mpp_trie_add_info(MppTrie trie, const char **info)
152 {
153 if (NULL == trie || NULL == info) {
154 mpp_err_f("invalid trie %p info %p\n", trie, info);
155 return MPP_ERR_NULL_PTR;
156 }
157
158 MppTrieImpl *p = (MppTrieImpl *)trie;
159
160 /* create */
161 if (p->info_used >= p->info_count) {
162 RK_S32 new_count = p->info_count * 2;
163 const char ***ptr = mpp_realloc(p->info, const char **, new_count);
164 if (NULL == ptr) {
165 mpp_err_f("failed to realloc new action %d\n", new_count);
166 return MPP_ERR_MALLOC;
167 }
168
169 trie_dbg_cnt("trie %p enlarge info %p:%d -> %p:%d\n",
170 trie, p->info, p->info_count, ptr, new_count);
171
172 p->info = ptr;
173 p->info_count = new_count;
174 }
175
176 MppTrieNode *node = NULL;
177 const char *s = *info;
178 RK_S32 len = strnlen(s, SZ_1K);
179 RK_S32 next = 0;
180 RK_S32 idx = 0;
181 RK_S32 i;
182
183 trie_dbg_set("trie %p add info %s len %d\n", trie, s, len);
184
185 for (i = 0; i < len && s[i]; i++) {
186 RK_U32 key = s[i];
187 RK_S32 key0 = (key >> 4) & 0xf;
188 RK_S32 key1 = (key >> 0) & 0xf;
189
190 node = p->nodes + idx;
191 next = node->next[key0];
192
193 trie_dbg_set("trie %p add %s at %2d char %c:%3d:%x:%x node %d -> %d\n",
194 trie, s, i, key, key, key0, key1, idx, next);
195
196 if (!next) {
197 next = trie_get_node(p);
198 /* realloc may cause memory address change */
199 node = p->nodes + idx;
200 node->next[key0] = next;
201
202 trie_dbg_set("trie %p add %s at %2d char %c:%3d node %d -> %d as new key0\n",
203 trie, s, i, key, key, node->idx, next);
204 }
205
206 idx = next;
207 node = p->nodes + idx;
208 next = node->next[key1];
209
210 trie_dbg_set("trie %p add %s at %2d char %c:%3d:%x:%x node %d -> %d as key0\n",
211 trie, s, i, key, key, key0, key1, idx, next);
212
213 if (!next) {
214 next = trie_get_node(p);
215 /* realloc may cause memory address change */
216 node = p->nodes + idx;
217 node->next[key1] = next;
218
219 trie_dbg_set("trie %p add %s at %2d char %c:%3d node %d -> %d as new child\n",
220 trie, s, i, key, key, node->idx, next);
221 }
222
223 idx = next;
224
225 trie_dbg_set("trie %p add %s at %2d char %c:%3d:%x:%x node %d -> %d as key1\n",
226 trie, s, i, key, key, key0, key1, idx, next);
227 }
228
229 RK_S32 act_id = p->info_used++;
230 p->nodes[idx].id = act_id;
231 p->info[act_id] = info;
232
233 trie_dbg_set("trie %p add %d info %s at node %d pos %d action %p done\n",
234 trie, i, s, idx, act_id, info);
235
236 return MPP_OK;
237 }
238
mpp_trie_get_node_count(MppTrie trie)239 RK_S32 mpp_trie_get_node_count(MppTrie trie)
240 {
241 if (NULL == trie) {
242 mpp_err_f("invalid NULL trie\n");
243 return 0;
244 }
245
246 MppTrieImpl *p = (MppTrieImpl *)trie;
247 return p->node_used;
248 }
249
mpp_trie_get_info_count(MppTrie trie)250 RK_S32 mpp_trie_get_info_count(MppTrie trie)
251 {
252 if (NULL == trie) {
253 mpp_err_f("invalid NULL trie\n");
254 return 0;
255 }
256
257 MppTrieImpl *p = (MppTrieImpl *)trie;
258 return p->info_used;
259 }
260
mpp_trie_get_node(MppTrieNode * root,const char * name)261 MppTrieNode *mpp_trie_get_node(MppTrieNode *root, const char *name)
262 {
263 MppTrieNode *node = root;
264 const char *s = name;
265 RK_S32 len = 0;
266 RK_S16 idx = 0;
267 RK_S32 i;
268
269 if (NULL == root || NULL == name) {
270 mpp_err_f("invalid root %p name %p\n", root, name);
271 return NULL;
272 }
273
274 len = strlen(name);
275
276 trie_dbg_get("root %p search %s len %2d start\n", root, name, len);
277
278 for (i = 0; i < len; i++, s++) {
279 idx = node->next[(s[0] >> 4) & 0xf];
280 if (!idx)
281 break;
282
283 node = &root[idx];
284
285 idx = node->next[(s[0] >> 0) & 0xf];
286 if (!idx)
287 break;
288
289 node = &root[idx];
290 }
291
292 trie_dbg_get("idx %d node %p id %d\n", idx, node, node->id);
293
294 if (!idx || node->id == INVALID_NODE_ID)
295 node = NULL;
296
297 return node;
298 }
299
mpp_trie_node_root(MppTrie trie)300 MppTrieNode *mpp_trie_node_root(MppTrie trie)
301 {
302 if (NULL == trie) {
303 mpp_err_f("invalid NULL trie\n");
304 return NULL;
305 }
306
307 MppTrieImpl *p = (MppTrieImpl *)trie;
308 return p->nodes;
309 }
310
mpp_trie_get_info(MppTrie trie,const char * name)311 const char **mpp_trie_get_info(MppTrie trie, const char *name)
312 {
313 MppTrieImpl *p = (MppTrieImpl *)trie;
314 MppTrieNode *node;
315
316 if (NULL == trie || NULL == name) {
317 mpp_err_f("invalid trie %p name %p\n", trie, name);
318 return NULL;
319 }
320
321 node = mpp_trie_get_node(p->nodes, name);
322
323 return (node && node->id >= 0) ? p->info[node->id] : NULL;
324 }
325