Thread: Not sure on hash table memory allocations

  1. #1
    Registered User
    Join Date
    Sep 2004
    Posts
    20

    Not sure on hash table memory allocations

    I'm trying to work on a program that inputs entries from a file and then builds a hash table. I'm a little new to programming so I know I do not have the best form. I only submitted the code that I think might be the problem...

    This code compiles but then has runtime errors and every time I look to see if the current hash table index is NULL it has a large number like a memory address. If anyone could give me some advice on what I might be doing wrong with the add and search functions that would be so nice...

    PHP Code:
    [CODE]


    struct  ht_entry {                             /* an entry (node) in hash table */
         
    char    ht_name[NAME_LENGTH 1];         /* name in hash table */
         
    int     ref_count;                        /* number of references to the name */
         
    struct  ht_entry  *next;
    };


    struct  ht_entry  *hash_tbl[BKT_SIZE];         /* bucket directory (hash index) */


    int search(char *name_ptrint *ind_ptr)       /* name to be searched , hash index (index into the hash table) */
    {
       
    struct ht_entry *tmp;                       /* declare tmp */
       
    tmp malloc(sizeof(*tmp));                 /* allocate memory for tmp */
       
    tmp=hash_tbl[*ind_ptr];                     /* sets to the head of hash_tbl */
       
       
    printf("SEARCH ");
       
       while(
    tmp!=NULL)                            /* while tmp is not NULL */
       
    {  
          if((
    strcmp(tmp->ht_namename_ptr))==0)  /* if hash_tbl name is equal to current name return true (FOUND) */
          
    {
              return 
    TRUE;
          }

          
    tmp=tmp->next;    
       }   

       return 
    FALSE;                               /* else return false (NOT FOUND) */

    }/* end of search */


    void add(char *name_ptr,int *ind_ptr)          /* (pointer to name, pointer to hash index)  THIS ADDS NODE TO HASH TABLE */
    {
        
    struct ht_entry *head;                                 /* declare head */
        
    head malloc(sizeof(*head));                          /* allocate memory for head */
        
        
    if(hash_tbl[*ind_ptr]==NULL)                           /* if hash_tbl[index] is NULL initialize a new node for index */
        
    {
           
    hash_tbl[*ind_ptr] = malloc(sizeof(*hash_tbl));     /* allocate memory for hash_tbl[hash_index] if it's NULL */ 
           
    strcpy(hash_tbl[*ind_ptr]->ht_namename_ptr);
           
    hash_tbl[*ind_ptr]->ref_count=0;
           
    printf("It was NULL."  );
        }
        else                                                   
    /* else initialize head then link to hash_tbl[index] */
        
    {
           
    strcpy(head->ht_namename_ptr);
           
    head->ref_count=0;
           
    head->next=hash_tbl[*ind_ptr];
           
    hash_tbl[*ind_ptr]=head;
           
    printf("It wasn't NULL.  ");
        }    

        
    printf("It's been added!\n");

    }
    //end add

    /*

    Sample Input:
       DEF  GONE
       DEF  KMN127
       DEF  EGG
       DEF  VAN
       DEF  AKK
       DEF  EGG
       USE  VAN
       USE  AKK
       USE  JEEP
       USE  AKK
       DEF  FUN
       DEF  ALI
       USE  KMN127
       
    Sample Output:
         Input Data
       Command   Name
       DEF       GONE
       DEF       KMN127
       DEF       EGG
       DEF       VAN
       DEF       AKK
       DEF       EGG          *** Duplicate Name ***
       USE       VAN
       USE       AKK
       USE       JEEP         *** Undefined Name ***
       USE       AKK
       DEF       FUN
       DEF       ALI
       USE       KMN127
       
    */

    [/CODE

  2. #2
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    Quote Originally Posted by Thumper333
    Code:
    void add(char *name_ptr,int *ind_ptr)          /* (pointer to name, pointer to hash index)  THIS ADDS NODE TO HASH TABLE */
    {
        struct ht_entry *head;                                 /* declare head */
        head = malloc(sizeof(*head));                          /* allocate memory for head */
        
        if(hash_tbl[*ind_ptr]==NULL)                           /* if hash_tbl[index] is NULL initialize a new node for index */
        {
    //ERROR HERE
           hash_tbl[*ind_ptr] = malloc(sizeof(*hash_tbl));     /* allocate memory for hash_tbl[hash_index] if it's NULL */ 
           strcpy(hash_tbl[*ind_ptr]->ht_name, name_ptr);
           hash_tbl[*ind_ptr]->ref_count=0;
           printf("It was NULL."  );
        }
        else                                                   /* else initialize head then link to hash_tbl[index] */
        {
    /*....................*/
        }    
    
    /*....................*/
    
    }//end add
    The problem is simple. When struct ht_entry *next is NULL you allocate memory to the pointer and initiate the variables. Then you must assign NULL the the next pointer in the allocated struct, or instead use calloc at stdlib to alocate memory initialized automaticly with zeros.
    Plus shouldn't this be
    Code:
    hash_tbl[*ind_ptr] = malloc(sizeof(*ht_entry));
    instead of
    Code:
    hash_tbl[*ind_ptr] = malloc(sizeof(*hash_tbl));
    I think it should, Otherwize you're allocating a diferent amount of memory rather than the one needed. In this case BKT_SIZE*4 bytes.
    So...
    Code:
      if(hash_tbl[*ind_ptr]==NULL)                           /* if hash_tbl[index] is NULL initialize a new node for index */
        {
           hash_tbl[*ind_ptr] = malloc(sizeof(*ht_entry));//<-- HERE's the fix
           strcpy(hash_tbl[*ind_ptr]->ht_name, name_ptr);
           hash_tbl[*ind_ptr]->ref_count=0;
           hash_tbl[*ind_ptr]->next=NULL;//<-- HERE's the fix
           printf("It was NULL."  );
        }
    Those big number you see are random values from the allocated memory, therefore invalid pointers.

    Hope this helps. Cheers!
    Last edited by xErath; 09-27-2004 at 07:03 PM.

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >struct ht_entry *tmp; /* declare tmp */
    Wow, what a waste of a comment. Please don't comment code that is obvious to anyone remotely familiar with C, it clutters the code.

    >tmp = malloc(sizeof(*tmp)); /* allocate memory for tmp */
    Okay, and there's another redundant comment.

    >tmp=hash_tbl[*ind_ptr];
    Not okay, you just caused a memory leak because tmp was the only reference to the memory you just allocated.

    >while(tmp!=NULL) /* while tmp is not NULL */
    Good thing you had a comment there to tell me exactly what kind of loop you were using and what the condition is.

    >void add(char *name_ptr,int *ind_ptr)
    This is a sweeping comment for both search and add. Why is ind_ptr a pointer? It doesn't buy you anything except added complexity.

    >hash_tbl[*ind_ptr] = malloc(sizeof(*hash_tbl));
    Good idea, bad execution. You already have a entry allocated with head, why not just use that?

    Try this instead:
    Code:
    struct  ht_entry {                          /* an entry (node) in hash table */ 
      char    ht_name[NAME_LENGTH + 1];         /* name in hash table */ 
      int     ref_count;                        /* number of references to the name */ 
      struct  ht_entry  *next;                  /* next entry with the same hash index */
    }; 
    
    struct  ht_entry  *hash_tbl[BKT_SIZE];      /* bucket directory (hash index) */ 
    
    int search(char *name_ptr, int ind)
    { 
      struct ht_entry *tmp = hash_tbl[ind];
    
      printf("SEARCH "); 
    
      while(tmp!=NULL)
      {   
        if((strcmp(tmp->ht_name, name_ptr))==0)
        { 
          return TRUE; 
        } 
    
        tmp=tmp->next;     
      }    
    
      return FALSE;
    }
    
    void add(char *name_ptr,int ind)
    { 
      struct ht_entry *head = malloc(sizeof(*head));
    
      if(hash_tbl[ind]==NULL)
      { 
        strcpy(head->ht_name, name_ptr); 
        head->ref_count=0;
        head->next=hash_tbl[ind];
        hash_tbl[ind]=head;
        printf("It was NULL."); 
      } 
      else
      { 
        strcpy(head->ht_name, name_ptr); 
        head->ref_count=0; 
        head->next=hash_tbl[ind]; 
        hash_tbl[ind]=head; 
        printf("It wasn't NULL.  "); 
      }     
    
      printf("It's been added!\n"); 
    }
    But, because you'll notice that both the null and not null casees in add are exactly the same, you can combine them:
    Code:
    void add(char *name_ptr,int ind)
    { 
      struct ht_entry *head = malloc(sizeof(*head));
    
      if(hash_tbl[ind]==NULL)
      { 
        printf("It was NULL."); 
      } 
      else
      { 
        printf("It wasn't NULL.  "); 
      }
    
      strcpy(head->ht_name, name_ptr); 
      head->ref_count=0; 
      head->next=hash_tbl[ind]; 
      hash_tbl[ind]=head; 
    
      printf("It's been added!\n"); 
    }
    Now we can test these functions with a simple driver:
    Code:
    int hash(char *s)
    {
      int h;
    
      for(h=0; *s!='\0'; s++)
      {
        h=*s+31*h;
      }
    
      return h%BKT_SIZE;
    }
    
    int main(void)
    {
      char buffer[20];
      struct ht_entry *p;
      int i;
    
      while(scanf("%19s", buffer)==1)
      {
        if(search(buffer, hash(buffer))==FALSE)
        {
          add(buffer, hash(buffer));
        }
        else
        {
          p=hash_tbl[hash(buffer)];
    
          while(strcmp(p->ht_name, buffer)!=0)
          {
            p=p->next;
          }
    
          p->ref_count++;
        }
      }
    
      for(i=0; i<BKT_SIZE; i++)
      {
        for(p=hash_tbl[i]; p!=NULL; p=p->next)
        {
          printf("%s(%d)->", p->ht_name, p->ref_count);
        }
        printf("\n");
      }
    
      return 0;
    }
    My best code is written with the delete key.

  4. #4
    Registered User
    Join Date
    Sep 2004
    Posts
    20
    Thank you both! You two have solved my problems... well at least the current problems. I've also learned a good amount. Thanks a lot!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Group Project Help/Volunteer
    By DarkDot in forum C++ Programming
    Replies: 3
    Last Post: 04-24-2007, 11:36 PM
  2. [Memory management] Hash table?
    By cboard_member in forum Game Programming
    Replies: 9
    Last Post: 04-15-2007, 01:52 PM
  3. Hash Table
    By siavoshkc in forum C++ Programming
    Replies: 4
    Last Post: 08-29-2006, 04:29 PM
  4. rehash help
    By kashifk in forum C++ Programming
    Replies: 1
    Last Post: 10-22-2003, 06:51 PM
  5. help with operator <
    By kashifk in forum C++ Programming
    Replies: 1
    Last Post: 10-21-2003, 03:49 PM