4
\$\begingroup\$

I am still working on basic data structures for C. Now I came up with a hash map:

unordered_map.h:

#ifndef UNORDERED_MAP_H
#define UNORDERED_MAP_H

#include <stdlib.h>
#include <stdbool.h>

#ifdef  __cplusplus
extern "C" {
#endif

    typedef struct unordered_map_t          unordered_map_t;
    typedef struct unordered_map_iterator_t unordered_map_iterator_t;

    /***************************************************************************
    * Allocates a new, empty map with given comparator function.               *
    ***************************************************************************/ 
    unordered_map_t* unordered_map_t_alloc 
           (size_t initial_capacity,
            float load_factor,
            size_t (*p_hash_function)(void*),
            bool (*p_equals_function)(void*, void*));

    /***************************************************************************
    * If p_map contains the key p_key, associates it with value p_value and    *
    * returns the old value of that key.                                       *
    ***************************************************************************/ 
    void*  unordered_map_t_put             (unordered_map_t* p_map, 
                                            void* p_key, 
                                            void* p_value);

    /***************************************************************************
    * Returns a positive value if p_key is mapped to some value in this map.   *
    ***************************************************************************/
    bool   unordered_map_t_contains_key    (unordered_map_t* p_map, 
                                            void* p_key);

    /***************************************************************************
    * Returns the value associated with the p_key, or NULL if p_key is not     *
    * mapped in the map.                                                       *
    ***************************************************************************/
    void*  unordered_map_t_get             (unordered_map_t* p_map, 
                                            void* p_key);

    /***************************************************************************
    * If p_key is mapped in the map, removes the mapping and returns the value *
    * of that mapping. If the map did not contain the mapping, return NULL.    *
    ***************************************************************************/ 
    void*  unordered_map_t_remove          (unordered_map_t* p_map, 
                                            void* p_key);

    /***************************************************************************
    * Removes all the contents of the map.                                     * 
    ***************************************************************************/ 
    void   unordered_map_t_clear           (unordered_map_t* p_map);

    /***************************************************************************
    * Returns the size of the map, or namely, the amount of key/value mappings *
    * in the map.                                                              *
    ***************************************************************************/ 
    int    unordered_map_t_size            (unordered_map_t* p_map);

    /***************************************************************************
    * Checks that the map maintains the AVL-tree invariant.                    *
    ***************************************************************************/  
    bool   unordered_map_t_is_healthy      (unordered_map_t* p_map);

    /***************************************************************************
    * Deallocates the entire map. Only the map and its nodes are deallocated.  *
    * The user is responsible to deallocate the actual data stored in the map. *
    ***************************************************************************/ 
    void   unordered_map_t_free            (unordered_map_t* p_map);

    /***************************************************************************
    * Returns the iterator over the map. The entries are iterated in order.    *
    ***************************************************************************/  
    unordered_map_iterator_t* unordered_map_iterator_t_alloc
                             (unordered_map_t* p_map);

    /***************************************************************************
    * Returns the number of keys not yet iterated over.                        *
    ***************************************************************************/ 
    int unordered_map_iterator_t_has_next(unordered_map_iterator_t* p_iterator);

    /***************************************************************************
    * Returns the next entry in the iteration order.                           *
    ***************************************************************************/  
    bool unordered_map_iterator_t_next(unordered_map_iterator_t* p_iterator, 
                                       void** pp_key, 
                                       void** pp_value);

    /***************************************************************************
    * Returns a positive integer if the map was modified during the iteration. *
    ***************************************************************************/  
    bool unordered_map_iterator_t_is_disturbed
        (unordered_map_iterator_t* p_iterator);

    /***************************************************************************
    * Deallocates the map iterator.                                            *
    ***************************************************************************/  
    void unordered_map_iterator_t_free(unordered_map_iterator_t* p_iterator);

#ifdef  __cplusplus
}
#endif

#endif  /* UNORDERED_MAP_H */

unordered_map.c:

#include "unordered_map.h"
#include <stdbool.h>
#include <stdlib.h>

typedef struct unordered_map_entry_t {
    void*                         p_key;
    void*                         p_value;
    struct unordered_map_entry_t* p_chain_next;
    struct unordered_map_entry_t* p_prev;
    struct unordered_map_entry_t* p_next;
} unordered_map_entry_t;

