6
\$\begingroup\$

I have this bidirectional hash map in C for dealing with bijective maps. Each key mapping consists of a primary key and a secondary key, and I can ask the data structure to give me a secondary key given a primary key, or vice versa, to give me a primary key given a secondary key.

I store the actual mappings in key_pair_t records. Also, I have two hash tables: the primary hash table and the secondary hash table. The primary hash table maps each array component to a doubly-linked list of primary collision chain nodes, and I do the same for the secondary hash table.

As a possible speed-up technique, I keep the hash values for both the keys in each key_pair_t; this reduces some hashing and may provide a slight performance gain when dealing, say, with strings or other containers.

To recap the structure:

Bidirectional hash map

Here is my code:

bidirectional_hash_map.h

#ifndef BIDIRECTIONAL_HASH_MAP_H
#define BIDIRECTIONAL_HASH_MAP_H

#include <stdlib.h>

typedef struct key_pair_t {

    /*******************
    * The primary key. *
    *******************/
    void* primary_key;

    /*********************
    * The secondary key. *
    *********************/
    void* secondary_key;

    /*******************************
    * The hash of the primary key. *
    *******************************/
    size_t primary_key_hash;

    /********************************
    * The hash of the secondary key *
    ********************************/
    size_t secondary_key_hash;
}
key_pair_t;

/********************************************************
* The collision chain node type for primary key chains. *
********************************************************/
typedef struct primary_collision_chain_node_t {

    /*************************************************************************
    * Points to the previous collision chain node or is set to NULL if there *
    * is no previous collision chain node.                                   *
    *************************************************************************/
    struct primary_collision_chain_node_t* prev;

    /***************************************************************************
    * Points to the next collision chain node or is set to NULL if there is no *
    * next collision chain node.                                               *
    ***************************************************************************/
    struct primary_collision_chain_node_t* next;

    /**************************************************************************
    * The previously added node. This field is used for faster iteration over *
    * the entire hash map.                                                    *
    **************************************************************************/
    struct primary_collision_chain_node_t* up;

    /***************************************************************************
    * The collision chain node added after this collision chain node. Used for *
    * faster iteration over the hash map.                                      *
    ***************************************************************************/
    struct primary_collision_chain_node_t* down;

    /*******************************************
    * Points to the actual key pair structure. *
    *******************************************/
    key_pair_t* key_pair;
}
primary_collision_chain_node_t;

/**********************************************************
* The collision chain node type for secondary key chains. *
**********************************************************/
typedef struct secondary_collision_chain_node_t {

    /*************************************************************************
    * Points to the previous collision chain node or is set to NULL if there *
    * is no previous collision chain node.                                   *
    *************************************************************************/
    struct secondary_collision_chain_node_t* prev;

    /***************************************************************************
    * Points to the next collision chain node or is set to NULL if there is no *
    * next collision chain node.                                               *
    ***************************************************************************/
    struct secondary_collision_chain_node_t* next;

    /*******************************************
    * Points to the actual key pair structure. *
    *******************************************/
    key_pair_t* key_pair;
}
secondary_collision_chain_node_t;

typedef struct bidirectional_hash_map_t {

    /**********************************
    * Caches the number of key pairs. *
    **********************************/
    size_t size;

    /*********************************************
    * Holds the capacity of the two hash tables. *
    *********************************************/
    size_t capacity;

    /*************************
    * Stores the load factor *
    *************************/
    float  load_factor;

    /***************************************
    * The mask used for simulating modulo. *
    ***************************************/ 
    size_t modulo_mask;

    /**************************
    * The primary hash table. *
    **************************/
    struct primary_collision_chain_node_t** primary_key_table;

    /****************************
    * The secondary hash table. *
    ****************************/
    struct secondary_collision_chain_node_t** secondary_key_table;

    /***************************************************************************
    * The function producing the bucket index in the primary key table given a *
    * primary key.                                                             *
    ***************************************************************************/
    size_t (*primary_key_hasher)(void* primary_key);

    /***************************************************************************
    * The function producing the bucket index in the secondary key table given *
    * a secondary key.                                                         *
    ***************************************************************************/
    size_t (*secondary_key_hasher)(void* secondary_key);

    /*****************************************************
    * The function for comparing two given primary keys. *
    *****************************************************/
    int    (*primary_key_equality)(void* primary_key_1, void* primary_key_2);

    /*******************************************************
    * The function for comparing two given secondary keys. *
    *******************************************************/
    int    (*secondary_key_equality)(void* secondary_key_1,
                                     void* secondary_key_2);

    /***************************************************************************
    * Caches the primary collision chain node of the mapping that was added to *
    * this hash map. Used for starting the iteration over all mappings. We     *
    * need this since the hash map may be too sparse after, say, adding a lot  *
    * of elements and removing most of them.                                   *
    ***************************************************************************/
    struct primary_collision_chain_node_t* first_collision_chain_node;

    /***************************************************************************
    * Caches the most recently added mapping to this hash map. We need this in *
    * order to link new mappings to the mapping list.                          *
    ***************************************************************************/
    struct primary_collision_chain_node_t* last_collision_chain_node;

    /*****************************************
    * A value that is returned upon failure. *
    *****************************************/
    void* error_sentinel;
}
bidirectional_hash_map_t;

typedef struct bidirectional_hash_map_iterator_t {

    /************************************
    * The mapping next to iterate over. *
    ************************************/
    struct primary_collision_chain_node_t* current_node;

    /**************************************
    * Number of mappings iterated so far. *
    **************************************/
    size_t iterated;

    /**************************************
    * The size of the map being iterated. *
    **************************************/
    size_t map_size;
}
bidirectional_hash_map_iterator_t;

