current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 3 down vote favorite

I made this function to teach myself about hash tables. Any ideas? I commented out free(addition) because it was giving me a compiler error, but I need to figure out how to deallocate the memory. 

#define hashSize 1000

typedef struct hashElem{
    char* date;
    char* holiday;
}hashElem;

typedef struct hash{
    struct hashElem element;
    struct hash* next;
}hash;

hash* hashTable[hashSize];

// Hash function
size_t murmurHash(const void *keyPtr, size_t keySize)
{
     /*  DESCRIPTION:    Very fast string hashing algorithm with excelleng distribution and 
     *                  collision resistance. This source code has been released into the public
     *                  domain.
     *
     *  NOTES:          http://murmurhash.googlepages.com
     *
     *  RETURNS:        Hashtable index for the key
     *
     */

    /* 'm' and 'r' are mixing constants generated offline.         */
    /* They're not really 'magic', they just happen to work well.  */

    const unsigned int m = 0x5bd1e995;
    const int r = 24;

    size_t hashValue = 0;

    /* Mix 4 bytes at a time into the hash */

    const unsigned char * data = (const unsigned char *)keyPtr;

    while(keySize >= 4)
    {
        unsigned int k = *(unsigned int *) data;

        k *= m; 
        k ^= k >> r; 
        k *= m; 

        hashValue *= m; 
        hashValue ^= k;

        data += 4;
        keySize -= 4;
    }

    /* Handle the last few bytes of the input array */

    switch(keySize)
    {
        case 3: hashValue ^= data[2] << 16;
        case 2: hashValue ^= data[1] << 8;
        case 1: hashValue ^= data[0];
                hashValue *= m;
    }; 

    /* Do a few final mixes of the hash to ensure the last few  */
    /* bytes are well-incorporated.                             */

    hashValue ^= hashValue >> 13;
    hashValue *= m;
    hashValue ^= hashValue >> 15;

    return (hashValue % hashSize);
}

// strlen: return length of string
int strlen(char *s)
{
    char* p = s;

    while (*p != '\0')
        ++p;
    return p - s;
}

// Add Holiday into hash table
void addHoliday(char* date, char* holiday)
{
   char* key;
   int keyLen;
   size_t keyHash;
   hash* addition = malloc(sizeof(*addition));

   key = date;
   addition->element.date = key;
   addition->element.holiday = holiday;

   // Add holiday to Hash Table
   if (hashTable[murmurHash(key, strlen(key))] == NULL)
   {    
       addition->next = NULL;
       hashTable[murmurHash(key, strlen(key))] = addition; 
   }
   else  //If there is already an element at the index, add current holiday to beginning of list
   {
       addition->next = hashTable[murmurHash(key, strlen(key))];
       hashTable[murmurHash(key, strlen(key))] = addition;
   }

   //free(addition);
}

// If a date is entered, retrieve holiday from hash function index
char* getHoliday(char* date)
{
    return(hashTable[murmurHash(date, strlen(date))]->element.holiday);
}

void main(void)
{
   addHoliday("01/01/13", "New Years Day");
   printf("%s\n", getHoliday("01/01/13"));

   getchar();
}
share|improve this question
1  
Is the question how to deallocate memory? –  Aseem Bansal Aug 23 '13 at 6:49
    
the question is for an overall code review along with some comments about any area where memory is being leaked –  sammis Aug 23 '13 at 11:41
    
possible duplicate of Working C code dealing with lists: problem with memory leak –  Aseem Bansal Aug 24 '13 at 11:47
add comment

2 Answers

up vote 2 down vote

For one thing, this:

   // Add holiday to Hash Table
   if (hashTable[murmurHash(key, strlen(key))] == NULL)
   {    
       addition->next = NULL;
       hashTable[murmurHash(key, strlen(key))] = addition; 
   }
   else  //If there is already an element at the index, add current holiday to beginning of list
   {
       addition->next = hashTable[murmurHash(key, strlen(key))];
       hashTable[murmurHash(key, strlen(key))] = addition;
   }

can simply be this:

   // Add holiday to Hash Table
   size_t idx = = murmurHash(key, strlen(key));
   addition->next = hashTable[idx];
   hashTable[idx] = addition;

Which cuts both a strlen and a conditional check out of your logic.

share|improve this answer
add comment
up vote 2 down vote

I agree with WhozCraig; it is not necessary to run the hash multiple times. I would add that freeing the pointer (addition) would result in loss of the data you just added. Your array hashTable is an array of pointers - it doesn't include storage for the hash elements themselves. Thus, you can't free any hash elements until you remove them from the table or are done with the table itself.

Tearing down the table will have to go something like this:

for (int i = 0 ; i < hashSize ; i++) {
    hash* ptrToFree = hashTable[i];
    while (ptrToFree != NULL) {
        hash* next = ptrToFree->next;
        mfree(ptrToFree);
        ptrToFree = next;
    }
}

If you don't like iterating over all of your pointers (it looks time-consuming, but you're probably on the way out of your process, right?) you can keep a static list of all elements, then iterate through that.

typedef struct _HashStorage {
    struct hash element;
    struct _HashStorage * more;
} HashStorage;

HashStorage* storage = NULL;

hash* newHash() {
    HashStorage* oldTop = storage;
    storage = malloc(sizeof(HashStorage));
    storage->more = oldTop;
    return (hash*) storage;
}

void dispose() {
    HashStorage* iterator = storage;
    while (iterator != NULL) {
        HashStorage* more = iterator->more;
        mfree(iterator);
        iterator = more;
    }
}
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.