hashmap.h File Reference

This is an implementation of Compressed Hash-Array Mapped Prefix-tree, which is a bit-partitioned, persistent, immutable Hashed array mapped trie. More...

#include <stddef.h>
#include <stdint.h>
#include "serene/rt/errors.h"

Include dependency graph for hashmap.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	hmap_key_t
	Note: For key equality we use the memcpy function. More...
struct	hmap_kv_entry_t
struct	hmap_node_t
struct	hmap_t
struct	hmap_control_t
	If we ever want to modify some of these behaviours for a new instance of hashmap, we should use this control type. More...

Macros
#define	HMAP_BR   32u
	branching factor (power of two)
#define	HMAP_SHIFT   5u
#define	HMAP_MASK   (HMAP_BR - 1u)
#define	HMAP_HASH_SIZE   32u
	By default we use 32bit hashes.
#define	HMAP_HASH_TYPE   uint32_t
#define	HMAP_BITMAP_TYPE   uint32_t

Typedefs
typedef HMAP_HASH_TYPE	hmap_hash_t
typedef HMAP_BITMAP_TYPE	hmap_bitmap_t
typedef void *	hmap_data_t
typedef struct hmap_key_t	hmap_key_t
	Note: For key equality we use the memcpy function.
typedef struct hmap_kv_entry_t	hmap_kv_entry_t
typedef struct hmap_node_t	hmap_node_t
typedef struct hmap_t	hmap_t
typedef struct hmap_control_t	hmap_control_t
	If we ever want to modify some of these behaviours for a new instance of hashmap, we should use this control type.

Functions
hmap_t	hmap_empty (const srn_context_t *ctx)
	Create, initialize and return a new hashmap pinned to ctx.
hmap_t	hmap_insert (const hmap_t *hmap, hmap_key_t *k, void *v)
	Insert the given key k with the value v in the given hash hmap and return the new map.
hmap_t	hmap_insert_ctl (const hmap_control_t *ctl, const hmap_t *hmap, hmap_key_t *k, void *v)
	Just like the hmap_insert function but, it receives a hmap_control_t to customize the comparison and hashing function.
void *	hmap_lookup (const hmap_t *hmap, const hmap_key_t *k, void *default_value)
	Lookup the given k in the given hmap and return the value if it's been found.
void *	hmap_lookup_ctl (const hmap_control_t *ctl, const hmap_t *hmap, const hmap_key_t *k, void *default_value)
	Just like the hmap_lookup function but, it receives a hmap_control_t to customize the comparison and hashing function.
hmap_hash_t	hmap_hash (const srn_context_t *ctx, const void *data, size_t len)
	This is a simple hack to mock the hash function during tests to force a high collision hashing function.
hmap_key_t *	hmap_make_key (srn_context_t *ctx, void *data, size_t len)
	Create a new key out of the given data, with the given len.
hmap_key_t *	hmap_copy_key (const hmap_t *hmap, const hmap_key_t *k)
	The default copy_key hook.

Variables
hmap_control_t	hmap_default_control

Detailed Description

This is an implementation of Compressed Hash-Array Mapped Prefix-tree, which is a bit-partitioned, persistent, immutable Hashed array mapped trie.

For more information, have a look at the Optimizing Hash-Array Mapped Tries for Fast and Lean Immutable JVM Collections paper.

TL;DR:

• Every struct is immutable
• Nodes are persistent and immutable.
• Nodes are heap allocated
• Heads can be stack allocated
• We create a new head for any change and probably will create inner nodes as well depending on the change
• New heads will share structure with the older version
• This is not a ordered hashmap
• The hashing function HAS TO BE DETERMINISTIC
• Don't use pointers value as the data to hash, use the data that they point to instead.

Definition in file hashmap.h.

Macro Definition Documentation

HMAP_BITMAP_TYPE

#define HMAP_BITMAP_TYPE   uint32_t

Definition at line 59 of file hashmap.h.

HMAP_BR

#define HMAP_BR   32u

branching factor (power of two)

Definition at line 54 of file hashmap.h.

HMAP_HASH_SIZE