typedef struct unordered_map_t {
    unordered_map_entry_t** p_table;
    unordered_map_entry_t*  p_head;
    unordered_map_entry_t*  p_tail;
    size_t                (*p_hash_function)(void*);
    bool                  (*p_equals_function)(void*, void*);
    size_t                  mod_count;
    size_t                  table_capacity;
    size_t                  size;
    size_t                  mask;
    float                   load_factor;
} unordered_map_t;

typedef struct unordered_map_iterator_t {
    unordered_map_t*       p_map;
    unordered_map_entry_t* p_next_entry;
    size_t                 iterated_count;
    size_t                 expected_mod_count;
} unordered_map_iterator_t;

static unordered_map_entry_t* unordered_map_entry_t_alloc(void* p_key,
                                                          void* p_value)
{
    unordered_map_entry_t* p_ret = malloc(sizeof(*p_ret));

    if (!p_ret) return NULL;

    p_ret->p_key        = p_key;
    p_ret->p_value      = p_value;
    p_ret->p_chain_next = NULL;
    p_ret->p_next       = NULL;
    p_ret->p_prev       = NULL;

    return p_ret;
}

static const float  MINIMUM_LOAD_FACTOR = 0.2f;
static const size_t MINIMUM_INITIAL_CAPACITY = 16;

static float maxf(float a, float b) 
{
    return a < b ? b : a;
}

static int maxi(int a, int b) 
{
    return a < b ? b : a;
}

/*******************************************************************************
* Makes sure that the load factor is no less than a minimum threshold.         *
*******************************************************************************/  
static float fix_load_factor(float load_factor)
{
    return maxf(load_factor, MINIMUM_LOAD_FACTOR);
}

/*******************************************************************************
* Makes sure that the initial capacity is no less than a minimum allowed and   *
* is a power of two.                                                           * 
*******************************************************************************/  
static size_t fix_initial_capacity(size_t initial_capacity) 
{
    size_t ret;

    initial_capacity = maxi(initial_capacity, MINIMUM_INITIAL_CAPACITY);
    ret = 1;

    while (ret < initial_capacity) ret <<= 1;
    return ret;
}

unordered_map_t* unordered_map_t_alloc(size_t initial_capacity,
                                       float load_factor,
                                       size_t (*p_hash_function)(void*),
                                       bool (*p_equals_function)(void*, void*))
{
    unordered_map_t* p_ret;

    if (!p_hash_function)   return NULL;
    if (!p_equals_function) return NULL;

    p_ret = malloc(sizeof(*p_ret));

    if (!p_ret) return NULL;

    load_factor      = fix_load_factor(load_factor);
    initial_capacity = fix_initial_capacity(initial_capacity);

    p_ret->load_factor       = load_factor;
    p_ret->table_capacity    = initial_capacity;
    p_ret->size              = 0;
    p_ret->mod_count         = 0;
    p_ret->p_head            = NULL;
    p_ret->p_tail            = NULL;
    p_ret->p_table           = calloc(initial_capacity, 
                                      sizeof(unordered_map_entry_t*));
    p_ret->p_hash_function   = p_hash_function;
    p_ret->p_equals_function = p_equals_function;
    p_ret->mask              = initial_capacity - 1;

    return p_ret;
}

static void ensure_capacity(unordered_map_t* p_map) 
{
    size_t new_capacity;
    size_t new_mask;
    size_t index;
    unordered_map_entry_t* p_entry;
    unordered_map_entry_t** p_new_table;

    if (p_map->size <= p_map->load_factor * p_map->table_capacity) return;

    new_capacity = 2 * p_map->table_capacity;
    new_mask = new_capacity - 1;
    p_new_table = calloc(new_capacity, sizeof(unordered_map_entry_t*));

    if (!p_new_table) return;

    /* Rehash the entries. */
    for (p_entry = p_map->p_head; p_entry; p_entry = p_entry->p_next)
    {
        index = p_map->p_hash_function(p_entry->p_key) & new_mask;
        p_entry->p_chain_next = p_new_table[index];
        p_new_table[index] = p_entry;
    }

    free(p_map->p_table);
    p_map->p_table        = p_new_table;
    p_map->table_capacity = new_capacity;
    p_map->mask           = new_mask;
}