/****************************************************************************
* Builds a new, empty bidirectional hash map.|                              *
*--------------------------------------------+                              *
* map -------------------- the map to initialize.                           *
* initial_capacity ------- the initial capacity of both the hash tables.    *
* load_factor ------------ the load factor.                                 *
* primary_key_hasher ----- the function for producing primary key hashes.   *
* secondary_key_hasher --- the function for producing secondary key hashes. *
* primary_key_equality --- the function for comparing primary keys.         *
* secondary_key_equality - the function for comparing secondary keys.       *
*-----------------------------------------------------------+               *
* RETURNS: 1 if initialization was successfull, 0 otherwise.|               *
****************************************************************************/
int bidirectional_hash_map_t_init(
        bidirectional_hash_map_t* map,
        size_t initial_capacity,
        float load_factor,
        size_t (*primary_key_hasher)  (void*),
        size_t (*secondary_key_hasher)(void*),
        int (*primary_key_equality)   (void*, void*),
        int (*secondary_key_equality)  (void*, void*),
        void* error_sentinel);

/************************************************
* Releases all the resources of the input map.| *
*---------------------------------------------+ *
* map - the map to destroy.                     *
************************************************/
void bidirectional_hash_map_t_destroy(bidirectional_hash_map_t* map);

/********************************************************************
* Checks that the map is well formed and is ready to receive data.| *
*-----------------------------------------------------------------+ *
* map - the map to check.                                           *
*------------------------------------------------+                  *
* RETURNS: 1 if the map is in order, 0 otherwise.|                  *
********************************************************************/
int bidirectional_hash_map_t_is_working(bidirectional_hash_map_t* map);

/*****************************************************
* Returns the number of key pairs in the input map.| *
*--------------------------------------------------+ *
* map - the map to query.                            *
*----------------------------------------------+     *
* RETURNS: the number of key pairs in this map.|     *
*****************************************************/
size_t bidirectional_hash_map_t_size(bidirectional_hash_map_t* map);

/*****************************************************************************
* Returns the capacity of one of the hash tables (another one has the same | *
* capacity).                                                               | *
*--------------------------------------------------------------------------+ *
* map - the map to query.                                                    *
*------------------------------------------+                                 *
* RETURNS: the capacity of each hash table.|                                 *
*****************************************************************************/
size_t bidirectional_hash_map_t_capacity(bidirectional_hash_map_t* map);

/******************************************************************************
* Associates the primary key to the secondary key in the input map.|          *
*------------------------------------------------------------------+          *
* map ----------- the map into which to store the pair.                       *
* primary_key --- the primary key.                                            *
* secondary_key - the secondary key.                                          *
*-------------------------------------------------------------------------- + *
* RETURNS: old secondary key in case the primary key is in the map, NULL if | *
* the primary key has no mappings yet.                                      | *
******************************************************************************/
void* bidirectional_hash_map_t_put_by_primary(bidirectional_hash_map_t* map,
                                              void* primary_key,
                                              void* secondary_key);

/******************************************************************************
* Associates the secondary key to the primary key in the input map.|          *
*------------------------------------------------------------------+          *
* map ----------- the map into which to store the pair.                       *
* primary_key --- the primary key.                                            *
* secondary_key - the secondary key.                                          *
*---------------------------------------------------------------------------+ *
* RETURNS: old primary key in case the secondary key is in the map, NULL if | *
* the secondary key has no mappings yet.                                    | *
******************************************************************************/
void* bidirectional_hash_map_t_put_by_secondary(bidirectional_hash_map_t* map,
                                                void* primary_key,
                                                void* secondary_key);

/******************************************************************************
* Removes a key pair by its primary key.|                                     *
*---------------------------------------+                                     *
* map --------- the map.                                                      *
* primary_key - the primary key.                                              *
*---------------------------------------------------------------------------+ *
* RETURNS: NULL if the primary key is not mapped. The current associated    | *
* secondary key otherwise.                                                  | *
******************************************************************************/
void* bidirectional_hash_map_t_remove_by_primary_key(
        bidirectional_hash_map_t* map,
        void* primary_key);

/****************************************************************************
* Removes a key pair by its secondary key.|                                 *
*-----------------------------------------+                                 *
* map --------- the map.                                                    *
* secondary_key - the primary key.                                          *
*-------------------------------------------------------------------------+ *
* RETURNS: NULL if the seconary key is not mapped. The current associated | *
* primary key otherwise.                                                  | *
****************************************************************************/
void* bidirectional_hash_map_t_remove_by_secondary_key(
        bidirectional_hash_map_t* map,
        void* secondary_key);

/******************************************************************************
* Queries the secondary key via its primary key.|                             *
*-----------------------------------------------+                             *
* map --------- the map to query.                                             *
* primary_key - the primary key to use.                                       *
*---------------------------------------------------------------------------+ *
* RETURNS: If the primary key is associated with a secondary key, that very | *
* secondary key is returned. Otherwise, NULL is returned.                   | *
******************************************************************************/
void* bidirectional_hash_map_t_get_by_primary_key(bidirectional_hash_map_t* map,
                                                  void* primary_key);

