Half generic hash table

Question

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.

• chux: "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."

Answer 1

• 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.

• chux: Style issue: () OK here, yet not needed in sizeof(*newnode). newhnode = malloc(sizeof *newnode); is OK
• vnp: @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.
• Yonlif: 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
• Yonlif: 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.