diff options
| author | Qiuwen Lu <[email protected]> | 2017-05-16 15:15:23 +0800 |
|---|---|---|
| committer | Qiuwen Lu <[email protected]> | 2017-05-16 15:15:23 +0800 |
| commit | 5e48736a6f57c842e723bddd457b412de0b21ee0 (patch) | |
| tree | 1b0dc521ca704b372e168c23f9ff779a3b2ea431 /support | |
| parent | 6e98e285b642a255d68f2de39793582d9511e02e (diff) | |
| parent | 503cac1d141ae15f2ab6c7a889a5361dd85842aa (diff) | |
Add 'support/MESA_htable/' from commit '503cac1d141ae15f2ab6c7a889a5361dd85842aa'
git-subtree-dir: support/MESA_htable
git-subtree-mainline: 6e98e285b642a255d68f2de39793582d9511e02e
git-subtree-split: 503cac1d141ae15f2ab6c7a889a5361dd85842aa
Diffstat (limited to 'support')
41 files changed, 8836 insertions, 0 deletions
diff --git a/support/MESA_htable/.gitignore b/support/MESA_htable/.gitignore new file mode 100644 index 0000000..b9e4d17 --- /dev/null +++ b/support/MESA_htable/.gitignore @@ -0,0 +1,4 @@ +__view +*.o +*.so +*.a diff --git a/support/MESA_htable/Makefile b/support/MESA_htable/Makefile new file mode 100644 index 0000000..ebe3bb7 --- /dev/null +++ b/support/MESA_htable/Makefile @@ -0,0 +1,8 @@ +all: + cd src; $(MAKE); + cd example; $(MAKE); + +clean: + cd src; $(MAKE) clean; + cd example; $(MAKE) clean; + rm -f lib/*; diff --git a/support/MESA_htable/doc/MESA_htable_介绍.pptx b/support/MESA_htable/doc/MESA_htable_介绍.pptx Binary files differnew file mode 100644 index 0000000..837cb70 --- /dev/null +++ b/support/MESA_htable/doc/MESA_htable_介绍.pptx diff --git a/support/MESA_htable/example/Makefile b/support/MESA_htable/example/Makefile new file mode 100644 index 0000000..2c9f5fd --- /dev/null +++ b/support/MESA_htable/example/Makefile @@ -0,0 +1,59 @@ +CC=gcc -g +LIB_PATH=../lib +INC=-I../include +LIB=../lib/libMESA_htable.so -lpthread +#LIB=-lMESA_htable -lpthread + +TARGET=test_htable_op test_htable_expire test_list_queue test_list test_htable_perf test_htable_del_old test_iterate_demand test_htable_create_destroy test_ring_queue lqueue_vs_rqueue_pointer lqueue_vs_rqueue_value +TARGET += test_htable_recursive +TARGET += test_htable_new_api_full +TARGET += test_htable_simulate +all:$(TARGET) + +test_list_queue:test_list_queue.c + $(CC) -o $@ $(INC) $^ -L$(LIB_PATH) $(LIB) + +test_ring_queue:test_ring_queue.c + $(CC) -o $@ $(INC) $^ -L$(LIB_PATH) $(LIB) + +lqueue_vs_rqueue_pointer:lqueue_vs_rqueue_pointer.c + $(CC) -o $@ $(INC) $^ -L$(LIB_PATH) $(LIB) + +lqueue_vs_rqueue_value:lqueue_vs_rqueue_value.c + $(CC) -o $@ $(INC) $^ -L$(LIB_PATH) $(LIB) + +test_htable_op:test_htable_op.c + $(CC) -o $@ $(INC) $^ -L$(LIB_PATH) $(LIB) + +test_htable_expire:test_htable_expire.c + $(CC) -o $@ $(INC) $^ -L$(LIB_PATH) $(LIB) + +test_htable_perf:test_htable_perf.c + $(CC) -o $@ $(INC) $^ -L$(LIB_PATH) $(LIB) + +test_list:test_mesa_list.c + $(CC) -o $@ $(INC) $^ -L$(LIB_PATH) $(LIB) + +test_htable_del_old:test_htable_del_old.c + $(CC) -o $@ $(INC) $^ -L$(LIB_PATH) $(LIB) + +test_iterate_demand:test_iterate_demand.c + $(CC) -o $@ $(INC) $^ -L$(LIB_PATH) $(LIB) + +test_htable_create_destroy:test_htable_create_destroy.c + $(CC) -o $@ $(INC) $^ -L$(LIB_PATH) $(LIB) + +test_htable_recursive:test_htable_recursive.c + $(CC) -o $@ $(INC) $^ -L$(LIB_PATH) $(LIB) + +lqueue_vs_rqueue:lqueue_vs_rqueue.c + $(CC) -o $@ $(INC) $^ -L$(LIB_PATH) $(LIB) + +test_htable_new_api_full:test_htable_new_api_full.c + $(CC) -o $@ $(INC) $^ -L$(LIB_PATH) $(LIB) + +test_htable_simulate:test_htable_simulate.c + $(CC) -o $@ $(INC) $^ -L$(LIB_PATH) $(LIB) + +clean: + rm -f $(TARGET) diff --git a/support/MESA_htable/example/lqueue_vs_rqueue_pointer.c b/support/MESA_htable/example/lqueue_vs_rqueue_pointer.c new file mode 100644 index 0000000..4450217 --- /dev/null +++ b/support/MESA_htable/example/lqueue_vs_rqueue_pointer.c @@ -0,0 +1,132 @@ +#include "MESA_ring_queue.h" +#include "MESA_list_queue.h" +#include <stdio.h> +#include <string.h> +#include <stdlib.h> +#include <time.h> +#include <unistd.h> +#include <pthread.h> +#include <assert.h> +#include <linux/limits.h> +#include <sys/types.h> +#include <sys/stat.h> +#include <unistd.h> +#include <sys/time.h> + + +#ifdef __cplusplus +extern "C" +{ +#endif + +#define USE_LQUEUE (1) +#define ITEM_LEN (1500) +#define ITEM_NUM (10000000) + +#if USE_LQUEUE +static MESA_lqueue_head VSQUEUE; +#else +static MESA_ring_queue_head VSQUEUE; +#endif + + +static struct timeval start_time, end_time; + +void *queue_producter(void *arg) +{ + int i; + char *data; + char __no_use[ITEM_LEN]; + + //while(1) + { + for(i = 0; i <= ITEM_NUM; i++){ + data = malloc(ITEM_LEN); + memcpy(data, __no_use, ITEM_LEN); +#if USE_LQUEUE + MESA_lqueue_join_tail(VSQUEUE, &data, sizeof(void *)); +#else + MESA_ring_queue_join(VSQUEUE, &data, sizeof(void *)); +#endif + } + } + + while(1){ + pause(); + } + + return NULL; +} + +void *queue_customer(void *arg) +{ + int ret, item_num = 0; + +#if USE_LQUEUE + long data_len; +#else + int data_len; +#endif + char *data; + + while(1){ + data_len = sizeof(void *); +#if USE_LQUEUE + ret = MESA_lqueue_get_head(VSQUEUE, &data, &data_len); +#else + ret = MESA_ring_queue_get(VSQUEUE, &data, &data_len); +#endif + if(ret == 0){ + item_num++; + //printf("data:%p, num:%d\n", data, item_num); + if(item_num >= ITEM_NUM){ + gettimeofday(&end_time, NULL); + printf("time:%ld ms\n", + (end_time.tv_sec * 1000 + end_time.tv_usec/1000) - + (start_time.tv_sec * 1000 + start_time.tv_usec/1000)); + exit(0); + } + free(data); + } + } + + return NULL; + +} + + +int main(void) +{ + pthread_t pid; + +#if USE_LQUEUE + VSQUEUE = MESA_lqueue_create(1, ITEM_NUM+2); +#else + VSQUEUE = MESA_ring_queue_born(); + + int opt = 1024; + MESA_ring_queue_set_opt(VSQUEUE, RQO_PRE_ALLOC_BUF_LEN, &opt, sizeof(int)); + + opt = 100000; + MESA_ring_queue_set_opt(VSQUEUE, RQO_RING_ELEMENT_NUM, &opt, sizeof(int)); + + MESA_ring_queue_mature(VSQUEUE); +#endif + + gettimeofday(&start_time, NULL); + + pthread_create(&pid, NULL, queue_producter, NULL); + pthread_create(&pid, NULL, queue_customer, NULL); + + while(1){ + pause(); + } + + return 0; +} + +#ifdef __cplusplus +} +#endif + + diff --git a/support/MESA_htable/example/lqueue_vs_rqueue_value.c b/support/MESA_htable/example/lqueue_vs_rqueue_value.c new file mode 100644 index 0000000..131f0e9 --- /dev/null +++ b/support/MESA_htable/example/lqueue_vs_rqueue_value.c @@ -0,0 +1,128 @@ +#include "MESA_ring_queue.h" +#include "MESA_list_queue.h" +#include <stdio.h> +#include <string.h> +#include <stdlib.h> +#include <time.h> +#include <unistd.h> +#include <pthread.h> +#include <assert.h> +#include <linux/limits.h> +#include <sys/types.h> +#include <sys/stat.h> +#include <unistd.h> +#include <sys/time.h> + + +#ifdef __cplusplus +extern "C" +{ +#endif + +#define USE_LQUEUE (0) +#define ITEM_LEN (1024) +#define ITEM_NUM (10000000) + +#if USE_LQUEUE +static MESA_lqueue_head VSQUEUE; +#else +static MESA_ring_queue_head VSQUEUE; +#endif + + +static struct timeval start_time, end_time; + +void *queue_producter(void *arg) +{ + int i; + char data[ITEM_LEN]; + + //while(1) + { + for(i = 0; i <= ITEM_NUM; i++){ +#if USE_LQUEUE + MESA_lqueue_join_tail(VSQUEUE, data, ITEM_LEN); +#else + MESA_ring_queue_join(VSQUEUE, data, ITEM_LEN); +#endif + } + } + + while(1){ + pause(); + } + + return NULL; +} + +void *queue_customer(void *arg) +{ + int ret, item_num = 0; + +#if USE_LQUEUE + long data_len; +#else + int data_len; +#endif + char data[ITEM_LEN]; + + while(1){ + data_len = ITEM_LEN; +#if USE_LQUEUE + ret = MESA_lqueue_get_head(VSQUEUE, data, &data_len); +#else + ret = MESA_ring_queue_get(VSQUEUE, data, &data_len); +#endif + if(ret == 0){ + item_num++; + //printf("data:%p, num:%d\n", data, item_num); + if(item_num >= ITEM_NUM){ + gettimeofday(&end_time, NULL); + printf("time:%ld ms\n", + (end_time.tv_sec * 1000 + end_time.tv_usec/1000) - + (start_time.tv_sec * 1000 + start_time.tv_usec/1000)); + exit(0); + } + } + } + + return NULL; + +} + + +int main(void) +{ + pthread_t pid; + +#if USE_LQUEUE + VSQUEUE = MESA_lqueue_create(1, ITEM_NUM+2); +#else + VSQUEUE = MESA_ring_queue_born(); + + int opt = ITEM_LEN; + MESA_ring_queue_set_opt(VSQUEUE, RQO_PRE_ALLOC_BUF_LEN, &opt, sizeof(int)); + + opt = 100000; + MESA_ring_queue_set_opt(VSQUEUE, RQO_RING_ELEMENT_NUM, &opt, sizeof(int)); + + MESA_ring_queue_mature(VSQUEUE); +#endif + + gettimeofday(&start_time, NULL); + + pthread_create(&pid, NULL, queue_producter, NULL); + pthread_create(&pid, NULL, queue_customer, NULL); + + while(1){ + pause(); + } + + return 0; +} + +#ifdef __cplusplus +} +#endif + + diff --git a/support/MESA_htable/example/memchk.sh b/support/MESA_htable/example/memchk.sh new file mode 100644 index 0000000..bbf7aea --- /dev/null +++ b/support/MESA_htable/example/memchk.sh @@ -0,0 +1 @@ +valgrind --tool=memcheck --leak-check=yes --leak-resolution=high --log-file=valgrind.log $1 diff --git a/support/MESA_htable/example/test_htable_create_destroy.c b/support/MESA_htable/example/test_htable_create_destroy.c new file mode 100644 index 0000000..a9ad8c1 --- /dev/null +++ b/support/MESA_htable/example/test_htable_create_destroy.c @@ -0,0 +1,117 @@ +#include <stdio.h> +#include <stdlib.h> +#include <unistd.h> +#include <time.h> +#include "MESA_htable.h" +#ifdef __cplusplus +extern "C" +{ +#endif + +#ifndef MALLOC_CHECK_ +#define MALLOC_CHECK_ (1) +#endif + +MESA_htable_handle htable; + +#define MULTI_THREAD (1) +#define HTABLE_SIZE (1024 * 1024) + +#define RAND_NUM_RANGE (0xfffff) + +struct test_complex_key{ + char *s1; + char *s2; +}; + +void my_free(void *data) +{ + free(data); +} + +uchar* test_key_dup(const uchar *key, uint key_size) +{ + struct test_complex_key *complex_key = (struct test_complex_key *)malloc(sizeof(struct test_complex_key)); + + complex_key->s1 = (char *)malloc(100); + complex_key->s2 = (char *)malloc(100); + + return (uchar *)complex_key; +} + +void test_key_free(uchar *key, uint key_size) +{ + struct test_complex_key *complex_key = (struct test_complex_key *)key; + + free(complex_key->s1); + free(complex_key->s2); + free(complex_key); + + return ; +} +/* �����ڲ��Դ���������, �˴����ж������ */ + int test_key_comp(const uchar * key1, uint size1, const uchar * key2, uint size2) + { + return -1; + } + + static void test_htable_add(MESA_htable_handle ttable) + { + unsigned char key[128]; + char *data = malloc(100); + + snprintf(key, 128, "%d", rand()); + + MESA_htable_add(ttable, key, strlen(key), data); + } + +static MESA_htable_handle test_htable_create(void) +{ + MESA_htable_handle ttable; + MESA_htable_create_args_t hargs; + + memset(&hargs, 0, sizeof(MESA_htable_create_args_t)); + hargs.thread_safe = 1; + hargs.recursive = 1; + hargs.hash_slot_size = HTABLE_SIZE; + hargs.max_elem_num = 100000; + hargs.eliminate_type = HASH_ELIMINATE_ALGO_LRU; + hargs.expire_time = 0; + hargs.key_comp = test_key_comp; + hargs.key2index = NULL; + hargs.data_free = my_free; + hargs.data_expire_with_condition = NULL; + hargs.complex_key_dup = test_key_dup; + hargs.complex_key_free = test_key_free; + ttable = MESA_htable_create(&hargs, sizeof(MESA_htable_create_args_t)); + + return ttable; +} + + +int main(void) +{ + MESA_htable_handle ttable; + int i, j; + + srand(time(NULL)); + + for(i = 0; i < 1000; i++){ + ttable = test_htable_create(); + MESA_htable_print_crtl(ttable, 1); + for(j = 0; j < 100; j++){ + test_htable_add(ttable); + } + MESA_htable_destroy(ttable, NULL); + } + + return 0; +} + +#ifdef __cplusplus +} +#endif + + + + diff --git a/support/MESA_htable/example/test_htable_del_old.c b/support/MESA_htable/example/test_htable_del_old.c new file mode 100644 index 0000000..fe98b25 --- /dev/null +++ b/support/MESA_htable/example/test_htable_del_old.c @@ -0,0 +1,164 @@ +#include <stdio.h> +#include <stdlib.h> +#include <unistd.h> +#include <time.h> +#include "MESA_htable.h" +#ifdef __cplusplus +extern "C" +{ +#endif + +#ifndef MALLOC_CHECK_ +#define MALLOC_CHECK_ (1) +#endif + +MESA_htable_handle htable; + +#define MULTI_THREAD (1) +#define HTABLE_SIZE (1024 * 1024) + +#define RAND_NUM_RANGE (0xfffff) + +static volatile int insert_ok = 0, insert_err = 0; +static volatile int select_hit = 0, select_not_hit = 0; +static volatile int delete_hit = 0, delete_not_hit = 0; +static volatile int rdelete_hit = 0, rdelete_not_hit = 0; /* �ݹ�ɾ�� */ +static volatile int tot_op_times = 0; + +static int ins_n; +static int sel_n; +static int del_n; + +void my_free(void *data) +{ + free(data); +} + +int my_expire(void *arg, int type) +{ + int ret; + int *data = (int *)arg; +// if((*data %2) == 0) + { + //printf("\t\t\titem %d expired, del it!\n", *data); + //return 1; + } + + if(ELIMINATE_TYPE_NUM == type){ + printf("\t\t\t ##### item %d exceed threshold, force del it!\n", *data); + ret = 1; + }else if(ELIMINATE_TYPE_MANUAL== type){ + printf("\t\t\titem %d del by manual!\n", *data); + ret = 0; + }else{ + printf("\t\t\titem %d still in use can't del it!\n", *data); + ret = 0; + } + + return ret; +} + + + +void *sel_thread(void *arg) +{ + int key = 50; + sleep(2); + + while(1) + { + MESA_htable_search(htable, (uchar *)&key, sizeof(int)); + usleep(1000 * 5); + key++; + if(key > 70){ + key = 50; + } + } + + return NULL; +} + + + +void *thread_print(void *arg) +{ + int n; + + while(1) + { + //printf("\ntotal element=%u\n", MESA_htable_get_elem_num(htable)); + + tot_op_times = 0; + //printf("\tOK : ins=%d, sel=%d, del=%d, rdel=%d\n", insert_ok, select_hit, delete_hit, rdelete_hit); + //printf("\tERR: ins=%d, sel=%d, del=%d, rdel=%d\n", insert_err, select_not_hit, delete_not_hit, rdelete_not_hit); + usleep(1000 * 995); + } + + return NULL; +} + +void *del_thread(void *arg) +{ + int n; + sleep(10); + + while(1) + { + MESA_htable_del_oldest_manual(htable, my_free, 10); + //printf("\ntotal element=%u\n", MESA_htable_get_elem_num(htable)); + //printf("\tOK : ins=%d, sel=%d, del=%d, rdel=%d\n", insert_ok, select_hit, delete_hit, rdelete_hit); + //printf("\tERR: ins=%d, sel=%d, del=%d, rdel=%d\n", insert_err, select_not_hit, delete_not_hit, rdelete_not_hit); + usleep(1000 * 95); + } + + return NULL; +} + +int main(void) +{ + pthread_t t[20]; + MESA_htable_create_args_t hargs; + int num = 0; + int *data; + + srand(time(NULL)); + memset(&hargs, 0, sizeof(MESA_htable_create_args_t)); + hargs.thread_safe = 1; + hargs.recursive = 1; + hargs.hash_slot_size = HTABLE_SIZE; + hargs.max_elem_num = 100000; + hargs.eliminate_type = HASH_ELIMINATE_ALGO_LRU; + hargs.expire_time = 0; + hargs.key_comp = NULL; + hargs.key2index = NULL; + hargs.data_free = my_free; + hargs.data_expire_with_condition = my_expire; + htable = MESA_htable_create(&hargs, sizeof(MESA_htable_create_args_t)); +MESA_htable_print_crtl(htable, 0); + + pthread_create(&t[0], NULL, sel_thread, NULL); + pthread_create(&t[1], NULL, thread_print, NULL); + pthread_create(&t[2], NULL, del_thread, NULL); + pthread_create(&t[3], NULL, del_thread, NULL); + + while(1) { + data = (int *)malloc(sizeof(int)); + *data = num; + if(MESA_htable_add(htable, (uchar *)&num, sizeof(int), data) < 0){ + printf("item %d insert error!\n", num); + }else{ + printf("item %d insert OK!\n", num); + } + usleep(1000 * 5); + num++; + } + + return 0; +} + +#ifdef __cplusplus +} +#endif + + + diff --git a/support/MESA_htable/example/test_htable_expire.c b/support/MESA_htable/example/test_htable_expire.c new file mode 100644 index 0000000..cd53310 --- /dev/null +++ b/support/MESA_htable/example/test_htable_expire.c @@ -0,0 +1,144 @@ +#include <stdio.h> +#include <stdlib.h> +#include <unistd.h> +#include <time.h> +#include "MESA_htable.h" +#ifdef __cplusplus +extern "C" +{ +#endif + +#ifndef MALLOC_CHECK_ +#define MALLOC_CHECK_ (1) +#endif + +MESA_htable_handle htable; + +#define MULTI_THREAD (1) +#define HTABLE_SIZE (1024 * 1024) + +#define RAND_NUM_RANGE (0xfffff) + +static volatile int insert_ok = 0, insert_err = 0; +static volatile int select_hit = 0, select_not_hit = 0; +static volatile int delete_hit = 0, delete_not_hit = 0; +static volatile int rdelete_hit = 0, rdelete_not_hit = 0; /* �ݹ�ɾ�� */ +static volatile int tot_op_times = 0; + +static int ins_n; +static int sel_n; +static int del_n; + +void my_free(void *data) +{ + free(data); +} + +int my_expire(void *arg, int type) +{ + int ret; + int *data = (int *)arg; + if((*data %2) == 0){ + printf("\t\t\titem %d expired, del it!\n", *data); + return 1; + } + + if(ELIMINATE_TYPE_NUM == type){ + printf("\t\t\t ##### item %d exceed threshold, force del it!\n", *data); + ret = 1; + }else if(ELIMINATE_TYPE_MANUAL== type){ + printf("\t\t\titem %d del by manual!\n", *data); + ret = 0; + }else{ + printf("\t\t\titem %d still in use can't del it!\n", *data); + ret = 0; + } + + return ret; +} + + + +void *sel_thread(void *arg) +{ + int key = 0x0fffffff; + + while(1) + { + MESA_htable_search(htable, (uchar *)&key, sizeof(int)); + usleep(1000 * 500); + } + + return NULL; +} + + + +void *thread_print(void *arg) +{ + int n; + + while(1) + { + //printf("\ntotal element=%u\n", MESA_htable_get_elem_num(htable)); + + tot_op_times = 0; + //printf("\tOK : ins=%d, sel=%d, del=%d, rdel=%d\n", insert_ok, select_hit, delete_hit, rdelete_hit); + //printf("\tERR: ins=%d, sel=%d, del=%d, rdel=%d\n", insert_err, select_not_hit, delete_not_hit, rdelete_not_hit); + usleep(1000 * 995); + } + + return NULL; +} + + + +int main(void) +{ + pthread_t t[20]; + MESA_htable_create_args_t hargs; + int num = 0; + int *data; + + srand(time(NULL)); + memset(&hargs, 0, sizeof(MESA_htable_create_args_t)); + hargs.thread_safe = 1; + hargs.recursive = 0; + hargs.hash_slot_size = HTABLE_SIZE; + hargs.max_elem_num = 100000; + hargs.eliminate_type = HASH_ELIMINATE_ALGO_LRU; + hargs.expire_time = 10; + hargs.key_comp = NULL; + hargs.key2index = NULL; + hargs.data_free = my_free; + hargs.data_expire_with_condition = my_expire; + htable = MESA_htable_create(&hargs, sizeof(MESA_htable_create_args_t)); + + //pthread_create(&t[0], NULL, sel_thread, NULL); + pthread_create(&t[1], NULL, thread_print, NULL); + + while(1) { + data = (int *)malloc(sizeof(int)); + *data = num; + if(MESA_htable_add(htable, (uchar *)&num, sizeof(int), data) < 0){ + printf("item %d insert error!\n", num); + }else{ + printf("item %d insert OK!\n", num); + } + usleep(1000 * 100); + num++; + + if(num > 100){ + //MESA_htable_del_oldest_manual(htable, my_free, 10); + } + } + + return 0; +} + +#ifdef __cplusplus +} +#endif + + + diff --git a/support/MESA_htable/example/test_htable_new_api_full.c b/support/MESA_htable/example/test_htable_new_api_full.c new file mode 100644 index 0000000..46171d7 --- /dev/null +++ b/support/MESA_htable/example/test_htable_new_api_full.c @@ -0,0 +1,179 @@ +#include <stdio.h> +#include <stdlib.h> +#include <unistd.h> +#include <time.h> +#include <assert.h> +#include "MESA_htable.h" +#ifdef __cplusplus +extern "C" +{ +#endif + +#define MIN_NUM (0) +#define MAX_NUM (0x7fffffff) + +static MESA_htable_handle htable; + +static long add_times, search_times, del_times; + +static void fstack4(MESA_htable_handle shtable, const uchar *key, uint key_len, const void *data) +{ + MESA_htable_add(shtable, key, key_len, data); +} + +static void fstack3(MESA_htable_handle shtable, const uchar *key, uint key_len, const void *data) +{ + fstack4(shtable, key, key_len, data); +} + +static void fstack2(MESA_htable_handle shtable, const uchar *key, uint key_len, const void *data) +{ + fstack3(shtable, key, key_len, data); +} + +static void fstack1(MESA_htable_handle shtable, const uchar *key, uint key_len, const void *data) +{ + fstack2(shtable, key, key_len, data); +} + + +static void *thread_insert(void *arg) +{ + int i; + + while(1){ + for(i = MIN_NUM; i <= MAX_NUM; i++){ + fstack1(htable, (const uchar *)&i, sizeof(int), NULL); + add_times++; + } + } + + return NULL; +} + +static void *thread_select(void *arg) +{ + int i; + int max_times; + double avg_times; + int len; + + while(1){ + for(i = MIN_NUM; i < MAX_NUM/2; i++){ + MESA_htable_search(htable, (const uchar *)&i, sizeof(int)); + search_times++; + } + for(i = MAX_NUM/2+1; i <= MAX_NUM; i++){ + MESA_htable_search(htable, (const uchar *)&i, sizeof(int)); + search_times++; + } + + len = sizeof(int); + MESA_htable_get_opt(htable, MHO_HASH_SEARCH_MAX_TIMES, &max_times, &len); + printf("max times:%d\n", max_times); + + len = sizeof(double); + MESA_htable_get_opt(htable, MHO_HASH_SEARCH_AVG_TIMES, &avg_times, &len); + printf("avg times:%.3f\n", avg_times); + } + + return NULL; +} + +static void *thread_delete(void *arg) +{ + int i ; + + while(1){ + for(i = MAX_NUM-1; i > MIN_NUM; i--){ + MESA_htable_del(htable, (const uchar *)&i, sizeof(int), NULL); + del_times++; + } + } + + return NULL; +} + +static void *thread_print(void *arg) +{ + int n; + long this_op_times = 0, last_op_times = 0; + + while(1) + { + this_op_times = add_times+search_times+del_times; + printf("\ntotal element=%u, total op times=%ld, op/s=%ld\n", MESA_htable_get_elem_num(htable), this_op_times, this_op_times-last_op_times); + last_op_times = this_op_times; + sleep(1); + } + + return NULL; +} +int main(void) +{ + int ret; + int opt_int; + pthread_t pid; + + htable = MESA_htable_born(); + assert(htable != NULL); + + opt_int = 1; + MESA_htable_set_opt(htable, MHO_THREAD_SAFE, &opt_int, sizeof(int)); + + opt_int = 128; + MESA_htable_set_opt(htable, MHO_MUTEX_NUM, &opt_int, sizeof(int)); + + opt_int = 1048576; + MESA_htable_set_opt(htable, MHO_HASH_SLOT_SIZE, &opt_int, sizeof(int)); + + opt_int = 99999; + MESA_htable_set_opt(htable, MHO_HASH_MAX_ELEMENT_NUM, &opt_int, sizeof(int)); + + opt_int = 10; + MESA_htable_set_opt(htable, MHO_EXPIRE_TIME, &opt_int, sizeof(int)); + + opt_int = 1; + MESA_htable_set_opt(htable, MHO_AUTO_UPDATE_TIME, &opt_int, sizeof(int)); + + opt_int = 0; + MESA_htable_set_opt(htable, MHO_SCREEN_PRINT_CTRL, &opt_int, sizeof(int)); + + opt_int = HASH_ELIMINATE_ALGO_LRU; + MESA_htable_set_opt(htable, MHO_ELIMIMINATE_TYPE, &opt_int, sizeof(int)); + + opt_int = 5; + MESA_htable_set_opt(htable, MHO_HASH_LIST_COLLIDE_THRESHOLD, &opt_int, sizeof(int)); + + char *err_log = "./test_hash_collide.log"; + MESA_htable_set_opt(htable, MHO_HASH_LOG_FILE, err_log, strlen(err_log)); + + ret = MESA_htable_mature(htable); + if(0 == ret){ + printf("MESA_htable_mature success!\n"); + }else{ + printf("MESA_htable_mature error!\n"); + return -1; + } + + pthread_create(&pid, NULL, thread_insert, NULL); + usleep(10000); + pthread_create(&pid, NULL, thread_select, NULL); + pthread_create(&pid, NULL, thread_delete, NULL); + + pthread_create(&pid, NULL, thread_print, NULL); + + while(1){ + pause(); + } + + return 0; +} + +#ifdef __cplusplus +} +#endif + + + + diff --git a/support/MESA_htable/example/test_htable_new_api_simple.c b/support/MESA_htable/example/test_htable_new_api_simple.c new file mode 100644 index 0000000..1b409fb --- /dev/null +++ b/support/MESA_htable/example/test_htable_new_api_simple.c @@ -0,0 +1,59 @@ +#include <stdio.h> +#include <stdlib.h> +#include <unistd.h> +#include <time.h> +#include <assert.h> +#include "MESA_htable.h" +#ifdef __cplusplus +extern "C" +{ +#endif + +static MESA_htable_handle htable; + + +int main(void) +{ + int ret; + + htable = MESA_htable_born(); + assert(htable != NULL); + + /* don't use MESA_htable_set_opt(), use default args. */ + + ret = MESA_htable_mature(htable); + if(0 == ret){ + printf("MESA_htable_mature success!\n"); + }else{ + printf("MESA_htable_mature error!\n"); + return -1; + } + + int key = 1234; + const char *raw_data = "I am in htable."; + + ret = MESA_htable_add(htable, (const uchar *)&key, sizeof(int), raw_data); + if(ret < 0){ + abort(); + } + const char *hdata; + hdata = (const char *)MESA_htable_search(htable, (const uchar *)&key, sizeof(int)); + if(hdata != NULL){ + printf("search ok, data=%s\n", hdata); + }else{ + printf("not found!\n"); + } + + MESA_htable_destroy(htable, NULL); + + htable = NULL; + + return 0; +} + +#ifdef __cplusplus +} +#endif + + + diff --git a/support/MESA_htable/example/test_htable_op.c b/support/MESA_htable/example/test_htable_op.c new file mode 100644 index 0000000..060400e --- /dev/null +++ b/support/MESA_htable/example/test_htable_op.c @@ -0,0 +1,476 @@ +#include <stdio.h> +#include <stdlib.h> +#include <unistd.h> +#include <time.h> +#include <assert.h> +#include "MESA_htable.h" +#ifdef __cplusplus +extern "C" +{ +#endif + +#ifndef MALLOC_CHECK_ +#define MALLOC_CHECK_ (1) +#endif + +#define TEST_COMPLEX_KEY (0) + + +#define KEY_STR_LEN (100) +typedef struct{ +#if TEST_COMPLEX_KEY + char *key1; + char *key2; +#endif + int key3; + long key4; +}complex_key_t; + + +MESA_htable_handle htable; + +#define MULTI_THREAD (8) +#define HTABLE_SIZE (1024 * 1024) + +#define RAND_NUM_RANGE (0xFFF) + +static volatile int insert_ok = 0, insert_err = 0; +static volatile int select_hit = 0, select_not_hit = 0; +static volatile int delete_hit = 0, delete_not_hit = 0; +static volatile int rdelete_hit = 0, rdelete_not_hit = 0; /* �ݹ�ɾ�� */ +static volatile int tot_op_times = 0; + +static int ins_n; +static int sel_n; +static int del_n; + +#if TEST_COMPLEX_KEY +void complex_key_free(uchar *key, uint key_size) +{ + complex_key_t *rkey = (complex_key_t *)key; + free(rkey->key1); + free(rkey->key2); + free(rkey); +} + +uchar* test_complex_key_dup(const uchar *key, uint key_size) +{ + complex_key_t *raw_key = (complex_key_t *)key; + complex_key_t *new_key = (complex_key_t *)malloc(sizeof(complex_key_t)); + + new_key->key1 = (char *)malloc(KEY_STR_LEN); + memcpy(new_key->key1, raw_key->key1,KEY_STR_LEN); + new_key->key2 = (char *)malloc(KEY_STR_LEN); + memcpy(new_key->key2, raw_key->key2,KEY_STR_LEN); + new_key->key3 = raw_key->key3; + new_key->key4 = raw_key->key4; + + return (uchar *)new_key; +} +#endif + +uint test_hash_key2index(const MESA_htable_handle table, const uchar * key, uint size) +{ + complex_key_t *raw_key = (complex_key_t *)key; + + return raw_key->key3 + raw_key->key4; +} + +int test_key_cmp(const uchar * key1, uint size1, const uchar * key2, uint size2) +{ + complex_key_t *rkey1 = (complex_key_t *)key1; + complex_key_t *rkey2 = (complex_key_t *)key2; + +#if TEST_COMPLEX_KEY + if(strncmp(rkey1->key1, rkey2->key1, KEY_STR_LEN) != 0){ + return -1; + } + + if(strncmp(rkey1->key2, rkey2->key2, KEY_STR_LEN) != 0){ + return -1; + } +#endif + + if(rkey1->key3 != rkey2->key3){ + return -1; + } + + if(rkey1->key4 != rkey2->key4){ + return -1; + } + + return 0; +} + +int test_hash_data_expire_with_condition(void *data, int eliminate_type) +{ + return 0; +} + +void my_free(void *data) +{ + free(data); +} + +int test_hash_insert(int num) +{ + int ret; + + int *data = (int *)calloc(1, sizeof(int)*(rand()%1024) + sizeof(int)); /* ÿ�����벻�����ڴ� */ + + complex_key_t ckey; +#if TEST_COMPLEX_KEY + ckey.key1 = "hello"; + ckey.key2 = "world"; +#endif + ckey.key3 = num; + ckey.key4 = num; + ret = MESA_htable_add(htable, (u_char *)&ckey, sizeof(complex_key_t), (void *)data); + if(ret < 0){ + free(data); + insert_err++; + tot_op_times++; + return -1; + } + + insert_ok++; + tot_op_times++; + return 0; +} + +static int test_hash_delete(int num) +{ + int ret; + + complex_key_t ckey; + + ckey.key3 = num; + ckey.key4 = num; + + ret = MESA_htable_del(htable, (u_char *)&ckey, sizeof(complex_key_t), NULL); + if(ret >= 0){ + delete_hit++; + tot_op_times++; + return 0; + } + + delete_not_hit++; + tot_op_times++; + return -1; +} + +static int test_hash_delete_manual(int num) +{ + int ret; + + del_n = num; + ret = MESA_htable_del_oldest_manual(htable, NULL, 10); + if(0 == ret){ + delete_hit++; + tot_op_times++; + return 0; + } + + delete_not_hit++; + tot_op_times++; + return -1; +} + +static long __sel_cb(void *data, const uchar *key, uint size, void *arg) +{ + if(0 == MESA_htable_del(arg, key, size, NULL)){ + rdelete_hit++; + }else{ + rdelete_not_hit++; + } + tot_op_times++; + + return 0; +} + +int test_hash_select(int num) +{ + void *ret; + long cb_ret; + sel_n = num; + + complex_key_t ckey; +#if TEST_COMPLEX_KEY + ckey.key1 = "hello"; + ckey.key2 = "world"; +#endif + ckey.key3 = num; + ckey.key4 = num; + ret = MESA_htable_search(htable, (u_char *)&ckey, sizeof(complex_key_t)); + + + if(ret != NULL){ + //if(MESA_htable_search_cb(htable, (u_char *)&sel_n, sizeof(int), __sel_cb, htable, &cb_ret)){ + //printf("%d is in hash-table!\n", n); + select_hit++; + tot_op_times++; + return 0; + } + + //printf("%d not in hash-table!\n", n); + select_not_hit++; + tot_op_times++; + return -1; +} + +void iterate_cb(const uchar * key, uint size, void * data, void *arg) +{ + int key2 = rand() % RAND_NUM_RANGE; + + if(0 == MESA_htable_del(htable, (uchar *)&key2, sizeof(int), NULL)){ + rdelete_hit++; + }else{ + rdelete_not_hit++; + } + tot_op_times++; + + return; +} + +int test_hash_iterate(void) +{ + MESA_htable_iterate(htable, iterate_cb, NULL); +} + +#if MULTI_THREAD + +void *thread_iterate(void *arg) +{ + while(1){ + test_hash_iterate(); + //usleep(rand() % 100); + } + + return NULL; +} + +void *thread_insert(void *arg) +{ + while(1){ + test_hash_insert(rand() % RAND_NUM_RANGE); + //usleep(rand() % 100); + } + + return NULL; +} + +void *thread_delete(void *arg) +{ + while(1){ + test_hash_delete(random() % RAND_NUM_RANGE); + //usleep(rand() % 200 + 200); + } + + return NULL; +} + +void *thread_delete_manual(void *arg) +{ + while(1){ + test_hash_delete_manual(rand() % RAND_NUM_RANGE); + //usleep(rand() % 200 + 200); + } + + return NULL; +} + +void *thread_select(void *arg) +{ + int times = 0; + while(1){ + test_hash_select(rand() % RAND_NUM_RANGE); + } + + return NULL; +} +#else +void *single_thread(void *arg) +{ + int n, times = 0; + while(1) + { + n = random() % 5; + switch(n) + { + case 0: + test_hash_insert(rand() % RAND_NUM_RANGE); + break; + + case 1: + case 3: + case 4: + test_hash_delete(rand() % RAND_NUM_RANGE); + break; + + case 2: + test_hash_select(rand() % RAND_NUM_RANGE); + break; + + default: + test_hash_select(rand() % RAND_NUM_RANGE); + break; + } + + //usleep(n); + //if(times++ > 999) + if(0) + { + printf("select thread exit!\n"); + pthread_exit(NULL); + } + } + + return NULL; +} + + +#endif + +void *thread_print(void *arg) +{ + int n; + + while(1) + { + printf("\ntotal element=%u, \ntotal-op-times:%u pps, \nop-detail:\n", MESA_htable_get_elem_num(htable), tot_op_times); + + tot_op_times = 0; + printf("\tOK : ins=%d, sel=%d, del=%d, rdel=%d\n", insert_ok, select_hit, delete_hit, rdelete_hit); + printf("\tERR: ins=%d, sel=%d, del=%d, rdel=%d\n", insert_err, select_not_hit, delete_not_hit, rdelete_not_hit); + + srand(time(NULL)); + + usleep(1000 * 990); + } + + return NULL; +} + + +static void test_hash_functionality(void) +{ + int i, ret; + void *res; + void *phony_data; + complex_key_t ckey; + + memset(&ckey, 0, sizeof(complex_key_t)); + + for(i =0 ; i < 100; i++){ + ckey.key3 = i; + ckey.key4 = i; + phony_data = malloc(1); + ret = MESA_htable_add(htable, (uchar *)&ckey, sizeof(complex_key_t), phony_data); + assert(ret >= 0); + printf("MESA_htable_add: %d, ret = %d\n", i, ret); + } + printf("after MESA_htable_add(), item is:%u\n", MESA_htable_get_elem_num(htable)); + + for(i =0 ; i < 100; i++){ + ckey.key3 = i; + ckey.key4 = i; + res = MESA_htable_search(htable, (uchar *)&ckey, sizeof(complex_key_t)); + assert(res != NULL); + printf("MESA_htable_search: %d\n", i); + } + + for(i =0 ; i < 100; i++){ + ckey.key3 = i; + ckey.key4 = i; + ret = MESA_htable_del(htable, (uchar *)&ckey, sizeof(complex_key_t), NULL); + assert(0 == ret); + printf("MESA_htable_del: %d\n", i); + } + printf("after MESA_htable_del(), item is:%u\n", MESA_htable_get_elem_num(htable)); + + sleep(3); +} + + + +int main(void) +{ + pthread_t t[20]; + MESA_htable_create_args_t hargs; + + srand(time(NULL)); + + memset(&hargs, 0, sizeof(MESA_htable_create_args_t)); + + hargs.thread_safe = 0; + hargs.hash_slot_size = HTABLE_SIZE; + hargs.max_elem_num = 10000; + hargs.eliminate_type = HASH_ELIMINATE_ALGO_LRU; + hargs.expire_time = 100; +#if TEST_COMPLEX_KEY + hargs.complex_key_dup = test_complex_key_dup; + hargs.complex_key_free = complex_key_free; +#endif + hargs.key_comp = test_key_cmp; + + hargs.key2index = test_hash_key2index; + hargs.data_free = my_free; + hargs.data_expire_with_condition = test_hash_data_expire_with_condition; + +#if MULTI_THREAD + hargs.thread_safe = 512; + hargs.recursive = 1; + htable = MESA_htable_create(&hargs, sizeof(MESA_htable_create_args_t)); + if(NULL == htable){ + return -1; + } + + MESA_htable_print_crtl(htable, 0); + + + test_hash_functionality(); + + + pthread_create(&t[0], NULL, thread_insert, NULL); + //pthread_create(&t[1], NULL, thread_insert, NULL); + pthread_create(&t[2], NULL, thread_insert, NULL); + pthread_create(&t[3], NULL, thread_insert, NULL); + //pthread_create(&t[4], NULL, thread_insert, NULL); + + //pthread_create(&t[5], NULL, thread_select, NULL); + //pthread_create(&t[6], NULL, thread_select, NULL); + //pthread_create(&t[7], NULL, thread_select, NULL); + //pthread_create(&t[8], NULL, thread_select, NULL); + //pthread_create(&t[9], NULL, thread_select, NULL); + + pthread_create(&t[10], NULL, thread_delete, NULL); + pthread_create(&t[11], NULL, thread_delete, NULL); + //pthread_create(&t[12], NULL, thread_delete_manual, NULL); + //pthread_create(&t[13], NULL, thread_iterate, NULL); + //pthread_create(&t[14], NULL, thread_iterate, NULL); +#else + hargs.thread_safe = 100; + htable = MESA_htable_create(&hargs, sizeof(MESA_htable_create_args_t)); + //MESA_hash_create(&htable, 0, HTABLE_SIZE, NULL, NULL, my_free, HASH_ELIMINATE_ALGO_FIFO, 3); + + test_hash_functionality(); + + pthread_create(&t[15], NULL, single_thread, NULL); +#endif + + pthread_create(&t[16], NULL, thread_print, NULL); + + MESA_htable_print_crtl(htable, 0); + + while(1) { + sleep(1); + } + + return 0; +} + +#ifdef __cplusplus +} +#endif + + diff --git a/support/MESA_htable/example/test_htable_perf.c b/support/MESA_htable/example/test_htable_perf.c new file mode 100644 index 0000000..c02c636 --- /dev/null +++ b/support/MESA_htable/example/test_htable_perf.c @@ -0,0 +1,146 @@ +#include <stdio.h> +#include <stdlib.h> +#include <unistd.h> +#include <time.h> +#include "MESA_htable.h" +#ifdef __cplusplus +extern "C" +{ +#endif + + +#define PERF_THREAD_NUM (8) +#define HTABLE_SIZE (1024 * 1024) +#define HASH_PERF_TEST_NUM (5000000) + +static MESA_htable_handle perf_test_htable; + + +typedef struct{ + unsigned long long hash_search_ok_num; + unsigned long long hash_search_not_found_num; + long long pad[6]; /* 64�ֽ�cache���� */ +}hash_perf_test_stat_t; + + +static hash_perf_test_stat_t HASH_PERF_TEST_STAT[PERF_THREAD_NUM]; + + + +int test_hash_insert_perf(int num) +{ + int ret; + static void *data = (void *)0x6620894; + + ret = MESA_htable_add(perf_test_htable, (u_char *)&num, sizeof(int), (void *)data); + if(ret < 0){ + return -1; + } + + return 0; +} + + + +static void *thread_select_perf(void *arg) +{ + int i, tid; + void *ret; + + tid = *((int *)arg); + while(1){ + for(i = 0; i < 0x7ffffffff; i++){ + ret = MESA_htable_search(perf_test_htable, (const uchar *)&i, sizeof(int)); + if(NULL == ret){ + HASH_PERF_TEST_STAT[tid].hash_search_not_found_num++; + }else{ + HASH_PERF_TEST_STAT[tid].hash_search_ok_num++; + } + } + } + + return NULL; +} + +static void *thread_print_for_test_perf(void *arg) +{ + int i; + time_t last_time = time(NULL); + unsigned long long new_search_time, last_search_time = 0; + + while(1) + { + if(last_time < time(NULL)){ + new_search_time = 0; + for(i = 0; i < PERF_THREAD_NUM; i++){ + new_search_time += HASH_PERF_TEST_STAT[i].hash_search_ok_num; + new_search_time += HASH_PERF_TEST_STAT[i].hash_search_not_found_num; + } + printf("\ntotal element=%u,\nhash op perf:%llu pps\n", MESA_htable_get_elem_num(perf_test_htable), new_search_time-last_search_time); + last_time = time(NULL); + last_search_time = new_search_time; + } + usleep(100); + } + + return NULL; +} + +void my_free(void *data) +{ + free(data); +} + +int main(void) +{ + pthread_t ptid[PERF_THREAD_NUM]; + int thread_seq[PERF_THREAD_NUM]; + MESA_htable_create_args_t hargs; + int i; + + srand(time(NULL)); + + memset(&hargs, 0, sizeof(MESA_htable_create_args_t)); + hargs.thread_safe = 100; + hargs.recursive = 1; + hargs.hash_slot_size = HTABLE_SIZE; + hargs.max_elem_num = 100*HTABLE_SIZE; + hargs.eliminate_type = HASH_ELIMINATE_ALGO_LRU; + hargs.expire_time = 0; + hargs.key2index = NULL; + hargs.data_free = my_free; + hargs.data_expire_with_condition = NULL; + + perf_test_htable = MESA_htable_create(&hargs, sizeof(MESA_htable_create_args_t)); + if(NULL == perf_test_htable){ + return -1; + } + + MESA_htable_print_crtl(perf_test_htable, 0); + + printf("please wait for preprocess data......\n"); + for(i = 0; i < HASH_PERF_TEST_NUM; i++){ + test_hash_insert_perf(i);/* Ԥ�Ȳ������� */ + } + printf("preprocess data success!\n\n"); + + pthread_create(&ptid[0], NULL, thread_print_for_test_perf, NULL); + + for(i = 0; i < PERF_THREAD_NUM; i++){ + thread_seq[i] = i; + pthread_create(&ptid[i], NULL, thread_select_perf, &thread_seq[i]); + } + + while(1) { + sleep(1); + } + + return 0; +} + +#ifdef __cplusplus +} +#endif + + + diff --git a/support/MESA_htable/example/test_htable_recursive.c b/support/MESA_htable/example/test_htable_recursive.c new file mode 100644 index 0000000..fa668a8 --- /dev/null +++ b/support/MESA_htable/example/test_htable_recursive.c @@ -0,0 +1,413 @@ +#include <stdio.h> +#include <stdlib.h> +#include <unistd.h> +#include <time.h> +#include "MESA_htable.h" +#ifdef __cplusplus +extern "C" +{ +#endif + +#ifndef MALLOC_CHECK_ +#define MALLOC_CHECK_ (1) +#endif + + +#define KEY_STR_LEN (100) +typedef struct{ +#if COMPLEX_KEY_SWITCH + char *key1; + char *key2; +#endif + int key3; + long key4; +}complex_key_t; + + +MESA_htable_handle htable; + +#define MULTI_THREAD (1) +#define HTABLE_SIZE (1024 * 1024) + +#define RAND_NUM_RANGE (0xFFFFF) + +static volatile int insert_ok = 0, insert_err = 0; +static volatile int select_hit = 0, select_not_hit = 0; +static volatile int delete_hit = 0, delete_not_hit = 0; +static volatile int rdelete_hit = 0, rdelete_not_hit = 0; /* �ݹ�ɾ�� */ +static volatile int tot_op_times = 0; + +static int ins_n; +static int sel_n; +static int del_n; + + +void complex_key_free(uchar *key, uint key_size) +{ + complex_key_t *rkey = (complex_key_t *)key; + free(rkey->key1); + free(rkey->key2); + free(rkey); +} + +uchar* test_complex_key_dup(const uchar *key, uint key_size) +{ + complex_key_t *raw_key = (complex_key_t *)key; + complex_key_t *new_key = (complex_key_t *)malloc(sizeof(complex_key_t)); + + new_key->key1 = (char *)malloc(KEY_STR_LEN); + memcpy(new_key->key1, raw_key->key1,KEY_STR_LEN); + new_key->key2 = (char *)malloc(KEY_STR_LEN); + memcpy(new_key->key2, raw_key->key2,KEY_STR_LEN); + new_key->key3 = raw_key->key3; + new_key->key4 = raw_key->key4; + + return (uchar *)new_key; +} + +uint test_hash_key2index(const MESA_htable_handle table, const uchar * key, uint size) +{ + complex_key_t *raw_key = (complex_key_t *)key; + + return raw_key->key3 + raw_key->key4; +} + +int test_key_cmp(const uchar * key1, uint size1, const uchar * key2, uint size2) +{ + complex_key_t *rkey1 = (complex_key_t *)key1; + complex_key_t *rkey2 = (complex_key_t *)key2; + + if(strncmp(rkey1->key1, rkey2->key1, KEY_STR_LEN) != 0){ + return -1; + } + + if(strncmp(rkey1->key2, rkey2->key2, KEY_STR_LEN) != 0){ + return -1; + } + + if(rkey1->key3 != rkey2->key3){ + return -1; + } + + if(rkey1->key4 != rkey2->key4){ + return -1; + } + + return 0; +} + + +void my_free(void *data) +{ + free(data); +} + +int test_hash_insert(int num) +{ + int ret; + + int *data = (int *)calloc(1, sizeof(int)*(rand()%1024) + sizeof(int)); /* ÿ�����벻�����ڴ� */ + + complex_key_t ckey; +#if COMPLEX_KEY_SWITCH + ckey.key1 = "hello"; + ckey.key2 = "world"; +#endif + //ckey.key3 = num; + //ckey.key4 = num; + ckey.key3 = 1; + ckey.key4 = 111; + ret = MESA_htable_add(htable, (u_char *)&ckey, sizeof(complex_key_t), (void *)data); + if(ret < 0){ + free(data); + insert_err++; + tot_op_times++; + return -1; + } + + insert_ok++; + tot_op_times++; + return 0; +} + +static int test_hash_delete(int num) +{ + int ret; + + del_n = num; + ret = MESA_htable_del(htable, (u_char *)&del_n, sizeof(int), NULL); + if(ret > 0){ + delete_hit++; + tot_op_times++; + return 0; + } + + delete_not_hit++; + tot_op_times++; + return -1; +} + +static int test_hash_delete_manual(int num) +{ + int ret; + + del_n = num; + ret = MESA_htable_del_oldest_manual(htable, NULL, 10); + if(0 == ret){ + delete_hit++; + tot_op_times++; + return 0; + } + + delete_not_hit++; + tot_op_times++; + return -1; +} + +static long __sel_cb(void *data, const uchar *key, uint size, void *arg) +{ + if(0 == MESA_htable_del(arg, key, size, NULL)){ + rdelete_hit++; + }else{ + rdelete_not_hit++; + } + tot_op_times++; + + return 0; +} + +int test_hash_select(int num) +{ + void *ret; + long cb_ret; + sel_n = num; + + complex_key_t ckey; + + ckey.key1 = "hello"; + ckey.key2 = "world"; + ckey.key3 = num; + ckey.key4 = num; + + if(MESA_htable_search_cb(htable, (u_char *)&sel_n, sizeof(int), __sel_cb, htable, &cb_ret)){ + //printf("%d is in hash-table!\n", n); + select_hit++; + tot_op_times++; + return 0; + } + + //printf("%d not in hash-table!\n", n); + select_not_hit++; + tot_op_times++; + return -1; +} + +void iterate_cb(const uchar * key, uint size, void * data, void *arg) +{ + int key2 = rand() % RAND_NUM_RANGE; + + if(0 == MESA_htable_del(htable, (uchar *)&key2, sizeof(int), NULL)){ + rdelete_hit++; + }else{ + rdelete_not_hit++; + } + tot_op_times++; + + return; +} + +int test_hash_iterate(void) +{ + MESA_htable_iterate(htable, iterate_cb, NULL); +} + +#if MULTI_THREAD + +void *thread_iterate(void *arg) +{ + while(1){ + test_hash_iterate(); + //usleep(rand() % 100); + } + + return NULL; +} + +void *thread_insert(void *arg) +{ + while(1){ + test_hash_insert(rand() % RAND_NUM_RANGE); + //usleep(rand() % 100); + } + + return NULL; +} + +void *thread_delete(void *arg) +{ + while(1){ + test_hash_delete(rand() % RAND_NUM_RANGE); + //usleep(rand() % 200 + 200); + } + + return NULL; +} + +void *thread_delete_manual(void *arg) +{ + while(1){ + test_hash_delete_manual(rand() % RAND_NUM_RANGE); + //usleep(rand() % 200 + 200); + } + + return NULL; +} + +void *thread_select(void *arg) +{ + int times = 0; + while(1){ + test_hash_select(rand() % RAND_NUM_RANGE); + } + + return NULL; +} +#else +void *single_thread(void *arg) +{ + int n, times = 0; + while(1) + { + n = rand() % 3; + switch(n) + { + case 0: + //test_hash_insert(rand() % RAND_NUM_RANGE); + break; + + case 1: + //test_hash_delete(rand() % RAND_NUM_RANGE); + break; + + case 2: + test_hash_select(rand() % RAND_NUM_RANGE); + break; + + default: + test_hash_select(rand() % RAND_NUM_RANGE); + break; + } + + //usleep(n); + //if(times++ > 999) + if(0) + { + printf("select thread exit!\n"); + pthread_exit(NULL); + } + } + + return NULL; +} + + +#endif + +void *thread_print(void *arg) +{ + int n; + + while(1) + { + printf("\ntotal element=%u, \ntotal-op-times:%u pps, \nop-detail:\n", MESA_htable_get_elem_num(htable), tot_op_times); + + tot_op_times = 0; + printf("\tOK : ins=%d, sel=%d, del=%d, rdel=%d\n", insert_ok, select_hit, delete_hit, rdelete_hit); + printf("\tERR: ins=%d, sel=%d, del=%d, rdel=%d\n", insert_err, select_not_hit, delete_not_hit, rdelete_not_hit); + + srand(time(NULL)); + + usleep(1000 * 990); + } + + return NULL; +} + + + +int main(void) +{ + pthread_t t[20]; + MESA_htable_create_args_t hargs; + + srand(time(NULL)); + + memset(&hargs, 0, sizeof(MESA_htable_create_args_t)); + + hargs.thread_safe = 100; + hargs.recursive = 1; + hargs.hash_slot_size = HTABLE_SIZE; + hargs.max_elem_num = 100*HTABLE_SIZE; + hargs.eliminate_type = HASH_ELIMINATE_ALGO_LRU; + hargs.expire_time = 10; +#if COMPLEX_KEY_SWITCH + hargs.complex_key_dup = NULL; + hargs.complex_key_free = NULL; +#endif + hargs.key_comp = NULL; + + hargs.key2index = NULL; + hargs.data_free = my_free; + hargs.data_expire_with_condition = NULL; + +#if MULTI_THREAD + hargs.thread_safe = 100; + hargs.recursive = 1; + htable = MESA_htable_create(&hargs, sizeof(MESA_htable_create_args_t)); + if(NULL == htable){ + return -1; + } + + MESA_htable_print_crtl(htable, 0); + + pthread_create(&t[0], NULL, thread_insert, NULL); + //pthread_create(&t[1], NULL, thread_insert, NULL); + //pthread_create(&t[2], NULL, thread_insert, NULL); + //pthread_create(&t[3], NULL, thread_insert, NULL); + //pthread_create(&t[4], NULL, thread_insert, NULL); + + //pthread_create(&t[5], NULL, thread_select, NULL); + //pthread_create(&t[6], NULL, thread_select, NULL); + pthread_create(&t[7], NULL, thread_select, NULL); + //pthread_create(&t[8], NULL, thread_select, NULL); + //pthread_create(&t[9], NULL, thread_select, NULL); + + //pthread_create(&t[10], NULL, thread_delete, NULL); + //pthread_create(&t[11], NULL, thread_delete, NULL); + + pthread_create(&t[12], NULL, thread_delete_manual, NULL); + + //pthread_create(&t[13], NULL, thread_iterate, NULL); + //pthread_create(&t[14], NULL, thread_iterate, NULL); +#else + hargs.thread_safe = 0; + htable = MESA_htable_create(&hargs, sizeof(MESA_htable_create_args_t)); + //MESA_hash_create(&htable, 0, HTABLE_SIZE, NULL, NULL, my_free, HASH_ELIMINATE_ALGO_FIFO, 3); + pthread_create(&t[15], NULL, single_thread, NULL); +#endif + + pthread_create(&t[16], NULL, thread_print, NULL); + + while(1) { + sleep(1); + } + + return 0; +} + +#ifdef __cplusplus +} +#endif + + + diff --git a/support/MESA_htable/example/test_htable_simulate.c b/support/MESA_htable/example/test_htable_simulate.c new file mode 100644 index 0000000..2568899 --- /dev/null +++ b/support/MESA_htable/example/test_htable_simulate.c @@ -0,0 +1,190 @@ +#include <stdio.h> +#include <stdlib.h> +#include <unistd.h> +#include <time.h> +#include <assert.h> +#include "MESA_htable.h" +#ifdef __cplusplus +extern "C" +{ +#endif + +#define HTABLE_ITEM_NUM (1000000) + +const char *G_HTABLE_ITEM_ARRAY[HTABLE_ITEM_NUM]; +char G_HTABLE_ITEM_LEN[HTABLE_ITEM_NUM]; +static volatile int insert_succ_flag = 0; +static MESA_htable_handle htable; + +static long add_times, search_times, del_times; + + +static inline void rand_data(char *data, int len) +{ + int i; + for(i = 0; i < len; i++){ + data[i] = (char)rand(); + } +} + +static void *thread_insert(void *arg) +{ + int i, ret; + int randval; + void *pdata; + int max_hash_collide = 0; + + for(i = 0; i < HTABLE_ITEM_NUM; i++){ + randval = rand() % 10 + 10; + pdata = malloc(randval); + rand_data(pdata, randval); + ret = MESA_htable_add(htable, pdata, randval, pdata); + assert(ret >= 0); + if(ret > max_hash_collide){ + max_hash_collide = ret; + printf("Max hash collide = %d\n", max_hash_collide); + } + G_HTABLE_ITEM_ARRAY[i] = pdata; + G_HTABLE_ITEM_LEN[i] = randval; + } + + insert_succ_flag = 1; + + while(1){ + pause(); + } + + return NULL; +} + +static void *thread_select(void *arg) +{ + int i; + void *res; + int max_times; + double avg_times; + int len; + int randval; + + while(1){ + for(i = 0; i < HTABLE_ITEM_NUM; i++){ + randval = rand() % HTABLE_ITEM_NUM; /* �������, ģ��ʵ����� */ + if(randval < 0){ + randval = 0; + } + res = MESA_htable_search(htable, (const uchar *)G_HTABLE_ITEM_ARRAY[randval], G_HTABLE_ITEM_LEN[randval]); + assert(res != NULL); + search_times++; + +#if 1 /* �ٴβ�ѯ��ͬ����, ���ʹ��bucket-LRU, �ܴ���ʵ�һ�ξ����� */ + res = MESA_htable_search(htable, (const uchar *)G_HTABLE_ITEM_ARRAY[randval], G_HTABLE_ITEM_LEN[randval]); + assert(res != NULL); + search_times++; +#else /* �ٴβ�ѯ��ͬ���� */ + randval = rand() % HTABLE_ITEM_NUM; /* �������, ģ��ʵ����� */ + res = MESA_htable_search(htable, (const uchar *)G_HTABLE_ITEM_ARRAY[randval], G_HTABLE_ITEM_LEN[randval]); + assert(res != NULL); + search_times++; +#endif + } + + len = sizeof(int); + MESA_htable_get_opt(htable, MHO_HASH_SEARCH_MAX_TIMES, &max_times, &len); + printf("max times:%d\n", max_times); + + len = sizeof(double); + MESA_htable_get_opt(htable, MHO_HASH_SEARCH_AVG_TIMES, &avg_times, &len); + printf("avg times:%.3f\n", avg_times); + } + + return NULL; +} + +static void *thread_print(void *arg) +{ + int n; + long this_op_times = 0, last_op_times = 0; + + while(1) + { + this_op_times = add_times+search_times+del_times; + printf("\ntotal element=%u, total op times=%ld, op/s=%ld\n", MESA_htable_get_elem_num(htable), this_op_times, this_op_times-last_op_times); + last_op_times = this_op_times; + sleep(1); + } + + return NULL; +} +int main(void) +{ + int ret; + int opt_int; + pthread_t pid; + + srand(time(NULL)); + + htable = MESA_htable_born(); + assert(htable != NULL); + + opt_int = 1; + MESA_htable_set_opt(htable, MHO_THREAD_SAFE, &opt_int, sizeof(int)); + + opt_int = 512; + MESA_htable_set_opt(htable, MHO_MUTEX_NUM, &opt_int, sizeof(int)); + + opt_int = 1048576; + MESA_htable_set_opt(htable, MHO_HASH_SLOT_SIZE, &opt_int, sizeof(int)); + + opt_int = HTABLE_ITEM_NUM+1; + MESA_htable_set_opt(htable, MHO_HASH_MAX_ELEMENT_NUM, &opt_int, sizeof(int)); + + opt_int = 0; + MESA_htable_set_opt(htable, MHO_EXPIRE_TIME, &opt_int, sizeof(int)); + + opt_int = 1; + MESA_htable_set_opt(htable, MHO_AUTO_UPDATE_TIME, &opt_int, sizeof(int)); + + opt_int = 1; + MESA_htable_set_opt(htable, MHO_SCREEN_PRINT_CTRL, &opt_int, sizeof(int)); + + opt_int = HASH_ELIMINATE_ALGO_LRU; + MESA_htable_set_opt(htable, MHO_ELIMIMINATE_TYPE, &opt_int, sizeof(int)); + + opt_int = 0; + MESA_htable_set_opt(htable, MHO_HASH_LIST_COLLIDE_THRESHOLD, &opt_int, sizeof(int)); + + char *err_log = "./test_hash_collide.log"; + MESA_htable_set_opt(htable, MHO_HASH_LOG_FILE, err_log, strlen(err_log)); + + ret = MESA_htable_mature(htable); + if(0 == ret){ + printf("MESA_htable_mature success!\n"); + }else{ + printf("MESA_htable_mature error!\n"); + return -1; + } + + pthread_create(&pid, NULL, thread_insert, NULL); + while(0 == insert_succ_flag){ + usleep(1); /* �������ݲ����̲߳���������� */ + } + pthread_create(&pid, NULL, thread_select, NULL); + //pthread_create(&pid, NULL, thread_delete, NULL); + + pthread_create(&pid, NULL, thread_print, NULL); + + while(1){ + pause(); + } + + return 0; +} + +#ifdef __cplusplus +} +#endif + + + + + diff --git a/support/MESA_htable/example/test_iterate_demand.c b/support/MESA_htable/example/test_iterate_demand.c new file mode 100644 index 0000000..fdfb88d --- /dev/null +++ b/support/MESA_htable/example/test_iterate_demand.c @@ -0,0 +1,132 @@ +#include <stdio.h> +#include <stdlib.h> +#include <unistd.h> +#include <time.h> +#include "MESA_htable.h" +#ifdef __cplusplus +extern "C" +{ +#endif + +#ifndef MALLOC_CHECK_ +#define MALLOC_CHECK_ (1) +#endif + +MESA_htable_handle htable; + +#define MULTI_THREAD (1) +#define HTABLE_SIZE (1024 * 1024) + +#define RAND_NUM_RANGE (0xfffff) + +static volatile int insert_ok = 0, insert_err = 0; +static volatile int select_hit = 0, select_not_hit = 0; +static volatile int delete_hit = 0, delete_not_hit = 0; +static volatile int rdelete_hit = 0, rdelete_not_hit = 0; /* �ݹ�ɾ�� */ +static volatile int tot_op_times = 0; + +static int ins_n; +static int sel_n; +static int del_n; + +void my_free(void *data) +{ + free(data); +} + + + + int _iterate_cb(const uchar * key, uint size, void * data, void *u) + { + int *p = (int *)data; + printf("\t ## iterate data:%d\n", *p); + +#if 0 + if(*p == 13){ + return ITERATE_CB_RET_DEL_FLAG; + } +#endif +#if 0 + if(*p == 12){ + return ITERATE_CB_RET_REVERSE_FLAG; + } +#endif +#if 1 + //if(*p == 7) + { + free(data); + return ITERATE_CB_RET_REMOVE_BUT_NOT_FREE; + } +#endif + + return ITERATE_CB_RET_CONTINUE_FLAG; + //return ITERATE_CB_RET_BREAK_FLAG; + } + +void *iterate_thread(void *arg) +{ + int n; + sleep(5); + + while(1) + { + MESA_htable_iterate_bytime(htable, 1, _iterate_cb, NULL); + //printf("\ntotal element=%u\n", MESA_htable_get_elem_num(htable)); + //printf("\tOK : ins=%d, sel=%d, del=%d, rdel=%d\n", insert_ok, select_hit, delete_hit, rdelete_hit); + //printf("\tERR: ins=%d, sel=%d, del=%d, rdel=%d\n", insert_err, select_not_hit, delete_not_hit, rdelete_not_hit); + usleep(1000 * 950); + } + + return NULL; +} + +int main(void) +{ + pthread_t t[20]; + MESA_htable_create_args_t hargs; + int num = 0; + int *data; + + srand(time(NULL)); + memset(&hargs, 0, sizeof(MESA_htable_create_args_t)); + hargs.thread_safe = 1; + hargs.recursive = 1; + hargs.hash_slot_size = HTABLE_SIZE; + hargs.max_elem_num = 100000; + hargs.eliminate_type = HASH_ELIMINATE_ALGO_LRU; + hargs.expire_time = 0; + hargs.key_comp = NULL; + hargs.key2index = NULL; + hargs.data_free = NULL; + hargs.data_expire_with_condition = NULL; + htable = MESA_htable_create(&hargs, sizeof(MESA_htable_create_args_t)); +MESA_htable_print_crtl(htable, 1); + + //pthread_create(&t[0], NULL, sel_thread, NULL); + //pthread_create(&t[1], NULL, thread_print, NULL); + pthread_create(&t[2], NULL, iterate_thread, NULL); + //pthread_create(&t[3], NULL, del_thread, NULL); + + while(1) { + data = (int *)malloc(sizeof(int)); + *data = num; + if(num < 200000000){ + if(MESA_htable_add(htable, (uchar *)&num, sizeof(int), data) < 0){ + printf("item %d insert error!\n", num); + }else{ + printf("item %d insert OK!\n", num); + } + num++; + } + usleep(1000 * 59); + } + + return 0; +} + +#ifdef __cplusplus +} +#endif + + + diff --git a/support/MESA_htable/example/test_list_queue.c b/support/MESA_htable/example/test_list_queue.c new file mode 100644 index 0000000..9e72fdd --- /dev/null +++ b/support/MESA_htable/example/test_list_queue.c @@ -0,0 +1,128 @@ +#ifdef __cplusplus +extern "C" +{ +#endif + +#include <stdio.h> +#include <stdlib.h> +#include <unistd.h> +#include <time.h> +#include <pthread.h> +#include <sys/time.h> +#include "MESA_list_queue.h" + +#define CUSTOM_THREAD_NUM (1) +#define PRODUCT_THREAD_NUM (1) + +struct timeval cur_time; +MESA_lqueue_head QUEUE; + +void *producer_thread(void *arg) +{ + int i, ret, count = 0; + char data[1000]; + long data_len; + + for(i = 0; i < 1000; i++) + //while(1) + { + data_len = rand() % 999 + 1; + ret = MESA_lqueue_join_tail(QUEUE, data, data_len); + //MESA_lqueue_try_join_tail(QUEUE, data, data_len); + + if(ret == 0){ + count++; + if(count == 1000){ + printf("post join queue num:%6ld, mem used:%10ld\n", MESA_lqueue_get_count(QUEUE), MESA_lqueue_get_mem_used(QUEUE)); + //sleep(100); + } + }else{ + printf("%s\n", MESA_lqueue_strerror(ret)); + } + } + + return NULL; +} + +void *customer_thread(void *arg) +{ + int i=0, ret, count = 0; + char data[1000]; + long data_len; + + + sleep(3); + printf("pre get queue num:%6ld, mem used:%10ld\n", MESA_lqueue_get_count(QUEUE), MESA_lqueue_get_mem_used(QUEUE)); + + //for(i = 0; i < 100000; i++) + while(1) + { + data_len = 1000; + ret = MESA_lqueue_try_get_head(QUEUE, data, &data_len); + //ret = MESA_lqueue_try_get_head(QUEUE, data, &data_len); + //ret = MESA_lqueue_read_head(QUEUE, data, &data_len); + //if((MESA_QUEUE_RET_OK == ret) && (i++ > 10000)) + + if(ret == 0){ + count++; + if(count == 1000){ + printf("get, queue num is %d\n", 1000); + + printf("post get queue num:%6ld, mem used:%10ld\n", MESA_lqueue_get_count(QUEUE), MESA_lqueue_get_mem_used(QUEUE)); + //sleep(1000); + } + }else{ + MESA_lqueue_destroy(QUEUE, NULL, NULL); + exit(0); + } + } + + return NULL; +} + +int main(void) +{ + void *tmp; + int i, ret; + pthread_t p_tid[PRODUCT_THREAD_NUM], c_tid[CUSTOM_THREAD_NUM]; + + + QUEUE = MESA_lqueue_create(1, 100000); + if(NULL == QUEUE) + { + return -1; + } + + printf("#init, queue num:%ld\n", MESA_lqueue_get_count(QUEUE)); + + srand(time(NULL)); + + for(i = 0; i < PRODUCT_THREAD_NUM; i++) + { + pthread_create(&p_tid[i], NULL, producer_thread, NULL); + } + + for(i = 0; i < CUSTOM_THREAD_NUM; i++) + { + pthread_create(&c_tid[i], NULL, customer_thread, NULL); + } + + for(i = 0; i < PRODUCT_THREAD_NUM; i++) + { + pthread_join(p_tid[i], NULL); + } + for(i = 0; i < CUSTOM_THREAD_NUM; i++) + { + pthread_join(c_tid[i], NULL); + } + + MESA_lqueue_destroy(QUEUE, NULL, NULL); + + return 0; +} + + +#ifdef __cplusplus +} +#endif + diff --git a/support/MESA_htable/example/test_mesa_list.c b/support/MESA_htable/example/test_mesa_list.c new file mode 100644 index 0000000..ba12e81 --- /dev/null +++ b/support/MESA_htable/example/test_mesa_list.c @@ -0,0 +1,91 @@ +#ifdef __cplusplus +extern "C" +{ +#endif + +#include <stdio.h> +#include <stdlib.h> +#include <unistd.h> +#include <time.h> +#include <pthread.h> +#include <sys/time.h> +#include "MESA_list_count.h" + +MESA_list_count_t list_head; + +static void insert_value(int value) +{ + int *p = malloc(sizeof(int)); + MESA_list_count_t *obj = malloc(sizeof(MESA_list_count_t)); + *p = value; + obj->quiddity = p; + MESA_list_count_add_tail(&list_head, obj); +} + + +MESA_list_count_t *find_value(MESA_list_count_t *head, int value) +{ + MESA_list_count_t *next, *p = head->nextele; + + while(p != head){ + next = p->nextele; + if(*((int *)p->quiddity) == value){ + return p; + } + p = next; + } + + return NULL; +} + +void print_list(MESA_list_count_t *head) +{ + MESA_list_count_t *next, *p = head->nextele; + + while(p != head){ + next = p->nextele; + printf("%d, ", *((int *)p->quiddity)); + p = next; + } + + printf("\n"); +} + +int main(void) +{ + MESA_list_count_t *p, *new_obj; + int *value; + + MESA_list_count_init_head(&list_head); + + insert_value(1); + insert_value(2); + insert_value(3); + insert_value(5); + print_list(&list_head); + + p = find_value(&list_head, 3); + if(NULL == p){ + printf("Not found %d\n", 3); + exit(1); + } + new_obj = malloc(sizeof(MESA_list_count_t)); + value = malloc(sizeof(int)); + *value = 4; + new_obj->quiddity = value; + +#if 1 + MESA_list_count_join_n(&list_head, p, new_obj); +#else + MESA_list_count_join_p(&list_head, new_obj, p); +#endif + + print_list(&list_head); + + return 0; +} + +#ifdef __cplusplus +} +#endif + diff --git a/support/MESA_htable/example/test_ring_queue.c b/support/MESA_htable/example/test_ring_queue.c new file mode 100644 index 0000000..3c0a47b --- /dev/null +++ b/support/MESA_htable/example/test_ring_queue.c @@ -0,0 +1,105 @@ +#include "MESA_ring_queue.h" +#include <stdio.h> +#include <string.h> +#include <stdlib.h> +#include <time.h> +#include <unistd.h> +#include <pthread.h> +#include <assert.h> +#include <linux/limits.h> +#include <sys/types.h> +#include <sys/stat.h> +#include <unistd.h> +#ifdef __cplusplus +extern "C" +{ +#endif + +#define RING_QUEUE_TEST_NUM (10000000) + +static MESA_ring_queue_head RQ; +static time_t start_time; + +void *rq_producter(void *arg) +{ + int i; + while(1){ + for(i = 0; i < RING_QUEUE_TEST_NUM+10; i++){ + //while(MESA_ring_queue_try_join(RQ, &i, sizeof(int)) != 0); + MESA_ring_queue_join(RQ, &i, sizeof(int)); + //usleep(1000); + } + + //MESA_ring_queue_destroy(RQ, NULL, NULL); + //exit(1); + } + + return NULL; +} + +void *rq_customer(void *arg) +{ + int ret, data, data_len, i; + int tid = *(int *)arg; + while(1){ + data_len = sizeof(int); + for(i = 0; i < RING_QUEUE_TEST_NUM; i++){ + MESA_ring_queue_get(RQ, &data, &data_len); + } + //printf("tid:%d get %d\n", tid, data); + //usleep(100000); + + printf("time cost = %d\n", time(NULL) - start_time); + + exit(0); + } + + return NULL; + +} + + +int main(void) +{ + pthread_t pid; + int opt, i; + + printf("program start, time=%d\n", time(NULL)); + + RQ = MESA_ring_queue_born(); + + opt = 0; + MESA_ring_queue_set_opt(RQ, RQO_THREAD_SAFE, &opt, sizeof(int)); + + opt = 1024; + MESA_ring_queue_set_opt(RQ, RQO_PRE_ALLOC_BUF_LEN, &opt, sizeof(int)); + + opt = RING_QUEUE_TEST_NUM; + MESA_ring_queue_set_opt(RQ, RQO_RING_ELEMENT_NUM, &opt, sizeof(int)); + + opt =1; + MESA_ring_queue_set_opt(RQ, RQO_MULTI_THREAD_LOCK_FREE, &opt, sizeof(int)); + + if(MESA_ring_queue_mature(RQ) < 0){ + return -1; + } + + i = 0; + + printf("queue init OK, time=%d\n", time(NULL)); + start_time = time(NULL); + pthread_create(&pid, NULL, rq_producter, NULL); + pthread_create(&pid, NULL, rq_customer, (void *)&i); + + + while(1){ + pause(); + } + + return 0; +} + +#ifdef __cplusplus +} +#endif + diff --git a/support/MESA_htable/include/MESA_atomic.h b/support/MESA_htable/include/MESA_atomic.h new file mode 100644 index 0000000..76e5b80 --- /dev/null +++ b/support/MESA_htable/include/MESA_atomic.h @@ -0,0 +1,38 @@ +#ifndef _MESA_ATOMIC_H_ +#define _MESA_ATOMIC_H_ + + +#if(__GNUC__ * 100 + __GNUC_MINOR__ * 10 + __GNUC_PATCHLEVEL__ >= 411) +typedef unsigned long MESA_ATOMIC_T; +#define MESA_ATOMIC_SET(v, i) __sync_lock_test_and_set((&v), i) +#define MESA_ATOMIC_READ(v) __sync_or_and_fetch((&v), 0) +#define MESA_ATOMIC_INC(v) __sync_add_and_fetch((&v),1) +#define MESA_ATOMIC_DEC(v) __sync_sub_and_fetch((&v),1) +#define MESA_ATOMIC_ADD(v,add) __sync_add_and_fetch((&v),(add)) +#define MESA_ATOMIC_SUB(v,sub) __sync_sub_and_fetch((&v),(sub)) +#else +#include <alsa/iatomic.h> +typedef atomic_t MESA_ATOMIC_T; +#define MESA_ATOMIC_SET(v, i) atomic_set((&v), i) +#define MESA_ATOMIC_READ(v) atomic_read((&v)) +#define MESA_ATOMIC_INC(v) atomic_inc((&v)) +#define MESA_ATOMIC_DEC(v) atomic_dec((&v)) +#define MESA_ATOMIC_ADD(v, add) atomic_add((add),(&v)) +#define MESA_ATOMIC_SUB(v, sub) atomic_sub((sub),(&v)) +#endif + + +#ifdef __tilegx__ +#include <arch/atomic.h> +typedef int MESA_ATOMIC_T; +#define MESA_ATOMIC_SET(v, i) arch_atomic_exchange((&v), i) +#define MESA_ATOMIC_READ(v) arch_atomic_or((&v), 0) +#define MESA_ATOMIC_INC(v) arch_atomic_add((&v), 1) +#define MESA_ATOMIC_DEC(v) arch_atomic_sub((&v), 1) +#define MESA_ATOMIC_ADD(v, add) arch_atomic_add((&v), add) +#define MESA_ATOMIC_SUB(v, sub) arch_atomic_sub((&v), sub) +#endif + + +#endif + diff --git a/support/MESA_htable/include/MESA_htable.h b/support/MESA_htable/include/MESA_htable.h new file mode 100644 index 0000000..ac7c2b2 --- /dev/null +++ b/support/MESA_htable/include/MESA_htable.h @@ -0,0 +1,419 @@ +#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); + +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 "./hash_list_collide.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_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_ */ + + diff --git a/support/MESA_htable/include/MESA_list.h b/support/MESA_htable/include/MESA_list.h new file mode 100644 index 0000000..6ad7c45 --- /dev/null +++ b/support/MESA_htable/include/MESA_list.h @@ -0,0 +1,34 @@ +#ifndef _MESA_LIST_H_ +#define _MESA_LIST_H_ + +typedef struct MESA_list{ + struct MESA_list *nextele; + struct MESA_list *preele; + void *quiddity; +}MESA_list_t; + + +#ifdef __cplusplus +extern "C" +{ +#endif + +#define MESA_LIST_VERSION_MACRO (20150529) +extern const unsigned int MESA_LIST_VERSION_INT; + +void MESA_list_init_head(struct MESA_list *head); +int MESA_list_is_empty(const struct MESA_list *head); +void MESA_list_add(struct MESA_list *head, struct MESA_list *new_list); +void MESA_list_add_tail(struct MESA_list *head, struct MESA_list *new_list); +void MESA_list_del(struct MESA_list *head, struct MESA_list *del_list); +void MESA_list_move(struct MESA_list *head, struct MESA_list *list); +void MESA_list_move_tail(struct MESA_list *head, struct MESA_list *list); +struct MESA_list *MESA_list_join_n(struct MESA_list *head, struct MESA_list *op_place, struct MESA_list *new_obj); +struct MESA_list *MESA_list_join_p(struct MESA_list *head, struct MESA_list *new_obj, struct MESA_list *op_place); + +#ifdef __cplusplus +} +#endif + +#endif + diff --git a/support/MESA_htable/include/MESA_list_count.h b/support/MESA_htable/include/MESA_list_count.h new file mode 100644 index 0000000..884ee74 --- /dev/null +++ b/support/MESA_htable/include/MESA_list_count.h @@ -0,0 +1,31 @@ +#ifndef _MESA_LIST_COUNT_H_ +#define _MESA_LIST_COUNT_H_ + +typedef struct MESA_list_count{ + struct MESA_list_count *nextele; + struct MESA_list_count *preele; + void *quiddity; +}MESA_list_count_t; + +#ifdef __cplusplus +extern "C" +{ +#endif + +void MESA_list_count_init_head(struct MESA_list_count *head); +long MESA_list_count_get_count(const struct MESA_list_count *head); +int MESA_list_count_is_empty(const struct MESA_list_count *head); +void MESA_list_count_add(struct MESA_list_count *head, struct MESA_list_count *new_list); +void MESA_list_count_add_tail(struct MESA_list_count *head, struct MESA_list_count *new_list); +void MESA_list_count_del(struct MESA_list_count *head, struct MESA_list_count *del_list); +void MESA_list_count_move(struct MESA_list_count *head, struct MESA_list_count *list); +void MESA_list_count_move_tail(struct MESA_list_count *head, struct MESA_list_count *list); +struct MESA_list_count *MESA_list_count_join_n(struct MESA_list_count *head, struct MESA_list_count *op_place, struct MESA_list_count *new_obj); +struct MESA_list_count *MESA_list_count_join_p(struct MESA_list_count *head, struct MESA_list_count *new_obj, struct MESA_list_count *op_place); + +#ifdef __cplusplus +} +#endif + +#endif + diff --git a/support/MESA_htable/include/MESA_list_queue.h b/support/MESA_htable/include/MESA_list_queue.h new file mode 100644 index 0000000..08ce32b --- /dev/null +++ b/support/MESA_htable/include/MESA_list_queue.h @@ -0,0 +1,115 @@ +#ifndef _MESA_LIST_QUEUE_H_ +#define _MESA_LIST_QUEUE_H_ + +#ifdef __cplusplus +extern "C" +{ +#endif + +/* + MESA_list �����棬 + 1-�����̰߳�ȫ����; + 2-�����ڲ��ṹ, ����ȫ���ӿڸ����; + 3-�������������й����ڵ�ṹ��ʹ�ø�����; +*/ + +#define MESA_LIST_QUEUE_VERSION_MACRO (20160308) +extern const unsigned int MESA_LIST_QUEUE_VERSION_INT; + +#define MESA_LIST_OP_PLACE_HEAD (0x1) +#define MESA_LIST_OP_PLACE_TAIL (0x2) + +#define MESA_list_GET (0x1) +#define MESA_list_JOIN (0x2) + +#define MESA_list_BOLCK (0x4) +#define MESA_list_NONBOLCK (0x8) + +#define MESA_list_JOIN_BLOCK (MESA_list_JOIN|MESA_list_BOLCK) +#define MESA_list_JOIN_NONBLOCK (MESA_list_JOIN|MESA_list_NONBOLCK) +#define MESA_list_GET_BLOCK (MESA_list_GET|MESA_list_BOLCK) +#define MESA_list_GET_NONBLOCK (MESA_list_GET|MESA_list_NONBOLCK) + +typedef void * MESA_lqueue_head; +typedef int (* MESA_lqueue_cb_t)(void *data, long data_len, void *arg); + +/* All of the following functions return value */ +typedef enum{ + MESA_QUEUE_RET_OK = 0, /* success */ + MESA_QUEUE_RET_COMMON_ERR = -1, /* general��undefined errors */ + MESA_QUEUE_RET_ARG_ERR = -2, /* invalid args */ + MESA_QUEUE_RET_NUM_FULL = -3, /* queue number full */ + MESA_QUEUE_RET_MEM_FULL = -4, /* queue memory full */ + MESA_QUEUE_RET_QEMPTY = -5, /* queue empty */ + MESA_QUEUE_RET_LEN_ERR = -6, /* length error */ + MESA_QUEUE_RET_CANT_GET_LOCK = -7, /* can't get lock in non-block mode */ + MESA_QUEUE_RET_GET_LOCK_TMOUT = -8, /* get lock timeout */ +}MESA_queue_errno_t; + +/* + args description: + [IN] + thread_safe : 1:create thread safe queue; 0:without thread safe insurance. + max_item_num: maximum queue items of the queue, 0 means infinity. +*/ +MESA_lqueue_head MESA_lqueue_create(int thread_safe, long max_item_num); + +/* + attention: + The follow two functions is get some value of queue in a moment, + however, the value you got is not exactly, + because it's maybe changed immediately by other thread when this functions is return. +*/ +long MESA_lqueue_get_mem_used(MESA_lqueue_head head); +long MESA_lqueue_get_count(MESA_lqueue_head head); + + +/* + args description: + [IN]: + lq_head : the handler of MESA_lqueue. + + [OUT]: + data : receive buffer. + + [IN && OUT]: + data_len: + is value-result argument, like "addrlen of recvfrom(2)", + the caller should initialize the size of the 'data', + will modified on return to indicate the actual size of the queue item. + +*/ +int MESA_lqueue_read_head(MESA_lqueue_head lq_head, void *data, long *data_len); +int MESA_lqueue_get_head(MESA_lqueue_head lqhead, void *data, long *data_len); + +/* + if return value of "cb" is 0, the behaviour is like MESA_lqueue_read_head(), + else if return value of "cb" is not 0, the behaviour is like MESA_lqueue_get_head(). +*/ +int MESA_lqueue_detect_get_head(MESA_lqueue_head lq_head, MESA_lqueue_cb_t cb, void *data, long *data_len, void *cb_arg); +int MESA_lqueue_get_tail(MESA_lqueue_head lq_head, void *data, long *data_len); + +int MESA_lqueue_join_head(MESA_lqueue_head lq_head, const void *data, long data_len); +int MESA_lqueue_join_tail(MESA_lqueue_head lq_head, const void *data, long data_len); + + +/* these functions features same with above no "try", + except shall return immediately, in other word is "Non-block mode"! + */ +int MESA_lqueue_try_read_head(MESA_lqueue_head lq_head, void *data, long *data_len); +int MESA_lqueue_try_get_head(MESA_lqueue_head lq_head, void *data, long *data_len); +int MESA_lqueue_try_get_tail(MESA_lqueue_head lq_head, void *data, long *data_len); +int MESA_lqueue_try_join_head(MESA_lqueue_head lq_head, const void *data, long data_len); +int MESA_lqueue_try_join_tail(MESA_lqueue_head lq_head, const void *data, long data_len); + + +void MESA_lqueue_destroy(MESA_lqueue_head head, MESA_lqueue_cb_t cb, void *cb_arg); + +const char *MESA_lqueue_strerror(MESA_queue_errno_t error_num); + +#ifdef __cplusplus +} +#endif + +#endif + diff --git a/support/MESA_htable/include/MESA_ring_queue.h b/support/MESA_htable/include/MESA_ring_queue.h new file mode 100644 index 0000000..cc1efe8 --- /dev/null +++ b/support/MESA_htable/include/MESA_ring_queue.h @@ -0,0 +1,107 @@ +#ifndef __MESA_RING_QUEUE_H_ +#define __MESA_RING_QUEUE_H_ 1 + +#ifdef __cplusplus +extern "C" +{ +#endif + +typedef void * MESA_ring_queue_head; + +#define MESA_RING_QUEUE_VERSION_MACRO (20160708) +extern const unsigned int MESA_RING_QUEUE_VERSION_INT; + +/* All of the following functions return value */ +typedef enum{ + MESA_RQUEUE_RET_OK = 0, /* success */ + MESA_RQUEUE_RET_COMMON_ERR = -1, /* general��undefined errors */ + MESA_RQUEUE_RET_ARG_ERR = -2, /* invalid args */ + MESA_RQUEUE_RET_NUM_FULL = -3, /* queue number full */ + MESA_RQUEUE_RET_MEM_FULL = -4, /* queue memory full */ + MESA_RQUEUE_RET_QEMPTY = -5, /* queue empty */ + MESA_RQUEUE_RET_LEN_ERR = -6, /* length error */ + MESA_RQUEUE_RET_CANT_GET_LOCK = -7, /* can't get lock in non-block mode */ + MESA_RQUEUE_RET_GET_LOCK_TMOUT = -8, /* get lock timeout */ +}MESA_ring_queue_errno_t; + + +/* + args description: + [IN] + thread_safe : 1:create thread safe queue; 0:without thread safe insurance. + max_item_num: maximum queue items of the queue, must more than zero. +*/ +MESA_ring_queue_head MESA_ring_queue_born(void); + + +enum MESA_rq_opt{ + RQO_THREAD_SAFE = 0, /* must be int, 1:create ring qqueue with thread safe features, default is 1 */ + RQO_RING_ELEMENT_NUM, /* must be unsigned int, defalut is 1000. */ + RQO_PRE_ALLOC_BUF_LEN, /* must be unsigned int, Ԥ�ȷ���ÿ��item���ڴ�, �Ժ�ֻ��memcpy */ + RQO_MULTI_THREAD_LOCK_FREE, /* must be int, default is 0, conflict with RQO_THREAD_SAFE */ +}; + +/* + to set features of specified MESA_ring_queue_headhandle. + 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_ring_queue_set_opt(MESA_ring_queue_head rq, enum MESA_rq_opt opt_type, void *opt_val, int opt_len); + + +/* + Construct ring queue and ready to running. + + return value: + 0 : success; + <0: error. +*/ +int MESA_ring_queue_mature(MESA_ring_queue_head rq); + + + +int MESA_ring_queue_get_count(MESA_ring_queue_head head); + +/* + args description: + [IN]: + lq_head : the handler of MESA_ring_queue. + + [OUT]: + data : receive buffer. + + [IN && OUT]: + data_len: + is value-result argument, like "addrlen of recvfrom(2)", + the caller should initialize the size of the 'data', + will modified on return to indicate the actual size of the queue item. + +*/ +int MESA_ring_queue_read(MESA_ring_queue_head rq_head, void *data, int *data_len); +int MESA_ring_queue_get(MESA_ring_queue_head rqhead, void *data, int *data_len); +int MESA_ring_queue_join(MESA_ring_queue_head rq_head, const void *data, int data_len); + + +/* these functions features same with above no "try", + except shall return immediately, in other word is "Non-block mode"! + */ +int MESA_ring_queue_try_read(MESA_ring_queue_head rq_head, void *data, int *data_len); +int MESA_ring_queue_try_get(MESA_ring_queue_head rqhead, void *data, int *data_len); +int MESA_ring_queue_try_join(MESA_ring_queue_head rq_head, const void *data, int data_len); + + +typedef int (* MESA_rqueue_cb_t)(void *data, long data_len, void *arg); +void MESA_ring_queue_destroy(MESA_ring_queue_head rq_head, MESA_rqueue_cb_t cb, void *cb_arg); +const char *MESA_ring_queue_strerror(MESA_ring_queue_errno_t error_num); + +#ifdef __cplusplus +} +#endif + +#endif + diff --git a/support/MESA_htable/lib/.gitignore b/support/MESA_htable/lib/.gitignore new file mode 100644 index 0000000..b9e4d17 --- /dev/null +++ b/support/MESA_htable/lib/.gitignore @@ -0,0 +1,4 @@ +__view +*.o +*.so +*.a diff --git a/support/MESA_htable/rb_tree/Makefile b/support/MESA_htable/rb_tree/Makefile new file mode 100644 index 0000000..6bc59ef --- /dev/null +++ b/support/MESA_htable/rb_tree/Makefile @@ -0,0 +1,2 @@ +rb_tree_test:rbtree.c rbtree_test.c + gcc -o $@ $^ diff --git a/support/MESA_htable/rb_tree/rbtree.c b/support/MESA_htable/rb_tree/rbtree.c new file mode 100644 index 0000000..9257006 --- /dev/null +++ b/support/MESA_htable/rb_tree/rbtree.c @@ -0,0 +1,496 @@ +/* + Red Black Trees + (C) 1999 Andrea Arcangeli <[email protected]> + (C) 2002 David Woodhouse <[email protected]> + (C) 2012 Michel Lespinasse <[email protected]> + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + + linux/lib/rbtree.c +*/ + +#include "rbtree_augmented.h" + +/* + * red-black trees properties: http://en.wikipedia.org/wiki/Rbtree + * + * 1) A node is either red or black + * 2) The root is black + * 3) All leaves (NULL) are black + * 4) Both children of every red node are black + * 5) Every simple path from root to leaves contains the same number + * of black nodes. + * + * 4 and 5 give the O(log n) guarantee, since 4 implies you cannot have two + * consecutive red nodes in a path and every red node is therefore followed by + * a black. So if B is the number of black nodes on every simple path (as per + * 5), then the longest possible path due to 4 is 2B. + * + * We shall indicate color with case, where black nodes are uppercase and red + * nodes will be lowercase. Unknown color nodes shall be drawn as red within + * parentheses and have some accompanying text comment. + */ + +static inline void rb_set_black(struct rb_node *rb) +{ + rb->__rb_parent_color |= RB_BLACK; +} + +static inline struct rb_node *rb_red_parent(struct rb_node *red) +{ + return (struct rb_node *)red->__rb_parent_color; +} + +/* + * Helper function for rotations: + * - old's parent and color get assigned to new + * - old gets assigned new as a parent and 'color' as a color. + */ +static inline void +__rb_rotate_set_parents(struct rb_node *old, struct rb_node *new, + struct rb_root *root, int color) +{ + struct rb_node *parent = rb_parent(old); + new->__rb_parent_color = old->__rb_parent_color; + rb_set_parent_color(old, new, color); + __rb_change_child(old, new, parent, root); +} + +static void +__rb_insert(struct rb_node *node, struct rb_root *root, + void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) +{ + struct rb_node *parent = rb_red_parent(node), *gparent, *tmp; + + while (1) { + /* + * Loop invariant: node is red + * + * If there is a black parent, we are done. + * Otherwise, take some corrective action as we don't + * want a red root or two consecutive red nodes. + */ + if (!parent) { + rb_set_parent_color(node, NULL, RB_BLACK); + break; + } else if (rb_is_black(parent)) + break; + + gparent = rb_red_parent(parent); + + tmp = gparent->rb_right; + if (parent != tmp) { /* parent == gparent->rb_left */ + if (tmp && rb_is_red(tmp)) { + /* + * Case 1 - color flips + * + * G g + * / \ / \ + * p u --> P U + * / / + * n N + * + * However, since g's parent might be red, and + * 4) does not allow this, we need to recurse + * at g. + */ + rb_set_parent_color(tmp, gparent, RB_BLACK); + rb_set_parent_color(parent, gparent, RB_BLACK); + node = gparent; + parent = rb_parent(node); + rb_set_parent_color(node, parent, RB_RED); + continue; + } + + tmp = parent->rb_right; + if (node == tmp) { + /* + * Case 2 - left rotate at parent + * + * G G + * / \ / \ + * p U --> n U + * \ / + * n p + * + * This still leaves us in violation of 4), the + * continuation into Case 3 will fix that. + */ + parent->rb_right = tmp = node->rb_left; + node->rb_left = parent; + if (tmp) + rb_set_parent_color(tmp, parent, + RB_BLACK); + rb_set_parent_color(parent, node, RB_RED); + augment_rotate(parent, node); + parent = node; + tmp = node->rb_right; + } + + /* + * Case 3 - right rotate at gparent + * + * G P + * / \ / \ + * p U --> n g + * / \ + * n U + */ + gparent->rb_left = tmp; /* == parent->rb_right */ + parent->rb_right = gparent; + if (tmp) + rb_set_parent_color(tmp, gparent, RB_BLACK); + __rb_rotate_set_parents(gparent, parent, root, RB_RED); + augment_rotate(gparent, parent); + break; + } else { + tmp = gparent->rb_left; + if (tmp && rb_is_red(tmp)) { + /* Case 1 - color flips */ + rb_set_parent_color(tmp, gparent, RB_BLACK); + rb_set_parent_color(parent, gparent, RB_BLACK); + node = gparent; + parent = rb_parent(node); + rb_set_parent_color(node, parent, RB_RED); + continue; + } + + tmp = parent->rb_left; + if (node == tmp) { + /* Case 2 - right rotate at parent */ + parent->rb_left = tmp = node->rb_right; + node->rb_right = parent; + if (tmp) + rb_set_parent_color(tmp, parent, + RB_BLACK); + rb_set_parent_color(parent, node, RB_RED); + augment_rotate(parent, node); + parent = node; + tmp = node->rb_left; + } + + /* Case 3 - left rotate at gparent */ + gparent->rb_right = tmp; /* == parent->rb_left */ + parent->rb_left = gparent; + if (tmp) + rb_set_parent_color(tmp, gparent, RB_BLACK); + __rb_rotate_set_parents(gparent, parent, root, RB_RED); + augment_rotate(gparent, parent); + break; + } + } +} + +void +__rb_erase_color(struct rb_node *parent, struct rb_root *root, + void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) +{ + struct rb_node *node = NULL, *sibling, *tmp1, *tmp2; + + while (1) { + /* + * Loop invariants: + * - node is black (or NULL on first iteration) + * - node is not the root (parent is not NULL) + * - All leaf paths going through parent and node have a + * black node count that is 1 lower than other leaf paths. + */ + sibling = parent->rb_right; + if (node != sibling) { /* node == parent->rb_left */ + if (rb_is_red(sibling)) { + /* + * Case 1 - left rotate at parent + * + * P S + * / \ / \ + * N s --> p Sr + * / \ / \ + * Sl Sr N Sl + */ + parent->rb_right = tmp1 = sibling->rb_left; + sibling->rb_left = parent; + rb_set_parent_color(tmp1, parent, RB_BLACK); + __rb_rotate_set_parents(parent, sibling, root, + RB_RED); + augment_rotate(parent, sibling); + sibling = tmp1; + } + tmp1 = sibling->rb_right; + if (!tmp1 || rb_is_black(tmp1)) { + tmp2 = sibling->rb_left; + if (!tmp2 || rb_is_black(tmp2)) { + /* + * Case 2 - sibling color flip + * (p could be either color here) + * + * (p) (p) + * / \ / \ + * N S --> N s + * / \ / \ + * Sl Sr Sl Sr + * + * This leaves us violating 5) which + * can be fixed by flipping p to black + * if it was red, or by recursing at p. + * p is red when coming from Case 1. + */ + rb_set_parent_color(sibling, parent, + RB_RED); + if (rb_is_red(parent)) + rb_set_black(parent); + else { + node = parent; + parent = rb_parent(node); + if (parent) + continue; + } + break; + } + /* + * Case 3 - right rotate at sibling + * (p could be either color here) + * + * (p) (p) + * / \ / \ + * N S --> N Sl + * / \ \ + * sl Sr s + * \ + * Sr + */ + sibling->rb_left = tmp1 = tmp2->rb_right; + tmp2->rb_right = sibling; + parent->rb_right = tmp2; + if (tmp1) + rb_set_parent_color(tmp1, sibling, + RB_BLACK); + augment_rotate(sibling, tmp2); + tmp1 = sibling; + sibling = tmp2; + } + /* + * Case 4 - left rotate at parent + color flips + * (p and sl could be either color here. + * After rotation, p becomes black, s acquires + * p's color, and sl keeps its color) + * + * (p) (s) + * / \ / \ + * N S --> P Sr + * / \ / \ + * (sl) sr N (sl) + */ + parent->rb_right = tmp2 = sibling->rb_left; + sibling->rb_left = parent; + rb_set_parent_color(tmp1, sibling, RB_BLACK); + if (tmp2) + rb_set_parent(tmp2, parent); + __rb_rotate_set_parents(parent, sibling, root, + RB_BLACK); + augment_rotate(parent, sibling); + break; + } else { + sibling = parent->rb_left; + if (rb_is_red(sibling)) { + /* Case 1 - right rotate at parent */ + parent->rb_left = tmp1 = sibling->rb_right; + sibling->rb_right = parent; + rb_set_parent_color(tmp1, parent, RB_BLACK); + __rb_rotate_set_parents(parent, sibling, root, + RB_RED); + augment_rotate(parent, sibling); + sibling = tmp1; + } + tmp1 = sibling->rb_left; + if (!tmp1 || rb_is_black(tmp1)) { + tmp2 = sibling->rb_right; + if (!tmp2 || rb_is_black(tmp2)) { + /* Case 2 - sibling color flip */ + rb_set_parent_color(sibling, parent, + RB_RED); + if (rb_is_red(parent)) + rb_set_black(parent); + else { + node = parent; + parent = rb_parent(node); + if (parent) + continue; + } + break; + } + /* Case 3 - right rotate at sibling */ + sibling->rb_right = tmp1 = tmp2->rb_left; + tmp2->rb_left = sibling; + parent->rb_left = tmp2; + if (tmp1) + rb_set_parent_color(tmp1, sibling, + RB_BLACK); + augment_rotate(sibling, tmp2); + tmp1 = sibling; + sibling = tmp2; + } + /* Case 4 - left rotate at parent + color flips */ + parent->rb_left = tmp2 = sibling->rb_right; + sibling->rb_right = parent; + rb_set_parent_color(tmp1, sibling, RB_BLACK); + if (tmp2) + rb_set_parent(tmp2, parent); + __rb_rotate_set_parents(parent, sibling, root, + RB_BLACK); + augment_rotate(parent, sibling); + break; + } + } +} + +/* + * Non-augmented rbtree manipulation functions. + * + * We use dummy augmented callbacks here, and have the compiler optimize them + * out of the rb_insert_color() and rb_erase() function definitions. + */ + +static inline void dummy_propagate(struct rb_node *node, struct rb_node *stop) {} +static inline void dummy_copy(struct rb_node *old, struct rb_node *new) {} +static inline void dummy_rotate(struct rb_node *old, struct rb_node *new) {} + +static const struct rb_augment_callbacks dummy_callbacks = { + dummy_propagate, dummy_copy, dummy_rotate +}; + +void rb_insert_color(struct rb_node *node, struct rb_root *root) +{ + __rb_insert(node, root, dummy_rotate); +} + +void rb_erase(struct rb_node *node, struct rb_root *root) +{ + rb_erase_augmented(node, root, &dummy_callbacks); +} + +/* + * Augmented rbtree manipulation functions. + * + * This instantiates the same __always_inline functions as in the non-augmented + * case, but this time with user-defined callbacks. + */ + +void __rb_insert_augmented(struct rb_node *node, struct rb_root *root, + void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) +{ + __rb_insert(node, root, augment_rotate); +} + +/* + * This function returns the first node (in sort order) of the tree. + */ +struct rb_node *rb_first(const struct rb_root *root) +{ + struct rb_node *n; + + n = root->rb_node; + if (!n) + return NULL; + while (n->rb_left) + n = n->rb_left; + return n; +} + +struct rb_node *rb_last(const struct rb_root *root) +{ + struct rb_node *n; + + n = root->rb_node; + if (!n) + return NULL; + while (n->rb_right) + n = n->rb_right; + return n; +} + +struct rb_node *rb_next(const struct rb_node *node) +{ + struct rb_node *parent; + + if (RB_EMPTY_NODE(node)) + return NULL; + + /* + * If we have a right-hand child, go down and then left as far + * as we can. + */ + if (node->rb_right) { + node = node->rb_right; + while (node->rb_left) + node=node->rb_left; + return (struct rb_node *)node; + } + + /* + * No right-hand children. Everything down and left is smaller than us, + * so any 'next' node must be in the general direction of our parent. + * Go up the tree; any time the ancestor is a right-hand child of its + * parent, keep going up. First time it's a left-hand child of its + * parent, said parent is our 'next' node. + */ + while ((parent = rb_parent(node)) && node == parent->rb_right) + node = parent; + + return parent; +} + +struct rb_node *rb_prev(const struct rb_node *node) +{ + struct rb_node *parent; + + if (RB_EMPTY_NODE(node)) + return NULL; + + /* + * If we have a left-hand child, go down and then right as far + * as we can. + */ + if (node->rb_left) { + node = node->rb_left; + while (node->rb_right) + node=node->rb_right; + return (struct rb_node *)node; + } + + /* + * No left-hand children. Go up till we find an ancestor which + * is a right-hand child of its parent. + */ + while ((parent = rb_parent(node)) && node == parent->rb_left) + node = parent; + + return parent; +} + +void rb_replace_node(struct rb_node *victim, struct rb_node *new, + struct rb_root *root) +{ + struct rb_node *parent = rb_parent(victim); + + /* Set the surrounding nodes to point to the replacement */ + __rb_change_child(victim, new, parent, root); + if (victim->rb_left) + rb_set_parent(victim->rb_left, new); + if (victim->rb_right) + rb_set_parent(victim->rb_right, new); + + /* Copy the pointers/colour from the victim to the replacement */ + *new = *victim; +} diff --git a/support/MESA_htable/rb_tree/rbtree.h b/support/MESA_htable/rb_tree/rbtree.h new file mode 100644 index 0000000..05e67d4 --- /dev/null +++ b/support/MESA_htable/rb_tree/rbtree.h @@ -0,0 +1,94 @@ +/* + Red Black Trees + (C) 1999 Andrea Arcangeli <[email protected]> + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + + linux/include/linux/rbtree.h + + To use rbtrees you'll have to implement your own insert and search cores. + This will avoid us to use callbacks and to drop drammatically performances. + I know it's not the cleaner way, but in C (not in C++) to get + performances and genericity... + + See Documentation/rbtree.txt for documentation and samples. +*/ + +#ifndef _LINUX_RBTREE_H +#define _LINUX_RBTREE_H + +#include <stdio.h> + +struct rb_node { + unsigned long __rb_parent_color; + struct rb_node *rb_right; + struct rb_node *rb_left; +} __attribute__((aligned(sizeof(long)))); + /* The alignment might seem pointless, but allegedly CRIS needs it */ + +struct rb_root { + struct rb_node *rb_node; +}; + +#undef offsetof +#ifdef __compiler_offsetof +#define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER) +#else +#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER) +#endif + +#define container_of(ptr, type, member) ({ \ + const typeof( ((type *)0)->member ) *__mptr = (ptr); \ + (type *)( (char *)__mptr - offsetof(type,member) );}) + + +#define rb_parent(r) ((struct rb_node *)((r)->__rb_parent_color & ~3)) + +#define RB_ROOT (struct rb_root) { NULL, } +#define rb_entry(ptr, type, member) container_of(ptr, type, member) + +#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL) + +/* 'empty' nodes are nodes that are known not to be inserted in an rbree */ +#define RB_EMPTY_NODE(node) \ + ((node)->__rb_parent_color == (unsigned long)(node)) +#define RB_CLEAR_NODE(node) \ + ((node)->__rb_parent_color = (unsigned long)(node)) + + +extern void rb_insert_color(struct rb_node *, struct rb_root *); +extern void rb_erase(struct rb_node *, struct rb_root *); + + +/* Find logical next and previous nodes in a tree */ +extern struct rb_node *rb_next(const struct rb_node *); +extern struct rb_node *rb_prev(const struct rb_node *); +extern struct rb_node *rb_first(const struct rb_root *); +extern struct rb_node *rb_last(const struct rb_root *); + +/* Fast replacement of a single node without remove/rebalance/add/rebalance */ +extern void rb_replace_node(struct rb_node *victim, struct rb_node *new, + struct rb_root *root); + +static inline void rb_link_node(struct rb_node * node, struct rb_node * parent, + struct rb_node ** rb_link) +{ + node->__rb_parent_color = (unsigned long)parent; + node->rb_left = node->rb_right = NULL; + + *rb_link = node; +} + +#endif /* _LINUX_RBTREE_H */ diff --git a/support/MESA_htable/rb_tree/rbtree_augmented.h b/support/MESA_htable/rb_tree/rbtree_augmented.h new file mode 100644 index 0000000..52692b8 --- /dev/null +++ b/support/MESA_htable/rb_tree/rbtree_augmented.h @@ -0,0 +1,223 @@ +/* + Red Black Trees + (C) 1999 Andrea Arcangeli <[email protected]> + (C) 2002 David Woodhouse <[email protected]> + (C) 2012 Michel Lespinasse <[email protected]> + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + + linux/include/linux/rbtree_augmented.h +*/ + +#ifndef _LINUX_RBTREE_AUGMENTED_H +#define _LINUX_RBTREE_AUGMENTED_H + +#include "rbtree.h" + +/* + * Please note - only struct rb_augment_callbacks and the prototypes for + * rb_insert_augmented() and rb_erase_augmented() are intended to be public. + * The rest are implementation details you are not expected to depend on. + * + * See Documentation/rbtree.txt for documentation and samples. + */ + +struct rb_augment_callbacks { + void (*propagate)(struct rb_node *node, struct rb_node *stop); + void (*copy)(struct rb_node *old, struct rb_node *new); + void (*rotate)(struct rb_node *old, struct rb_node *new); +}; + +extern void __rb_insert_augmented(struct rb_node *node, struct rb_root *root, + void (*augment_rotate)(struct rb_node *old, struct rb_node *new)); +static inline void +rb_insert_augmented(struct rb_node *node, struct rb_root *root, + const struct rb_augment_callbacks *augment) +{ + __rb_insert_augmented(node, root, augment->rotate); +} + +#define RB_DECLARE_CALLBACKS(rbstatic, rbname, rbstruct, rbfield, \ + rbtype, rbaugmented, rbcompute) \ +static inline void \ +rbname ## _propagate(struct rb_node *rb, struct rb_node *stop) \ +{ \ + while (rb != stop) { \ + rbstruct *node = rb_entry(rb, rbstruct, rbfield); \ + rbtype augmented = rbcompute(node); \ + if (node->rbaugmented == augmented) \ + break; \ + node->rbaugmented = augmented; \ + rb = rb_parent(&node->rbfield); \ + } \ +} \ +static inline void \ +rbname ## _copy(struct rb_node *rb_old, struct rb_node *rb_new) \ +{ \ + rbstruct *old = rb_entry(rb_old, rbstruct, rbfield); \ + rbstruct *new = rb_entry(rb_new, rbstruct, rbfield); \ + new->rbaugmented = old->rbaugmented; \ +} \ +static void \ +rbname ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new) \ +{ \ + rbstruct *old = rb_entry(rb_old, rbstruct, rbfield); \ + rbstruct *new = rb_entry(rb_new, rbstruct, rbfield); \ + new->rbaugmented = old->rbaugmented; \ + old->rbaugmented = rbcompute(old); \ +} \ +rbstatic const struct rb_augment_callbacks rbname = { \ + rbname ## _propagate, rbname ## _copy, rbname ## _rotate \ +}; + + +#define RB_RED 0 +#define RB_BLACK 1 + +#define __rb_parent(pc) ((struct rb_node *)(pc & ~3)) + +#define __rb_color(pc) ((pc) & 1) +#define __rb_is_black(pc) __rb_color(pc) +#define __rb_is_red(pc) (!__rb_color(pc)) +#define rb_color(rb) __rb_color((rb)->__rb_parent_color) +#define rb_is_red(rb) __rb_is_red((rb)->__rb_parent_color) +#define rb_is_black(rb) __rb_is_black((rb)->__rb_parent_color) + +static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) +{ + rb->__rb_parent_color = rb_color(rb) | (unsigned long)p; +} + +static inline void rb_set_parent_color(struct rb_node *rb, + struct rb_node *p, int color) +{ + rb->__rb_parent_color = (unsigned long)p | color; +} + +static inline void +__rb_change_child(struct rb_node *old, struct rb_node *new, + struct rb_node *parent, struct rb_root *root) +{ + if (parent) { + if (parent->rb_left == old) + parent->rb_left = new; + else + parent->rb_right = new; + } else + root->rb_node = new; +} + +extern void __rb_erase_color(struct rb_node *parent, struct rb_root *root, + void (*augment_rotate)(struct rb_node *old, struct rb_node *new)); + +static void +rb_erase_augmented(struct rb_node *node, struct rb_root *root, + const struct rb_augment_callbacks *augment) +{ + struct rb_node *child = node->rb_right, *tmp = node->rb_left; + struct rb_node *parent, *rebalance; + unsigned long pc; + + if (!tmp) { + /* + * Case 1: node to erase has no more than 1 child (easy!) + * + * Note that if there is one child it must be red due to 5) + * and node must be black due to 4). We adjust colors locally + * so as to bypass __rb_erase_color() later on. + */ + pc = node->__rb_parent_color; + parent = __rb_parent(pc); + __rb_change_child(node, child, parent, root); + if (child) { + child->__rb_parent_color = pc; + rebalance = NULL; + } else + rebalance = __rb_is_black(pc) ? parent : NULL; + tmp = parent; + } else if (!child) { + /* Still case 1, but this time the child is node->rb_left */ + tmp->__rb_parent_color = pc = node->__rb_parent_color; + parent = __rb_parent(pc); + __rb_change_child(node, tmp, parent, root); + rebalance = NULL; + tmp = parent; + } else { + struct rb_node *successor = child, *child2; + tmp = child->rb_left; + if (!tmp) { + /* + * Case 2: node's successor is its right child + * + * (n) (s) + * / \ / \ + * (x) (s) -> (x) (c) + * \ + * (c) + */ + parent = successor; + child2 = successor->rb_right; + augment->copy(node, successor); + } else { + /* + * Case 3: node's successor is leftmost under + * node's right child subtree + * + * (n) (s) + * / \ / \ + * (x) (y) -> (x) (y) + * / / + * (p) (p) + * / / + * (s) (c) + * \ + * (c) + */ + do { + parent = successor; + successor = tmp; + tmp = tmp->rb_left; + } while (tmp); + parent->rb_left = child2 = successor->rb_right; + successor->rb_right = child; + rb_set_parent(child, successor); + augment->copy(node, successor); + augment->propagate(parent, successor); + } + + successor->rb_left = tmp = node->rb_left; + rb_set_parent(tmp, successor); + + pc = node->__rb_parent_color; + tmp = __rb_parent(pc); + __rb_change_child(node, successor, tmp, root); + if (child2) { + successor->__rb_parent_color = pc; + rb_set_parent_color(child2, parent, RB_BLACK); + rebalance = NULL; + } else { + unsigned long pc2 = successor->__rb_parent_color; + successor->__rb_parent_color = pc; + rebalance = __rb_is_black(pc2) ? parent : NULL; + } + tmp = successor; + } + + augment->propagate(tmp, NULL); + if (rebalance) + __rb_erase_color(rebalance, root, augment->rotate); +} + +#endif /* _LINUX_RBTREE_AUGMENTED_H */ diff --git a/support/MESA_htable/rb_tree/rbtree_test.c b/support/MESA_htable/rb_tree/rbtree_test.c new file mode 100644 index 0000000..007b7e6 --- /dev/null +++ b/support/MESA_htable/rb_tree/rbtree_test.c @@ -0,0 +1,315 @@ +#include "rbtree.h" +#include "rbtree_augmented.h" +#include <time.h> +#include <stdlib.h> +#include <sys/time.h> + +#define NODES 100 +#define PERF_LOOPS 100000 +#define CHECK_LOOPS 100 + +#ifndef u32 +#define u32 unsigned int +#endif + +struct test_node { + struct rb_node rb; + u32 key; + + /* following fields used for testing augmented rbtree functionality */ + u32 val; + u32 augmented; +}; + +static struct rb_root root = RB_ROOT; +static struct test_node nodes[NODES]; + +static int rnd; + +static void insert(struct test_node *node, struct rb_root *root) +{ + struct rb_node **new = &root->rb_node, *parent = NULL; + u32 newkey = node->key; + struct test_node *in_tree_node; + + while (*new) { + parent = *new; + in_tree_node = rb_entry(parent, struct test_node, rb); + if (newkey < in_tree_node->key){ + new = &parent->rb_left; + }else if(newkey > in_tree_node->key){ + new = &parent->rb_right; + }else{ + return; /* dup key */ + } + } + + rb_link_node(&node->rb, parent, new); + rb_insert_color(&node->rb, root); +} + + +static struct test_node *search(int search_key) +{ + struct rb_node **new = &root.rb_node, *parent = NULL; + struct test_node *in_tree_node; + + while (*new) { + parent = *new; + in_tree_node = rb_entry(parent, struct test_node, rb); + if(search_key == in_tree_node->key){ + return in_tree_node; + } + if (search_key < in_tree_node->key){ + new = &parent->rb_left; + }else{ + new = &parent->rb_right; + } + } + + return NULL; +} + +static inline void __erase(struct test_node *node, struct rb_root *root) +{ + rb_erase(&node->rb, root); +} + +static inline void erase(int erase_key, struct rb_root *root) +{ + struct test_node *erase_node; + + erase_node = search(erase_key); + if(NULL == erase_node){ + abort(); + return; + } + + rb_erase(&erase_node->rb, root); +} + +static inline u32 augment_recompute(struct test_node *node) +{ + u32 max = node->val, child_augmented; + if (node->rb.rb_left) { + child_augmented = rb_entry(node->rb.rb_left, struct test_node, rb)->augmented; + if (max < child_augmented) + max = child_augmented; + } + if (node->rb.rb_right) { + child_augmented = rb_entry(node->rb.rb_right, struct test_node, rb)->augmented; + if (max < child_augmented) + max = child_augmented; + } + return max; +} + +RB_DECLARE_CALLBACKS(static, augment_callbacks, struct test_node, rb,u32, augmented, augment_recompute) + +static void insert_augmented(struct test_node *node, struct rb_root *root) +{ + struct rb_node **new = &root->rb_node, *rb_parent = NULL; + u32 key = node->key; + u32 val = node->val; + struct test_node *parent; + + while (*new) { + rb_parent = *new; + parent = rb_entry(rb_parent, struct test_node, rb); + if (parent->augmented < val) + parent->augmented = val; + if (key < parent->key) + new = &parent->rb.rb_left; + else + new = &parent->rb.rb_right; + } + + node->augmented = val; + rb_link_node(&node->rb, rb_parent, new); + rb_insert_augmented(&node->rb, root, &augment_callbacks); +} + +static void erase_augmented(struct test_node *node, struct rb_root *root) +{ + rb_erase_augmented(&node->rb, root, &augment_callbacks); +} + +static void init(void) +{ + int i; + for (i = 0; i < NODES; i++) { + nodes[i].key = rand(); + nodes[i].val = rand(); + } +} + +static int is_red(struct rb_node *rb) +{ + return !(rb->__rb_parent_color & 1); +} + +static int black_path_count(struct rb_node *rb) +{ + int count; + for (count = 0; rb; rb = rb_parent(rb)) + count += !is_red(rb); + return count; +} + +static void check(int nr_nodes) +{ + struct rb_node *rb; + int count = 0; + int blacks; + u32 prev_key = 0; + + for (rb = rb_first(&root); rb; rb = rb_next(rb)) { + struct test_node *node = rb_entry(rb, struct test_node, rb); + //WARN_ON_ONCE(node->key < prev_key); + //WARN_ON_ONCE(is_red(rb) && (!rb_parent(rb) || is_red(rb_parent(rb)))); + if (!count) + blacks = black_path_count(rb); + else{ + //WARN_ON_ONCE((!rb->rb_left || !rb->rb_right) && blacks != black_path_count(rb)); + } + prev_key = node->key; + count++; + } + //WARN_ON_ONCE(count != nr_nodes); +} + +static void check_augmented(int nr_nodes) +{ + struct rb_node *rb; + + check(nr_nodes); + for (rb = rb_first(&root); rb; rb = rb_next(rb)) { + struct test_node *node = rb_entry(rb, struct test_node, rb); + //WARN_ON_ONCE(node->augmented != augment_recompute(node)); + } +} + +static int rbtree_test_init(void) +{ + int i, j; + time_t time1, time2, time3; + + printf("rbtree testing\n"); + + rnd = random(); + init(); + + time1 = time(NULL); + + for (i = 0; i < PERF_LOOPS; i++) { + for (j = 0; j < NODES; j++) + insert(nodes + j, &root); + for (j = 0; j < NODES; j++) + __erase(nodes + j, &root); + } + + time2 = time(NULL); + time3 = time2 - time1; + + printf(" -> %llu cycles\n", (unsigned long long)time3); + + for (i = 0; i < CHECK_LOOPS; i++) { + init(); + for (j = 0; j < NODES; j++) { + check(j); + insert(nodes + j, &root); + } + for (j = 0; j < NODES; j++) { + check(NODES - j); + __erase(nodes + j, &root); + } + check(0); + } + + printf("augmented rbtree testing\n"); + + init(); + + time1 = time(NULL); + + for (i = 0; i < PERF_LOOPS; i++) { + for (j = 0; j < NODES; j++) + insert_augmented(nodes + j, &root); + for (j = 0; j < NODES; j++) + erase_augmented(nodes + j, &root); + } + + time2 = time(NULL); + time3 = time2 - time1; + + //time3 = div_u64(time, PERF_LOOPS); + printf(" -> %llu cycles\n", (unsigned long long)time3); + + for (i = 0; i < CHECK_LOOPS; i++) { + init(); + for (j = 0; j < NODES; j++) { + check_augmented(j); + insert_augmented(nodes + j, &root); + } + for (j = 0; j < NODES; j++) { + check_augmented(NODES - j); + erase_augmented(nodes + j, &root); + } + check_augmented(0); + } + + return 0; /* Fail will directly unload the module */ +} + +int main(void) +{ +#define OP_NUM (1000000) + + int i; + struct test_node *node; + struct timeval begin_time, end_time; + + srand(time(NULL)); + + //rbtree_test_init(); + + struct test_node *new_nodes = calloc(OP_NUM, sizeof(struct test_node)); + + for(i = 0; i < OP_NUM; i++){ + new_nodes[i].key = i; + new_nodes[i].val = i; + } + +gettimeofday(&begin_time, NULL); + + for( i = 0; i < OP_NUM; i++){ + insert(&new_nodes[i], &root); + } +gettimeofday(&end_time, NULL); + +printf("insert use time in ms:%lld\n", (end_time.tv_sec * 1000 + end_time.tv_usec/1000) - (begin_time.tv_sec * 1000 + begin_time.tv_usec/1000) ); + +gettimeofday(&begin_time, NULL); + for(i = OP_NUM - 1 ; i >= 0 ; i--){ + node = search(i); + if(NULL == node){ + printf("not found key=1!\n"); + abort(); + }else{ + //printf("bingo! key =1\n"); + } + } +gettimeofday(&end_time, NULL); +printf("search use time in ms:%lld\n", (end_time.tv_sec * 1000 + end_time.tv_usec/1000) - (begin_time.tv_sec * 1000 + begin_time.tv_usec/1000) ); + + + +gettimeofday(&begin_time, NULL); + for(i = 0 ; i < OP_NUM; i++){ + erase(i,&root); + } +gettimeofday(&end_time, NULL); +printf("erase use time in ms:%lld\n", (end_time.tv_sec * 1000 + end_time.tv_usec/1000) - (begin_time.tv_sec * 1000 + begin_time.tv_usec/1000) ); + return 0; +} + diff --git a/support/MESA_htable/readme_GBK.txt b/support/MESA_htable/readme_GBK.txt new file mode 100644 index 0000000..834bbf2 --- /dev/null +++ b/support/MESA_htable/readme_GBK.txt @@ -0,0 +1,143 @@ +/* + ͨ��HASH��������������ʵ��. + ʹ�÷�ʽ���.h���ܼ�./example��ʾ������. + +History: + +************************************************************************ +2014-01-27, LiJia, +����ΪMESA_hash_v3�汾. + (1)����ģ��汾�ű�ʶ, ʹ����������鿴: + nm libMESA_hash_v3.a | grep version + (2)����HASH���ṹ, �Ե����߲���, �ڲ�����ʱ(��ṹ��������һ������), �û�������.h��Դ����; + (3)��MESA_htable_create()�������ݷ�ʽ, ����MESA_hash_create_args_t�ṹ, + ���������һ������, ��������ʱû�и���ԭ.h�ļ�, ���²�������Ĭ��ֵ, ����ǿ�ƴ��±���. + (4)MESA_htable_search_cb()�Ⱥ�����"_r"��, ����reentrant��,������ݹ���ð汾, + ��: + ���̰߳�ȫģʽ��, + ����MESA_htable_search_cb()��MESA_hash_iterate_v3_r()�Ⱥ�����, + ��ֱ���ٴε���MESA_htable_del()��ijHASH�ڵ��HASH��ɾ��. +************************************************************************ +2014-03-25, LiJia, + ����ڶ���ġ������¹���, �ӿ���ԭ�а汾��һ��, ������ɷ��ű���ͻ, + �����°汾�������˰汾��, _v2, _v3��, ʹ�ò���. + ����Ŀǰ��������������, ����ṹ�����ȶ�, �˰汾ʹ����������, ����ʹ�ð汾������. +************************************************************************ +2014-04-03, LiJia, + 1)�Ĵ����ṹ��MESA_hash_create_args_t->data_expire���������� + ԭ��: void (*data_expire)(void *data); + �°�: int (*data_expire_with_condition)(void *data, int type); + + ԭ���expire����ֻ��Ϊ֪ͨʹ�ã���֮ʹ���ߣ���Ԫ�ؼ�����������봦����������������; + + �°�expire_with_condition��������ԭ�������ϣ���֮ʹ��������Ϊʲôԭ����̭�����Ҽ�鷵��ֵ�� + ����0 : ��Ԫ�ز��ܱ���̭�������洢; + ����1 : ��Ԫ�ؿ��Ա���̭; + + 2)���������v3�汾��ͬ��Ϊ�˱����ͻ����MESA_hash_handle��Ϊ MESA_htable_handle�� +************************************************************************ +2014-04-04,LiJia + 1)��hash_cb_t�ص������ӿڣ� + ����ֵ����Ϊlong, ��������߷���ָ�����ͱ���(��ǿ������ת��); + ���Ӳ���key��size�������������cb�����У������ٵ���MESA_htable_add��MESA_htable_del�Ⱥ���; + +************************************************************************ +2014-04-18,LiJia + 1)��common_list�ļ���ΪMESA_list���ĺ����������ƣ���ֹ��MESA_hash��MESA_hash_v2�汾����ʱ, ������ͻ����. + +************************************************************************ +2014-06-04,LiJia + 1)�������ģ���һЩ�����������const����. + +************************************************************************ +2014-07-07,LiJia + 1)���̰߳�ȫģʽ�£�ֱ��ʹ��MESA_htable_search()���ص�ָ���Ǻ�Σ�յģ� + �����ⲿ�����������б�֤�̰߳�ȫ, ��������Ȼ���ӡ������Ϣ�� + ���ȷ��û�����⣬���Ե���MESA_htable_print_crtl()�رվ�����Ϣ�� + +************************************************************************ +2014-07-10,LiJia + ����MESA_lqueue_try_read_head()ʵ��. +************************************************************************ +2014-07-15,LiJia + ����(�ָ�ԭlist_v3����)�� + MESA_q_join_list_p()�� + MESA_q_join_list_n(), + MESA_q_read_next() +************************************************************************ +2014-07-17,LiJia + 1)��MESA_lqueue_read_head()ʵ�ֻ���, + 2)�����ǰ����Ԫ��Ϊ��, �������ȴ�, ֱ������Ԫ�ر�����. +************************************************************************ +2014-09-03,LiJia + 1)����complex_key֧�֣�����ǿ��Ҫ��key����Ϊ�������ڴ棬��key������һ�����ӵĽṹ��,ʹ�ô�����ʱ�������߱�������ʵ��complex_key_dup()��complex_key_free()����; + 2)����MESA_htable_del_oldest_manual()�����������߿��ֶ�ɾ��"���δʹ��"��Ԫ�أ�������ȴ�HASH��Ԫ�س�ʱ��ﵽ�����������. + +************************************************************************ +2014-09-12,LiJia + 1)�ı���ʱ����callback����ɾ��Ԫ�ص�BUG; +************************************************************************ +2014-09-24,LiJia + 1)�°����ʱ����ʹ�ú궨�忪��ijЩ�������ܺͽӿڣ���������������Զ��жϣ�����������; +************************************************************************ +2015-01-05,LiJia + 1)���Ӹ���ʱ���߳�, ����ÿ��HASH����������time(NULL),�������. +************************************************************************ +2015-03-20,LiJia + 1)����MESA_htable_iterate_bytime()����. +************************************************************************ +2015-04-22,LiJia + 1)��MESA_list_queue����ֵȫ��-1��BUG. +************************************************************************ +2015-05-13 LiJia +1)����ʱδʹ��ע���complex_key_free()����,ʹ����Ĭ�ϵ�free(),����ڴ�й¶. +************************************************************************ +2015-07-17 LiJia +1)�����궨��"PTHREAD_MUTEX_RECURSIVE"��ϵͳ�汾��һ�£�����������. + +************************************************************************ +2016-01-27 LiJia +1)���ӱ����-D_XOPEN_SOURCE=500, �����ijЩ�Ͼ�linuxϵͳ�ϵı������ +2)�ָ�2015-01-05ʱ���ӵĺ�̨�Զ�����ʱ���̹߳���, ����Ϊѡ��, ��Ӧ�����п����Ƿ���. + +************************************************************************ +2016-02-24 LiJia +1)�����½ӿ�MESA_htable_born, MESA_htable_set_opt, MESA_htable_mature, + ���������¹��ܺ�, �Կ�������. +************************************************************************ +2016-03-04 LiJia +1)����MESA_ring_queue, Ԥ�ȷ����ڴ棬��ȥÿ�β��룬ȡ��Ԫ�ض���Ҫmalloc/free������������ܡ� + +************************************************************************ +2016-03-08 LiJia +1)����MESA_lqueue_strerror�Ⱥ��������������ת��Ϊ�ɶ����ַ�����ʽ�� +************************************************************************ +2016-03-16 LiJia +1)������ϸ�IJ��������顣 +************************************************************************ +2016-03-23 LiJia +1)MESA_htable_search_cb()��������cb����ΪNULLʱ�������������У�����ӡ������ʾ�� +************************************************************************ +2016-03-24 LiJia +1)���Ӳ�����ϺϷ��Ժͷ��ռ�飬����thread=0��eliminate_type=1���ڶ��߳�ģʽ������ʱ�ͻ����ڴ���ҷ��ա� +************************************************************************ +2016-11-30 LiJia +1)����HASH������ͻ��־, ��ʾ�ⲿ�����߿��ܴ�������ƿ������ͨ��MESA_htable_set_opt()���ü�¼��־����ֵ���ļ�·��. +************************************************************************ +2016-12-05 LiJia +1)���Ӻ궨��MESA_HTABLE_VERSION_MACRO, MESA_LIST_QUEUE_VERSION_MACRO�ȣ����ڱ���ʱʹ��#ifdef, #if���ƴ�����, + �����������Ͱ汾��MESA_HTABLE_VERSION_INT, MESA_LIST_QUEUE_VERSION_INT��, ��ֹ��ʹ�����¹��ܡ��½ӿ�, �Ѿ��������, + ��ij̨������������Ǿɰ汾.so, �������ʱ����. +************************************************************************ +2016-12-30 LiJia +1)��ʹ��MESA_htable_born()�½ӿڴ����ľ��, ��ͬʱʹ����key_dup�ص�����ʱ, �����ڴ�й©��BUG. + +********************************************************************* +************************* 2017 year ********************************* +********************************************************************* + +2017-01-04 LiJia +1)���ӳ�ͻ��LRU����, ��һ���̶��ϼ���ƽ�����Ҵ���; +2)����ѡ��MHO_HASH_SEARCH_MAX_TIMES, MHO_HASH_SEARCH_AVG_TIMES, ���ڻ�ȡ�����Ҵ�����ƽ�����Ҵ���, + ���ڵ���������ʹ��htable��ʵ������. +*/
\ No newline at end of file diff --git a/support/MESA_htable/readme_UTF8.txt b/support/MESA_htable/readme_UTF8.txt new file mode 100644 index 0000000..6b8c321 --- /dev/null +++ b/support/MESA_htable/readme_UTF8.txt @@ -0,0 +1,143 @@ +/* + 通用HASH表、链表、队列实现. + 使用方式详见.h介绍及./example中示例程序. + +History: + +************************************************************************ +2014-01-27, LiJia, +升级为MESA_hash_v3版本. + (1)增加模块版本号标识, 使用如下命令查看: + nm libMESA_hash_v3.a | grep version + (2)隐藏HASH表结构, 对调用者不透明, 内部升级时(如结构体中新增一个变量), 用户无需修改.h及源代码; + (3)修改MESA_htable_create()参数传递方式, 新增MESA_hash_create_args_t结构, + 如果新增了一个参数, 调用者暂时没有更新原.h文件, 则新参数采用默认值, 无需强制从新编译. + (4)MESA_htable_search_cb()等函数追加"_r"后缀, 即“reentrant”,可重入递归调用版本, + 例: + 在线程安全模式下, + 进入MESA_htable_search_cb()、MESA_hash_iterate_v3_r()等函数中, + 可直接再次调用MESA_htable_del()将某HASH节点从HASH表删除. +************************************************************************ +2014-03-25, LiJia, + 因近期多次修改、添加新功能, 接口与原有版本不一致, 容易造成符号表冲突, + 所以新版本都增加了版本后缀, _v2, _v3等, 使用不便. + 鉴于目前各项功能已添加完毕, 整体结构趋于稳定, 此版本使用了新名字, 不再使用版本号区分. +************************************************************************ +2014-04-03, LiJia, + 1)修改创建结构体MESA_hash_create_args_t->data_expire参数及类型 + 原版: void (*data_expire)(void *data); + 新版: int (*data_expire_with_condition)(void *data, int type); + + 原版的expire函数只做为通知使用,告之使用者,此元素即将被清除,请处理,别无其他作用; + + 新版expire_with_condition函数,在原来基础上,告之使用者是因为什么原因被淘汰,并且检查返回值, + 返回0 : 此元素不能被淘汰,继续存储; + 返回1 : 此元素可以被淘汰; + + 2)句柄名称与v3版本相同,为了避免冲突,将MESA_hash_handle改为 MESA_htable_handle。 +************************************************************************ +2014-04-04,LiJia + 1)修改hash_cb_t回调函数接口, + 返回值类型为long, 方便调用者返回指针类型变量(需强制类型转换); + 增加参数key和size,方便调用者在cb函数中,可以再调用MESA_htable_add、MESA_htable_del等函数; + +************************************************************************ +2014-04-18,LiJia + 1)修改common_list文件名为MESA_list、修改函数类型名称,防止与MESA_hash、MESA_hash_v2版本共存时, 命名冲突问题. + +************************************************************************ +2014-06-04,LiJia + 1)无功能性修改,给一些输入变量增加const修饰. + +************************************************************************ +2014-07-07,LiJia + 1)在线程安全模式下,直接使用MESA_htable_search()返回的指针是很危险的, + 除非外部调用者能自行保证线程安全, 但本库仍然会打印警告信息, + 如果确认没有问题,可以调用MESA_htable_print_crtl()关闭警告信息。 + +************************************************************************ +2014-07-10,LiJia + 增加MESA_lqueue_try_read_head()实现. +************************************************************************ +2014-07-15,LiJia + 增加(恢复原list_v3功能), + MESA_q_join_list_p(), + MESA_q_join_list_n(), + MESA_q_read_next() +************************************************************************ +2014-07-17,LiJia + 1)修改MESA_lqueue_read_head()实现机制, + 2)如果当前队列元素为空, 则阻塞等待, 直到有新元素被添加. +************************************************************************ +2014-09-03,LiJia + 1)增加complex_key支持,不再强制要求key必须为连续的内存,即key可以是一个复杂的结构体,使用此特性时,调用者必须自行实现complex_key_dup()和complex_key_free()函数; + 2)增加MESA_htable_del_oldest_manual()函数,调用者可手动删除"最久未使用"的元素,而无需等待HASH表元素超时或达到最大数量限制. + +************************************************************************ +2014-09-12,LiJia + 1)修改遍历时调用callback函数删除元素的BUG; +************************************************************************ +2014-09-24,LiJia + 1)新版更新时不再使用宏定义开启某些新增功能和接口,靠传入参数长度自动判断,方便向后兼容; +************************************************************************ +2015-01-05,LiJia + 1)增加更新时间线程, 避免每次HASH操作都调用time(NULL),提高性能. +************************************************************************ +2015-03-20,LiJia + 1)增加MESA_htable_iterate_bytime()函数. +************************************************************************ +2015-04-22,LiJia + 1)修改MESA_list_queue错误返回值全是-1的BUG. +************************************************************************ +2015-05-13 LiJia +1)销毁时未使用注册的complex_key_free()函数,使用了默认的free(),造成内存泄露. +************************************************************************ +2015-07-17 LiJia +1)解决因宏定义"PTHREAD_MUTEX_RECURSIVE"因系统版本不一致,无法编译问题. + +************************************************************************ +2016-01-27 LiJia +1)增加编译宏-D_XOPEN_SOURCE=500, 解决在某些老旧linux系统上的编译错误。 +2)恢复2015-01-05时增加的后台自动更新时间线程功能, 但做为选项, 由应用自行控制是否开启. + +************************************************************************ +2016-02-24 LiJia +1)增加新接口MESA_htable_born, MESA_htable_set_opt, MESA_htable_mature, + 用于增加新功能后, 仍可向后兼容. +************************************************************************ +2016-03-04 LiJia +1)新增MESA_ring_queue, 预先分配内存,免去每次插入,取出元素都需要malloc/free操作,提高性能。 + +************************************************************************ +2016-03-08 LiJia +1)增加MESA_lqueue_strerror等函数,将错误代码转换为可读的字符串形式。 +************************************************************************ +2016-03-16 LiJia +1)增加详细的参数错误检查。 +************************************************************************ +2016-03-23 LiJia +1)MESA_htable_search_cb()函数,当cb参数为NULL时,允许继续运行,但打印警告提示。 +************************************************************************ +2016-03-24 LiJia +1)增加参数组合合法性和风险检查,比如thread=0且eliminate_type=1,在多线程模式下运行时就会有内存混乱风险。 +************************************************************************ +2016-11-30 LiJia +1)增加HASH链表冲突日志, 提示外部调用者可能存在性能瓶颈,可通过MESA_htable_set_opt()设置记录日志的阈值和文件路径. +************************************************************************ +2016-12-05 LiJia +1)增加宏定义MESA_HTABLE_VERSION_MACRO, MESA_LIST_QUEUE_VERSION_MACRO等,便于编译时使用#ifdef, #if控制代码逻辑, + 增加数字类型版本号MESA_HTABLE_VERSION_INT, MESA_LIST_QUEUE_VERSION_INT等, 防止因使用了新功能、新接口, 已经编译完成, + 但某台服务器部署的是旧版本.so, 造成运行时错误. +************************************************************************ +2016-12-30 LiJia +1)修改使用MESA_htable_born()新接口创建的句柄, 且同时使用了key_dup回调函数时, 会有内存泄漏的BUG. + +********************************************************************* +************************* 2017 year ********************************* +********************************************************************* + +2017-01-04 LiJia +1)增加冲突链LRU机制, 在一定程度上减少平均查找次数; +2)增加选项MHO_HASH_SEARCH_MAX_TIMES, MHO_HASH_SEARCH_AVG_TIMES, 用于获取最大查找次数和平均查找次数, + 便于调用者评估使用htable的实际性能. +*/
\ No newline at end of file diff --git a/support/MESA_htable/src/MESA_htable.c b/support/MESA_htable/src/MESA_htable.c new file mode 100644 index 0000000..3252516 --- /dev/null +++ b/support/MESA_htable/src/MESA_htable.c @@ -0,0 +1,2203 @@ +#include <stdio.h> +#include <time.h> +#include <unistd.h> +#include <pthread.h> +#include <assert.h> +#include <linux/limits.h> +#include <sys/types.h> +#include <sys/stat.h> +#include <unistd.h> +#include <execinfo.h> +#include "MESA_htable.h" +#include "MESA_list_queue.h" +#include "MESA_list_count.h" +#include "MESA_htable_internal.h" +#include "MESA_atomic.h" + + + +#define N 999 + +#ifdef __cplusplus +extern "C" +{ +#endif + +#if MESA_HASH_DEBUG +#define HASH_INLINE +#else +#define HASH_INLINE inline +#endif + +const char *MESA_htable_version_VERSION_20170104 = "MESA_htable_version_VERSION_20170104"; + +const unsigned int MESA_HTABLE_VERSION_INT = 20170104; + +#define MESA_HASH_LIST_COLLIDE_DETECT (1) + +/* 2014-09-24 lijia add, ������������ */ +#define HARGS_BASE_LEN (56) /* ����data_expire_with_condition, ��COMPLEX_KEY_SWITCH */ +#define HARGS_COMPLEX_KEY_LEN (72) /* COMPLEX_KEY_SWITCH������ */ + +#define HTABLE_INNER_BASE_LEN (88) /* MESA_htable_inner_t �ڲ��ṹ���� */ +#define HTABLE_INNER_PRINT_SW_LEN (96) /* MESA_htable_inner_t, ����print_switch */ +#define HTABLE_INNER_COMPLEX_KEY_LEN (112) /* MESA_htable_inner_t, ����complex_key */ + +#define THREAD_PID_INIT1 ((pthread_t)0) +#define THREAD_PID_INIT2 ((pthread_t)~0) + +#define MHT_PRINT(table, format, args...) do{if(((MESA_htable_inner_t *)table)->print_switch){fprintf(stderr, format, ##args);}}while(0) + +const char *__MH_htable_runtime_log = "htable_runtime.log"; + +/* + �����ܼ�������ͻ��ÿN��Hash-slot����һ��������, + (HASH_Index % HASH_TABLE_MUTEX_NUM)��ֵ��ͬ��item����һ��mutex. + + ͨ������֤��, ����������������1024��, ���������������, �������ֵΪ1024. +*/ +#define HASH_TABLE_MUTEX_NUM (1024) + + + +/* + * hash element structure. + * + * key : a copy of key; + * size: size of key; + * hash_index: index which use this key and key2index_fun_t() calculated; + * data: pointer to attached data; + * prev, next: pointer to prev and next item; + */ +typedef struct struct_hash_elem { + uchar *key; + void *data; + uint size; /* size of key */ + uint hash_index; + time_t op_time; + struct struct_hash_elem *prev; + struct struct_hash_elem *next; + MESA_list_count_t list_node; +} htable_elem_t; + + +typedef struct{ + int opt_switch; /* �Ƿ��� */ + volatile time_t current_time; + pthread_t timer_thread_pid; +}htable_opt_time_t; + + +typedef struct{ + int max_item_search_times; /* ������ͻ�������������(����) */ + long long total_api_search_times; /* �ⲿ�����ܼƵ���MESA_htable_search()�Ĵ��� */ + long long total_item_search_times; /* �ⲿ��������ʱ, ����������ͻ������ܼƲ���Ԫ�ش��� */ +}htable_search_status_t; + +/* + * hash structure. + * + * size: number of slots; + * key_comp: pointer to the function that compares 2 keys; + * key2index: pointer to the function that computes index from key; + * expire: pointer to the function that do somthing when data expired; + * free: pointer to the function that cleans up attached data; + * elems: array of slots; + * elem_count: number of items; + * threshold_lo, threshold_hi: low and high threshold; when elem_count reaches + * one of them, an iteration will be launched to clean up expired items; + */ +typedef struct { + uint size; + uint thread_safe; + int recursive; + union{ + volatile uint elem_count_unsafe; + volatile MESA_ATOMIC_T elem_count_safe; + }; + key_comp_fun_t * key_comp; + key2index_fun_t * key2index; + int (* expire)(void * data, int type); + void (* free)(void * data); + htable_elem_t ** elems; + unsigned int max_elem_num; + int eliminate_type; + int expire_time; + int print_switch; + pthread_mutex_t *htable_mutex; + MESA_list_count_t *hlist_head; + uchar* (*complex_key_dup)(const uchar *key, uint key_size); + void (* complex_key_free)(uchar *key, uint key_size); + int caller_hargs_len; + int create_type; /* 0:init; 1:by MESA_htable_create(); 2:by MESA_htable_born(); */ + int mutex_num; + int is_running; /* htable����MESA_htable_mature֮��, is_running=1, �������ٵ���MESA_htable_set_opt() */ + void *htable_option[__MHO_MAX_VAL]; /* 2016-01-27 lijia add, �����¹���ʹ��ѡ��, ��ȷ����ʲôѡ������, ʹ��void *�洢 */ + unsigned short *hash_bucket_item_num; /* ÿ��bucket�´洢��item����, ���ʹ������, ��hash��ͻ���� */ + int hash_list_collide_threshold; /* hash list number������ֵ��д������־�ļ�, Ĭ��100 */ + htable_search_status_t hash_search_status; + const char *htable_runtime_log; /* htable��־�ļ���, malloc���ڴ�, destroyʱҪfree. */ +} MESA_htable_inner_t; + + +enum htable_create_type +{ + HTABLE_CREATE_TYPE_ORIGINAL = 1, + HTABLE_CREATE_TYPE_BORN = 2, /* 2016-01-31 lijia add new API */ +}; + +typedef struct{ + enum MESA_htable_opt opt_type; + int (*MESA_htable_set_opt_fun)(MESA_htable_handle table, enum MESA_htable_opt opt_type, void *opt_val, int opt_len); + int (*MESA_htable_get_opt_fun)(MESA_htable_handle table, enum MESA_htable_opt opt_type, void *opt_val, int *opt_len); + /* ��Ҫ�����������ѡ������, ���Զ�����ʱ�书��, Ҫ��̨������һ���߳� */ + int (*MESA_htable_process_opt_fun)(MESA_htable_handle table); + void (*MESA_htable_free_opt_fun)(MESA_htable_inner_t *table); +}MESA_opt_manage_t; + +#if MESA_HASH_LIST_COLLIDE_DETECT +static char backtrace_print_buf[4096]; +static int __MH_exec_shell(const char*cmd ,char* buff,int buff_size) +{ + FILE* fp = popen(cmd, "r"); + if(fp==NULL) + { + return -1; + } + memset(buff,0,buff_size); + fgets(buff,buff_size,fp); + pclose(fp); + return strlen(buff); +} + +static int __MH_get_backtrace_string(void* bt,char* buff,int buff_size) +{ + char cmd[128] = {0}; + char property[256]={0}; + char not_care1[128]={0},not_care2[128]={0},not_care3[128]={0}; + char library_path[256]={0}; + char exe_path[256]={0},function_name[256]={0}; + char maps_line[1024]={0}; + void* offset_start,*offset_end; + int ret , maps_column_num=0; + FILE* fd_maps=NULL; + fd_maps=fopen("/proc/self/maps","r"); + unsigned long exe_symbol_offset=0; + const char* unknow_position="??:0\n"; + if(fd_maps==NULL) + { + return -1; + } + while(NULL!=fgets(maps_line,sizeof(maps_line),fd_maps)) + { + maps_column_num=sscanf(maps_line,"%p-%p\t%s\t%s\t%s\t%s\t%s" + ,&offset_start + ,&offset_end + ,property + ,not_care1 + ,not_care2 + ,not_care3 + ,library_path); + if(maps_column_num==7&&bt>=offset_start&&bt<=offset_end) + { + break; + } + + } + fclose(fd_maps); + memset(exe_path,0,sizeof(exe_path)); + readlink("/proc/self/exe", exe_path, sizeof(exe_path)); + if(exe_path[strlen(exe_path)-1]=='\n') + { + exe_path[strlen(exe_path)-1]='\0'; + } + if(0==strcmp(exe_path,library_path)) + { + exe_symbol_offset=(unsigned long)bt; + } + else + { + exe_symbol_offset=(char*)bt-(char*)offset_start; + } + snprintf(cmd,sizeof(cmd),"addr2line -C -e %s 0x%lx",library_path,exe_symbol_offset); + ret = __MH_exec_shell(cmd, buff, buff_size); + if(ret < 0){ + return -1; + } + if(0==strcmp(buff,unknow_position)) + { + snprintf(cmd,sizeof(cmd),"addr2line -Cif -e %s 0x%lx",library_path,exe_symbol_offset); + ret = __MH_exec_shell(cmd, function_name, sizeof(function_name)); + if(ret < 0){ + return -1; + } + function_name[strlen(function_name)-1]='\0'; + snprintf(buff,buff_size,"%s(%s+0x%lx)\n",library_path,function_name,exe_symbol_offset); + } + return 0; +} +static void __MH_backtrace_print(MESA_htable_inner_t *table, int hlist_collide_num) +{ +#define SIZE 32 + int ret, j, nptrs; + FILE *fp; + void *buffer[SIZE]; + char **strings; + nptrs = backtrace(buffer, SIZE); + + /* The call backtrace_symbols_fd(buffer, nptrs, STDOUT_FILENO) + * would produce similar output to the following: */ + + strings = backtrace_symbols(buffer, nptrs); + if (strings == NULL) { + return; + } + + fp = fopen(table->htable_runtime_log, "a+"); + if(NULL == fp){ + return; + } + + fprintf(fp, "--------------In this functions stack, hlist collide number:%d------------\n", hlist_collide_num); + for (j = 0; j < nptrs; j++){ + //fprintf(fp, "%s\n", strings[j]); + ret = __MH_get_backtrace_string(buffer[j], backtrace_print_buf, 4096); + if(ret < 0){ + continue; + } + fprintf(fp, "%s", backtrace_print_buf); + } + fprintf(fp, "----------------------------------------------------------------------\n"); + + free(strings); + fclose(fp); +} +#endif + +static int __MHO_set_opt_thread_safe(MESA_htable_handle apitable, enum MESA_htable_opt opt_type, void *opt_val, int opt_len) +{ + MESA_htable_inner_t *table; + + if(opt_len != sizeof(int)){ + return -1; + } + + table = (MESA_htable_inner_t *)apitable; + + table->thread_safe = *((unsigned int *)opt_val); + + if(0 == table->thread_safe){ + table->mutex_num = 0; /* ���̰߳�ȫģʽ��, ��������������Ϊ0, ��Ϊ__MESA_htable_set_default_opt()��Ĭ����Ϊ1 */ + } + + return 0; +} + + +static int __MHO_set_opt_mutex_num(MESA_htable_handle apitable, enum MESA_htable_opt opt_type, void *opt_val, int opt_len) +{ + MESA_htable_inner_t *table; + + if(opt_len != sizeof(int)){ + return -1; + } + + table = (MESA_htable_inner_t *)apitable; + + if(*((int *)opt_val) <= 0){ + printf("Error!Hash mutex number must bigger than zero!\n"); + return -1; + } + + table->mutex_num = *((int *)opt_val); + if(table->mutex_num > HASH_TABLE_MUTEX_NUM){ + printf("Warning! Max hash mutex num is:%d\n", HASH_TABLE_MUTEX_NUM); + table->mutex_num = HASH_TABLE_MUTEX_NUM; + } + + return 0; +} + +static int __MHO_set_opt_slot_size(MESA_htable_handle apitable, enum MESA_htable_opt opt_type, void *opt_val, int opt_len) +{ + MESA_htable_inner_t *table; + + if(opt_len != sizeof(int)){ + return -1; + } + + table = (MESA_htable_inner_t *)apitable; + + table->size = *((unsigned int *)opt_val); + + if(table->size < 1024){ + printf("Warning! Hash slot size is:%u, maybe more colliding!\n", table->size); + } + + return 0; +} + +static int __MHO_set_opt_max_ele_num(MESA_htable_handle apitable, enum MESA_htable_opt opt_type, void *opt_val, int opt_len) +{ + MESA_htable_inner_t *table; + + if(opt_len != sizeof(int)){ + return -1; + } + + table = (MESA_htable_inner_t *)apitable; + + table->max_elem_num = *((unsigned int *)opt_val); + + return 0; +} + +static int __MHO_set_opt_expire_time(MESA_htable_handle apitable, enum MESA_htable_opt opt_type, void *opt_val, int opt_len) +{ + MESA_htable_inner_t *table; + + if(opt_len != sizeof(int)){ + return -1; + } + + table = (MESA_htable_inner_t *)apitable; + + table->expire_time = *((int *)opt_val); + + return 0; +} + +static int __MHO_set_opt_expire_type(MESA_htable_handle apitable, enum MESA_htable_opt opt_type, void *opt_val, int opt_len) +{ + MESA_htable_inner_t *table; + + if(opt_len != sizeof(int)){ + return -1; + } + + table = (MESA_htable_inner_t *)apitable; + + table->eliminate_type = *((int *)opt_val); + + if((HASH_ELIMINATE_ALGO_FIFO != table->eliminate_type) + && (HASH_ELIMINATE_ALGO_LRU != table->eliminate_type)){ + printf("Error! Hash eliminate type invalid: %d\n", table->eliminate_type); + return -1; + } + + return 0; +} + +static int __MHO_set_opt_key_compare(MESA_htable_handle apitable, enum MESA_htable_opt opt_type, void *opt_val, int opt_len) +{ + MESA_htable_inner_t *table; + + if(opt_len != sizeof(void *)){ + return -1; + } + + table = (MESA_htable_inner_t *)apitable; + + table->key_comp = opt_val; + + return 0; +} + +static int __MHO_set_opt_key2index(MESA_htable_handle apitable, enum MESA_htable_opt opt_type, void *opt_val, int opt_len) +{ + MESA_htable_inner_t *table; + + if(opt_len != sizeof(void *)){ + return -1; + } + + table = (MESA_htable_inner_t *)apitable; + + table->key2index = opt_val; + + return 0; +} + +static int __MHO_set_opt_data_free(MESA_htable_handle apitable, enum MESA_htable_opt opt_type, void *opt_val, int opt_len) +{ + MESA_htable_inner_t *table; + + if(opt_len != sizeof(void *)){ + return -1; + } + + table = (MESA_htable_inner_t *)apitable; + + table->free = opt_val; + + return 0; +} + +static int __MHO_set_opt_expire_notify(MESA_htable_handle apitable, enum MESA_htable_opt opt_type, void *opt_val, int opt_len) +{ + MESA_htable_inner_t *table; + + if(opt_len != sizeof(void *)){ + return -1; + } + + table = (MESA_htable_inner_t *)apitable; + + table->expire = opt_val; + + return 0; +} + +static int __MHO_set_opt_key_dup(MESA_htable_handle apitable, enum MESA_htable_opt opt_type, void *opt_val, int opt_len) +{ + MESA_htable_inner_t *table; + + if(opt_len != sizeof(void *)){ + return -1; + } + + table = (MESA_htable_inner_t *)apitable; + + table->complex_key_dup = opt_val; + + return 0; +} + +static int __MHO_set_opt_key_free(MESA_htable_handle apitable, enum MESA_htable_opt opt_type, void *opt_val, int opt_len) +{ + MESA_htable_inner_t *table; + + if(opt_len != sizeof(void *)){ + return -1; + } + + table = (MESA_htable_inner_t *)apitable; + + table->complex_key_free = opt_val; + + return 0; +} + +static int __MHO_set_opt_auto_update_time(MESA_htable_handle apitable, enum MESA_htable_opt opt_type, void *opt_val, int opt_len) +{ + MESA_htable_inner_t *table; + htable_opt_time_t *time_opt; + + if(opt_len != sizeof(int)){ + return -1; + } + + table = (MESA_htable_inner_t *)apitable; + + if(*((int *)opt_val) != 0){ + time_opt = table->htable_option[MHO_AUTO_UPDATE_TIME]; + time_opt = (htable_opt_time_t *)HASH_MALLOC(sizeof(htable_opt_time_t)); + memset(time_opt, 0, sizeof(htable_opt_time_t)); + time_opt->opt_switch = *((int *)opt_val); + table->htable_option[MHO_AUTO_UPDATE_TIME] = time_opt; + }else{ + table->htable_option[MHO_AUTO_UPDATE_TIME] = NULL; + } + + return 0; +} + +static int __MHO_set_opt_screen_print(MESA_htable_handle apitable, enum MESA_htable_opt opt_type, void *opt_val, int opt_len) +{ + MESA_htable_inner_t *table; + + if(opt_len != sizeof(int)){ + return -1; + } + + table = (MESA_htable_inner_t *)apitable; + + table->print_switch = *((int *)opt_val); + + return 0; +} + +static int __MHO_set_opt_collide_threshold(MESA_htable_handle apitable, enum MESA_htable_opt opt_type, void *opt_val, int opt_len) +{ + MESA_htable_inner_t *table; + + if(opt_len != sizeof(int)){ + return -1; + } + + table = (MESA_htable_inner_t *)apitable; + + table->hash_list_collide_threshold = *((int *)opt_val); + + return 0; +} + +static int __MHO_set_opt_runtime_log(MESA_htable_handle apitable, enum MESA_htable_opt opt_type, void *opt_val, int opt_len) +{ + MESA_htable_inner_t *table; + + table = (MESA_htable_inner_t *)apitable; + + if(table->htable_runtime_log != NULL){ + table->htable_runtime_log = (const char *)realloc((void *)table->htable_runtime_log, opt_len + 1); + }else{ + table->htable_runtime_log = (const char *)malloc(opt_len + 1); + } + + memcpy((void *)table->htable_runtime_log, opt_val, opt_len + 1); + + return 0; +} + +static void *__MESA_htable_update_time(void *arg) +{ + htable_opt_time_t *time_opt = (htable_opt_time_t *)arg; + + while(1){ + if(unlikely(time_opt->current_time < time(NULL))){ + time_opt->current_time = time(NULL); + } + usleep(1000 * 10); + } + + return NULL; +} + +static int __MHO_proc_opt_mutex_num(MESA_htable_handle apitable) +{ + int i, ret = 0; + MESA_htable_inner_t *table; + pthread_mutexattr_t attr; + int attr_type; + + table = (MESA_htable_inner_t *)apitable; + + if(table->mutex_num > 0){ + table->htable_mutex = (pthread_mutex_t *)HASH_MALLOC(sizeof(pthread_mutex_t) * table->mutex_num); + + for(i = 0; i < table->mutex_num; i++){ + pthread_mutexattr_init(&attr); + pthread_mutexattr_gettype(&attr, &attr_type); + attr_type |= PTHREAD_MUTEX_RECURSIVE_NP; /* can be recursive call */ + pthread_mutexattr_settype(&attr, attr_type); + ret = pthread_mutex_init(&table->htable_mutex[i], &attr); + if(ret != 0){ + break; + } + } + + table->hlist_head = (MESA_list_count_t *)HASH_MALLOC(sizeof(MESA_list_count_t) * table->mutex_num); + for(i=0; i < table->mutex_num; i++){ + MESA_list_count_init_head(&(table->hlist_head[i])); + } + }else{ + /* ������Ϊ0ʱ, ����һ��head�ڵ�, ���ڼ�¼��ǰMUTEX_INDEX��Ԫ������ */ + table->hlist_head = (MESA_list_count_t *)HASH_MALLOC(sizeof(MESA_list_count_t)); + MESA_list_count_init_head(&table->hlist_head[0]); + } + + return ret; +} + + +static void __MHO_free_opt_slot_size(MESA_htable_inner_t *table) +{ + HASH_FREE(table->elems); +} + +static void __MHO_free_opt_mutex_num(MESA_htable_inner_t *table) +{ + int i; + + if(table->mutex_num > 0){ + for(i = 0; i < table->mutex_num; i++){ + pthread_mutex_destroy(&table->htable_mutex[i]); + } + HASH_FREE(table->htable_mutex); + } + + HASH_FREE(table->hlist_head); +} + +static int __MHO_proc_opt_auto_update_time(MESA_htable_handle apitable) +{ + MESA_htable_inner_t *table; + + table = (MESA_htable_inner_t *)apitable; + + htable_opt_time_t *time_opt = table->htable_option[MHO_AUTO_UPDATE_TIME]; + /* 2015-01-04 lijia add, ��̨����ʱ������߳�, ����ÿ�ζ�����time(0), ���������� */ + if((time_opt != NULL) && (time_opt->opt_switch != 0)){ + pthread_create(&time_opt->timer_thread_pid, NULL, __MESA_htable_update_time, time_opt); + pthread_detach(time_opt->timer_thread_pid); + sched_yield(); + time_opt->current_time = time(NULL); + } + + return 0; +} + + +static int __MHO_proc_opt_slot_size(MESA_htable_handle apitable) +{ + MESA_htable_inner_t *table; + + table = (MESA_htable_inner_t *)apitable; + + table->elems = (htable_elem_t **)HASH_MALLOC(table->size * sizeof(void *)); + memset(table->elems, 0, table->size * sizeof(void *)); + + return 0; +} + +static void __MHO_free_opt_auto_update_time(MESA_htable_inner_t *table) +{ + htable_opt_time_t *time_opt = table->htable_option[MHO_AUTO_UPDATE_TIME]; + + if(time_opt != NULL){ + pthread_cancel(time_opt->timer_thread_pid); + sched_yield(); + HASH_FREE(time_opt); + } +} + +static void __MHO_free_opt_runtime_log(MESA_htable_inner_t *table) +{ + free((void *)table->htable_runtime_log); +} + +static int __MHO_get_opt_max_search_times(MESA_htable_handle apitable, enum MESA_htable_opt opt_type, void *opt_val, int *opt_len) +{ + MESA_htable_inner_t *table; + int *max_times; + + if((NULL == opt_val) || (NULL == opt_len) || (*opt_len != sizeof(int))){ + return -1; + } + + table = (MESA_htable_inner_t *)apitable; + max_times = (int *)opt_val; + + *max_times = table->hash_search_status.max_item_search_times; + + return 0; +} + +static int __MHO_get_opt_avg_search_times(MESA_htable_handle apitable, enum MESA_htable_opt opt_type, void *opt_val, int *opt_len) +{ + MESA_htable_inner_t *table; + double *avg_times; + + if((NULL == opt_val) || (NULL == opt_len) || (*opt_len != sizeof(double))){ + return -1; + } + + table = (MESA_htable_inner_t *)apitable; + avg_times = (double *)opt_val; + + *avg_times = (double)table->hash_search_status.total_item_search_times/(double)table->hash_search_status.total_api_search_times; + + return 0; +} + +static MESA_opt_manage_t MESA_OPT_MANAGE[__MHO_MAX_VAL] = +{ + {MHO_THREAD_SAFE, __MHO_set_opt_thread_safe, NULL, NULL, NULL}, + {MHO_MUTEX_NUM, __MHO_set_opt_mutex_num, NULL, __MHO_proc_opt_mutex_num, __MHO_free_opt_mutex_num}, + {MHO_HASH_SLOT_SIZE, __MHO_set_opt_slot_size, NULL, __MHO_proc_opt_slot_size, __MHO_free_opt_slot_size}, + {MHO_HASH_MAX_ELEMENT_NUM, __MHO_set_opt_max_ele_num, NULL, NULL, NULL}, + {MHO_EXPIRE_TIME, __MHO_set_opt_expire_time, NULL, NULL, NULL}, + {MHO_ELIMIMINATE_TYPE, __MHO_set_opt_expire_type, NULL, NULL, NULL}, + {MHO_CBFUN_KEY_COMPARE, __MHO_set_opt_key_compare, NULL, NULL, NULL}, + {MHO_CBFUN_KEY_TO_INDEX, __MHO_set_opt_key2index, NULL, NULL, NULL}, + {MHO_CBFUN_DATA_FREE, __MHO_set_opt_data_free, NULL, NULL, NULL}, + {MHO_CBFUN_DATA_EXPIRE_NOTIFY, __MHO_set_opt_expire_notify, NULL, NULL, NULL}, + {MHO_CBFUN_COMPLEX_KEY_DUP, __MHO_set_opt_key_dup, NULL, NULL, NULL}, + {MHO_CBFUN_COMPLEX_KEY_FREE, __MHO_set_opt_key_free, NULL, NULL, NULL}, + {MHO_AUTO_UPDATE_TIME, __MHO_set_opt_auto_update_time, NULL, __MHO_proc_opt_auto_update_time, __MHO_free_opt_auto_update_time}, + {MHO_SCREEN_PRINT_CTRL, __MHO_set_opt_screen_print, NULL, NULL, NULL}, + {MHO_HASH_LIST_COLLIDE_THRESHOLD, __MHO_set_opt_collide_threshold, NULL, NULL, NULL}, + {MHO_HASH_LOG_FILE, __MHO_set_opt_runtime_log, NULL, NULL, __MHO_free_opt_runtime_log}, + {MHO_HASH_SEARCH_MAX_TIMES, NULL, __MHO_get_opt_max_search_times, NULL, NULL}, + {MHO_HASH_SEARCH_AVG_TIMES, NULL, __MHO_get_opt_avg_search_times, NULL, NULL} +}; + +void MESA_htable_print_crtl(MESA_htable_handle api_table, int print_switch) +{ + MESA_htable_inner_t *table = (MESA_htable_inner_t *)api_table; + + table->print_switch = print_switch; + + return; +} + +/* + * hash implementation, xh, 2001-07-26 + */ + +/*Developer Notice: + in hash_add function,hash table MALLOC memory for keys and RECORD data pointer, + which means need NOT malloc memory for keys before call hash_add. zhengchao + + 2013-05, LiJia, add thread safe implement. +*/ + + +/* return value: + 1:first time get lock success; + 0:can't get lock. +*/ +static HASH_INLINE int __MESA_hash_mutex_lock(const MESA_htable_inner_t * table, uint slot_index) +{ + int get_lock = 0; + int mutex_index; +#if 0 + + pthread_t my_id = pthread_self(); + + + if(table->thread_safe != 0){ + mutex_index = slot_index % table->thread_safe; + if(pthread_equal(my_id, table->acquire_lock1[mutex_index]) + && pthread_equal(my_id, table->acquire_lock2[mutex_index])){ + get_lock = 0; /* already get lock */ + }else{ + ret = pthread_mutex_lock(&table->htable_mutex[mutex_index]); + if(0 == ret){ + table->acquire_lock1[mutex_index] = my_id; + table->acquire_lock2[mutex_index] = my_id; + get_lock = 1; + } + } + } + + return get_lock; +#else + if(table->thread_safe != 0){ + mutex_index = slot_index % table->thread_safe; + get_lock = pthread_mutex_lock(&table->htable_mutex[mutex_index]); + } + + return get_lock; +#endif +} + +static HASH_INLINE int __MESA_hash_mutex_unlock(const MESA_htable_inner_t * table, uint slot_index) +{ + int ret = 0; + int mutex_index; +#if 0 + pthread_t my_id = pthread_self(); + + if(table->thread_safe != 0){ + mutex_index = slot_index % table->thread_safe; + if(pthread_equal(my_id, table->acquire_lock1[mutex_index]) + && pthread_equal(my_id, table->acquire_lock2[mutex_index])){ + table->acquire_lock1[mutex_index] = THREAD_PID_INIT1; + table->acquire_lock2[mutex_index] = THREAD_PID_INIT2; + ret = pthread_mutex_unlock(&table->htable_mutex[mutex_index]); + }else{ + ret = 0; + } + } +#else + if(table->thread_safe != 0){ + mutex_index = slot_index % table->thread_safe; + ret = pthread_mutex_unlock(&table->htable_mutex[mutex_index]); + } +#endif + return ret; +} + +static int __MESA_hash_time_list_insert(MESA_htable_inner_t *table, + htable_elem_t *hash_elem, uint index) +{ + int ret = 0; + MESA_list_count_t *list_head; + + if(table->thread_safe > 0){ + list_head = &table->hlist_head[index%table->thread_safe]; + }else{ + list_head = &table->hlist_head[0]; + } + + MESA_list_count_add_tail(list_head, &hash_elem->list_node); + + return ret; +} + +static HASH_INLINE void __MESA_hash_time_list_delete(MESA_htable_inner_t *table, + htable_elem_t *hash_elem, uint index) +{ + MESA_list_count_t *list_head; + + if(table->thread_safe > 0){ + list_head = &table->hlist_head[index%table->thread_safe]; + }else{ + list_head = &table->hlist_head[0]; + } + MESA_list_count_del(list_head, &hash_elem->list_node); + + + + return; +} + +static inline time_t __MESA_htable_get_time_now(const MESA_htable_inner_t *table) +{ + htable_opt_time_t *time_opt = table->htable_option[MHO_AUTO_UPDATE_TIME]; + + if((NULL == time_opt) || (0 == time_opt->opt_switch)){ + return time(NULL); + } + + return time_opt->current_time; +} + +static HASH_INLINE void __MESA_hash_time_list_lru(MESA_htable_inner_t *table, + htable_elem_t *hash_elem, uint index) +{ + MESA_list_count_t *list_head; + + if(table->expire_time != 0){ + hash_elem->op_time = __MESA_htable_get_time_now(table); + } + if(table->thread_safe > 0){ + list_head = &table->hlist_head[index%table->thread_safe]; + }else{ + list_head = &table->hlist_head[0]; + } + + MESA_list_count_move_tail(list_head, &hash_elem->list_node); + + return; +} + +static HASH_INLINE int __MESA_hash_bucket_lru(MESA_htable_inner_t *table, + htable_elem_t *cur_elem, uint index) +{ + if(cur_elem != table->elems[index]){ + /* �����ǰԪ�ز��ڵ�ǰbucket��һ��λ����, ���ƶ���bucket��һλ, �´β��Ҽ������ֻ��Ҫһ�� */ + + if(NULL != cur_elem->prev){ + cur_elem->prev->next = cur_elem->next; + }else{ + assert(0); + } + + if(NULL != cur_elem->next){ + cur_elem->next->prev = cur_elem->prev; + } + + cur_elem->next = table->elems[index]; + table->elems[index]->prev = cur_elem; + cur_elem->prev = NULL; + table->elems[index] = cur_elem; + } + + return ; +} + +/* + search HASH-table whether has duplicate key. +*/ +/*@null@*/ static htable_elem_t *__MESA_hash_key_search(MESA_htable_inner_t * table, + const uchar *key, uint size, uint index) +{ + htable_elem_t *ptr; + key_comp_fun_t *keycmp_fun = table->key_comp; + + for(ptr = table->elems[index]; NULL != ptr; ptr = ptr->next) { + if(keycmp_fun(ptr->key, ptr->size, key, size) == 0){ + break; + } + } + + return ptr; +} + +/* + search HASH-table whether has duplicate key. + ���ڷ���������������Ϣ, ֻ��MESA_htable_search��MESA_htable_search_cb()����. +*/ +static htable_elem_t *__MESA_hash_key_search_with_status_feedback( + MESA_htable_inner_t * table, const uchar *key, uint size, uint index) +{ + htable_elem_t *ptr; + key_comp_fun_t *keycmp_fun = table->key_comp; + int this_item_search_times = 1; /* ����һ��, ��ͻʱΪ1 */ + + for(ptr = table->elems[index]; NULL != ptr; ptr = ptr->next) { + if(keycmp_fun(ptr->key, ptr->size, key, size) == 0){ + break; + } + this_item_search_times++; + } + + if(this_item_search_times > table->hash_search_status.max_item_search_times){ + table->hash_search_status.max_item_search_times = this_item_search_times; + } + + table->hash_search_status.total_api_search_times++; + table->hash_search_status.total_item_search_times += (long long)this_item_search_times; + + return ptr; +} + +static HASH_INLINE unsigned short __MESA_hash_list_insert(MESA_htable_inner_t * table, + htable_elem_t * ptr, uint index) +{ + unsigned short ret; + htable_elem_t **helems = table->elems; + + ptr->prev = NULL; + ptr->next = helems[index]; + if(NULL != helems[index]){ + helems[index]->prev = ptr; + } + helems[index] = ptr; + + if(table->thread_safe > 0){ + MESA_ATOMIC_INC(table->elem_count_safe); + }else{ + table->elem_count_unsafe++; + } + + ret = ++table->hash_bucket_item_num[index]; + + return ret; +} + +static HASH_INLINE void __MESA_hash_list_delete(MESA_htable_inner_t * table, + htable_elem_t * ptr, uint index) +{ + if(NULL != ptr->prev){ + ptr->prev->next = ptr->next; + }else{ + table->elems[index] = ptr->next; + } + + if(NULL != ptr->next){ + ptr->next->prev = ptr->prev; + } + + if(table->thread_safe > 0){ + MESA_ATOMIC_DEC(table->elem_count_safe); + }else{ + table->elem_count_unsafe--; + } + + table->hash_bucket_item_num[index]--; +} + +static HASH_INLINE htable_elem_t *__MESA_hash_alloc_resource( + MESA_htable_inner_t *table, const uchar * key, uint size, const void *data, uint index) +{ + htable_elem_t *ptr = NULL; + + ptr = (htable_elem_t*)HASH_MALLOC(sizeof(htable_elem_t)); + + if(table->complex_key_dup != NULL){ + ptr->key = table->complex_key_dup(key, size); + }else{ + ptr->key = (unsigned char*)HASH_MALLOC(size); + memcpy(ptr->key, key, size); + } + + ptr->size = size; + ptr->data = (void *)data; /* lijia comment, dataָ����ڴ��ǵ���������� */ + ptr->list_node.nextele = NULL; + ptr->list_node.preele = NULL; + ptr->list_node.quiddity = (void *)ptr; + if(table->expire_time != 0){ + ptr->op_time = __MESA_htable_get_time_now(table); + } + ptr->hash_index = index; + + return ptr; + +//err_2: +// HASH_FREE(ptr); +//err_1: +// return NULL; +} + + +static HASH_INLINE void __MESA_hash_free_resource(MESA_htable_inner_t * table, + htable_elem_t *ptr, void (* func)(void *)) +{ + /* ���ͷ�key��Դ, ���ͷ�data��Դ, ��Ϊ�ܿ���key��data�ṹ���ڵ�һ��ָ�� */ + + if((table->caller_hargs_len >= HARGS_COMPLEX_KEY_LEN) && (table->complex_key_free != NULL)){ + table->complex_key_free(ptr->key, ptr->size); + }else{ + HASH_FREE(ptr->key); + } + + if(NULL != func){ + func(ptr->data); + }else if(NULL != table->free){ + table->free(ptr->data); + } + + HASH_FREE(ptr); +} + +/* NOTE: ֻ��HASH���Ƴ������ṹ��key, data�����ͷ� */ +static HASH_INLINE void __MESA_hash_item_pick(MESA_htable_inner_t * table, + htable_elem_t *ptr) +{ + if((table->caller_hargs_len >= HARGS_COMPLEX_KEY_LEN) && (table->complex_key_free != NULL)){ + table->complex_key_free(ptr->key, ptr->size); + }else{ + HASH_FREE(ptr->key); + } + + HASH_FREE(ptr); +} + + +static HASH_INLINE void __MESA_hash_del_node(MESA_htable_inner_t * table, + htable_elem_t * ptr, uint index, void (* func)(void *)) +{ + __MESA_hash_list_delete(table, ptr, index); + __MESA_hash_time_list_delete(table, ptr, index); + __MESA_hash_free_resource(table, ptr, func); +} + +static inline unsigned int __MESA_htable_get_elem_num(const MESA_htable_inner_t *table) +{ + unsigned int elenum; + + /* NOTE: likely()�÷��̰߳�ȫģʽ�µIJ�������һЩ */ + if(likely(0 == table->thread_safe)){ + elenum = table->elem_count_unsafe; + }else{ + elenum = (unsigned int )MESA_ATOMIC_READ(table->elem_count_safe); + } + return elenum; +} + +/* + kick out a oldest node from HASH-table if elements number exceed threshold, + or the node's operate time expired. +*/ +static int __MESA_hash_eliminate(MESA_htable_inner_t *table, uint index) +{ + MESA_list_count_t *list_head, *oldest_node; + htable_elem_t *hash_elem; + int do_eliminate_type = 0; + int can_be_eliminate = 1; + int do_eliminate_flag = 0; + + if(table->thread_safe > 0){ + list_head = &table->hlist_head[index%table->thread_safe]; + }else{ + list_head = &table->hlist_head[0]; + } + + if(MESA_list_count_is_empty(list_head)){ + return 0; + } + + oldest_node = list_head->nextele; + if(oldest_node){ + hash_elem = (htable_elem_t *)oldest_node->quiddity; + if((table->max_elem_num != 0) + && (__MESA_htable_get_elem_num(table) >= table->max_elem_num)){ /* too many elements */ + do_eliminate_type = ELIMINATE_TYPE_NUM; + }else if((table->expire_time != 0) + &&(hash_elem->op_time + table->expire_time < __MESA_htable_get_time_now(table))){ /* time expired */ + do_eliminate_type = ELIMINATE_TYPE_TIME; + } + if(do_eliminate_type != 0){ + if(table->expire){ + can_be_eliminate = table->expire(hash_elem->data, do_eliminate_type); + }else{ + if(ELIMINATE_TYPE_NUM == do_eliminate_type){ + can_be_eliminate = 0; /* Ϊ�˺���ǰ�汾����, ���ֵĬ�ϲ��Զ���̭ */ + }else{ + can_be_eliminate = 1; + } + } + + if(0 == can_be_eliminate){ + //__MESA_hash_time_list_lru(table, hash_elem, index); /* 2016-03-24 lijia close, �˴�����LRU ���� */ + }else{ + __MESA_hash_del_node(table ,hash_elem, hash_elem->hash_index, NULL); + do_eliminate_flag = 1; + } + } + } + + return do_eliminate_flag; +} + + + +/* + * name: __default_hash_key2index + * functionality: computes index from key, default key2index implementation + * if previous hash_create() call did not provide such a function; + * params: + * table: with which table are you dealing, we want this param be present + * because we may need size of table to compute the key; + * key: what is the label; + * size: how long is the label; + * returns: + * index in given table for given key, never fails; + */ +#if 0 +static uint __default_hash_key2index(MESA_htable_inner_t * table, uchar * key, uint size) +{ + uchar * c; + uint h, g; + + for (c = key, h = 0; c - key < size; c ++) { + h = (h << 2) + c[0]; + if(0 != (g = (h & 0xf0000000))) { + h = h ^ (g >> 24); + h = h ^ g; + } + } + return h % table->size; +} +#else +/* BKDR Hash Function */ +static uint __default_hash_key2index(MESA_htable_handle api_table, const uchar *str, uint size) +{ + uint i; + uint seed = 131; // 31 131 1313 13131 131313 etc.. + uint hash = 0; + //MESA_htable_inner_t * table = (MESA_htable_inner_t *)api_table; + + for(i = 0; i < size; i++){ + hash = hash * seed + (*str++); + } + + /* ��Ϊ������HASH���������ڲ�����, size���ɼ�, + ����, ֻ����һ��uint32_t����, ӳ�䵽ʵ�ʵ�slotʱ, ����Ҫ����HASH_SLOT_SIZE + */ + return hash; +} +#endif + +/* + * name: __default_hash_key_comp + * functionality: compares two key; + * params: + * key1, key2: what are the labels; + * size1, size2: how long are them; + * returns: + * 0, if two keys are identical; (just a simple memcmp() ); + * 1, no. + */ +static int __default_hash_key_comp(const uchar * key1, uint size1, const uchar * key2, uint size2) +{ + if(size1 != size2) return 1; + return memcmp(key1, key2, size1); +} + + +/* �����Ƿ�2��N�η� */ +static HASH_INLINE int number_is_2N(uint n) +{ +#if 0 + uint s; + for(s = n; s != 0; ) { + if(0x01 != s && 0x01 == (0x01 & s)) return 0; + s = s >> 1; + } +#else + if(n & (n-1)){ + return 0; + } +#endif + + return 1; +} + + + +/* + * get total number of HASH element. +*/ +unsigned int MESA_htable_get_elem_num(const MESA_htable_handle api_table) +{ + return __MESA_htable_get_elem_num((const MESA_htable_inner_t *)api_table); +} + + + +/* + * name: hash_create + * functionality: allocats memory for hash slots, and fill in hash structure; + * + * args: + * thread_safe: 0:create hashtable without thread safe features; + * positive:the bigger number has more performance, 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, low performance when enable. + * 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, only free attached data pointer if NULL; + * data_expire_with_condition: if expire_time > 0, call this function when a element expire, eliminate always if NULL; + * args: + * data: pointer to attached data; + * type: eliminate reason, ELIMINATE_TYPE_NUM or ELIMINATE_TYPE_TIME; + * return value of 'data_expire_with_condition': + * 1: can be eliminated; + * 0: 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. + */ +MESA_htable_handle MESA_htable_create(const MESA_htable_create_args_t *args, int args_struct_len) +{ + MESA_htable_inner_t *table = NULL; + unsigned int i = 0, j = 0; + int ret = 0; + pthread_mutexattr_t attr; + int attr_type; + + if(args_struct_len > (int)sizeof(MESA_htable_create_args_t)){ + printf("\033[41mError! Caller MESA_htable header version is newer, please update libMESA_htable.x!\033[0m\n"); + return NULL; + } + + if(args_struct_len != (int)sizeof(MESA_htable_create_args_t)){ + printf("\033[41mWarning!!\033[0m\n"); + printf("\033[41mMESA_htable header version is different with library! Program action is unpredictable!\033[0m\n"); + //return NULL; + } + + if(number_is_2N(args->hash_slot_size) == 0){ + printf("\033[41mHtable error! hash_slot_size must be power 2!\033[0m\n"); + return NULL; + } + + table = (MESA_htable_inner_t *)HASH_MALLOC(sizeof(MESA_htable_inner_t)); + memset(table, 0, sizeof(MESA_htable_inner_t)); + + table->elems = (htable_elem_t**)HASH_MALLOC(sizeof(htable_elem_t *) * args->hash_slot_size); + memset(table->elems, 0, sizeof(htable_elem_t *) * args->hash_slot_size); + + table->caller_hargs_len = args_struct_len; + table->size = args->hash_slot_size; + + table->hash_bucket_item_num = (unsigned short *)HASH_MALLOC(sizeof(short) * args->hash_slot_size); + memset(table->hash_bucket_item_num, 0, sizeof(short) * args->hash_slot_size); + + if(NULL == args->key_comp){ + table->key_comp = __default_hash_key_comp; + }else{ + table->key_comp = args->key_comp; + } + if(NULL == args->key2index){ + table->key2index = __default_hash_key2index; + }else{ + table->key2index = args->key2index; + } + + table->expire = args->data_expire_with_condition; + //if(NULL == data_free) return -1; /* 2013-05-06 modify, can be NULL */ + table->free = args->data_free; + + if(args->thread_safe > 1){ + MESA_ATOMIC_SET(table->elem_count_safe, 0); + }else{ + table->elem_count_unsafe = 0; + } + table->thread_safe = args->thread_safe; + table->max_elem_num = args->max_elem_num; + table->eliminate_type = args->eliminate_type; + table->expire_time = args->expire_time; + table->recursive = args->recursive; + table->print_switch = 1; /* default print switch is open */ + + /* NOTE: �Ϸ��Լ��; ������Ϸ��ռ�� */ + if((HASH_ELIMINATE_ALGO_LRU == table->eliminate_type) &&(0 == table->thread_safe)){ + if((0 == table->max_elem_num) && (0 == table->expire_time)){ + printf("\033[33mWarning!MESA_htable_create(): thread_safe is 0, max_elem_num is 0 and expire_time is 0, but eliminate_type is LRU! Reset eliminate_type to FIFO!\033[0m\n"); + }else{ + printf("\033[33mWarning!MESA_htable_create(): thread_safe is 0, but eliminate_type is LRU!\nThe action is inscrutable if running in multi-thread mode, be careful!\033[0m\n"); + } + } + + if(args_struct_len >= HARGS_COMPLEX_KEY_LEN){ + table->complex_key_dup = args->complex_key_dup; + table->complex_key_free = args->complex_key_free; + + if((table->complex_key_dup != NULL) + && (NULL == table->complex_key_free)){ + fprintf(stderr, "Error! Set 'complex_key_dup' but no 'complex_key_free', maybe memory leak!\n "); + goto err_1; + } + + if((table->complex_key_dup != NULL) + && (NULL == table->key_comp)){ + fprintf(stderr, "Error! Set 'complex_key_dup' but no 'key_comp', compare result maybe incorrect!\n "); + goto err_1; + } + + if((table->complex_key_dup != NULL) + && (NULL == table->key2index)){ + fprintf(stderr, "Error! Set 'complex_key_dup' but no 'key2index', HASH index maybe incorrect!\n "); + goto err_1; + } + + }else{ + table->complex_key_dup = NULL; + table->complex_key_free = NULL; + } + + if(table->thread_safe > 0){ + if(table->thread_safe > HASH_TABLE_MUTEX_NUM){ + printf("\033[33mWarning!thread_safe max value is :%d, set to %d.\033[0m\n", + HASH_TABLE_MUTEX_NUM, HASH_TABLE_MUTEX_NUM); + table->thread_safe = HASH_TABLE_MUTEX_NUM; + } + + table->htable_mutex = (pthread_mutex_t *)HASH_MALLOC(sizeof(pthread_mutex_t) * table->thread_safe); + if(NULL == table->htable_mutex){ + ret = -1; + goto err_1; + } + for(i = 0; i < table->thread_safe; i++){ + if(table->recursive != 0){ + pthread_mutexattr_init(&attr); + pthread_mutexattr_gettype(&attr, &attr_type); + attr_type |= PTHREAD_MUTEX_RECURSIVE_NP; /* can be recursive call */ + pthread_mutexattr_settype(&attr, attr_type); + ret = pthread_mutex_init(&table->htable_mutex[i], &attr); + }else{ + ret = pthread_mutex_init(&table->htable_mutex[i], NULL); + } + if(ret !=0){ + ret = -1; + goto err_2; + } +#if 0 + table->acquire_lock1[i] = THREAD_PID_INIT1; + table->acquire_lock2[i] = THREAD_PID_INIT2; +#endif + } + table->hlist_head = (MESA_list_count_t *)HASH_MALLOC(sizeof(MESA_list_count_t) * table->thread_safe); + if(NULL == table->hlist_head){ + ret = -1; + goto err_2; + } + for(i=0;i<table->thread_safe;i++){ + MESA_list_count_init_head(&(table->hlist_head[i])); + } + }else{ + table->hlist_head = (MESA_list_count_t *)HASH_MALLOC(sizeof(MESA_list_count_t)); + if(NULL == table->hlist_head){ + ret = -1; + goto err_2; + } + MESA_list_count_init_head(&table->hlist_head[0]); + } + + + table->create_type = HTABLE_CREATE_TYPE_ORIGINAL; /* 2016-02-24 lijia add */ + +#if MESA_HASH_LIST_COLLIDE_DETECT + table->hash_list_collide_threshold = 100; + table->htable_runtime_log = __MH_htable_runtime_log; +#endif + + return (MESA_htable_handle)table; + +err_2: + for(j = 0; (table->thread_safe > 0) &&(j < i); j++){ + pthread_mutex_destroy(&table->htable_mutex[j]); + } + HASH_FREE(table->htable_mutex); +err_1: + HASH_FREE(table->elems); + return NULL; +} + + + +/* + * adds data identified by key to table. + * table->elems always points to the newest added element. + * no two elements should have a same key, although them may have a same index. + * returns: + * >0 success,return hash elems' linklist size + * -1, duplicates found and can't add this one; + * -2, memory failure; + * -3, item num full. + * -4, other errors. + */ +int MESA_htable_add(MESA_htable_handle api_table, const uchar * key, uint size, const void * data) +{ + uint index; + htable_elem_t * ptr; + int ret = MESA_HTABLE_RET_OK, del_elem = 0; + MESA_htable_inner_t *table = (MESA_htable_inner_t *)api_table; + + if(unlikely((NULL == api_table) || (NULL == key))){ + return MESA_HTABLE_RET_ARG_ERR; + } + + if(unlikely(size <= 0)){ + return MESA_HTABLE_RET_LEN_ERR; + } + + index = table->key2index(table, key, size) % table->size; + + ret = __MESA_hash_mutex_lock(table,index); + if(unlikely(ret != 0)){ + return MESA_HTABLE_RET_CANT_GET_LOCK; + } + + del_elem = __MESA_hash_eliminate(table,index);/* 2013-09-12 LiJia modify, ����̭�ٲ���,����Ὣ�鵽�Ľ����̭���ַ��ظ��˵����� */ + + if((table->max_elem_num > 0) && (__MESA_htable_get_elem_num(table) >= table->max_elem_num)){ + if(0 == del_elem){ /* ���������ֵ������̭����Ԫ�� */ + ret = MESA_HTABLE_RET_NUM_FULL; + goto err; + } + } + + if(__MESA_hash_key_search(table,key,size,index)){ /* already exist */ + ret = MESA_HTABLE_RET_DUP_ITEM; + goto err; + } + ptr = __MESA_hash_alloc_resource(table, key, size, data, index); + ret = (int )__MESA_hash_list_insert(table, ptr, index); + __MESA_hash_time_list_insert(table, ptr, index); + + __MESA_hash_mutex_unlock(table, index); + +#if MESA_HASH_LIST_COLLIDE_DETECT + if((ret > table->hash_list_collide_threshold) && (table->hash_list_collide_threshold > 0)){ + __MH_backtrace_print(table, ret); + } +#endif + + return ret; + +err: + __MESA_hash_mutex_unlock(table,index); + return ret; + +} + + + +/* + * name: hash_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; + * -1, no such thing; + */ +int MESA_htable_del(MESA_htable_handle api_table, const uchar * key, uint size, + void (* func)(void *)) +{ + uint index; + htable_elem_t * ptr; + int ret = MESA_HTABLE_RET_OK; + MESA_htable_inner_t *table = (MESA_htable_inner_t *)api_table; + + if(unlikely((NULL == api_table) || (NULL == key))){ + return MESA_HTABLE_RET_ARG_ERR; + } + + if(unlikely(size <= 0)){ + return MESA_HTABLE_RET_LEN_ERR; + } + + index = table->key2index(table, key, size) % table->size; + + ret = __MESA_hash_mutex_lock(table,index); + if(unlikely(ret != 0)){ + return MESA_HTABLE_RET_CANT_GET_LOCK; + } + ptr = __MESA_hash_key_search(table,key,size,index); + if(NULL == ptr){ + ret = MESA_HTABLE_RET_NOT_FOUND; + goto err; /* success, maybe? why? */ + } + + __MESA_hash_del_node(table ,ptr, index, func); + + __MESA_hash_mutex_unlock(table,index); + + + return ret; + +err: + + __MESA_hash_mutex_unlock(table,index); + return ret; +} + + +/* + * 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 api_table, void (* func)(void *), int batch_num) +{ + MESA_list_count_t *list_head, *oldest_node; + htable_elem_t *del_item; + int ret = 0; + MESA_htable_inner_t *table = (MESA_htable_inner_t *)api_table; + unsigned int i, del_num = 0; + unsigned int cur_ele_num = __MESA_htable_get_elem_num(table); + unsigned int del_batch_num = (unsigned int )batch_num <= cur_ele_num? (unsigned int )batch_num: cur_ele_num; + + while(del_num < del_batch_num){ + for(i = 0; i <= table->thread_safe; i++){ + /* ѭ������ʹ��"i<=", ��Ϊtable->thread_safe����Ϊ0, + �����table->thread_safe>0, i����ʵ��==table->thread_safe, ����ѭ����������һ���ж�. */ + if((i > 0) && (i >= table->thread_safe)){ + break; + } + ret = __MESA_hash_mutex_lock(table,i); + if(unlikely(ret != 0)){ + continue; + } + cur_ele_num = __MESA_htable_get_elem_num(table); + del_batch_num = batch_num <= cur_ele_num? batch_num: cur_ele_num; + + if(table->thread_safe > 0){ + list_head = &table->hlist_head[i]; + }else{ + list_head = &table->hlist_head[0]; + } + + if(MESA_list_count_is_empty(list_head)){ + __MESA_hash_mutex_unlock(table,i); + continue; + } + + oldest_node = list_head->nextele; + del_item = (htable_elem_t *)oldest_node->quiddity; + + if(table->expire){ + table->expire(del_item->data, ELIMINATE_TYPE_MANUAL); + } + + /* �˴�ʹ��hash_item�洢��hash_index */ + __MESA_hash_list_delete(table, del_item, del_item->hash_index); + __MESA_hash_time_list_delete(table, del_item, i); + __MESA_hash_free_resource(table, del_item, func); + + __MESA_hash_mutex_unlock(table,i); + + del_num++; + } + + } + + return del_num; +} + + +/* + * name: hash_sel + * 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 api_table, const uchar * key, uint size) +{ + uint index; + htable_elem_t * ptr; + void *ret; + int res; + MESA_htable_inner_t *table = (MESA_htable_inner_t *)api_table; + + if(unlikely((NULL == api_table) || (NULL == key))){ + MHT_PRINT(table, "MESA_htable_search() error, Invalid args!\n"); + return NULL; + } + + if(unlikely(size <= 0)){ + MHT_PRINT(table, "MESA_htable_search() error, Invalid key size!\n"); + return NULL; + } + + if(unlikely(table->thread_safe != 0)){ + MHT_PRINT(table, "Warning! Use 'MESA_htable_search' in thread safe mode!\n\tIf you know this risk and determine to running\n\tYou should call 'MESA_htable_print_crtl' or 'MESA_htable_set_opt' to close the screen print. \n\tBut, be careful, good luck!!!\n "); + } + + index = table->key2index(table, key, size) % table->size; + res = __MESA_hash_mutex_lock(table,index); + if(unlikely(res != 0)){ + return NULL; + } + __MESA_hash_eliminate(table,index); /* 2013-09-12 LiJia modify, ����̭�ٲ���,����Ὣ�鵽�Ľ����̭���ַ��ظ��˵����� */ + ptr = __MESA_hash_key_search_with_status_feedback(table,key,size,index); + if(NULL != ptr){ + ret = ptr->data; + if(HASH_ELIMINATE_ALGO_LRU==table->eliminate_type){ + __MESA_hash_time_list_lru(table, ptr, index); + __MESA_hash_bucket_lru(table, ptr, index); + } + }else{ + ret = NULL; + } + + __MESA_hash_mutex_unlock(table,index); + + return ret; +} + +/* + * name: hash_sel + * functionality: selects item from table, 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 api_table, const uchar * key, uint size, + hash_cb_fun_t *cb, void *arg, long *cb_ret) +{ + uint index; + htable_elem_t * ptr; + void *ret; + int res; + MESA_htable_inner_t *table = (MESA_htable_inner_t *)api_table; + + if(unlikely((NULL == api_table) || (NULL == key) || (size <= 0))){ + MHT_PRINT(table, "MESA_htable_search_cb() error, Invalid args!\n"); + return NULL; + } + + if((NULL == cb) && (table->thread_safe != 0)){ + MHT_PRINT(table, "MESA_htable_search_cb() warning, thread_safe is %d and 'cb' is NULL!\n", table->thread_safe); + /* �˴���ʱ��ǿ�Ʒ��ش���, ֻ��ӡ������Ϣ */ + } + + index = table->key2index(api_table, key, size) % table->size; + + res = __MESA_hash_mutex_lock(table,index); + if(unlikely(res != 0)){ + return NULL; + } + + __MESA_hash_eliminate(table,index);/* 2013-09-12 LiJia modify, ����̭�ٲ���,����Ὣ�鵽�Ľ����̭���ַ��ظ��˵����� */ + + ptr = __MESA_hash_key_search_with_status_feedback(table,key,size,index); + if(NULL != ptr){ + ret = ptr->data; + if(HASH_ELIMINATE_ALGO_LRU == table->eliminate_type){ + __MESA_hash_time_list_lru(table, ptr, index); + __MESA_hash_bucket_lru(table, ptr, index); + } + if(cb){ + *cb_ret = cb(ptr->data, key, size, arg); + } + }else{ + ret = NULL; + if(cb){ + *cb_ret = cb(NULL, key, size, arg); + } + } + + __MESA_hash_mutex_unlock(table,index); + + return ret; +} + +#if 0 +int MESA_hash_iterate_v3_r(MESA_htable_handle api_table, void (* func)(uchar * key, uint size, void * data)) +{ + int i, get_lock; + htable_elem_t * ptr; + MESA_htable_inner_t *table = (MESA_htable_inner_t *)api_table; + + if(NULL == func){ + return -1; + } + + for(i = 0; i < (int)table->size; i++){ + get_lock = __MESA_hash_mutex_lock(table, i); + + for(ptr = table->elems[i]; NULL != ptr; ptr = ptr->next){ + func(ptr->key, ptr->size, ptr->data); + } + + if(get_lock){ + __MESA_hash_mutex_unlock(table, i); + } + } + + return 0; +} +#endif + +int MESA_htable_iterate(MESA_htable_handle api_table, + void (* func)(const uchar * key, uint size, void * data, void * u), void * user) +{ + int i, ret; + htable_elem_t *ptr, *next; + MESA_htable_inner_t *table = (MESA_htable_inner_t *)api_table; + + if(NULL == func){ + return MESA_HTABLE_RET_ARG_ERR; + } + for(i = 0; i < (int)table->size; i ++){ /* iterate slot */ + ret = __MESA_hash_mutex_lock(table, i); + if(unlikely(ret != 0)){ + continue; + } + /* NOTE: ֧�ֵݹ�ɾ��, ��next����ptr->next, ptr�����Ѿ���func�ͷ�, ptr->nextΪҰָ�� */ + for(ptr = table->elems[i]; NULL != ptr; ptr = next){ + next = ptr->next; + func(ptr->key, ptr->size, ptr->data, user); + } + + __MESA_hash_mutex_unlock(table, i); + } + + return 0; +} + +static inline int __check_ret_val(int cb_fun_ret) +{ + if((cb_fun_ret & ITERATE_CB_RET_CONTINUE_FLAG) + && (cb_fun_ret & ITERATE_CB_RET_BREAK_FLAG)){ + return -1; + } + + if((cb_fun_ret & ITERATE_CB_RET_DEL_FLAG) + && (cb_fun_ret & ITERATE_CB_RET_REVERSE_FLAG)){ + return -1; + } + + if((cb_fun_ret & ITERATE_CB_RET_DEL_FLAG) + && (cb_fun_ret & ITERATE_CB_RET_REMOVE_BUT_NOT_FREE)){ + return -1; + } + + if((cb_fun_ret & ITERATE_CB_RET_REVERSE_FLAG) + && (cb_fun_ret & ITERATE_CB_RET_REMOVE_BUT_NOT_FREE)){ + return -1; + } + + return 0; +} + +/* + iterate_type: + 1: newest item first; 2: oldest item first; +*/ +int MESA_htable_iterate_bytime(MESA_htable_handle api_table, int iterate_type, + int (* func)(const uchar * key, uint size, void * data, void *u), void * user) +{ + int ret; + unsigned int i; + htable_elem_t *hitem; + MESA_htable_inner_t *table = (MESA_htable_inner_t *)api_table; + MESA_list_count_t *list_node= NULL, *list_head, *demand_next, *anchor = NULL; + + if((NULL == api_table) || (NULL == func)){ + return MESA_HTABLE_RET_ARG_ERR; + } + + if(table->mutex_num > 1){ + MHT_PRINT(table, "thread_safe is:%d, in MESA_htable_iterate_bytime(), the result is not exact!\n", table->mutex_num); + } + + for(i = 0; (i == 0) || ((i > 0) && (i < table->thread_safe)); i++){ + __MESA_hash_mutex_lock(table, i); + list_head = &table->hlist_head[i]; + if(1 == iterate_type){ + list_node = list_head->preele; + }else{ + list_node = list_head->nextele; + } + while((MESA_list_count_is_empty(list_head) == 0) &&(list_node != list_head) && (list_node != anchor)){ + hitem = (htable_elem_t *)list_node->quiddity; + if(1 == iterate_type){ + demand_next = list_node->preele; + }else{ + demand_next = list_node->nextele; + } + ret = func(hitem->key, hitem->size, hitem->data, user); + if(__check_ret_val(ret) < 0){ + MHT_PRINT(table, "cb_fun return value illegal!\n"); + } + + if(ret & ITERATE_CB_RET_REVERSE_FLAG){ + if(1 == iterate_type){ + MESA_list_count_del(list_head, list_node); + MESA_list_count_add(list_head, list_node); + }else if (2 == iterate_type){ + MESA_list_count_del(list_head, list_node); + MESA_list_count_add_tail(list_head, list_node); + }else{ + MHT_PRINT(table, "iterate_type value illegal!\n"); + goto fun_exit; + } + if(NULL == anchor){ + anchor = list_node; /* ��ֹ�ص�����һֱ����reverse, �����ѭ��, �˴��Ӹ�ê, �ٴ�ѭ����������� */ + } + }else if(ret & ITERATE_CB_RET_DEL_FLAG){ + __MESA_hash_del_node(table ,hitem, hitem->hash_index, table->free); + }else if(ret & ITERATE_CB_RET_REMOVE_BUT_NOT_FREE){ + __MESA_hash_list_delete(table,hitem, hitem->hash_index); + __MESA_hash_time_list_delete(table, hitem, hitem->hash_index); + __MESA_hash_item_pick(table, hitem); + } + + if(ret & ITERATE_CB_RET_BREAK_FLAG){ + goto fun_exit; + } + list_node = demand_next; + } + __MESA_hash_mutex_unlock(table, i); + } + + return 0; + +fun_exit: + __MESA_hash_mutex_unlock(table, i); + return -1; +} +#if 0 +int MESA_hash_expire(MESA_htable_inner_t * table) +{ + int i, delta; + htable_elem_t * ptr, * tmp; + + if(NULL == table->expire) return 0; + for(i = 0; i < (int)table->size; i ++) { + ptr = table->elems[i]; + while(NULL != ptr) { + if(table->expire(ptr->data)) { + if(NULL != ptr->prev) + { + ptr->prev->next = ptr->next; + } + else + { + table->elems[i] = ptr->next; + } + if(NULL != ptr->next) + ptr->next->prev = ptr->prev; + tmp = ptr; + ptr = ptr->next; + if(NULL != table->free) + table->free(tmp->data); + free(tmp); + + table->elem_count --; + + continue; + } + ptr = ptr->next; + } + } + return 0; +} +#endif + + + +/* + to set feature 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; + + return value: + 0 :OK; + <0:error; +*/ +int MESA_htable_set_opt(MESA_htable_handle api_table, enum MESA_htable_opt opt_type, void *opt_val, int opt_len) +{ + int ret; + MESA_htable_inner_t *table = (MESA_htable_inner_t *)api_table; + + if((NULL == api_table) || (NULL == opt_val)){ + return -1; + } + + if(HTABLE_CREATE_TYPE_ORIGINAL == table->create_type){ + MHT_PRINT(table, "MESA_htable_handle is create by MESA_htable_create(), not support MESA_htable_set_opt, \n"); + MHT_PRINT(table, "please use MESA_htable_born() API to create MESA_htable_handle!\n"); + return -1; + } + + if(table->is_running){ + MHT_PRINT(table, "Can't call MESA_htable_set_opt() again after MESA_htable_mature!\n"); + return -1; + } + + if(((int)opt_type < 0) || ((int)opt_type >= __MHO_MAX_VAL)){ + MHT_PRINT(table, "opt_type invalid!\n"); + return -1; + } + + switch((int)opt_type){ + case MHO_THREAD_SAFE: + case MHO_MUTEX_NUM: + case MHO_HASH_SLOT_SIZE: + case MHO_HASH_MAX_ELEMENT_NUM: + case MHO_EXPIRE_TIME: + case MHO_ELIMIMINATE_TYPE: + case MHO_CBFUN_KEY_COMPARE: + case MHO_CBFUN_KEY_TO_INDEX: + case MHO_CBFUN_DATA_FREE: + case MHO_CBFUN_DATA_EXPIRE_NOTIFY: + case MHO_CBFUN_COMPLEX_KEY_DUP: + case MHO_CBFUN_COMPLEX_KEY_FREE: + case MHO_AUTO_UPDATE_TIME: + case MHO_SCREEN_PRINT_CTRL: + case MHO_HASH_LIST_COLLIDE_THRESHOLD: + case MHO_HASH_LOG_FILE: + break; + + default: + MHT_PRINT(table, "opt_type invalid or not support!\n"); + return -1; + break; + } + + ret = MESA_OPT_MANAGE[opt_type].MESA_htable_set_opt_fun(api_table, opt_type, opt_val, opt_len); + + return ret; +} + + +int MESA_htable_get_opt(MESA_htable_handle api_table, enum MESA_htable_opt opt_type, void *opt_val, int *opt_len) +{ + int ret = 0; + MESA_htable_inner_t *table = (MESA_htable_inner_t *)api_table; + + if((NULL == api_table) || (NULL == opt_val)){ + return -1; + } + + if(((int)opt_type < 0) || ((int)opt_type >= __MHO_MAX_VAL)){ + MHT_PRINT(table, "opt_type invalid!\n"); + return -1; + } + + switch((int)opt_type){ + case MHO_HASH_SEARCH_MAX_TIMES: + case MHO_HASH_SEARCH_AVG_TIMES: + break; + + default: + MHT_PRINT(table, "opt_type invalid or not support!\n"); + return -1; + break; + } + + ret = MESA_OPT_MANAGE[opt_type].MESA_htable_get_opt_fun(api_table, opt_type, opt_val, opt_len); + + return ret; +} + +/* + Ϊ�˼���֮ǰ�Ĵ���, ����ʹ��MESA_htable_inner_t�ṹ, + ����һЩ���û�������, ��������߲�ʹ��MESA_htable_set_opt()���ø��Ի�����, + Ҳ�ܱ�֤���HASH�����ܿ���. +*/ +static void __MESA_htable_set_default_opt(MESA_htable_inner_t *table) +{ + table->size = 1024 * 1024; + table->thread_safe = 1; /* Ĭ�����̰߳�ȫ��, ���ٱ�֤��ʲô����¶�������������. */ + table->recursive = 1; + table->elem_count_unsafe = 0; + table->key_comp = __default_hash_key_comp; + table->key2index = __default_hash_key2index; + table->expire = NULL; + table->free = NULL; /* �˴������ɵ���������ʵ�� */ + table->max_elem_num = 0; + table->eliminate_type = HASH_ELIMINATE_ALGO_FIFO; + table->expire_time = 0; + table->print_switch = 1; /* Ĭ�Ͽ�����Ļ��ӡ */ + table->complex_key_dup = NULL; + table->complex_key_free = NULL; + table->mutex_num = 1; + table->caller_hargs_len = sizeof(MESA_htable_create_args_t); /* ����MESA_htable_born()�����ľ��, args_lenǡ�õ��ڵ�ǰ��MESA_htable_create_args_t */ + memset(table->htable_option, 0, sizeof(table->htable_option)); + table->hash_list_collide_threshold = 100; + table->htable_runtime_log = (const char *)malloc(strlen(__MH_htable_runtime_log) + 1); + memcpy((void *)table->htable_runtime_log, __MH_htable_runtime_log, strlen(__MH_htable_runtime_log) + 1); +} + + +/* + Create a htable handel and Alloc memory, it's struct is forbidden for caller. + return value: + not NULL: success. + NULL : error. +*/ +MESA_htable_handle MESA_htable_born(void) +{ + MESA_htable_inner_t *handle; + handle = (MESA_htable_inner_t *)HASH_MALLOC(sizeof(MESA_htable_inner_t)); + memset(handle, 0, sizeof(MESA_htable_inner_t)); + + __MESA_htable_set_default_opt(handle); + + return (void *)handle; +} + +/* + Construct htable and ready to running. + + return value: + 0 : success; + <0: error. +*/ +int MESA_htable_mature(MESA_htable_handle apitable) +{ + int i, ret; + MESA_htable_inner_t *table = (MESA_htable_inner_t *)apitable; + + if(NULL == apitable){ + return MESA_HTABLE_RET_ARG_ERR; + } + + if(table->create_type != 0){ + printf("Error! This handle is already enabled!\n"); + return MESA_HTABLE_RET_COMMON_ERR; + } + + for(i = 0; i < __MHO_MAX_VAL; i++){ + if(MESA_OPT_MANAGE[i].MESA_htable_process_opt_fun != NULL){ + ret = MESA_OPT_MANAGE[i].MESA_htable_process_opt_fun(apitable); + if(ret < 0){ + goto err; + } + } + } + + /* NOTE: �Ϸ��Լ��; ������Ϸ��ռ�� */ + if((HASH_ELIMINATE_ALGO_LRU == table->eliminate_type) &&(0 == table->thread_safe)){ + if((0 == table->max_elem_num) && (0 == table->expire_time)){ + MHT_PRINT(table,"\033[33mWarning!MESA_htable_mature(): thread_safe is 0, max_elem_num is 0 and expire_time is 0, but eliminate_type is LRU! Reset eliminate_type to FIFO!\033[0m\n"); + table->eliminate_type = HASH_ELIMINATE_ALGO_FIFO; + }else{ + MHT_PRINT(table, "\033[33mWarning!MESA_htable_mature(): thread_safe is 0, but eliminate_type is LRU!\nThe action is inscrutable if running in multi-thread mode, be careful!\033[0m\n"); + } + } + + table->hash_bucket_item_num = (unsigned short *)HASH_MALLOC(sizeof(short) * table->size); + memset(table->hash_bucket_item_num, 0, sizeof(short) * table->size); + + table->create_type = HTABLE_CREATE_TYPE_BORN; + table->is_running = 1; + + return MESA_HTABLE_RET_OK; + +err: + MESA_htable_destroy(table, NULL); + return MESA_HTABLE_RET_COMMON_ERR; +} + + +/* + * frees table->elems and chains attached to each element of it. + * always returns 0. + */ +int MESA_htable_destroy(MESA_htable_handle api_table, void (* func)(void *)) +{ + unsigned int i; + htable_elem_t *cur, *next; + MESA_htable_inner_t *table = (MESA_htable_inner_t *)api_table; + + if(NULL == api_table){ + return MESA_HTABLE_RET_ARG_ERR; + } + + for(i = 0; i < table->size; i ++) { + cur = table->elems[i]; + while(NULL != cur) { + next = cur->next; + /* 2015-05-13 lijia add, for complex key memory leak */ +#if 0 + if(NULL != func) func(cur->data); + else if(NULL != table->free) table->free(cur->data); + table->elems[i] = (table->elems[i])->next; + + if((table->caller_hargs_len >= HARGS_COMPLEX_KEY_LEN) && (table->complex_key_free != NULL)){ + (*table->complex_key_free)(cur->key, cur->size); + }else + HASH_FREE(cur->key); + } + HASH_FREE(cur); +#else + __MESA_hash_free_resource(table, cur, func); +#endif + cur = next; + } + } + + if( HTABLE_CREATE_TYPE_ORIGINAL == table->create_type){ + if(table->thread_safe > 0){ + for(i=0;i<table->thread_safe;i++){ + pthread_mutex_destroy(&table->htable_mutex[i]); + } + HASH_FREE(table->htable_mutex); + } + + HASH_FREE(table->hlist_head); + HASH_FREE(table->elems); + table->elems = NULL; + table->size = 0; + }else{ + for(i = 0; i < __MHO_MAX_VAL; i++){ + if(MESA_OPT_MANAGE[i].MESA_htable_free_opt_fun){ + MESA_OPT_MANAGE[i].MESA_htable_free_opt_fun(table); + } + } + } + + HASH_FREE(table->hash_bucket_item_num); + memset(table, 0xFE, sizeof(MESA_htable_inner_t)); /* ����֮ǰȫ���, ��ֹʹ��Ұָ�����, ����debug */ + HASH_FREE(table); + + return MESA_HTABLE_RET_OK; +} + +#ifdef __cplusplus +} +#endif + + diff --git a/support/MESA_htable/src/MESA_htable_internal.h b/support/MESA_htable/src/MESA_htable_internal.h new file mode 100644 index 0000000..f9c0924 --- /dev/null +++ b/support/MESA_htable/src/MESA_htable_internal.h @@ -0,0 +1,13 @@ +#ifndef _MESA_HTABLE_INTERNAL_H_ +#define _MESA_HTABLE_INTERNAL_H_ + +#ifndef likely +#define likely(x) __builtin_expect(!!(x), 1) +#endif + +#ifndef unlikely +#define unlikely(x) __builtin_expect(!!(x), 0) +#endif + +#endif + diff --git a/support/MESA_htable/src/MESA_list.c b/support/MESA_htable/src/MESA_list.c new file mode 100644 index 0000000..8e52ed2 --- /dev/null +++ b/support/MESA_htable/src/MESA_list.c @@ -0,0 +1,212 @@ +#ifdef __cplusplus +extern "C" +{ +#endif +#include <stdio.h> +#include "MESA_list.h" + +/*************************** �ڲ�ʵ�ֽӿ� ********************************/ + +const char *MESA_list_version_VERSION_20150529 = "MESA_list_version_VERSION_20150529"; +const unsigned int MESA_LIST_VERSION_INT = 20150529; + +/* + * Simple doubly linked list implementation. + * + * Some of the internal functions ("__xxx") are useful when + * manipulating whole lists rather than single entries, as + * sometimes we already know the next/prev entries and we can + * generate better code by using them directly rather than + * using the generic single-entry routines. + */ + +#if 0 +static void __MESA_list_count_init(void **list_count) +{ + long *p_c = (long *)list_count; + *p_c = 0; +} + +static void __MESA_list_count_inc(void **list_count) +{ + long *p_c = (long *)list_count; + long c = *p_c; + *p_c = c + 1; +} + +static void __MESA_list_count_dec(void **list_count) +{ + long *p_c = (long *)list_count; + long c = *p_c; + *p_c = c - 1; +} +#endif + +void MESA_list_init_head(struct MESA_list *head) +{ + head->nextele = head; + head->preele = head; + //__MESA_list_count_init(&head->quiddity); +} + +long MESA_list_get_count(const struct MESA_list *head) +{ + return (long)head->quiddity; +} + + +/* + * Insert a new entry between two known consecutive entries. + * + * This is only for internal list manipulation where we know + * the prev/next entries already! + */ +static inline void __MESA_list_add(struct MESA_list *new_list, + struct MESA_list *prev, + struct MESA_list *next) +{ + next->preele = new_list; + new_list->nextele = next; + new_list->preele = prev; + prev->nextele = new_list; +} + +/** + * list_add - add a new entry + * @new: new entry to be added + * @head: list head to add it after + * + * Insert a new entry after the specified head. + * This is good for implementing stacks. + * lijia comment: list_add()���½ڵ����head��head->next֮��. + */ +void MESA_list_add(struct MESA_list *head, struct MESA_list *new_list) +{ + __MESA_list_add(new_list, head, head->nextele); + //__MESA_list_count_inc(&head->quiddity); +} + + +/** + * list_add_tail - add a new entry + * @new: new entry to be added + * @head: list head to add it before + * + * Insert a new entry before the specified head. + * This is useful for implementing queues. + * lijia comment: list_add_tail()���½ڵ����head��head->prev֮��. + */ +void MESA_list_add_tail(struct MESA_list *head, struct MESA_list *new_list) +{ + __MESA_list_add(new_list, head->preele, head); + //__MESA_list_count_inc(&head->quiddity); +} + +/* + * Delete a list entry by making the prev/next entries + * point to each other. + * + * This is only for internal list manipulation where we know + * the prev/next entries already! + */ +static inline void __MESA_list_del(struct MESA_list * prev, struct MESA_list * next) +{ + next->preele = prev; + prev->nextele = next; +} + +static inline void __MESA_list_del_entry(struct MESA_list *entry) +{ + __MESA_list_del(entry->preele, entry->nextele); + entry->nextele = NULL; + entry->preele = NULL; +} + +/** + * list_del - deletes entry from list. + * @entry: the element to delete from the list. + * Note: list_empty() on entry does not return true after this, the entry is + * in an undefined state. + */ + +void MESA_list_del(struct MESA_list *head, struct MESA_list *entry) +{ + __MESA_list_del(entry->preele, entry->nextele); + entry->nextele = NULL; + entry->preele = NULL; + //__MESA_list_count_dec(&head->quiddity); +} + + +/** + * list_move - delete from one list and add as another's head + * @list: the entry to move + * @head: the head that will precede our entry + */ +void MESA_list_move(struct MESA_list *head, struct MESA_list *list) +{ + __MESA_list_del_entry(list); + MESA_list_add(head, list); +} + +/** + * list_move_tail - delete from one list and add as another's tail + * @list: the entry to move + * @head: the head that will follow our entry + */ +void MESA_list_move_tail(struct MESA_list *head, struct MESA_list *list) +{ + __MESA_list_del_entry(list); + MESA_list_add_tail(head, list); +} + +#if 0 +/** + * list_empty - tests whether a list is empty + * @head: the list to test. + */ +static int list_empty(const struct MESA_list *head) +{ + return head->nextele == head; +} +#endif + +/* insert "new_obj" between "op_place" and "op_place->nextele" */ +struct MESA_list *MESA_list_join_n(struct MESA_list *head, struct MESA_list *op_place, struct MESA_list *new_obj) +{ + __MESA_list_add(new_obj, op_place, op_place->nextele); + //__MESA_list_count_inc(&head->quiddity); + return new_obj; +} + +/* insert "new_obj" between "op_place->preele" and "op_place" */ +struct MESA_list *MESA_list_join_p(struct MESA_list *head, struct MESA_list *new_obj, struct MESA_list *op_place) +{ + __MESA_list_add(new_obj, op_place->preele, op_place); + //__MESA_list_count_inc(&head->quiddity); + return new_obj; +} + +/** + * list_empty_careful - tests whether a list is empty and not being modified + * @head: the list to test + * + * Description: + * tests whether a list is empty _and_ checks that no other CPU might be + * in the process of modifying either member (next or prev) + * + * NOTE: using list_empty_careful() without synchronization + * can only be safe if the only activity that can happen + * to the list entry is list_del_init(). Eg. it cannot be used + * if another CPU could re-list_add() it. + */ +int MESA_list_is_empty(const struct MESA_list *head) +{ + struct MESA_list *next = head->nextele; + return (next == head) && (next == head->preele); +} + +#ifdef __cplusplus +} +#endif + diff --git a/support/MESA_htable/src/MESA_list_count.c b/support/MESA_htable/src/MESA_list_count.c new file mode 100644 index 0000000..13618d7 --- /dev/null +++ b/support/MESA_htable/src/MESA_list_count.c @@ -0,0 +1,208 @@ +#ifdef __cplusplus +extern "C" +{ +#endif +#include <stdio.h> +#include "MESA_list_count.h" +#include "MESA_htable_internal.h" + +/*************************** �ڲ�ʵ�ֽӿ� ********************************/ + +/* + * Simple doubly linked list implementation. + * + * Some of the internal functions ("__xxx") are useful when + * manipulating whole lists rather than single entries, as + * sometimes we already know the next/prev entries and we can + * generate better code by using them directly rather than + * using the generic single-entry routines. + */ + +static void __MESA_list_count_init(void **list_count) +{ + long *p_c = (long *)list_count; + *p_c = 0; +} + +static void __MESA_list_count_inc(void **list_count) +{ + long *p_c = (long *)list_count; + long c = *p_c; + *p_c = c + 1; +} + +static void __MESA_list_count_dec(void **list_count) +{ + long *p_c = (long *)list_count; + long c = *p_c; + *p_c = c - 1; +} + +void MESA_list_count_init_head(struct MESA_list_count *head) +{ + head->nextele = head; + head->preele = head; + __MESA_list_count_init(&head->quiddity); +} + +long MESA_list_count_get_count(const struct MESA_list_count *head) +{ + return (long)head->quiddity; +} + + +/* + * Insert a new entry between two known consecutive entries. + * + * This is only for internal list manipulation where we know + * the prev/next entries already! + */ +static inline void __MESA_list_count_add(struct MESA_list_count *new_list, + struct MESA_list_count *prev, + struct MESA_list_count *next) +{ + next->preele = new_list; + new_list->nextele = next; + new_list->preele = prev; + prev->nextele = new_list; +} + +/** + * list_add - add a new entry + * @new: new entry to be added + * @head: list head to add it after + * + * Insert a new entry after the specified head. + * This is good for implementing stacks. + * lijia comment: list_add()���½ڵ����head��head->next֮��. + */ +void MESA_list_count_add(struct MESA_list_count *head, struct MESA_list_count *new_list) +{ + __MESA_list_count_add(new_list, head, head->nextele); + __MESA_list_count_inc(&head->quiddity); +} + + +/** + * list_add_tail - add a new entry + * @new: new entry to be added + * @head: list head to add it before + * + * Insert a new entry before the specified head. + * This is useful for implementing queues. + * lijia comment: list_add_tail()���½ڵ����head��head->prev֮��. + */ +void MESA_list_count_add_tail(struct MESA_list_count *head, struct MESA_list_count *new_list) +{ + __MESA_list_count_add(new_list, head->preele, head); + __MESA_list_count_inc(&head->quiddity); +} + +/* + * Delete a list entry by making the prev/next entries + * point to each other. + * + * This is only for internal list manipulation where we know + * the prev/next entries already! + */ +static inline void __MESA_list_count_del(struct MESA_list_count * prev, struct MESA_list_count * next) +{ + next->preele = prev; + prev->nextele = next; +} + +static inline void __MESA_list_count_del_entry(struct MESA_list_count *entry) +{ + __MESA_list_count_del(entry->preele, entry->nextele); + entry->nextele = NULL; + entry->preele = NULL; +} + +/** + * list_del - deletes entry from list. + * @entry: the element to delete from the list. + * Note: list_empty() on entry does not return true after this, the entry is + * in an undefined state. + */ + +void MESA_list_count_del(struct MESA_list_count *head, struct MESA_list_count *entry) +{ + __MESA_list_count_del(entry->preele, entry->nextele); + entry->nextele = NULL; + entry->preele = NULL; + __MESA_list_count_dec(&head->quiddity); +} + + +/** + * list_move - delete from one list and add as another's head + * @list: the entry to move + * @head: the head that will precede our entry + */ +void MESA_list_count_move(struct MESA_list_count *head, struct MESA_list_count *list) +{ + __MESA_list_count_del_entry(list); + MESA_list_count_add(head, list); +} + +/** + * list_move_tail - delete from one list and add as another's tail + * @list: the entry to move + * @head: the head that will follow our entry + */ +void MESA_list_count_move_tail(struct MESA_list_count *head, struct MESA_list_count *list) +{ + __MESA_list_count_del_entry(list); + MESA_list_count_add_tail(head, list); +} + +#if 0 +/** + * list_empty - tests whether a list is empty + * @head: the list to test. + */ +static int list_empty(const struct MESA_list_count *head) +{ + return head->nextele == head; +} +#endif + +/* insert "new_obj" between "op_place" and "op_place->nextele" */ +struct MESA_list_count *MESA_list_count_join_n(struct MESA_list_count *head, struct MESA_list_count *op_place, struct MESA_list_count *new_obj) +{ + __MESA_list_count_add(new_obj, op_place, op_place->nextele); + __MESA_list_count_inc(&head->quiddity); + return new_obj; +} + +/* insert "new_obj" between "op_place->preele" and "op_place" */ +struct MESA_list_count *MESA_list_count_join_p(struct MESA_list_count *head, struct MESA_list_count *new_obj, struct MESA_list_count *op_place) +{ + __MESA_list_count_add(new_obj, op_place->preele, op_place); + __MESA_list_count_inc(&head->quiddity); + return new_obj; +} + +/** + * list_empty_careful - tests whether a list is empty and not being modified + * @head: the list to test + * + * Description: + * tests whether a list is empty _and_ checks that no other CPU might be + * in the process of modifying either member (next or prev) + * + * NOTE: using list_empty_careful() without synchronization + * can only be safe if the only activity that can happen + * to the list entry is list_del_init(). Eg. it cannot be used + * if another CPU could re-list_add() it. + */ +int MESA_list_count_is_empty(const struct MESA_list_count *head) +{ + struct MESA_list_count *next = head->nextele; + return (next == head) && (next == head->preele); +} + +#ifdef __cplusplus +} +#endif + diff --git a/support/MESA_htable/src/MESA_list_queue.c b/support/MESA_htable/src/MESA_list_queue.c new file mode 100644 index 0000000..d20fc0b --- /dev/null +++ b/support/MESA_htable/src/MESA_list_queue.c @@ -0,0 +1,651 @@ +#ifdef __cplusplus +extern "C" +{ +#endif +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <unistd.h> +#include <linux/types.h> +#include <linux/stddef.h> +#include <assert.h> +#ifndef __USE_UNIX98 +#define __USE_UNIX98 1 +#endif +#include <pthread.h> +#include <time.h> +#include <assert.h> +#include <errno.h> +#include <semaphore.h> +#include "MESA_list_queue.h" +#include "MESA_list_count.h" +#include "MESA_htable_internal.h" + +const char * MESA_lqueue_version_VERSION_20160308 = "MESA_lqueue_version_VERSION_20160308"; +const unsigned int MESA_LIST_QUEUE_VERSION_INT = 20160308; + +/* + ��֤nextele��preeleλ�ò��䣬���Ը���list_common�еIJ��������� +*/ +typedef struct list_index_v3 { + struct list_index_v3 *nextele; /* ����ָ�������ڽṹ��ǰ2λ, ����MESA_list���� */ + struct list_index_v3 *preele; /* ����ָ�������ڽṹ��ǰ2λ, ����MESA_list���� */ + void *data; + long data_len; +}MESA_list_index_v3_t; + +typedef struct list_head_v3 { + struct list_index_v3 *nextele; /* ����ָ�������ڽṹ��ǰ2λ, ����MESA_list���� */ + struct list_index_v3 *preele; /* ����ָ�������ڽṹ��ǰ2λ, ����MESA_list���� */ + volatile long cur_item_num; /* ��ǰԪ������������ڵ�3λ */ + volatile long max_item_num; + volatile long mem_used; /* 2014-02-24 add */ + int thread_safe; + pthread_mutex_t mutex; + pthread_cond_t customer_cond; + pthread_cond_t producter_cond; +}Inter_head_v3_t; + +extern void list_count_init(void **list_count); +extern void list_count_inc(void **list_count); +extern void list_count_dec(void **list_count); + + +static int MESA_q_lock_v3(Inter_head_v3_t *queue_v3_handle, int block) +{ + int ret = -1; + + if(queue_v3_handle->thread_safe){ + if(MESA_list_BOLCK == block){ + ret = pthread_mutex_lock(&queue_v3_handle->mutex); + if(ret != 0){ + ret = MESA_QUEUE_RET_CANT_GET_LOCK; + } + }else{ + ret = pthread_mutex_trylock(&queue_v3_handle->mutex); + if(ret != 0){ + ret = MESA_QUEUE_RET_CANT_GET_LOCK; + } + } + }else{ + ret = MESA_QUEUE_RET_OK; + } + + return ret; +} + + + +static int MESA_q_unlock_v3(Inter_head_v3_t *queue_v3_handle) +{ + int ret = 0; + + if(queue_v3_handle->thread_safe){ + ret = pthread_mutex_unlock(&queue_v3_handle->mutex); + } + + return ret; +} + +static int MESA_q_cond_wait_v3(Inter_head_v3_t *queue_v3_handle, int op_type, int block) +{ + int ret = -1; + + if(queue_v3_handle->thread_safe){ + if(MESA_list_BOLCK == block){ + if(MESA_list_GET == op_type){ + ret = pthread_cond_wait(&queue_v3_handle->customer_cond, &queue_v3_handle->mutex); + }else{ + ret = pthread_cond_wait(&queue_v3_handle->producter_cond, &queue_v3_handle->mutex); + } + if(ret != 0){ + ret = -1; + } + }else{ /* ������ģʽ��, ֱ�ӷ���ʧ�� */ + ret = -1; + } + }else{ + ret = -1; + } + + return ret; +} + +static int __can_i_do_it(Inter_head_v3_t *queue_v3_handle, int op_type, int block) +{ + int ret = MESA_QUEUE_RET_OK; + + ret = MESA_q_lock_v3(queue_v3_handle, block); + if(ret < 0){ + ret = MESA_QUEUE_RET_CANT_GET_LOCK; + goto err1; + } + + if(MESA_list_JOIN == op_type){ + if((queue_v3_handle->max_item_num != 0) + && (queue_v3_handle->cur_item_num >= queue_v3_handle->max_item_num)){ + ret = MESA_q_cond_wait_v3(queue_v3_handle, op_type, block); + if(ret < 0){ + ret = MESA_QUEUE_RET_NUM_FULL; + goto err2; + } + }else{ + ret = MESA_QUEUE_RET_OK; + } + }else{ + if(0 == queue_v3_handle->cur_item_num){ + ret = MESA_q_cond_wait_v3(queue_v3_handle, op_type, block); + if(ret < 0){ + ret = MESA_QUEUE_RET_QEMPTY; + goto err2; + } + }else{ + ret = MESA_QUEUE_RET_OK; + } + } + + return ret; + +err2: + MESA_q_unlock_v3(queue_v3_handle); +err1: + return ret; +} + +static int MESA_lqueue_del_node(MESA_list_index_v3_t *queue_node) +{ + //MESA_list_count_del(NULL, (struct MESA_list_count *)queue_node); + queue_node->preele->nextele = queue_node->nextele; + queue_node->nextele->preele = queue_node->preele; + free(queue_node->data); + free(queue_node); + return 0; +} + +long MESA_lqueue_get_mem_used(MESA_lqueue_head head) +{ + Inter_head_v3_t *queue_v3_handle = (Inter_head_v3_t *)head; + return queue_v3_handle->mem_used; +} + +long MESA_lqueue_get_mem_used_exactly(MESA_lqueue_head head) +{ + long memuse = -1; + Inter_head_v3_t *queue_v3_handle = (Inter_head_v3_t *)head; + + if(MESA_q_lock_v3(queue_v3_handle, MESA_list_BOLCK) < 0){ + errno = ERANGE; + return (long)-1; + } + + memuse = queue_v3_handle->mem_used; + + MESA_q_unlock_v3(queue_v3_handle); + + return memuse; +} + + +long MESA_lqueue_get_count(MESA_lqueue_head head) +{ + Inter_head_v3_t *queue_v3_handle = (Inter_head_v3_t *)head; + /* + TODO: + �˴��Ƿ���Ҫ������? + Ӧ�ò���, ����˴�����, �������غ�, ���������Ҳ���ϻ�ı�, û��������. + �����õ���ȷ��������, Ȼ�����������Ļ�, Ӧ���ûص�������ʽ. + + */ + return queue_v3_handle->cur_item_num; +} + +long MESA_lqueue_get_count_exactly(MESA_lqueue_head head) +{ + long count = -1; + Inter_head_v3_t *queue_v3_handle = (Inter_head_v3_t *)head; + + if(MESA_q_lock_v3(queue_v3_handle, MESA_list_BOLCK) < 0){ + errno = ERANGE; + return (long)-1; + } + + count = queue_v3_handle->cur_item_num; + + MESA_q_unlock_v3(queue_v3_handle); + + return count; +} + +/* + args description: + [IN]: + lq_head : the handler of MESA_lqueue. + + [OUT]: + data : receive buffer. + + [IN $ OUT]: + data_len: is value-result argument, like "addrlen of recvfrom(2)" + the caller should initialize before the call to the size of the 'data', + and modified on return to indicate the actual size of the queue item. + +*/ +static int __MESA_lqueue_read_head(MESA_lqueue_head head, void *data, long *data_len, int block) +{ + int ret; + MESA_list_index_v3_t *queue_node; + Inter_head_v3_t *queue_v3_handle = (Inter_head_v3_t *)head; + + if(MESA_list_BOLCK == block){ + ret = __can_i_do_it(queue_v3_handle, MESA_list_GET, block); + if(unlikely(ret < 0)){ + ret = MESA_QUEUE_RET_COMMON_ERR; + goto err_1; + } + }else{ + ret = MESA_q_lock_v3(queue_v3_handle, block); + if(unlikely(ret != 0)){ + ret = MESA_QUEUE_RET_CANT_GET_LOCK; + goto err_1; + } + } + + if(MESA_list_count_is_empty((const struct MESA_list_count *)queue_v3_handle)){ + ret = MESA_QUEUE_RET_QEMPTY; + goto err_2; + } + + queue_node = queue_v3_handle->nextele; + if((NULL == data) || (NULL == data_len) || (queue_node->data_len > *data_len)){ + ret = MESA_QUEUE_RET_ARG_ERR; + goto err_2; + } + + memcpy(data, queue_node->data, queue_node->data_len); + *data_len = queue_node->data_len; + + MESA_q_unlock_v3(queue_v3_handle); + return 0; + +err_2: + MESA_q_unlock_v3(queue_v3_handle); +err_1: + return ret; +} + + +/* + args description: + [IN]: + lq_head : the handler of MESA_lqueue. + + [OUT]: + data : receive buffer. + + [IN $ OUT]: + data_len: is value-result argument, like "addrlen of recvfrom(2)" + the caller should initialize before the call to the size of the 'data', + and modified on return to indicate the actual size of the queue item. + +*/ +int MESA_lqueue_read_head(MESA_lqueue_head head, void *data, long *data_len) +{ + return __MESA_lqueue_read_head(head, data, data_len, MESA_list_BOLCK); +} + +int MESA_lqueue_try_read_head(MESA_lqueue_head head, void *data, long *data_len) +{ + return __MESA_lqueue_read_head(head, data, data_len, MESA_list_NONBOLCK); +} + +/* + get_place: 1:head; 2:tail +*/ +static int MESA_q_get_v3(MESA_lqueue_head head, void *data, long *data_len, int get_place, int block) +{ + int ret; + MESA_list_index_v3_t *queue_node; + Inter_head_v3_t *queue_v3_handle = (Inter_head_v3_t *)head; + + if(unlikely((NULL == data) || (NULL == data_len))){ + ret = MESA_QUEUE_RET_ARG_ERR; + goto err_1; + } + + ret = __can_i_do_it(queue_v3_handle, MESA_list_GET, block); + if(unlikely(ret < 0)){ + goto err_1; + } + + if(MESA_list_count_is_empty((const struct MESA_list_count *)queue_v3_handle)){ + ret = MESA_QUEUE_RET_QEMPTY; + goto err_2; + } + + if(MESA_LIST_OP_PLACE_HEAD == get_place){ + queue_node = queue_v3_handle->nextele; + }else{ + queue_node = queue_v3_handle->preele; + } + if(queue_node->data_len > *data_len){ + ret = MESA_QUEUE_RET_LEN_ERR; + goto err_2; + } + memcpy(data, queue_node->data, queue_node->data_len); + *data_len = queue_node->data_len; + +#if 0 + if((queue_v3_handle->max_item_num != 0) + && (queue_v3_handle->cur_item_num >= queue_v3_handle->max_item_num)){ + pthread_cond_signal(&queue_v3_handle->producter_cond); + } +#endif + + queue_v3_handle->cur_item_num--; + + queue_v3_handle->mem_used -= queue_node->data_len; + + MESA_lqueue_del_node(queue_node); + + pthread_cond_signal(&queue_v3_handle->producter_cond); + + MESA_q_unlock_v3(queue_v3_handle); + return MESA_QUEUE_RET_OK; + +err_2: + MESA_q_unlock_v3(queue_v3_handle); +err_1: + return ret; +} + +int MESA_lqueue_detect_get_head(MESA_lqueue_head head, MESA_lqueue_cb_t cb, + void *data, long *data_len, void *arg) +{ + int ret; + int get_action = 0; + MESA_list_index_v3_t *queue_node; + Inter_head_v3_t *queue_v3_handle = (Inter_head_v3_t *)head; + + if((NULL==cb) || (NULL == data) || (NULL == data_len)){ + ret = MESA_QUEUE_RET_ARG_ERR; + goto err_1; + } + + ret = MESA_q_lock_v3(queue_v3_handle, MESA_list_BOLCK); + if(ret < 0){ + ret = MESA_QUEUE_RET_CANT_GET_LOCK; + goto err_1; + } + + if(MESA_list_count_is_empty((const struct MESA_list_count *)queue_v3_handle)){ + ret = MESA_QUEUE_RET_QEMPTY; + goto err_2; + } + + queue_node = queue_v3_handle->nextele; + + + if( cb(queue_node->data, queue_node->data_len, arg) != 0){ + get_action = 1; + } + + if(get_action){ + if(0 == queue_v3_handle->cur_item_num){ + ret = MESA_q_cond_wait_v3(queue_v3_handle, MESA_list_GET, MESA_list_BOLCK); + if(ret < 0){ + ret = MESA_QUEUE_RET_NUM_FULL; + goto err_2; + } + } +#if 0 + else if((queue_v3_handle->max_item_num != 0) + && (queue_v3_handle->cur_item_num >= queue_v3_handle->max_item_num)){ + pthread_cond_signal(&queue_v3_handle->producter_cond); + } +#endif + else{ + /* �ǿշ�������, do nothing! */ + } + + memcpy(data, queue_node->data, queue_node->data_len); + *data_len = queue_node->data_len; + + MESA_lqueue_del_node(queue_node); + queue_v3_handle->cur_item_num--; + queue_v3_handle->mem_used -= queue_node->data_len; + pthread_cond_signal(&queue_v3_handle->producter_cond); + } + + MESA_q_unlock_v3(queue_v3_handle); + return MESA_QUEUE_RET_OK; + +err_2: + MESA_q_unlock_v3(queue_v3_handle); +err_1: + return ret; +} + +int MESA_lqueue_get_head(MESA_lqueue_head head, void *data, long *data_len) +{ + return MESA_q_get_v3(head, data, data_len, MESA_LIST_OP_PLACE_HEAD, MESA_list_BOLCK); +} + +int MESA_lqueue_try_get_head(MESA_lqueue_head head, void *data, long *data_len) +{ + return MESA_q_get_v3(head, data, data_len, MESA_LIST_OP_PLACE_HEAD, MESA_list_NONBOLCK); +} + +int MESA_lqueue_get_tail(MESA_lqueue_head head, void *data, long *data_len) +{ + return MESA_q_get_v3(head, data, data_len, MESA_LIST_OP_PLACE_TAIL, MESA_list_BOLCK); +} + +int MESA_lqueue_try_get_tail(MESA_lqueue_head head, void *data, long *data_len) +{ + return MESA_q_get_v3(head, data, data_len, MESA_LIST_OP_PLACE_TAIL, MESA_list_NONBOLCK); +} + + +/* + join_place: 1:head; 2:tail +*/ +static int MESA_q_join_v3(MESA_lqueue_head head, const void *data, long data_len, int join_place, int block) +{ + int ret; + MESA_list_index_v3_t *queue_node; + Inter_head_v3_t *queue_v3_handle = (Inter_head_v3_t *)head; + + if(unlikely((NULL == data) || (data_len <= 0))){ + ret = MESA_QUEUE_RET_ARG_ERR; + goto err_1; + } + + ret = __can_i_do_it(queue_v3_handle, MESA_list_JOIN, block); + if(unlikely(ret < 0)){ + goto err_1; + } + + if((queue_v3_handle->max_item_num != 0) + && (queue_v3_handle->cur_item_num >= queue_v3_handle->max_item_num)){ + ret = MESA_QUEUE_RET_NUM_FULL; + goto err_2; + } + queue_node = (MESA_list_index_v3_t *)calloc(1, sizeof(MESA_list_index_v3_t)); + //memset(queue_node, 0, sizeof(MESA_list_index_v3_t)); + queue_node->data = malloc(data_len); + memcpy(queue_node->data, data, data_len); + queue_node->data_len = data_len; + queue_v3_handle->mem_used += data_len; + + if(MESA_LIST_OP_PLACE_HEAD == join_place){ + MESA_list_count_add((struct MESA_list_count *)head, (struct MESA_list_count *)queue_node); + }else{ + MESA_list_count_add_tail((struct MESA_list_count *)head, (struct MESA_list_count *)queue_node); + } + +#if 0 + if(0 == queue_v3_handle->cur_item_num){ + pthread_cond_signal(&queue_v3_handle->cond); + } +#endif + pthread_cond_signal(&queue_v3_handle->customer_cond); + + MESA_q_unlock_v3(queue_v3_handle); + + return MESA_QUEUE_RET_OK; + +err_2: + MESA_q_unlock_v3(queue_v3_handle); +err_1: + return ret; +} + + +int MESA_lqueue_join_head(MESA_lqueue_head head, const void *data, long data_len) +{ + return MESA_q_join_v3(head, data, data_len, MESA_LIST_OP_PLACE_HEAD, MESA_list_BOLCK); +} + +int MESA_lqueue_try_join_head(MESA_lqueue_head head, const void *data, long data_len) +{ + return MESA_q_join_v3(head, data, data_len, MESA_LIST_OP_PLACE_HEAD, MESA_list_NONBOLCK); +} + +int MESA_lqueue_join_tail(MESA_lqueue_head head, const void *data, long data_len) +{ + return MESA_q_join_v3(head, data, data_len, MESA_LIST_OP_PLACE_TAIL, MESA_list_BOLCK); +} + +int MESA_lqueue_try_join_tail(MESA_lqueue_head head, const void *data, long data_len) +{ + return MESA_q_join_v3(head, data, data_len, MESA_LIST_OP_PLACE_TAIL, MESA_list_NONBOLCK); +} + +MESA_lqueue_head MESA_lqueue_create(int thread_safe, long max_item_num) +{ + Inter_head_v3_t *queue_v3_handle; + + queue_v3_handle = (Inter_head_v3_t *)calloc(1, sizeof(Inter_head_v3_t)); + //memset(queue_v3_handle, 0, sizeof(Inter_head_v3_t)); + queue_v3_handle->thread_safe = thread_safe; + queue_v3_handle->max_item_num = max_item_num; + queue_v3_handle->cur_item_num = 0; + queue_v3_handle->mem_used = 0; + + if(thread_safe != 0){ + pthread_mutex_init(&queue_v3_handle->mutex, NULL); + //sem_init(&queue_v3_handle->empty_sem, 0, (unsigned int)max_item_num); + //sem_init(&queue_v3_handle->data_sem, 0, 0); + pthread_cond_init(&queue_v3_handle->customer_cond, NULL); + pthread_cond_init(&queue_v3_handle->producter_cond, NULL); + } + + MESA_list_count_init_head((struct MESA_list_count *)queue_v3_handle); + + return (void *)queue_v3_handle; +} + +void MESA_lqueue_destroy(MESA_lqueue_head head, MESA_lqueue_cb_t cb,void *arg) +{ + int ret; + MESA_list_index_v3_t *queue_node, *queue_next; + Inter_head_v3_t *queue_v3_handle = (Inter_head_v3_t *)head; + + if(queue_v3_handle->thread_safe){ + ret = pthread_mutex_lock(&queue_v3_handle->mutex); + if(ret != 0){ + goto err_1; + } + } + + if(MESA_list_count_is_empty((const struct MESA_list_count *)queue_v3_handle)){ + goto err_2; + } + + queue_node = (MESA_list_index_v3_t *)queue_v3_handle->nextele; + while((void *)queue_node != (void *)queue_v3_handle){ + queue_next = queue_node->nextele; + if(cb){ + cb(queue_node->data, queue_node->data_len, arg); + } + MESA_lqueue_del_node(queue_node); + queue_node = queue_next; + } + + MESA_q_unlock_v3(queue_v3_handle); + + if(queue_v3_handle->thread_safe){ + pthread_mutex_destroy(&queue_v3_handle->mutex); + //sem_destroy(&queue_v3_handle->empty_sem); + //sem_destroy(&queue_v3_handle->data_sem); + pthread_cond_destroy(&queue_v3_handle->customer_cond); + pthread_cond_destroy(&queue_v3_handle->producter_cond); + } + free(head); + return; + +err_2: + MESA_q_unlock_v3(queue_v3_handle); + if(queue_v3_handle->thread_safe){ + pthread_mutex_destroy(&queue_v3_handle->mutex); + pthread_cond_destroy(&queue_v3_handle->customer_cond); + pthread_cond_destroy(&queue_v3_handle->producter_cond); + } + free(head); +err_1: + return; +} + +const char *MESA_lqueue_strerror(MESA_queue_errno_t error_num) +{ + const char *msg; + + switch((int)error_num){ + case MESA_QUEUE_RET_OK: + msg = "success"; + break; + + case MESA_QUEUE_RET_COMMON_ERR: + msg = "general error"; + break; + + case MESA_QUEUE_RET_ARG_ERR: + msg = "arguments error"; + break; + + case MESA_QUEUE_RET_NUM_FULL: + msg = "queue number full"; + break; + + case MESA_QUEUE_RET_MEM_FULL: + msg = "queue memory full"; + break; + + case MESA_QUEUE_RET_QEMPTY: + msg = "queue empty"; + break; + + case MESA_QUEUE_RET_LEN_ERR: + msg = "length error"; + break; + + case MESA_QUEUE_RET_CANT_GET_LOCK: + msg = "get lock error"; + break; + + case MESA_QUEUE_RET_GET_LOCK_TMOUT: + msg = "get lock timeout"; + break; + + default: + msg = "Invalid error num"; + break; + } + + return msg; +} + +#ifdef __cplusplus +} +#endif + diff --git a/support/MESA_htable/src/MESA_ring_queue.c b/support/MESA_htable/src/MESA_ring_queue.c new file mode 100644 index 0000000..bcb340d --- /dev/null +++ b/support/MESA_htable/src/MESA_ring_queue.c @@ -0,0 +1,680 @@ +#ifdef __cplusplus +extern "C" +{ +#endif + +#include "MESA_ring_queue.h" +#include "MESA_list.h" +#include "MESA_atomic.h" +#include <stdio.h> +#include <string.h> +#include <stdlib.h> +#include <time.h> +#include <unistd.h> +#include <pthread.h> +#include <assert.h> +#include <linux/limits.h> +#include <sys/types.h> +#include <sys/stat.h> +#include <unistd.h> + + +const char * MESA_rqueue_version_VERSION_20160708 = "MESA_rqueue_version_VERSION_20160708"; +const unsigned int MESA_RING_QUEUE_VERSION_INT = 20160708; + +#define RQ_MULTI_LOCK_FREE_RESERVE_NUM (2) /* ���߳��������б���Ԫ������ */ + +/* + ��֤nextele��preeleλ�ò��䣬���Ը���list_common�еIJ��������� +*/ +typedef struct __mesa_rlist{ + struct __mesa_rlist *nextele; /* ����ָ�������ڽṹ��ǰ2λ, ����MESA_list���� */ + struct __mesa_rlist *preele; /* ����ָ�������ڽṹ��ǰ2λ, ����MESA_list���� */ + void *data; + long data_len; +}MESA_rlist_index_t; + +typedef struct { + struct __mesa_rlist *root; /* ���ζ��еĸ�ָ��, createʱ�����������ζ���, destroyʱʹ�� */ + struct __mesa_rlist *p_customer; /* ������ָ��, ָ�����һ�������ݵ�Ԫ��, ��ȡ���ݺ��ƶ� */ + struct __mesa_rlist *p_producter; /* ������ָ��, ִ���Ԫ��, �Ȳ�����ƶ� */ + union{ + volatile unsigned int cur_item_num; /* ��ǰʵ��Ԫ������ */ + MESA_ATOMIC_T cur_item_num_lock_free; /* ��ǰʵ��Ԫ������, ���߳�����ʵ�� */ + }; + volatile unsigned int ring_item_num; /* �������ζ��е����Ԫ������ */ + int thread_safe; + int multi_thread_lock_free; + int __pad[1]; + unsigned int pre_alloc_buf_len; /* ����8���ֽ���Ҫ�������ڴ�, С�ڵ���8�ֽ�, ֱ�Ӹ���dataָ��ռ� */ + pthread_mutex_t mutex; + pthread_cond_t customer_cond; + pthread_cond_t producter_cond; +}MESA_ring_inter_t; + + +static inline unsigned int __MESA_rq_cur_num_get(MESA_ring_inter_t *mesa_rq_handle) +{ + unsigned int res; + if(mesa_rq_handle->multi_thread_lock_free != 0){ + res = MESA_ATOMIC_READ(mesa_rq_handle->cur_item_num_lock_free); + }else{ + res = mesa_rq_handle->cur_item_num; + } + + return res; +} + +static inline void __MESA_rq_cur_num_set(MESA_ring_inter_t *mesa_rq_handle, unsigned int num) +{ + if(mesa_rq_handle->multi_thread_lock_free != 0){ + MESA_ATOMIC_SET(mesa_rq_handle->cur_item_num_lock_free, num); + }else{ + mesa_rq_handle->cur_item_num = num; + } + + return; +} + +static inline void __MESA_rq_cur_num_inc(MESA_ring_inter_t *mesa_rq_handle) +{ + if(mesa_rq_handle->multi_thread_lock_free != 0){ + MESA_ATOMIC_INC(mesa_rq_handle->cur_item_num_lock_free); + }else{ + mesa_rq_handle->cur_item_num++; + } + + return ; +} + +static inline void __MESA_rq_cur_num_dec(MESA_ring_inter_t *mesa_rq_handle) +{ + if(mesa_rq_handle->multi_thread_lock_free != 0){ + MESA_ATOMIC_DEC(mesa_rq_handle->cur_item_num_lock_free); + }else{ + mesa_rq_handle->cur_item_num--; + } + + return ; +} + +static void __MESA_rq_set_default_opt(MESA_ring_inter_t *mesa_rq_handle) +{ + mesa_rq_handle->thread_safe = 1; /* Ĭ��Ϊ�̰߳�ȫģʽ, ʲô����¶����� */ + mesa_rq_handle->ring_item_num = 10000; + mesa_rq_handle->pre_alloc_buf_len = 0; /* Ĭ��Ϊ��ָ�뷽ʽ, ����������ռ� */ + mesa_rq_handle->multi_thread_lock_free = 0; +} + +static int __MESA_rq_opt_check(MESA_ring_inter_t *mesa_rq_handle) +{ + if((0 != mesa_rq_handle->thread_safe) + &&(0 != mesa_rq_handle->multi_thread_lock_free)){ + printf("\033[41mMESA_ring_queue opt conflict! thread_safe is %d, and multi_thread_lock_free is:%d!\033[0m\n", + mesa_rq_handle->thread_safe, mesa_rq_handle->multi_thread_lock_free); + return -1; + } + + return 0; +} + + +static void __MESA_rq_create_ring(MESA_ring_inter_t *mesa_rq_handle) +{ + int i; + struct __mesa_rlist *ring_item; + + if(mesa_rq_handle->pre_alloc_buf_len > sizeof(void *)){ + mesa_rq_handle->root->data = malloc(mesa_rq_handle->pre_alloc_buf_len); + } + + for(i = 0; i < mesa_rq_handle->ring_item_num; i++){ + ring_item = malloc(sizeof(struct __mesa_rlist)); + if(mesa_rq_handle->pre_alloc_buf_len > sizeof(void *)){ + ring_item->data = malloc(mesa_rq_handle->pre_alloc_buf_len); + } + ring_item->data_len = 0; + + MESA_list_add((struct MESA_list *)mesa_rq_handle->root, (struct MESA_list *)ring_item); + } + + mesa_rq_handle->p_customer = mesa_rq_handle->root; + mesa_rq_handle->p_producter = mesa_rq_handle->root; + + __MESA_rq_cur_num_set(mesa_rq_handle, 0); + + return; +} + +static int __MESA_rq_lock(MESA_ring_inter_t *mesa_rq_handle, int block) +{ + int ret = MESA_RQUEUE_RET_OK; + + if(mesa_rq_handle->thread_safe){ + if(block){ + ret = pthread_mutex_lock(&mesa_rq_handle->mutex); + if(ret != 0){ + ret = MESA_RQUEUE_RET_CANT_GET_LOCK; + } + }else{ + ret = pthread_mutex_trylock(&mesa_rq_handle->mutex); + if(ret != 0){ + ret = MESA_RQUEUE_RET_CANT_GET_LOCK; + } + } + }else{ + ret = MESA_RQUEUE_RET_OK; + } + + return ret; +} + +static int __MESA_rq_unlock(MESA_ring_inter_t *mesa_rq_handle) +{ + int ret = MESA_RQUEUE_RET_OK; + + if(mesa_rq_handle->thread_safe){ + ret = pthread_mutex_unlock(&mesa_rq_handle->mutex); + if(ret != 0){ + ret = MESA_RQUEUE_RET_CANT_GET_LOCK; + } + }else{ + ret = MESA_RQUEUE_RET_OK; + } + + return ret; +} + +static int __MESA_rq_wait(MESA_ring_inter_t *mesa_rq_handle, int op_get, int block) +{ + int ret = -1; + + if(mesa_rq_handle->multi_thread_lock_free != 0){ + if(block){ + if(op_get){ + while(__MESA_rq_cur_num_get(mesa_rq_handle) <= RQ_MULTI_LOCK_FREE_RESERVE_NUM){ + usleep(1); + } + }else{ + while(__MESA_rq_cur_num_get(mesa_rq_handle) >= mesa_rq_handle->ring_item_num-RQ_MULTI_LOCK_FREE_RESERVE_NUM){ + usleep(1); + } + } + }else{ + ret = -1; + } + }else{ + if(mesa_rq_handle->thread_safe){ + if(block){ + if(op_get != 0){ + ret = pthread_cond_wait(&mesa_rq_handle->customer_cond, &mesa_rq_handle->mutex); + }else{ + ret = pthread_cond_wait(&mesa_rq_handle->producter_cond, &mesa_rq_handle->mutex); + } + if(ret != 0){ + ret = -1; + } + }else{ /* ������ģʽ��, ֱ�ӷ���ʧ�� */ + ret = -1; + } + }else{ + /* ���̰߳�ȫʽ��, ��Ϊ�ǵ��̴߳���, ��������������, ֱ�ӷ���ʧ��, */ + ret = -1; + } + } + + return ret; +} + + +static int __rq_can_i_do_it(MESA_ring_inter_t *mesa_rq_handle, int op_get, int block) +{ + int ret = MESA_RQUEUE_RET_OK; + unsigned cur_rqitem_num; + + ret = __MESA_rq_lock(mesa_rq_handle, block); + if(ret < 0){ + ret = MESA_RQUEUE_RET_CANT_GET_LOCK; + goto err1; + } + + cur_rqitem_num = __MESA_rq_cur_num_get(mesa_rq_handle); + + if(0 == op_get){ /* join */ + if(mesa_rq_handle->multi_thread_lock_free != 0){ + if(cur_rqitem_num >= mesa_rq_handle->ring_item_num-RQ_MULTI_LOCK_FREE_RESERVE_NUM){ /* �������й̶�����2�����ϵ�Ԫ��, ��ָ֤�벻��ͻ */ + ret = __MESA_rq_wait(mesa_rq_handle, op_get, block); + if(ret < 0){ + ret = MESA_RQUEUE_RET_NUM_FULL; + goto err2; + } + }else{ + ret = MESA_RQUEUE_RET_OK; + } + }else{ + if(cur_rqitem_num >= mesa_rq_handle->ring_item_num){ + ret = __MESA_rq_wait(mesa_rq_handle, op_get, block); + if(ret < 0){ + ret = MESA_RQUEUE_RET_NUM_FULL; + goto err2; + } + }else{ + ret = MESA_RQUEUE_RET_OK; + } + } + }else{ /* get */ + if(mesa_rq_handle->multi_thread_lock_free != 0){ + if(cur_rqitem_num <= RQ_MULTI_LOCK_FREE_RESERVE_NUM){ /* �������й̶�����2�����ϵ�Ԫ��, ��ָ֤�벻��ͻ */ + ret = __MESA_rq_wait(mesa_rq_handle, op_get, block); + if(ret < 0){ + ret = MESA_RQUEUE_RET_QEMPTY; + goto err2; + } + }else{ + ret = MESA_RQUEUE_RET_OK; + } + }else{ + if(0 == cur_rqitem_num){ + ret = __MESA_rq_wait(mesa_rq_handle, op_get, block); + if(ret < 0){ + ret = MESA_RQUEUE_RET_QEMPTY; + goto err2; + } + }else{ + ret = MESA_RQUEUE_RET_OK; + } + } + } + + return ret; + +err2: + __MESA_rq_unlock(mesa_rq_handle); +err1: + return ret; +} + + +static int __MESA_rq_read(MESA_ring_inter_t *mesa_rq_handle, void *data, int *data_len, int block) +{ + int ret = MESA_RQUEUE_RET_OK; + int item_data_len; + + ret = __rq_can_i_do_it(mesa_rq_handle, 1, block); + if(ret < 0){ + goto err1; + } + + if(mesa_rq_handle->p_customer == mesa_rq_handle->p_producter){ + ret = MESA_RQUEUE_RET_QEMPTY; + goto err2; + } + + item_data_len = mesa_rq_handle->p_customer->data_len; + if(*data_len < item_data_len){ + ret = MESA_RQUEUE_RET_LEN_ERR; + goto err2; + } + if(item_data_len <= sizeof(void *)){ + memcpy(data, &mesa_rq_handle->p_customer->data, item_data_len); + }else{ + memcpy(data, mesa_rq_handle->p_customer->data, item_data_len); + } + *data_len = item_data_len; + __MESA_rq_unlock(mesa_rq_handle); + + return ret; + +err2: + __MESA_rq_unlock(mesa_rq_handle); +err1: + return ret; +} + + +static int __MESA_rq_get(MESA_ring_inter_t *mesa_rq_handle, void *data, int *data_len, int block) +{ + int ret = MESA_RQUEUE_RET_OK; + int item_data_len; + + ret = __rq_can_i_do_it(mesa_rq_handle, 1 ,block); + if(ret < 0){ + goto err1; + } + + if(mesa_rq_handle->p_customer == mesa_rq_handle->p_producter){ + ret = MESA_RQUEUE_RET_QEMPTY; + goto err2; + } + + item_data_len = mesa_rq_handle->p_customer->data_len; + if(*data_len < item_data_len){ + ret = MESA_RQUEUE_RET_LEN_ERR; + goto err2; + } + if(mesa_rq_handle->pre_alloc_buf_len > sizeof(void *)){ + memcpy(data, mesa_rq_handle->p_customer->data, item_data_len); + }else{ + if(item_data_len <= sizeof(void *)){ + + memcpy(data, &mesa_rq_handle->p_customer->data, item_data_len); + }else{ + memcpy(data, mesa_rq_handle->p_customer->data, item_data_len); + } + } + *data_len = item_data_len; + + if((0 == mesa_rq_handle->pre_alloc_buf_len) + && (item_data_len > sizeof(void *))){ + free(mesa_rq_handle->p_customer->data); + } + + mesa_rq_handle->p_customer = mesa_rq_handle->p_customer->nextele; + //mesa_rq_handle->cur_item_num--; + __MESA_rq_cur_num_dec(mesa_rq_handle); + + pthread_cond_signal(&mesa_rq_handle->producter_cond); + + __MESA_rq_unlock(mesa_rq_handle); + + return ret; + +err2: + __MESA_rq_unlock(mesa_rq_handle); +err1: + return ret; +} + + +static int __MESA_rq_join(MESA_ring_inter_t *mesa_rq_handle, const void *data, int data_len, int block) +{ + int ret = MESA_RQUEUE_RET_OK; + + ret = __rq_can_i_do_it(mesa_rq_handle, 0, block); + if(ret < 0){ + goto err1; + } + + if(mesa_rq_handle->p_producter->nextele == mesa_rq_handle->p_customer){ + ret = MESA_RQUEUE_RET_NUM_FULL; + goto err2; + } + + if(mesa_rq_handle->pre_alloc_buf_len > sizeof(void *)){ + if(data_len > mesa_rq_handle->pre_alloc_buf_len){ + ret = MESA_RQUEUE_RET_LEN_ERR; + goto err2; + } + + memcpy(mesa_rq_handle->p_producter->data, data, data_len); + }else{ + if(data_len > sizeof(void *)){ + /* δԤ�ȷ���, �ռ䲻��, ��ʱ���� */ + mesa_rq_handle->p_producter->data = malloc(data_len); + memcpy(mesa_rq_handle->p_producter->data, data, data_len); + }else{ + memcpy(&mesa_rq_handle->p_producter->data, data, data_len); + } + } + mesa_rq_handle->p_producter->data_len = data_len; + mesa_rq_handle->p_producter = mesa_rq_handle->p_producter->nextele; + //mesa_rq_handle->cur_item_num++; + __MESA_rq_cur_num_inc(mesa_rq_handle); + + if(mesa_rq_handle->thread_safe != 0){ + pthread_cond_signal(&mesa_rq_handle->customer_cond); + } + + __MESA_rq_unlock(mesa_rq_handle); + + return ret; + +err2: + __MESA_rq_unlock(mesa_rq_handle); +err1: + return ret; +} + + + + +MESA_ring_queue_head MESA_ring_queue_born(void) +{ + MESA_ring_inter_t *mesa_rq_handle = (MESA_ring_inter_t *)calloc(1, sizeof(MESA_ring_inter_t)); + + __MESA_rq_set_default_opt(mesa_rq_handle); + + return (void *)mesa_rq_handle; +} + + +int MESA_ring_queue_set_opt(MESA_ring_queue_head rq, enum MESA_rq_opt opt_type, void *opt_val, int opt_len) +{ + assert(rq != NULL); + + int ret = 0; + MESA_ring_inter_t *mesa_rq_handle = (MESA_ring_inter_t *)rq; + + switch(opt_type){ + case RQO_THREAD_SAFE: + mesa_rq_handle->thread_safe = *((int *)opt_val); + break; + + case RQO_RING_ELEMENT_NUM: + mesa_rq_handle->ring_item_num = *((unsigned int *)opt_val); + break; + + case RQO_PRE_ALLOC_BUF_LEN: + mesa_rq_handle->pre_alloc_buf_len = *((unsigned int *)opt_val); + break; + + case RQO_MULTI_THREAD_LOCK_FREE: + mesa_rq_handle->multi_thread_lock_free = *((int *)opt_val); + break; + + default: + ret = -1; + break; + } + + return ret; +} + + +int MESA_ring_queue_mature(MESA_ring_queue_head rq) +{ + MESA_ring_inter_t *mesa_rq_handle = (MESA_ring_inter_t *)rq; + + assert(rq != NULL); + + if(__MESA_rq_opt_check(mesa_rq_handle) < 0){ + return -1; + } + + if(mesa_rq_handle->thread_safe){ + pthread_mutex_init(&mesa_rq_handle->mutex, NULL); + pthread_cond_init(&mesa_rq_handle->customer_cond, NULL); + pthread_cond_init(&mesa_rq_handle->producter_cond, NULL); + } + + mesa_rq_handle->root = calloc(1, sizeof(struct __mesa_rlist)); + + MESA_list_init_head((struct MESA_list *)mesa_rq_handle->root); + + __MESA_rq_create_ring(mesa_rq_handle); + + return 0; +} + + +int MESA_ring_queue_get_count(MESA_ring_queue_head rq) +{ + MESA_ring_inter_t *mesa_rq_handle = (MESA_ring_inter_t *)rq; + int cur_num; + + if(mesa_rq_handle->multi_thread_lock_free){ + cur_num = MESA_ATOMIC_READ(mesa_rq_handle->cur_item_num_lock_free); + }else{ + if(mesa_rq_handle->thread_safe){ + pthread_mutex_lock(&mesa_rq_handle->mutex); + cur_num = mesa_rq_handle->cur_item_num; + pthread_mutex_unlock(&mesa_rq_handle->mutex); + }else{ + cur_num = mesa_rq_handle->cur_item_num; + } + } + + return cur_num; +} + + + + +int MESA_ring_queue_read(MESA_ring_queue_head rq_head, void *data, int *data_len) +{ + assert(rq_head && data && data_len); + + return __MESA_rq_read(rq_head, data, data_len, 1); +} + + +int MESA_ring_queue_try_read(MESA_ring_queue_head rq_head, void *data, int *data_len) +{ + assert(rq_head && data && data_len); + + return __MESA_rq_read(rq_head, data, data_len, 0); +} + +int MESA_ring_queue_get(MESA_ring_queue_head rq_head, void *data, int *data_len) +{ + assert(rq_head && data && data_len); + + return __MESA_rq_get(rq_head, data, data_len, 1); +} + + +int MESA_ring_queue_try_get(MESA_ring_queue_head rq_head, void *data, int *data_len) +{ + assert(rq_head && data && data_len); + + return __MESA_rq_get(rq_head, data, data_len, 0); +} + + +int MESA_ring_queue_join(MESA_ring_queue_head rq_head, const void *data, int data_len) +{ + assert(rq_head && data && (data_len > 0)); + + return __MESA_rq_join(rq_head, data, data_len, 1); +} + + +int MESA_ring_queue_try_join(MESA_ring_queue_head rq_head, const void *data, int data_len) +{ + assert(rq_head && data && (data_len > 0)); + + return __MESA_rq_join(rq_head, data, data_len, 0); +} + + +void MESA_ring_queue_destroy(MESA_ring_queue_head rq_head, MESA_rqueue_cb_t cb, void *cb_arg) +{ + MESA_ring_inter_t *mesa_rq_handle = (MESA_ring_inter_t *)rq_head; + struct __mesa_rlist *p_customer, *p_producter, *item, *next; + + __MESA_rq_lock(mesa_rq_handle, 1); + + p_customer = mesa_rq_handle->p_customer; + p_producter = mesa_rq_handle->p_producter; + + while(p_customer != p_producter){ + item = p_customer->nextele; + if(p_customer->data_len > sizeof(void *)){ + if(cb){ + (*cb)(p_customer->data, p_customer->data_len, cb_arg); + } + free(p_customer->data); + }else{ + if(cb){ + (*cb)(&p_customer->data, p_customer->data_len, cb_arg); + } + } + p_customer = item; + } + + item = mesa_rq_handle->root->nextele; + while(item != mesa_rq_handle->root){ + next = item->nextele; + if(mesa_rq_handle->pre_alloc_buf_len > sizeof(void *)){ + free(item->data); + } + free(item); + item = next; + } + + if(mesa_rq_handle->pre_alloc_buf_len > sizeof(void *)){ + free(mesa_rq_handle->root->data); + } + free(mesa_rq_handle->root); + + pthread_mutex_destroy(&mesa_rq_handle->mutex); + pthread_cond_destroy(&mesa_rq_handle->customer_cond); + pthread_cond_destroy(&mesa_rq_handle->producter_cond); + + free(mesa_rq_handle); + + return; +} + +const char *MESA_ring_queue_strerror(MESA_ring_queue_errno_t error_num) +{ + const char *msg; + + switch((int)error_num){ + case MESA_RQUEUE_RET_OK: + msg = "success"; + break; + + case MESA_RQUEUE_RET_COMMON_ERR: + msg = "general error"; + break; + + case MESA_RQUEUE_RET_ARG_ERR: + msg = "arguments error"; + break; + + case MESA_RQUEUE_RET_NUM_FULL: + msg = "queue number full"; + break; + + case MESA_RQUEUE_RET_MEM_FULL: + msg = "queue memory full"; + break; + + case MESA_RQUEUE_RET_QEMPTY: + msg = "queue empty"; + break; + + case MESA_RQUEUE_RET_LEN_ERR: + msg = "length error"; + break; + + case MESA_RQUEUE_RET_CANT_GET_LOCK: + msg = "get lock error"; + break; + + case MESA_RQUEUE_RET_GET_LOCK_TMOUT: + msg = "get lock timeout"; + break; + + default: + msg = "Invalid error num"; + break; + } + + return msg; +} + +#ifdef __cplusplus +} +#endif diff --git a/support/MESA_htable/src/Makefile b/support/MESA_htable/src/Makefile new file mode 100644 index 0000000..4307e7a --- /dev/null +++ b/support/MESA_htable/src/Makefile @@ -0,0 +1,29 @@ +CC=gcc +CCC=g++ + +CFLAGS=-g -Wall -fPIC -shared -D_XOPEN_SOURCE=500 -D__USE_GNU=1 -D_GNU_SOURCE=1 +LIBPATH=../lib +H_DIR=-I../include + +OBJS=MESA_htable.o MESA_list_queue.o MESA_list.o MESA_list_count.o MESA_ring_queue.o + +TARGET=libMESA_htable.a libMESA_htable.so + +all:$(TARGET) + +.c.o: + $(CC) -c $(CFLAGS) -I. $(H_DIR) $< + +.cpp.o: + $(CCC) -c $(CFLAGS) -I. $(H_DIR) $< + +libMESA_htable.a: $(OBJS) + #echo making static lib ... + (rm -f $@ ;ar -r $@ $^; cp $@ $(LIBPATH);) + +libMESA_htable.so: $(OBJS) + #echo making dynamic lib ... + (rm -f $@; gcc -o $@ $(CFLAGS) $^; cp $@ $(LIBPATH);) + +clean: + rm -f *.o $(TARGET) |