#define HMAP_HASH_SIZE   32u

By default we use 32bit hashes.

Definition at line 57 of file hashmap.h.

HMAP_HASH_TYPE

#define HMAP_HASH_TYPE   uint32_t

Definition at line 58 of file hashmap.h.

HMAP_MASK

#define HMAP_MASK   (HMAP_BR - 1u)

Definition at line 56 of file hashmap.h.

HMAP_SHIFT

#define HMAP_SHIFT   5u

Definition at line 55 of file hashmap.h.

Typedef Documentation

hmap_bitmap_t

typedef HMAP_BITMAP_TYPE hmap_bitmap_t

Definition at line 62 of file hashmap.h.

hmap_control_t

typedef struct hmap_control_t hmap_control_t

If we ever want to modify some of these behaviours for a new instance of hashmap, we should use this control type.

hmap_data_t

typedef void* hmap_data_t

Definition at line 63 of file hashmap.h.

hmap_hash_t

typedef HMAP_HASH_TYPE hmap_hash_t

Definition at line 61 of file hashmap.h.

hmap_key_t

typedef struct hmap_key_t hmap_key_t

Note: For key equality we use the memcpy function.

hmap_kv_entry_t

typedef struct hmap_kv_entry_t hmap_kv_entry_t

hmap_node_t

typedef struct hmap_node_t hmap_node_t

hmap_t

typedef struct hmap_t hmap_t

Function Documentation

hmap_copy_key()

hmap_key_t * hmap_copy_key	(	const hmap_t *	hmap,
		const hmap_key_t *	k )

The default copy_key hook.

Clone the key struct and its bytes into the map's map_ctx so the map never retains pointers into a caller's block.

Definition at line 678 of file hashmap.c.

                                                                   {
  PANIC_IF_NULL(hmap);
  PANIC_IF_NULL(k);
  PANIC_IF_NULL(hmap->map_ctx);
 
  hmap_key_t *copy = ALLOC(hmap->map_ctx, hmap_key_t);
  copy->len        = k->len;
  copy->data =
    (k->len == 0) ? nullptr : srn_copy_bytes(hmap->map_ctx, k->data, k->len, alignof(char));
  return copy;
}

Here is the call graph for this function:

hmap_empty()

hmap_t hmap_empty ( const srn_context_t * ctx )

nodiscard

Create, initialize and return a new hashmap pinned to ctx.

The pinned context owns every allocation the map (and all of its future versions) retains, so pick a context that lives at least as long as the map.

Definition at line 655 of file hashmap.c.

                                            {
  PANIC_IF_NULL(ctx);
  hmap_t map = {.len = 0, .root = nullptr, .map_ctx = ctx};
  return map;
}

Here is the caller graph for this function:

hmap_hash()

hmap_hash_t hmap_hash	(	const srn_context_t *	ctx,
		const void *	data,
		size_t	len )

This is a simple hack to mock the hash function during tests to force a high collision hashing function.

Outside of tests, this will be a wrapper around srn_hash.

Definition at line 77 of file hashmap.c.

                                                                              {
  return srn_hash(ctx->engine, data, len);
}

Here is the call graph for this function:

Here is the caller graph for this function:

hmap_insert()

hmap_t hmap_insert ( const hmap_t * hmap, hmap_key_t * k, void * v )

nodiscard

Insert the given key k with the value v in the given hash hmap and return the new map.

The new map will share parts of its structure with the old map and never mutate the old map. All retained allocations go through the map's map_ctx. The control's copy_key clones the key into it, so k may point at stack or transient memory. The value v is stored as is and must outlive the map.

Definition at line 661 of file hashmap.c.

                                                               {
  return hmap_default_control.insert(&hmap_default_control, hmap, k, v);
}

Here is the caller graph for this function:

hmap_insert_ctl()

hmap_t hmap_insert_ctl ( const hmap_control_t * ctl, const hmap_t * hmap, hmap_key_t * k, void * v )

nodiscard

Just like the hmap_insert function but, it receives a hmap_control_t to customize the comparison and hashing function.

