nemea-common  1.6.3
Data Structures | Macros | Enumerations | Functions | Variables
fast_hash_table.h File Reference

Fast 4-way hash table with stash - header file. More...

#include <inttypes.h>
#include <stdlib.h>
#include <string.h>

Go to the source code of this file.

Data Structures

struct  fht_table_t
 
struct  fht_iter_t
 

Macros

#define FHT_TABLE_COLS   4
 
#define FHT_COL_FULL   ((uint8_t) 0x000F)
 

Enumerations

enum  fht_table {
  FHT_INSERT_OK = 0, FHT_INSERT_LOST = 1, FHT_INSERT_STASH_OK = 2, FHT_INSERT_STASH_LOST = 3,
  FHT_INSERT_FAILED = -1, FHT_INSERT_FULL = -2
}
 
enum  fht_iter {
  FHT_ITER_RET_OK = 0, FHT_ITER_RET_END = 1, FHT_ITER_START = -1, FHT_ITER_STASH = -2,
  FHT_ITER_END = -3
}
 

Functions

fht_table_tfht_init (uint32_t table_rows, uint32_t key_size, uint32_t data_size, uint32_t stash_size)
 Function for initializing the hash table. More...
 
int fht_insert (fht_table_t *table, const void *key, const void *data, void *key_lost, void *data_lost)
 Function for inserting the item into the table without using stash. More...
 
int fht_insert_wr (fht_table_t *table, const void *key, const void *data)
 Function for inserting the item into the table without using stash and without replacing the oldest item when the row is full. More...
 
int fht_insert_with_stash (fht_table_t *table, const void *key, const void *data, void *key_lost, void *data_lost)
 Function for inserting the item into the table using stash. More...
 
int fht_insert_with_stash_wr (fht_table_t *table, const void *key, const void *data)
 Function for inserting the item into the table using stash and without replacing items in stash. More...
 
int fht_remove (fht_table_t *table, const void *key)
 Function for removing item from the table without looking for in stash. More...
 
int fht_remove_locked (fht_table_t *table, const void *key, int8_t *lock_ptr)
 Function for removing item from the table without looking for in stash. Function does not locks lock, it can be used only to remove item which is locked (after use of function fht_get_data_locked or fht_get_data_with_stash_locked). More...
 
int fht_remove_with_stash (fht_table_t *table, const void *key)
 Function for removing item from the table with looking for in stash. More...
 
int fht_remove_with_stash_locked (fht_table_t *table, const void *key, int8_t *lock_ptr)
 Function for removing item from the table with looking for in stash. Function does not locks lock, it can be used only to remove item which is locked (after use of function fht_get_data_locked or fht_get_data_with_stash_locked). More...
 
int fht_remove_iter (fht_iter_t *iter)
 Function for removing actual item from the table when using iterator. More...
 
void fht_clear (fht_table_t *table)
 Function for clearing the table. More...
 
void fht_destroy (fht_table_t *table)
 Function for destroying the table and freeing memory. More...
 
fht_iter_tfht_init_iter (fht_table_t *table)
 Function for initializing iterator for the table. More...
 
void fht_reinit_iter (fht_iter_t *iter)
 Function for reinitializing iterator for the table. More...
 
int32_t fht_get_next_iter (fht_iter_t *iter)
 Function for getting next item in the table. More...
 
void fht_destroy_iter (fht_iter_t *iter)
 Function for destroying iterator and freeing memory. More...
 

Variables

uint8_t lt_free_flag []
 
uint8_t lt_pow_of_two []
 
uint8_t lt_replacement_vector [][4]
 
uint8_t lt_replacement_vector_remove [][4]
 
uint8_t lt_replacement_index []
 

Detailed Description

Fast 4-way hash table with stash - header file.

Author
Matej Vido, xvido.nosp@m.m00@.nosp@m.stud..nosp@m.fit..nosp@m.vutbr.nosp@m..cz
Date
2014

Definition in file fast_hash_table.h.

Macro Definition Documentation

◆ FHT_COL_FULL

#define FHT_COL_FULL   ((uint8_t) 0x000F)

Value of free flag when column is full.

Definition at line 63 of file fast_hash_table.h.

◆ FHT_TABLE_COLS

#define FHT_TABLE_COLS   4

Number of columns in the hash table.

Definition at line 58 of file fast_hash_table.h.

Enumeration Type Documentation

◆ fht_iter

enum fht_iter

Constants used for iterator functions.

Enumerator
FHT_ITER_RET_OK 
FHT_ITER_RET_END 
FHT_ITER_START 
FHT_ITER_STASH 
FHT_ITER_END 

Definition at line 90 of file fast_hash_table.h.

◆ fht_table

enum fht_table

Constants used for table functions.

Enumerator
FHT_INSERT_OK 
FHT_INSERT_LOST 
FHT_INSERT_STASH_OK 
FHT_INSERT_STASH_LOST 
FHT_INSERT_FAILED 
FHT_INSERT_FULL 

Definition at line 77 of file fast_hash_table.h.

Function Documentation

◆ fht_clear()

void fht_clear ( fht_table_t table)

Function for clearing the table.

Function sets replacement flags of all items in the table and in stash to zero. Items with zero replacement flag are considered free. Data and keys remain in table.

Parameters
tablePointer to the hash table structure.

◆ fht_destroy()

void fht_destroy ( fht_table_t table)

Function for destroying the table and freeing memory.

Function frees memory of the table structure.

Parameters
tablePointer to the hash table structure.

◆ fht_destroy_iter()

void fht_destroy_iter ( fht_iter_t iter)

Function for destroying iterator and freeing memory.

If function is used in the middle of the table, function also unlocks row or stash, which is locked.

Parameters
iterPointer to the iterator structure.

◆ fht_get_next_iter()

int32_t fht_get_next_iter ( fht_iter_t iter)

Function for getting next item in the table.

Parameters
iterPointer to the iterator structure.
Returns
FHT_ITER_RET_OK if iterator structure contain next structure. FHT_ITER_RET_END if iterator is in the end of the table and does not contain any other item.

◆ fht_init()

fht_table_t* fht_init ( uint32_t  table_rows,
uint32_t  key_size,
uint32_t  data_size,
uint32_t  stash_size 
)

Function for initializing the hash table.

Parameters need to meet following requirements: table_rows - non-zero, power of two key_size - non-zero data_size - non-zero stash_size - power of two

Parameters
table_rowsNumber of rows in the table.
key_sizeSize of key in bytes.
data_sizeSize of data in bytes.
stash_sizeNumber of items in stash.
Returns
Pointer to the structure of the hash table, NULL if the memory couldn't be allocated or parameters do not meet requirements.

◆ fht_init_iter()

fht_iter_t* fht_init_iter ( fht_table_t table)

Function for initializing iterator for the table.

Parameters
tablePointer to the hash table structure.
Returns
Pointer to the iterator structure. NULL if could not allocate memory.

◆ fht_insert()

int fht_insert ( fht_table_t table,
const void *  key,
const void *  data,
void *  key_lost,
void *  data_lost 
)

Function for inserting the item into the table without using stash.

Function checks whether there already is item with the key "key" in the table. If not, function inserts the item in the table. Function checks whether there is free place in the current row. If yes, new item is inserted. If not, new item will replace the oldest item in row according to replacement vector. Function updates replacement vector and free flag.

key_lost and data_lost are set only when the return value is FHT_INSERT_LOST.

Parameters
tablePointer to the hash table structure.
keyPointer to key of the inserted item.
dataPointer to data of the inserted item.
key_lostPointer to memory, where key of the replaced item will be inserted. If NULL, key of that item will be lost.
data_lostPointer to memory, where data of the replaced item will be inserted. If NULL, data of that item will be lost.
Returns
FHT_INSERT_OK if the item was successfully inserted. FHT_INSERT_LOST if the inserted item pulled out the oldest item in the row of the table. FHT_INSERT_FAILED if there already is an item with such key in the table.

◆ fht_insert_with_stash()

int fht_insert_with_stash ( fht_table_t table,
const void *  key,
const void *  data,
void *  key_lost,
void *  data_lost 
)

Function for inserting the item into the table using stash.

Function checks whether there already is item with the key "key" in the table. If not, function inserts the item in the table. Function checks whether there is free place in the current row. If yes, new item is inserted. If not, new item will replace the oldest item in row according to replacement vector and the oldest item is inserted in stash. Function updates replacement vector and free flag.

Parameters
tablePointer to the hash table structure.
keyPointer to key of the inserted item.
dataPointer to data of the inserted item.
key_lostPointer to memory, where key of the replaced item will be inserted. If NULL, key of that item will be lost.
data_lostPointer to memory, where data of the replaced item will be inserted. If NULL, data of that item will be lost.

key_lost and data_lost are set only when the return value is FHT_INSERT_LOST or FHT_INSERT_STASH_LOST.

Returns
FHT_INSERT_OK if the item was successfully inserted. FHT_INSERT_LOST if the inserted item pulled out the oldest item in the row of the table and it was not inserted in stash. FHT_INSERT_STASH_OK if the inserted item pulled out the oldest item in the row of the table and it was inserted in stash. FHT_INSERT_STASH_LOST if item inserted in stash replaced an item in stash. FHT_INSERT_FAILED if there already is an item with such key in the table.

◆ fht_insert_with_stash_wr()

int fht_insert_with_stash_wr ( fht_table_t table,
const void *  key,
const void *  data 
)

Function for inserting the item into the table using stash and without replacing items in stash.

Parameters
tablePointer to the hash table structure.
keyPointer to key of the inserted item.
dataPointer to data of the inserted item.
Returns
FHT_INSERT_OK if the item was successfully inserted. FHT_INSERT_STASH_OK if the inserted item pulled out the oldest item in the row of the table and it was inserted in stash. FHT_INSERT_FAILED if there already is an item with such key in the table. FHT_INSERT_FULL if the row where the item should be placed is full.

◆ fht_insert_wr()

int fht_insert_wr ( fht_table_t table,
const void *  key,
const void *  data 
)

Function for inserting the item into the table without using stash and without replacing the oldest item when the row is full.

Parameters
tablePointer to the hash table structure.
keyPointer to key of the inserted item.
dataPointer to data of the inserted item.
Returns
FHT_INSERT_OK if the item was successfully inserted. FHT_INSERT_FAILED if there already is an item with such key in the table. FHT_INSERT_FULL if the row where the item should be placed is full.

◆ fht_reinit_iter()

void fht_reinit_iter ( fht_iter_t iter)

Function for reinitializing iterator for the table.

Parameters
iterPointer to the existing iterator.

◆ fht_remove()

int fht_remove ( fht_table_t table,
const void *  key 
)

Function for removing item from the table without looking for in stash.

Function removes item which key is equal to "key" from the table. Replacement vector and free flag are updated.

Parameters
tablePointer to the hash table structure.
keyKey of item which will be removed.
Returns
0 if item is found and removed. 1 if item is not found and not removed.

◆ fht_remove_iter()

int fht_remove_iter ( fht_iter_t iter)

Function for removing actual item from the table when using iterator.

Parameters
iterPointer to iterator structure.
Returns
0 if item is removed. 1 if item is not removed.

◆ fht_remove_locked()

int fht_remove_locked ( fht_table_t table,
const void *  key,
int8_t *  lock_ptr 
)

Function for removing item from the table without looking for in stash. Function does not locks lock, it can be used only to remove item which is locked (after use of function fht_get_data_locked or fht_get_data_with_stash_locked).

Parameters
tablePointer to the hash table structure.
keyKey of item which will be removed.
lock_ptrPointer to lock of the table row, where the item is.
Returns
0 if item is found. Item is removed and ROW IS UNLOCKED!! 1 if item is not found and not removed. ROW REMAINS LOCKED!!

◆ fht_remove_with_stash()

int fht_remove_with_stash ( fht_table_t table,
const void *  key 
)

Function for removing item from the table with looking for in stash.

Function removes item which key is equal to "key" from the table. When removing from table, replacement vector and free flag are updated. When removing from stash, free flag is updated.

Parameters
tablePointer to the hash table structure.
keyKey of item which will be removed.
Returns
0 if item is found and removed. 1 if item is not found and not removed.

◆ fht_remove_with_stash_locked()

int fht_remove_with_stash_locked ( fht_table_t table,
const void *  key,
int8_t *  lock_ptr 
)

Function for removing item from the table with looking for in stash. Function does not locks lock, it can be used only to remove item which is locked (after use of function fht_get_data_locked or fht_get_data_with_stash_locked).

Parameters
tablePointer to the hash table structure.
keyKey of item which will be removed.
lock_ptrPointer to lock of the table row or stash, where the item is.
Returns
0 if item is found. Item is removed and ROW/STASH IS UNLOCKED!! 1 if item is not found and not removed. ROW/STASH REMAINS LOCKED!!

Variable Documentation

◆ lt_free_flag

uint8_t lt_free_flag[]

Lookup tables.

◆ lt_pow_of_two

uint8_t lt_pow_of_two[]

◆ lt_replacement_index

uint8_t lt_replacement_index[]

◆ lt_replacement_vector

uint8_t lt_replacement_vector[][4]

◆ lt_replacement_vector_remove

uint8_t lt_replacement_vector_remove[][4]