3
\$\begingroup\$

After alot of reading and testing I've created a "half generic" hash table.

What I mean by half generic is that the struct that I'm using have a name variable which is char * which is my key, and the second variable it contains is a pointer to void so it can be any struct.

hashTable.c

#include "hashTable.h"


/*createHnode*/
  hnode* createHnode(hnode* next, char* name, void* value)
  {
      hnode* newhnode;
      char*  copiedname;
      if((NULL == name)||(NULL == value)){
        return NULL;
      }
    /*Allocate hnode*/
      if (NULL == (newhnode = (hnode*)malloc(sizeof(hnode)))) {
        return NULL;
      }
    /*set next*/
      newhnode->next = next;
    /*set name*/
      if (NULL == (copiedname = (char*)malloc(sizeof(char)*(strlen(name)+1)))) {
        return NULL;
      }
      strcpy(copiedname,name);
      newhnode->name = copiedname;   /*point at the input name string*/
    /*set value*/
      newhnode->value = value; /*points at the input value*/
    /*return a pointer to the allocated hnode*/
      return newhnode;
  }


/*createHashTable*/
/*Allocate an array of pointers to item.*/
  hnode** createHashTable(int hashsize)
  {
    int i;
    hnode** hashtable;
  /*If allocation failed, return NULL */
    if(NULL == (hashtable = (hnode**)malloc(sizeof(hnode*)*hashsize)) ){
       return NULL;
    }
  /*set all pointers in hashtable to NULL */
    for(i=0; i<hashsize; i++){
        hashtable[i]=NULL;
    }
    return hashtable;
  }


/*hashfunction*/
/*gets a string as argument, returns the index inside
  the hash-array:  0 - 51.
  A string is match to the index of its first character: a-z or A-Z.
  If several words start with the same character, a linked-list joins each new key.*/
  int hashfunction(char* name)
  {
     if(NULL == name){
        return -1; /*name = NULL*/
     }
   /*A-Z:  ASCII: 65-90*/
     if( name[0] - 97 <0 ){
         return (name[0]-65); /*index  0 - 25 in the hash-array*/
     }
   /*a-z: ASCII: 97-122*/
          return (26+ name[0]-97); /*index 26 - 51 in the hash-array*/
  }


/*insertNameValue*/
/*Input arguments:
   The hash-array and the new item to be added (if not inside hash-table already).
   The item will be added to the array-cell according to its key.
   If several items have the same hashindex, they will form a linked-list, in which the last
   item is added last in line.
   If the item is first in the hash-index, it will be the first
  Will enter the object to the hash-array according to the key.
  If object is already inside (has the same key string), than putValueForKey returns an
  error code*/
  int insertNameValue (hnode** hashArray, char* name, void* value)
  {
     int hashIndex;
     hnode* curr = NULL;             /*A pointer to the current item in the Hash(not the new item).*/
     if( (NULL == name)||(NULL == value) ){
          return -1;
     }
     hashIndex = hashfunction(name); /*get index for new name*/
   /*parse the linked-list, if exist, and compare input name to existing name-value pairs.*/
     curr = hashArray[hashIndex];
   /*if hashArray is empty at this cell, insert the new name-value pair*/
     if( NULL == curr){
         /*create a new hnode with name and value*/
           hashArray[hashIndex] = createHnode(NULL, name, value);
           return 1;
     }
   /*if hashArray points at a single hnode in this cell*/
     else if( NULL == curr->next){
              /*compare names(keys) of new pair and existing one*/
                if( 0 == strcmp(name, curr->name)){
                    return(-1); /*item is already in hash*/
                }
     }
   /*hashArray has a linked-list --> compare and add name-value at the end of
     the list. New hnode points at the end, need to point at NULL*/
     while( NULL != curr->next ){
            /*compare new key with each existing keys*/
              printf("curr->name = %s, name = %s\n",curr->name, name);
              if( 0 == strcmp(name, curr->name)){
                  return(-1); /*item is already in hash*/
              }
              curr = curr->next;
     }
   /*Reached end of list*/
   /*Create a new hnode with name and value*/
     curr->next = createHnode(NULL, name, value);
     return 1;
  }


/*getValueByName*/
/*returns a pointer to the value-object if the given name exists in the hash-Table*/
  void *getValueByName (hnode** hashArray, char* name)
  {
      hnode* curr; /*curr cell in the hashTable*/
    /*Get the hash index*/
      int hashIndex = hashfunction(name);
      curr = hashArray[hashIndex];
    /*Move in array until an empty */
      while(curr != NULL) {
            if(0 == (strcmp(hashArray[hashIndex]->name,name))){
               return hashArray[hashIndex]; /*key has value in hash*/
            }
            curr = curr->next;
      }
      return NULL;
  }/*End getValueByKey*/



  void deleteHashTable(hnode** hashArray, void (*deleteValue)(void*))
  {
     int i;
     hnode* curr;             /*points at hashArray[]                               */
     hnode* next;             /*another temporary hnode                             */
     if (hashArray == NULL){
         return;
     }
   /*parse the hashTable and delete hnodes, also in list*/
     for(i=0; i< HASHSIZE; i++){
         curr = hashArray[i];
         while(NULL != curr){
               next = curr->next; /*mark next hnode */
             /*Delete current hnode*/
             /*Delete the value*/
               deleteValue(curr->value);
             /*Delete the name*/
               free(curr->name);
             /*Delete current hnode*/
               free(curr);
             /*continue to next hnode*/
               curr = next;
         }
     }
   /*Delete the hash-Array: */
     free(hashArray);
  }/*End deleteHashTable*/