/******************************************************************************
* Queries the primary key via its secondary key.|                             *
*-----------------------------------------------+                             *
* map --------- the map to query.                                             *
* secondary_key - the secondary key to use.                                   *
*---------------------------------------------------------------------------+ *
* RETURNS: If the secondary key is associated with a primary key, that very | *
* primary key is returned. Otherwise, NULL is returned.                     | *
******************************************************************************/
void* bidirectional_hash_map_t_get_by_secondary_key(
        bidirectional_hash_map_t* map,
        void* secondary_key);

/**************************************************************************
* Queries whether the map contains 'primary_key' as a primary key.|       *
*-----------------------------------------------------------------+       *
* map --- the map to query.                                               *
* primary_key - the primary key to query.                                 *
*-----------------------------------------------------------------------+ *
* RETURNS: If the primary key is in the map, returns 1. Otherwise, 0 is | *
* returned.                                                             | *
**************************************************************************/
int bidirectional_hash_map_t_contains_primary_key(bidirectional_hash_map_t* map,
                                                  void* primary_key);

/****************************************************************************
* Queries whether the map contains 'secondary_key' as a secondary key.|     *
*---------------------------------------------------------------------+     *
* map ----------- the map to query.                                         *
* secondary_key - the primary key to query.                                 *
*-------------------------------------------------------------------------+ *
* RETURNS: If the secondary key is in the map, returns 1. Otherwise, 0 is | *
* returned.                                                               | *
****************************************************************************/
int bidirectional_hash_map_t_contains_secondary_key(
                                                bidirectional_hash_map_t* map,
                                                void* secondary_key);

#endif /* BIDIRECTIONAL_HASH_MAP_H */

... some declarations omitted since everything does not fit. 

bidirectional_hash_map_c

#include "bidirectional_hash_map.h"
#include <stdlib.h>

static float max_float(float a, float b)
{
    return a > b ? a : b;
}

static size_t max_size_t(size_t a, size_t b)
{
    return a > b ? a : b;
}

/****************************************************************
* Returns an integer that is a power of two no less than 'num'. *
****************************************************************/
static size_t to_power_of_two(size_t num)
{
    size_t ret = 1;

    while (ret < num)
    {
        ret <<= 1;
    }

    return  ret;
}

static const float  MINIMUM_LOAD_FACTOR      = 0.2;
static const size_t MINIMUM_INITIAL_CAPACITY = 8;

/*************************************************************************
* This function unlinks 'primary_collision_chain_node' from it collision *
* chain.                                                                 *
*************************************************************************/
static void unlink_primary_collision_chain_node(
                bidirectional_hash_map_t* map,
                primary_collision_chain_node_t* primary_collision_chain_node)
{
    size_t primary_node_collision_chain_bucket_index;

    if (primary_collision_chain_node->prev)
    {
        primary_collision_chain_node->prev->next =
        primary_collision_chain_node->next;
    }
    else
    {
        primary_node_collision_chain_bucket_index =
        primary_collision_chain_node->key_pair
        ->primary_key_hash & map->modulo_mask;

        map->primary_key_table[primary_node_collision_chain_bucket_index] =
        map->primary_key_table[primary_node_collision_chain_bucket_index]->next;
    }

    if (primary_collision_chain_node->next)
    {
        primary_collision_chain_node->next->prev =
        primary_collision_chain_node->prev;
    }
}

/****************************************************************************
* This function unlinks 'secondary_collision_chain_node' from its collision *
* chain.                                                                    *
****************************************************************************/
static void unlink_secondary_collision_chain_node(
            bidirectional_hash_map_t* map,
            secondary_collision_chain_node_t* secondary_collision_chain_node)
{
    size_t secondary_node_collision_chain_bucket_index;

    if (secondary_collision_chain_node->prev)
    {
        secondary_collision_chain_node->prev->next =
        secondary_collision_chain_node->next;
    }
    else
    {
        secondary_node_collision_chain_bucket_index =
        secondary_collision_chain_node->key_pair
        ->secondary_key_hash & map->modulo_mask;

        map->secondary_key_table[secondary_node_collision_chain_bucket_index] =
        map->secondary_key_table[secondary_node_collision_chain_bucket_index]
           ->next;
    }

    if (secondary_collision_chain_node->next)
    {
        secondary_collision_chain_node->next->prev =
        secondary_collision_chain_node->prev;
    }
}

/*************************************************************
* Finds a secondary collision chain node that corresponds to *
* 'primary_collision_chain_node'.                            *
*************************************************************/
static secondary_collision_chain_node_t*
find_secondary_collision_chain_node_via_primary_collision_chain_node(
                bidirectional_hash_map_t* map,
                primary_collision_chain_node_t* primary_collision_chain_node)
{
    size_t secondary_collision_chain_node_bucket_index =
    primary_collision_chain_node->key_pair
    ->secondary_key_hash & map->modulo_mask;

    secondary_collision_chain_node_t* secondary_collision_chain_node =
    map->secondary_key_table[secondary_collision_chain_node_bucket_index];

    for (;
         secondary_collision_chain_node;
         secondary_collision_chain_node = secondary_collision_chain_node->next)
    {
        if (secondary_collision_chain_node->key_pair ==
            primary_collision_chain_node->key_pair)
        {
            break;
        }
    }

    return secondary_collision_chain_node;
}

