在C特里实施 [英] Trie implementation in c
本文介绍了在C特里实施的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我实施C.多位特里当我运行code，我得到运行时错误：总线错误（核心转储）。我得到这个错误，当我通过调用insert_rule方法添加不同的节点。
在code我写的评论理解。
这code写成multibit.h头文件，这方法正在从另一个.c文件调用。 codeS里caller.c文件是完全正确的。我还检查init_mtnode通过样品测试code方法。 Init_mtnode方法也是完全正常的。
的#define STRIDE 3 / *在特里结构的每个节点都是C code *的结构/
结构MtNode {
/ *节点是一个数组8个元素。每个元素是一个指向它的子节点。* /
结构MtNode *节点; [8] // 2 ^跨距= 2 ^ 3 = 8
INT下一跳;
}; typedef结构MtNode节点; 结构MtNode *帮手（MtNode * curr_node，uint32_t的prefix_r，诠释preLEN，INT端口编号，INT B）;
uint32_t的* paddingFunction（uint32_t的prefix_r，诠释preLEN，诠释padded_ preLEN）; / *初始化多位特里结构节点* /
节点* init_mtnode（）{
节点* RET;
INT大小;
RET =的static_cast＆下;节点* GT（malloc的（的sizeof（节点）））;
如果（RET == NULL）/ *检查NULL * /
返回NULL;
大小= 2;＆下; STRIDE;
如果（大小＆GT; = 8）
大小= 7; / *最大可能值* /
的for（int i = 0; I＆LT;大小; ++ I）
ret-个节点由[i] = NULL;
ret-＆GT下一跳= -1;
返回RET;
} / *清理二进制特里结构* /
无效free_mt（结构MtNode *根）{
的for（int i = 0;我≤（INT）POW（2，STRIDE）;我++）{
free_mt（根 - 个节点[I]）;
}
免费（根）;
} / *插入规则* /
/ * preFIX是一个32位的整数。但其preLEN（MSB - preFIX位长）比特数* /
/ * preLEN - preFIX长度=面膜
/ *端口编号 - 端口号保存为下一跳* /
无效insert_rule（结构MtNode *根，uint32_t的preFIX，诠释preLEN，诠释端口编号）{ 静态INT n_rules = 0;
n_rules ++;
的printf（规则数：％d \\ n，n_rules）; 如果（preLEN == 0）{
根 - ＆GT;下一跳=端口编号;
返回;
}
如果（preLEN％STRIDE == 0）{
根=帮手（根，preFIX，preLEN，端口编号，0）;
}其他{
int展开= STRIDE - （preLEN％STRIDE）;
INT padded_ preLEN = preLEN +扩张;
uint32_t的* prefixes;
prefixes = paddingFunction（preFIX，preLEN，padded_ preLEN）;
对（INT I = 0; I＆≤（INT）POW（2，扩张）;我++）{
根=助手（根，*（prefixes + i）中，padded_ preLEN，端口编号，0）;
}
免费（prefixes）;
}
}结构MtNode *帮手（结构MtNode * curr_node，uint32_t的preFIX，诠释preLEN，INT端口编号，INT B）{
//的printf（％U \\ N，prefix_r）;
uint32_t的temp_ preFIX = preFIX;
如果（二== preLEN）{
curr_node-＆GT;下一跳=端口编号;
返回curr_node;
} / *获得preFIX的前3位为指数* /
temp_ preFIX =（preFIX＆LT;＆LT; B）;
temp_ preFIX = temp_ preFIX＆安培; 0xE0000000;
temp_ preFIX = temp_ preFIX＆GT;＆GT; 29;
INT指数=（int）的temp_ preFIX;
如果（curr_node-个节点[指数] == NULL）{
curr_node-个节点[指数] = init_mtnode（）;
} curr_node-个节点[指数] =帮手（curr_node-个节点[指数]，preFIX，preLEN，端口编号，B + STRIDE）;
返回curr_node;
}/ *这个方法垫'0'和'1'，如果preFIX是不是STRIDE整除
如果preFIX = 1111 *，它返回数组[111100，111101，1111111] * /uint32_t的* paddingFunction（uint32_t的prefix_r，诠释preLEN，诠释padded_ preLEN）{
int展开= padded_ preLEN - preLEN;
INT大小=（int）的POW（2扩展）;
uint32_t的* ARR =（uint32_t的*）malloc的（大小*的sizeof（uint32_t的））;
的for（int i = 0; I＆LT;大小;我++）{
uint32_t的TEMP = I;
TEMP =温度＆LT;＆LT; （31- preLEN）;
改编[I] = prefix_r |温度;
}
返回ARR;
}
解决方案
在这里你叫辅助线（）函数
根=帮手（根，*（prefixes + I），preLEN，端口编号，0）;
您应该通过 padded_ preLEN 在 preLEN ，因为你在增加b STRIDE 每次长度。如果你与他进行比较 preLEN ，它永远不会等于除非
preLEN％STRIDE == 0
I am implementing multibit trie in C. When I run the code, I get run-time error: bus error (core dumped). I am getting this error when I am adding different nodes through calling insert_rule method.
I wrote comments in code to understand.
This code is written as multibit.h header file and this methods are being called from another .c file. Codes in caller.c file are perfectly right. I also checked init_mtnode method by sample test code. Init_mtnode method is also perfectly fine.
#define STRIDE 3
/* each node in trie is struct of c code*/
struct MtNode{
/* nodes is an array 8 elements. Each element is a pointer to its child node.*/
struct MtNode* nodes[8]; // 2^stride = 2^3 = 8
int nexthop;
};
typedef struct MtNode node;
struct MtNode* helper(MtNode *curr_node, uint32_t prefix_r, int prelen, int portnum, int b);
uint32_t* paddingFunction(uint32_t prefix_r, int prelen, int padded_prelen);
/* Initialize multibit trie node */
node* init_mtnode(){
node *ret;
int size;
ret = static_cast<node *>(malloc(sizeof(node)));
if (ret == NULL) /* check for NULL */
return NULL;
size = 2 << STRIDE;
if (size >= 8)
size = 7; /* maximum possible value */
for (int i = 0 ; i < size ; ++i)
ret->nodes[i] = NULL;
ret->nexthop = -1;
return ret;
}
/* Clean up binary trie */
void free_mt(struct MtNode *root){
for(int i = 0; i < (int)pow(2,STRIDE); i++){
free_mt(root->nodes[i]);
}
free(root);
}
/* Insert a rule */
/* prefix is a 32 bit integer. But its "prelen (MSB - prefix length bits)" bits are counted */
/* prelen - prefix length = Mask "
/* portnum - port number to be saved as next hop*/
void insert_rule(struct MtNode* root, uint32_t prefix, int prelen, int portnum){
static int n_rules = 0;
n_rules ++;
printf("rules: %d\n", n_rules);
if( prelen == 0){
root->nexthop = portnum;
return;
}
if(prelen % STRIDE == 0){
root = helper(root, prefix, prelen, portnum, 0);
}else{
int expansion = STRIDE - (prelen%STRIDE);
int padded_prelen = prelen + expansion;
uint32_t *prefixes;
prefixes = paddingFunction(prefix, prelen, padded_prelen);
for(int i = 0; i < (int)pow(2,expansion); i++){
root = helper(root, *(prefixes + i) , padded_prelen, portnum, 0);
}
free(prefixes);
}
}
struct MtNode* helper(struct MtNode* curr_node, uint32_t prefix, int prelen, int portnum, int b){
//printf("%u\n", prefix_r);
uint32_t temp_prefix = prefix;
if(b==prelen){
curr_node->nexthop = portnum;
return curr_node;
}
/* get first 3 bits of prefix as index*/
temp_prefix = (prefix << b);
temp_prefix = temp_prefix & 0xE0000000;
temp_prefix = temp_prefix >> 29;
int index = (int) temp_prefix;
if(curr_node->nodes[index] == NULL){
curr_node->nodes[index] = init_mtnode();
}
curr_node->nodes[index] = helper(curr_node->nodes[index], prefix, prelen, portnum, b+STRIDE);
return curr_node;
}
/* this method pads '0's and '1's if prefix is not divisible by STRIDE
if prefix = 1111* , it returns array [111100 , 111101 , 1111111]*/
uint32_t *paddingFunction(uint32_t prefix_r, int prelen, int padded_prelen){
int expansion = padded_prelen - prelen;
int size = (int) pow(2,expansion);
uint32_t *arr = (uint32_t *)malloc(size*sizeof(uint32_t));
for(int i = 0; i < size; i++){
uint32_t temp = i;
temp = temp << (31-prelen);
arr[i] = prefix_r | temp;
}
return arr;
}
解决方案
The line where you call the helper() function
root = helper(root, *(prefixes + i) , prelen, portnum, 0);
you should pass padded_prelen in place of prelen because you increment b by the STRIDE length each time. And if you compare it with he prelen, it will never be equal to that unless
prelen % STRIDE == 0
这篇关于在C特里实施的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
