Trie реализация в c

Question

Я реализую multibit trie в C. Когда я запускаю код, я получаю ошибку во время выполнения: ошибка шины (сбрасывается ядром). Я получаю эту ошибку, когда добавляю разные узлы, вызывая метод insert_rule.

Я написал комментарии в коде для понимания.

Этот код написан как файл заголовка multibit.h, и эти методы вызывают из другого .c-файла. Коды в файле caller.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: %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; 
} 

Answer 1

Линия, на которой вы вызываете функцию helper()

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

вы должны пройти padded_prelen вместо prelen, потому что приращение б по длине STRIDE каждый раз. А если сравнить его с он prelen, он никогда не будет равно, что если

prelen % STRIDE == 0