1
\$\begingroup\$

I created a program for a college class. After I got it working, I wanted to improve it. As a beginner, it is probably a mess.

Description

It uses a HashFunction and a HashTable and quadratic probing for collisions. It will tell the user to enter a word and after that will check if that word exist in any of the 3 text files foo.txt, bar.txt, or foo2.txt. If the word is found in multiple files it will print "Word found in foo.txt & bar.txt".

Questions:

  1. Am I using dynamic allocation correctly?
  2. How could I make this code modular without breaking it?
  3. I'm getting a 85% of correct answers (word is found). However, some words are not found (maybe because collisions and not indexed correctly? Should I use another hash function?).
  4. Are there any general or beginners errors that you've found, or things that could make it better, more elegant ,better use of dynamic allocation?
  5. Any tips or suggestions for the future?

Current code (running and finding words):

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TABLESIZE 4001
#define LINESIZE 2048
#define DELIMITER " \t"

typedef struct TTable {
    char*   Word;               /* The actual word  */
    int     Documents[5];           /* Documents Index */
    int     DocumentsCount;             /* Number of documents where the word exist */
} TTable;


int Hash (char *Word);
void Index (TTable **HashTable, char* Word, int DocumentIndex);
int Search (TTable **HashTable, char* Word);
int mystrcmp(char *s1, char *s2);
char* Documents[] = {"foo.txt","bar.txt","foo2.txt",NULL};


int main() {

    FILE* file;
    TTable **HashTable;
    int DocumentIndex;
    char Line[LINESIZE];
    char* Word;
    char* Tmp;

    HashTable = (TTable**) malloc (sizeof(TTable)*TABLESIZE);
    for (int i = 0; i < TABLESIZE; i++) {
      HashTable[i] = (TTable*) NULL;
    }

    for (DocumentIndex = 0; Documents[DocumentIndex] != NULL; DocumentIndex++) {

      file = fopen(Documents[DocumentIndex],"r");
      if (file == NULL) {

          fprintf(stderr, "Error%s\n", Documents[DocumentIndex]);
          continue;

      }


      while (fgets (Line,LINESIZE,file) != NULL) {

          Line[LINESIZE-1] = '\0';
          Tmp = strtok (Line,DELIMITER);

          do {

              Word = (char*) malloc (strlen(Tmp)+1);
              strcpy(Word,Tmp);
              Index(HashTable,Word,DocumentIndex);
              Tmp = strtok(NULL,DELIMITER);
          } while (Tmp != NULL);

      }

        fclose(file);

    }


        printf("Enter the word:");
        fgets(Line,100,stdin);
        Line[strlen(Line)-1]='\0'; //fgets stores newline as well. so removing newline.
        int i = Search(HashTable,Line);
        if (i != -1) {
          for (int j = 0; j < HashTable[i]->DocumentsCount; j++) {
            printf("%s\n", Documents[HashTable[i]->Documents[j]]);
            if ( j < HashTable[i]->DocumentsCount-1) {

                printf(",");
            }
          }
        }

        else {
          printf("Cant find word\n");
        }


        for (i = 0; i < TABLESIZE; i++) {
          if (HashTable[i] != NULL) {

              free(HashTable[i]->Word);
              free(HashTable[i]);

          }
        }


return 0;
}

/* Theorem: If TableSize is prime and ? < 0.5, quadratic
probing will always find an empty slot
*/
int Search (TTable **HashTable, char* Word) {

    int Aux = Hash(Word);
    int OldPosition,ActualPosition;

    ActualPosition = -1;

    for (int i = 0; i < TABLESIZE; i++) {
      OldPosition = ActualPosition;
      ActualPosition = (Aux + i*i) % TABLESIZE;

      if (HashTable[ActualPosition] == NULL) {
        return -1;
      }

    if (strcmp(Word,HashTable[ActualPosition]->Word) == 0) {

        return ActualPosition;

    }
    }

    return -1; // Word not found
}


void Index (TTable **HashTable, char* Word, int DocumentIndex) {

    int Aux; //Hash value
    int OldPosition, ActualPosition;

    if ((ActualPosition = Search(HashTable,Word)) != -1) {

        for (int j = 0; j < HashTable[ActualPosition]->DocumentsCount;j++) {

            if(HashTable[ActualPosition]->Documents[j] == DocumentIndex) {
              return;
            }

        }

        HashTable[ActualPosition]->Documents[HashTable[ActualPosition]->DocumentsCount] = DocumentIndex;        HashTable[ActualPosition]->DocumentsCount++;
        return;
    }

    ActualPosition = -1;
    Aux = Hash(Word);

    for (int i = 0; i < TABLESIZE; i++) {

        OldPosition = ActualPosition;
        ActualPosition = (Aux + i*i) % TABLESIZE;
        if (OldPosition == ActualPosition) {
          break;
        }

    if (HashTable[ActualPosition] == NULL) {

        HashTable[ActualPosition] = (TTable*)malloc (sizeof(TTable));
        HashTable[ActualPosition]->Word = Word;
        HashTable[ActualPosition]->Documents[0] = DocumentIndex;
        HashTable[ActualPosition]->DocumentsCount = 1;
        return;
    }

    }

    printf("No more free space\n");

}


