7
\$\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\$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.