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

Fast 8-way hash table with rehashing possibility. More...

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

Go to the source code of this file.

Data Structures

struct  fhf_table_struct
 
struct  fhf_iter_t
 

Macros

#define UINT64_MAX   -1ULL
 
#define FHF_TABLE_COLS   8
 
#define FHF_COL_FULL   ((uint8_t) 0xFF)
 

Typedefs

typedef struct fhf_table_struct fhf_table_t
 

Enumerations

enum  fhf_insert { FHF_INSERT_OK = 0, FHF_INSERT_FAILED = -1, FHF_INSERT_FULL = -2 }
 
enum  fhf_resize { FHF_RESIZE_OK = 0, FHF_RESIZE_FAILED_ALLOC = 1, FHF_RESIZE_FAILED_INSERT = 2 }
 
enum  fhf_found { FHF_FOUND = 0, FHF_NOT_FOUND = 1 }
 
enum  fhf_remove { FHF_REMOVED = 0, FHF_NOT_REMOVED = 1 }
 
enum  fhf_iter { FHF_ITER_RET_OK = 0, FHF_ITER_RET_END = 1, FHF_ITER_START = -1, FHF_ITER_END = -2 }
 

Functions

fhf_table_tfhf_init (uint64_t table_rows, uint32_t key_size, uint32_t data_size)
 Function for initializing table. More...
 
void fhf_clear (fhf_table_t *table)
 Function for clearing table. More...
 
void fhf_destroy (fhf_table_t *table)
 Function for destroying table and freeing memory. More...
 
fhf_iter_tfhf_init_iter (fhf_table_t *table)
 Function for initializing iterator for the table. More...
 
void fhf_reinit_iter (fhf_iter_t *iter)
 Function for reinitializing iterator for table. More...
 
void fhf_destroy_iter (fhf_iter_t *iter)
 Function for destroying iterator and freeing memory. More...
 

Variables

uint8_t fhf_lt_free_flag []
 
uint8_t fhf_lt_pow_of_two []
 

Detailed Description

Fast 8-way hash table with rehashing possibility.

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_filter.h.

Macro Definition Documentation

◆ FHF_COL_FULL

#define FHF_COL_FULL   ((uint8_t) 0xFF)

Value of free flag when column is full.

Definition at line 70 of file fast_hash_filter.h.

◆ FHF_TABLE_COLS

#define FHF_TABLE_COLS   8

Number of columns in the hash table.

Definition at line 65 of file fast_hash_filter.h.

◆ UINT64_MAX

#define UINT64_MAX   -1ULL

Needed for some C++ modules

Definition at line 59 of file fast_hash_filter.h.

Typedef Documentation

◆ fhf_table_t

typedef struct fhf_table_struct fhf_table_t

Hash table structure.

Free flag: 0 - free 1 - full

                   MSB                         LSB

Bits | X | X | X | X | X | X | X | X | Index of item in row 7 6 5 4 3 2 1 0

Definition at line 133 of file fast_hash_filter.h.

Enumeration Type Documentation

◆ fhf_found

enum fhf_found

Constants used for get and update data functions.

Enumerator
FHF_FOUND 
FHF_NOT_FOUND 

Definition at line 93 of file fast_hash_filter.h.

◆ fhf_insert

enum fhf_insert

Constants used for insert functions.

Enumerator
FHF_INSERT_OK 
FHF_INSERT_FAILED 
FHF_INSERT_FULL 

Definition at line 75 of file fast_hash_filter.h.

◆ fhf_iter

enum fhf_iter

Constants used for iterator functions.

Enumerator
FHF_ITER_RET_OK 
FHF_ITER_RET_END 
FHF_ITER_START 
FHF_ITER_END 

Definition at line 109 of file fast_hash_filter.h.

◆ fhf_remove

enum fhf_remove

Constants used for removing functions.

Enumerator
FHF_REMOVED 
FHF_NOT_REMOVED 

Definition at line 101 of file fast_hash_filter.h.

◆ fhf_resize

enum fhf_resize

Constants used for resizing function.

Enumerator
FHF_RESIZE_OK 
FHF_RESIZE_FAILED_ALLOC 
FHF_RESIZE_FAILED_INSERT 

Definition at line 84 of file fast_hash_filter.h.

Function Documentation

◆ fhf_clear()

void fhf_clear ( fhf_table_t table)

Function for clearing table.

Function sets free flags of all items in the table to zero. Items with zero free flags are considered free. Data and keys remain in table while they are replaced by new items.

Parameters
tablePointer to the table structure.

◆ fhf_destroy()

void fhf_destroy ( fhf_table_t table)

Function for destroying table and freeing memory.

Function frees memory of the whole table structure.

Parameters
tablePointer to the table structure.

◆ fhf_destroy_iter()

void fhf_destroy_iter ( fhf_iter_t iter)

Function for destroying iterator and freeing memory.

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

Parameters
iterPointer to the existing iterator.

◆ fhf_init()

fhf_table_t* fhf_init ( uint64_t  table_rows,
uint32_t  key_size,
uint32_t  data_size 
)

Function for initializing table.

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

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

◆ fhf_init_iter()

fhf_iter_t* fhf_init_iter ( fhf_table_t table)

Function for initializing iterator for the table.

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

◆ fhf_reinit_iter()

void fhf_reinit_iter ( fhf_iter_t iter)

Function for reinitializing iterator for table.

Parameters
iterPointer to the existing iterator.

Variable Documentation

◆ fhf_lt_free_flag

uint8_t fhf_lt_free_flag[]

Lookup tables.

◆ fhf_lt_pow_of_two

uint8_t fhf_lt_pow_of_two[]