/***********************************************************
* Finds a primary collision chain node that corresponds to *
* 'secondary_collision_chain_node'.                        *
***********************************************************/
static primary_collision_chain_node_t*
find_primary_collision_chain_node_via_secondary_collision_chain_node(
            bidirectional_hash_map_t* map,
            secondary_collision_chain_node_t* secondary_collision_chain_node)
{
    size_t primary_collision_chain_node_bucket_index =
    secondary_collision_chain_node->key_pair
    ->primary_key_hash & map->modulo_mask;

    primary_collision_chain_node_t* primary_collision_chain_node =
    map->primary_key_table[primary_collision_chain_node_bucket_index];

    for (;
         primary_collision_chain_node;
         primary_collision_chain_node = primary_collision_chain_node->next)
    {
        if (primary_collision_chain_node->key_pair ==
            secondary_collision_chain_node->key_pair)
        {
            break;
        }
    }

    return primary_collision_chain_node;
}

/**************************************************************************
* This function removes 'primary_collision_chain_node' from the iteration *
* list.                                                                   *
**************************************************************************/
static void unlink_primary_collision_chain_node_from_iteraton_list(
                                                                   bidirectional_hash_map_t* map,
                                                                   primary_collision_chain_node_t* primary_collision_chain_node)
{
    if (primary_collision_chain_node->up == NULL)
    {
        map->first_collision_chain_node = primary_collision_chain_node->down;
    }
    else
    {
        primary_collision_chain_node->up->down =
        primary_collision_chain_node->down;
    }

    if (primary_collision_chain_node->down == NULL)
    {
        map->last_collision_chain_node = primary_collision_chain_node->up;
    }
    else
    {
        primary_collision_chain_node->down->up =
        primary_collision_chain_node->up;
    }
}

/****************************************************************************
* This function is responsible for removing a primary/secondary key mapping *
* from the bidirectional hash map.                                          *
****************************************************************************/
static void remove_mapping(
                bidirectional_hash_map_t* map,
                primary_collision_chain_node_t* primary_collision_chain_node)
{
    secondary_collision_chain_node_t* secondary_collision_chain_node =
    find_secondary_collision_chain_node_via_primary_collision_chain_node(
                                                map,
                                                primary_collision_chain_node);

    free(primary_collision_chain_node->key_pair);
    unlink_primary_collision_chain_node_from_iteraton_list(
                                                map,
                                                primary_collision_chain_node);

    /*****************************************************
    * Unlink and purge the primary collision chain node: *
    *****************************************************/
    unlink_primary_collision_chain_node(map, primary_collision_chain_node);
    free(primary_collision_chain_node);

    /*******************************************************
    * Unlink and purge the secondary collision chain node: *
    *******************************************************/
    unlink_secondary_collision_chain_node(map, secondary_collision_chain_node);
    free(secondary_collision_chain_node);
}

/*************************************************************************
* This functions returns a primary collision chain node corresponding to *
* 'primary_key'.                                                         *
*************************************************************************/
static primary_collision_chain_node_t* find_primary_collision_chain_node(
                                                bidirectional_hash_map_t* map,
                                                void* primary_key)
{
    size_t primary_key_hash = map->primary_key_hasher(primary_key);

    size_t primary_key_collision_chain_bucket_index =
    primary_key_hash & map->modulo_mask;

    primary_collision_chain_node_t* primary_collision_chain_node =
    map->primary_key_table[primary_key_collision_chain_bucket_index];

    for (;
         primary_collision_chain_node;
         primary_collision_chain_node = primary_collision_chain_node->next)
    {
        if (primary_collision_chain_node->key_pair->primary_key_hash ==
            primary_key_hash)
        {
            if (map->primary_key_equality(
                        primary_key,
                        primary_collision_chain_node->key_pair->primary_key))
            {
                break;
            }
        }
    }

    return primary_collision_chain_node;
}

/***************************************************************************
* This functions returns a secondary collision chain node corresponding to *
* 'secondary_key'.                                                         *
***************************************************************************/
static secondary_collision_chain_node_t* find_secondary_collision_chain_node(
                                                bidirectional_hash_map_t* map,
                                                void* secondary_key)
{
    size_t secondary_key_hash = map->secondary_key_hasher(secondary_key);

    size_t secondary_key_collision_chain_bucket_index =
    secondary_key_hash & map->modulo_mask;

    secondary_collision_chain_node_t* secondary_collision_chain_node =
    map->secondary_key_table[secondary_key_collision_chain_bucket_index];

    for (;
         secondary_collision_chain_node;
         secondary_collision_chain_node = secondary_collision_chain_node->next)
    {
        if (secondary_collision_chain_node->key_pair->secondary_key_hash ==
            secondary_key_hash)
        {
            if (map->secondary_key_equality(
                    secondary_key,
                    secondary_collision_chain_node->key_pair->secondary_key))
            {
                break;
            }
        }
    }

    return secondary_collision_chain_node;
}

int bidirectional_hash_map_t_init(
                                bidirectional_hash_map_t* map,
                                size_t initial_capacity,
                                float load_factor,
                                size_t (*primary_key_hasher)  (void*),
                                size_t (*secondary_key_hasher)(void*),
                                int (*primary_key_equality)   (void*, void*),
                                int (*secondary_key_equality) (void*, void*),
                                void* error_sentinel)
{
    if (!map)
    {
        return 0;
    }

    if (!primary_key_hasher ||
        !secondary_key_hasher ||
        !primary_key_equality ||
        !secondary_key_equality)
    {
        return 0;
    }

    load_factor      = max_float(load_factor, MINIMUM_LOAD_FACTOR);
    initial_capacity = max_size_t(initial_capacity, MINIMUM_INITIAL_CAPACITY);
    initial_capacity = to_power_of_two(initial_capacity);

    map->primary_key_table   = NULL;
    map->secondary_key_table = NULL;
    map->capacity            = initial_capacity;
    map->load_factor         = load_factor;
    map->size                = 0;

    map->primary_key_table = calloc(initial_capacity,
                                    sizeof(primary_collision_chain_node_t*));

    if (!map->primary_key_table)
    {
        return 0;
    }

    map->secondary_key_table =
        calloc(initial_capacity, sizeof(secondary_collision_chain_node_t*));

    if (!map->secondary_key_table)
    {
        free(map->primary_key_table);
        map->primary_key_table = NULL;
        return 0;
    }

    map->modulo_mask            = map->capacity - 1;
    map->primary_key_hasher     = primary_key_hasher;
    map->secondary_key_hasher   = secondary_key_hasher;
    map->primary_key_equality   = primary_key_equality;
    map->secondary_key_equality = secondary_key_equality;
    map->error_sentinel         = error_sentinel;

    return 1;
}