void* unordered_map_t_put(unordered_map_t* p_map, void* p_key, void* p_value)
{
    size_t index;
    void* p_old_value;
    unordered_map_entry_t* p_entry;

    if (!p_map) return NULL;

    index = p_map->p_hash_function(p_key) & p_map->mask;

    for (p_entry = p_map->p_table[index]; 
         p_entry;
         p_entry = p_entry->p_chain_next)
    {
        if (p_map->p_equals_function(p_entry->p_key, p_key))
        {
            p_old_value = p_entry->p_value;
            p_entry->p_value = p_value;
            return p_old_value;
        }
    }

    ensure_capacity(p_map);

    /* Recompute the index since it is possibly changed by 'ensure_capacity' */
    index = p_map->p_hash_function(p_key) & p_map->mask;
    p_entry               = unordered_map_entry_t_alloc(p_key, p_value);
    p_entry->p_chain_next = p_map->p_table[index];
    p_map->p_table[index] = p_entry;

    /* Link the new entry to the tail of the list. */
    if (!p_map->p_tail)
    {
        p_map->p_head = p_entry;
        p_map->p_tail = p_entry;
    }
    else
    {
        p_map->p_tail->p_next = p_entry;
        p_entry->p_prev = p_map->p_tail;
        p_map->p_tail = p_entry;
    }

    p_map->size++;
    p_map->mod_count++;
    return NULL;
}

bool unordered_map_t_contains_key(unordered_map_t* p_map, void* p_key)
{
    size_t index;
    unordered_map_entry_t* p_entry;

    if (!p_map) return false;

    index = p_map->p_hash_function(p_key) & p_map->mask;

    for (p_entry = p_map->p_table[index]; 
         p_entry; 
         p_entry = p_entry->p_chain_next) 
    {
        if (p_map->p_equals_function(p_key, p_entry->p_key)) return true;
    }

    return false;
}

void* unordered_map_t_get(unordered_map_t* p_map, void* p_key)
{
    size_t index;
    unordered_map_entry_t* p_entry;

    if (!p_map) return NULL;

    index = p_map->p_hash_function(p_key) & p_map->mask;

    for (p_entry = p_map->p_table[index];
         p_entry;
         p_entry = p_entry->p_chain_next)
    {
        if (p_map->p_equals_function(p_key, p_entry->p_key)) 
            return p_entry->p_value;
    }

    return NULL;
}

void* unordered_map_t_remove(unordered_map_t* p_map, void* p_key)
{
    void*  p_ret;
    size_t index;
    unordered_map_entry_t* p_prev_entry;
    unordered_map_entry_t* p_current_entry;

    if (!p_map) return NULL;

    index = p_map->p_hash_function(p_key) & p_map->mask;

    p_prev_entry = NULL;

    for (p_current_entry = p_map->p_table[index];
         p_current_entry;
         p_current_entry = p_current_entry->p_chain_next)
    {
        if (p_map->p_equals_function(p_key, p_current_entry->p_key)) 
        {
            if (p_prev_entry)
            {
                /* Omit the 'p_current_entry' in the collision chain. */
                p_prev_entry->p_chain_next = p_current_entry->p_chain_next;
            }
            else
            {
                // Here?
                p_map->p_table[index] = p_current_entry->p_chain_next;
            }

            /* Unlink from the global iteration chain. */
            if (p_current_entry->p_prev && p_current_entry->p_next) 
            {
                /* Once here, the current entry has both next and previous. */
                p_current_entry->p_prev->p_next = p_current_entry->p_next;
                p_current_entry->p_next->p_prev = p_current_entry->p_prev;
            }
            else if (!p_current_entry->p_prev && !p_current_entry->p_next)
            {
                /* Once here, the current entry 
                   is the only entry in the chain. */
                p_map->p_head = NULL;
                p_map->p_tail = NULL;
            }
            else if (p_current_entry->p_next)
            {
                /* Once here, the current entry is the head of the chain. */
                p_map->p_head = p_current_entry->p_next;
                p_map->p_head->p_prev = NULL;
            }
            else
            {
                /* Once here, the current entry is the tail of the chain. */
                p_map->p_tail = p_current_entry->p_prev;
                p_map->p_tail->p_next = NULL;
            }

            p_ret = p_current_entry->p_value;
            p_map->size--;
            p_map->mod_count++;
            free(p_current_entry);
            return p_ret;
        }

        p_prev_entry = p_current_entry;
    }

    return NULL;
}

