0

Still getting segmentation fault and have updated code several times. Here is my most recent iteration and have also attached copy of valgrind report.

/**
 * Loads dictionary into memory. Returns true if successful else false.
*/
bool load(const char *dictionary)
{
    root = calloc(1, sizeof(node));
    // assigns NULL value to root's array of pointers
    /*for (int i = 0; i < 27; i++)
    {
       current->children[i] = calloc(1,sizeof(node));
    }*/


   // to hold the current word
    char word[LENGTH +1];
    FILE *loadin = fopen(dictionary, "r");
    size_count = 0;

   while (fscanf(loadin, "%s", word) != EOF)
   {
        int index = 0;
        // defines constant to use in calculating index
        const int ltr = 'a';   
        printf("%s\n", word);
         // creates root node
        current = root;

        printf("%lu\n", strlen(word));

        // checks each character in word one by one
        for (int i =0; i < strlen(word); i++)
        {
            // ' is at index 26
            if (word[i] == '\'')
            {
            index = 26;
            }
            // determines index number of letters in words based on lower case ascii mod with base
            elsem
            {
                index = word[i] % ltr;
            }


            // word and pointer at that "letter" points to nothing
            //    then, create node
            if (current->children[index] == NULL)
            {
                current->children[index] = calloc(1,sizeof(node));
                // move current to next node
                current = current->children[index];
            }


            // if pointer already points to something, assign that pointer to current
            else
            {
                current = current->children[index];
            }
            //test
            printf("%i\n", index);

        }
        // when finished iterating through word
        current->children[index]->is_word = true;
        // increase word count
        size_count++;
        // test
        printf("%i\n", size_count);
    }
    // close dictionary
    fclose(loadin);

    return true;
}

Output with the above is: bat Segmentation fault

Valgrind:
==8459== TO CONTROL THIS PROCESS USING vgdb (which you probably
==8459== don't want to do, unless you know exactly what you're doing,
==8459== or are doing some strange experiment):
==8459== /usr/lib/valgrind/../../bin/vgdb --pid=8459 ...command...
==8459==
==8459== TO DEBUG THIS PROCESS USING GDB: start GDB like this
==8459== /path/to/gdb ./speller
==8459== and then give GDB the following command
==8459== target remote | /usr/lib/valgrind/../../bin/vgdb --pid=8459
==8459== --pid is optional if only one valgrind process is running
==8459== --8459-- REDIR: 0x4019ca0 (strlen) redirected to 0x38068331 (???)
--8459-- Reading syms from /usr/lib/valgrind/vgpreload_core-amd64-linux.so
--8459-- Considering /usr/lib/valgrind/vgpreload_core-amd64-linux.so ..
--8459-- .. CRC mismatch (computed 329d6860 wanted c0186920)
--8459-- object doesn't have a symbol table
--8459-- Reading syms from /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so
--8459-- Considering /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so ..
--8459-- .. CRC mismatch (computed 1fb85af8 wanted 2e9e3c16)
--8459-- object doesn't have a symbol table
==8459== WARNING: new redirection conflicts with existing -- ignoring it
--8459-- old: 0x04019ca0 (strlen ) R-> (0000.0) 0x38068331 ???
--8459-- new: 0x04019ca0 (strlen ) R-> (2007.0) 0x04c2e1a0 strlen
--8459-- REDIR: 0x4019a50 (index) redirected to 0x4c2dd50 (index)
--8459-- REDIR: 0x4019c70 (strcmp) redirected to 0x4c2f2f0 (strcmp)
--8459-- REDIR: 0x401a9c0 (mempcpy) redirected to 0x4c31da0 (mempcpy)
--8459-- Reading syms from /lib/x86_64-linux-gnu/libc-2.19.so
--8459-- Considering /lib/x86_64-linux-gnu/libc-2.19.so ..
--8459-- .. CRC mismatch (computed dc620abc wanted 148cbd6e)
--8459-- Considering /usr/lib/debug/lib/x86_64-linux-gnu/libc-2.19.so ..
--8459-- .. CRC is valid
--8459-- REDIR: 0x4ec3d60 (strcasecmp) redirected to 0x4a25720 (_vgnU_ifunc_wrapper)
--8459-- REDIR: 0x4ec6050 (strncasecmp) redirected to 0x4a25720 (_vgnU_ifunc_wrapper)
--8459-- REDIR: 0x4ec3530 (memcpy@GLIBC_2.2.5) redirected to 0x4a25720 (_vgnU_ifunc_wrapper)
--8459-- REDIR: 0x4ec17c0 (rindex) redirected to 0x4c2da30 (rindex)
--8459-- REDIR: 0x4eba220 (calloc) redirected to 0x4c2cbf0 (calloc)
--8459-- REDIR: 0x4eb9750 (malloc) redirected to 0x4c2ab10 (malloc)
--8459-- REDIR: 0x4ec2410 (__GI_strstr) redirected to 0x4c32030 (__strstr_sse2)
--8459-- REDIR: 0x4ecaac0 (strchrnul) redirected to 0x4c319b0 (strchrnul)
bat
--8459-- REDIR: 0x4ebfac0 (strlen) redirected to 0x4c2e0e0 (strlen)
3
==8459== Invalid write of size 1
==8459== at 0x401435: load (dictionary.c:149)
==8459== by 0x40092D: main (speller.c:40)
==8459== Address 0x0 is not stack'd, malloc'd or (recently) free'd
==8459==
==8459==
==8459== Process terminating with default action of signal 11 (SIGSEGV)
==8459== Access not within mapped region at address 0x0
==8459== at 0x401435: load (dictionary.c:149)
==8459== by 0x40092D: main (speller.c:40)
==8459== If you believe this happened as a result of a stack
==8459== overflow in your program's main thread (unlikely but
==8459== possible), you can try to increase the size of the
==8459== main thread stack using the --main-stacksize= flag.
==8459== The main thread stack size used in this run was 8388608.
--8459-- REDIR: 0x4eb9df0 (free) redirected to 0x4c2bd80 (free)
==8459==
==8459== HEAP SUMMARY:
==8459== in use at exit: 792 bytes in 2 blocks
==8459== total heap usage: 2 allocs, 0 frees, 792 bytes allocated
==8459==
==8459== Searching for pointers to 2 not-freed blocks
==8459== Checked 83,920 bytes
==8459==
==8459== 224 bytes in 1 blocks are still reachable in loss record 1 of 2
==8459== at 0x4C2CC70: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64- linux.so)
==8459== by 0x401214: load (dictionary.c:83)
==8459== by 0x40092D: main (speller.c:40)
==8459==
==8459== 568 bytes in 1 blocks are still reachable in loss record 2 of 2
==8459== at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64- linux.so)
==8459== by 0x4EA544C: __fopen_internal (iofopen.c:73)
==8459== by 0x40122F: load (dictionary.c:94)
==8459== by 0x40092D: main (speller.c:40)
==8459==
==8459== LEAK SUMMARY:
==8459== definitely lost: 0 bytes in 0 blocks
==8459== indirectly lost: 0 bytes in 0 blocks
==8459== possibly lost: 0 bytes in 0 blocks
==8459== still reachable: 792 bytes in 2 blocks
==8459== suppressed: 0 bytes in 0 blocks
==8459==
==8459== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
==8459==
==8459== 1 errors in context 1 of 1:
==8459== Invalid write of size 1
==8459== at 0x401435: load (dictionary.c:149)
==8459== by 0x40092D: main (speller.c:40)
==8459== Address 0x0 is not stack'd, malloc'd or (recently) free'd
==8459==
==8459== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
Segmentation fault

