0

My code below is taking a text file and hashing it, keys will be English words, values will be the Spanish translation.

My code crashes when it goes into the function insertHash, specifically the while loop below

while(hashTable[hashIndex].marker == 1)
    {
        printf("%d loop of hash index \n", i);
        hashIndex = (hashIndex+1)%tableSize;
        i++;
    }

Please ignore the i++ and printf, those are for debugging purposes.
The function itself does not even go through one iteration, just crashes.
Any help is appreciated, code is below:

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>

    int numofEle = 0;
    const int STEPSIZE = 100;
    //Hash table structure
    struct node *hashTable;
    struct node{
        int marker;
        char *key;
        char *value;
    };

    //function declaration
    char **loadfile(char *filename, int *len);

    //Hash function for strings;
    unsigned long hash(unsigned char *str)
    {
        unsigned long hash = 5381;
        int c;

        while (c = *str++)
            hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

        return hash;
    }
    //Function to insert elements in hash table
    void insertHash(int len, char *words){
        printf("Just entered insert hash function \n");
        int hashKey, hashIndex;
        int tableSize = len;
        printf("before hashing\n");
        hashKey = hash(words);
        printf("after hashing\n");
        hashIndex = hashKey % tableSize;
        printf("After hash index \n");
        if(numofEle == tableSize)
        {
            printf("The hash table is full\n.");
            return;
        }
        printf("before checking for marker\n");
        while(hashTable[hashIndex].marker == 1)
        {
            hashIndex = (hashIndex+1)%tableSize;
        }
        printf("After checking index \n");
        strcpy(hashTable[hashIndex].key, strtok(words, "\t"));
        strcpy(hashTable[hashIndex].value, strtok(NULL, "\t"));
        hashTable[hashIndex].marker = 1;
        printf("After assigning variables to table \n");
        numofEle++;

        return;
    }
    //Function to search for element
    void searchElement(char *key, int len, int *totalProbe)
    {
        int count = 0;
        int probe = 0;
        int flag = 0;
        char search;
        int hashKey = hash(key);
        int tableSize = len;
        int hashIndex = hashKey % tableSize;

        if(numofEle == 0)
        {
            printf("Hash Table is empty\n.");
            return;
        }
        printf("Probes|  keys\n");
        printf("    %d|     0\n", probe);

        while(hashTable[hashIndex].marker != 0 && count <= tableSize)
        {
            probe++;
            if(hashTable[hashIndex].key == key)
            {
                printf("The word %s ", key);
                printf("translate to %s.\n", hashTable[hashIndex].value);
                flag = 1;
                break;
            }
            else
            {
                printf("    %d|    %d\n", probe, hashIndex);
            }
            hashIndex = (hashIndex+1) % tableSize;
        }

        if(!flag)
        {
            printf("Given data is not here\n.");
        }

        *totalProbe = probe;
        return;
    }

    int main(int argc, char *argv[])
    {
        //Check for readable input
        if(argc == 1)
        {
            fprintf(stderr, "Must supply a file name to read.\n");
            exit(1);
        }
        int i, totalProbe;
        int len = 0;
        //Function to read text into array
        char **words = loadfile(argv[1], &len);
        printf("After loading files\n ");
        //allocating memory for hash table and elements
        struct node *hashTable = malloc(sizeof(struct node)* len);
         printf("After struct allocation\n");
        for(i = 0; i < len; i++)
        {
            hashTable[i].key = malloc(300 * sizeof(char));
            hashTable[i].value = malloc(300 * sizeof(char));
            hashTable[i].marker =(int*)malloc(sizeof(int));
        }
        for(i = 0; i < len; i++)
        {
            hashTable[i].marker = 0;
        }
         printf("After allocation for table elements\n");
        //Loop to hash and insert elements
        int totalHash = len;
        for(i = 0; i < len; i++)
        {
            insertHash(len, words[i]);
            totalHash--;
        }
         printf("After hashing words");
        char input[100];
        printf("Hash Table:\n");
        printf("total NOT hashed: %d out of %d\n", totalHash, len);

        printf("Please enter key: \n");
        scanf("%s", input);

        searchElement(input, len, &totalProbe);
        printf("max_run of probes = %d\n", totalProbe);

        return (EXIT_SUCCESS);
    }

    //Reads large files into array
    char **loadfile(char *filename, int *len)
    {
        FILE *fp = fopen(filename, "r");
        if(!fp)
        {
            fprintf(stderr, "Can't open %s for reading.\n", filename);
            return NULL;
        }

        int arrlen = STEPSIZE;

        //Allocate space for 100 char pointers.
        char **lines = (char**)malloc(arrlen*sizeof(char*));

        char buff[10000];
        int i = 0;

        while(fgets(buff, 10000, fp))
        {
            //Check for full array, if so, extend the array
            if(i == arrlen)
            {
                arrlen += STEPSIZE;
                char **newlines = realloc(lines, arrlen*sizeof(char*));
                if(!newlines)
                {
                    fprintf(stderr, "Can't reallocate\n");
                    exit(1);
                }
                lines = newlines;
            }
            // trim off \0 at the end
            buff[strlen(buff)-1] = '\0';
            //get length of buffer
            int blen = strlen(buff);

            char *str = (char*)malloc((blen+1)*sizeof(char));

            //copy string from buff to structure
            strcpy(str, buff);

            lines[i] = str;

            i++;
        }

        *len = i; //Set length of char pointers
        return lines;
}
Cuong Nguyen
  • 3
  • 2
  • If it doesn't go through one iteration, it suggests that either `hashTable` is not pointing anywhere valid or `hashIndex` is out of bounds (too big or too small). Run the code in a debugger, set a breakpoint on the function, and run the program. Or just run it in the debugger and wait for it to crash and then do the post mortem analysis Or add assertions that you think should be valid and see whether those fire instead (indicating that the assertions weren't satisfied: `assert(hashTable != NULL):` and `assert(hashIndex >= 0 && hashIndex < maxHashIndex);` or something similar. – Jonathan Leffler Dec 05 '16 at 06:29
  • 2
    Heed your compiler warnings: `hashTable[i].marker =(int*)malloc(sizeof(int));` is wrong. The `marker` member is `int`, not `int*`. And fyi, `hash` returns `unsigned long`, so saving to `int` seems optimistic. – WhozCraig Dec 05 '16 at 06:29
  • check for `malloc` return – Dilip Kumar Dec 05 '16 at 06:36
  • Please remove the four unnecessary spaces before each line. – MD XF Dec 05 '16 at 06:39
  • @WhozCraig will the hash function perform subpar if I change it to int instead of leaving it as unsigned? I also changed the cast to int but it's still crashing. – Cuong Nguyen Dec 05 '16 at 06:40
  • @DilipKumar what do you mean by checking for malloc in return? – Cuong Nguyen Dec 05 '16 at 06:40
  • @CuongNguyen check whether malloc has returned successfully with valid address without any error, an option to reduce chances of memory crash. This link might be helpful http://stackoverflow.com/questions/5607455/checking-that-malloc-succeeded-in-c – Dilip Kumar Dec 05 '16 at 06:44
  • @DilipKumar the check returns non null pointers, so the it was malloc successfully. – Cuong Nguyen Dec 05 '16 at 06:57

1 Answers1

2

Two things :

1.You need to declare struct node *hashTable below the structure definition,

//Hash table structure    
//struct node *hashTable; <--- incorrect
struct node{
    int marker;
    char *key;
    char *value;
};
struct node *hashTable;

2.You are re-declaring struct node *hashTable in main().

struct node *hashTable = malloc(sizeof(struct node)* len);

The scope of this pointer will be local.

You have already declared struct node *hashTable globally.

Use :

hashTable = (struct node *)malloc(sizeof(struct node)* len);

3.why are you dynamically allocating memory for marker? It is an int member of struct node. It has sizeof(int) bytes of memory.

hashTable[i].marker =(int*)malloc(sizeof(int)); ---> Not needed. You can comment it.

Akshay Patole
  • 454
  • 3
  • 14