void bidirectional_hash_map_t_destroy(bidirectional_hash_map_t* map)
{
    primary_collision_chain_node_t* primary_collision_chain_node;
    primary_collision_chain_node_t* primary_collision_chain_node_next;

    if (!map)
    {
        return;
    }

    if (!map->primary_key_table)
    {
        /*********************************************************************
        * The input map is invalid (failed to be constructed due to shortage *
        * of memory).                                                        *
        *********************************************************************/
        return;
    }

    primary_collision_chain_node = map->first_collision_chain_node;

    /*************************
    * Free the mapping data. *
    *************************/
    while (primary_collision_chain_node)
    {
        primary_collision_chain_node_next = primary_collision_chain_node->down;
        remove_mapping(map, primary_collision_chain_node);
        primary_collision_chain_node = primary_collision_chain_node_next;
    }

    /*******************************
    * Free the actual hash tables. *
    *******************************/
    free(map->primary_key_table);
    free(map->secondary_key_table);

    map->primary_key_table   = NULL;
    map->secondary_key_table = NULL;
    map->first_collision_chain_node = NULL;
    map->last_collision_chain_node = NULL;
    map->capacity = 0;
    map->size = 0;
}

int bidirectional_hash_map_t_is_working(bidirectional_hash_map_t* map)
{
    return map->primary_key_table ? 1 : 0;
}

size_t bidirectional_hash_map_t_size(bidirectional_hash_map_t* map)
{
    return map->size;
}

size_t bidirectional_hash_map_t_capacity(bidirectional_hash_map_t* map)
{
    return map->capacity;
}

/*****************************************************************************
* This function relinks all the mappings (key pairs and collision chains) to *
* new hash tables.                                                           *
*****************************************************************************/
static void relink_to_new_tables(
                bidirectional_hash_map_t* map,
                primary_collision_chain_node_t* primary_collision_chain_node,
                primary_collision_chain_node_t** next_primary_hash_table,
                secondary_collision_chain_node_t** next_secondary_hash_table)
{
    size_t primary_collision_chain_bucket_index;
    size_t secondary_collision_chain_bucket_index;
    size_t next_capacity;
    size_t next_modulo_mask;

    secondary_collision_chain_node_t* secondary_collision_chain_node =
        find_secondary_collision_chain_node_via_primary_collision_chain_node(
                                                map,
                                                primary_collision_chain_node);

    /********************************************************************
    * Unlink the 'primary_collision_chain_node' from its current chain. *
    ********************************************************************/
    unlink_primary_collision_chain_node(map, primary_collision_chain_node);

    /*********************************************************
    * Unlink the opposite collision chain node of            *
    * 'primary_collision_chain_node' from its current chain. *
    *********************************************************/
    unlink_secondary_collision_chain_node(map, secondary_collision_chain_node);

    /*******************************************************
    * Relink both 'primary_collision_chain_node' and       *
    * 'secondary_collision_chain_node' to new hash tables. *
    *******************************************************/
    next_capacity = map->capacity << 1;
    next_modulo_mask = next_capacity - 1;

    /*************************************************************
    * Link 'primary_collision_chain_node' to its new hash table. *
    *************************************************************/
    primary_collision_chain_bucket_index =
    primary_collision_chain_node->key_pair->primary_key_hash & next_modulo_mask;

    primary_collision_chain_node->prev = NULL;
    primary_collision_chain_node->next =
    next_primary_hash_table[primary_collision_chain_bucket_index];

    if (next_primary_hash_table[primary_collision_chain_bucket_index])
    {
        next_primary_hash_table[primary_collision_chain_bucket_index]->prev =
        primary_collision_chain_node;
    }

    next_primary_hash_table[primary_collision_chain_bucket_index] =
    primary_collision_chain_node;

    /***************************************************************
    * Link 'secondary_collision_chain_node' to its new hash table. *
    ***************************************************************/
    secondary_collision_chain_bucket_index =
    secondary_collision_chain_node->key_pair->secondary_key_hash
    & next_modulo_mask;

    secondary_collision_chain_node->prev = NULL;
    secondary_collision_chain_node->next =
    next_secondary_hash_table[secondary_collision_chain_bucket_index];

    if (next_secondary_hash_table[secondary_collision_chain_bucket_index])
    {
        next_secondary_hash_table[secondary_collision_chain_bucket_index]->prev
        = secondary_collision_chain_node;
    }

    next_secondary_hash_table[secondary_collision_chain_bucket_index] =
    secondary_collision_chain_node;
}

