diff options
Diffstat (limited to 'include/MESA/MESA_htable.h')
| -rw-r--r-- | include/MESA/MESA_htable.h | 425 |
1 files changed, 425 insertions, 0 deletions
diff --git a/include/MESA/MESA_htable.h b/include/MESA/MESA_htable.h new file mode 100644 index 0000000..26d976e --- /dev/null +++ b/include/MESA/MESA_htable.h @@ -0,0 +1,425 @@ +#ifndef __MESA_HTABLE_H_ +#define __MESA_HTABLE_H_ +#ifdef __cplusplus +extern "C" +{ +#endif + +#include <stdlib.h> +#include <errno.h> +#include <string.h> +#include <pthread.h> + +/* + * general purpose hash table implementation. + * + * xiang hong + * 2002-07-28 + *History: + * 2012-03-23 zhengchao add thread safe option and link expire feature; + * 2014-01-27 lijia add reentrant feature. + */ +#define MESA_HTABLE_VERSION_MACRO (20170104) +extern const unsigned int MESA_HTABLE_VERSION_INT; + +#define MESA_HASH_DEBUG (0) + +#define COMPLEX_KEY_SWITCH (1) + +#define ELIMINATE_TYPE_NUM (1) +#define ELIMINATE_TYPE_TIME (2) +#define ELIMINATE_TYPE_MANUAL (3) /* delete oldest item by manual */ + +typedef void * MESA_htable_handle; + + +#define HASH_MALLOC(_n_) malloc(_n_) +#define HASH_FREE(_p_) free(_p_) + + +#ifndef uchar +#define uchar unsigned char +#endif +#ifndef uint +#define uint unsigned int +#endif + +/* eliminate algorithm */ +#define HASH_ELIMINATE_ALGO_FIFO (0) /* by default */ +#define HASH_ELIMINATE_ALGO_LRU (1) + +/* + * hash key compare function prototype, see hash_key_comp(). + * return value: + * 0:key1 and key2 are equal; + * other:key1 and key2 not equal. + */ +typedef int key_comp_fun_t(const uchar * key1, uint size1, const uchar * key2, uint size2); + +/* + * hash key->index computing function prototype, see hash_key2index(). + */ +typedef uint key2index_fun_t(const MESA_htable_handle table, const uchar * key, uint size); + +/* common HASH algorithm, MESA_htable use BKDR_hash_algo as default, user can choose any one */ +extern uint BKDR_hash_algo(MESA_htable_handle api_table, const uchar *str, uint size); +extern uint APHash_algo(MESA_htable_handle api_table, const uchar *str, uint size); +extern uint murmur3_32_algo(MESA_htable_handle api_table, const uchar* str, uint size) ; + +typedef void MESA_htable_data_free_cbfun_t(void *data); + +typedef int MESA_htable_expire_notify_cbfun_t(void *data, int eliminate_type); + +typedef uchar* MESA_htable_complex_key_dup_cbfun_t(const uchar *key, uint key_size); + +typedef void MESA_htable_complex_key_free_cbfun_t(uchar *key, uint key_size); + +typedef long hash_cb_fun_t(void *data, const uchar *key, uint size, void *user_arg); + +/* + * thread_safe: 0:create hash table without thread safe features; + * positive:the bigger number has more performance, less collide, but less timeout accuracy. + * max number is 1024. + * recursive: 0:can't recursive call MESA_htable_xxx series function + * 1:can recursive call MESA_htable_xxx series function. + * hash_slot_size: how big do you want the table to be, must be 2^N; + * max_elem_num: the maximum elements of the HASH-table,0 means infinite; + * key_comp: hash key compare function, use default function if NULL; + * suggest implement by yourself. + * key2index: hash key->index computing function, use default function if NULL; + * suggest use MESA_htable built-in function. + * data_free: release resources function; + * data_expire_with_condition: + * if expire_time > 0 and data_expire_with_condition != NULL, + * then call this function when an element expired, and give the reason by the 'type' + * if expire_time > 0 and data_expire_with_condition is NULL, + * eliminate the item immediately; + * args: + * data: pointer to attached data; + * type: item eliminate reason, ELIMINATE_TYPE_NUM or ELIMINATE_TYPE_TIME; + * return value of 'data_expire_with_condition': + * 1: the item can be eliminated; + * 0: the item can't be eliminated, renew the item. + * eliminate_type: the algorithm of elimanate a expired element, 0:FIFO; 1:LRU. + * expire_time: the element expire time in second, 0 means infinite. + */ +typedef struct{ + unsigned int thread_safe; + int recursive; + unsigned int hash_slot_size; + unsigned int max_elem_num; + int eliminate_type; + int expire_time; + key_comp_fun_t * key_comp; + key2index_fun_t * key2index; + void (* data_free)(void *data); + int (*data_expire_with_condition)(void *data, int eliminate_type); +#if COMPLEX_KEY_SWITCH + uchar* (*complex_key_dup)(const uchar *key, uint key_size); + void (* complex_key_free)(uchar *key, uint key_size); +#endif +}MESA_htable_create_args_t; + + +/* All of the following functions return value */ +typedef enum{ + MESA_HTABLE_RET_OK = 0, /* success */ + MESA_HTABLE_RET_COMMON_ERR = -1, /* general��undefined errors */ + MESA_HTABLE_RET_ARG_ERR = -2, /* invalid args */ + MESA_HTABLE_RET_NUM_FULL = -3, /* htable number full */ + MESA_HTABLE_RET_QEMPTY = -4, /* htable empty */ + MESA_HTABLE_RET_DUP_ITEM = -5, /* duplicate item */ + MESA_HTABLE_RET_NOT_FOUND = -6, /* not found item */ + MESA_HTABLE_RET_LEN_ERR = -7, /* length error */ + MESA_HTABLE_RET_CANT_GET_LOCK = -8, /* can't get lock in non-block mode */ + MESA_HTABLE_RET_GET_LOCK_TMOUT = -9, /* get lock timeout */ +}MESA_htable_errno_t; + +/* + * You should never use this API to create a hash table, use MESA_htable_born() instead. + * name: MESA_htable_create + * functionality: allocats memory for hash slots, and initialize hash structure; + * param: + * args: argments set; + * args_len: length of argment set; + * returns: + * NULL : error; + * Non-NULL : success; + */ +MESA_htable_handle MESA_htable_create(const MESA_htable_create_args_t *args, int args_struct_len); + +/* + * get total number of HASH element. +*/ +unsigned int MESA_htable_get_elem_num(const MESA_htable_handle table); + +/* + * name: MESA_htable_destroy + * functionality: cleans up hash structure, frees memory occupied; + * param: + * table: who is the victim; + * func: callback function to clean up data attached to hash items, has higher priority level than MESA_htable_data_free_cbfun_t in initialization. + + * returns: + * always returns 0; + */ +int MESA_htable_destroy(MESA_htable_handle table, void (* func)(void *)); + +/* + * name: MESA_htable_add + * functionality: adds item to table, call hash_expire() if elem_count gets + * bigger than threshold_hi, and adjust threshold; + * param: + * table: to which table do you want to add; + * key: what is the label; + * size: how long is the label; + * data: what data do you want to attach; + * returns: + * >0: success,return hash elems' linklist size; + * 0: success. + * <0: error, refer to MESA_htable_errno_t. + */ +int MESA_htable_add(MESA_htable_handle table, const uchar * key, uint size, const void *data); + +/* + TODO, + sturct hash_status{ + uint hlist_max; + uint hlist_max_slot_index; + uint cur_index_hlist_num; + uint hash_value; + }; + + ����MESA_htable_add_feedback(MESA_htable_handle table, const uchar * key, uint size, const void *data, sturct hash_status *hstat); + ���ڷ���HASH����һЩ�ؼ���Ϣ, + +*/ + +#if 0 +/* + * name: hash_add_with_expire + * functionality: adds item to table, than call hash_expire() on its list + * param: + * table: to which table do you want to add; + * key: what is the label; + * size: how long is the label; + * data: what data do you want to attach; + * returns: + * >0 success,return hash elems' linklist size + * -1, duplicates found and can't add this one; + * -2, memory failure; + */ +int MESA_hash_add_with_expire_v3(MESA_htable_inner_t * table, uchar * key, uint size, void * data); + +#endif + + +/* + * name: MESA_htable_del + * functionality: deletes item from table. + * param: + * table: from which table do you want to delete; + * key : what is the label; + * size : how long is the label; + * func : callback function to clean up data attached to hash items, + if this pointer is NULL will call "data_free" in MESA_hash_create(), + * returns: + * 0 : success; + * <0: error, refer to MESA_htable_errno_t. + */ +int MESA_htable_del(MESA_htable_handle table, const uchar * key, uint size, + void (* func)(void *)); +/* + TODO: + ����MESA_htable_del_with_hash(MESA_htable_handle table, const uchar * key, uint size, uint hash_value, + void (* func)(void *)); + ɾ��ʱ����֮ǰ��hash_value, ����һ��hash���㿪��, +*/ + + +/* + * name: MESA_htable_del_oldest_manual + * functionality: deletes oldest item from table. + * param: + * table: from which table do you want to delete; + * func : callback function to clean up data attached to hash items, + if this pointer is NULL will call "data_free" in MESA_hash_create(), + * batch_num: delete oldest items. + * returns: + * 0, do nothing ; + * >0, delete items; + */ +int MESA_htable_del_oldest_manual(MESA_htable_handle table, void (* func)(void *), int batch_num); + +/* + * name: MESA_htable_search + * functionality: selects item from table; + * param: + * table: from which table do you want to select; + * key : what is the label; + * size : how long is the label; + * + * return: + * not NULL :pointer to attached data; + * NULL :not found(thus be careful if you are attaching NULL data on purpose). + */ +void *MESA_htable_search(const MESA_htable_handle table, const uchar * key, uint size); + +/* + * name: MESA_htable_search_cb + * functionality: selects item from table, and then call 'cb', reentrant; + * in param: + * table: from which table do you want to select; + * key : what is the label; + * size : how long is the label; + * cb : call this function when found the attached data; + * arg : the argument of "cb" function. + * out param: + * cb_ret: the return value of the function "cb". + * return: + * not NULL :pointer to attached data; + * NULL :not found(thus be careful if you are attaching NULL data on purpose). + */ +void *MESA_htable_search_cb(const MESA_htable_handle table, const uchar * key, uint size, + hash_cb_fun_t *cb, void *arg, long *cb_ret); + +/* + * name: MESA_htable_iterate + * functionality: iterates each hash item; + * params: + * table: what table is to be iterated; + * func: what do you want to do to each attached data item; + * returns: + * 0: iterates all items; + * -1: error; + */ +int MESA_htable_iterate(MESA_htable_handle table, + void (* func)(const uchar * key, uint size, void * data, void *user), void * user); + + +/* + * name: MESA_htable_iterate_bytime + * functionality: iterates each hash item by your demand; + * note: + * if 'thread_safe' more than one, this function is not correct. + * params: + * table: what table is to be iterated; + * iterate_type: 1: newest item first; 2: oldest item first; + * iterate_cb: what do you want to do to each attached data item; + * return value of iterate_cb: + * refer to ITERATE_CB_RET_xxx; + * returns: + * 0: iterates all items; + * -1: uncomplete break. + * -2: error; + */ +#define ITERATE_CB_RET_CONTINUE_FLAG (0) /* default, like MESA_htable_iterate() */ +#define ITERATE_CB_RET_BREAK_FLAG (1<<1) /* break iterate, return from MESA_htable_iterate_bytime() immediately */ +#define ITERATE_CB_RET_DEL_FLAG (1<<2) /* del this item, like but faster than call MESA_htable_del() */ +#define ITERATE_CB_RET_REVERSE_FLAG (1<<3) /* if the item is newest item, it will become the oldest item, and vice versa */ +#define ITERATE_CB_RET_REMOVE_BUT_NOT_FREE (1<<4) /* only remove the item from Hash table, but don't free the attached data, be careful */ + +#define ITERATE_TYPE_NEWEST_FIRST (1) +#define ITERATE_TYPE_OLDEST_FIRST (2) +int MESA_htable_iterate_bytime(MESA_htable_handle table, int iterate_type, + int (*iterate_cb)(const uchar * key, uint size, void * data, void *user), void * user); + +/* + args: + print_switch: + 0: disable print message; + 1: enable print message; +*/ +void MESA_htable_print_crtl(MESA_htable_handle table, int print_switch); + + +/* + Create a htable handle and Alloc memory, and set default option, + but can't running before call MESA_htable_mature(). + + return value: + not NULL: success. + NULL : error. +*/ +MESA_htable_handle MESA_htable_born(void); + +/* + MESA_htable option definition. +*/ +enum MESA_htable_opt{ + MHO_THREAD_SAFE = 0, /* must be int, 1:create hash table with thread safe features, default is 0 */ + MHO_MUTEX_NUM, /* must be int, valid only if MHO_THREAD_SAFE is not zero, max value is 1024, defalut is 1. the bigger number has more performance and less mutex collide, but less timeout accuracy */ + MHO_HASH_SLOT_SIZE, /* must be unsigned int, default is 1048576. */ + MHO_HASH_MAX_ELEMENT_NUM, /* must be unsigned int, defalut is 0, means infinite */ + MHO_EXPIRE_TIME, /* must be int, defalut is 0, means infinite */ + MHO_ELIMIMINATE_TYPE, /* must be int, valid only if MHO_EXPIRE_TIME is not zero. HASH_ELIMINATE_ALGO_FIFO or HASH_ELIMINATE_ALGO_LRU, defalut HASH_ELIMINATE_ALGO_FIFO */ + MHO_CBFUN_KEY_COMPARE, /* must be key_comp_fun_t, hash key compare function, use default function if NULL */ + MHO_CBFUN_KEY_TO_INDEX, /* must be key2index_fun_t, hash key->index computing function, use default function if NULL */ + MHO_CBFUN_DATA_FREE, /* must be MESA_htable_data_free_cbfun_t, release resources function */ + /* data_expire_notify, must be MESA_htable_expire_notify_cbfun_t, + * if expire_time > 0 and data_expire_notify != NULL, + * then call this function when an element expired, and give the reason by the 'type' + * if expire_time > 0 and data_expire_notify is NULL, + * eliminate the item immediately; + * args: + * data: pointer to attached data; + * type: item eliminate reason, ELIMINATE_TYPE_NUM or ELIMINATE_TYPE_TIME; + * return value of 'data_expire_with_condition': + * 1: the item can be eliminated; + * 0: the item can't be eliminated, renew the item. + */ + MHO_CBFUN_DATA_EXPIRE_NOTIFY, + MHO_CBFUN_COMPLEX_KEY_DUP, /* must be MESA_htable_complex_key_dup_cbfun_t, if key store in a complex struct, caller must be implement this duplicate function. */ + MHO_CBFUN_COMPLEX_KEY_FREE, /* must be MESA_htable_complex_key_free_cbfun_t, if key store in a complex struct, caller must be implement this duplicate function. */ + MHO_AUTO_UPDATE_TIME, /* must be int, create a background thread used to update current_time instead of time(NULL). 1:enable; 0:disable; default value is 0; */ + MHO_SCREEN_PRINT_CTRL, /* must be int, 1:enable screen print; 0:disable screen print; default is 1. */ + MHO_HASH_LIST_COLLIDE_THRESHOLD, /* must be int, write log when hash collide number more than this, default is 100, 0 means infinite. */ + MHO_HASH_LOG_FILE, /* must be char * with EOF, default is "./log/htable_runtime_%p_%t.log", opt_len is strlen(optval) */ + MHO_HASH_SEARCH_MAX_TIMES, /* must be int, max compare items in once MESA_htable_search() */ + MHO_HASH_SEARCH_AVG_TIMES, /* must be double, average compare items in all previous MESA_htable_search() */ + MHO_AUTO_EXPAND_MULTIPLE, /* must be int, used for save memory, default is 0, if this option value bigger than zero, user should set small SLOT_SIZE in initialization, htable will auto expand SLOT_SIZE if many colliding happen. */ + __MHO_MAX_VAL, /* caller can't use this definition, it's value maybe changed in next version!! */ +}; + + +/* + to set features of specified MESA_htable handle. + opt_type: option type, refer to enum MESA_htable_opt; + opt_val : option value, depend on opt type; + opt_len : opt_val size, depend on opt type; + + return value: + 0 :success; + <0:error; +*/ +int MESA_htable_set_opt(MESA_htable_handle table, enum MESA_htable_opt opt_type, void *opt_val, int opt_len); + +/* + to get features of specified MESA_htable handle. + opt_type: option type, refer to enum MESA_htable_opt; + opt_val : option value, depend on opt type; + opt_len : value-result argument, opt_val size, depend on opt type; + + return value: + 0 :success; + <0:error; +*/ +int MESA_htable_get_opt(MESA_htable_handle api_table, enum MESA_htable_opt opt_type, void *opt_val, int *opt_len); + +/* + Construct htable and ready to running. + + return value: + 0 : success; + <0: error. +*/ +int MESA_htable_mature(MESA_htable_handle table); + + +#ifdef __cplusplus +} +#endif + +#endif /* _LIB_HASH_H_INCLUDED_ */ + + |