Problems with Hash Tables

**Zildjian** · 11-06-2003

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.

**quzah** · 11-06-2003

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.

**Zildjian** · 11-06-2003

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.

**XSquared** · 11-06-2003

Where do you malloc name and temp?

**Zildjian** · 11-06-2003

Um, no where? Should I be? I don't really know much about malloc.

**quzah** · 11-06-2003

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.

**Zildjian** · 11-06-2003

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]

Thread: Problems with Hash Tables

Thread Tools

Search Thread

Display

Problems with Hash Tables

Similar Threads

File I/O - Hash files

Dictionary in C# to hash table in C?

Problem with unaligned intrinsics

Hash algorithm suggestions

hash tables