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