1 /* SPDX-License-Identifier: Apache-2.0 OR MIT */
2 /*
3 * Copyright (c) 2024 Rockchip Electronics Co., Ltd.
4 */
5
6 #define MODULE_TAG "mpp_trie"
7
8 #include "mpp_env.h"
9 #include "mpp_mem.h"
10 #include "mpp_time.h"
11 #include "mpp_debug.h"
12 #include "mpp_common.h"
13
14 #include "mpp_trie.h"
15
16 #define MPP_TRIE_DBG_PAVE (0x00000001)
17 #define MPP_TRIE_DBG_SET (0x00000002)
18 #define MPP_TRIE_DBG_GET (0x00000004)
19 #define MPP_TRIE_DBG_CNT (0x00000008)
20 #define MPP_TRIE_DBG_WALK (0x00000010)
21 #define MPP_TRIE_DBG_LAST (0x00000020)
22 #define MPP_TRIE_DBG_LAST_STEP (0x00000040)
23 #define MPP_TRIE_DBG_LAST_CHECK (0x00000080)
24 #define MPP_TRIE_DBG_IMPORT (0x00000100)
25
26 #define trie_dbg(flag, fmt, ...) _mpp_dbg_f(mpp_trie_debug, flag, fmt, ## __VA_ARGS__)
27 #define trie_dbg_pave(fmt, ...) trie_dbg(MPP_TRIE_DBG_PAVE, fmt, ## __VA_ARGS__)
28 #define trie_dbg_set(fmt, ...) trie_dbg(MPP_TRIE_DBG_SET, fmt, ## __VA_ARGS__)
29 #define trie_dbg_get(fmt, ...) trie_dbg(MPP_TRIE_DBG_GET, fmt, ## __VA_ARGS__)
30 #define trie_dbg_cnt(fmt, ...) trie_dbg(MPP_TRIE_DBG_CNT, fmt, ## __VA_ARGS__)
31 #define trie_dbg_walk(fmt, ...) trie_dbg(MPP_TRIE_DBG_WALK, fmt, ## __VA_ARGS__)
32 #define trie_dbg_last(fmt, ...) trie_dbg(MPP_TRIE_DBG_LAST, fmt, ## __VA_ARGS__)
33
34 #define MPP_TRIE_KEY_LEN (4)
35 #define MPP_TRIE_KEY_MAX (1 << (MPP_TRIE_KEY_LEN))
36 #define MPP_TRIE_INFO_MAX (1 << 12)
37 #define MPP_TRIE_NAME_MAX (1 << 12)
38
39 #define DEFAULT_NODE_COUNT 900
40 #define DEFAULT_INFO_COUNT 80
41 #define INVALID_NODE_ID (-1)
42 #define MPP_TRIE_TAG_LEN_MAX ((sizeof(rk_u64) * 8) / MPP_TRIE_KEY_LEN)
43
44 /* spatial optimized trie tree */
45 typedef struct MppTrieNode_t {
46 /* next - next trie node index */
47 rk_s16 next[MPP_TRIE_KEY_MAX];
48 /* id - payload data offset of current trie node */
49 rk_s32 id;
50 /* idx - trie node index in ascending order */
51 rk_s16 idx;
52 /* prev - previous trie node index */
53 rk_s16 prev;
54
55 /* tag_val - prefix tag */
56 rk_u64 tag_val;
57 /* key - current key value in previous node as next */
58 rk_u16 key;
59 /*
60 * tag len - prefix tag length
61 * zero - normal node with 16 next node
62 * positive - tag node with 64bit prefix tag
63 */
64 rk_s16 tag_len;
65
66 /* next_cnt - valid next node count */
67 rk_u16 next_cnt;
68 } MppTrieNode;
69
70 typedef struct MppTrieImpl_t {
71 char *name;
72 rk_s32 name_len;
73 rk_s32 buf_size;
74
75 rk_s32 node_count;
76 rk_s32 node_used;
77 MppTrieNode *nodes;
78
79 /* info and name record buffer */
80 void *info_buf;
81 rk_s32 info_count;
82 rk_s32 info_buf_size;
83 rk_s32 info_buf_pos;
84 rk_s32 info_name_max;
85 } MppTrieImpl;
86
87 /* work structure for trie traversal */
88 typedef struct MppTrieWalk_t {
89 MppTrieNode *root;
90 rk_u64 tag;
91 rk_u32 len;
92 rk_s32 match;
93 } MppTrieWalk;
94
95 rk_u32 mpp_trie_debug = 0;
96
trie_get_node(MppTrieImpl * trie,rk_s32 prev,rk_u64 key)97 static rk_s32 trie_get_node(MppTrieImpl *trie, rk_s32 prev, rk_u64 key)
98 {
99 MppTrieNode *node;
100 rk_s32 idx;
101
102 if (trie->node_used >= trie->node_count) {
103 rk_s32 old_count = trie->node_count;
104 rk_s32 new_count = old_count * 2;
105 MppTrieNode *new_nodes = mpp_realloc(trie->nodes, MppTrieNode, new_count);
106
107 if (!new_nodes) {
108 mpp_err_f("failed to realloc new nodes %d\n", new_count);
109 return -1;
110 }
111
112 /* NOTE: new memory should be memset to zero */
113 memset(new_nodes + old_count, 0, sizeof(*new_nodes) * old_count);
114
115 trie_dbg_cnt("trie %p enlarge node %p:%d -> %p:%d\n",
116 trie, trie->nodes, trie->node_count, new_nodes, new_count);
117
118 trie->nodes = new_nodes;
119 trie->node_count = new_count;
120 }
121
122 idx = trie->node_used++;
123 node = &trie->nodes[idx];
124 node->idx = idx;
125 node->prev = (prev > 0) ? prev : 0;
126 node->key = key;
127 node->id = INVALID_NODE_ID;
128
129 if (prev >= 0)
130 trie->nodes[prev].next_cnt++;
131
132 trie_dbg_cnt("get node %d\n", idx);
133
134 return idx;
135 }
136
trie_prepare_buf(MppTrieImpl * p,rk_s32 info_size)137 static rk_s32 trie_prepare_buf(MppTrieImpl *p, rk_s32 info_size)
138 {
139 if (p->info_count >= MPP_TRIE_INFO_MAX) {
140 mpp_loge_f("invalid trie info count %d larger than max %d\n",
141 p->info_count, MPP_TRIE_INFO_MAX);
142 return rk_nok;
143 }
144
145 /* check and enlarge info buffer */
146 if (p->info_buf_pos + info_size > p->info_buf_size) {
147 rk_s32 old_size = p->info_buf_size;
148 rk_s32 new_size = old_size * 2;
149 void *ptr = mpp_realloc(p->info_buf, void, new_size);
150
151 if (!ptr) {
152 mpp_loge_f("failed to realloc new info buffer %d\n", new_size);
153 return rk_nok;
154 }
155
156 trie_dbg_cnt("trie %p enlarge info_buf %p:%d -> %p:%d\n",
157 p, p->info_buf, old_size, ptr, new_size);
158
159 p->info_buf = ptr;
160 p->info_buf_size = new_size;
161 }
162
163 return rk_ok;
164 }
165
trie_pave_node(MppTrieImpl * p,const char * name,rk_s32 str_len)166 static rk_s32 trie_pave_node(MppTrieImpl *p, const char *name, rk_s32 str_len)
167 {
168 MppTrieNode *node = NULL;
169 const char *s = name;
170 rk_s32 next = 0;
171 rk_s32 idx = 0;
172 rk_s32 i;
173
174 trie_dbg_pave("trie %p add info %s len %d\n", p, s, str_len);
175
176 for (i = 0; i < str_len && s[i]; i++) {
177 rk_u32 key = s[i];
178 rk_s32 key0 = (key >> 4) & 0xf;
179 rk_s32 key1 = (key >> 0) & 0xf;
180
181 node = p->nodes + idx;
182 next = node->next[key0];
183
184 trie_dbg_pave("trie %p add %s at %2d char %c:%3d:%x:%x node %d -> %d\n",
185 p, name, i, key, key, key0, key1, idx, next);
186
187 if (!next) {
188 next = trie_get_node(p, idx, key0);
189 if (next < 0)
190 return next;
191
192 /* realloc may cause memory address change */
193 node = p->nodes + idx;
194 node->next[key0] = next;
195
196 trie_dbg_pave("trie %p add %s at %2d char %c:%3d node %d -> %d as new key0\n",
197 p, name, i, key, key, node->idx, next);
198 }
199
200 idx = next;
201 node = p->nodes + idx;
202 next = node->next[key1];
203
204 trie_dbg_pave("trie %p add %s at %2d char %c:%3d:%x:%x node %d -> %d as key0\n",
205 p, s, i, key, key, key0, key1, idx, next);
206
207 if (!next) {
208 next = trie_get_node(p, idx, key1);
209 if (next < 0)
210 return next;
211
212 /* realloc may cause memory address change */
213 node = p->nodes + idx;
214 node->next[key1] = next;
215
216 trie_dbg_pave("trie %p add %s at %2d char %c:%3d node %d -> %d as new child\n",
217 p, name, i, key, key, node->idx, next);
218 }
219
220 idx = next;
221
222 trie_dbg_pave("trie %p add %s at %2d char %c:%3d:%x:%x node %d -> %d as key1\n",
223 p, name, i, key, key, key0, key1, idx, next);
224 }
225
226 return idx;
227 }
228
mpp_trie_init(MppTrie * trie,const char * name)229 rk_s32 mpp_trie_init(MppTrie *trie, const char *name)
230 {
231 MppTrieImpl *p;
232 rk_s32 name_len;
233 rk_s32 ret = rk_nok;
234
235 if (!trie || !name) {
236 mpp_loge_f("invalid trie %p name %p\n", trie, name);
237 return ret;
238 }
239
240 mpp_env_get_u32("mpp_trie_debug", &mpp_trie_debug, 0);
241
242 name_len = strnlen(name, MPP_TRIE_NAME_MAX) + 1;
243 p = mpp_calloc_size(MppTrieImpl, sizeof(*p) + name_len);
244 if (!p) {
245 mpp_loge_f("create trie impl %s failed\n", name);
246 goto done;
247 }
248
249 p->name = (char *)(p + 1);
250 p->name_len = name_len;
251 strncpy(p->name, name, name_len);
252
253 p->node_count = DEFAULT_NODE_COUNT;
254 p->nodes = mpp_calloc(MppTrieNode, p->node_count);
255 if (!p->nodes) {
256 mpp_loge_f("create %d nodes failed\n", p->node_count);
257 goto done;
258 }
259
260 p->info_buf_size = 4096;
261 p->info_buf = mpp_calloc(void, p->info_buf_size);
262 if (!p->info_buf) {
263 mpp_loge_f("failed to alloc %d info buffer\n", p->info_buf_size);
264 goto done;
265 }
266
267 /* get node 0 as root node*/
268 trie_get_node(p, -1, 0);
269
270 ret = rk_ok;
271
272 done:
273 if (ret && p) {
274 MPP_FREE(p->info_buf);
275 MPP_FREE(p->nodes);
276 MPP_FREE(p);
277 }
278
279 *trie = p;
280 return ret;
281 }
282
mpp_trie_init_by_root(MppTrie * trie,void * root)283 rk_s32 mpp_trie_init_by_root(MppTrie *trie, void *root)
284 {
285 MppTrieImpl *p;
286 MppTrieInfo *info;
287 rk_s32 i;
288
289 if (!trie || !root) {
290 mpp_loge_f("invalid trie %p root %p\n", trie, root);
291 return rk_nok;
292 }
293
294 *trie = NULL;
295 p = mpp_calloc(MppTrieImpl, 1);
296 if (!p) {
297 mpp_loge_f("create trie impl failed\n");
298 return rk_nok;
299 }
300
301 info = mpp_trie_get_info_from_root(root, "__name__");
302 if (info)
303 p->name = mpp_trie_info_ctx(info);
304
305 info = mpp_trie_get_info_from_root(root, "__node__");
306 if (info)
307 p->node_used = *(rk_u32 *)mpp_trie_info_ctx(info);
308
309 info = mpp_trie_get_info_from_root(root, "__info__");
310 if (info)
311 p->info_count = *(rk_u32 *)mpp_trie_info_ctx(info);
312
313 /* import and update new buffer */
314 p->nodes = (MppTrieNode *)root;
315
316 if (mpp_trie_debug & MPP_TRIE_DBG_IMPORT)
317 mpp_trie_dump(p, "root import");
318
319 info = mpp_trie_get_info_first(p);
320
321 for (i = 0; i < p->info_count; i++) {
322 const char *name = mpp_trie_info_name(info);
323 MppTrieInfo *info_set = info;
324 MppTrieInfo *info_ret = mpp_trie_get_info(p, name);
325
326 info = mpp_trie_get_info_next(p, info);
327
328 if (info_ret && info_set == info_ret && info_ret->index == i)
329 continue;
330
331 mpp_loge_f("trie check on import found mismatch info %s [%d:%p] - [%d:%p]\n",
332 name, i, info_set, info_ret ? info_ret->index : -1, info_ret);
333 return rk_nok;
334 }
335
336 *trie = p;
337
338 return rk_ok;
339 }
340
mpp_trie_deinit(MppTrie trie)341 rk_s32 mpp_trie_deinit(MppTrie trie)
342 {
343 if (trie) {
344 MppTrieImpl *p = (MppTrieImpl *)trie;
345
346 /* NOTE: do not remvoe imported root */
347 if (p->node_count)
348 mpp_free(p->nodes);
349 else
350 p->nodes = NULL;
351
352 MPP_FREE(p->info_buf);
353 MPP_FREE(p);
354 return rk_ok;
355 }
356
357 return rk_nok;
358 }
359
mpp_trie_walk(MppTrieWalk * p,rk_s32 idx,rk_u32 key,rk_u32 keyx,rk_u32 end)360 static rk_s32 mpp_trie_walk(MppTrieWalk *p, rk_s32 idx, rk_u32 key, rk_u32 keyx, rk_u32 end)
361 {
362 MppTrieNode *node = &p->root[idx];
363 char log_buf[128];
364 rk_u32 log_size = sizeof(log_buf) - 1;
365 rk_u32 log_len = 0;
366 rk_u32 log_en = (mpp_trie_debug & MPP_TRIE_DBG_WALK) ? 1 : 0;
367 rk_s32 next = -1;
368
369 if (log_en)
370 log_len += snprintf(log_buf + log_len, log_size - log_len,
371 "node %d:%d key %02x:%x -> ",
372 node->idx, node->id, key, keyx);
373
374 /* check high 4 bits */
375 if (!node->tag_len || p->match == node->idx) {
376 /* not tag or tag has be matched -> normal next switch node */
377 next = node->next[keyx];
378 if (log_en)
379 log_len += snprintf(log_buf + log_len, log_size - log_len,
380 "tag %s -> ",
381 !node->tag_len ? "n/a" : "match");
382 p->tag = 0;
383 p->len = 0;
384 p->match = -1;
385 } else {
386 /* with tag check len to fill or to stop */
387 rk_u64 val_new = (p->tag << 4) | keyx;
388 rk_s32 len_new = p->len + 1;
389
390 if (log_en)
391 log_len += snprintf(log_buf + log_len, log_size - log_len,
392 "tag %0*llx:%d - st %0*llx:%d -> ",
393 node->tag_len, node->tag_val, node->tag_len,
394 node->tag_len, val_new, len_new);
395
396 /* clear old matched node */
397 p->match = -1;
398 if (node->tag_len > len_new && !end) {
399 /* more tag to fill keep current node */
400 p->tag = val_new;
401 p->len = len_new;
402 next = node->idx;
403 if (log_en)
404 log_len += snprintf(log_buf + log_len, log_size - log_len,
405 "fill -> ");
406 } else {
407 /* check tag match with new value */
408 p->tag = 0;
409 p->len = 0;
410
411 if (node->tag_val != val_new) {
412 if (log_en)
413 log_len += snprintf(log_buf + log_len, log_size - log_len,
414 "mismatch -> ");
415 next = INVALID_NODE_ID;
416 } else {
417 if (log_en)
418 log_len += snprintf(log_buf + log_len, log_size - log_len,
419 "match -> ");
420 next = node->idx;
421 p->match = node->idx;
422 }
423 }
424 }
425
426 if (log_en) {
427 snprintf(log_buf + log_len, log_size - log_len, "%d", next);
428 mpp_logi_f("%s\n", log_buf);
429 }
430
431 return next;
432 }
433
mpp_trie_get_node(MppTrieNode * root,const char * name)434 static MppTrieNode *mpp_trie_get_node(MppTrieNode *root, const char *name)
435 {
436 MppTrieNode *ret = NULL;
437 const char *s = name;
438 MppTrieWalk walk;
439 rk_s32 idx = 0;
440
441 if (!root || !name) {
442 mpp_err_f("invalid root %p name %p\n", root, name);
443 return NULL;
444 }
445
446 trie_dbg_get("root %p search %s start\n", root, name);
447
448 walk.root = root;
449 walk.tag = 0;
450 walk.len = 0;
451 walk.match = 0;
452
453 do {
454 char key = *s++;
455 rk_u32 key0 = (key >> 4) & 0xf;
456 rk_u32 key1 = key & 0xf;
457 rk_u32 end = s[0] == '\0';
458
459 idx = mpp_trie_walk(&walk, idx, key, key0, 0);
460 if (idx < 0)
461 break;
462
463 idx = mpp_trie_walk(&walk, idx, key, key1, end);
464 if (idx < 0 || end)
465 break;
466 } while (1);
467
468 ret = (idx >= 0) ? &root[idx] : NULL;
469
470 trie_dbg_get("get %s ret node %d:%d\n", name, idx, ret ? ret->id : INVALID_NODE_ID);
471
472 return ret;
473 }
474
mpp_trie_check(MppTrie trie,const char * log)475 static rk_s32 mpp_trie_check(MppTrie trie, const char *log)
476 {
477 MppTrieImpl *p = (MppTrieImpl *)trie;
478 char *base = p->info_buf;
479 rk_s32 info_size = 0;
480 rk_s32 pos = 0;
481 rk_s32 i;
482
483 for (i = 0; i < p->info_count; i++, pos += info_size) {
484 MppTrieInfo *info = (MppTrieInfo *)(base + pos);
485 const char *name = (const char *)(info + 1);
486 MppTrieNode *node = mpp_trie_get_node(p->nodes, name);
487
488 info_size = sizeof(*info) + info->str_len + info->ctx_len;
489
490 if (node && node->id >= 0 && node->id == pos)
491 continue;
492
493 mpp_loge("trie check on %s found mismatch info %s %d - %d\n",
494 log, name, i, node ? node->id : -1);
495 return rk_nok;
496 }
497
498 return rk_ok;
499 }
500
mpp_trie_last_info(MppTrie trie)501 rk_s32 mpp_trie_last_info(MppTrie trie)
502 {
503 MppTrieImpl *p = (MppTrieImpl *)trie;
504 MppTrieNode *root;
505 MppTrieNode *node;
506 char *buf;
507 rk_s32 node_count;
508 rk_s32 node_valid;
509 rk_s32 nodes_size;
510 rk_s32 len = 0;
511 rk_s32 pos = 0;
512 rk_s32 i;
513 rk_s32 j;
514
515 if (!trie) {
516 mpp_loge_f("invalid NULL trie\n");
517 return rk_nok;
518 }
519
520 /* write trie self entry info */
521 pos = p->info_count + 3;
522 mpp_trie_add_info(trie, "__name__", p->name, p->name_len);
523 mpp_trie_add_info(trie, "__info__", &pos, sizeof(pos));
524 /* NOTE: node count need to be update after shrinking */
525 mpp_trie_add_info(trie, "__node__", &p->node_used, sizeof(p->node_used));
526
527 root = p->nodes;
528 node_count = p->node_used;
529 node_valid = node_count;
530
531 trie_dbg_last("shrink trie node start node %d info %d\n", node_count, p->info_count);
532
533 if (mpp_trie_debug & MPP_TRIE_DBG_LAST_STEP)
534 mpp_trie_dump_f(trie);
535
536 for (i = node_count - 1; i > 0; i--) {
537 MppTrieNode *prev;
538 rk_s32 prev_idx;
539
540 node = &root[i];
541 prev_idx = node->prev;
542 prev = &root[prev_idx];
543
544 if (prev->next_cnt > 1) {
545 trie_dbg_last("node %d:%d prev %d next count %d stop shrinking for multi next\n",
546 i, node->id, prev_idx, prev->next_cnt);
547 continue;
548 }
549
550 if (node->tag_len >= (rk_s16)MPP_TRIE_TAG_LEN_MAX) {
551 trie_dbg_last("node %d:%d tag %d - %016llx stop shrinking for max tag len\n",
552 i, node->id, node->tag_len, node->tag_val);
553 continue;
554 }
555
556 if (prev->id >= 0) {
557 trie_dbg_last("node %d:%d tag %d - %016llx stop shrinking for valid info node\n",
558 i, node->id, node->tag_len, node->tag_val);
559 continue;
560 }
561
562 prev->id = node->id;
563 /* NOTE: do NOT increase tag length on root node */
564 prev->tag_len = node->tag_len + 1;
565 prev->tag_val = ((rk_u64)node->key << (node->tag_len * 4)) | node->tag_val;
566 prev->next_cnt = node->next_cnt;
567 memcpy(prev->next, node->next, sizeof(node->next));
568
569 trie_dbg_last("node %d:%d shrink prev %d key %x tag %016llx -> %016llx\n",
570 i, node->id, prev->idx, prev->key, node->tag_val, prev->tag_val);
571
572 for (j = 0; j < MPP_TRIE_KEY_MAX; j++) {
573 if (!prev->next[j])
574 continue;
575
576 root[prev->next[j]].prev = prev_idx;
577 }
578
579 memset(node, 0, sizeof(*node));
580 node->id = INVALID_NODE_ID;
581 node_valid--;
582 }
583
584 trie_dbg_last("shrink trie node finish count %d -> %d\n", node_count, node_valid);
585
586 if (mpp_trie_debug & MPP_TRIE_DBG_LAST_STEP)
587 mpp_trie_dump_f(trie);
588
589 if (mpp_trie_debug & MPP_TRIE_DBG_LAST_CHECK)
590 mpp_trie_check(trie, "shrink merge tag stage");
591
592 trie_dbg_last("move trie node start to reduce memory %d -> %d\n", node_count, node_valid);
593
594 for (i = 1; i < node_valid; i++) {
595 node = &root[i];
596
597 /* skip valid node */
598 if (node->idx)
599 continue;
600
601 for (j = i; j < node_count; j++) {
602 MppTrieNode *tmp = &root[j];
603 MppTrieNode *prev;
604 rk_s32 k;
605
606 /* skip empty node */
607 if (!tmp->idx)
608 continue;
609
610 trie_dbg_last("move node %d to %d prev %d\n", j, i, tmp->prev);
611
612 prev = &root[tmp->prev];
613
614 /* relink previous node */
615 for (k = 0; k < MPP_TRIE_KEY_MAX; k++) {
616 if (prev->next[k] != tmp->idx)
617 continue;
618
619 prev->next[k] = i;
620 break;
621 }
622
623 memcpy(node, tmp, sizeof(*node));
624 node->idx = i;
625 memset(tmp, 0, sizeof(*tmp));
626
627 /* relink next node */
628 for (k = 0; k < MPP_TRIE_KEY_MAX; k++) {
629 if (!node->next[k])
630 continue;
631
632 root[node->next[k]].prev = i;
633 }
634
635 break;
636 }
637 }
638
639 p->node_used = node_valid;
640
641 trie_dbg_last("move trie node finish used %d\n", p->node_used);
642
643 if (mpp_trie_debug & MPP_TRIE_DBG_LAST_STEP)
644 mpp_trie_dump_f(trie);
645
646 if (mpp_trie_debug & MPP_TRIE_DBG_LAST_CHECK)
647 mpp_trie_check(trie, "shrink move node stage");
648
649 trie_dbg_last("create user buffer start\n");
650
651 nodes_size = sizeof(MppTrieNode) * p->node_used;
652 p->buf_size = nodes_size + p->info_buf_pos;
653 p->buf_size = MPP_ALIGN(p->buf_size, sizeof(void *));
654
655 buf = mpp_calloc(char, p->buf_size);
656 if (!buf) {
657 mpp_loge("failed to alloc trie buffer size %d\n", p->buf_size);
658 return rk_nok;
659 }
660
661 p->nodes = (MppTrieNode *)buf;
662 memcpy(p->nodes, root, nodes_size);
663 pos = nodes_size;
664 len = 0;
665
666 for (i = 0; i < p->info_count; i++) {
667 MppTrieInfo *src = (MppTrieInfo *)(p->info_buf + len);
668 MppTrieInfo *dst = (MppTrieInfo *)(buf + pos);
669 rk_s32 info_size = sizeof(MppTrieInfo) + src->str_len + src->ctx_len;
670 const char *name = (char *)(src + 1);
671
672 node = mpp_trie_get_node(p->nodes, name);
673 node->id = pos;
674
675 memcpy(dst, src, info_size);
676 pos += info_size;
677 len += info_size;
678 }
679
680 MPP_FREE(root);
681 MPP_FREE(p->info_buf);
682
683 /* NOTE: udpate final shrinked node count */
684 {
685 MppTrieInfo *info = mpp_trie_get_info_from_root(p->nodes, "__node__");
686
687 if (info)
688 *(rk_u32 *)mpp_trie_info_ctx(info) = p->node_used;
689 }
690
691 return rk_ok;
692 }
693
mpp_trie_add_info(MppTrie trie,const char * name,void * ctx,rk_u32 ctx_len)694 rk_s32 mpp_trie_add_info(MppTrie trie, const char *name, void *ctx, rk_u32 ctx_len)
695 {
696 MppTrieImpl *p = (MppTrieImpl *)trie;
697 rk_s32 info_size;
698 rk_u32 ctx_real;
699 rk_s32 str_real;
700 rk_s32 str_len;
701 rk_s32 idx;
702
703 if (!p) {
704 mpp_loge_f("invalid trie %p name %s ctx %p\n", p, name, ctx);
705 return rk_nok;
706 }
707
708 if (!name)
709 return mpp_trie_last_info(p);
710
711 str_real = strnlen(name, MPP_TRIE_NAME_MAX) + 1;
712 str_len = MPP_ALIGN(str_real, 4);
713 /* NOTE: align all ctx_len to four bytes */
714 ctx_real = ctx_len;
715 ctx_len = MPP_ALIGN(ctx_real, 4);
716 info_size = sizeof(MppTrieInfo) + str_len + ctx_len;
717
718 if (str_len >= MPP_TRIE_NAME_MAX) {
719 mpp_loge_f("invalid trie name %s len %d larger than max %d\n",
720 name, str_len, MPP_TRIE_NAME_MAX);
721 return rk_nok;
722 }
723
724 if (trie_prepare_buf(p, info_size))
725 return rk_nok;
726
727 idx = trie_pave_node(p, name, str_real);
728 if (idx < 0) {
729 mpp_loge_f("trie %p pave node %s failed\n", p, name);
730 return rk_nok;
731 }
732 if (p->nodes[idx].id != -1) {
733 mpp_loge_f("trie %p add info %s already exist\n", p, name);
734 return rk_nok;
735 }
736
737 p->nodes[idx].id = p->info_buf_pos;
738 if (p->info_name_max < str_real - 1)
739 p->info_name_max = str_real - 1;
740
741 {
742 MppTrieInfo *info = (MppTrieInfo *)(p->info_buf + p->info_buf_pos);
743 char *buf = (char *)(info + 1);
744
745 info->index = p->info_count;
746 info->ctx_len = ctx_len;
747 info->str_len = str_len;
748
749 memcpy(buf, name, str_real);
750 while (str_real < str_len)
751 buf[str_real++] = 0;
752
753 buf += str_len;
754
755 memcpy(buf, ctx, ctx_real);
756 while (ctx_real < ctx_len)
757 buf[ctx_real++] = 0;
758 }
759
760 trie_dbg_set("trie %p add info %d - %s at node %d pos %d ctx %p size %d\n",
761 p, p->info_count, name, idx, p->info_buf_pos, ctx, ctx_len);
762
763 p->info_buf_pos += info_size;
764 p->info_count++;
765
766 return rk_ok;
767 }
768
mpp_trie_get_node_count(MppTrie trie)769 rk_s32 mpp_trie_get_node_count(MppTrie trie)
770 {
771 MppTrieImpl *p = (MppTrieImpl *)trie;
772
773 return (p) ? p->node_used : 0;
774 }
775
mpp_trie_get_info_count(MppTrie trie)776 rk_s32 mpp_trie_get_info_count(MppTrie trie)
777 {
778 MppTrieImpl *p = (MppTrieImpl *)trie;
779
780 return (p) ? p->info_count : 0;
781 }
782
mpp_trie_get_buf_size(MppTrie trie)783 rk_s32 mpp_trie_get_buf_size(MppTrie trie)
784 {
785 MppTrieImpl *p = (MppTrieImpl *)trie;
786
787 return (p) ? p->buf_size : 0;
788 }
789
mpp_trie_get_name_max(MppTrie trie)790 rk_s32 mpp_trie_get_name_max(MppTrie trie)
791 {
792 MppTrieImpl *p = (MppTrieImpl *)trie;
793
794 return (p) ? p->info_name_max : 0;
795 }
796
mpp_trie_get_node_root(MppTrie trie)797 void *mpp_trie_get_node_root(MppTrie trie)
798 {
799 MppTrieImpl *p = (MppTrieImpl *)trie;
800
801 return (p) ? p->nodes : NULL;
802 }
803
mpp_trie_get_info(MppTrie trie,const char * name)804 MppTrieInfo *mpp_trie_get_info(MppTrie trie, const char *name)
805 {
806 MppTrieImpl *p = (MppTrieImpl *)trie;
807 MppTrieNode *node;
808
809 if (!trie || !name) {
810 mpp_err_f("invalid trie %p name %p\n", trie, name);
811 return NULL;
812 }
813
814 node = mpp_trie_get_node(p->nodes, name);
815 if (!node || node->id < 0)
816 return NULL;
817
818 return (MppTrieInfo *)(((char *)p->nodes) + node->id);
819 }
820
mpp_trie_get_info_first(MppTrie trie)821 MppTrieInfo *mpp_trie_get_info_first(MppTrie trie)
822 {
823 MppTrieImpl *p = (MppTrieImpl *)trie;
824
825 return (p) ? (MppTrieInfo *)(((char *)p->nodes) + p->node_used * sizeof(MppTrieNode)) : NULL;
826 }
827
mpp_trie_get_info_next(MppTrie trie,MppTrieInfo * info)828 MppTrieInfo *mpp_trie_get_info_next(MppTrie trie, MppTrieInfo *info)
829 {
830 MppTrieImpl *p = (MppTrieImpl *)trie;
831
832 if (!p || !info || info->index >= p->info_count - 1)
833 return NULL;
834
835 return (MppTrieInfo *)((char *)(info + 1) + info->str_len + info->ctx_len);
836 }
837
mpp_trie_get_info_from_root(void * root,const char * name)838 MppTrieInfo *mpp_trie_get_info_from_root(void *root, const char *name)
839 {
840 MppTrieNode *node;
841
842 if (!root || !name) {
843 mpp_loge_f("invalid root %p name %p\n", root, name);
844 return NULL;
845 }
846
847 mpp_env_get_u32("mpp_trie_debug", &mpp_trie_debug, 0);
848
849 node = mpp_trie_get_node((MppTrieNode *)root, name);
850 if (!node || node->id < 0)
851 return NULL;
852
853 return (MppTrieInfo *)(((char *)root) + node->id);
854 }
855
mpp_trie_dump(MppTrie trie,const char * func)856 void mpp_trie_dump(MppTrie trie, const char *func)
857 {
858 MppTrieImpl *p = (MppTrieImpl *)trie;
859 char *base = p->info_buf ? (char *)p->info_buf : (char *)p->nodes;
860 rk_s32 i;
861 rk_s32 next_cnt[17];
862 rk_s32 tag_len[17];
863
864 memset(next_cnt, 0, sizeof(next_cnt));
865 memset(tag_len, 0, sizeof(tag_len));
866
867 mpp_logi("%s dumping trie %p\n", func, trie);
868 mpp_logi("name %s size %d node %d info %d\n",
869 p->name, p->buf_size, p->node_used, p->info_count);
870
871 for (i = 0; i < p->node_used; i++) {
872 MppTrieNode *node = &p->nodes[i];
873 rk_s32 valid_count = 0;
874 rk_s32 j;
875
876 if (i && !node->idx)
877 continue;
878
879 if (node->id >= 0) {
880 MppTrieInfo *info = (MppTrieInfo *)((char *)base + node->id);
881
882 /* check before and after last info */
883 if (node->id < (rk_s32)(p->node_used * sizeof(MppTrieNode)))
884 mpp_logi("node %d key %x info %d - %s\n", node->idx, node->key, node->id,
885 mpp_trie_info_name(info));
886 else
887 mpp_logi("node %d key %x info %d - %s\n", node->idx, node->key, node->id,
888 mpp_trie_info_name(info));
889 } else
890 mpp_logi("node %d key %x\n", node->idx, node->key);
891
892 if (node->tag_len)
893 mpp_logi(" prev %d count %d tag %d - %llx\n", node->prev, node->next_cnt, node->tag_len, node->tag_val);
894 else
895 mpp_logi(" prev %d count %d\n", node->prev, node->next_cnt);
896
897 for (j = 0; j < MPP_TRIE_KEY_MAX; j++) {
898 if (node->next[j] > 0) {
899 mpp_logi(" next %d:%d -> %d\n", valid_count, j, node->next[j]);
900 valid_count++;
901 }
902 }
903
904 next_cnt[valid_count]++;
905 tag_len[node->tag_len]++;
906 }
907
908 mpp_logi("node | next | tag | used %d\n", p->node_used);
909
910 for (i = 0; i < 17; i++) {
911 if (next_cnt[i] || tag_len[i])
912 mpp_logi("%2d | %4d | %4d |\n", i, next_cnt[i], tag_len[i]);
913 }
914
915 mpp_logi("%s dumping node end\n", func, p->node_used);
916 }
917
mpp_trie_timing_test(MppTrie trie)918 void mpp_trie_timing_test(MppTrie trie)
919 {
920 MppTrieInfo *root = mpp_trie_get_info_first(trie);
921 MppTrieInfo *info = root;
922 rk_s64 sum = 0;
923 rk_s32 loop = 0;
924
925 do {
926 rk_s64 start, end;
927
928 start = mpp_time();
929 mpp_trie_get_info(trie, mpp_trie_info_name(info));
930 end = mpp_time();
931
932 info = mpp_trie_get_info_next(trie, info);
933 sum += end - start;
934 loop++;
935 } while (info);
936
937 mpp_logi("trie access %d info %lld us averga %lld us\n",
938 loop, sum, sum / loop);
939 }
940