views:

193

answers:

2

I have been cutting my teeth for the past 48 hours or so trying to implement this hash table function in C. My code is rather long (I realize it is not the most efficient, some of it is more me playing around with C to get a feel for how it works etc).

The problem I am having is with the last line of my main program at the bottom (printing MyEntry->Name). I am receiving a bus error and am unsure why. I do not believe I am supposed to allocate memory in the main driver for this pointer but I could be wrong.

Sorry about the length of this code. BTW SymEntry is 'struct SymEntry{char *Name, void *Attributes, struct SymEntry *Next}

#include <strings.h>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <stdbool.h>
#include "SymTab.h"



struct SymTab * CreateSymTab(int Size)
{
   struct SymTab *symtable;
   if(!(symtable=malloc(sizeof(struct SymTab)))) return NULL;
   if(!(symtable->Contents=calloc(Size, sizeof(struct SymEntry*)))) {
          free(symtable);
          return NULL;
   }

   symtable->Size=Size;
   return symtable;
}

/* hash form hash value for string s, taken from 'The C Programming Language'*/
unsigned hash(struct SymTab *ATable, const char *s)
{
     unsigned hashval, size;
     size = ATable->Size;;
     for (hashval = 0; *s != '\0'; s++)
         hashval = *s + 31 * hashval;
     return hashval % size;
}

bool EnterName(struct SymTab *ATable,
          const char *Name,
          struct SymEntry **AnEntry)
{
          struct SymEntry *ptr;
          unsigned hashvalue;
          char *string;
          struct SymEntry *previous;

          string = malloc(strlen(Name)+1);
          AnEntry=(struct SymEntry**)malloc(sizeof(struct SymEntry*));

          strcpy(string, Name);
          printf("string is: is %s\n",string);
          hashvalue = hash(ATable, string);

          printf("hv is %d\n",hashvalue);
          ptr = ATable->Contents[hashvalue];
          previous = NULL;

          while(ptr)
          {
              printf("WHILE LOOP\n");
              if(!(strcmp(ptr->Name,string)))
              {
                  printf("if(!strcmp(ptr->Name,string))\n");
                  *AnEntry = ptr;
                  return true;
              }
              previous = ptr;
              ptr=ptr->Next;
          }
          if(previous)
          {
              printf("IF (PREVIOUS)\n");
              if(!(ptr=malloc(sizeof(struct SymEntry)))) return false;
              if(!(ptr->Name=string))
              {
                  printf("if(!(ptr->Name=string))\n");
                  free(ptr);
                  return false;
              }
              ptr->Name = string;
              previous->Next = ptr;
              printf("Previous->Next: %s\n", previous->Next->Name);
              *AnEntry = ptr;
              return false;
          }
          else
          {
              printf("ELSE (PREVIOUS)\n");
              if(!(ptr=malloc(sizeof(struct SymEntry)))) return false;
              if(!(ptr->Name=string))
              {
                  printf("if(!(ptr->Name=string))\n");
                  free(ptr);
                  return false;
              }
              ptr->Name = string;
              ATable->Contents[hashvalue] = ptr;
              printf("here\n");
              *AnEntry = ptr;
              printf("there\n");
              return false;
          }

}

struct SymEntry * FindName(struct SymTab *ATable, const char *Name)
{
   struct SymEntry *Entry;
   unsigned hashvalue;

   hashvalue = hash(ATable, Name);
   Entry = ATable->Contents[hashvalue];

   while(Entry)
   {
               if(strcmp(Name,Entry->Name)==0)
               {
                                              return Entry;
               }
   }
   return NULL;
}



main(int argc, char **argv)
{
   struct SymTab *mysymtab;
   struct SymEntry *myEntry;

   mysymtab = CreateSymTab(1);
   const char *string1 = "HELLO";
   printf("%d\n",6);
   EnterName(mysymtab, string1, &myEntry);
   printf("first: %s\n", mysymtab->Contents[0]->Name);
   EnterName(mysymtab, string1, NULL);
   EnterName(mysymtab, "WORLD", NULL);
   printf("second: %s\n", mysymtab->Contents[0]->Name);
   printf("second->Next: %s\n", mysymtab->Contents[0]->Next->Name);
   EnterName(mysymtab, "!@#$%", &myEntry);
   printf("third: %s\n", mysymtab->Contents[0]->Name);
   printf("third->Next: %s\n", mysymtab->Contents[0]->Next->Name);
   printf("third->Next->Next: %s\n", mysymtab->Contents[0]->Next->Next->Name);
   printf("myEntry->Name: %s\n", myEntry->Name);
}
+8  A: 

The problem is this line in EnterName:

AnEntry=(struct SymEntry**)malloc(sizeof(struct SymEntry*));

You need to remove that as you want AnEntry to point to the argument that the caller specified.

Because AnEntry may be NULL, you will also need to change every instance of:

*AnEntry = ptr;

to:

if (AnEntry)
    *AnEntry = ptr;

What is happening is that when the function starts, AnEntry is pointing to the pointer the caller wants to change. When you change the value of AnEntry (i.e AnEntry = ...;), your code will not modify the pointer the caller want you to change but some internal pointer. Therefore, when EnterName returns, myEntry is still pointing to some random place in memory.

R Samuel Klatchko
Thanks that worked. That makes sense now that I think about it.Thanks again!
James
Whilst on the subject each SymEntry's Next pointer should be set to NULL in all cases, which it isn't here in the 'else' case.
brone
ya I caught that too. Also, there is an infinite loop in the FindName function that I fixed now...forgot to walk through the list.
James
A: 

While you're at learning, there are some stylistic WTFs in your code. Take this part, for example.

if(!(ptr=malloc(sizeof(struct SymEntry)))) return false;
if(!(ptr->Name=string))
{
    printf("if(!(ptr->Name=string))\n");
    free(ptr);
    return false;
}
ptr->Name = string;

It's inconsistent. You cast the return of malloc for AnEntry above, but not this malloc. Either do one or the other, but don't mix it. Better yet, write it in a way that doesn't "need" a cast at all.

You shouldn't assign values within if-statements. While it is still clear what you want to do in the malloc-case, the intention is obfuscated in the string assignment. Especially since it is superfluous. When the if evaluates to true, ptr is immediately freed. When it evaluates to false, the exact same assignment is done again. Additionally, in this case it prevents an obvious optimization.

Here is the same code rewritten:

if (string == NULL)
{
    printf("string == NULL\n");
    return false;
}
ptr = malloc(sizeof *ptr);
if (ptr == NULL)
{
    return false;
}
ptr->Name = string;
Secure