0
bool load(const char *dictionary)
{
    // TODO
    FILE *fdict = fopen(dictionary, "r");
    if (fdict == NULL)
    {
        return false;
    }

    // create container string to hold word
    char *string = malloc(sizeof(LENGTH+1));
    if (string == NULL)
    {
        return false;
    }

    // initialize new node
    node *n = malloc(sizeof(node));
    if (n == NULL)
    {
        return false;
    }

    //condition begins by scanning file
    while (fscanf(fdict, "%s", string) != EOF)
    {
        // assign values to n
        n->next = NULL;
        strcpy(n->word, string);

        // obtain hashcode for table
        int hcode = hash(n->word);

        // if no elements at hcode, fill with n. else, attatch table[hcode] as next and slot n as table[hcode].
        if (table[hcode] == NULL)
        {
            table[hcode] = n;
        }
        else
        {
            n->next = table[hcode];
            table[hcode] = n;
        }
        count++;

        n = malloc(sizeof(node));
    }

    free(n);
    //n = NULL;
    free(string);
    fclose(fdict);
    return true;
} 

Load() was working perfectly, except that it would not load the first word in the large dictionary, "a". I debugged for a bit and found that after initiating fscan() at the point in the loop where the longest word ("pneumonoultramicroscopicsilicovolcanoconiosis") would be scanned by fscan(), the last 12 characters of the longest word would immediately replace "a" where it existed in its linked list on the hash table before any data is actually allocated into a linked list.

Node before error:node before error

Node after scanning long word:node after error

The memory address remains the same, for all intents and purposes it is the same node, but now the n->word value would be changed to "lcanoconiosis". Does anyone know what might cause this? I'm completely at a loss, as nothing touches the hash table at this point in the loop. Theoretically I could hardcode an exception in check() to always count "a", but I'd rather know what's happening in case this happens again.

EDIT: included text of code instead of code screenshot (10/5/23)

5
  • post your code here not images of your code
    – UpAndAdam
    Oct 4, 2023 at 21:00
  • thank you taking a look
    – UpAndAdam
    Oct 5, 2023 at 14:43
  • what do you mean by "replace 'a' where it existed in its linked list on the hash table before any days is actualy allocated into a linked list" if no data is allocated into the linked list then how is a there? do you mean before that word is put into the linked list? Are you checking that n is succeeding in it malloc calls? Also why bother with the string variable instead of just reading directly into n->word with the pattern you are using? Just wasting time on a strcopy. how is your node defined? also you are leaking memory on your return false cases.
    – UpAndAdam
    Oct 5, 2023 at 14:59
  • Hi UpAndAdam, I misspoke in saying no data has been loaded prior to this. I meant that in this iteration of the loop, the specific scanned string has not yet been loaded into the table. At this point in the program, about 58,000 other pieces of data have already been loaded into the table with no issue. For the string variable, I'm using it because that's what was suggested in the specifications, and I didn't know you could scan directly into n->word. I had been using string as a buffer to ensure that the data wasn't lost along the way. I am still troubleshooting valgrind leaks :)
    – Poptart
    Oct 6, 2023 at 1:30
  • valgrind or your compiler should also be complaining about your use of defined values in the area Cliff points out below. a good LINT tool or Compiler would absolutely detect that, but in practice I've often had to find them myself. Best practice is to always make sure your variables are initialized/assigned to before you read from them whether they are pointers or not.
    – UpAndAdam
    Oct 6, 2023 at 15:13

1 Answer 1

1

I suspect that this problem exists with each and every linked list that the table[] elements point to. (i.e., if the hash value is the first letter of each word, the first word in the dictionary file for each letter fails to show up in the table array.)

It would have been helpful to see the declaration of table, but I'll assume that it's the standard array of pointers to nodes.

The problem is that an important step is missing from the code. Look at this from your code:

// if no elements at hcode, fill with n. else, attatch table[hcode] as next and slot n as table[hcode].
    if (table[hcode] == NULL)
    {
        table[hcode] = n;
    }

The problem is that table[] is not initialized. When an array of pointers is declared, the array elements are NOT set to null by default. Instead, they contain whatever garbage data was left in physical memory. Since this is NOT NULL, the if test fails and the code assumes that there's a node there already.

So, the code goes to the else block, gets n->next, which is NULL and puts it in as the new node at the front of the list. The next node to be added will see that the first node is null now, and will insert the second node as the first node in the list. From here on, everything works as it should.

Simply put, every node in table MUST be set to NULL manually, using a for loop before table can be used and populated with live data.

Best practice: Pointers of any type should ALWAYS be immediately manually initialized, no matter what, either with NULL or live data at the time of their creation, to prevent this exact issue.

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)

5
  • Thanks for checking this out! table[] is declared at the top of the file, but I see that it hasn't actually been initialized. What's strange is that this error does not occur for any other item that gets loaded into the hash table; it's only this instance of the loop that causes this bug, and a similar type of bug does not appear anywhere else in the table. That being said, I'll likely make the changes you're suggesting anyway, but it doesn't appear that this is the issue that's causing the bug, otherwise I would assume it would pop up in other spots on the table. Thanks for your suggestion!
    – Poptart
    Oct 6, 2023 at 1:26
  • 1
    @Poptart its undefined behavior anything can happen. some can work right others can not work right. making any other assumptions is not possible until you fix this error. This is an important lesson you need to learn now and remember. Undefined behavior means undefined behavior; anecdotal evidence that other things are working doesn't mean you are safe. It could fail now it could fail later. That's why undefined behavior and testing are so important in programming.
    – UpAndAdam
    Oct 6, 2023 at 15:08
  • I would extend your best practice not just to pointers but to any data type. In C you can not assume the value of any declared variable until it is assigned.
    – UpAndAdam
    Oct 6, 2023 at 15:15
  • @UpAndAdam, you're exactly correct about undefined behavior. It could happening the way they describe because "A" may be table[0] and has garbage data, but the rest of the table may be zeroed out because the memory space simply hasn't been used in a lightly active system. In a busy environment, the entire table could contain non-zero garbage data. This is the definition of undefined behavior.
    – Cliff B
    Oct 6, 2023 at 17:19
  • 1
    As for best practice, yes, it's always good to initialize all vars. I do. Not necessary for any var type that is known to be initialized by the system, but there are so many data types in C that aren't, I find it best to initialize everything. Unless you're doing something that requires every grain of efficiency you can squeeze out, It's best to initialize everything.
    – Cliff B
    Oct 6, 2023 at 17:21

You must log in to answer this question.

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