1 Answer 1

0

After new code post:

Once you are processing a word, you should never reference root again. This is wrong

current = root->children[index];

            // if first letter of word and pointer at that "letter" points to nothing
            //    then, create node
            if (i == 0 && root->children[index] == NULL)
            {
                root->children[index]->children[index] = calloc(1,sizeof(node));
                // move current to next node
                current = root->children[index]->children[index];
            }

The walkthrough shows each word as a "chain" from the root node, which is technically correct; but that is dramatized for demonstration purposes. Programatically, you are always going to start at the root node, but you are going build the path of the word by keeping track of the current node.

When you start a new word, before you iterate through the letters, you need to reset your pointer to the root node. Something like current = root. The path of the word will be built using the current pointer. Create a new node if necessary (when current->children[index] is NULL) and make it the current node (current = current->children[index]), or just make it the current node.

When it's done iterating through the letters (finishes the i loop), the current node is the last letter, so that's where is_word should be set.

root needs to be declared globally (ie node* root). When you declare it here node *root = calloc(1,sizeof(node)); in the load function, it can only be used by the load function. check will need access to root too. You only need root = calloc......

current can be declared locally. If you allocate it, as here, node *current = calloc(1,sizeof(node)); be sure to free it before exiting the function. It does not need to be allocated, however, since it will be "sharing" memory with root (ie. current = root).


Assuming root is the root node, you only want to create a child node at the index in root for first letter of each word. This test if (root->children[index] == NULL) will create a node at the index for each letter of the word, assuming the node doesn't exist, which is a fairly safe assumption for the first word.

The basic logic is good. You have to be at the root node when you start every word. Think about how to rework the existing code so that you 1) set current to root when it begins a word, and 2) only use current to build the trie - create a new node if necessary, or simply move to the next node.

The valgrind warnings are probably "unitialized" values. Here if (root->children[index] == NULL), for instance, you are testing for NULL but root->children[index] was not initialized. You can read up on calloc; it's a nice choice because it initializes for you. Otherwise, you'll need to initialize each of the children pointers to NULL wherever you create a new node.

I would expect the output for bat to be "bat 1 0 19 1":

bat from printf("%s\n", word);
1 0 19 from printf("%i\n", index); ('b' 'a' 't' respectively)
and 1 from printf("%i\n", size_count);

11
  • I thought that I fixed it by adding "if (i == 0 && root->children[index..." but instead I get a segmentation fault. Also, I can't figure out why the loading of the dictionary stops after the first word.
    – KitSeason
    Jun 26, 2017 at 18:25
  • Not sure what you mean "loading of the dictionary stops after the first word". Jun 26, 2017 at 21:31
  • It seems that the while loop only goes through one time when it should go through more than that. (printing each word in my mini-dictionary) I moved the return true outside the while loop. At the same time, it looks like my code still needs a lot of work as I am now getting a segmentation fault. I saved valgrind, but haven't quite figured how to read it yet. It appears though there are problems with initializing my variables and using malloc. Not sure -- should I edit above to add valgrind?
    – KitSeason
    Jun 26, 2017 at 22:30
  • Added info to the answer. Jun 27, 2017 at 3:10
  • I've updated my question to show my most recent code version and included the entire load function not just the while loop. I should note also, the typedef of the node struct occurs before the function definitions as well as "int size_count;" for use with size function.
    – KitSeason
    Jun 27, 2017 at 20:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .