Problems with Hash Tables

This is a discussion on Problems with Hash Tables within the C Programming forums, part of the General Programming Boards category; Hello, I'm currently working on a Hash Table that takes strings as keys and maps them to any sort of ...

  1. #1
    Registered User
    Join Date
    Sep 2003
    Posts
    69

    Problems with Hash Tables

    Hello,

    I'm currently working on a Hash Table that takes strings as keys and maps them to any sort of object. Here is my Hash Table module:

    Code:
    // Header file
    #define HASHSIZE 101
    
    struct entry { struct entry *next; char* name; void* defn; };
    typedef struct hashtable { struct entry* hashtab[HASHSIZE]; } HT;
    
    void newHT(HT* , int );
    void* getHT(HT* , char* );
    void* putHT(HT* , char* , void* );
    unsigned hash(char* );
    
    // implementation
    #include "HT.h"
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    int size;
    
    void newHT(HT* p, int tableSize) {
       size = tableSize;
    }
    
    void* getHT(HT* p, char* s) {
       struct entry* np;
       
       for (np = p->hashtab[hash(s)]; np != NULL; np = np->next)
          if (strcmp(s,np->name) == 0) return np->defn;
       return NULL;
    }
    
    void* putHT(HT* p, char* name, void* defn) {
       struct entry* np;
       unsigned hashval;
       
       if ((np = getHT(p,name)) == NULL) {
          np = (struct entry *) malloc(sizeof(*np));
          if (np == NULL || (np->name = name) == NULL)
             return NULL;
          hashval = hash(name);
          np->next = p->hashtab[hashval];
          p->hashtab[hashval] = np;
       }
       else
          free((void*)np->defn);
       if ((np->defn = defn) == NULL)
          return NULL;
       return np;
    }
    
    /* hash: form hash value for string s */
    unsigned hash(char *s) {
       unsigned hashval;
       
       for (hashval = 0; *s != '\0'; s++)
          hashval = *s + 31 * hashval;
       return hashval % size;
    }
    What I'm trying to do is insert objects that are another module I created called TeamRecord. Here is the code for that:

    Code:
    // Header file
    typedef struct grecord {
       char* team1;
       char* team2;
       int score1, score2;
    } GameRecord;
    
    typedef struct trecord { 
       char* name;
       int totPoints, goalsFor, goalsForInGame, goalsAgainst, goalsAgInGame, gamesPlayed;
       GameRecord* games[100];
    } TeamRecord;
    
    void newTeamRecord(TeamRecord *,char *);
    void totalPoints(TeamRecord *);
    void totalGoals(TeamRecord *, int );
    void goalsAgainst(TeamRecord *, int );
    void gameList(TeamRecord *, GameRecord*);
    void output(TeamRecord *);
    void newGameRecord(GameRecord*,char *,char *,int ,int );
    void outputGame(GameRecord*);
    
    //implementation
    #include "TeamRecord.h"
    #include <stdio.h>
    #include <string.h>
    
    void newTeamRecord(TeamRecord *tr, char* name) {
       tr->name = name;
       tr->goalsFor = 0;
       tr->goalsAgainst = 0;
       tr->gamesPlayed = 0;
    }
    
    void totalPoints(TeamRecord *tr) {
       if (tr->goalsForInGame > tr->goalsAgInGame) tr->totPoints += 2;
       else if (tr->goalsForInGame == tr->goalsAgInGame) tr->totPoints++;
    }
    
    void totalGoals(TeamRecord *tr, int goals) {
       tr->goalsForInGame = 0; 
       tr->goalsFor += goals;
       tr->goalsForInGame += goals;
    }
    
    void goalsAgainst(TeamRecord *tr, int goals) {
       tr->goalsAgInGame = 0;
       tr->goalsAgainst += goals;
       tr->goalsAgInGame += goals;
    }
    
    void gameList(TeamRecord *tr, GameRecord* game) {
       tr->games[tr->gamesPlayed] = game;
       tr->gamesPlayed++;
    }
    
    void output(TeamRecord *tr) {
        int i;
        printf("%s %d %d %d %d ",tr->name,tr->totPoints,tr->goalsFor,tr->goalsAgainst,tr->gamesPlayed);
        for (i = 0; i < tr->gamesPlayed; i++)
           outputGame(tr->games[i]);
        putchar('\n');
    }
    
    void newGameRecord(GameRecord* gr,char* team1, char* team2, int score1, int score2) {
       gr->team1 = team1;
       gr->team2 = team2;
       gr->score1 = score1;
       gr->score2 = score2;
    }
    
    void outputGame(GameRecord* gr) {
       printf("[ %s %d %s %d ]", gr->team1, gr->score1, gr->team2, gr->score2);
    }
    I know that both of these work on their own. I created test programs for both and they both appeared to work correctly. However, when I try to insert TeamRecords (created from lines in stdin), I get bizarre output. Here is my code where I'm putting the TeamRecords into the Hash Table.

    Code:
    #include "HT.h"
     #include "TeamRecord.h"
     #include <stdio.h>
     #include <stdlib.h>
     #include <string.h>
     
     main() {
        char buf[BUFSIZ];
        char* team1;
        char* team2;
        char* keys[100];
        int score1, score2,keyNum = 0,i;
    
        HT map;
        newHT(&map,101);
        
        while( fgets(buf,BUFSIZ,stdin) ) {
           team1 = strtok(buf," ");
           score1 = atoi(strtok(NULL," "));
           team2 = strtok(NULL," ");
           score2 = atoi(strtok(NULL,"\n"));
           
           GameRecord game;
           newGameRecord(&game,team1,team2,score1,score2);
           
           TeamRecord temp;
           
           if(getHT(&map,team1) != NULL) {
              gameList((TeamRecord*)getHT(&map,team1),&game);
              totalGoals((TeamRecord*)getHT(&map,team1),score1);
              goalsAgainst((TeamRecord*)getHT(&map,team1),score2);
              totalPoints((TeamRecord*)getHT(&map,team1));
           }
           else {
              newTeamRecord(&temp,team1);
              gameList(&temp,&game);
              totalGoals(&temp,score1);
              goalsAgainst(&temp,score2);
              totalPoints(&temp);
              putHT(&map,team1,&temp);
              keys[keyNum] = team1;
              keyNum++;
           }
    
           if(getHT(&map,team2) != NULL) {
              gameList((TeamRecord*)getHT(&map,team2),&game);
              totalGoals((TeamRecord*)getHT(&map,team2),score2);
              goalsAgainst((TeamRecord*)getHT(&map,team2),score1);
              totalPoints((TeamRecord*)getHT(&map,team2));
           }
           else {
              newTeamRecord(&temp,team2);
              gameList(&temp,&game);
              totalGoals(&temp,score2);
              goalsAgainst(&temp,score1);
              totalPoints(&temp);
              putHT(&map,team2,&temp);
              keys[keyNum] = team2;
              keyNum++;
              
           }
           free(&temp);
           free(&game);
        }
    
        for (i = 0; i < keyNum; i++) {
           output((TeamRecord*)getHT(&map,keys[i]));
        }
     }
    When I run this with input like this:
    Dal 4 SMU 2

    My output looks like this:
    SMU 1936666163 2 4 1 [ Dal 4 SMU 2 ]
    SMU 1936666163 2 4 1 [ Dal 4 SMU 2 ]

    It should look like this:
    Dal 2 4 2 1 [ Dal 4 SMU 2 ]
    SMU 0 2 4 1 [ Dal 4 SMU 2]

    I think I'm doing something wrong with TeamRecord temp. It seems like only one TeamRecord gets created and is changed with each new team. Also, the total points number (the second number in the output) is messed up for some reason. Can anyone figure out what's wrong with this? I've been working at it for a couple of days and can't figure out what's going on.

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    1) Both of these are wrong:
    Code:
    free(&temp);
    free(&game);
    Because:
    Code:
    GameRecord game;
    ...
    TeamRecord temp;
    Neither of those are pointers. You don't 'free' automatic variables. You only free pointers. These are automaticly destructed when the program exits.

    2) However:
    Code:
    typedef struct grecord {
       char* team1;
       char* team2;
       int score1, score2;
    } GameRecord;
    
    typedef struct trecord { 
       char* name; 
       int totPoints, goalsFor, goalsForInGame, goalsAgainst, goalsAgInGame, gamesPlayed;
       GameRecord* games[100]; 
    } TeamRecord;
    None of the hilighted items are freed correctly. You need to free them implicitly.

    3) This:
    Code:
    score2 = atoi(strtok(NULL,"\n"));
           
           GameRecord game; 
           newGameRecord(&game,team1,team2,score1,score2);
           
           TeamRecord temp; 
           
           if(getHT(&map,team1) != NULL) {
    Is not valid C. You cannot just throw new variable declarations in mid-block like this in C. In C++, yes, but in C, no. (Unless they added it in C99, and if then, only if your compiler is C99 compliant.)

    4) You never check for NULL:
    Code:
    void output(TeamRecord *tr) {
        int i;
        printf("%s %d %d %d %d ",tr->name,tr->totPoints,tr->goalsFor,tr->goalsAgainst,tr->gamesPlayed);
        for (i = 0; i < tr->gamesPlayed; i++)
           outputGame(tr->games[i]);
        putchar('\n');
    }
    So to follow this train of thought:
    Code:
    for (i = 0; i < keyNum; i++) {
           output((TeamRecord*)getHT(&map,keys[i]));
        }
    It is definately possible for...
    Code:
    void* getHT(HT* p, char* s) {
       struct entry* np;
       
       for (np = p->hashtab[hash(s)]; np != NULL; np = np->next)
          if (strcmp(s,np->name) == 0) return np->defn;
       return NULL;
    }
    ...you to be trying to display the contents of a non-existing game.

    You also don't show us your HT header, so I can only guess that your hash is working right. That's my few minutes glance.

    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Registered User
    Join Date
    Sep 2003
    Posts
    69
    Ok, I changed my code around a bit, to follow what I think you're saying. Here is my code now:

    Code:
     #include "HT.h"
     #include "TeamRecord.h"
     #include <stdio.h>
     #include <stdlib.h>
     #include <string.h>
     
     main() {
        char buf[BUFSIZ];
        char* team1;
        char* team2;
        char* keys[100];
        int score1, score2,keyNum = 0,i;
        GameRecord* game;
        TeamRecord* temp;
    
        HT* map;
        newHT(map,101);
        
        while( fgets(buf,BUFSIZ,stdin) ) {
           team1 = strtok(buf," ");
           score1 = atoi(strtok(NULL," "));
           team2 = strtok(NULL," ");
           score2 = atoi(strtok(NULL,"\n"));
           
           newGameRecord(game,team1,team2,score1,score2);
           
           if(getHT(map,team1) != NULL) {
              gameList((TeamRecord*)getHT(map,team1),game);
              totalGoals((TeamRecord*)getHT(map,team1),score1);
              goalsAgainst((TeamRecord*)getHT(map,team1),score2);
              totalPoints((TeamRecord*)getHT(map,team1));
           }
           else {
              newTeamRecord(temp,team1);
              gameList(temp,game);
              totalGoals(temp,score1);
              goalsAgainst(temp,score2);
              totalPoints(temp);
              putHT(map,team1,temp);
              keys[keyNum] = team1;
              keyNum++;
           }
           
           if(getHT(map,team2) != NULL) {
              gameList((TeamRecord*)getHT(map,team2),game);
              totalGoals((TeamRecord*)getHT(map,team2),score2);
              goalsAgainst((TeamRecord*)getHT(map,team2),score1);
              totalPoints((TeamRecord*)getHT(map,team2));
           }
           else {
              newTeamRecord(temp,team2);
              gameList(temp,game);
              totalGoals(temp,score2);
              goalsAgainst(temp,score1);
              totalPoints(temp);
              putHT(map,team2,temp);
              keys[keyNum] = team2;
              keyNum++;
              
           }
           free(temp);
           free(game);
        }
    
        for (i = 0; i < keyNum; i++) {
           output((TeamRecord*)getHT(map,keys[i]));
        }
     }
    Now when I compile and run it, I get a segmentation fault. I'm not really familiar with freeing pointers and such. Maybe you could show me code on how to do the things you're suggesting? Also, here is my HT header:

    Code:
    #define HASHSIZE 101
    
    struct entry { struct entry *next; char* name; void* defn; };
    typedef struct hashtable { struct entry* hashtab[HASHSIZE]; } HT;
    
    void newHT(HT* , int );
    void* getHT(HT* , char* );
    void* putHT(HT* , char* , void* );
    unsigned hash(char* );
    Thanks for the help. I really appreciate it.

  4. #4
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    Where do you malloc name and temp?
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  5. #5
    Registered User
    Join Date
    Sep 2003
    Posts
    69
    Um, no where? Should I be? I don't really know much about malloc.

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Originally posted by Zildjian
    Um, no where? Should I be? I don't really know much about malloc.
    Yep. If you actually expect them to store something you'd better. Otherwise all you're doing is making pointers. Pointers don't contain any space for you to put anything, they just point to something that's already there.

    If there is nothing there for them to point at, then you need to make them point to:
    a) a variable that is automaticly allocated, as in this case:
    Code:
    int x;
    int *ptr;
    
    ptr = &x; /* make ptr point to x */
    Or...
    b) dynamicly create space for them, as shown here:
    Code:
    int *ptr;
    
    ptr = malloc( sizeof( int ) ); /* 'ptr' points to dynamicly allocated memory now, assuming malloc doesn't fail */
    
    if( ptr != NULL )
        printf("malloc didn't fail");
    And remember, anything you malloc or calloc, you have to free. That's the only time you use free, for something you dynamicly allocate.

    Quzah.
    Hope is the first step on the road to disappointment.

  7. #7
    Registered User
    Join Date
    Sep 2003
    Posts
    69
    Ok, thanks for the quick lesson in malloc. Would've been nice if my prof had done that, but whatever. My program is working better now, however, when I give it more than one line of input, it seems to only act on the last line of input. In other words, it's changing what my TeamRecord variables have stored in them. Here is my code now:

    Code:
    #include "HT.h"
     #include "TeamRecord.h"
     #include <stdio.h>
     #include <stdlib.h>
     #include <string.h>
     
     main() {
        char buf[BUFSIZ];
        char* team1;
        char* team2;
        char* keys[100];
        int score1, score2,keyNum = 0,i;
        GameRecord* game;
        TeamRecord* temp;
        TeamRecord* temp2;
        HT* map;
        
        map = malloc( sizeof(HT) );
        
        newHT(map,101);
        
        while( fgets(buf,BUFSIZ,stdin) ) {
           team1 = strtok(buf," ");
           score1 = atoi(strtok(NULL," "));
           team2 = strtok(NULL," ");
           score2 = atoi(strtok(NULL,"\n"));
           
           game = malloc( sizeof(GameRecord) );
           temp = malloc( sizeof(TeamRecord) );
           temp2 = malloc( sizeof(TeamRecord) );
           
           newGameRecord(game,team1,team2,score1,score2);
           
           if(getHT(map,team1) != NULL) {
              gameList((TeamRecord*)getHT(map,team1),game);
              totalGoals((TeamRecord*)getHT(map,team1),score1);
              goalsAgainst((TeamRecord*)getHT(map,team1),score2);
              totalPoints((TeamRecord*)getHT(map,team1));
           }
           else {
              newTeamRecord(temp,team1);
              gameList(temp,game);
              totalGoals(temp,score1);
              goalsAgainst(temp,score2);
              totalPoints(temp);
              putHT(map,team1,temp);
              keys[keyNum] = team1;
              keyNum++;
           }
      
           if(getHT(map,team2) != NULL) {
              gameList((TeamRecord*)getHT(map,team2),game);
              totalGoals((TeamRecord*)getHT(map,team2),score2);
              goalsAgainst((TeamRecord*)getHT(map,team2),score1);
              totalPoints((TeamRecord*)getHT(map,team2));
           }
           else {
              newTeamRecord(temp2,team2);
              gameList(temp2,game);
              totalGoals(temp2,score2);
              goalsAgainst(temp2,score1);
              totalPoints(temp2);
              putHT(map,team2,temp2);
              keys[keyNum] = team2;
              keyNum++;
              
           }
           free(temp);     
           free(temp2);
           free(game);
        }
    
        for (i = 0; i < keyNum; i++) {
           output((TeamRecord*)getHT(map,keys[i]));
        }
     }
    When I give it input like this:
    Dal 4 SMU 2
    SMU 3 SFX 2
    SFX 1 Dal 1

    I get output like this:
    SMU 4 3 2 1 [ SMU 3 SFX 2 ]
    SFX 0 2 3 1 [ SMU 3 SFX 2 ]
    SMU 4 3 2 1 [ SMU 3 SFX 2 ]
    SFX 0 2 3 1 [ SMU 3 SFX 2 ]

    I should be getting output like this:
    Dal 3 5 3 2 [Dal 4 SMU 2] [SFX 1 Dal 1]
    SFX 1 3 4 2 [SMU 3 SFX 2] [SFX 1 Dal 1]
    SMU 2 5 6 2 [Dal 4 SMU 2] [SMU 3 SFX 2]

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. File I/O - Hash files
    By I BLcK I in forum C++ Programming
    Replies: 3
    Last Post: 04-29-2009, 02:30 AM
  2. Dictionary in C# to hash table in C?
    By dinoman in forum C Programming
    Replies: 2
    Last Post: 04-12-2009, 10:23 PM
  3. Problem with unaligned intrinsics
    By The Wazaa in forum C++ Programming
    Replies: 4
    Last Post: 02-18-2009, 12:36 PM
  4. Hash algorithm suggestions
    By itsme86 in forum C Programming
    Replies: 4
    Last Post: 08-06-2004, 01:05 PM
  5. hash tables
    By iain in forum C++ Programming
    Replies: 3
    Last Post: 12-08-2001, 04:10 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21