Add a list on a trie node in C

Question

I'm adding words (character per node) on a trie data structure - that happens correctly based on a implementantion I found on the web - http://www.techiedelight.com/trie-implementation-insert-search-delete/ Although I want to extend this and add a list containing some data based on the words, such term frequency etc. Right now I'm facing an issue with the pointer of the list when adding the first element on a trie node - in the method append_posting_list - and getting a segmetation fault. Here is the code so far.

main.h

#ifndef TRIE_H
#define TRIE_H

#define CHAR_SIZE 26

typedef struct posting_list {
    int doc_id;
    int tf;
    int df;
    struct posting_list *next;
} posting_list_node ;

struct Trie
{
    posting_list_node *p_node; // this will be the head of the posting list for every word;
    int isLeaf;    // 1 when node is a leaf node
    struct Trie* character[CHAR_SIZE];
};

struct Trie* getNewTrieNode();
void insert(struct Trie* *head, char* str, int doc_id);
int search(struct Trie* head, char* str);

#endif //TRIE_H

main.c

#include <stdio.h>
#include <stdlib.h>
#include "main.h"


int main(){
    struct Trie* head = getNewTrieNode();
    insert(&head, "hello", 1);
    return 0;
}

// Function that returns a new Trie node
struct Trie* getNewTrieNode()
{
    struct Trie* node = (struct Trie*)malloc(sizeof(struct Trie));
    node->isLeaf = 0;

    for (int i = 0; i < CHAR_SIZE; i++)
        node->character[i] = NULL;

    return node;
}

posting_list_node* get_mem(){
    posting_list_node* p;
    p = (posting_list_node *)malloc(sizeof(posting_list_node));
    if (p == NULL){
        printf("Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }
    return p;
}

void append_posting_list(int doc_id, posting_list_node **n){
    posting_list_node *new, *q;
    new = get_mem();

    new->doc_id = doc_id;
    new->tf = 1;
    new->next = NULL;

    // if new is the first element of the list
    if(n == NULL) {
        *n = new;
    } else {
        q = *n;
        while( q->next!=NULL) {
            q = q->next;
        }
        q->next = new;
    }
}

// Iterative function to insert a string in Trie.
void insert(struct Trie* *head, char* str, int doc_id)
{
    // start from root node
    struct Trie* curr = *head;
    while (*str)
    {
        // create a new node if path doesn't exists
        if (curr->character[*str - 'a'] == NULL)
            curr->character[*str - 'a'] = getNewTrieNode();

        // go to next node
        curr = curr->character[*str - 'a'];

        // move to next character
        str++;
    }

    // already found this word, increase frequency
    if(curr->isLeaf) {
        curr->p_node->tf += 1;
    } else {
        append_posting_list(doc_id, curr->p_node);
        // mark current node as leaf
        curr->isLeaf = 1;
    }
}

// Iterative function to search a string in Trie. It returns 1
// if the string is found in the Trie, else it returns 0
int search(struct Trie* head, char* str)
{
    // return 0 if Trie is empty
    if (head == NULL)
        return 0;

    struct Trie* curr = head;
    while (*str)
    {
        // go to next node
        curr = curr->character[*str - 'a'];

        // if string is invalid (reached end of path in Trie)
        if (curr == NULL)
            return 0;

        // move to next character
        str++;
    }

    // if current node is a leaf and we have reached the
    // end of the string, return 1
    return curr->isLeaf;
}

I'm really stuck here. Any suggestions would be really appreciated.

Answer 1

I found a couple things that when fixed, got rid of your segmentation fault.

In getNewTrieNode() I think you need to set p_node to NULL

struct Trie* getNewTrieNode() {
    struct Trie* node = (struct Trie*)malloc(sizeof(struct Trie));
    node->isLeaf = 0;

    for (int i = 0; i < CHAR_SIZE; i++)
        node->character[i] = NULL;

    node->p_node = NULL;

    return node;
}

append_posting_list() takes post_list_node **, but in insert(), you are passing just post_list_node *

void append_posting_list(int doc_id, posting_list_node **n)

append_posting_list(doc_id, curr->p_node);

looks like it should be

append_posting_list(doc_id, &(curr->p_node));

In append_posting_list()

if (n == NULL) {

should be

if (*n == NULL) {

in order to see if a pointer to an empty list is being passed in.

You should really have some functions to print out your data structure while you are working on it, so you can test each piece as you develop it. Simply compiling and running code and not getting any errors is no gurantee the code is working correctly with complex data structures like this. Making sure that each piece works perfectly before going on to the next piece will save you hours in trying to track down segmentation faults and other errors like this.