void unordered_map_t_clear(unordered_map_t* p_map)
{
    unordered_map_entry_t* p_entry;
    unordered_map_entry_t* p_next_entry;
    size_t index;

    if (!p_map) return;

    p_entry = p_map->p_head;

    while (p_entry)
    {
        index = p_map->p_hash_function(p_entry->p_key) & p_map->mask;
        p_next_entry = p_entry->p_next;
        free(p_entry);
        p_entry = p_next_entry;

        if (p_map->p_table[index])
        {
            p_map->p_table[index] = p_map->p_table[index]->p_chain_next;
        }
    }

    p_map->mod_count += p_map->size;
    p_map->size = 0;
    p_map->p_head = NULL;
    p_map->p_tail = NULL;
}

int unordered_map_t_size(unordered_map_t* p_map)
{
    return p_map ? p_map->size : -1;
}

bool unordered_map_t_is_healthy(unordered_map_t* p_map)
{
    size_t counter;
    unordered_map_entry_t* p_entry;

    if (!p_map) return false;

    counter = 0;
    p_entry = p_map->p_head;

    if (p_entry && p_entry->p_prev) return false;

    for (; p_entry; p_entry = p_entry->p_next)
    {
        counter++;
    }

    return counter == p_map->size;
}

void unordered_map_t_free(unordered_map_t* p_map)
{
    if (!p_map) return;

    unordered_map_t_clear(p_map);
    free(p_map->p_table);
    free(p_map);
}

unordered_map_iterator_t* 
unordered_map_iterator_t_alloc(unordered_map_t* p_map)
{
    unordered_map_iterator_t* p_ret;

    if (!p_map) return NULL;

    p_ret = malloc(sizeof(*p_ret));

    if (!p_ret) return NULL;

    p_ret->p_map              = p_map;
    p_ret->iterated_count     = 0;
    p_ret->p_next_entry       = p_map->p_head;
    p_ret->expected_mod_count = p_map->mod_count;

    return p_ret;
}

int unordered_map_iterator_t_has_next(unordered_map_iterator_t* p_iterator)
{
    if (!p_iterator) return 0;

    if (unordered_map_iterator_t_is_disturbed(p_iterator)) return 0;

    return p_iterator->p_map->size - p_iterator->iterated_count;
}

bool unordered_map_iterator_t_next(unordered_map_iterator_t* p_iterator, 
                                   void** pp_key, 
                                   void** pp_value)
{
    if (!p_iterator)                                       return false;
    if (!p_iterator->p_next_entry)                         return false;
    if (unordered_map_iterator_t_is_disturbed(p_iterator)) return false;

    *pp_key   = p_iterator->p_next_entry->p_key;
    *pp_value = p_iterator->p_next_entry->p_value;
    p_iterator->iterated_count++;
    p_iterator->p_next_entry = p_iterator->p_next_entry->p_next;
    return true;
}

bool
unordered_map_iterator_t_is_disturbed(unordered_map_iterator_t* p_iterator)
{
    if (!p_iterator) false;

    return p_iterator->expected_mod_count != p_iterator->p_map->mod_count;
}

void unordered_map_iterator_t_free(unordered_map_iterator_t* p_iterator)
{
    if (!p_iterator) return;

    p_iterator->p_map = NULL;
    p_iterator->p_next_entry = NULL;
    free(p_iterator);
}

Demonstration driver with other stuff may be found in coderodde.c.utils.

Is there anything I could do in order to improve the data structure?

\$\endgroup\$

1 Answer 1

Reset to default
3
\$\begingroup\$

Pointer used after free

In your clear() function, there is this code:

while (p_entry)
{
    index = p_map->p_hash_function(p_entry->p_key) & p_map->mask;
    p_next_entry = p_entry->p_next;
    free(p_entry);
    p_entry = p_next_entry;

    if (p_map->p_table[index])
    {
        p_map->p_table[index] = p_map->p_table[index]->p_chain_next;
    }
}

Notice that after the entry is freed, you take the bucket head and move it forward by one element. But the head of that bucket is the entry you just freed. So when you access p_chain_next, you are reading into the entry you just freed.

Actually I wouldn't even bother advancing the bucket heads one by one. Since you are clearing the entire hash table, I would probably just memset the entire table to zero. That way you don't have to call the hash function on each entry.

Double call to hash function

In your put() function, you end up calling the hash function twice if the element doesn't already exist, because you double check in case the table may have increased in size since the first call. Since the hash function may be slow, you should store the result of the hash in a local variable to avoid calling the hash function again. An alternative solution would be to add the entry first and then resize the table after.

Out of memory check

In your alloc() function, you're missing a NULL check for when you allocate p_table. That allocation may well fail because the user can pass in an arbitrarily large initial capacity.