int Hash (char *Word) {

    int HashValue;
    for (HashValue = 0; *Word != '\0';) {
      HashValue += *Word++;
    }

    return (HashValue % TABLESIZE);
}
\$\endgroup\$
1
\$\begingroup\$

Key criticism. problem #4. Hash table size is fixed. A table that intelligently re-sizes as needed is more generally useful. Yet this is a good start.

  1. Allocation is incorrect size. But since code over allocates, it is just wasteful. problem #1

    // HashTable = (TTable**) malloc (sizeof(TTable)*TABLESIZE);
    // could be                                  v  
    HashTable = (TTable**) malloc (sizeof(TTable *)*TABLESIZE);
    // or better, drop the unneeded cast
    HashTable = malloc (sizeof(TTable *)*TABLESIZE);
    // best, sizeof the the refenced variable rather than the type
    // Easy to code, less chance for error, easier to review and maintin
    HashTable = malloc (sizeof *HashTable * TABLESIZE);
    
  2. Good use of number theory. With a prime mod, such as 4001, this will improve a weak pre-hash function , such as HashValue += *Word++; and will not harm a good one.

    #define TABLESIZE 4001
    ...
    return (HashValue % TABLESIZE);`
    
  3. Strongly suspect needs to tokenize \n as a delimiter else it ends up as part of a word. Might as well use all standard 7 whites-spaces. Likely source of problem #3

    // #define DELIMITER " \t"
    #define DELIMITER " \t\n\r\v\a\f"
    
  4. Missing free(HashTable)

  5. Avoid a hacker exploit. The first character read by fgets() may be a null character. Test result too.

    // fgets(Line,100,stdin);
    // Line[strlen(Line)-1]='\0';
    if (fgets(Line, sizeof Line, stdin) == NULL) Handle_Problem();
    Line[strcspn(Line, "\n")] = '\0';
    
  6. Lack of size protection. I see no code to prevent j getting too large for HashTable[ActualPosition]->Documents[].

    for (int j = 0; j < HashTable[ActualPosition]->DocumentsCount;j++) {
        if(HashTable[ActualPosition]->Documents[j] == DocumentIndex) {
    
  7. Use overflow protection. What prevents Aux + i*i from int undefined behavior on overflow? Suggest unsigned types and math

    // int Aux = Hash(Word);
    // ....
    // for (int i = 0; i < TABLESIZE; i++) {
    //  ...
    //  ActualPosition = (Aux + i*i) % TABLESIZE;
    
    unsigned Aux = Hash(Word);
    ....
    for (unsigned i = 0; i < TABLESIZE; i++) {
      ...
      ActualPosition = (Aux + i*i) % TABLESIZE;
    

Minor Stuff problem #5

  1. Always like a name and and year in the file header.

  2. Avoid naked magic numbers

    // int     Documents[5];  
    #define DOCUMENT_MAX 5
    int     Documents[DOCUMENT_MAX];
    
  3. No need for cast

    // HashTable[i] = (TTable*) NULL;
    HashTable[i] = NULL;
    // Word = (char*) malloc (strlen(Tmp)+1);
    // Word = malloc(strlen(Tmp) + 1);
    
  4. No need for compare to NULL;

    // for (DocumentIndex = 0; Documents[DocumentIndex] != NULL; DocumentIndex++) {
    for (DocumentIndex = 0; Documents[DocumentIndex]; DocumentIndex++) {
    
    // while (fgets (Line,LINESIZE,file) != NULL) {
    while (fgets(Line, LINESIZE, file)) {
    
  5. size_t is the best type for array indexing, not to wide, not too narrow. int may be undersized.

    // int DocumentIndex;
    size_t DocumentIndex;
    
  6. Useless code. Serves no purpose. Line is null character terminated.

    // Line[LINESIZE-1] = '\0';
    ;
    
  7. Style: Why do some functions have space between the name and the (. Suggest uniformity. This implies code is not auto-formatted. Use auto-formatting.

  8. Functions that do not modify the referenced data should have const pointers. This allows additional optimizations and conveys codes intent.

    // int mystrcmp(char *s1, char *s2);
    int mystrcmp(const char *s1, const char *s2);
    // int Hash (char *Word) {
    int Hash (const char *Word) {
    
  9. Curious indentation. Use an auto formatter.

    // various places.
    return 0;
    }
    
  10. Avoid long code lines. With auto formating, this is easy.

    // HashTable[ActualPosition]->Documents[HashTable[ActualPosition]->DocumentsCount] = DocumentIndex;        HashTable[ActualPosition]->DocumentsCount++;
    

or this ?

    HashTable[ActualPosition]->Documents[HashTable[ActualPosition]->DocumentsCount] = 
        DocumentIndex;
    HashTable[ActualPosition]->DocumentsCount++;

Enough for now.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.