/*******************************************************************************
* This function is responsible for allocating larger hash tables and relinking *
* all current collision chain nodes and key pairs to them.                     *
*******************************************************************************/
static int expand_hash_map(bidirectional_hash_map_t* map)
{
    size_t next_capacity;
    size_t next_modulo_mask;
    primary_collision_chain_node_t** next_primary_hash_table;
    secondary_collision_chain_node_t** next_secondary_hash_table;
    primary_collision_chain_node_t* primary_collision_chain_node;
    primary_collision_chain_node_t* primary_collision_chain_node_next;

    next_capacity = map->capacity << 1;

    next_primary_hash_table = calloc(next_capacity,
                                     sizeof(primary_collision_chain_node_t*));

    if (!next_primary_hash_table)
    {
        return 0;
    }

    next_secondary_hash_table =
        calloc(next_capacity, sizeof(secondary_collision_chain_node_t*));

    if (!next_secondary_hash_table)
    {
        free(next_primary_hash_table);
        return 0;
    }

    next_modulo_mask = next_capacity - 1;
    primary_collision_chain_node = map->first_collision_chain_node;

    while (primary_collision_chain_node)
    {
        primary_collision_chain_node_next = primary_collision_chain_node->down;
        relink_to_new_tables(map,
                             primary_collision_chain_node,
                             next_primary_hash_table,
                             next_secondary_hash_table);

        primary_collision_chain_node = primary_collision_chain_node_next;
    }

    free(map->primary_key_table);
    free(map->secondary_key_table);

    map->primary_key_table = next_primary_hash_table;
    map->secondary_key_table = next_secondary_hash_table;
    map->capacity = next_capacity;
    map->modulo_mask = next_modulo_mask;

    return 1;
}

/************************************************************************
* This function is responsible for updating a primary key of a mapping. *
************************************************************************/
static void* update_primary_key(
            bidirectional_hash_map_t* map,
            secondary_collision_chain_node_t* secondary_collision_chain_node,
            void* new_primary_key)
{
    void* old_primary_key;
    size_t new_primary_key_hash;
    size_t new_primary_key_collision_chain_bucket_index;

    /*******************************************************
    * Find the corresponding primary collision chain node: *
    *******************************************************/
    primary_collision_chain_node_t* primary_collision_chain_node =
    find_primary_collision_chain_node_via_secondary_collision_chain_node(
                                                map,
                                                secondary_collision_chain_node);

    old_primary_key = primary_collision_chain_node->key_pair->primary_key;

    /**************************************************************************
    * Unlink 'primary_collision_chain_node' from its current collision chain: *
    **************************************************************************/
    unlink_primary_collision_chain_node(map, primary_collision_chain_node);

    /************************************************************************
    * Link the unlinked 'primary_collision_chain_node' to its new collision *
    * chain. Updates the actual key and its hash as well.                   *
    ************************************************************************/
    new_primary_key_hash = map->primary_key_hasher(new_primary_key);
    new_primary_key_collision_chain_bucket_index =
    new_primary_key_hash & map->modulo_mask;

    primary_collision_chain_node->key_pair->primary_key = new_primary_key;
    primary_collision_chain_node->key_pair->primary_key_hash =
    new_primary_key_hash;

    primary_collision_chain_node->prev = NULL;
    primary_collision_chain_node->next =
    map->primary_key_table[new_primary_key_collision_chain_bucket_index];

    if (map->primary_key_table[new_primary_key_collision_chain_bucket_index])
    {
        map->primary_key_table[new_primary_key_collision_chain_bucket_index]
           ->prev = primary_collision_chain_node;
    }

    map->primary_key_table[new_primary_key_collision_chain_bucket_index] =
    primary_collision_chain_node;

    return old_primary_key;
}

static void* update_secondary_key(
                bidirectional_hash_map_t* map,
                primary_collision_chain_node_t* primary_collision_chain_node,
                void* new_secondary_key)
{
    void* old_secondary_key;
    size_t new_secondary_key_hash;
    size_t new_secondary_key_collision_chain_bucket_index;

    /*********************************************************
    * Find the corresponding secondary collision chain node: *
    *********************************************************/
    secondary_collision_chain_node_t* secondary_collision_chain_node =
        find_secondary_collision_chain_node_via_primary_collision_chain_node(
                                                map,
                                                primary_collision_chain_node);

    old_secondary_key = secondary_collision_chain_node->key_pair->secondary_key;

    /*********************************************************************
    * Unlink 'secondary_collision_chain_node' from its current collision *
    * chain:                                                             *
    *********************************************************************/
    unlink_secondary_collision_chain_node(map, secondary_collision_chain_node);

    /***************************************************************************
    * Links the unlinked 'secondary_collision_chain_node' to its new collision *
    * chain. Updates the actual key and its has as well.                       *
    ***************************************************************************/
    new_secondary_key_hash = map->secondary_key_hasher(new_secondary_key);
    new_secondary_key_collision_chain_bucket_index =
    new_secondary_key_hash & map->modulo_mask;

    secondary_collision_chain_node->key_pair->secondary_key = new_secondary_key;
    secondary_collision_chain_node->key_pair->secondary_key_hash =
    new_secondary_key_hash;

    secondary_collision_chain_node->prev = NULL;
    secondary_collision_chain_node->next =
    map->secondary_key_table[new_secondary_key_collision_chain_bucket_index];

    if (map->
        secondary_key_table[new_secondary_key_collision_chain_bucket_index])
    {
        map->secondary_key_table[new_secondary_key_collision_chain_bucket_index]
           ->prev = secondary_collision_chain_node;
    }

    map->secondary_key_table[new_secondary_key_collision_chain_bucket_index] =
    secondary_collision_chain_node;

    return old_secondary_key;
}