Simplify list removal

In your remove() function, you use an if-else block of four cases to remove a node from a doubly linked list:

        /* Unlink from the global iteration chain. */
        if (p_current_entry->p_prev && p_current_entry->p_next) 
        {
            /* Once here, the current entry has both next and previous. */
            p_current_entry->p_prev->p_next = p_current_entry->p_next;
            p_current_entry->p_next->p_prev = p_current_entry->p_prev;
        }
        else if (!p_current_entry->p_prev && !p_current_entry->p_next)
        {
            /* Once here, the current entry 
               is the only entry in the chain. */
            p_map->p_head = NULL;
            p_map->p_tail = NULL;
        }
        else if (p_current_entry->p_next)
        {
            /* Once here, the current entry is the head of the chain. */
            p_map->p_head = p_current_entry->p_next;
            p_map->p_head->p_prev = NULL;
        }
        else
        {
            /* Once here, the current entry is the tail of the chain. */
            p_map->p_tail = p_current_entry->p_prev;
            p_map->p_tail->p_next = NULL;
        }

You can actually handle each of the head and tail cases separately like this:

        /* Unlink from the global iteration chain. */
        if (p_current_entry->p_prev) {
            p_current_entry->p_prev->p_next = p_current_entry->p_next;
        } else {
            p_map->p_head = p_current_entry->p_next;
        }
        if (p_current_entry->p_next) {
            p_current_entry->p_next->p_prev = p_current_entry->p_prev;
        } else {
            p_map->p_tail = p_current_entry->p_prev;
        }

Use common find function

Right now, you have four nearly identical copies of code to find an existing entry in get(), contains_key(), put(), and remove(). I would recommend writing an internal find_entry() function that all four functions can use.

Note that the four uses aren't all the same. remove() also needs to know the previous entry pointer, and put() also needs to know the hash value if the entry didn't exist. So you'll have to figure out how you want to write your find_entry() function to make that happen.

Use size_t

You use size_t almost everywhere, which is good. But you missed two spots. The return values of your size() and has_next() functions should return size_t instead of int.

Out of date comment

The comment for the is_healthy function says something about an AVL-tree. It must have been copy and pasted from your previous project.

const

A lot of your functions could take const arguments since they do not modify the argument. For example:

int unordered_map_t_size(const unordered_map_t* p_map);

Floating point

The Floating Point Police™ would like to point out that you could avoid using floating point. Instead of a floating point load factor, you could use a fixed point value. For example, the load factor could be a value between 1..256 and represent a fraction out of 256.

Why bother, you ask? When you use floating point:

  1. The OS needs to start saving/restoring floating point state for your process every time you context switch.
  2. If the OS decides to lazily save/restore your floating point state, you will take an exception the first time you use floating point after a context switch. This exception tells the OS that it needs to swap in the floating point state now.

Of course, you probably won't even notice these things are happening (I compare it to garbage collection and Java). And it's perfectly fine to use floating point if you want to. It's just a personal preference of mine to avoid floating point whenever possible.

\$\endgroup\$
8
  • \$\begingroup\$ "I compare it to garbage collection and Java" That sounds kind of sarcastic. :D \$\endgroup\$ Commented Sep 2, 2015 at 18:09
  • \$\begingroup\$ @coderodde I meant it's just some kind of overhead that you don't really notice or think about. But if your program has real-time response requirements, you actually start to care about these things. \$\endgroup\$ Commented Sep 2, 2015 at 18:12
  • \$\begingroup\$ I fear your argument about floating points is premature optimization \$\endgroup\$ Commented Sep 2, 2015 at 18:36
  • \$\begingroup\$ @Caridorc I never liked the phrase "premature optimization" because people tend to use it to mean "I don't have to care about optimization". If you always avoid some kind of bad practice, I don't consider that premature optimization. It's like the x86 assembly person who knows that using add %eax, %eax, 1 is faster than inc %eax. For any normal program, it probably doesn't matter which instruction you use. But once you know that one way is better, you just always do it that way. \$\endgroup\$ Commented Sep 2, 2015 at 18:53
  • \$\begingroup\$ @Caridorc BTW I grew up in a world where floating point in hardware didn't always exist, and sometimes had to be emulated in software. So that probably influences my behavior somewhat. I also work on things that are very low level and close to the hardware. So a lot of times, real time performance matters to me. \$\endgroup\$ Commented Sep 2, 2015 at 18:55

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.