NVMLib  very early alpha
A library to optimally use a Hybrid RAM setup.
Macros | Typedefs | Enumerations | Functions
hashmap.h File Reference
#include <stdbool.h>
#include <stdlib.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.

Macros

#define LOAD_FACTOR   0.8
 
#define HASH_MAP(VALUE_TYPE)   VALUE_TYPE##_hash_map
 
#define HASH_MAP_BUCKET(VALUE_TYPE)   VALUE_TYPE##_hash_map_bucket
 
#define HASH_MAP_INSERT(VALUE_TYPE)   insert_into_##VALUE_TYPE##_hash_map
 
#define HASH_MAP_FIND(VALUE_TYPE)   find_in_##VALUE_TYPE##_hash_map
 
#define HASH_MAP_CREATE(VALUE_TYPE)   create_new_##VALUE_TYPE##_hash_map
 
#define HASH_MAP_ERASE(VALUE_TYPE)   erase_from_##VALUE_TYPE##_hash_map
 
#define HASH_MAP_DESTROY(VALUE_TYPE)   destroy_##VALUE_TYPE##_hash_map
 
#define _HASH_STRUCTURE(VALUE_TYPE)
 
#define DECLARE_HASHMAP(VALUE_TYPE)
 Declaration of HashMap of a given type. More...
 
#define DEFINE_HASHMAP(VALUE_TYPE, CMP, GET_HASH, FREE, REALLOC)
 Definition of the declared HashMap. More...
 
#define HASH_MAP_PRINT(VALUE_TYPE)   print_##VALUE_TYPE##_hash_map
 For Debug purposes. More...
 
#define HASH_MAP_PRINT_FUNC(VALUE_TYPE, PRINT_OBJ_FUNC)
 

Typedefs

typedef __uint128_t uint128_t
 
typedef __uint64_t uint64_t
 
typedef __uint32_t uint32_t
 
typedef __uint16_t uint16_t
 
typedef __uint8_t uint8_t
 

Enumerations

enum  HashMapDuplicateResolution { HMDR_FAIL = 0, HMDR_FIND, HMDR_REPLACE, HMDR_SWAP }
 
enum  HashMapResult {
  HMR_FAILED = 0, HMR_FOUND, HMR_REPLACED, HMR_SWAPPED,
  HMR_INSERTED
}
 

Functions

static size_t next_power_of_two (size_t i)
 
static size_t index_for_hash (size_t hash, size_t shift, size_t pow_of_two)
 Fibonacci hashing 11400714819323198485ull = 2^64 / golden_ratio. More...
 

Detailed Description

This file provides a generic hashmap stored in DRAM.

This hashmap will be a chaining hashmap, with load factor = 0.8 no. of buckets = power of 2 hash function for distribution = fibonacci hashing hash function for hashing the object = User provided

See also
object_maintainance.c pool.c

Definition in file hashmap.h.

Macro Definition Documentation

◆ _HASH_STRUCTURE

#define _HASH_STRUCTURE (   VALUE_TYPE)
Value:
struct {\
size_t size; /*current size*/\
size_t power_of_two; /*capacity*/\
VALUE_TYPE *entries;\
}

Definition at line 75 of file hashmap.h.

◆ DECLARE_HASHMAP

#define DECLARE_HASHMAP (   VALUE_TYPE)

Declaration of HashMap of a given type.

Parameters
VALUE_TYPE: The type of entries that would be stored. It has to be the Typedef'd name, i.e struct abc is not allowed.

Definition at line 88 of file hashmap.h.

◆ DEFINE_HASHMAP

#define DEFINE_HASHMAP (   VALUE_TYPE,
  CMP,
  GET_HASH,
  FREE,
  REALLOC 
)

Definition of the declared HashMap.

Parameters
VALUE_TYPE: Type of stored entries. It has to be Typedef'd name.
CMP: int (*cmp)(VALUE_TYPE *left, VALUE_TYPE *right). Could easily be a macro. Must return 0 if and only if *left equals *right.
GET_HASH: inttype (*getHash)(VALUE_TYPE *entry). Could easily be a macro.
FREE: free() to use
REALLOC: realloc() to use.

Definition at line 127 of file hashmap.h.

◆ HASH_MAP

#define HASH_MAP (   VALUE_TYPE)    VALUE_TYPE##_hash_map

Definition at line 30 of file hashmap.h.

