Trie implementation in c

Question

我正在c中实现多位trie。当我运行代码时，我得到运行时错误:总线错误(核心转储)。当我通过调用insert_rule方法添加不同的节点时，我得到了这个错误。

我用代码写注释来理解。

这段代码是作为multibit.h头文件编写的，这些方法是从另一个。c文件调用的。c文件中的代码是完全正确的。我还通过示例测试代码检查了init_mtnode方法。Init_mtnode方法也非常好。

    #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: %dn", 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("%un", 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;
}

Answer 1

调用helper()函数的行

root = helper(root, *(prefixes + i) , prelen, portnum, 0);

你应该传递padded_prelen来代替prelen，因为你每次增加b的STRIDE长度。如果你把它和prelen比较，它永远不会等于它，除非

prelen % STRIDE == 0