0

I have put many controls into the code, simplified the hash function, used gdb extensively, all which suggest the code works yet it still fails the tests, especially words like Still, Home, Video, TIGHT, etc, even though when I put them in my own test they aren't misspelled. I would immensely appreciate any help!

     /****************************************************************************
     * dictionary.c
     *
     * Computer Science 50
     * Problem Set 5
     *
     * Implements a dictionary's functionality.
     ***************************************************************************/
    #include <stdint.h>
    #include <stdlib.h>
    #include <string.h>
    #include <strings.h>
    #include <stdbool.h>
    #include "dictionary.h"
    #include <stdio.h>
    #include <ctype.h>

    uint32_t adler32(const char *data, size_t len);


    int word_count = 0;
    bool loaded = false;



    typedef struct node
    {
        struct node* next;
        const char* word;
    }
    node;

    void free_em(node* ptr);

    node* hashtable[CAP];

    /**
     * Returns true if word is in dictionary else false.
     */
    bool
    check(const char *word)
    {
      char temp_word[LENGTH +1];
      node *nodep;

      //Convert to lower case

      int len = strlen(word);

      for(int i = 0; i < len; i++) {
        int low = tolower(word[i]);
        temp_word[i] = (char)low;
      }

      // Add the terminating char
      temp_word[len] = '\0';
                

      int hv = hash(word);
      nodep = hasht[hv];
      if (!nodep ) return false;//Not even a hash node created.
      
      // Else search in list


      while( nodep ) {
        if (!strcmp(word,temp_word)) {
        return true;
        }
        nodep = nodep->next;
      }

      return false;

    }

    /**
     * Loads dictionary into memory.  Returns true if successful else false.
     */
    bool load(const char* dictionary)
    {
        int collisions = 0;
        // node* hashtable[CAP];
        
        FILE* fp = fopen(dictionary, "r");
        if (fp == NULL)
        {
            return false;
        }
        else
        {
            while (!feof(fp))
            {
                
                char* word = malloc(sizeof(char) * (LENGTH + 1));
                
                fscanf(fp, "%s", word);
                
                node* new_node = malloc(sizeof(node));
                
                new_node->word = word;
                
                int index = adler32(new_node->word, strlen(new_node->word)) % CAP;
                
                if (hashtable[index] == NULL)
                {
                    hashtable[index] = new_node;
                    new_node->next = NULL;
                }
                else
                {
                    new_node->next = hashtable[index];
                    hashtable[index] = new_node;
                    collisions++;
                }
                
                word_count++;
            }
        }
        // printf("%d\n", collisions);
        fclose(fp);
        loaded = true;
        return true;
    }

    /**
     * Returns number of words in dictionary if loaded else 0 if not yet loaded.
     */
    unsigned int size(void)
    {
        if (loaded)
            return word_count;
        
        return 0; 
    }

    /**
     * Unloads dictionary from memory.  Returns true if successful else false.
     */
    bool unload(void)
    {
        if (loaded)
        {
            for (int i = 0, n = CAP; i < n; i++)
            {
                //node* cursor = malloc(sizeof(node));
                
                
                if (hashtable[n] != NULL)
                {
                    //cursor = hashtable[n];
                    free(hashtable[n]);
                    //free_em(cursor);
                }
            
            }
            return true;
        }
        return false;
    }



    const int MOD_ADLER = 65521;

    uint32_t adler32(const char *data, size_t len) /* where data is the location of the data in physical memory and 
                                                          len is the length of the data in bytes */
    {
        int hash = 0;
        int lengh = len;
        
        for (int i = 0; i < length; i++)
        {
            hash += word[i];
        }
        return hash;
    }


    void free_em(node* ptr)
    {
        if (ptr->next != NULL)
            free_em(ptr->next);
        free(ptr);
    }


    /**
    uint32_t adler32(const void *bufs, size_t buflength) {
         const uint8_t *buffer = (const uint8_t*)buf;

         uint32_t s1 = 1;
         uint32_t s2 = 0;

         for (size_t n = 0; n < buflength; n++) {
            s1 = (s1 + buffer[n]) % 65521;
            s2 = (s2 + s1) % 65521;
         }     
         return (s2 << 16) | s1;
    }
    **/


    /**

    bool strcasecomp(char* a, char* b)
    {
        if(strlen(a) == strlen(b))
        {
            for (int i = 0, n = strlen(a); i < n; i++)
            {
                if (tolower(a[i]) != tolower(b[i]))
                {
                    return false;
                }
                
                return true;
            }
        }
        return false;
    }

    **/
3
  • Haven't spent as much time in the program as you have, but this line int lengh = len; is suspicious because of spelling. – DinoCoderSaurus Dec 12 '15 at 16:35
  • The code posted doesn't compile. Is it possible that you posted an earlier version? It is missing the declaration for CAP, your hash function, adler32() uses a variable word[ ] that is undeclared inside the function or isn't passed to it, and of course, there's the previously mentioned typo. Please edit the question and add the code that compiles. – Cliff B Dec 12 '15 at 17:25
  • Yes, this was a slightly earlier version taken while I was implementing a new hash function. I've now fixed it. Thanks. – Paddy Dec 13 '15 at 0:36
0

This is still not compilable code. The lengh typo still exists. And unless it's declared in dictionary.h, hasht array appears out of nowhere. Here are some things to look at:

If your dictionary is {home, still, tight, video}, "TIGHT" will return false here:

int hv = hash(word);
  nodep = hasht[hv];
  if (!nodep ) return false;//Not even a hash node created.

This "word" if (!strcmp(word,temp_word)) { is the argument to "check", so "Still" et al will return false. You are not comparing to the "word" in the node.

You'd be well served to create a small test dictionary and text file and take this for a spin in gdb.

You must log in to answer this question.

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