/*For testing...*/
  void displayHashTable (hnode** hashArray, void (*printValue)(void* )){
       int i;
       hnode *curr, *next;
       printf("%-20s%-20s\n", "hashTable-Key,", "hashTable-Value");
       for (i = 0; i < HASHSIZE; i++){
            curr = hashArray[i];
            while(NULL != curr){
                  next = curr->next;
                  printf("%-20s,",curr->name);
                  printValue(curr->value);
                  printf("\n");
                  curr = next;
             }
       }
  }

hashTable.h

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#ifndef HASHTABLE_H_INCLUDED
#define HASHTABLE_H_INCLUDED
#define HASHSIZE 52  /* 26 for a-z and 26 for A-Z*/

/*struct hnode*/
  struct hnode{
       struct hnode *next;       /*next entry in chain                         */
       char*  name;             /*the key is a string(label or name)          */
       void*  value;            /*value can be any type or struct --> Generic */
  }typedef hnode;

/*createHnode*/
  hnode* createHnode(hnode* next, char* name, void* value);


/*hashfunction*/
  int hashfunction(char* name);


/*createHashTable*/
/*Allocate an array of pointers to item.*/
  hnode** createHashTable(int hashsize);


/*putValueForKey*/
  int insertNameValue(hnode** hashArray, char* name, void* value);


/*getValueByKey*/
  void* getValueByName(hnode** hashArray, char* key);


/*deleteHashTable*/
/*get the hashTable to be deleted
  and a pointer to a function to delete the value object
  void (*deleteValue)(void *)  --> a pointer to function to delete the value struct */
  void deleteHashTable(hnode** hashArray, void (*deleteValue)(void*));


/*For testing...*/
  void displayHashTable (hnode** hashArray, void (*printValue)(void* ob));


#endif /* HASHTABLE_H_INCLUDED */

I believe the code is commented well and would like to read your opinion about it.

\$\endgroup\$
  • \$\begingroup\$ "second variable it contains is a pointer to void so it can be any struct." is not correct. I suspect you want "second variable it contains is a pointer to void so it can be a pointer to any object." \$\endgroup\$ – chux Aug 15 '17 at 17:41
2
\$\begingroup\$
  • Comments should not duplicate the code. For example, a comment in

    /*Allocate hnode*/
      if (NULL == (newhnode = (hnode*)malloc(sizeof(hnode)))) {
        return NULL;
      }
    

    adds nothing to clarity, but rather creates noise.

  • Don't cast return value of malloc. At best it is redundant, and at worst may lead to hard-to-find bugs.

  • Avoid magic numbers. 65, 26, 97 are better expressed as 'a', 'z' - 'a' + 1, 'A'. That said, prefer standard library calls isalpha and islower.

    Speaking of standard library, a malloc/strcpy is a long way to say strdup.

  • Returning -1 on a collision does not look right. The caller would most likely be interested in what element prevented the insertion. Consider returning a pointer.

  • getValueByName has a gaping bug: the hashArray[hashIndex] inside the loop must be curr. I hope it is a copy-paste error.

  • DRY. The lookup loop in insertNameValue duplicates the (intended) functionality of getValueByName.

  • Missing functionality. There is no way to delete individual entries.

  • Nitpicking.

    sizeof(type) may lead to double maintenance. Prefer sizeof(expression), e.g.

        newhnode = malloc(sizeof(*newnode))
    

    Use calloc where appropriate.

    sizeof(char) is 1 by definition.

\$\endgroup\$
  • \$\begingroup\$ Style issue: () OK here, yet not needed in sizeof(*newnode). newhnode = malloc(sizeof *newnode); is OK \$\endgroup\$ – chux Aug 15 '17 at 17:38
  • \$\begingroup\$ @chux You are right. However I never understood the rationale behind two incarnations of sizeof (sorry if I already discussed it with you), and since parenthesis work both way, I rather have them. \$\endgroup\$ – vnp Aug 15 '17 at 17:42
  • \$\begingroup\$ Thanks alot, it is a copy paste error - I've already found this bug. I will change my code according to your tips. Thanks again \$\endgroup\$ – Yonlif Aug 15 '17 at 18:26
  • \$\begingroup\$ Hi @vnp, this code is part of a big project im working on. Recently I've got a segmentation fault and after alot of debugging I've decided the problem is in the hashTabel. Can you please take another look? I also think there's a bug in insertNameValue, if we are in this situation: aa, ab, ac and we are trying to add ac it won't fail. Please help. \$\endgroup\$ – Yonlif Aug 20 '17 at 13:33

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.