/*******************************************************************************
* Adds a new mapping to the map. A mapping (primary_key, secondary_key) is     *
* "new" if primary_key is not mapped to anything and secondary is not mapped   *
* to anything as well. This function also increments the 'size' of the map.    *
*******************************************************************************/
static int add_new_mapping(bidirectional_hash_map_t* map,
                           void* primary_key,
                           void* secondary_key)
{
    key_pair_t* key_pair;
    primary_collision_chain_node_t* primary_collision_chain_node;
    secondary_collision_chain_node_t* secondary_collision_chain_node;
    size_t primary_key_collision_chain_bucket_index;
    size_t secondary_key_collision_chain_bucket_index;

    if (map->size > map->capacity * map->load_factor)
    {
        if (!expand_hash_map(map))
        {
            return 0;
        }
    }

    key_pair = malloc(sizeof(*key_pair));

    if (!key_pair)
    {
        return 0;
    }

    primary_collision_chain_node =
    malloc(sizeof(*primary_collision_chain_node));

    if (!primary_collision_chain_node)
    {
        free(key_pair);
        return 0;
    }

    secondary_collision_chain_node =
    malloc(sizeof(*secondary_collision_chain_node));

    if (!secondary_collision_chain_node)
    {
        free(key_pair);
        free(primary_collision_chain_node);
        return 0;
    }

    key_pair->primary_key = primary_key;
    key_pair->primary_key_hash = map->primary_key_hasher(primary_key);
    key_pair->secondary_key = secondary_key;
    key_pair->secondary_key_hash = map->secondary_key_hasher(secondary_key);

    /****************************************************
    * Link 'primary_collision_chain_node' to its table: *
    ****************************************************/
    primary_collision_chain_node->key_pair = key_pair;
    primary_collision_chain_node->prev = NULL;
    primary_key_collision_chain_bucket_index =
    key_pair->primary_key_hash & map->modulo_mask;

    primary_collision_chain_node->next =
    map->primary_key_table[primary_key_collision_chain_bucket_index];

    if (map->primary_key_table[primary_key_collision_chain_bucket_index])
    {
        map->primary_key_table[primary_key_collision_chain_bucket_index]->prev =
        primary_collision_chain_node;
    }

    map->primary_key_table[primary_key_collision_chain_bucket_index] =
    primary_collision_chain_node;

    /******************************************************
    * Link 'secondary_collision_chain_node' to its table: *
    ******************************************************/
    secondary_collision_chain_node->key_pair = key_pair;
    secondary_collision_chain_node->prev = NULL;
    secondary_key_collision_chain_bucket_index =
    key_pair->secondary_key_hash & map->modulo_mask;

    secondary_collision_chain_node->next =
    map->secondary_key_table[secondary_key_collision_chain_bucket_index];

    if (map->secondary_key_table[secondary_key_collision_chain_bucket_index])
    {
        map->secondary_key_table[secondary_key_collision_chain_bucket_index]
        ->prev = secondary_collision_chain_node;
    }

    map->secondary_key_table[secondary_key_collision_chain_bucket_index] =
    secondary_collision_chain_node;

    /********************************
    * Deal with the iteration list. *
    ********************************/ 
    if (map->size == 0)
    {
        map->first_collision_chain_node = primary_collision_chain_node;
        map->last_collision_chain_node = primary_collision_chain_node;
        primary_collision_chain_node->up = NULL;
        primary_collision_chain_node->down = NULL;
    }
    else
    {
        primary_collision_chain_node->up = map->last_collision_chain_node;
        primary_collision_chain_node->down = NULL;
        map->last_collision_chain_node->down = primary_collision_chain_node;
        map->last_collision_chain_node = primary_collision_chain_node;
    }

    map->size++;
    return 1;
}

void* bidirectional_hash_map_t_put_by_primary(bidirectional_hash_map_t* map,
                                              void* primary_key,
                                              void* secondary_key)
{
    size_t primary_key_hash;
    size_t primary_key_collision_chain_bucket_index;
    primary_collision_chain_node_t* primary_collision_chain_node;
    void* return_value;

    primary_key_hash = map->primary_key_hasher(primary_key);
    primary_key_collision_chain_bucket_index =
    primary_key_hash & map->modulo_mask;

    primary_collision_chain_node =
        find_primary_collision_chain_node(map, primary_key);

    if (primary_collision_chain_node)
    {
        return update_secondary_key(map,
                                    primary_collision_chain_node,
                                    secondary_key);
    }
    else
    {
        add_new_mapping(map, primary_key, secondary_key);
        return NULL;
    }
}

void* bidirectional_hash_map_t_put_by_secondary(bidirectional_hash_map_t* map,
                                                void* primary_key,
                                                void* secondary_key)
{
    size_t secondary_key_hash;
    size_t secondary_key_collision_chain_bucket_index;
    secondary_collision_chain_node_t* secondary_collision_chain_node;
    void* return_value;

    secondary_key_hash = map->secondary_key_hasher(secondary_key);
    secondary_key_collision_chain_bucket_index =
    secondary_key_hash & map->modulo_mask;

    secondary_collision_chain_node =
        find_secondary_collision_chain_node(map, secondary_key);

    if (secondary_collision_chain_node)
    {
        return update_primary_key(map,
                                  secondary_collision_chain_node,
                                  primary_key);
    }
    else
    {
        add_new_mapping(map, primary_key, secondary_key);
        return NULL;
    }
}