Definition at line 594 of file hashmap.c.

                                                                                              {
  PANIC_IF_NULL(ctl);
  PANIC_IF_NULL(hmap);
  PANIC_IF_NULL(k);
  PANIC_IF_NULL(ctl->copy_key);
 
  // Everything the map retains has to live in the map's context, so the map
  // survives the release of the inserting caller's context. A null map_ctx
  // means the map was zero-initialized instead of created with hmap_empty.
  const srn_context_t *map_ctx = hmap->map_ctx;
  PANIC_IF_NULL(map_ctx);
 
  hmap_hash_t hash = ctl->hash(hmap, k);
  hmap_key_t *key  = ctl->copy_key(hmap, k);
  hmap_t new_map   = *hmap;
 
  HMAP_LOG("Trying to insert a key with the hash: %x", hash);
 
  if (hmap->root == nullptr) {
    // First insertion, just create a singleton node.
    HMAP_LOG("First insertion on an empty map");
    hmap_kv_entry_t *kv = hmap_new_kv_entry(map_ctx, hash, key, v);
    hmap_node_t *root   = hmap_singleton_node(map_ctx, hash, 0, kv);
 
    new_map.root = root;
    new_map.len  = hmap->len + 1;
    return new_map;
  }
  HMAP_LOG("Find the correct node to insert the key");
  // Create the intermediate nodes recursively
  bool added            = false;
  hmap_node_t *new_root = hmap_insert_node(ctl, hmap, hmap->root, hash, key, v, 0, &added);
 
  new_map.root = new_root;
  if (added) {
    HMAP_LOG("The key was added successfully");
    new_map.len = hmap->len + 1;
  } else {
    HMAP_LOG("The key existed, just updated the value");
    new_map.len = hmap->len;
  }
  return new_map;
}

Here is the call graph for this function:

Here is the caller graph for this function:

hmap_lookup()

void * hmap_lookup ( const hmap_t * hmap, const hmap_key_t * k, void * default_value )

nodiscard

Lookup the given k in the given hmap and return the value if it's been found.

Otherwise return the default_value value. Since a nullptr is a valid value for any keys, returning a nullptr is not a good option to indicate that the key does not exist, So it's safer to use explicit values to differenciate between a missing key and a legit nullptr as a value.

Definition at line 665 of file hashmap.c.

                                                                                {
  return hmap_default_control.lookup(&hmap_default_control, hmap, k, default_value);
}

Here is the caller graph for this function:

hmap_lookup_ctl()

void * hmap_lookup_ctl	(	const hmap_control_t *	ctl,
		const hmap_t *	hmap,
		const hmap_key_t *	k,
		void *	default_value )

Just like the hmap_lookup function but, it receives a hmap_control_t to customize the comparison and hashing function.

Definition at line 638 of file hashmap.c.

  {
  PANIC_IF_NULL(ctl);
  PANIC_IF_NULL(hmap);
  PANIC_IF_NULL(k);
 
  PANIC_IF_NULL(hmap->map_ctx);
 
  if (hmap->root == nullptr) {
    return default_value;
  }
 
  hmap_hash_t hash = ctl->hash(hmap, k);
  return hmap_lookup_in_node(ctl, hmap, hmap->root, hash, k, 0, default_value);
}

Here is the call graph for this function:

Here is the caller graph for this function:

hmap_make_key()

hmap_key_t * hmap_make_key	(	srn_context_t *	ctx,
		void *	data,
		size_t	len )

Create a new key out of the given data, with the given len.

Definition at line 669 of file hashmap.c.

                                                                      {
  PANIC_IF_NULL(ctx);
  PANIC_IF_NULL(data);
  hmap_key_t *key = ALLOC(ctx, hmap_key_t);
  key->data       = data;
  key->len        = len;
  return key;
}

Variable Documentation

hmap_default_control

hmap_control_t hmap_default_control

extern

Definition at line 690 of file hashmap.c.

                                    {
  .cmp      = &hmap_internal_cmp,
  .hash     = &hmap_hash_internal,
  .insert   = &hmap_insert_ctl,
  .lookup   = &hmap_lookup_ctl,
  .copy_key = &hmap_copy_key,
};