◆ HASH_MAP_BUCKET

#define HASH_MAP_BUCKET (   VALUE_TYPE)    VALUE_TYPE##_hash_map_bucket

Definition at line 31 of file hashmap.h.

◆ HASH_MAP_CREATE

#define HASH_MAP_CREATE (   VALUE_TYPE)    create_new_##VALUE_TYPE##_hash_map

Definition at line 35 of file hashmap.h.

◆ HASH_MAP_DESTROY

#define HASH_MAP_DESTROY (   VALUE_TYPE)    destroy_##VALUE_TYPE##_hash_map

Definition at line 37 of file hashmap.h.

◆ HASH_MAP_ERASE

#define HASH_MAP_ERASE (   VALUE_TYPE)    erase_from_##VALUE_TYPE##_hash_map

Definition at line 36 of file hashmap.h.

◆ HASH_MAP_FIND

#define HASH_MAP_FIND (   VALUE_TYPE)    find_in_##VALUE_TYPE##_hash_map

Definition at line 34 of file hashmap.h.

◆ HASH_MAP_INSERT

#define HASH_MAP_INSERT (   VALUE_TYPE)    insert_into_##VALUE_TYPE##_hash_map

Definition at line 33 of file hashmap.h.

◆ HASH_MAP_PRINT

#define HASH_MAP_PRINT (   VALUE_TYPE)    print_##VALUE_TYPE##_hash_map

For Debug purposes.

Parameters
VALUE_TYPE: Type of stored entries. It has to be Typedef'd name.
PRINT_OBJ_FUNC: void (*print_obj)(VALUE_TYPE entry). A function to print the contents of the stored object. Could be a marco too.

Definition at line 294 of file hashmap.h.

◆ HASH_MAP_PRINT_FUNC

#define HASH_MAP_PRINT_FUNC (   VALUE_TYPE,
  PRINT_OBJ_FUNC 
)
Value:
void print_##VALUE_TYPE##_hash_map(HASH_MAP(VALUE_TYPE) *map) {\
if(!map->entries){\
return;\
}\
for(size_t i = 0; i < map->power_of_two ; i++) {\
printf("%ld ---> ", i);\
HASH_MAP_BUCKET(VALUE_TYPE) *bucket = &map->entries[i];\
printf("size = %ld || ", bucket->size);\
for(int j = 0; j < bucket->size; j++) {\
PRINT_OBJ_FUNC(&bucket->entries[j]);\
printf(" | ");\
}\
printf("\n");\
}\
printf("\n");\
}

Definition at line 296 of file hashmap.h.

◆ LOAD_FACTOR

#define LOAD_FACTOR   0.8

Definition at line 28 of file hashmap.h.

Typedef Documentation

◆ uint128_t

typedef __uint128_t uint128_t

Definition at line 21 of file hashmap.h.

◆ uint16_t

typedef __uint16_t uint16_t

Definition at line 24 of file hashmap.h.

◆ uint32_t

typedef __uint32_t uint32_t

Definition at line 23 of file hashmap.h.

◆ uint64_t

typedef __uint64_t uint64_t

Definition at line 22 of file hashmap.h.

◆ uint8_t

typedef __uint8_t uint8_t

Definition at line 25 of file hashmap.h.

Enumeration Type Documentation

◆ HashMapDuplicateResolution

enum HashMapDuplicateResolution
Enumerator
HMDR_FAIL 
HMDR_FIND 
HMDR_REPLACE 
HMDR_SWAP 

Definition at line 38 of file hashmap.h.

◆ HashMapResult

enum HashMapResult
Enumerator
HMR_FAILED 
HMR_FOUND 
HMR_REPLACED 
HMR_SWAPPED 
HMR_INSERTED 

Definition at line 45 of file hashmap.h.

Function Documentation

◆ index_for_hash()

static size_t index_for_hash ( size_t  hash,
size_t  shift,
size_t  pow_of_two 
)
inlinestatic

Fibonacci hashing 11400714819323198485ull = 2^64 / golden_ratio.

Definition at line 69 of file hashmap.h.

Here is the call graph for this function:

◆ next_power_of_two()

static size_t next_power_of_two ( size_t  i)
inlinestatic

Definition at line 53 of file hashmap.h.

HASH_MAP
#define HASH_MAP(VALUE_TYPE)
Definition: hashmap.h:29