void* bidirectional_hash_map_t_remove_by_primary_key(
                                                bidirectional_hash_map_t* map,
                                                void* primary_key)
{
    primary_collision_chain_node_t* primary_collision_chain_node =
        find_primary_collision_chain_node(map, primary_key);

    secondary_collision_chain_node_t* secondary_collision_chain_node =
        find_secondary_collision_chain_node_via_primary_collision_chain_node(
                                                map,
                                                primary_collision_chain_node);
    void* secondary_key;

    if (primary_collision_chain_node == NULL)
    {
        return NULL;
    }

    unlink_primary_collision_chain_node(map, primary_collision_chain_node);
    unlink_secondary_collision_chain_node(map, secondary_collision_chain_node);
    secondary_key = primary_collision_chain_node->key_pair->secondary_key;

    unlink_primary_collision_chain_node_from_iteraton_list(
                                                map,
                                                primary_collision_chain_node);

    free(primary_collision_chain_node->key_pair);
    free(primary_collision_chain_node);
    free(secondary_collision_chain_node);

    return secondary_key;
}

void* bidirectional_hash_map_t_remove_by_secondary_key(
                                                bidirectional_hash_map_t* map,
                                                void* secondary_key)
{
    secondary_collision_chain_node_t* secondary_collision_chain_node =
        find_secondary_collision_chain_node(map, secondary_key);

    primary_collision_chain_node_t* primary_collision_chain_node =
        find_primary_collision_chain_node_via_secondary_collision_chain_node(
                                                map,
                                                secondary_collision_chain_node);
    void* primary_key;

    if (secondary_collision_chain_node == NULL)
    {
        return NULL;
    }

    unlink_primary_collision_chain_node(map, primary_collision_chain_node);
    unlink_secondary_collision_chain_node(map, secondary_collision_chain_node);
    primary_key = primary_collision_chain_node->key_pair->primary_key;

    unlink_primary_collision_chain_node_from_iteraton_list(
                                                map,
                                                primary_collision_chain_node);

    unlink_primary_collision_chain_node_from_iteraton_list(map, primary_collision_chain_node);

    free(primary_collision_chain_node->key_pair);
    free(primary_collision_chain_node);
    free(secondary_collision_chain_node);

    return primary_key;
}

void* bidirectional_hash_map_t_get_by_primary_key(bidirectional_hash_map_t* map,
                                                  void* primary_key)
{
    primary_collision_chain_node_t* primary_collision_chain_node =
        find_primary_collision_chain_node(map, primary_key);

    secondary_collision_chain_node_t* secondary_collision_chain_node;

    if (primary_collision_chain_node == NULL)
    {
        return NULL;
    }

    secondary_collision_chain_node =
        find_secondary_collision_chain_node_via_primary_collision_chain_node(
                                                map,
                                                primary_collision_chain_node);

    return secondary_collision_chain_node->key_pair->secondary_key;
}

void* bidirectional_hash_map_t_get_by_secondary_key(
                                                bidirectional_hash_map_t* map,
                                                void* secondary_key)
{
    secondary_collision_chain_node_t* secondary_collision_chain_node =
        find_secondary_collision_chain_node(map, secondary_key);

    primary_collision_chain_node_t* primary_collision_chain_node;

    if (secondary_collision_chain_node == NULL)
    {
        return NULL;
    }

    primary_collision_chain_node =
        find_primary_collision_chain_node_via_secondary_collision_chain_node(
                                                map,
                                                secondary_collision_chain_node);

    return secondary_collision_chain_node->key_pair->primary_key;
}

int bidirectional_hash_map_t_contains_primary_key(bidirectional_hash_map_t* map,
                                                  void* primary_key)
{
    primary_collision_chain_node_t* primary_collision_chain_node =
        find_primary_collision_chain_node(map, primary_key);

    return primary_collision_chain_node != NULL ? 1 : 0;
}

int bidirectional_hash_map_t_contains_secondary_key(
                                                    bidirectional_hash_map_t* map,
                                                    void* secondary_key)
{
    secondary_collision_chain_node_t* secondary_collision_chain_node =
        find_secondary_collision_chain_node(map, secondary_key);

    return secondary_collision_chain_node != NULL ? 1 : 0;
}

int bidirectional_hash_map_iterator_t_init(
                                           bidirectional_hash_map_t* map,
                                           bidirectional_hash_map_iterator_t* iterator)
{
    if (!map)
    {
        return 0;
    }

    iterator->current_node = map->first_collision_chain_node;
    iterator->iterated = 0;
    iterator->map_size = map->size;

    return 1;
}

int bidirectional_hash_map_iterator_t_has_next(
                                               bidirectional_hash_map_iterator_t* iterator)
{
    return iterator->iterated < iterator->map_size;
}

int bidirectional_hash_map_iterator_t_next(
                                           bidirectional_hash_map_iterator_t* iterator,
                                           void** primary_key_ptr,
                                           void** secondary_key_ptr)
{
    if (iterator->iterated >= iterator->map_size)
    {
        return 0;
    }

    *primary_key_ptr = iterator->current_node->key_pair->primary_key;
    *secondary_key_ptr = iterator->current_node->key_pair->secondary_key;
    iterator->current_node = iterator->current_node->down;
    return 1;
}

The entire project with a test driver is here: https://github.com/coderodde/bidirectional_hash_map_t

Critique request

I would like to hear comments on naming, design, code layout, adherence to C programming idioms, usability, to name a few. Please tell me anything that comes to mind.

Note

I used ANSI C. I know there is C99 and C11, but I like the old way.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.