Public_Skunkworks/singe
Public_Skunkworks/singe
1
0
Fork 0
Code Issues 7 Pull requests Projects Releases Packages Wiki Activity Actions
singe/thirdparty/rockchip-mpp/mpp/base/mpp_trie.c
Scott Duensing e3ae4eec95 More ARM support.
2026-09-10 20:17:28 -05:00

1246 lines
34 KiB
C
Raw Permalink Blame History

/* SPDX-License-Identifier: Apache-2.0 OR MIT */
/*
* Copyright (c) 2024 Rockchip Electronics Co., Ltd.
*/
#define MODULE_TAG "mpp_trie"
#include "mpp_env.h"
#include "mpp_mem.h"
#include "mpp_time.h"
#include "mpp_debug.h"
#include "mpp_common.h"
#include "mpp_trie.h"
#define MPP_TRIE_DBG_PAVE (0x00000001)
#define MPP_TRIE_DBG_SET (0x00000002)
#define MPP_TRIE_DBG_GET (0x00000004)
#define MPP_TRIE_DBG_CNT (0x00000008)
#define MPP_TRIE_DBG_WALK (0x00000010)
#define MPP_TRIE_DBG_LAST (0x00000020)
#define MPP_TRIE_DBG_LAST_STEP (0x00000040)
#define MPP_TRIE_DBG_LAST_CHECK (0x00000080)
#define MPP_TRIE_DBG_IMPORT (0x00000100)
#define trie_dbg(flag, fmt, ...) mpp_dbg_f(mpp_trie_debug, flag, fmt, ## __VA_ARGS__)
#define trie_dbg_pave(fmt, ...) trie_dbg(MPP_TRIE_DBG_PAVE, fmt, ## __VA_ARGS__)
#define trie_dbg_set(fmt, ...) trie_dbg(MPP_TRIE_DBG_SET, fmt, ## __VA_ARGS__)
#define trie_dbg_get(fmt, ...) trie_dbg(MPP_TRIE_DBG_GET, fmt, ## __VA_ARGS__)
#define trie_dbg_cnt(fmt, ...) trie_dbg(MPP_TRIE_DBG_CNT, fmt, ## __VA_ARGS__)
#define trie_dbg_walk(fmt, ...) trie_dbg(MPP_TRIE_DBG_WALK, fmt, ## __VA_ARGS__)
#define trie_dbg_last(fmt, ...) trie_dbg(MPP_TRIE_DBG_LAST, fmt, ## __VA_ARGS__)
#define MPP_TRIE_KEY_LEN (4)
#define MPP_TRIE_KEY_MAX (1 << (MPP_TRIE_KEY_LEN))
#define MPP_TRIE_INFO_MAX (1 << 12)
#define MPP_TRIE_NAME_MAX (1 << 12)
#define DEFAULT_NODE_COUNT 900
#define DEFAULT_INFO_COUNT 80
#define INVALID_NODE_ID (-1)
#define MPP_TRIE_TAG_LEN_MAX ((sizeof(rk_u64) * 8) / MPP_TRIE_KEY_LEN)
/* spatial optimized trie tree */
typedef struct MppTrieNode_t {
/* next - next trie node index */
rk_s16 next[MPP_TRIE_KEY_MAX];
/* id - payload data offset of current trie node */
rk_s32 id;
/* idx - trie node index in ascending order */
rk_s16 idx;
/* prev - previous trie node index */
rk_s16 prev;
/* tag_val - prefix tag */
rk_u64 tag_val;
/* key - current key value in previous node as next */
rk_u16 key;
/*
* tag len - prefix tag length
* zero - normal node with 16 next node
* positive - tag node with 64bit prefix tag
*/
rk_s16 tag_len;
/* next_cnt - valid next node count */
/* use union for array index support */
union {
rk_u16 next_cnt;
struct {
rk_u16 count : 14; /* array element count */
rk_u16 sub_root : 1; /* subtree root flag (array) */
rk_u16 is_branch : 1; /* pure routing / branch node flag */
};
};
} MppTrieNode;
typedef struct MppTrieImpl_t {
char *name;
rk_s32 name_len;
rk_s32 buf_size;
rk_s32 node_count;
rk_s32 node_used;
MppTrieNode *nodes;
/* info and name record buffer */
void *info_buf;
rk_s32 info_count;
rk_s32 info_buf_size;
rk_s32 info_buf_pos;
rk_s32 info_name_max;
} MppTrieImpl;
/* work structure for trie traversal */
typedef struct MppTrieWalk_t {
MppTrieNode *root;
rk_u64 tag;
rk_u32 len;
rk_s32 match;
} MppTrieWalk;
static rk_u32 mpp_trie_debug = 0;
static rk_s32 trie_get_node(MppTrieImpl *trie, rk_s32 prev, rk_u64 key)
{
MppTrieNode *node;
rk_s32 idx;
if (trie->node_used >= trie->node_count) {
rk_s32 old_count = trie->node_count;
rk_s32 new_count = old_count * 2;
MppTrieNode *new_nodes = mpp_realloc(trie->nodes, MppTrieNode, new_count);
if (!new_nodes) {
mpp_loge_f("failed to realloc new nodes %d\n", new_count);
return -1;
}
/* NOTE: new memory should be memset to zero */
memset(new_nodes + old_count, 0, sizeof(*new_nodes) * old_count);
trie_dbg_cnt("trie %p enlarge node %p:%d -> %p:%d\n",
trie, trie->nodes, trie->node_count, new_nodes, new_count);
trie->nodes = new_nodes;
trie->node_count = new_count;
}
idx = trie->node_used++;
node = &trie->nodes[idx];
node->idx = idx;
node->prev = (prev > 0) ? prev : 0;
node->key = key;
node->id = INVALID_NODE_ID;
if (prev >= 0)
trie->nodes[prev].next_cnt++;
trie_dbg_cnt("get node %d\n", idx);
return idx;
}
static rk_s32 trie_prepare_buf(MppTrieImpl *p, rk_s32 info_size)
{
if (p->info_count >= MPP_TRIE_INFO_MAX) {
mpp_loge_f("invalid trie info count %d larger than max %d\n",
p->info_count, MPP_TRIE_INFO_MAX);
return rk_nok;
}
/* check and enlarge info buffer */
if (p->info_buf_pos + info_size > p->info_buf_size) {
rk_s32 old_size = p->info_buf_size;
rk_s32 new_size = old_size * 2;
void *ptr = mpp_realloc(p->info_buf, void, new_size);
if (!ptr) {
mpp_loge_f("failed to realloc new info buffer %d\n", new_size);
return rk_nok;
}
trie_dbg_cnt("trie %p enlarge info_buf %p:%d -> %p:%d\n",
p, p->info_buf, old_size, ptr, new_size);
p->info_buf = ptr;
p->info_buf_size = new_size;
}
return rk_ok;
}
rk_s32 mpp_trie_init(MppTrie *trie, const char *name)
{
MppTrieImpl *p;
rk_s32 name_len;
rk_s32 ret = rk_nok;
if (!trie || !name) {
mpp_loge_f("invalid trie %p name %p\n", trie, name);
return ret;
}
mpp_env_get_u32("mpp_trie_debug", &mpp_trie_debug, 0);
name_len = strnlen(name, MPP_TRIE_NAME_MAX) + 1;
p = mpp_calloc_size(MppTrieImpl, sizeof(*p) + name_len);
if (!p) {
mpp_loge_f("create trie impl %s failed\n", name);
goto done;
}
p->name = (char *)(p + 1);
p->name_len = name_len;
strncpy(p->name, name, name_len);
p->node_count = DEFAULT_NODE_COUNT;
p->nodes = mpp_calloc(MppTrieNode, p->node_count);
if (!p->nodes) {
mpp_loge_f("create %d nodes failed\n", p->node_count);
goto done;
}
p->info_buf_size = 4096;
p->info_buf = mpp_calloc(void, p->info_buf_size);
if (!p->info_buf) {
mpp_loge_f("failed to alloc %d info buffer\n", p->info_buf_size);
goto done;
}
/* get node 0 as root node*/
trie_get_node(p, -1, 0);
ret = rk_ok;
done:
if (ret && p) {
MPP_FREE(p->info_buf);
MPP_FREE(p->nodes);
MPP_FREE(p);
}
*trie = p;
return ret;
}
static rk_s32 mpp_trie_walk(MppTrieWalk *p, rk_s32 idx, rk_u32 key, rk_u32 keyx, rk_u32 end)
{
MppTrieNode *node = &p->root[idx];
char log_buf[128];
rk_u32 log_size = sizeof(log_buf) - 1;
rk_u32 log_len = 0;
rk_u32 log_en = ((mpp_trie_debug & MPP_TRIE_DBG_WALK) != 0) ? 1 : 0;
rk_s32 next = -1;
if (log_en)
log_len += snprintf(log_buf + log_len, log_size - log_len,
"node %d:%d key %02x:%x -> ",
node->idx, node->id, key, keyx);
/* check high 4 bits */
if (!node->tag_len || p->match == node->idx) {
/* not tag or tag has be matched -> normal next switch node */
next = node->next[keyx];
if (log_en)
log_len += snprintf(log_buf + log_len, log_size - log_len,
"tag %s -> ",
(node->tag_len == 0) ? "n/a" : "match");
p->tag = 0;
p->len = 0;
p->match = -1;
} else {
/* with tag check len to fill or to stop */
rk_u64 val_new = (p->tag << 4) | keyx;
rk_s32 len_new = p->len + 1;
if (log_en)
log_len += snprintf(log_buf + log_len, log_size - log_len,
"tag %0*llx:%d - st %0*llx:%d -> ",
node->tag_len, node->tag_val, node->tag_len,
node->tag_len, val_new, len_new);
/* clear old matched node */
p->match = -1;
if (node->tag_len > len_new && !end) {
/* more tag to fill keep current node */
p->tag = val_new;
p->len = len_new;
next = node->idx;
if (log_en)
log_len += snprintf(log_buf + log_len, log_size - log_len,
"fill -> ");
} else {
/* check tag match with new value */
p->tag = 0;
p->len = 0;
if (node->tag_val != val_new) {
if (log_en)
log_len += snprintf(log_buf + log_len, log_size - log_len,
"mismatch -> ");
next = INVALID_NODE_ID;
} else {
if (log_en)
log_len += snprintf(log_buf + log_len, log_size - log_len,
"match -> ");
next = node->idx;
p->match = node->idx;
}
}
}
if (log_en) {
snprintf(log_buf + log_len, log_size - log_len, "%d", next);
mpp_logi_f("%s\n", log_buf);
}
return next;
}
static MppTrieNode *mpp_trie_get_node_at(MppTrieNode *root, rk_s32 start, const char *name)
{
const char *s = name;
MppTrieWalk walk;
rk_s32 idx = start;
if (!root || !name || !*name) {
mpp_loge_f("invalid root %p name %p\n", root, name);
return NULL;
}
trie_dbg_get("root %p search %s from %d\n", root, name, start);
walk.root = root;
walk.tag = 0;
walk.len = 0;
walk.match = 0;
do {
char key = *s++;
rk_u32 key0 = (key >> 4) & 0xf;
rk_u32 key1 = key & 0xf;
rk_u32 end = s[0] == '\0';
idx = mpp_trie_walk(&walk, idx, key, key0, 0);
if (idx < 0)
break;
idx = mpp_trie_walk(&walk, idx, key, key1, end);
if (idx < 0 || end)
break;
} while (1);
trie_dbg_get("get %s ret node %d:%d\n", name, idx, (idx >= 0) ? root[idx].id : INVALID_NODE_ID);
return (idx >= 0) ? &root[idx] : NULL;
}
rk_s32 mpp_trie_init_by_root(MppTrie *trie, void *root)
{
MppTrieImpl *p;
MppTrieInfo *info;
rk_s32 i;
if (!trie || !root) {
mpp_loge_f("invalid trie %p root %p\n", trie, root);
return rk_nok;
}
*trie = NULL;
p = mpp_calloc(MppTrieImpl, 1);
if (!p) {
mpp_loge_f("create trie impl failed\n");
return rk_nok;
}
info = mpp_trie_get_info_from_root(root, "__name__");
if (info)
p->name = mpp_trie_info_ctx(info);
info = mpp_trie_get_info_from_root(root, "__node__");
if (info)
p->node_used = *(rk_u32 *)mpp_trie_info_ctx(info);
info = mpp_trie_get_info_from_root(root, "__info__");
if (info)
p->info_count = *(rk_u32 *)mpp_trie_info_ctx(info);
/* import and update new buffer */
p->nodes = (MppTrieNode *)root;
if (mpp_trie_debug & MPP_TRIE_DBG_IMPORT)
mpp_trie_dump(p, "root import");
info = mpp_trie_get_info_first(p);
for (i = 0; i < p->info_count; i++) {
const char *name = mpp_trie_info_name(info);
MppTrieInfo *info_set = info;
MppTrieInfo *info_ret = mpp_trie_get_info(p, name);
info = mpp_trie_get_info_next(p, info);
if (info_ret && info_set == info_ret && info_ret->index == i)
continue;
/*
* Fallback for entries under VLA/array sub-trees.
* The info stores the segment name but the entry is registered
* under a sub-root node. Walk back through prev links to find
* the sub-root ancestor, then retry the name lookup from there.
*/
if (!info_ret) {
rk_s32 off = (rk_s32)((rk_u8 *)info_set - (rk_u8 *)p->nodes);
rk_s32 j;
rk_s32 validated = 0;
for (j = 0; j < p->node_used; j++) {
MppTrieNode *n = &p->nodes[j];
if (n->id != off)
continue;
rk_s32 walk = n->idx;
while (walk > 0 && !p->nodes[walk].sub_root)
walk = p->nodes[walk].prev;
if (walk > 0) {
MppTrieNode *node = mpp_trie_get_node_at(p->nodes, walk, name);
if (node && node == n)
validated = 1;
}
break;
}
if (validated)
continue;
}
mpp_loge_f("trie check on import found mismatch info %s [%d:%p] - [%d:%p]\n",
name, i, info_set, info_ret ? info_ret->index : -1, info_ret);
return rk_nok;
}
*trie = p;
return rk_ok;
}
rk_s32 mpp_trie_deinit(MppTrie trie)
{
if (trie) {
MppTrieImpl *p = (MppTrieImpl *)trie;
/* NOTE: do not remvoe imported root */
if (p->node_count)
mpp_free(p->nodes);
else
p->nodes = NULL;
MPP_FREE(p->info_buf);
MPP_FREE(p);
return rk_ok;
}
return rk_nok;
}
/*
* trie_pave_segment - pave one segment's characters into trie from start_idx
*
* Returns end node index on success, negative on error.
*/
static rk_s32 trie_pave_segment(MppTrieImpl *p, const char *seg, rk_s32 seg_len, rk_s32 start_idx)
{
rk_s32 idx = start_idx;
rk_s32 i;
for (i = 0; i < seg_len && seg[i]; i++) {
rk_u32 key = seg[i];
rk_s32 key0 = (key >> 4) & 0xf;
rk_s32 key1 = key & 0xf;
MppTrieNode *node = p->nodes + idx;
rk_s32 next;
next = node->next[key0];
if (!next) {
next = trie_get_node(p, idx, key0);
if (next < 0)
return next;
node = p->nodes + idx;
node->next[key0] = next;
}
idx = next;
node = p->nodes + idx;
next = node->next[key1];
if (!next) {
next = trie_get_node(p, idx, key1);
if (next < 0)
return next;
node = p->nodes + idx;
node->next[key1] = next;
}
idx = next;
}
return idx;
}
static MppTrieNode *mpp_trie_get_node(MppTrieNode *root, const char *name)
{
return mpp_trie_get_node_at(root, 0, name);
}
static rk_s32 mpp_trie_check(MppTrie trie, char *base, const char *log)
{
MppTrieImpl *p = (MppTrieImpl *)trie;
rk_s32 found = 0;
rk_s32 i;
for (i = 0; i < p->node_used; i++) {
MppTrieNode *n = &p->nodes[i];
MppTrieNode *node;
const char *name;
if (i && !n->idx)
continue;
if (n->id < 0)
continue;
name = (const char *)((MppTrieInfo *)(base + n->id) + 1);
/*
* Verify entry is accessible via trie walk.
* Try full-path from root first; if not found, try from subroot ancestor.
*/
node = mpp_trie_get_node_at(p->nodes, 0, name);
if (!node || node != n) {
rk_s32 walk = n->idx;
while (walk > 0 && !p->nodes[walk].sub_root)
walk = p->nodes[walk].prev;
node = (walk > 0) ? mpp_trie_get_node_at(p->nodes, walk, name) : NULL;
if (!node || node != n) {
mpp_loge("trie check on %s: node %d '%s' mismatch\n",
log, i, name);
return rk_nok;
}
}
found++;
}
if (found != p->info_count) {
mpp_loge("trie check on %s: %d nodes with info, expected %d\n",
log, found, p->info_count);
return rk_nok;
}
/* Check subroot nodes have valid info and children */
for (i = 0; i < p->node_used; i++) {
MppTrieNode *n = &p->nodes[i];
rk_s32 child_cnt = 0;
rk_s32 j;
if (!n->sub_root)
continue;
if (n->id < 0) {
mpp_loge("trie check on %s: subroot node %d has no info entry\n", log, i);
continue;
}
for (j = 0; j < MPP_TRIE_KEY_MAX; j++) {
if (n->next[j] > 0)
child_cnt++;
}
if (!child_cnt)
mpp_loge("trie check on %s: subroot node %d has no children\n", log, i);
}
return rk_ok;
}
rk_s32 mpp_trie_last_info(MppTrie trie)
{
MppTrieImpl *p = (MppTrieImpl *)trie;
MppTrieNode *root;
MppTrieNode *node;
char *buf;
rk_s32 node_count;
rk_s32 node_valid;
rk_s32 nodes_size;
rk_s32 pos = 0;
rk_s32 i;
rk_s32 j;
if (!trie) {
mpp_loge_f("invalid NULL trie\n");
return rk_nok;
}
/* write trie self entry info */
pos = p->info_count + 3;
mpp_trie_add_info(trie, "__name__", p->name, p->name_len);
mpp_trie_add_info(trie, "__info__", &pos, sizeof(pos));
/* NOTE: node count need to be update after shrinking */
mpp_trie_add_info(trie, "__node__", &p->node_used, sizeof(p->node_used));
root = p->nodes;
node_count = p->node_used;
node_valid = node_count;
trie_dbg_last("shrink trie node start node %d info %d\n", node_count, p->info_count);
if (mpp_trie_debug & MPP_TRIE_DBG_LAST_STEP)
mpp_trie_dump_f(trie);
for (i = node_count - 1; i > 0; i--) {
MppTrieNode *prev;
rk_s32 prev_idx;
node = &root[i];
prev_idx = node->prev;
prev = &root[prev_idx];
if (prev->next_cnt > 1) {
trie_dbg_last("node %d:%d prev %d next count %d stop shrinking for multi next\n",
i, node->id, prev_idx, prev->next_cnt);
continue;
}
if (node->tag_len >= (rk_s16)MPP_TRIE_TAG_LEN_MAX) {
trie_dbg_last("node %d:%d tag %d - %016llx stop shrinking for max tag len\n",
i, node->id, node->tag_len, node->tag_val);
continue;
}
if (prev->id >= 0) {
trie_dbg_last("node %d:%d tag %d - %016llx stop shrinking for valid info node\n",
i, node->id, node->tag_len, node->tag_val);
continue;
}
if (node->sub_root) {
trie_dbg_last("node %d:%d tag %d - %016llx stop shrinking for sub_root\n",
i, node->id, node->tag_len, node->tag_val);
continue;
}
prev->id = node->id;
/* NOTE: do NOT increase tag length on root node */
prev->tag_len = node->tag_len + 1;
prev->tag_val = ((rk_u64)node->key << (node->tag_len * 4)) | node->tag_val;
prev->next_cnt = node->next_cnt;
memcpy(prev->next, node->next, sizeof(node->next));
trie_dbg_last("node %d:%d shrink prev %d key %x tag %016llx -> %016llx\n",
i, node->id, prev->idx, prev->key, node->tag_val, prev->tag_val);
for (j = 0; j < MPP_TRIE_KEY_MAX; j++) {
if (!prev->next[j])
continue;
root[prev->next[j]].prev = prev_idx;
}
memset(node, 0, sizeof(*node));
node->id = INVALID_NODE_ID;
node_valid--;
}
trie_dbg_last("shrink trie node finish count %d -> %d\n", node_count, node_valid);
if (mpp_trie_debug & MPP_TRIE_DBG_LAST_STEP)
mpp_trie_dump_f(trie);
if (mpp_trie_debug & MPP_TRIE_DBG_LAST_CHECK)
mpp_trie_check(trie, p->info_buf, "shrink merge tag stage");
trie_dbg_last("move trie node start to reduce memory %d -> %d\n", node_count, node_valid);
for (i = 1; i < node_valid; i++) {
node = &root[i];
/* skip valid node */
if (node->idx)
continue;
for (j = i; j < node_count; j++) {
MppTrieNode *tmp = &root[j];
MppTrieNode *prev;
rk_s32 k;
/* skip empty node */
if (!tmp->idx)
continue;
trie_dbg_last("move node %d to %d prev %d\n", j, i, tmp->prev);
prev = &root[tmp->prev];
/* relink previous node */
for (k = 0; k < MPP_TRIE_KEY_MAX; k++) {
if (prev->next[k] != tmp->idx)
continue;
prev->next[k] = i;
break;
}
memcpy(node, tmp, sizeof(*node));
node->idx = i;
memset(tmp, 0, sizeof(*tmp));
/* relink next node */
for (k = 0; k < MPP_TRIE_KEY_MAX; k++) {
if (!node->next[k])
continue;
root[node->next[k]].prev = i;
}
break;
}
}
p->node_used = node_valid;
trie_dbg_last("move trie node finish used %d\n", p->node_used);
if (mpp_trie_debug & MPP_TRIE_DBG_LAST_STEP)
mpp_trie_dump_f(trie);
if (mpp_trie_debug & MPP_TRIE_DBG_LAST_CHECK)
mpp_trie_check(trie, p->info_buf, "shrink move node stage");
trie_dbg_last("create user buffer start\n");
nodes_size = sizeof(MppTrieNode) * p->node_used;
p->buf_size = nodes_size + p->info_buf_pos;
p->buf_size = MPP_ALIGN(p->buf_size, sizeof(void *));
buf = mpp_calloc(char, p->buf_size);
if (!buf) {
mpp_loge("failed to alloc trie buffer size %d\n", p->buf_size);
return rk_nok;
}
p->nodes = (MppTrieNode *)buf;
memcpy(p->nodes, root, nodes_size);
/* Block copy all info entries, then adjust node->id offsets */
memcpy(buf + nodes_size, p->info_buf, p->info_buf_pos);
for (i = 0; i < p->node_used; i++) {
if (p->nodes[i].id >= 0)
p->nodes[i].id += nodes_size;
}
if (mpp_trie_debug & MPP_TRIE_DBG_LAST_CHECK)
mpp_trie_check(trie, (char *)p->nodes, "final buffer");
MPP_FREE(root);
MPP_FREE(p->info_buf);
/* NOTE: udpate final shrinked node count */
{
MppTrieInfo *info = mpp_trie_get_info_from_root(p->nodes, "__node__");
if (info)
*(rk_u32 *)mpp_trie_info_ctx(info) = p->node_used;
}
return rk_ok;
}
rk_s32 mpp_trie_add_info(MppTrie trie, const char *name, void *ctx, rk_u32 ctx_len)
{
MppTrieImpl *p = (MppTrieImpl *)trie;
rk_s32 info_size;
rk_u32 ctx_real;
rk_s32 str_real;
rk_s32 str_len;
rk_s32 idx;
if (!p) {
mpp_loge_f("invalid trie %p name %s ctx %p\n", p, name, ctx);
return rk_nok;
}
if (!name)
return mpp_trie_last_info(p);
str_real = strnlen(name, MPP_TRIE_NAME_MAX) + 1;
/* pad name so the ctx area behind it stays 8-byte aligned;
* ctx holds KmppEntry with 64-bit members */
str_len = MPP_ALIGN8(str_real + sizeof(MppTrieInfo)) - sizeof(MppTrieInfo);
/* NOTE: align all ctx_len to eight bytes */
ctx_real = ctx_len;
ctx_len = MPP_ALIGN8(ctx_real);
info_size = sizeof(MppTrieInfo) + str_len + ctx_len;
if (str_len >= MPP_TRIE_NAME_MAX) {
mpp_loge_f("invalid trie name %s len %d larger than max %d\n",
name, str_len, MPP_TRIE_NAME_MAX);
return rk_nok;
}
if (trie_prepare_buf(p, info_size))
return rk_nok;
idx = trie_pave_segment(p, name, str_real, 0);
if (idx < 0) {
mpp_loge_f("trie %p pave node %s failed\n", p, name);
return rk_nok;
}
if (p->nodes[idx].id != -1) {
mpp_logw("trie %p add_info duplicate key \"%s\" id=%d\n",
p, name, p->nodes[idx].id);
return rk_nok;
}
p->nodes[idx].id = p->info_buf_pos;
if (p->info_name_max < str_real - 1)
p->info_name_max = str_real - 1;
{
MppTrieInfo *info = (MppTrieInfo *)(p->info_buf + p->info_buf_pos);
char *buf = (char *)(info + 1);
info->index = p->info_count;
info->ctx_len = ctx_len;
info->str_len = str_len;
memcpy(buf, name, str_real);
while (str_real < str_len)
buf[str_real++] = 0;
buf += str_len;
memcpy(buf, ctx, ctx_real);
while (ctx_real < ctx_len)
buf[ctx_real++] = 0;
}
trie_dbg_set("trie %p add info %d - %s at node %d pos %d ctx %p size %d\n",
p, p->info_count, name, idx, p->info_buf_pos, ctx, ctx_len);
p->info_buf_pos += info_size;
p->info_count++;
return rk_ok;
}
rk_s32 mpp_trie_add_entry(MppTrie trie, MppTrieStatus *st,
const char *name, KmppEntry *entry)
{
MppTrieImpl *p = (MppTrieImpl *)trie;
rk_s32 name_len;
rk_s32 idx;
if (!p || !st) {
mpp_loge_f("invalid param trie %p st %p\n", p, st);
return rk_nok;
}
if (!name)
return mpp_trie_last_info(p);
st->node_idx = -1;
st->array_idx = -1;
name_len = strnlen(name, MPP_TRIE_NAME_MAX);
if (!name_len) {
mpp_loge_f("invalid empty path\n");
return rk_nok;
}
idx = trie_pave_segment(p, name, name_len, st->root_idx);
if (idx < 0)
return rk_nok;
MppTrieNode *node = &p->nodes[idx];
rk_s32 is_vla = entry && entry->type == ENTRY_TYPE_VLA_INFO;
if (is_vla) {
node->sub_root = 1;
node->count = entry->vla.elem_count;
}
/* Attach info payload to node */
if (node->id < 0 && entry) {
rk_s32 str_real = name_len + 1;
rk_s32 str_len = MPP_ALIGN8(str_real + sizeof(MppTrieInfo)) -
sizeof(MppTrieInfo);
rk_s32 info_size = sizeof(MppTrieInfo) + str_len + sizeof(*entry);
if (trie_prepare_buf(p, info_size))
return rk_nok;
node->id = p->info_buf_pos;
if (p->info_name_max < name_len)
p->info_name_max = name_len;
{
MppTrieInfo *info = (MppTrieInfo *)(p->info_buf + p->info_buf_pos);
char *buf = (char *)(info + 1);
info->index = p->info_count;
info->ctx_len = sizeof(*entry);
info->str_len = str_len;
memcpy(buf, name, name_len);
buf[name_len] = '\0';
buf += str_len;
((KmppEntry *)buf)->val = entry->val;
trie_dbg_set("trie %p add_entry %s %d - %s at node %d pos %d\n",
p, is_vla ? "subroot" : "leaf",
p->info_count, name, idx, node->id);
}
p->info_buf_pos += info_size;
p->info_count++;
}
st->array_idx = is_vla ? entry->vla.elem_count : -1;
st->node_idx = idx;
return is_vla ? MPP_TRIE_SUBROOT : MPP_TRIE_LEAF;
}
rk_s32 mpp_trie_get_entry(MppTrie trie, MppTrieStatus *st,
const char *name, KmppEntry *entry)
{
MppTrieImpl *p = (MppTrieImpl *)trie;
rk_s32 text_len;
rk_s32 index = -1;
const char *s;
rk_s32 idx;
if (!p || !st || !name) {
mpp_loge_f("invalid param trie %p st %p name %p\n", p, st, name);
return rk_nok;
}
if (!*name) {
mpp_loge_f("invalid empty path\n");
return rk_nok;
}
st->node_idx = -1;
st->array_idx = -1;
st->name_pos = 0;
if (entry)
entry->val = 0;
/* Find first ':digits' boundary */
for (s = name; *s; s++) {
if (*s == ':' && s[1] >= '0' && s[1] <= '9' && s > name) {
text_len = s - name;
s++;
index = 0;
while (*s >= '0' && *s <= '9') {
index = index * 10 + (*s - '0');
s++;
}
if (*s == ':')
s++;
break;
}
}
/* No ':digits' found - entire name is text */
if (index < 0)
text_len = s - name;
idx = st->root_idx;
{
MppTrieWalk walk;
rk_s32 i;
walk.root = p->nodes;
walk.tag = 0;
walk.len = 0;
walk.match = 0;
for (i = 0; i < text_len && name[i]; i++) {
rk_u32 key = name[i];
rk_s32 key0 = (key >> 4) & 0xf;
rk_s32 key1 = key & 0xf;
rk_s32 end = (i == text_len - 1);
idx = mpp_trie_walk(&walk, idx, key, key0, 0);
if (idx < 0)
return rk_nok;
idx = mpp_trie_walk(&walk, idx, key, key1, end);
if (idx < 0 || (idx <= 0 && !end))
return rk_nok;
}
}
/* Read entry payload */
if (entry) {
MppTrieNode *node = &p->nodes[idx];
if (node->id >= 0) {
char *base = p->info_buf ? (char *)p->info_buf : (char *)p->nodes;
MppTrieInfo *info = (MppTrieInfo *)(base + node->id);
entry->val = ((KmppEntry *)mpp_trie_info_ctx(info))->val;
}
trie_dbg_get("trie %p get_entry node %d %s idx -%d\n",
p, idx, index >= 0 ? "subroot" : "leaf", index);
}
st->node_idx = idx;
st->array_idx = index;
st->name_pos = s - name;
return index >= 0 ? MPP_TRIE_SUBROOT : MPP_TRIE_LEAF;
}
rk_s32 mpp_trie_for_each_entry(MppTrie trie, MppTrieInfoCb cb, void *ctx)
{
MppTrieImpl *p = (MppTrieImpl *)trie;
char *base;
rk_s32 i;
if (!p || !cb)
return rk_nok;
base = p->info_buf ? (char *)p->info_buf : (char *)p->nodes;
for (i = 0; i < p->node_used; i++) {
MppTrieNode *n = &p->nodes[i];
if (i && !n->idx)
continue;
if (n->id < 0)
continue;
MppTrieInfo *info = (MppTrieInfo *)(base + n->id);
const char *name = mpp_trie_info_name(info);
void *data = mpp_trie_info_ctx(info);
if (mpp_trie_info_is_self(info))
continue;
rk_s32 walk;
rk_s32 subroot = 0;
if (n->sub_root) {
subroot = n->idx;
} else if (mpp_trie_get_node_at(p->nodes, 0, name) != n) {
walk = n->idx;
while (walk > 0 && !p->nodes[walk].sub_root)
walk = p->nodes[walk].prev;
if (walk > 0)
subroot = walk;
}
if (cb(name, data, subroot, ctx))
return rk_nok;
}
return rk_ok;
}
rk_s32 mpp_trie_get_node_count(MppTrie trie)
{
MppTrieImpl *p = (MppTrieImpl *)trie;
return (p) ? p->node_used : 0;
}
rk_s32 mpp_trie_get_info_count(MppTrie trie)
{
MppTrieImpl *p = (MppTrieImpl *)trie;
return (p) ? p->info_count : 0;
}
rk_s32 mpp_trie_get_buf_size(MppTrie trie)
{
MppTrieImpl *p = (MppTrieImpl *)trie;
return (p) ? p->buf_size : 0;
}
rk_s32 mpp_trie_get_name_max(MppTrie trie)
{
MppTrieImpl *p = (MppTrieImpl *)trie;
return (p) ? p->info_name_max : 0;
}
const char *mpp_trie_get_name(MppTrie trie)
{
MppTrieImpl *p = (MppTrieImpl *)trie;
return (p) ? p->name : NULL;
}
void *mpp_trie_get_node_root(MppTrie trie)
{
MppTrieImpl *p = (MppTrieImpl *)trie;
return (p) ? p->nodes : NULL;
}
MppTrieInfo *mpp_trie_get_info(MppTrie trie, const char *name)
{
MppTrieImpl *p = (MppTrieImpl *)trie;
MppTrieNode *node;
if (!trie || !name) {
mpp_loge_f("invalid trie %p name %p\n", trie, name);
return NULL;
}
node = mpp_trie_get_node(p->nodes, name);
if (!node || node->id < 0)
return NULL;
return (MppTrieInfo *)(((char *)p->nodes) + node->id);
}
MppTrieInfo *mpp_trie_get_info_first(MppTrie trie)
{
MppTrieImpl *p = (MppTrieImpl *)trie;
return (p) ? (MppTrieInfo *)(((char *)p->nodes) + p->node_used * sizeof(MppTrieNode)) : NULL;
}
MppTrieInfo *mpp_trie_get_info_next(MppTrie trie, MppTrieInfo *info)
{
MppTrieImpl *p = (MppTrieImpl *)trie;
if (!p || !info || info->index >= p->info_count - 1)
return NULL;
return (MppTrieInfo *)((char *)(info + 1) + info->str_len + info->ctx_len);
}
MppTrieInfo *mpp_trie_get_info_from_root(void *root, const char *name)
{
MppTrieNode *node;
if (!root || !name) {
mpp_loge_f("invalid root %p name %p\n", root, name);
return NULL;
}
mpp_env_get_u32("mpp_trie_debug", &mpp_trie_debug, 0);
node = mpp_trie_get_node((MppTrieNode *)root, name);
if (!node || node->id < 0)
return NULL;
return (MppTrieInfo *)(((char *)root) + node->id);
}
void mpp_trie_dump(MppTrie trie, const char *func)
{
MppTrieImpl *p = (MppTrieImpl *)trie;
char *base = p->info_buf ? (char *)p->info_buf : (char *)p->nodes;
rk_s32 i;
rk_s32 next_cnt[17];
rk_s32 tag_len[17];
memset(next_cnt, 0, sizeof(next_cnt));
memset(tag_len, 0, sizeof(tag_len));
mpp_logi("%s dumping trie %p\n", func, trie);
mpp_logi("name %s size %d node %d info %d\n",
p->name, p->buf_size, p->node_used, p->info_count);
for (i = 0; i < p->node_used; i++) {
MppTrieNode *node = &p->nodes[i];
rk_s32 valid_count = 0;
rk_s32 j;
if (i && !node->idx)
continue;
if (node->id >= 0) {
MppTrieInfo *info = (MppTrieInfo *)((char *)base + node->id);
/* check before and after last info */
if (node->id < (rk_s32)(p->node_used * sizeof(MppTrieNode)))
mpp_logi("node %d key %x info %d - %s\n", node->idx, node->key, node->id,
mpp_trie_info_name(info));
else
mpp_logi("node %d key %x info %d - %s\n", node->idx, node->key, node->id,
mpp_trie_info_name(info));
} else
mpp_logi("node %d key %x\n", node->idx, node->key);
if (node->tag_len)
mpp_logi(" prev %d count %d tag %d - %llx\n", node->prev, node->next_cnt, node->tag_len, node->tag_val);
else
mpp_logi(" prev %d count %d\n", node->prev, node->next_cnt);
for (j = 0; j < MPP_TRIE_KEY_MAX; j++) {
if (node->next[j] > 0) {
mpp_logi(" next %d:%d -> %d\n", valid_count, j, node->next[j]);
valid_count++;
}
}
next_cnt[valid_count]++;
tag_len[node->tag_len]++;
}
mpp_logi("node | next | tag | used %d\n", p->node_used);
for (i = 0; i < 17; i++) {
if (next_cnt[i] || tag_len[i])
mpp_logi("%2d | %4d | %4d |\n", i, next_cnt[i], tag_len[i]);
}
mpp_logi("%s dumping node end\n", func, p->node_used);
}
void mpp_trie_timing_test(MppTrie trie)
{
MppTrieInfo *root = mpp_trie_get_info_first(trie);
MppTrieInfo *info = root;
rk_s64 sum = 0;
rk_s32 loop = 0;
do {
rk_s64 start, end;
start = mpp_time();
mpp_trie_get_info(trie, mpp_trie_info_name(info));
end = mpp_time();
info = mpp_trie_get_info_next(trie, info);
sum += end - start;
loop++;
} while (info);
mpp_logi("trie access %d info %lld us averga %lld us\n",
loop, sum, sum / loop);
}
Reference in a new issue View git blame Copy permalink