diff options
Diffstat (limited to 'test')
27 files changed, 4317 insertions, 907 deletions
diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt index 07c1456..d41aac2 100644 --- a/test/CMakeLists.txt +++ b/test/CMakeLists.txt @@ -2,7 +2,7 @@ set(DECODER_NAME http_decoder) aux_source_directory(${PROJECT_SOURCE_DIR}/deps/toml DEPS_SRC) -add_library(${DECODER_NAME}_test SHARED http_decoder_gtest.cpp md5.c ${DEPS_SRC}) +add_library(${DECODER_NAME}_test SHARED http_decoder_test_plug.cpp md5.c ${DEPS_SRC}) add_dependencies(${DECODER_NAME}_test ${DECODER_NAME}) target_link_libraries(${DECODER_NAME}_test MESA_prof_load cjson-static) set_target_properties(${DECODER_NAME}_test PROPERTIES PREFIX "") @@ -25,5 +25,9 @@ aux_source_directory(${PROJECT_SOURCE_DIR}/deps/mempool PERF_TEST_DEP_SRC) aux_source_directory(${PROJECT_SOURCE_DIR}/deps/toml PERF_TEST_DEP_SRC) aux_source_directory(${PROJECT_SOURCE_DIR}/src PERF_TEST_DEP_SRC) -add_executable(httpd_perf_test ${PERF_TEST_DEP_SRC} http_decoder_perf_main.cpp http_decoder_perf_plug.cpp) +add_executable(httpd_perf_test ${PERF_TEST_DEP_SRC} http_decoder_perf_main.cpp http_decoder_perf_plug.cpp http_stellar_mock.cpp) target_link_libraries(httpd_perf_test z brotlidec llhttp-static fieldstat4 pthread) + + +add_executable(httpd_gtest http_decoder_gtest.cpp http_stellar_mock.cpp ${PROJECT_SOURCE_DIR}/src/http_decoder_utils.cpp) +target_link_libraries(httpd_gtest gtest) diff --git a/test/http_decoder_gtest.cpp b/test/http_decoder_gtest.cpp index 27fb0e6..c8ad653 100644 --- a/test/http_decoder_gtest.cpp +++ b/test/http_decoder_gtest.cpp @@ -1,592 +1,64 @@ -#include <stdio.h> -#include <time.h> +#include <gtest/gtest.h> #include <unistd.h> -#include <assert.h> -#include <string.h> - +#include <stdio.h> +#include "http_decoder.h" #include "http_decoder_inc.h" -#ifdef __cplusplus -extern "C" -{ -#include "cJSON.h" -#include "http_decoder_gtest.h" -#include "md5.h" -#include "toml/toml.h" - - int commit_test_result_json(cJSON *node, const char *name); - extern void http_decoder_test_entry(struct session *sess, int topic_id, const void *raw_msg, void *no_use_ctx, void *plugin_env); - extern void http_decoder_test_state_entry(struct session *sess, int topic_id, const void *raw_msg, void *no_use_ctx, void *plugin_env); - extern void http_decoder_tunnel_entry(struct session *sess, int topic_id, const void *raw_msg, void *no_use_ctx, void *plugin_env); - static on_session_msg_cb_func *g_entry_fun = http_decoder_test_entry; -} -#endif - -#define MAX_KEY_STR_LEN 2048 -#define GTEST_PLUG_ENTRY_CFG "./etc/http/gtest_entry.toml" - -struct plug_entry_t{ - const char *name; - on_session_msg_cb_func *entry; -}; - -static struct plug_entry_t g_entry_tbl[] = { - {"http_decoder_test_entry", http_decoder_test_entry}, - {"http_decoder_test_state_entry", http_decoder_test_state_entry}, - {"http_decoder_tunnel_entry", http_decoder_tunnel_entry}, - {NULL, NULL} -}; - -enum http_transaction_type -{ - HTTP_TRANSACTION_REQ = 0, - HTTP_TRANSACTION_RES, - HTTP_TRANSACTION_SESSION, // global session info - HTTP_TRANSACTION_MAX -}; - -struct gtest_plug_exdata_t -{ - cJSON *result_jnode[HTTP_TRANSACTION_MAX]; - MD5_CTX *md5ctx[HTTP_TRANSACTION_MAX]; -}; - -static int g_result_count = 0; -static int g_header_count = 1; -static int g_http_gtest_plugin_id = -1; -static int g_exdata_idx = -1; -static int g_topic_id = -1; - - - -#if 0 -void output_http_req_line(struct http_request_line *req_line) -{ - char tmp_str[MAX_KEY_STR_LEN] = {0}; - memcpy(tmp_str, req_line->method.iov_base, req_line->method.iov_len); - printf("req_method:%s\n", tmp_str); - - memset(tmp_str, 0, sizeof(tmp_str)); - memcpy(tmp_str, req_line->uri.iov_base, req_line->uri.iov_len); - printf("req_uri:%s\n", tmp_str); - - memset(tmp_str, 0, sizeof(tmp_str)); - memcpy(tmp_str, req_line->version.iov_base, req_line->version.iov_len); - printf("req_version:%s\n", tmp_str); -} - -void output_http_res_line(struct http_response_line *res_line) -{ - char tmp_str[MAX_KEY_STR_LEN] = {0}; - memcpy(tmp_str, res_line->version.iov_base, res_line->version.iov_len); - printf("res_version:%s\n", tmp_str); - - memset(tmp_str, 0, sizeof(tmp_str)); - memcpy(tmp_str, res_line->status.iov_base, res_line->status.iov_len); - printf("res_status:%s\n", tmp_str); -} - -void output_http_header(struct http_header *header) +void httpd_url_decode(const char *string, size_t length, char *ostring, size_t *olen); +TEST(url_decoder, none) { - char tmp_key[MAX_KEY_STR_LEN] = {0}; - char tmp_val[MAX_KEY_STR_LEN] = {0}; + char decode_url_buf[2048]; + size_t decode_url_len = sizeof(decode_url_buf); + const char *encode_url = "https://docs.geedge.net/#all-updates"; + httpd_url_decode(encode_url, strlen(encode_url), decode_url_buf, &decode_url_len); - memcpy(tmp_key, header->key.iov_base, header->key.iov_len); - memcpy(tmp_val, header->val.iov_base, header->val.iov_len); - printf("<%s:%s>\n", tmp_key, tmp_val); + EXPECT_STREQ("https://docs.geedge.net/#all-updates", decode_url_buf); + EXPECT_EQ(decode_url_len, strlen("https://docs.geedge.net/#all-updates")); } -void output_http_body(hstring *body, int decompress_flag) +TEST(url_decoder, simple) { - int counter = 0; + char decode_url_buf[2048]; + size_t decode_url_len = sizeof(decode_url_buf); + const char *encode_url = "http://a.b.cn/%A1%B2%C3%D4"; + httpd_url_decode(encode_url, strlen(encode_url), decode_url_buf, &decode_url_len); - if (1 == decompress_flag) - { - printf("\n\n----------------decompress body len:%zu---------------\n", - body->iov_len); - } - else - { - printf("\n\n----------------raw body len:%zu---------------\n", - body->iov_len); - } - - for (size_t i = 0; i < body->iov_len; i++) - { - if (counter % 16 == 0) - { - printf("\n"); - } - printf("%02x ", (unsigned char)body->iov_base[i]); - counter++; - } - printf("\n"); -} -#endif - -static void append_http_payload(struct session *sess, struct gtest_plug_exdata_t *gtest_plug_exdata, const hstring *body, enum http_transaction_type type) -{ - if (NULL == body->iov_base || 0 == body->iov_len) - { - return; - } - if (NULL == gtest_plug_exdata->md5ctx[type]) - { - gtest_plug_exdata->md5ctx[type] = MMALLOC(MD5_CTX, sizeof(MD5_CTX)); - MD5Init(gtest_plug_exdata->md5ctx[type]); - } - MD5Update(gtest_plug_exdata->md5ctx[type], (unsigned char *)body->iov_base, body->iov_len); + const unsigned char expect_result[] = + {0x68, 0x74, 0x74, 0x70, + 0x3A, 0x2F, 0x2F, 0x61, + 0x2E, 0x62, 0x2E, 0x63, + 0x6E, 0x2F, 0xA1, 0xB2, + 0xC3, 0xD4, 0x00 + }; + EXPECT_STREQ((char *)expect_result, decode_url_buf); + EXPECT_EQ(decode_url_len, sizeof(expect_result)-1); } -int http_field_to_json(cJSON *object, const char *key, char *val, size_t val_len) +TEST(url_decoder, chinese1) { - if (NULL == object || NULL == key || NULL == val || 0 == val_len) - { - return -1; - } + char decode_url_buf[2048]; + size_t decode_url_len = sizeof(decode_url_buf); + const char *encode_url = "http://www.baidu.com/%E6%B5%8B%E8%AF%95%E4%B8%AD%E6%96%87%E8%A7%A3%E7%A0%81"; + httpd_url_decode(encode_url, strlen(encode_url), decode_url_buf, &decode_url_len); - char *tmp = CALLOC(char, val_len + 1); - memcpy(tmp, val, val_len); - cJSON_AddStringToObject(object, key, tmp); - FREE(tmp); - - return 0; + EXPECT_STREQ("http://www.baidu.com/\xE6\xB5\x8B\xE8\xAF\x95\xE4\xB8\xAD\xE6\x96\x87\xE8\xA7\xA3\xE7\xA0\x81", decode_url_buf); + EXPECT_EQ(decode_url_len, strlen("http://www.baidu.com/\xE6\xB5\x8B\xE8\xAF\x95\xE4\xB8\xAD\xE6\x96\x87\xE8\xA7\xA3\xE7\xA0\x81")); } -void transaction_index_to_json(cJSON *ctx, int transaction_index) +TEST(url_decoder, chinese2) { - cJSON_AddNumberToObject(ctx, GTEST_HTTP_TRANS_SEQ_NAME, transaction_index); -} + char decode_url_buf[2048]; + size_t decode_url_len = sizeof(decode_url_buf); + const char *encode_url = "http%3A%2F%2Fwww.baidu.com%2F%E7%BC%96%E8%A7%A3%E7%A0%81%E6%B5%8B%E8%AF%95%E5%93%88%E5%93%88"; + httpd_url_decode(encode_url, strlen(encode_url), decode_url_buf, &decode_url_len); -void req_line_to_json(cJSON *ctx, struct http_request_line *req_line) -{ - http_field_to_json(ctx, "method", (char *)req_line->method.iov_base, - req_line->method.iov_len); - http_field_to_json(ctx, "uri", (char *)req_line->uri.iov_base, req_line->uri.iov_len); - http_field_to_json(ctx, "req_version", (char *)req_line->version.iov_base, - req_line->version.iov_len); - - cJSON_AddNumberToObject(ctx, "major_version", req_line->major_version); - cJSON_AddNumberToObject(ctx, "minor_version", req_line->minor_version); -} - -void res_line_to_json(cJSON *ctx, struct http_response_line *res_line) -{ - http_field_to_json(ctx, "res_version", (char *)res_line->version.iov_base, - res_line->version.iov_len); - http_field_to_json(ctx, "res_status", (char *)res_line->status.iov_base, - res_line->status.iov_len); - - cJSON_AddNumberToObject(ctx, "major_version", res_line->major_version); - cJSON_AddNumberToObject(ctx, "minor_version", res_line->minor_version); - cJSON_AddNumberToObject(ctx, "status_code", res_line->status_code); + EXPECT_STREQ("http://www.baidu.com/\xE7\xBC\x96\xE8\xA7\xA3\xE7\xA0\x81\xE6\xB5\x8B\xE8\xAF\x95\xE5\x93\x88\xE5\x93\x88", decode_url_buf); + EXPECT_EQ(decode_url_len, strlen("http://www.baidu.com/\xE7\xBC\x96\xE8\xA7\xA3\xE7\xA0\x81\xE6\xB5\x8B\xE8\xAF\x95\xE5\x93\x88\xE5\x93\x88")); } -void http_header_to_json(cJSON *ctx, struct http_header *header) -{ - char key[MAX_KEY_STR_LEN] = {0}; - assert(header->key.iov_base); - assert(header->val.iov_base); - - memcpy(key, header->key.iov_base, header->key.iov_len); - - if (cJSON_HasObjectItem(ctx, key) == FALSE) - { - http_field_to_json(ctx, key, (char *)header->val.iov_base, header->val.iov_len); - } - else - { - // ctx already has the key, so rename key by key%d - char new_key[MAX_KEY_STR_LEN] = {0}; - sprintf(new_key, "%s%d", key, g_header_count++); - http_field_to_json(ctx, new_key, (char *)header->val.iov_base, header->val.iov_len); - } -} -void http_url_add_to_json(cJSON *ctx, struct http_message *msg) +int main(int argc, char const *argv[]) { - hstring url_result = {}; - - if (cJSON_GetObjectItem(ctx, GTEST_HTTP_URL_NAME)) - { - return; - } - - http_message_get_url(msg, &url_result); - if(url_result.iov_base == NULL) - { - // printf("url:%s\n", url_result.iov_base); - return; - } - - struct http_header url_header_result = {}; - - url_header_result.key.iov_base = (char *)GTEST_HTTP_URL_NAME; - url_header_result.key.iov_len = strlen(GTEST_HTTP_URL_NAME); - url_header_result.val = url_result; - - http_header_to_json(ctx, &url_header_result); + ::testing::InitGoogleTest(&argc, (char **)argv); + return RUN_ALL_TESTS(); } - -// Full duplex -static void commit_last_half_flow_data(struct session *sess, struct gtest_plug_exdata_t *gtest_plug_exdata, - struct http_message *msg, enum http_transaction_type type, int final) -{ - char result_name[MAX_KEY_STR_LEN] = {0}; - - cJSON *last_jnode = gtest_plug_exdata->result_jnode[type]; - if (last_jnode) - { - // finish md5 streming hash - if (gtest_plug_exdata->md5ctx[type]) - { - unsigned char md5_result_bin[16] = {0}; - unsigned char md5_result_cstr[33] = {0}; - MD5Final(md5_result_bin, gtest_plug_exdata->md5ctx[type]); - - for (int i = 0; i < 16; i++) - sprintf((char *)md5_result_cstr + 2 * i, "%02x", md5_result_bin[i]); - md5_result_cstr[32] = '\0'; - - cJSON_AddStringToObject(last_jnode, GTEST_HTTP_PAYLOAD_MD5_NAME, (char *)md5_result_cstr); - FREE(gtest_plug_exdata->md5ctx[type]); - gtest_plug_exdata->md5ctx[type] = NULL; - } - - sprintf(result_name, "%d", g_result_count); - commit_test_result_json(last_jnode, result_name); - gtest_plug_exdata->result_jnode[type] = NULL; - g_result_count++; - } - - if(0 == final){ - gtest_plug_exdata->result_jnode[type] = cJSON_CreateObject(); - if (HTTP_TRANSACTION_REQ == type) - { - cJSON_AddStringToObject(gtest_plug_exdata->result_jnode[type], GTEST_HTTP_TRANS_NAME, "request"); - } - else if (HTTP_TRANSACTION_RES == type) - { - cJSON_AddStringToObject(gtest_plug_exdata->result_jnode[type], GTEST_HTTP_TRANS_NAME, "response"); - } - if (msg) - { - transaction_index_to_json(gtest_plug_exdata->result_jnode[type], http_message_get_transaction_seq(msg)); - } - } -} - -static void http_decoder_test_update_session_tuple4(struct session *sess, struct gtest_plug_exdata_t *gtest_plug_exdata) -{ - if (gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_SESSION] == NULL) - { - const char *human_addr_cstr = session_get0_readable_addr(sess); - if(NULL == human_addr_cstr){ - fprintf(stderr, "can't get readable_addr, to use session_get0_readable_addr() the sapp_log.conf level must <= INFO\n"); - return; - } - char result_name[MAX_KEY_STR_LEN] = {0}; - gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_SESSION] = cJSON_CreateObject(); - cJSON_AddStringToObject(gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_SESSION], GTEST_HTTP_TUPLE4_NAME, human_addr_cstr); - sprintf(result_name, "%d", g_result_count++); - commit_test_result_json(gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_SESSION], result_name); - } -} - -static int get_gtest_plug_entry(const char *cfg_path, char *entry_name, int max_len, char *topic_name, int topic_max_len) -{ - FILE *fp = fopen(cfg_path, "r"); - if (NULL == fp) - { - fprintf(stderr, "[%s:%d]Can't open config file:%s", - __FUNCTION__, __LINE__, cfg_path); - return -1; - } - - int ret = 0; - char errbuf[256] = {0}; - - toml_table_t *root = toml_parse_file(fp, errbuf, sizeof(errbuf)); - fclose(fp); - - toml_table_t *basic_sec_tbl = toml_table_in(root, "entry"); - if (NULL == basic_sec_tbl) - { - fprintf(stderr, "[%s:%d]config file:%s has no key: [entry]", - __FUNCTION__, __LINE__, cfg_path); - toml_free(root); - return -1; - } - - toml_datum_t str_val = toml_string_in(basic_sec_tbl, "name"); - if (str_val.ok != 0) - { - strncpy(entry_name, str_val.u.s, max_len); - free(str_val.u.s); - } - - toml_datum_t topic_str_val = toml_string_in(basic_sec_tbl, "topic"); - if (str_val.ok != 0) - { - strncpy(topic_name, topic_str_val.u.s, topic_max_len); - free(topic_str_val.u.s); - } - - toml_free(root); - return 0; -} - -static void set_gtest_plug_entry(const char *entry_name) -{ - if(NULL == entry_name){ - g_entry_fun = http_decoder_test_entry; //set default - return; - } - for (size_t i = 0; g_entry_tbl[i].name != NULL; i++) - { - if(strcmp(entry_name, g_entry_tbl[i].name) == 0){ - g_entry_fun = g_entry_tbl[i].entry; - return; - } - } - g_entry_fun = http_decoder_test_entry; //set default -} - -extern "C" void http_decoder_test_entry(struct session *sess, int topic_id, const void *raw_msg, void *no_use_ctx, void *plugin_env) -{ - struct http_request_line req_line = {0}; - struct http_response_line res_line = {0}; - struct http_header header = {0}; - hstring body = {0}; - struct http_message *msg = (struct http_message *)raw_msg; - enum http_message_type msg_type = http_message_type_get(msg); - - struct gtest_plug_exdata_t *gtest_plug_exdata = (struct gtest_plug_exdata_t *)session_exdata_get(sess, g_exdata_idx); - if (NULL == gtest_plug_exdata) - { - gtest_plug_exdata = (struct gtest_plug_exdata_t *)calloc(1, sizeof(struct gtest_plug_exdata_t)); - session_exdata_set(sess, g_exdata_idx, gtest_plug_exdata); - } - - if (http_message_type_is_req(sess, msg_type)) - { - cJSON *json = gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_REQ]; - } - else - { - cJSON *json = gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_RES]; - } - - http_decoder_test_update_session_tuple4(sess, gtest_plug_exdata); - - switch (msg_type) - { - case HTTP_MESSAGE_REQ_LINE: - commit_last_half_flow_data(sess, gtest_plug_exdata, msg, HTTP_TRANSACTION_REQ, 0); - http_message_get_request_line(msg, &req_line); - req_line_to_json(gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_REQ], &req_line); - break; - case HTTP_MESSAGE_REQ_HEADER: - while (http_message_header_next(msg, &header) >= 0) - { - http_header_to_json(gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_REQ], &header); - } - g_header_count = 1; - http_url_add_to_json(gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_REQ], msg); - break; - case HTTP_MESSAGE_REQ_BODY: - // http_message_get_request_raw_body(msg, &body); - // output_http_body(&body, 0); - http_message_get_decompress_body(msg, &body); - // output_http_body(&body, 1); - append_http_payload(sess, gtest_plug_exdata, &body, HTTP_TRANSACTION_REQ); - break; - case HTTP_MESSAGE_RES_LINE: - commit_last_half_flow_data(sess, gtest_plug_exdata, msg, HTTP_TRANSACTION_RES, 0); - http_message_get_response_line(msg, &res_line); - res_line_to_json(gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_RES], &res_line); - break; - case HTTP_MESSAGE_RES_HEADER: - while (http_message_header_next(msg, &header) >= 0) - { - http_header_to_json(gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_RES], &header); - } - g_header_count = 1; - break; - case HTTP_MESSAGE_RES_BODY: - // http_message_get_response_raw_body(msg, &body); - // output_http_body(&body, 0); - http_message_get_decompress_body(msg, &body); - // output_http_body(&body, 1); - append_http_payload(sess, gtest_plug_exdata, &body, HTTP_TRANSACTION_RES); - break; - - // to do: check payload - default: - break; - } - - return; -} - -void http_decoder_test_exdata_free(struct session *sess, int idx, void *ex_ptr, void *arg) -{ - if (ex_ptr != NULL) - { - struct gtest_plug_exdata_t *gtest_plug_exdata = (struct gtest_plug_exdata_t *)ex_ptr; - if (gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_REQ]) - { - commit_last_half_flow_data(sess, gtest_plug_exdata, NULL, HTTP_TRANSACTION_REQ, 1); - } - if (gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_RES]) - { - commit_last_half_flow_data(sess, gtest_plug_exdata, NULL, HTTP_TRANSACTION_RES, 1); - } - free(ex_ptr); - } -} - -static int update_config_file(const char *filename, const char *key, const char *value) -{ - char cmd_buf[1024] = {}; - snprintf(cmd_buf, 1024, "sed 's/^[ \t]*%s=.*/%s=%s/g' -i %s", key, key, value, filename); - int ret = system(cmd_buf); - return ret; -} - -extern "C" void http_decoder_test_state_entry(struct session *sess, int topic_id, const void *raw_msg, void *no_use_ctx, void *plugin_env) -{ - static int msg_index = 0; - char msg_index_name[64] = {}; - char msg_index_value[64] = {}; - cJSON *json_object = NULL; - enum http_message_type msg_type = http_message_type_get((struct http_message *)raw_msg); - - struct gtest_plug_exdata_t *gtest_plug_exdata = (struct gtest_plug_exdata_t *)session_exdata_get(sess, g_exdata_idx); - if (NULL == gtest_plug_exdata) - { - gtest_plug_exdata = (struct gtest_plug_exdata_t *)calloc(1, sizeof(struct gtest_plug_exdata_t)); - gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_REQ] = cJSON_CreateObject(); - gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_RES] = cJSON_CreateObject(); - session_exdata_set(sess, g_exdata_idx, gtest_plug_exdata); - } - - if (http_message_type_is_req(sess, msg_type)){ - json_object = gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_REQ]; - }else{ - json_object = gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_RES]; - } - if(HTTP_TRANSACTION_FREE == msg_type){ - unsigned char flow_flag; - session_is_symmetric(sess, &flow_flag); - if(SESSION_SEEN_C2S_FLOW == flow_flag){ - json_object = gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_REQ]; - } - else if(SESSION_SEEN_S2C_FLOW == flow_flag){ - json_object = gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_RES]; - }else{ // is symmetric - json_object = gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_RES]; - } - } - int cur_transaction_id = http_message_get_transaction_seq((const http_message* )raw_msg); - - if(HTTP_TRANSACTION_NEW ==msg_type || HTTP_TRANSACTION_FREE == msg_type){ - snprintf(msg_index_name, sizeof(msg_index_name), "msg_%d", msg_index++); - snprintf(msg_index_value, sizeof(msg_index_value), "%s_transaction_%d", http_message_type_to_string(msg_type), cur_transaction_id); - cJSON_AddStringToObject(json_object, msg_index_name, msg_index_value); - }else{ - snprintf(msg_index_name, sizeof(msg_index_name), "msg_%d", msg_index++); - cJSON_AddStringToObject(json_object, msg_index_name, http_message_type_to_string(msg_type)); - } - return; -} - -extern "C" void http_decoder_tunnel_entry(struct session *sess, int topic_id, const void *raw_msg, void *no_use_ctx, void *plugin_env) -{ - struct gtest_plug_exdata_t *gtest_plug_exdata; - enum http_tunnel_message_type tmsg_type = http_tunnel_message_type_get((const struct http_tunnel_message *)raw_msg); - static size_t req_payload_block = 0, req_payload_size = 0; - static size_t res_payload_block = 0, res_payload_size = 0; - gtest_plug_exdata = (struct gtest_plug_exdata_t *)session_exdata_get(sess, g_exdata_idx); - - switch(tmsg_type){ - case HTTP_TUNNEL_OPENING: - { - if (NULL == gtest_plug_exdata) - { - gtest_plug_exdata = (struct gtest_plug_exdata_t *)calloc(1, sizeof(struct gtest_plug_exdata_t)); - session_exdata_set(sess, g_exdata_idx, gtest_plug_exdata); - } - const char *human_addr_cstr = session_get0_readable_addr(sess); - gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_REQ] = cJSON_CreateObject(); - gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_RES] = cJSON_CreateObject(); - gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_SESSION] = cJSON_CreateObject(); - cJSON_AddStringToObject(gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_SESSION], GTEST_HTTP_TUPLE4_NAME, human_addr_cstr); - commit_test_result_json(gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_SESSION], "TUNNEL_NEW"); - } - // OPENING state has payload, go on - - case HTTP_TUNNEL_ACTIVE: - { - int curdir = packet_get_direction(session_get0_current_packet(sess)); - hstring tunnel_payload = {}; - http_tunnel_message_get_payload((const struct http_tunnel_message *)raw_msg, &tunnel_payload); - if(PACKET_DIRECTION_C2S == curdir){ - req_payload_block++; - req_payload_size += tunnel_payload.iov_len; - }else{ - res_payload_block++; - res_payload_size += tunnel_payload.iov_len; - } - } - break; - case HTTP_TUNNEL_CLOSING: - { - cJSON_AddStringToObject(gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_REQ], "flow", "C2S"); - cJSON_AddStringToObject(gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_RES], "flow", "S2C"); - cJSON_AddNumberToObject(gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_REQ], "payload_block", req_payload_block); - cJSON_AddNumberToObject(gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_REQ], "payload_size", req_payload_size); - cJSON_AddNumberToObject(gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_RES], "payload_block", res_payload_block); - cJSON_AddNumberToObject(gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_RES], "payload_size", res_payload_size); - } - break; - default: - assert(0); - break; - } -} - -extern "C" void *http_decoder_test_init(struct stellar *st) -{ - g_http_gtest_plugin_id = stellar_session_plugin_register(st, NULL, NULL, NULL); - g_exdata_idx = stellar_session_exdata_new_index(st, "HTTP_DECODER_GTEST_EXDATA",http_decoder_test_exdata_free, NULL); - if (g_exdata_idx < 0) - { - printf("[%s:%d]: can't get http_decoder exdata index !!!\n", __FUNCTION__, __LINE__); - return NULL; - } - - char entry_name[64] = ""; - char topic_name[64] = ""; - get_gtest_plug_entry(GTEST_PLUG_ENTRY_CFG, entry_name, sizeof(entry_name)-1, topic_name, sizeof(topic_name)-1); - set_gtest_plug_entry(entry_name); - g_topic_id = stellar_session_mq_get_topic_id(st, topic_name); - if (g_topic_id < 0) - { - printf("[%s:%d]: can't get http_decoder topic:%s id !!!\n", __FUNCTION__, __LINE__, topic_name); - return NULL; - } - stellar_session_mq_subscribe(st, g_topic_id, g_entry_fun, g_http_gtest_plugin_id); - printf("http_decoder_gtest_init succ, plugin_id:%d, sub_topic_id:%d\n", g_http_gtest_plugin_id, g_topic_id); - - return (void *)strdup("http_decoder_test_ctx"); -} - -extern "C" void http_decoder_test_exit(void *test_ctx) -{ - if (test_ctx != NULL) - { - FREE(test_ctx); - } - printf("http_decoder_test_exit OK!\n"); -}
\ No newline at end of file diff --git a/test/http_decoder_gtest.h b/test/http_decoder_gtest.h index c413d08..d620972 100644 --- a/test/http_decoder_gtest.h +++ b/test/http_decoder_gtest.h @@ -1,7 +1,16 @@ #pragma once +#ifdef __cplusplus +extern "C" +{ +#endif +#include <stellar/session.h> +#include <stellar/session_mq.h> +#include <stellar/session_exdata.h> +#include <stellar/stellar.h> +#ifdef __cplusplus +} +#endif #include "http_decoder.h" -#include "stellar/session.h" -#include "stellar/session_mq.h" #include "md5.h" #include <stdint.h> #include <stdlib.h> @@ -46,4 +55,11 @@ #define GTEST_HTTP_TRANS_SEQ_NAME "__X_HTTP_TRANSACTION_SEQ" #define GTEST_HTTP_TUPLE4_NAME "__X_HTTP_TUPLE4" #define GTEST_HTTP_PAYLOAD_NAME "__X_HTTP_PAYLOAD" -#define GTEST_HTTP_PAYLOAD_MD5_NAME "__X_HTTP_PAYLOAD_MD5"
\ No newline at end of file +#define GTEST_HTTP_PAYLOAD_MD5_NAME "__X_HTTP_PAYLOAD_MD5" + +struct stellar *stellar_init(void); +void stellar_destroy(struct stellar *st); +int stellar_load_plugin(struct stellar *st, void *(plugin_init_cb)(struct stellar *st)); +struct session *stellar_session_new(struct stellar *st, int topic_id, const char *payload, size_t payload_len, u_int8_t dir); +void stellar_session_active(struct stellar *st, struct session *sess, int topic_id, const char *payload, size_t payload_len, u_int8_t dir); +void stellar_session_close(struct stellar *st, struct session *sess, int topic_id);
\ No newline at end of file diff --git a/test/http_decoder_perf_main.cpp b/test/http_decoder_perf_main.cpp index bd82b18..c567d5a 100644 --- a/test/http_decoder_perf_main.cpp +++ b/test/http_decoder_perf_main.cpp @@ -1,18 +1,30 @@ +#ifdef __cplusplus +extern "C" +{ +#endif +#include <stellar/session.h> +#include <stellar/session_mq.h> +#include <stellar/session_exdata.h> +#include <stellar/stellar.h> +#ifdef __cplusplus +} +#endif #include <stdio.h> #include <stdlib.h> #include <string.h> -#include <assert.h> +#include <unistd.h> #include <time.h> -#include "http_decoder_inc.h" +#include <fieldstat/fieldstat_easy.h> +#include "http_decoder_gtest.h" #define TIME_MEASURE 1 #if TIME_MEASURE -#define TIME_START() struct timespec _start_time, _end_time; clock_gettime(CLOCK_REALTIME, &_start_time) +#define TIME_START() struct timespec _start_time, _end_time; long long time_diff_ns; clock_gettime(CLOCK_REALTIME, &_start_time) +#define TIME_UPDATE() clock_gettime(CLOCK_REALTIME, &_start_time) #define TIME_DIFF() \ - long long time_diff_ns;\ do { \ clock_gettime(CLOCK_REALTIME, &_end_time); \ - if (likely(_end_time.tv_sec == _start_time.tv_sec))\ + if (_end_time.tv_sec == _start_time.tv_sec)\ {\ time_diff_ns = (_end_time.tv_nsec - _start_time.tv_nsec);\ }else{\ @@ -24,40 +36,12 @@ #define TIME_DIFF() #endif -static struct http_topic_exdata_compose g_topic_exdata_set[] = -{ - {HTTPD_TOPIC_TCP_STREAM_INDEX, TOPIC_TCP_STREAM, NULL, NULL, "HTTP_DECODER_EXDATA_BASEON_TCP_STREAM", NULL, 0, 0}, - {HTTPD_TOPIC_HTTP_MSG_INDEX, HTTP_DECODER_TOPIC, NULL, NULL, NULL, NULL, 1, 1}, - {HTTPD_TOPIC_HTTP_TUNNEL_INDEX, HTTP_DECODER_TUNNEL_TOPIC, NULL, NULL, "HTTP_DECODER_EXDATA_BASEON_HTTP_TUNNEL", NULL, 2, 2}, -}; - -struct packet{ +struct test_packet{ const char *payload; size_t payload_len; u_int8_t dir; }; - -struct stellar{ - int plugin_id; - void *plugin_env; - int exdata_id; - void *exdata; - int consumer_topid_id; - int publish_topic_id; - session_exdata_free *free_func; - session_msg_free_cb_func *publish_msg_free_cb; -}; - -struct session{ - struct stellar *st; - enum session_state sess_state; - struct session_addr addr; - void *context; - void *exdata; - void *message; - const struct packet *current_payload_st; -}; - +extern "C" void *http_decoder_perf_plug_init(struct stellar *st); extern "C" void *http_decoder_init(struct stellar *st); extern "C" void http_decoder_exit(void *plugin_env); extern "C" void *httpd_session_ctx_new_cb(struct session *sess, void *plugin_env); @@ -66,204 +50,43 @@ extern "C" void http_decoder_tcp_stream_msg_cb(struct session *sess, int topic_i extern "C" void http_decoder_perf_entry(struct session *sess, int topic_id, const void *raw_msg, void *per_session_ctx, void *plugin_env); static struct fieldstat_easy *fs4_instance; -static struct fieldstat_tag FS4_SIMPLE_HISGRAM_TAG; static int fs4_simple_id; - -static struct fieldstat_tag FS4_LONG_LONG_URL_HISGRAM_TAG; static int fs4_long_long_url_id; - -static struct fieldstat_tag FS4_FRAG_HISGRAM_TAG; static int fs4_frag_id; -void stellar_session_plugin_dettach_current_session(struct session *sess) -{ - return; -} - -int stellar_session_mq_destroy_topic(struct stellar *st, int topic_id) -{ - return 0; -} -int stellar_get_worker_thread_num(struct stellar *st) -{ - return 1; -} -int stellar_get_current_thread_id(struct stellar *st) -{ - return 0; -} -int session_get_current_thread_id(struct session *sess) -{ - return 0; -} -int stellar_session_plugin_register(struct stellar *st, - session_ctx_new_func session_ctx_new, - session_ctx_free_func session_ctx_free, - void *plugin_env) -{ - return 0; -} -int stellar_session_exdata_new_index(struct stellar *st, const char *name, session_exdata_free *free_func,void *arg) -{ - st->free_func = free_func; - return 0; -} -int session_exdata_set(struct session *sess, int idx, void *ex_ptr) -{ - sess->exdata = ex_ptr; - return 0; -} -void *session_exdata_get(struct session *sess, int idx) -{ - return sess->exdata; -} - -enum session_state session_get_current_state(struct session *sess) -{ - return sess->sess_state; -} - -int stellar_session_mq_get_topic_id(struct stellar *st, const char *topic_name) +static void perf_test_loop(struct stellar *st, int tcp_stream_topic_id, struct test_packet *test_payload, int test_payload_index_max, int fs4_metric_id) { - // for(int i = 0; i < HTTPD_TOPIC_INDEX_MAX; i++){ - // if(strcmp(topic_name, "TCP_STREAM") == 0){ - // st->consumer_topid_id = g_topic_exdata_set[HTTPD_TOPIC_TCP_STREAM_INDEX].sub_topic_id; - // st->publish_topic_id = g_topic_exdata_set[HTTPD_TOPIC_HTTP_MSG_INDEX].sub_topic_id; - // } - // if(strcmp(topic_name, g_topic_exdata_set[i].topic_name) == 0){ - // return st->consumer_topid_id; - // } - // } - return -1; -} - -int stellar_session_mq_create_topic(struct stellar *st, const char *topic_name, session_msg_free_cb_func *msg_free_cb, void *msg_free_arg) -{ - - for(int i = 0; i < HTTPD_TOPIC_INDEX_MAX; i++){ - if(strcmp(topic_name, g_topic_exdata_set[i].topic_name) == 0){ - if(strcmp(topic_name, HTTP_DECODER_TOPIC) == 0){ - st->publish_msg_free_cb = msg_free_cb; - } - if(strcmp(topic_name, "TCP_STREAM") == 0){ - st->publish_topic_id = g_topic_exdata_set[HTTPD_TOPIC_HTTP_MSG_INDEX].sub_topic_id; - } - return g_topic_exdata_set[i].sub_topic_id; - } - } - return -1; -} -const char *session_get0_current_payload(struct session *sess, size_t *payload_len) -{ - const struct packet *test_payload = sess->current_payload_st; - *payload_len = test_payload->payload_len; - return test_payload->payload; -} - - -struct session_addr *session_get0_addr(struct session *sess, enum session_addr_type *addr_type) -{ - *addr_type = SESSION_ADDR_TYPE_IPV4_TCP; - return &sess->addr; -} - -int packet_get_direction(const struct packet *pkt) -{ - return pkt->dir; -} - -const struct packet *session_get0_current_packet(struct session *sess) -{ - return sess->current_payload_st; -} -int stellar_session_mq_subscribe(struct stellar *st, int topic_id, on_session_msg_cb_func *plugin_on_msg_cb, int plugin_id) -{ - return 0; -} -int session_mq_publish_message(struct session *sess, int topic_id, void *msg) -{ - if(topic_id == g_topic_exdata_set[HTTPD_TOPIC_HTTP_MSG_INDEX].sub_topic_id){ - http_decoder_perf_entry(sess, topic_id, msg, NULL, NULL); - //maybe generate many messages for one packet, so free msg immediately - sess->st->publish_msg_free_cb(sess, msg, NULL); - } - return 0; -} - -int session_is_symmetric(struct session *sess, unsigned char *flag) -{ - *flag = (SESSION_SEEN_C2S_FLOW | SESSION_SEEN_S2C_FLOW); - return 1; -} - -int session_mq_ignore_message(struct session *sess, int topic_id, int plugin_id) -{ - return 0; -} - -static void perf_test_init_per_session(struct session *sess) -{ - sess->context = httpd_session_ctx_new_cb(sess, sess->st->plugin_env); -} - -static void perf_test_free_per_session(struct session *sess) -{ - sess->st->free_func(sess, sess->st->exdata_id, sess->exdata, NULL); -} - -static void perf_test_loop(struct stellar *st, struct session *sess, struct packet *test_payload, int test_payload_index_max, const struct fieldstat_tag *tag, int fs4_metric_id) -{ - sess->current_payload_st = &test_payload[0]; - perf_test_init_per_session(sess); - sess->sess_state = SESSION_STATE_OPENING; + int idx = 0; + struct session *sess; TIME_START(); - - for(int i = 0; i < test_payload_index_max; i++) - { - sess->current_payload_st = &test_payload[i]; - http_decoder_tcp_stream_msg_cb(sess, g_topic_exdata_set[HTTPD_TOPIC_TCP_STREAM_INDEX].sub_topic_id, test_payload[i].payload, NULL, sess->st->plugin_env); + sess = stellar_session_new(st, tcp_stream_topic_id, test_payload[idx].payload, test_payload[idx].payload_len, test_payload[idx].dir); + idx++; + TIME_DIFF(); + fieldstat_easy_histogram_record(fs4_instance, 0, fs4_metric_id, NULL, 0, time_diff_ns); + + for(; idx < test_payload_index_max; idx++){ + TIME_UPDATE(); + stellar_session_active(st, sess, tcp_stream_topic_id, test_payload[idx].payload, test_payload[idx].payload_len, test_payload[idx].dir); TIME_DIFF(); - fieldstat_easy_histogram_record(fs4_instance, 0, fs4_metric_id, tag, 1, time_diff_ns); - sess->sess_state = SESSION_STATE_ACTIVE; + fieldstat_easy_histogram_record(fs4_instance, 0, fs4_metric_id, NULL, 0, time_diff_ns); } - sess->sess_state = SESSION_STATE_CLOSING; - perf_test_free_per_session(sess); -} -static void perf_test_load_plug(struct stellar *st) -{ - st->plugin_env = http_decoder_init(st); - assert(st->plugin_env != NULL); - return; -} - -static void perf_test_init(struct stellar *st, struct session *sess) -{ - memset(st, 0, sizeof(struct stellar)); - memset(sess, 0, sizeof(struct session)); - st->plugin_id = 0; - st->exdata_id = 0; - st->publish_topic_id = -1; //init - st->consumer_topid_id = 2; //init - perf_test_load_plug(st); - - sess->st = st; - sess->addr.ipv4.saddr = 0x01020304; - sess->addr.ipv4.daddr = 0x05060708; - sess->addr.ipv4.sport = 12345; - sess->addr.ipv4.dport = 80; + TIME_UPDATE(); + stellar_session_close(st, sess, tcp_stream_topic_id); + TIME_DIFF(); + fieldstat_easy_histogram_record(fs4_instance, 0, fs4_metric_id, NULL, 0, time_diff_ns); } #define SET_DATA_LENGTH_DIR(pkt_payload, cstr_in_heap, cur_dir, tmp_index) \ pkt_payload.payload = cstr_in_heap; \ - pkt_payload.payload_len = strlen(cstr_in_heap); \ + pkt_payload.payload_len = strlen(pkt_payload.payload); \ pkt_payload.dir = cur_dir;\ tmp_index++; -static void init_test_data_simple(struct packet *test_payload, int *index) +static void init_test_data_simple(struct test_packet *test_payload, int *index) { int tmp_index = 0; - const char *c2s_payload = "GET / HTTP/1.1\r\nHost: www.simple.com\r\nConnection: keep-alive\r\nCache-Control: max-age=0\r\nUpgrade-Insecure-Requests: 1\r\nUser-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/58.0.3029.110 Safari/537.36 Edge/16.16299\r\nAccept: text/html,application/xhtml+xml,application/xml;q=0.9,image/webp,image/apng,*/*;q=0.8\r\nAccept-Encoding: gzip, deflate\r\nAccept-Language: zh-CN,zh;q=0.9\r\n\r\n"; + const char *c2s_payload = strdup("GET / HTTP/1.1\r\nHost: www.simple.com\r\nConnection: keep-alive\r\nCache-Control: max-age=0\r\nUpgrade-Insecure-Requests: 1\r\nUser-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/58.0.3029.110 Safari/537.36 Edge/16.16299\r\nAccept: text/html,application/xhtml+xml,application/xml;q=0.9,image/webp,image/apng,*/*;q=0.8\r\nAccept-Encoding: gzip, deflate\r\nAccept-Language: zh-CN,zh;q=0.9\r\n\r\n"); SET_DATA_LENGTH_DIR(test_payload[tmp_index], c2s_payload, PACKET_DIRECTION_C2S, tmp_index); const char *content = "Hello, http decoder perf test simple!!!"; @@ -272,65 +95,62 @@ static void init_test_data_simple(struct packet *test_payload, int *index) snprintf(s2c_payload, 1024, "HTTP/1.1 200 OK\r\nServer: Apache-Coyote/1.1\r\nConnection: keep-alive\r\nDate: Sat, 01 May 2024 01:36:57 GMT\r\nContent-Type: text/html;charset=UTF-8\r\nContent-Length: %d\r\n\r\n%s", content_length, content); SET_DATA_LENGTH_DIR(test_payload[tmp_index], s2c_payload, PACKET_DIRECTION_S2C, tmp_index); - *index = tmp_index; } -static void init_test_data_frag(struct packet *test_payload, int *index) +static void init_test_data_frag(struct test_packet *test_payload, int *index) { int tmp_index = 0; /* c2s */ - SET_DATA_LENGTH_DIR(test_payload[tmp_index], "GET / HTTP/1.1\r\n", PACKET_DIRECTION_C2S, tmp_index); - SET_DATA_LENGTH_DIR(test_payload[tmp_index], "Host: www.fragment.com\r\n", PACKET_DIRECTION_C2S, tmp_index); - SET_DATA_LENGTH_DIR(test_payload[tmp_index], "Cache-Control: max-age=0\r\n", PACKET_DIRECTION_C2S, tmp_index); - SET_DATA_LENGTH_DIR(test_payload[tmp_index], "Connection: keep-alive\r\n", PACKET_DIRECTION_C2S, tmp_index); - SET_DATA_LENGTH_DIR(test_payload[tmp_index], "Referer: http://fragment.com/register.jsp?redirect:http://aa.bb.cc.dd.com/?\r\n", PACKET_DIRECTION_C2S, tmp_index); - SET_DATA_LENGTH_DIR(test_payload[tmp_index], "User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/58.0.3029.110 Safari/537.36 Edge/16.16299\r\n", PACKET_DIRECTION_C2S, tmp_index); - SET_DATA_LENGTH_DIR(test_payload[tmp_index], "Cookie: JSESSIONID=385C79E211D561C0CA13D90F150F603D34875GH87FSHG8S7RTHG74875GHS8R7THG87SRTH\r\n", PACKET_DIRECTION_C2S, tmp_index); - SET_DATA_LENGTH_DIR(test_payload[tmp_index], "Accept: */*\r\n", PACKET_DIRECTION_C2S, tmp_index); - SET_DATA_LENGTH_DIR(test_payload[tmp_index], "Accept-Encoding: gzip, deflate\r\n", PACKET_DIRECTION_C2S, tmp_index); - SET_DATA_LENGTH_DIR(test_payload[tmp_index], "\r\n", PACKET_DIRECTION_C2S, tmp_index); //header EOF + SET_DATA_LENGTH_DIR(test_payload[tmp_index], strdup("GET / HTTP/1.1\r\n"), PACKET_DIRECTION_C2S, tmp_index); + SET_DATA_LENGTH_DIR(test_payload[tmp_index], strdup("Host: www.fragment.com\r\n"), PACKET_DIRECTION_C2S, tmp_index); + SET_DATA_LENGTH_DIR(test_payload[tmp_index], strdup("Cache-Control: max-age=0\r\n"), PACKET_DIRECTION_C2S, tmp_index); + SET_DATA_LENGTH_DIR(test_payload[tmp_index], strdup("Connection: keep-alive\r\n"), PACKET_DIRECTION_C2S, tmp_index); + SET_DATA_LENGTH_DIR(test_payload[tmp_index], strdup("Referer: http://fragment.com/register.jsp?redirect:http://aa.bb.cc.dd.com/?\r\n"), PACKET_DIRECTION_C2S, tmp_index); + SET_DATA_LENGTH_DIR(test_payload[tmp_index], strdup("User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/58.0.3029.110 Safari/537.36 Edge/16.16299\r\n"), PACKET_DIRECTION_C2S, tmp_index); + SET_DATA_LENGTH_DIR(test_payload[tmp_index], strdup("Cookie: JSESSIONID=385C79E211D561C0CA13D90F150F603D34875GH87FSHG8S7RTHG74875GHS8R7THG87SRTH\r\n"), PACKET_DIRECTION_C2S, tmp_index); + SET_DATA_LENGTH_DIR(test_payload[tmp_index], strdup("Accept: */*\r\n"), PACKET_DIRECTION_C2S, tmp_index); + SET_DATA_LENGTH_DIR(test_payload[tmp_index], strdup("Accept-Encoding: gzip, deflate\r\n"), PACKET_DIRECTION_C2S, tmp_index); + SET_DATA_LENGTH_DIR(test_payload[tmp_index], strdup("\r\n"), PACKET_DIRECTION_C2S, tmp_index); //header EOF /* s2c */ - SET_DATA_LENGTH_DIR(test_payload[tmp_index], "HTTP/1.1 200 OK\r\n", PACKET_DIRECTION_S2C, tmp_index); - SET_DATA_LENGTH_DIR(test_payload[tmp_index], "Server: Apache-Coyote/1.1\r\n", PACKET_DIRECTION_S2C, tmp_index); - SET_DATA_LENGTH_DIR(test_payload[tmp_index], "Connection: keep-alive\r\n", PACKET_DIRECTION_S2C, tmp_index); - SET_DATA_LENGTH_DIR(test_payload[tmp_index], "Content-Type: text/html;charset=UTF-8\r\n", PACKET_DIRECTION_S2C, tmp_index); - SET_DATA_LENGTH_DIR(test_payload[tmp_index], "Date: Sat, 01 May 2024 01:36:57 GMT\r\n", PACKET_DIRECTION_S2C, tmp_index); + SET_DATA_LENGTH_DIR(test_payload[tmp_index], strdup("HTTP/1.1 200 OK\r\n"), PACKET_DIRECTION_S2C, tmp_index); + SET_DATA_LENGTH_DIR(test_payload[tmp_index], strdup("Server: Apache-Coyote/1.1\r\n"), PACKET_DIRECTION_S2C, tmp_index); + SET_DATA_LENGTH_DIR(test_payload[tmp_index], strdup("Connection: keep-alive\r\n"), PACKET_DIRECTION_S2C, tmp_index); + SET_DATA_LENGTH_DIR(test_payload[tmp_index], strdup("Content-Type: text/html;charset=UTF-8\r\n"), PACKET_DIRECTION_S2C, tmp_index); + SET_DATA_LENGTH_DIR(test_payload[tmp_index], strdup("Date: Sat, 01 May 2024 01:36:57 GMT\r\n"), PACKET_DIRECTION_S2C, tmp_index); char *cont_len_buf = (char *)malloc(1024); - const char *s2c_payload = "Hello, http decoder perf test fragment!!!"; + const char *s2c_payload = strdup("Hello, http decoder perf test fragment!!!"); int content_length = strlen(s2c_payload); - snprintf(cont_len_buf, 1024, "Content-Length: %d\r\n\r\n", content_length); + snprintf(cont_len_buf, 1024, "Content-Length: %d\r\n", content_length); SET_DATA_LENGTH_DIR(test_payload[tmp_index], cont_len_buf, PACKET_DIRECTION_S2C, tmp_index); - SET_DATA_LENGTH_DIR(test_payload[tmp_index], "\r\n", PACKET_DIRECTION_S2C, tmp_index); //header EOF - + SET_DATA_LENGTH_DIR(test_payload[tmp_index], strdup("\r\n"), PACKET_DIRECTION_S2C, tmp_index); //header EOF SET_DATA_LENGTH_DIR(test_payload[tmp_index], s2c_payload, PACKET_DIRECTION_S2C, tmp_index); - *index = tmp_index; } -static void init_test_data_long_long_url(struct packet *test_payload, int *index) +static void init_test_data_long_long_url(struct test_packet *test_payload, int *index) { int tmp_index = 0; - const char *request_line_frag1 = "GET /long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/\ + const char *request_line_frag1 = strdup("GET /long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/\ /long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/\ /long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/\ /long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/\ /long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/\ /long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/\ /long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/\ -/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/"; +/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/"); SET_DATA_LENGTH_DIR(test_payload[tmp_index], request_line_frag1, PACKET_DIRECTION_C2S, tmp_index); - const char *request_line_frag2 = "long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/\ + const char *request_line_frag2 = strdup("long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/\ /long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/\ -/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long.index.html HTTP/1.1\r\n"; +/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long/long.index.html HTTP/1.1\r\n"); SET_DATA_LENGTH_DIR(test_payload[tmp_index], request_line_frag2, PACKET_DIRECTION_C2S, tmp_index); - const char *request_line_frag3 = "Host: www.long-long-url.com\r\nConnection: keep-alive\r\nCache-Control: max-age=0\r\nUpgrade-Insecure-Requests: 1\r\nUser-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/58.0.3029.110 Safari/537.36 Edge/16.16299\r\nAccept: text/html,application/xhtml+xml,application/xml;q=0.9,image/webp,image/apng,*/*;q=0.8\r\nAccept-Encoding: gzip, deflate\r\nAccept-Language: zh-CN,zh;q=0.9\r\n\r\n"; + const char *request_line_frag3 = strdup("Host: www.long-long-url.com\r\nConnection: keep-alive\r\nCache-Control: max-age=0\r\nUpgrade-Insecure-Requests: 1\r\nUser-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/58.0.3029.110 Safari/537.36 Edge/16.16299\r\nAccept: text/html,application/xhtml+xml,application/xml;q=0.9,image/webp,image/apng,*/*;q=0.8\r\nAccept-Encoding: gzip, deflate\r\nAccept-Language: zh-CN,zh;q=0.9\r\n\r\n"); SET_DATA_LENGTH_DIR(test_payload[tmp_index], request_line_frag3, PACKET_DIRECTION_C2S, tmp_index); const char *content = "Hello, http decoder perf test long long url!!!"; @@ -339,55 +159,68 @@ static void init_test_data_long_long_url(struct packet *test_payload, int *index snprintf(s2c_payload, 1024, "HTTP/1.1 200 OK\r\nServer: Apache-Coyote/1.1\r\nConnection: keep-alive\r\nDate: Sat, 01 May 2024 01:36:57 GMT\r\nContent-Type: text/html;charset=UTF-8\r\nContent-Length: %d\r\n\r\n%s", content_length, content); SET_DATA_LENGTH_DIR(test_payload[tmp_index], s2c_payload, PACKET_DIRECTION_S2C, tmp_index); - *index = tmp_index; } +static void test_payload_free(struct test_packet *test_payload, int test_payload_index_max) +{ + for(int i = 0; i < test_payload_index_max; i++){ + if(test_payload[i].payload){ + free((void *)test_payload[i].payload); + } + } +} + static void perf_stat_init(void) { fs4_instance = fieldstat_easy_new(1, "http_decoder_test", NULL, 0); fieldstat_easy_enable_auto_output(fs4_instance, "./httpd_hisgram.json", 1); - FS4_SIMPLE_HISGRAM_TAG.key = "simple"; - FS4_SIMPLE_HISGRAM_TAG.type = TAG_DOUBLE; - FS4_SIMPLE_HISGRAM_TAG.value_double = 0.00001; fs4_simple_id = fieldstat_easy_register_histogram(fs4_instance, "simple", 1, 99999999, 5); - - FS4_FRAG_HISGRAM_TAG.key = "frag"; - FS4_FRAG_HISGRAM_TAG.type = TAG_DOUBLE; - FS4_FRAG_HISGRAM_TAG.value_double = 0.00001; fs4_frag_id = fieldstat_easy_register_histogram(fs4_instance, "frag", 1, 99999999, 5); - - FS4_LONG_LONG_URL_HISGRAM_TAG.key = "long-url"; - FS4_LONG_LONG_URL_HISGRAM_TAG.type = TAG_DOUBLE; - FS4_LONG_LONG_URL_HISGRAM_TAG.value_double = 0.00001; fs4_long_long_url_id = fieldstat_easy_register_histogram(fs4_instance, "long-url", 1, 99999999, 5); } int main(int argc, char const *argv[]) { - struct stellar st; - struct session sess; - struct packet test_payload_simple [4] = {}; + struct test_packet test_payload_simple [4] = {}; int payload_index_simple = 0; - - struct packet test_payload_long_long_url [8] = {}; + struct test_packet test_payload_long_long_url [8] = {}; int payload_index_long_long_url = 0; - - struct packet test_payload_frag [32] = {}; + struct test_packet test_payload_frag [32] = {}; int payload_index_frag = 0; - perf_test_init(&st, &sess); - perf_stat_init(); + struct stellar *st = stellar_init(); + + int tcp_stream_topic_id = stellar_session_mq_get_topic_id(st, TOPIC_TCP_STREAM); + if(stellar_load_plugin(st, http_decoder_init) < 0){ + fprintf(stderr, "load plugin 'http_decoder_init' failed\n"); + return -1; + } + + if(stellar_load_plugin(st, http_decoder_perf_plug_init) < 0){ + fprintf(stderr, "load plugin 'http_decoder_perf_plug_init' failed\n"); + return -1; + } + + perf_stat_init(); init_test_data_simple(test_payload_simple, &payload_index_simple); init_test_data_long_long_url(test_payload_long_long_url, &payload_index_long_long_url); init_test_data_frag(test_payload_frag, &payload_index_frag); - while(1){ - perf_test_loop(&st, &sess, test_payload_simple, payload_index_simple, &FS4_SIMPLE_HISGRAM_TAG, fs4_simple_id); - perf_test_loop(&st, &sess, test_payload_long_long_url, payload_index_long_long_url, &FS4_LONG_LONG_URL_HISGRAM_TAG, fs4_long_long_url_id); - perf_test_loop(&st, &sess, test_payload_frag, payload_index_frag, &FS4_FRAG_HISGRAM_TAG, fs4_frag_id); + // while(1){ + for(int i = 0; i < 1000; i++){ + perf_test_loop(st, tcp_stream_topic_id,test_payload_simple, payload_index_simple, fs4_simple_id); + perf_test_loop(st, tcp_stream_topic_id,test_payload_long_long_url, payload_index_long_long_url, fs4_long_long_url_id); + perf_test_loop(st, tcp_stream_topic_id,test_payload_frag, payload_index_frag, fs4_frag_id); } + + test_payload_free(test_payload_simple, sizeof(test_payload_simple)/sizeof(struct test_packet)) ; + test_payload_free(test_payload_long_long_url, sizeof(test_payload_long_long_url)/sizeof(struct test_packet)) ; + test_payload_free(test_payload_frag, sizeof(test_payload_frag)/sizeof(struct test_packet)) ; + stellar_destroy(st); + sleep(1); + fieldstat_easy_free(fs4_instance); return 0; } diff --git a/test/http_decoder_perf_plug.cpp b/test/http_decoder_perf_plug.cpp index c8c8771..3a3d14a 100644 --- a/test/http_decoder_perf_plug.cpp +++ b/test/http_decoder_perf_plug.cpp @@ -1,3 +1,4 @@ +#include "http_decoder.h" #include <stdio.h> #include <time.h> #include <unistd.h> @@ -20,16 +21,15 @@ static int g_exdata_idx = -1; static int g_topic_id = -1; static int g_plugin_id = -1; -#define DEBUG_PRINT(fmt, ...) ///printf(fmt, ##__VA_ARGS__) +#define DEBUG_PRINT(fmt, ...) //printf(fmt, ##__VA_ARGS__) extern "C" void http_decoder_perf_entry(struct session *sess, int topic_id, const void *raw_msg, void *per_session_ctx, void *plugin_env) -// extern "C" int http_decoder_perf_entry(struct session *sess, int topic_id, const void *data, void *cb_arg) { struct http_request_line req_line = {0}; struct http_response_line res_line = {0}; struct http_header header = {0}; - hstring url = {0}; - hstring body = {0}; + hstring url = {}; + hstring body = {}; struct http_message *msg = (struct http_message *)raw_msg; enum http_message_type msg_type = http_message_type_get(msg); void *ret1, *ret2; @@ -38,7 +38,7 @@ extern "C" void http_decoder_perf_entry(struct session *sess, int topic_id, cons { case HTTP_MESSAGE_REQ_LINE: DEBUG_PRINT("---------------------------------------------------------------\n"); - http_message_get_request_line(msg, &req_line); + http_message_request_line_get0(msg, &req_line); if (req_line.uri.iov_base) { DEBUG_PRINT("req_line.method.iov_base: %.*s\n", req_line.method.iov_len, req_line.method.iov_base); @@ -53,7 +53,7 @@ extern "C" void http_decoder_perf_entry(struct session *sess, int topic_id, cons ret2 = memmem(header.val.iov_base, header.val.iov_len, "val", 3); DEBUG_PRINT("REQ header: %.*s : %.*s\n", (int)header.key.iov_len, header.key.iov_base, (int)header.val.iov_len, header.val.iov_base); } - http_message_get_url(msg, &url); + http_message_raw_url_get0(msg, &url); if(url.iov_base && url.iov_len){ DEBUG_PRINT("URL: %.*s\n", url.iov_len, url.iov_base); } @@ -61,12 +61,12 @@ extern "C" void http_decoder_perf_entry(struct session *sess, int topic_id, cons case HTTP_MESSAGE_REQ_BODY: // http_message_get_request_raw_body(msg, &body); // output_http_body(&body, 0); - http_message_get_decompress_body(msg, &body); + http_message_decompress_body_get0(msg, &body); // output_http_body(&body, 1); ret1 = memmem(body.iov_base, body.iov_len, "</html>", 7); break; case HTTP_MESSAGE_RES_LINE: - http_message_get_response_line(msg, &res_line); + http_message_response_line_get0(msg, &res_line); ret1 = memmem(res_line.status.iov_base, res_line.status.iov_len, "OK", 2); DEBUG_PRINT("res_line.status.iov_base: %.*s\n", (int)res_line.status.iov_len, res_line.status.iov_base); break; @@ -78,17 +78,22 @@ extern "C" void http_decoder_perf_entry(struct session *sess, int topic_id, cons DEBUG_PRINT("RES header: %.*s : %.*s\n", (int)header.key.iov_len, header.key.iov_base, (int)header.val.iov_len, header.val.iov_base); } break; + case HTTP_MESSAGE_RES_BODY_START: case HTTP_MESSAGE_RES_BODY: - http_message_get_raw_body(msg, &body); - DEBUG_PRINT("res raw body: %.*s\n", body.iov_len, body.iov_base); + case HTTP_MESSAGE_RES_BODY_END: + http_message_raw_body_get0(msg, &body); + if(body.iov_base!=NULL && body.iov_len > 0){ + DEBUG_PRINT("res raw body: %.*s\n", body.iov_len, body.iov_base); + } // output_http_body(&body, 0); - http_message_get_decompress_body(msg, &body); - // output_http_body(&body, 1); - ret1 = memmem(body.iov_base, body.iov_len, "</html>", 7); - DEBUG_PRINT("res unzip body: %.*s\n", body.iov_len, body.iov_base); - DEBUG_PRINT("---------------------------------------------------------------\n"); + http_message_decompress_body_get0(msg, &body); + if(body.iov_base!=NULL && body.iov_len > 0){ + // output_http_body(&body, 1); + ret1 = memmem(body.iov_base, body.iov_len, "</html>", 7); + DEBUG_PRINT("res unzip body: %.*s\n", body.iov_len, body.iov_base); + DEBUG_PRINT("---------------------------------------------------------------\n"); + } break; - // to do: check payload default: break; @@ -103,7 +108,7 @@ static void http_decoder_test_exdata_free(struct session *sess, int idx, void *e return; } -extern "C" void *http_decoder_perf_init(struct stellar *st) +extern "C" void *http_decoder_perf_plug_init(struct stellar *st) { g_plugin_id = stellar_session_plugin_register(st, NULL, NULL, NULL); g_exdata_idx = stellar_session_exdata_new_index(st, "HTTP_DECODER_REQ_TEST", @@ -128,7 +133,7 @@ extern "C" void *http_decoder_perf_init(struct stellar *st) return NULL; } -extern "C" void http_decoder_perf_exit(void *test_ctx) +extern "C" void http_decoder_perf_plug_exit(void *test_ctx) { if (test_ctx != NULL) { diff --git a/test/http_decoder_test_plug.cpp b/test/http_decoder_test_plug.cpp new file mode 100644 index 0000000..1ae9e51 --- /dev/null +++ b/test/http_decoder_test_plug.cpp @@ -0,0 +1,607 @@ +#include <stdio.h> +#include <time.h> +#include <unistd.h> +#include <assert.h> +#include <string.h> + +#include "http_decoder.h" +#include "http_decoder_inc.h" + +#ifdef __cplusplus +extern "C" +{ +#include "cJSON.h" +#include "http_decoder_gtest.h" +#include "md5.h" +#include "toml/toml.h" + + int commit_test_result_json(cJSON *node, const char *name); + extern void http_decoder_test_entry(struct session *sess, int topic_id, const void *raw_msg, void *no_use_ctx, void *plugin_env); + extern void http_decoder_test_state_entry(struct session *sess, int topic_id, const void *raw_msg, void *no_use_ctx, void *plugin_env); + extern void http_decoder_tunnel_entry(struct session *sess, int topic_id, const void *raw_msg, void *no_use_ctx, void *plugin_env); + static on_session_msg_cb_func *g_entry_fun = http_decoder_test_entry; +} +#endif + +#define MAX_KEY_STR_LEN 2048 +#define GTEST_PLUG_ENTRY_CFG "./etc/http/gtest_entry.toml" + +struct plug_entry_t{ + const char *name; + on_session_msg_cb_func *entry; +}; + +static struct plug_entry_t g_entry_tbl[] = { + {"http_decoder_test_entry", http_decoder_test_entry}, + {"http_decoder_test_state_entry", http_decoder_test_state_entry}, + {"http_decoder_tunnel_entry", http_decoder_tunnel_entry}, + {NULL, NULL} +}; + +enum http_transaction_type +{ + HTTP_TRANSACTION_REQ = 0, + HTTP_TRANSACTION_RES, + HTTP_TRANSACTION_SESSION, // global session info + HTTP_TRANSACTION_MAX +}; + +struct gtest_plug_exdata_t +{ + cJSON *result_jnode[HTTP_TRANSACTION_MAX]; + MD5_CTX *md5ctx[HTTP_TRANSACTION_MAX]; +}; + +static int g_result_count = 0; +static int g_header_count = 1; +static int g_http_gtest_plugin_id = -1; +static int g_exdata_idx = -1; +static int g_topic_id = -1; + + + +#if 0 +void output_http_req_line(struct http_request_line *req_line) +{ + char tmp_str[MAX_KEY_STR_LEN] = {0}; + memcpy(tmp_str, req_line->method.iov_base, req_line->method.iov_len); + printf("req_method:%s\n", tmp_str); + + memset(tmp_str, 0, sizeof(tmp_str)); + memcpy(tmp_str, req_line->uri.iov_base, req_line->uri.iov_len); + printf("req_uri:%s\n", tmp_str); + + memset(tmp_str, 0, sizeof(tmp_str)); + memcpy(tmp_str, req_line->version.iov_base, req_line->version.iov_len); + printf("req_version:%s\n", tmp_str); +} + +void output_http_res_line(struct http_response_line *res_line) +{ + char tmp_str[MAX_KEY_STR_LEN] = {0}; + memcpy(tmp_str, res_line->version.iov_base, res_line->version.iov_len); + printf("res_version:%s\n", tmp_str); + + memset(tmp_str, 0, sizeof(tmp_str)); + memcpy(tmp_str, res_line->status.iov_base, res_line->status.iov_len); + printf("res_status:%s\n", tmp_str); +} + +void output_http_header(struct http_header *header) +{ + char tmp_key[MAX_KEY_STR_LEN] = {0}; + char tmp_val[MAX_KEY_STR_LEN] = {0}; + + memcpy(tmp_key, header->key.iov_base, header->key.iov_len); + memcpy(tmp_val, header->val.iov_base, header->val.iov_len); + printf("<%s:%s>\n", tmp_key, tmp_val); +} + +void output_http_body(hstring *body, int decompress_flag) +{ + int counter = 0; + + if (1 == decompress_flag) + { + printf("\n\n----------------decompress body len:%zu---------------\n", + body->iov_len); + } + else + { + printf("\n\n----------------raw body len:%zu---------------\n", + body->iov_len); + } + + for (size_t i = 0; i < body->iov_len; i++) + { + if (counter % 16 == 0) + { + printf("\n"); + } + printf("%02x ", (unsigned char)body->iov_base[i]); + counter++; + } + printf("\n"); +} +#endif + +static void append_http_payload(struct session *sess, struct gtest_plug_exdata_t *gtest_plug_exdata, const hstring *body, enum http_transaction_type type) +{ + if (NULL == body->iov_base || 0 == body->iov_len) + { + return; + } + if (NULL == gtest_plug_exdata->md5ctx[type]) + { + gtest_plug_exdata->md5ctx[type] = MMALLOC(MD5_CTX, sizeof(MD5_CTX)); + MD5Init(gtest_plug_exdata->md5ctx[type]); + } + MD5Update(gtest_plug_exdata->md5ctx[type], (unsigned char *)body->iov_base, body->iov_len); +} + +int http_field_to_json(cJSON *object, const char *key, char *val, size_t val_len) +{ + if (NULL == object || NULL == key || NULL == val || 0 == val_len) + { + return -1; + } + + char *tmp = CALLOC(char, val_len + 1); + memcpy(tmp, val, val_len); + cJSON_AddStringToObject(object, key, tmp); + FREE(tmp); + + return 0; +} + +void transaction_index_to_json(cJSON *ctx, int transaction_index) +{ + cJSON_AddNumberToObject(ctx, GTEST_HTTP_TRANS_SEQ_NAME, transaction_index); +} + +void req_line_to_json(cJSON *ctx, struct http_request_line *req_line) +{ + http_field_to_json(ctx, "method", (char *)req_line->method.iov_base, + req_line->method.iov_len); + http_field_to_json(ctx, "uri", (char *)req_line->uri.iov_base, req_line->uri.iov_len); + http_field_to_json(ctx, "req_version", (char *)req_line->version.iov_base, + req_line->version.iov_len); + + cJSON_AddNumberToObject(ctx, "major_version", req_line->major_version); + cJSON_AddNumberToObject(ctx, "minor_version", req_line->minor_version); +} + +void res_line_to_json(cJSON *ctx, struct http_response_line *res_line) +{ + http_field_to_json(ctx, "res_version", (char *)res_line->version.iov_base, + res_line->version.iov_len); + http_field_to_json(ctx, "res_status", (char *)res_line->status.iov_base, + res_line->status.iov_len); + + cJSON_AddNumberToObject(ctx, "major_version", res_line->major_version); + cJSON_AddNumberToObject(ctx, "minor_version", res_line->minor_version); + cJSON_AddNumberToObject(ctx, "status_code", res_line->status_code); +} + +void http_header_to_json(cJSON *ctx, struct http_header *header) +{ + char key[MAX_KEY_STR_LEN] = {0}; + if((header->key.iov_base == NULL) || (header->val.iov_base == NULL)){ + return; + } + + memcpy(key, header->key.iov_base, header->key.iov_len); + + if (cJSON_HasObjectItem(ctx, key) == FALSE) + { + http_field_to_json(ctx, key, (char *)header->val.iov_base, header->val.iov_len); + } + else + { + // ctx already has the key, so rename key by key%d + char new_key[MAX_KEY_STR_LEN] = {0}; + sprintf(new_key, "%s%d", key, g_header_count++); + http_field_to_json(ctx, new_key, (char *)header->val.iov_base, header->val.iov_len); + } +} + +void http_url_add_to_json(cJSON *ctx, struct http_message *msg) +{ + hstring raw_url_result = {}; + + if (cJSON_GetObjectItem(ctx, GTEST_HTTP_URL_NAME)) + { + return; + } + + http_message_raw_url_get0(msg, &raw_url_result); + if(raw_url_result.iov_base == NULL) + { + return; + } + + struct http_header raw_url_header_result = {}; + + raw_url_header_result.key.iov_base = (char *)GTEST_HTTP_URL_NAME; + raw_url_header_result.key.iov_len = strlen(GTEST_HTTP_URL_NAME); + raw_url_header_result.val = raw_url_result; + + http_header_to_json(ctx, &raw_url_header_result); + + hstring decode_url_result = {}; + struct http_header decode_url_header_result = {}; + http_message_decoded_url_get0(msg, &decode_url_result); + if(decode_url_result.iov_len != raw_url_result.iov_len){ + decode_url_header_result.key.iov_base = (char *)"__X_HTTP_DECODED_URL"; + decode_url_header_result.key.iov_len = strlen("__X_HTTP_DECODED_URL"); + decode_url_header_result.val = decode_url_result; + http_header_to_json(ctx, &decode_url_header_result); + } +} + +// Full duplex +static void commit_last_half_flow_data(struct session *sess, struct gtest_plug_exdata_t *gtest_plug_exdata, + struct http_message *msg, enum http_transaction_type type, int final) +{ + char result_name[MAX_KEY_STR_LEN] = {0}; + + cJSON *last_jnode = gtest_plug_exdata->result_jnode[type]; + if (last_jnode) + { + // finish md5 streming hash + if (gtest_plug_exdata->md5ctx[type]) + { + unsigned char md5_result_bin[16] = {0}; + unsigned char md5_result_cstr[33] = {0}; + MD5Final(md5_result_bin, gtest_plug_exdata->md5ctx[type]); + + for (int i = 0; i < 16; i++) + sprintf((char *)md5_result_cstr + 2 * i, "%02x", md5_result_bin[i]); + md5_result_cstr[32] = '\0'; + + cJSON_AddStringToObject(last_jnode, GTEST_HTTP_PAYLOAD_MD5_NAME, (char *)md5_result_cstr); + FREE(gtest_plug_exdata->md5ctx[type]); + gtest_plug_exdata->md5ctx[type] = NULL; + } + + sprintf(result_name, "%d", g_result_count); + commit_test_result_json(last_jnode, result_name); + gtest_plug_exdata->result_jnode[type] = NULL; + g_result_count++; + } + + if(0 == final){ + gtest_plug_exdata->result_jnode[type] = cJSON_CreateObject(); + if (HTTP_TRANSACTION_REQ == type) + { + cJSON_AddStringToObject(gtest_plug_exdata->result_jnode[type], GTEST_HTTP_TRANS_NAME, "request"); + } + else if (HTTP_TRANSACTION_RES == type) + { + cJSON_AddStringToObject(gtest_plug_exdata->result_jnode[type], GTEST_HTTP_TRANS_NAME, "response"); + } + if (msg) + { + transaction_index_to_json(gtest_plug_exdata->result_jnode[type], http_message_get_transaction_seq(msg)); + } + } +} + +static void http_decoder_test_update_session_tuple4(struct session *sess, struct gtest_plug_exdata_t *gtest_plug_exdata) +{ + if (gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_SESSION] == NULL) + { + const char *human_addr_cstr = session_get0_readable_addr(sess); + if(NULL == human_addr_cstr){ + fprintf(stderr, "can't get readable_addr, to use session_get0_readable_addr() the sapp_log.conf level must <= INFO\n"); + return; + } + char result_name[MAX_KEY_STR_LEN] = {0}; + gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_SESSION] = cJSON_CreateObject(); + cJSON_AddStringToObject(gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_SESSION], GTEST_HTTP_TUPLE4_NAME, human_addr_cstr); + sprintf(result_name, "%d", g_result_count++); + commit_test_result_json(gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_SESSION], result_name); + } +} + +static int get_gtest_plug_entry(const char *cfg_path, char *entry_name, int max_len, char *topic_name, int topic_max_len) +{ + FILE *fp = fopen(cfg_path, "r"); + if (NULL == fp) + { + fprintf(stderr, "[%s:%d]Can't open config file:%s", + __FUNCTION__, __LINE__, cfg_path); + return -1; + } + + int ret = 0; + char errbuf[256] = {0}; + + toml_table_t *root = toml_parse_file(fp, errbuf, sizeof(errbuf)); + fclose(fp); + + toml_table_t *basic_sec_tbl = toml_table_in(root, "entry"); + if (NULL == basic_sec_tbl) + { + fprintf(stderr, "[%s:%d]config file:%s has no key: [entry]", + __FUNCTION__, __LINE__, cfg_path); + toml_free(root); + return -1; + } + + toml_datum_t str_val = toml_string_in(basic_sec_tbl, "name"); + if (str_val.ok != 0) + { + strncpy(entry_name, str_val.u.s, max_len); + free(str_val.u.s); + } + + toml_datum_t topic_str_val = toml_string_in(basic_sec_tbl, "topic"); + if (str_val.ok != 0) + { + strncpy(topic_name, topic_str_val.u.s, topic_max_len); + free(topic_str_val.u.s); + } + + toml_free(root); + return 0; +} + +static void set_gtest_plug_entry(const char *entry_name) +{ + if(NULL == entry_name){ + g_entry_fun = http_decoder_test_entry; //set default + return; + } + for (size_t i = 0; g_entry_tbl[i].name != NULL; i++) + { + if(strcmp(entry_name, g_entry_tbl[i].name) == 0){ + g_entry_fun = g_entry_tbl[i].entry; + return; + } + } + g_entry_fun = http_decoder_test_entry; //set default +} + +extern "C" void http_decoder_test_entry(struct session *sess, int topic_id, const void *raw_msg, void *no_use_ctx, void *plugin_env) +{ + struct http_request_line req_line = {0}; + struct http_response_line res_line = {0}; + struct http_header header = {0}; + hstring body = {0}; + struct http_message *msg = (struct http_message *)raw_msg; + enum http_message_type msg_type = http_message_type_get(msg); + + struct gtest_plug_exdata_t *gtest_plug_exdata = (struct gtest_plug_exdata_t *)session_exdata_get(sess, g_exdata_idx); + if (NULL == gtest_plug_exdata) + { + gtest_plug_exdata = (struct gtest_plug_exdata_t *)calloc(1, sizeof(struct gtest_plug_exdata_t)); + session_exdata_set(sess, g_exdata_idx, gtest_plug_exdata); + } + + if (http_message_type_is_req(sess, msg_type)) + { + cJSON *json = gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_REQ]; + } + else + { + cJSON *json = gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_RES]; + } + + http_decoder_test_update_session_tuple4(sess, gtest_plug_exdata); + + switch (msg_type) + { + case HTTP_MESSAGE_REQ_LINE: + commit_last_half_flow_data(sess, gtest_plug_exdata, msg, HTTP_TRANSACTION_REQ, 0); + http_message_request_line_get0(msg, &req_line); + req_line_to_json(gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_REQ], &req_line); + break; + case HTTP_MESSAGE_REQ_HEADER: + while (http_message_header_next(msg, &header) >= 0) + { + http_header_to_json(gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_REQ], &header); + } + g_header_count = 1; + break; + case HTTP_MESSAGE_REQ_HEADER_END: + http_url_add_to_json(gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_REQ], msg); + break; + case HTTP_MESSAGE_REQ_BODY_START: + case HTTP_MESSAGE_REQ_BODY: + // http_message_get_request_raw_body(msg, &body); + // output_http_body(&body, 0); + http_message_decompress_body_get0(msg, &body); + // output_http_body(&body, 1); + append_http_payload(sess, gtest_plug_exdata, &body, HTTP_TRANSACTION_REQ); + break; + case HTTP_MESSAGE_RES_LINE: + commit_last_half_flow_data(sess, gtest_plug_exdata, msg, HTTP_TRANSACTION_RES, 0); + http_message_response_line_get0(msg, &res_line); + res_line_to_json(gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_RES], &res_line); + break; + case HTTP_MESSAGE_RES_HEADER: + while (http_message_header_next(msg, &header) >= 0) + { + http_header_to_json(gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_RES], &header); + } + g_header_count = 1; + break; + case HTTP_MESSAGE_RES_BODY_START: + case HTTP_MESSAGE_RES_BODY: + // http_message_get_response_raw_body(msg, &body); + // output_http_body(&body, 0); + http_message_decompress_body_get0(msg, &body); + // output_http_body(&body, 1); + append_http_payload(sess, gtest_plug_exdata, &body, HTTP_TRANSACTION_RES); + break; + + // to do: check payload + default: + break; + } + + return; +} + +void http_decoder_test_exdata_free(struct session *sess, int idx, void *ex_ptr, void *arg) +{ + if (ex_ptr != NULL) + { + struct gtest_plug_exdata_t *gtest_plug_exdata = (struct gtest_plug_exdata_t *)ex_ptr; + if (gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_REQ]) + { + commit_last_half_flow_data(sess, gtest_plug_exdata, NULL, HTTP_TRANSACTION_REQ, 1); + } + if (gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_RES]) + { + commit_last_half_flow_data(sess, gtest_plug_exdata, NULL, HTTP_TRANSACTION_RES, 1); + } + free(ex_ptr); + } +} + +static int update_config_file(const char *filename, const char *key, const char *value) +{ + char cmd_buf[1024] = {}; + snprintf(cmd_buf, 1024, "sed 's/^[ \t]*%s=.*/%s=%s/g' -i %s", key, key, value, filename); + int ret = system(cmd_buf); + return ret; +} + +extern "C" void http_decoder_test_state_entry(struct session *sess, int topic_id, const void *raw_msg, void *no_use_ctx, void *plugin_env) +{ + static int msg_index = 0; + char msg_index_name[64] = {}; + char msg_index_value[64] = {}; + cJSON *json_object = NULL; + enum http_message_type msg_type = http_message_type_get((struct http_message *)raw_msg); + + struct gtest_plug_exdata_t *gtest_plug_exdata = (struct gtest_plug_exdata_t *)session_exdata_get(sess, g_exdata_idx); + if (NULL == gtest_plug_exdata) + { + gtest_plug_exdata = (struct gtest_plug_exdata_t *)calloc(1, sizeof(struct gtest_plug_exdata_t)); + gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_REQ] = cJSON_CreateObject(); + gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_RES] = cJSON_CreateObject(); + session_exdata_set(sess, g_exdata_idx, gtest_plug_exdata); + } + + if (http_message_type_is_req(sess, msg_type)){ + json_object = gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_REQ]; + }else{ + json_object = gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_RES]; + } + if(HTTP_TRANSACTION_END == msg_type){ + unsigned char flow_flag; + session_is_symmetric(sess, &flow_flag); + if(SESSION_SEEN_C2S_FLOW == flow_flag){ + json_object = gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_REQ]; + } + else if(SESSION_SEEN_S2C_FLOW == flow_flag){ + json_object = gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_RES]; + }else{ // is symmetric + json_object = gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_RES]; + } + } + int cur_transaction_id = http_message_get_transaction_seq((const http_message* )raw_msg); + + if(HTTP_TRANSACTION_START ==msg_type || HTTP_TRANSACTION_END == msg_type){ + snprintf(msg_index_name, sizeof(msg_index_name), "msg_%d", msg_index++); + snprintf(msg_index_value, sizeof(msg_index_value), "%s_transaction_%d", http_message_type_to_string(msg_type), cur_transaction_id); + cJSON_AddStringToObject(json_object, msg_index_name, msg_index_value); + }else{ + snprintf(msg_index_name, sizeof(msg_index_name), "msg_%d", msg_index++); + cJSON_AddStringToObject(json_object, msg_index_name, http_message_type_to_string(msg_type)); + } + return; +} + +extern "C" void http_decoder_tunnel_entry(struct session *sess, int topic_id, const void *raw_msg, void *no_use_ctx, void *plugin_env) +{ + struct gtest_plug_exdata_t *gtest_plug_exdata; + enum http_tunnel_message_type tmsg_type = http_tunnel_message_type_get((const struct http_tunnel_message *)raw_msg); + static size_t req_payload_block = 0, req_payload_size = 0; + static size_t res_payload_block = 0, res_payload_size = 0; + gtest_plug_exdata = (struct gtest_plug_exdata_t *)session_exdata_get(sess, g_exdata_idx); + + switch(tmsg_type){ + case HTTP_TUNNEL_OPENING: + { + if (NULL == gtest_plug_exdata) + { + gtest_plug_exdata = (struct gtest_plug_exdata_t *)calloc(1, sizeof(struct gtest_plug_exdata_t)); + session_exdata_set(sess, g_exdata_idx, gtest_plug_exdata); + } + const char *human_addr_cstr = session_get0_readable_addr(sess); + gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_REQ] = cJSON_CreateObject(); + gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_RES] = cJSON_CreateObject(); + gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_SESSION] = cJSON_CreateObject(); + cJSON_AddStringToObject(gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_SESSION], GTEST_HTTP_TUPLE4_NAME, human_addr_cstr); + commit_test_result_json(gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_SESSION], "TUNNEL_NEW"); + } + // OPENING state has payload, go on + + case HTTP_TUNNEL_ACTIVE: + { + int curdir = packet_get_direction(session_get0_current_packet(sess)); + hstring tunnel_payload = {}; + http_tunnel_message_get_payload((const struct http_tunnel_message *)raw_msg, &tunnel_payload); + if(PACKET_DIRECTION_C2S == curdir){ + req_payload_block++; + req_payload_size += tunnel_payload.iov_len; + }else{ + res_payload_block++; + res_payload_size += tunnel_payload.iov_len; + } + } + break; + case HTTP_TUNNEL_CLOSING: + { + cJSON_AddStringToObject(gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_REQ], "flow", "C2S"); + cJSON_AddStringToObject(gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_RES], "flow", "S2C"); + cJSON_AddNumberToObject(gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_REQ], "payload_block", req_payload_block); + cJSON_AddNumberToObject(gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_REQ], "payload_size", req_payload_size); + cJSON_AddNumberToObject(gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_RES], "payload_block", res_payload_block); + cJSON_AddNumberToObject(gtest_plug_exdata->result_jnode[HTTP_TRANSACTION_RES], "payload_size", res_payload_size); + } + break; + default: + assert(0); + break; + } +} + +extern "C" void *http_decoder_test_init(struct stellar *st) +{ + g_http_gtest_plugin_id = stellar_session_plugin_register(st, NULL, NULL, NULL); + g_exdata_idx = stellar_session_exdata_new_index(st, "HTTP_DECODER_GTEST_EXDATA",http_decoder_test_exdata_free, NULL); + if (g_exdata_idx < 0) + { + printf("[%s:%d]: can't get http_decoder exdata index !!!\n", __FUNCTION__, __LINE__); + return NULL; + } + + char entry_name[64] = ""; + char topic_name[64] = ""; + get_gtest_plug_entry(GTEST_PLUG_ENTRY_CFG, entry_name, sizeof(entry_name)-1, topic_name, sizeof(topic_name)-1); + set_gtest_plug_entry(entry_name); + g_topic_id = stellar_session_mq_get_topic_id(st, topic_name); + if (g_topic_id < 0) + { + printf("[%s:%d]: can't get http_decoder topic:%s id !!!\n", __FUNCTION__, __LINE__, topic_name); + return NULL; + } + stellar_session_mq_subscribe(st, g_topic_id, g_entry_fun, g_http_gtest_plugin_id); + printf("http_decoder_gtest_init succ, plugin_id:%d, sub_topic_id:%d\n", g_http_gtest_plugin_id, g_topic_id); + + return (void *)strdup("http_decoder_test_ctx"); +} + +extern "C" void http_decoder_test_exit(void *test_ctx) +{ + if (test_ctx != NULL) + { + FREE(test_ctx); + } + printf("http_decoder_test_exit OK!\n"); +}
\ No newline at end of file diff --git a/test/http_pcap/http_chn_encode_url.pcap b/test/http_pcap/http_chn_encode_url.pcap Binary files differnew file mode 100644 index 0000000..dac9495 --- /dev/null +++ b/test/http_pcap/http_chn_encode_url.pcap diff --git a/test/http_stellar_mock.cpp b/test/http_stellar_mock.cpp new file mode 100644 index 0000000..b0897d6 --- /dev/null +++ b/test/http_stellar_mock.cpp @@ -0,0 +1,290 @@ +#include "uthash-2.3.0/include/utlist.h" +#include "http_decoder_gtest.h" +#include "http_stellar_mock.h" + +static int G_TCP_STREAM_TOPIC_ID = -1; +static int G_UDP_TOPIC_ID = -1; +static struct stellar *G_STELLAR; +static struct plugin_mgr *g_plugin_mgr_list_head = NULL; +static struct stellar *g_st; + +static void stellar_internal_msg_free_cb_func(struct session *sess, void *msg, void *msg_free_arg) {/* do nothing*/} +static void stellar_register_internal_topic(struct stellar *st) +{ + G_TCP_STREAM_TOPIC_ID = stellar_session_mq_get_topic_id(st, TOPIC_TCP_STREAM); + if(G_TCP_STREAM_TOPIC_ID < 0){ + G_TCP_STREAM_TOPIC_ID = stellar_session_mq_create_topic(st, TOPIC_TCP_STREAM, stellar_internal_msg_free_cb_func, NULL); + } + G_UDP_TOPIC_ID = stellar_session_mq_get_topic_id(st, TOPIC_UDP); + if(G_UDP_TOPIC_ID < 0){ + G_UDP_TOPIC_ID = stellar_session_mq_create_topic(st, TOPIC_UDP, stellar_internal_msg_free_cb_func, NULL); + } +} +void stellar_session_plugin_dettach_current_session(struct session *sess) { return; } +int stellar_session_mq_destroy_topic(struct stellar *st, int topic_id) { return 0; } +int stellar_get_worker_thread_num(struct stellar *st) { return 1; } +int stellar_get_current_thread_id(struct stellar *st) { return 0; } +int session_get_current_thread_id(struct session *sess) { return 0; } +int session_mq_ignore_message(struct session *sess, int topic_id, int plugin_id) { return 0; } +int session_mq_unignore_message(struct session *sess, int topic_id, int plugin_id) { return 0; } +int stellar_session_exdata_new_index(struct stellar *st, const char *name, session_exdata_free *free_func,void *arg) +{ + int list_count = 0; + struct exdata_mgr *tmp, *new_exdata = (struct exdata_mgr *)calloc(1, sizeof(struct exdata_mgr)); + DL_FOREACH(st->exdata_mgr_head, tmp){ + if(0 == strcmp(tmp->name, name) && (strlen(tmp->name) == strlen(name))){ + return 0; //already exist + } + } + DL_COUNT(st->exdata_mgr_head, tmp, list_count); + new_exdata->exdata_id = list_count; + new_exdata->name = strdup(name); + new_exdata->free_func = free_func; + new_exdata->arg = arg; + DL_APPEND(st->exdata_mgr_head, new_exdata); + return 0; +} +int session_exdata_set(struct session *sess, int idx, void *ex_ptr) +{ + struct exdata_mgr *el = NULL; + DL_FOREACH(sess->runtime_exdata_head, el){ + if(el->exdata_id == idx){ + el->user_ptr = ex_ptr; + return 0; + } + } + struct exdata_mgr *new_exdata = (struct exdata_mgr *)calloc(1, sizeof(struct exdata_mgr)); + new_exdata->exdata_id = idx; + new_exdata->user_ptr = ex_ptr; + DL_APPEND(sess->runtime_exdata_head, new_exdata); + return 0; +} +void *session_exdata_get(struct session *sess, int idx) +{ + struct exdata_mgr *el = NULL; + DL_FOREACH(sess->runtime_exdata_head, el){ + if(el->exdata_id == idx){ + return el->user_ptr; + } + } + return NULL; +} +enum session_state session_get_current_state(struct session *sess) +{ + return sess->sess_state; +} +const char *session_get0_current_payload(struct session *sess, size_t *payload_len) +{ + const struct packet *test_payload = &sess->pkt; + *payload_len = test_payload->payload_len; + return test_payload->payload; +} +struct session_addr *session_get0_addr(struct session *sess, enum session_addr_type *addr_type) +{ + *addr_type = SESSION_ADDR_TYPE_IPV4_TCP; + return &sess->addr; +} +int packet_get_direction(const struct packet *pkt) +{ + return pkt->dir; +} +const struct packet *session_get0_current_packet(struct session *sess) +{ + return &sess->pkt; +} +int session_is_symmetric(struct session *sess, unsigned char *flag) +{ + *flag = (SESSION_SEEN_C2S_FLOW | SESSION_SEEN_S2C_FLOW); + return 1; +} +static struct plugin_mgr *get_stat_by_plugin_id(int plugin_id) +{ + struct plugin_mgr *plugin = NULL; + DL_FOREACH(g_plugin_mgr_list_head, plugin){ + if(plugin->plugin_id == plugin_id){ + break; + } + } + return plugin; +} +int stellar_session_mq_subscribe(struct stellar *st, int topic_id, on_session_msg_cb_func *plugin_on_msg_cb, int plugin_id) +{ + struct topic_mgr *topic_el = NULL; + DL_FOREACH(st->topic_mgr_head, topic_el){ + if(topic_el->topic_id == topic_id){ + break; + } + } + if(NULL == topic_el){ + return -1; + } + struct plugin_mgr *plugin = get_stat_by_plugin_id(plugin_id); + struct sub_topic_cb_list *sub_cb_list = (struct sub_topic_cb_list *)calloc(1, sizeof(struct sub_topic_cb_list)); + sub_cb_list->sub_cb = plugin_on_msg_cb; + sub_cb_list->plugin_id = plugin_id; + sub_cb_list->plugin_env = plugin->plugin_env; + DL_APPEND(topic_el->sub_free_cb_list_head, sub_cb_list); + return 0; +} +int stellar_session_mq_get_topic_id(struct stellar *st, const char *topic_name) +{ + struct topic_mgr *el = NULL; + DL_FOREACH(st->topic_mgr_head, el){ + if(0 == strcmp(el->topic_name, topic_name) && (strlen(el->topic_name) == strlen(topic_name))){ + return el->topic_id; + } + } + return -1; +} +int stellar_session_mq_create_topic(struct stellar *st, const char *topic_name, session_msg_free_cb_func *msg_free_cb, void *msg_free_arg) +{ + int topic_id = stellar_session_mq_get_topic_id(st, topic_name); + if(topic_id >= 0){ + return topic_id;//already exist + } + struct topic_mgr *tmp, *new_topic = (struct topic_mgr *)calloc(1, sizeof(struct topic_mgr)); + int list_count; + DL_APPEND(st->topic_mgr_head, new_topic); + DL_COUNT(st->topic_mgr_head, tmp, list_count); + new_topic->topic_id = list_count; + new_topic->pub_free_cb = msg_free_cb; + new_topic->pub_free_arg = msg_free_arg; + new_topic->topic_name = strdup(topic_name); + return new_topic->topic_id; +} + +int stellar_session_plugin_register(struct stellar *st, session_ctx_new_func session_ctx_new, + session_ctx_free_func session_ctx_free, void *plugin_env) +{ + int list_count; + struct plugin_mgr *tmp, *plugin = (struct plugin_mgr *)calloc(1, sizeof(struct plugin_mgr)); + DL_APPEND(g_plugin_mgr_list_head, plugin); + DL_COUNT(g_plugin_mgr_list_head, tmp, list_count); + plugin->plugin_id = list_count; + plugin->plugin_env = plugin_env; + plugin->session_ctx_new = session_ctx_new; + plugin->session_ctx_free = session_ctx_free; + return plugin->plugin_id; +} +int session_mq_publish_message(struct session *sess, int topic_id, void *msg) +{ + struct topic_mgr *el = NULL; + DL_FOREACH(sess->st->topic_mgr_head, el){ + if(el->topic_id == topic_id){ + break; + } + } + if(NULL == el){ + return -1; + } + sub_topic_cb_list *sub_cb_node = NULL; + DL_FOREACH(el->sub_free_cb_list_head, sub_cb_node){ + (*sub_cb_node->sub_cb)(sess, topic_id, msg, NULL, sub_cb_node->plugin_env); //todo + } + el->pub_free_cb(sess, msg, el->pub_free_arg); + return 0; +} +int stellar_load_plugin(struct stellar *st, void *(plugin_init_cb)(struct stellar *st)) +{ + plugin_init_cb(st); + return 0; +} +struct session *stellar_session_new(struct stellar *st, int topic_id, const char *payload, size_t payload_len, u_int8_t dir) +{ + struct session *sess = (struct session *)calloc(1, sizeof(struct session)); + sess->st = st; + sess->sess_state = SESSION_STATE_OPENING; + sess->addr.ipv4.saddr = 0x7f000001; + sess->addr.ipv4.daddr = 0x7f000002; + sess->addr.ipv4.sport = htons(12345); + sess->addr.ipv4.dport = htons(80); + if(G_TCP_STREAM_TOPIC_ID == topic_id){ + sess->addr_type = SESSION_ADDR_TYPE_IPV4_TCP; + }else{ + sess->addr_type = SESSION_ADDR_TYPE_IPV4_UDP; + } + sess->pkt.dir = dir; + sess->pkt.payload = payload; + sess->pkt.payload_len = payload_len; + stellar_message *message = (stellar_message *)&sess->pkt; + session_mq_publish_message(sess, topic_id, message); + return sess; +} +void stellar_session_active(struct stellar *st, struct session *sess, int topic_id, const char *payload, size_t payload_len, u_int8_t dir) +{ + sess->sess_state = SESSION_STATE_ACTIVE; + sess->pkt.dir = dir; + sess->pkt.payload = payload; + sess->pkt.payload_len = payload_len; + stellar_message *message = (stellar_message *)&sess->pkt; + session_mq_publish_message(sess, topic_id, message); + return; +} +static void session_plugin_exdata_free(struct stellar *st, struct session *sess, int exdata_idx, void *user_ptr) +{ + struct exdata_mgr *el = NULL; + DL_FOREACH(st->exdata_mgr_head, el){ + if(el->exdata_id == exdata_idx){ + el->free_func(sess, exdata_idx, user_ptr, el->arg); + } + } +} +static void session_plugin_exdata_free_all(struct stellar *st, struct session *sess) +{ + struct exdata_mgr *el = NULL, *tmp = NULL; + DL_FOREACH_SAFE(sess->runtime_exdata_head, el, tmp){ + session_plugin_exdata_free(st, sess, el->exdata_id, el->user_ptr); + DL_DELETE(sess->runtime_exdata_head, el); + free(el); + } +} +static void stellar_session_free(struct stellar *st, struct session *sess) +{ + session_plugin_exdata_free_all(st, sess); + free(sess); +} +void stellar_session_close(struct stellar *st, struct session *sess, int topic_id) +{ + sess->sess_state = SESSION_STATE_CLOSING; + sess->pkt.payload = NULL; + sess->pkt.payload_len = 0; + stellar_message *message = (stellar_message *)&sess->pkt; + session_mq_publish_message(sess, topic_id, message); + stellar_session_free(st, sess); + return; +} +struct stellar *stellar_init(void) +{ + if(NULL == g_st){ + g_st = (struct stellar *)calloc(1, sizeof(struct stellar)); + } + stellar_register_internal_topic(g_st); + return g_st; +} +static void stellar_sub_topi_mgr_destroy(struct topic_mgr *topic_mgr) +{ + struct sub_topic_cb_list *sub_cb_node = NULL, *tmp = NULL; + DL_FOREACH_SAFE(topic_mgr->sub_free_cb_list_head, sub_cb_node, tmp){ + DL_DELETE(topic_mgr->sub_free_cb_list_head, sub_cb_node); + free(sub_cb_node); + } + return; +} +void stellar_destroy(struct stellar *st) +{ + struct exdata_mgr *el = NULL, *tmp; + DL_FOREACH_SAFE(st->exdata_mgr_head, el, tmp){ + free((void *)el->name); + DL_DELETE(st->exdata_mgr_head, el); + free(el); + } + struct topic_mgr *el_topic, *tmp_topic; + DL_FOREACH_SAFE(st->topic_mgr_head, el_topic, tmp_topic){ + DL_DELETE(st->topic_mgr_head, el_topic); + stellar_sub_topi_mgr_destroy(el_topic); + free((void *)el_topic->topic_name); + free(el_topic); + } + free(st); + return; +}
\ No newline at end of file diff --git a/test/http_stellar_mock.h b/test/http_stellar_mock.h new file mode 100644 index 0000000..d3c2dc5 --- /dev/null +++ b/test/http_stellar_mock.h @@ -0,0 +1,72 @@ +#pragma once +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <sys/types.h> +#include <time.h> +#include </usr/include/bits/types/struct_iovec.h> +#ifdef __cplusplus +extern "C" +{ +#endif +#include <stellar/session.h> +#include <stellar/session_mq.h> +#include <stellar/session_exdata.h> +#include <stellar/stellar.h> +#ifdef __cplusplus +} +#endif + +struct packet{ + const char *payload; + size_t payload_len; + u_int8_t dir; //PACKET_DIRECTION_C2S PACKET_DIRECTION_S2C +}; +typedef struct packet stellar_message; +struct exdata_mgr{ + const char *name; + int exdata_id; + void *arg; + void *user_ptr; + session_exdata_free *free_func; + struct exdata_mgr *next, *prev; +}; +struct sub_topic_mgr{ + int topic_id; + int plugin_id; + void *plugin_env; +}; +struct topic_mgr{ + struct topic_mgr *next, *prev; + const char *topic_name; + int topic_id; + session_msg_free_cb_func *pub_free_cb; + void *pub_free_arg; + struct sub_topic_cb_list *sub_free_cb_list_head; +}; +struct stellar{ + struct topic_mgr *topic_mgr_head; + struct exdata_mgr *exdata_mgr_head; +}; +struct session{ + struct stellar *st; + enum session_state sess_state; + enum session_addr_type addr_type; + struct session_addr addr; + void *exdata; + struct packet pkt; + struct exdata_mgr *runtime_exdata_head; +}; +struct plugin_mgr{ + struct plugin_mgr *next, *prev; + int plugin_id; + void *plugin_env; + session_ctx_new_func *session_ctx_new; + session_ctx_free_func *session_ctx_free; +}; +struct sub_topic_cb_list{ + int plugin_id; + void *plugin_env; + on_session_msg_cb_func *sub_cb; + struct sub_topic_cb_list *next, *prev; +}; diff --git a/test/test_result_json/http_chn_encode_url.json b/test/test_result_json/http_chn_encode_url.json new file mode 100644 index 0000000..642aaa5 --- /dev/null +++ b/test/test_result_json/http_chn_encode_url.json @@ -0,0 +1,42 @@ +[ + { + "__X_HTTP_TUPLE4": "2607:5d00:2:2::38:2.56343>240e:928:101:80::80.80" + }, + { + "__X_HTTP_TRANSACTION": "request", + "__X_HTTP_TRANSACTION_SEQ": 0, + "method": "GET", + "uri": "/%E6%B5%8B%E8%AF%95%E4%B8%AD%E6%96%87URL%E7%BC%96%E8%A7%A3%E7%A0%81", + "req_version": "1.1", + "major_version": 1, + "minor_version": 1, + "Host": "www.airchina.com.cn", + "Connection": "keep-alive", + "DNT": "1", + "Upgrade-Insecure-Requests": "1", + "User-Agent": "Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/126.0.0.0 Safari/537.36", + "Accept": "text/html,application/xhtml+xml,application/xml;q=0.9,image/avif,image/webp,image/apng,*/*;q=0.8,application/signed-exchange;v=b3;q=0.7", + "Accept-Encoding": "gzip, deflate", + "Accept-Language": "zh-CN,zh;q=0.9,en;q=0.8", + "Cookie": "_gcl_au=1.1.240068387.1720059437; _ga_CGYVD7S4G4=GS1.1.1720059448.3.0.1720059453.0.0.0; HMF_CI=7967e38cc3874dbbefa260b8dcbee31fa827a01fc2b7073105a5e05f4a1ea361c74f6d4c37fb199bfc9470036f06fb537da2a74e96450b7949e0b686f0569f9680; HMY_JC=84f9c8a99e076ee2dda5ba48cd953f61c4dc2707823205d8171c8818eea9d60fda,; _ga=GA1.3.822493162.1711101509; _gid=GA1.3.304369429.1721120134; arialoadData=true; ariawapChangeViewPort=false; C3VK=be8842; HBB_HC=faa7f3e2477e14525534a5560ed6a307b29ae2c324e1f631a428e53fb74c9d72575c155d682554ba15cc9e52afe31218b1; mbox=check#true#1721120252|session#1721120133635-517642#1721122052; s_pers=%20s_fid%3D52863027521849CD-3A72894997C48527%7C1878886591105%3B; s_sess=%20s_cc%3Dtrue%3B", + "__X_HTTP_URL": "www.airchina.com.cn/%E6%B5%8B%E8%AF%95%E4%B8%AD%E6%96%87URL%E7%BC%96%E8%A7%A3%E7%A0%81", + "__X_HTTP_DECODED_URL": "www.airchina.com.cn/测试中文URL编解码" + }, + { + "__X_HTTP_TRANSACTION": "response", + "__X_HTTP_TRANSACTION_SEQ": 0, + "res_version": "1.1", + "res_status": "Moved Temporarily", + "major_version": 1, + "minor_version": 1, + "status_code": 302, + "Date": "Tue, 16 Jul 2024 08:57:32 GMT", + "Content-Length": "0", + "Connection": "keep-alive", + "Server": "waf/4.39.0-0.el7", + "Location": "https://www.airchina.com.cn/%E6%B5%8B%E8%AF%95%E4%B8%AD%E6%96%87URL%E7%BC%96%E8%A7%A3%E7%A0%81", + "x-ws-origin-error": "-", + "X-Via": "1.1 PSjsczBGPiv194:0 (Cdn Cache Server V2.0), 1.1 PStjdxpn34:6 (Cdn Cache Server V2.0)", + "X-Ws-Request-Id": "669635fc_PStjdxks32_7630-15285" + } +]
\ No newline at end of file diff --git a/test/test_result_json/http_get_encoded_uri.json b/test/test_result_json/http_get_encoded_uri.json index fe57717..d999063 100644 --- a/test/test_result_json/http_get_encoded_uri.json +++ b/test/test_result_json/http_get_encoded_uri.json @@ -56,7 +56,8 @@ "Cookie": "JSESSIONID=385C79E211D561C0CA13D90F150F603D", "Host": "58.16.70.122", "Accept-Encoding": "gzip, deflate", - "__X_HTTP_URL": "58.16.70.122/upload/%E6%B3%95%E5%BE%8B%E6%B3%95%E8%A7%84/%E5%B8%82%E4%BA%BA%E6%B0%91%E6%94%BF%E5%BA%9C%E5%8A%9E%E5%85%AC%E5%8E%85%E5%8D%B0%E5%8F%91%E8%B4%B5%E9%98%B3%E5%B8%82%E5%85%B3%E4%BA%8E%E6%8E%A8%E8%BF%9B%E5%B7%A5%E5%95%86%E8%90%A5%E4%B8%9A%E6%89%A7%E7%85%A7%E3%80%81%E7%BB%84%E7%BB%87%E6%9C%BA%E6%9E%84%E4%BB%A3%E7%A0%81%E8%AF%81%E5%92%8C%E7%A8%8E%E5%8A%A1%E7%99%BB%E8%AE%B0%E8%AF%81%E2%80%9C%E4%B8%89%E8%AF%81%E5%90%88%E4%B8%80%E2%80%9D%E7%99%BB%E8%AE%B0%E5%88%B6%E5%BA%A6%E6%94%B9%E9%9D%A9%E5%AE%9E%E6%96%BD%E6%96%B9%E6%A1%88%E7%9A%84%E9%80%9A%E7%9F%A5%EF%BC%88%E7%AD%91%E5%BA%9C%E5%8A%9E%E5%87%BD%E3%80%902015%E3%80%91162%E5%8F%B7%EF%BC%89.docx?nsextt=N3TSP4RKE2" + "__X_HTTP_URL": "58.16.70.122/upload/%E6%B3%95%E5%BE%8B%E6%B3%95%E8%A7%84/%E5%B8%82%E4%BA%BA%E6%B0%91%E6%94%BF%E5%BA%9C%E5%8A%9E%E5%85%AC%E5%8E%85%E5%8D%B0%E5%8F%91%E8%B4%B5%E9%98%B3%E5%B8%82%E5%85%B3%E4%BA%8E%E6%8E%A8%E8%BF%9B%E5%B7%A5%E5%95%86%E8%90%A5%E4%B8%9A%E6%89%A7%E7%85%A7%E3%80%81%E7%BB%84%E7%BB%87%E6%9C%BA%E6%9E%84%E4%BB%A3%E7%A0%81%E8%AF%81%E5%92%8C%E7%A8%8E%E5%8A%A1%E7%99%BB%E8%AE%B0%E8%AF%81%E2%80%9C%E4%B8%89%E8%AF%81%E5%90%88%E4%B8%80%E2%80%9D%E7%99%BB%E8%AE%B0%E5%88%B6%E5%BA%A6%E6%94%B9%E9%9D%A9%E5%AE%9E%E6%96%BD%E6%96%B9%E6%A1%88%E7%9A%84%E9%80%9A%E7%9F%A5%EF%BC%88%E7%AD%91%E5%BA%9C%E5%8A%9E%E5%87%BD%E3%80%902015%E3%80%91162%E5%8F%B7%EF%BC%89.docx?nsextt=N3TSP4RKE2", + "__X_HTTP_DECODED_URL": "58.16.70.122/upload/法律法规/市人民政府办公厅印发贵阳市关于推进工商营业执照、组织机构代码证和税务登记证“三证合一”登记制度改革实施方案的通知（筑府办函【2015】162号）.docx?nsextt=N3TSP4RKE2" }, { "__X_HTTP_TRANSACTION": "response", diff --git a/test/test_result_json/http_get_long_cookie.json b/test/test_result_json/http_get_long_cookie.json index 4efa43d..125e42a 100644 --- a/test/test_result_json/http_get_long_cookie.json +++ b/test/test_result_json/http_get_long_cookie.json @@ -18,6 +18,7 @@ "Accept-Encoding": "gzip,deflate,sdch", "Accept-Language": "zh-CN,zh;q=0.8", "__X_HTTP_URL": "livep.l.qq.com/livemsg?imagemd5=02f5efd8a349c50280f8540b2735bd54&tailroll=1&plugin=1.3.8&pf=out&si=3766845706&url=http%3A%2F%2Fsports.qq.com%2Fa%2F20160106%2F008987.htm&soid=CA7F9C5B0120568CDC2F68726300&chid=0&ping_data=dXNlcl9pbmZvPXVCWDluVDg5SFJhOUFQK0JQVGdKRUxVYi9Kdz0&t=0&iptype=0&vptag=&pid=7F993E38C0E676ACC07DE764D1F3DEF56AA8F90A&adtype=LD&oadid=6012&ev=3236&l=4020&ufc_filter=0&imagelog=1&pid2=7F993E38C0E676ACC07DE764D1F3DEF56AA8F90A&mt=15000&coverid=&reqtime=1452071981&requestl=4020&isthirdip=0&cid=0&isfloatindex=0&o=100654557&lcount=2&refluence=4020&from=0&vid=m01794rm5ej&cip=202.127.156.91&aver=0&ip_filter=0&adlength=30000&tagid=&v=TencentPlayerOutV3.2.19.346&live=0&dura=105", + "__X_HTTP_DECODED_URL": "livep.l.qq.com/livemsg?imagemd5=02f5efd8a349c50280f8540b2735bd54&tailroll=1&plugin=1.3.8&pf=out&si=3766845706&url=http://sports.qq.com/a/20160106/008987.htm&soid=CA7F9C5B0120568CDC2F68726300&chid=0&ping_data=dXNlcl9pbmZvPXVCWDluVDg5SFJhOUFQK0JQVGdKRUxVYi9Kdz0&t=0&iptype=0&vptag=&pid=7F993E38C0E676ACC07DE764D1F3DEF56AA8F90A&adtype=LD&oadid=6012&ev=3236&l=4020&ufc_filter=0&imagelog=1&pid2=7F993E38C0E676ACC07DE764D1F3DEF56AA8F90A&mt=15000&coverid=&reqtime=1452071981&requestl=4020&isthirdip=0&cid=0&isfloatindex=0&o=100654557&lcount=2&refluence=4020&from=0&vid=m01794rm5ej&cip=202.127.156.91&aver=0&ip_filter=0&adlength=30000&tagid=&v=TencentPlayerOutV3.2.19.346&live=0&dura=105", "Cookie": "flashuser=95621BA8CB862E09; piao_city=179; lv_irt_id=3628e1bbe25a6c941da9fac02ec2df8b; cm_cookie=V1,10017&-EP5mRruXhQarsCl5LD-2YzgjVTvyr2K&AQEBh7uoLMUB9lnaB5Tz9XdYnGIWflXmsDrU&150723&150723,10035&7t-tEmfJ076VAsM9&AQEBh7uoLMUB9lnc4tpW7vbazqdrRdBYOUCi&150724&150807,110054&ucO0Z0gctNn3&AQEBh7uoLMUB9llxMNl45F3RAIsKK0iMOJAG&150716&151008,10040&ACZ1r0A70NaEFcGT&AQEBh7uoLMUB9lmVgSoTwuuXZi896zSVsXIF&150818&151014,110015&1&AQEBh7uoLMUB9lkt2LUHO6ARwODHLI_Y51rj&150928&151103,10037&1433388364186289251984&AQEBh7uoLMUB9llIBencOqTAEh2aQ2SURSSQ&150909&151110,10011&jL40Z03uUFI0&AQEBh7uoLMUB9lkfw2sJVNx9g12Fzs12rPSN&150717&151125,10016&F64E6LFZs0W&AQEBh7uoLMUB9llE4yoPFNUykSj7WKaRK5lH&150805&151127,10019&WQAO-C1K9qI5OP8W_t2pSw&AQEBh7uoLMUB9llhpZE87GmOk3XGo_MJgV6K&150826&151130,10015&820490997316506147&AQEBh7uoLMUB9llXiynsGYRhMO3XuPnkuHUt&150715&151201,10012&x3X1yY6b&AQEBh7uoLMUB9ll9mraU_LJCDBYsE0Sbk_V9&151202&151202,110065&ucO0Z0gctNn3&AQEBh7uoLMUB9lkJcK3KDBQTKF0YfZ5wB7r5&150716&151203,110066&jL40Z03uUFI0&AQEBh7uoLMUB9lnyvKSYhcJD1X_rSs_DLVWx&150916&151221,10013&ePyYB2MSKa0TCbebpxKjmU&AQEBh7uoLMUB9ln6_6nGNidqml4nFKXhtE58&151221&151221,110061&d9cfa518d82abee&AQEBh7uoLMUB9llj2NYzmCjxaLWXALTcAGIH&150818&151224,10038&CAESEPZbUhToZJ39CS9MlgXGUSQ&AQEBh7uoLMUB9lmhnrDM5lIGtl6vc1NxMD6F&151110&151224,10077&820490997316506147&AQEBh7uoLMUB9lmkUdUe2xSHGkvM0IRu9Jt9&151214&151228,10008&0yPSvk92ie1nhB8wTUlTq&AQEBh7uoLMUB9lnL5ZCYvXJNvlv53G0CKEkj&150817&151228,10045&0&AQEBh7uoLMUB9llW3v1Vh7W72lv14RlAjUXn&151023&151228,110064&jL40Z03uUFI0&AQEBh7uoLMUB9lkBYuCUDLDrOcGURJcilogv&151016&160104,110069&26d49ecc&AQEBh7uoLMUB9lmlBLTxQY9BkCmimkMFqTo5&151204&160105,10079&B8hGto5y1e3uDXwCMsIun3rjk--dVCof&AQEBh7uoLMUB9llxnFrhDtdNMjZ1hs1il5J4&151214&160105; LHTturn=24; ptisp=ctc; RK=hRWyd82Gd8; pgv_pvi=7567882240; image_md5=bd21d5fb2f401b37cf3a02724dc06545; LTPturn=27; pt2gguin=o0583115900; uin=o0583115900; skey=@Mp9aCinaO; ptcz=10d4b1b7bde835d64663338a8008fd4f81e2c6b5f0ba81a90da3627ee617c7ee; pgv_info=ssid=s4768939310; pgv_pvid=6872592818; o_cookie=583115900; lv_play_index_textAd=47; lv_play_indexl.=32; dc_vplaying=1; LKBturn=29; Lturn=29; adid=583115900; appuser=95621BA8CB862E09; o_minduid=phhdxyNLkxBWMa74VTm5zU4y5EbUv5vR; appuser_95621BA8CB862E09_0=2b7gwp=1453219199_6&2btemv=1455551999_1&2c8311=1453305599_3&2cfx4j=1453651199_3&2cfx9l=1453651199_1&2d49y9=1453823999_2&2d67kl=1454255999_2&2d69mf=1454255999_3&2dxv8l=1455465599_6&2dzhfl=1452614399_1&f_pogvwp=1452095999_1&f_pogvwv=1452095999_2&f_pogw0m=1452095999_1&fd_15bm2t7=1452095999_1&fd_1h2pbsd=1452095999_2&fd_1k6so62=1452095999_1&fd_rhmjmq=1452095999_2&m_roiw0t=1452095999_3&m_xty8wl=1452095999_1&pogree=1452095999_2; TX.boid=100655474=1452072582_1&701041365=1452072585_1; appuser_95621BA8CB862E09_effect_0=fd_1ez2rcc=1452095999_1&fd_qdh7zw=1452095999_1&fd_ul215j=1452095999_1; psessionid=ca7f9c5b_1452071982_583115900_30754; psessiontime=1452071990" } ]
\ No newline at end of file diff --git a/test/test_result_json/http_msg_type_state.json b/test/test_result_json/http_msg_type_state.json index 8fae48a..5dc0564 100644 --- a/test/test_result_json/http_msg_type_state.json +++ b/test/test_result_json/http_msg_type_state.json @@ -1,18 +1,20 @@ [ { - "msg_0": "HTTP_TRANSACTION_NEW_transaction_0", + "msg_0": "HTTP_TRANSACTION_START_transaction_0", "msg_1": "HTTP_MESSAGE_REQ_LINE", "msg_2": "HTTP_MESSAGE_REQ_HEADER", "msg_3": "HTTP_MESSAGE_REQ_HEADER_END", - "msg_4": "HTTP_MESSAGE_REQ_BODY", - "msg_5": "HTTP_MESSAGE_REQ_BODY_END" + "msg_4": "HTTP_MESSAGE_REQ_BODY_START", + "msg_5": "HTTP_MESSAGE_REQ_BODY", + "msg_6": "HTTP_MESSAGE_REQ_BODY_END" }, { - "msg_6": "HTTP_MESSAGE_RES_LINE", - "msg_7": "HTTP_MESSAGE_RES_HEADER", - "msg_8": "HTTP_MESSAGE_RES_HEADER_END", - "msg_9": "HTTP_MESSAGE_RES_BODY", - "msg_10": "HTTP_MESSAGE_RES_BODY_END", - "msg_11": "HTTP_TRANSACTION_FREE_transaction_0" + "msg_7": "HTTP_MESSAGE_RES_LINE", + "msg_8": "HTTP_MESSAGE_RES_HEADER", + "msg_9": "HTTP_MESSAGE_RES_HEADER_END", + "msg_10": "HTTP_MESSAGE_RES_BODY_START", + "msg_11": "HTTP_MESSAGE_RES_BODY", + "msg_12": "HTTP_MESSAGE_RES_BODY_END", + "msg_13": "HTTP_TRANSACTION_END_transaction_0" } ]
\ No newline at end of file diff --git a/test/test_result_json/http_msg_type_state_c2s.json b/test/test_result_json/http_msg_type_state_c2s.json index 05ed4f1..8533bb9 100644 --- a/test/test_result_json/http_msg_type_state_c2s.json +++ b/test/test_result_json/http_msg_type_state_c2s.json @@ -1,12 +1,13 @@ [ { - "msg_0": "HTTP_TRANSACTION_NEW_transaction_0", + "msg_0": "HTTP_TRANSACTION_START_transaction_0", "msg_1": "HTTP_MESSAGE_REQ_LINE", "msg_2": "HTTP_MESSAGE_REQ_HEADER", "msg_3": "HTTP_MESSAGE_REQ_HEADER_END", - "msg_4": "HTTP_MESSAGE_REQ_BODY", - "msg_5": "HTTP_MESSAGE_REQ_BODY_END", - "msg_6": "HTTP_TRANSACTION_FREE_transaction_0" + "msg_4": "HTTP_MESSAGE_REQ_BODY_START", + "msg_5": "HTTP_MESSAGE_REQ_BODY", + "msg_6": "HTTP_MESSAGE_REQ_BODY_END", + "msg_7": "HTTP_TRANSACTION_END_transaction_0" }, {} ]
\ No newline at end of file diff --git a/test/test_result_json/http_msg_type_state_exception_c2s.json b/test/test_result_json/http_msg_type_state_exception_c2s.json index 1edf964..e694238 100644 --- a/test/test_result_json/http_msg_type_state_exception_c2s.json +++ b/test/test_result_json/http_msg_type_state_exception_c2s.json @@ -1,12 +1,13 @@ [ { - "msg_0": "HTTP_TRANSACTION_NEW_transaction_0", + "msg_0": "HTTP_TRANSACTION_START_transaction_0", "msg_1": "HTTP_MESSAGE_REQ_LINE", "msg_2": "HTTP_MESSAGE_REQ_HEADER", "msg_3": "HTTP_MESSAGE_REQ_HEADER_END", - "msg_4": "HTTP_MESSAGE_REQ_BODY" + "msg_4": "HTTP_MESSAGE_REQ_BODY_START", + "msg_5": "HTTP_MESSAGE_REQ_BODY" }, { - "msg_5": "HTTP_TRANSACTION_FREE_transaction_0" + "msg_6": "HTTP_TRANSACTION_END_transaction_0" } ]
\ No newline at end of file diff --git a/test/test_result_json/http_msg_type_state_exception_s2c.json b/test/test_result_json/http_msg_type_state_exception_s2c.json index 50fda4e..cf03270 100644 --- a/test/test_result_json/http_msg_type_state_exception_s2c.json +++ b/test/test_result_json/http_msg_type_state_exception_s2c.json @@ -1,6 +1,6 @@ [ { - "msg_0": "HTTP_TRANSACTION_NEW_transaction_0", + "msg_0": "HTTP_TRANSACTION_START_transaction_0", "msg_1": "HTTP_MESSAGE_REQ_LINE", "msg_2": "HTTP_MESSAGE_REQ_HEADER", "msg_3": "HTTP_MESSAGE_REQ_HEADER_END" @@ -9,7 +9,8 @@ "msg_4": "HTTP_MESSAGE_RES_LINE", "msg_5": "HTTP_MESSAGE_RES_HEADER", "msg_6": "HTTP_MESSAGE_RES_HEADER_END", - "msg_7": "HTTP_MESSAGE_RES_BODY", - "msg_8": "HTTP_TRANSACTION_FREE_transaction_0" + "msg_7": "HTTP_MESSAGE_RES_BODY_START", + "msg_8": "HTTP_MESSAGE_RES_BODY", + "msg_9": "HTTP_TRANSACTION_END_transaction_0" } ]
\ No newline at end of file diff --git a/test/test_result_json/http_msg_type_state_pipeline.json b/test/test_result_json/http_msg_type_state_pipeline.json index 5384420..d50f4ac 100644 --- a/test/test_result_json/http_msg_type_state_pipeline.json +++ b/test/test_result_json/http_msg_type_state_pipeline.json @@ -1,18 +1,18 @@ [ { - "msg_0": "HTTP_TRANSACTION_NEW_transaction_0", + "msg_0": "HTTP_TRANSACTION_START_transaction_0", "msg_1": "HTTP_MESSAGE_REQ_LINE", "msg_2": "HTTP_MESSAGE_REQ_HEADER", "msg_3": "HTTP_MESSAGE_REQ_HEADER_END", - "msg_8": "HTTP_TRANSACTION_NEW_transaction_1", + "msg_8": "HTTP_TRANSACTION_START_transaction_1", "msg_9": "HTTP_MESSAGE_REQ_LINE", "msg_10": "HTTP_MESSAGE_REQ_HEADER", "msg_11": "HTTP_MESSAGE_REQ_HEADER_END", - "msg_16": "HTTP_TRANSACTION_NEW_transaction_2", + "msg_16": "HTTP_TRANSACTION_START_transaction_2", "msg_17": "HTTP_MESSAGE_REQ_LINE", "msg_18": "HTTP_MESSAGE_REQ_HEADER", "msg_19": "HTTP_MESSAGE_REQ_HEADER_END", - "msg_24": "HTTP_TRANSACTION_NEW_transaction_3", + "msg_24": "HTTP_TRANSACTION_START_transaction_3", "msg_25": "HTTP_MESSAGE_REQ_LINE", "msg_26": "HTTP_MESSAGE_REQ_HEADER", "msg_27": "HTTP_MESSAGE_REQ_HEADER_END" @@ -21,19 +21,19 @@ "msg_4": "HTTP_MESSAGE_RES_LINE", "msg_5": "HTTP_MESSAGE_RES_HEADER", "msg_6": "HTTP_MESSAGE_RES_HEADER_END", - "msg_7": "HTTP_TRANSACTION_FREE_transaction_0", + "msg_7": "HTTP_TRANSACTION_END_transaction_0", "msg_12": "HTTP_MESSAGE_RES_LINE", "msg_13": "HTTP_MESSAGE_RES_HEADER", "msg_14": "HTTP_MESSAGE_RES_HEADER_END", - "msg_15": "HTTP_TRANSACTION_FREE_transaction_1", + "msg_15": "HTTP_TRANSACTION_END_transaction_1", "msg_20": "HTTP_MESSAGE_RES_LINE", "msg_21": "HTTP_MESSAGE_RES_HEADER", "msg_22": "HTTP_MESSAGE_RES_HEADER_END", - "msg_23": "HTTP_TRANSACTION_FREE_transaction_2", + "msg_23": "HTTP_TRANSACTION_END_transaction_2", "msg_28": "HTTP_MESSAGE_RES_LINE", "msg_29": "HTTP_MESSAGE_RES_HEADER", "msg_30": "HTTP_MESSAGE_RES_HEADER_END", - "msg_31": "HTTP_MESSAGE_RES_BODY", + "msg_31": "HTTP_MESSAGE_RES_BODY_START", "msg_32": "HTTP_MESSAGE_RES_BODY", "msg_33": "HTTP_MESSAGE_RES_BODY", "msg_34": "HTTP_MESSAGE_RES_BODY", @@ -54,7 +54,8 @@ "msg_49": "HTTP_MESSAGE_RES_BODY", "msg_50": "HTTP_MESSAGE_RES_BODY", "msg_51": "HTTP_MESSAGE_RES_BODY", - "msg_52": "HTTP_MESSAGE_RES_BODY_END", - "msg_53": "HTTP_TRANSACTION_FREE_transaction_3" + "msg_52": "HTTP_MESSAGE_RES_BODY", + "msg_53": "HTTP_MESSAGE_RES_BODY_END", + "msg_54": "HTTP_TRANSACTION_END_transaction_3" } ]
\ No newline at end of file diff --git a/test/test_result_json/http_msg_type_state_s2c.json b/test/test_result_json/http_msg_type_state_s2c.json index 8a05b49..c59d0bb 100644 --- a/test/test_result_json/http_msg_type_state_s2c.json +++ b/test/test_result_json/http_msg_type_state_s2c.json @@ -1,12 +1,13 @@ [ {}, { - "msg_0": "HTTP_TRANSACTION_NEW_transaction_0", + "msg_0": "HTTP_TRANSACTION_START_transaction_0", "msg_1": "HTTP_MESSAGE_RES_LINE", "msg_2": "HTTP_MESSAGE_RES_HEADER", "msg_3": "HTTP_MESSAGE_RES_HEADER_END", - "msg_4": "HTTP_MESSAGE_RES_BODY", - "msg_5": "HTTP_MESSAGE_RES_BODY_END", - "msg_6": "HTTP_TRANSACTION_FREE_transaction_0" + "msg_4": "HTTP_MESSAGE_RES_BODY_START", + "msg_5": "HTTP_MESSAGE_RES_BODY", + "msg_6": "HTTP_MESSAGE_RES_BODY_END", + "msg_7": "HTTP_TRANSACTION_END_transaction_0" } ]
\ No newline at end of file diff --git a/test/test_result_json/http_msg_type_state_tunnel.json b/test/test_result_json/http_msg_type_state_tunnel.json index cdbad4e..4a66f37 100644 --- a/test/test_result_json/http_msg_type_state_tunnel.json +++ b/test/test_result_json/http_msg_type_state_tunnel.json @@ -1,10 +1,10 @@ [ { - "msg_0": "HTTP_TRANSACTION_NEW_transaction_0", + "msg_0": "HTTP_TRANSACTION_START_transaction_0", "msg_1": "HTTP_MESSAGE_REQ_LINE", "msg_2": "HTTP_MESSAGE_REQ_HEADER", "msg_3": "HTTP_MESSAGE_REQ_HEADER_END", - "msg_8": "HTTP_TRANSACTION_NEW_transaction_1", + "msg_8": "HTTP_TRANSACTION_START_transaction_1", "msg_9": "HTTP_MESSAGE_REQ_LINE", "msg_10": "HTTP_MESSAGE_REQ_HEADER", "msg_11": "HTTP_MESSAGE_REQ_HEADER_END" @@ -13,7 +13,7 @@ "msg_4": "HTTP_MESSAGE_RES_LINE", "msg_5": "HTTP_MESSAGE_RES_HEADER", "msg_6": "HTTP_MESSAGE_RES_HEADER_END", - "msg_7": "HTTP_TRANSACTION_FREE_transaction_0", + "msg_7": "HTTP_TRANSACTION_END_transaction_0", "msg_12": "HTTP_MESSAGE_RES_LINE", "msg_13": "HTTP_MESSAGE_RES_HEADER", "msg_14": "HTTP_MESSAGE_RES_HEADER_END", @@ -21,6 +21,6 @@ "msg_16": "HTTP_MESSAGE_RES_BODY", "msg_17": "HTTP_MESSAGE_RES_BODY", "msg_18": "HTTP_MESSAGE_RES_BODY_END", - "msg_19": "HTTP_TRANSACTION_FREE_transaction_1" + "msg_19": "HTTP_TRANSACTION_END_transaction_1" } ]
\ No newline at end of file diff --git a/test/test_result_json/http_msg_type_state_tunnel_c2s.json b/test/test_result_json/http_msg_type_state_tunnel_c2s.json index 71e5cb5..5b7e588 100644 --- a/test/test_result_json/http_msg_type_state_tunnel_c2s.json +++ b/test/test_result_json/http_msg_type_state_tunnel_c2s.json @@ -1,15 +1,15 @@ [ { - "msg_0": "HTTP_TRANSACTION_NEW_transaction_0", + "msg_0": "HTTP_TRANSACTION_START_transaction_0", "msg_1": "HTTP_MESSAGE_REQ_LINE", "msg_2": "HTTP_MESSAGE_REQ_HEADER", "msg_3": "HTTP_MESSAGE_REQ_HEADER_END", - "msg_4": "HTTP_TRANSACTION_FREE_transaction_0", - "msg_5": "HTTP_TRANSACTION_NEW_transaction_1", + "msg_4": "HTTP_TRANSACTION_END_transaction_0", + "msg_5": "HTTP_TRANSACTION_START_transaction_1", "msg_6": "HTTP_MESSAGE_REQ_LINE", "msg_7": "HTTP_MESSAGE_REQ_HEADER", "msg_8": "HTTP_MESSAGE_REQ_HEADER_END", - "msg_9": "HTTP_TRANSACTION_FREE_transaction_1" + "msg_9": "HTTP_TRANSACTION_END_transaction_1" }, {} ]
\ No newline at end of file diff --git a/test/test_result_json/http_msg_type_state_tunnel_s2c.json b/test/test_result_json/http_msg_type_state_tunnel_s2c.json index b31260d..07a1451 100644 --- a/test/test_result_json/http_msg_type_state_tunnel_s2c.json +++ b/test/test_result_json/http_msg_type_state_tunnel_s2c.json @@ -1,12 +1,12 @@ [ {}, { - "msg_0": "HTTP_TRANSACTION_NEW_transaction_0", + "msg_0": "HTTP_TRANSACTION_START_transaction_0", "msg_1": "HTTP_MESSAGE_RES_LINE", "msg_2": "HTTP_MESSAGE_RES_HEADER", "msg_3": "HTTP_MESSAGE_RES_HEADER_END", - "msg_4": "HTTP_TRANSACTION_FREE_transaction_0", - "msg_5": "HTTP_TRANSACTION_NEW_transaction_1", + "msg_4": "HTTP_TRANSACTION_END_transaction_0", + "msg_5": "HTTP_TRANSACTION_START_transaction_1", "msg_6": "HTTP_MESSAGE_RES_LINE", "msg_7": "HTTP_MESSAGE_RES_HEADER", "msg_8": "HTTP_MESSAGE_RES_HEADER_END", @@ -14,6 +14,6 @@ "msg_10": "HTTP_MESSAGE_RES_BODY", "msg_11": "HTTP_MESSAGE_RES_BODY", "msg_12": "HTTP_MESSAGE_RES_BODY_END", - "msg_13": "HTTP_TRANSACTION_FREE_transaction_1" + "msg_13": "HTTP_TRANSACTION_END_transaction_1" } ]
\ No newline at end of file diff --git a/test/uthash-2.3.0/include/utarray.h b/test/uthash-2.3.0/include/utarray.h new file mode 100644 index 0000000..992fe7c --- /dev/null +++ b/test/uthash-2.3.0/include/utarray.h @@ -0,0 +1,248 @@ +/* +Copyright (c) 2008-2021, Troy D. Hanson http://troydhanson.github.com/uthash/ +All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS +IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED +TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A +PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER +OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, +EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, +PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR +PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF +LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING +NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS +SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +/* a dynamic array implementation using macros + */ +#ifndef UTARRAY_H +#define UTARRAY_H + +#define UTARRAY_VERSION 2.3.0 + +#include <stddef.h> /* size_t */ +#include <string.h> /* memset, etc */ +#include <stdlib.h> /* exit */ + +#ifdef __GNUC__ +#define UTARRAY_UNUSED __attribute__((__unused__)) +#else +#define UTARRAY_UNUSED +#endif + +#ifdef oom +#error "The name of macro 'oom' has been changed to 'utarray_oom'. Please update your code." +#define utarray_oom() oom() +#endif + +#ifndef utarray_oom +#define utarray_oom() exit(-1) +#endif + +typedef void (ctor_f)(void *dst, const void *src); +typedef void (dtor_f)(void *elt); +typedef void (init_f)(void *elt); +typedef struct { + size_t sz; + init_f *init; + ctor_f *copy; + dtor_f *dtor; +} UT_icd; + +typedef struct { + unsigned i,n;/* i: index of next available slot, n: num slots */ + UT_icd icd; /* initializer, copy and destructor functions */ + char *d; /* n slots of size icd->sz*/ +} UT_array; + +#define utarray_init(a,_icd) do { \ + memset(a,0,sizeof(UT_array)); \ + (a)->icd = *(_icd); \ +} while(0) + +#define utarray_done(a) do { \ + if ((a)->n) { \ + if ((a)->icd.dtor) { \ + unsigned _ut_i; \ + for(_ut_i=0; _ut_i < (a)->i; _ut_i++) { \ + (a)->icd.dtor(utarray_eltptr(a,_ut_i)); \ + } \ + } \ + free((a)->d); \ + } \ + (a)->n=0; \ +} while(0) + +#define utarray_new(a,_icd) do { \ + (a) = (UT_array*)malloc(sizeof(UT_array)); \ + if ((a) == NULL) { \ + utarray_oom(); \ + } \ + utarray_init(a,_icd); \ +} while(0) + +#define utarray_free(a) do { \ + utarray_done(a); \ + free(a); \ +} while(0) + +#define utarray_reserve(a,by) do { \ + if (((a)->i+(by)) > (a)->n) { \ + char *utarray_tmp; \ + while (((a)->i+(by)) > (a)->n) { (a)->n = ((a)->n ? (2*(a)->n) : 8); } \ + utarray_tmp=(char*)realloc((a)->d, (a)->n*(a)->icd.sz); \ + if (utarray_tmp == NULL) { \ + utarray_oom(); \ + } \ + (a)->d=utarray_tmp; \ + } \ +} while(0) + +#define utarray_push_back(a,p) do { \ + utarray_reserve(a,1); \ + if ((a)->icd.copy) { (a)->icd.copy( _utarray_eltptr(a,(a)->i++), p); } \ + else { memcpy(_utarray_eltptr(a,(a)->i++), p, (a)->icd.sz); }; \ +} while(0) + +#define utarray_pop_back(a) do { \ + if ((a)->icd.dtor) { (a)->icd.dtor( _utarray_eltptr(a,--((a)->i))); } \ + else { (a)->i--; } \ +} while(0) + +#define utarray_extend_back(a) do { \ + utarray_reserve(a,1); \ + if ((a)->icd.init) { (a)->icd.init(_utarray_eltptr(a,(a)->i)); } \ + else { memset(_utarray_eltptr(a,(a)->i),0,(a)->icd.sz); } \ + (a)->i++; \ +} while(0) + +#define utarray_len(a) ((a)->i) + +#define utarray_eltptr(a,j) (((j) < (a)->i) ? _utarray_eltptr(a,j) : NULL) +#define _utarray_eltptr(a,j) ((void*)((a)->d + ((a)->icd.sz * (j)))) + +#define utarray_insert(a,p,j) do { \ + if ((j) > (a)->i) utarray_resize(a,j); \ + utarray_reserve(a,1); \ + if ((j) < (a)->i) { \ + memmove( _utarray_eltptr(a,(j)+1), _utarray_eltptr(a,j), \ + ((a)->i - (j))*((a)->icd.sz)); \ + } \ + if ((a)->icd.copy) { (a)->icd.copy( _utarray_eltptr(a,j), p); } \ + else { memcpy(_utarray_eltptr(a,j), p, (a)->icd.sz); }; \ + (a)->i++; \ +} while(0) + +#define utarray_inserta(a,w,j) do { \ + if (utarray_len(w) == 0) break; \ + if ((j) > (a)->i) utarray_resize(a,j); \ + utarray_reserve(a,utarray_len(w)); \ + if ((j) < (a)->i) { \ + memmove(_utarray_eltptr(a,(j)+utarray_len(w)), \ + _utarray_eltptr(a,j), \ + ((a)->i - (j))*((a)->icd.sz)); \ + } \ + if ((a)->icd.copy) { \ + unsigned _ut_i; \ + for(_ut_i=0;_ut_i<(w)->i;_ut_i++) { \ + (a)->icd.copy(_utarray_eltptr(a, (j) + _ut_i), _utarray_eltptr(w, _ut_i)); \ + } \ + } else { \ + memcpy(_utarray_eltptr(a,j), _utarray_eltptr(w,0), \ + utarray_len(w)*((a)->icd.sz)); \ + } \ + (a)->i += utarray_len(w); \ +} while(0) + +#define utarray_resize(dst,num) do { \ + unsigned _ut_i; \ + if ((dst)->i > (unsigned)(num)) { \ + if ((dst)->icd.dtor) { \ + for (_ut_i = (num); _ut_i < (dst)->i; ++_ut_i) { \ + (dst)->icd.dtor(_utarray_eltptr(dst, _ut_i)); \ + } \ + } \ + } else if ((dst)->i < (unsigned)(num)) { \ + utarray_reserve(dst, (num) - (dst)->i); \ + if ((dst)->icd.init) { \ + for (_ut_i = (dst)->i; _ut_i < (unsigned)(num); ++_ut_i) { \ + (dst)->icd.init(_utarray_eltptr(dst, _ut_i)); \ + } \ + } else { \ + memset(_utarray_eltptr(dst, (dst)->i), 0, (dst)->icd.sz*((num) - (dst)->i)); \ + } \ + } \ + (dst)->i = (num); \ +} while(0) + +#define utarray_concat(dst,src) do { \ + utarray_inserta(dst, src, utarray_len(dst)); \ +} while(0) + +#define utarray_erase(a,pos,len) do { \ + if ((a)->icd.dtor) { \ + unsigned _ut_i; \ + for (_ut_i = 0; _ut_i < (len); _ut_i++) { \ + (a)->icd.dtor(utarray_eltptr(a, (pos) + _ut_i)); \ + } \ + } \ + if ((a)->i > ((pos) + (len))) { \ + memmove(_utarray_eltptr(a, pos), _utarray_eltptr(a, (pos) + (len)), \ + ((a)->i - ((pos) + (len))) * (a)->icd.sz); \ + } \ + (a)->i -= (len); \ +} while(0) + +#define utarray_renew(a,u) do { \ + if (a) utarray_clear(a); \ + else utarray_new(a, u); \ +} while(0) + +#define utarray_clear(a) do { \ + if ((a)->i > 0) { \ + if ((a)->icd.dtor) { \ + unsigned _ut_i; \ + for(_ut_i=0; _ut_i < (a)->i; _ut_i++) { \ + (a)->icd.dtor(_utarray_eltptr(a, _ut_i)); \ + } \ + } \ + (a)->i = 0; \ + } \ +} while(0) + +#define utarray_sort(a,cmp) do { \ + qsort((a)->d, (a)->i, (a)->icd.sz, cmp); \ +} while(0) + +#define utarray_find(a,v,cmp) bsearch((v),(a)->d,(a)->i,(a)->icd.sz,cmp) + +#define utarray_front(a) (((a)->i) ? (_utarray_eltptr(a,0)) : NULL) +#define utarray_next(a,e) (((e)==NULL) ? utarray_front(a) : (((a)->i != utarray_eltidx(a,e)+1) ? _utarray_eltptr(a,utarray_eltidx(a,e)+1) : NULL)) +#define utarray_prev(a,e) (((e)==NULL) ? utarray_back(a) : ((utarray_eltidx(a,e) != 0) ? _utarray_eltptr(a,utarray_eltidx(a,e)-1) : NULL)) +#define utarray_back(a) (((a)->i) ? (_utarray_eltptr(a,(a)->i-1)) : NULL) +#define utarray_eltidx(a,e) (((char*)(e) - (a)->d) / (a)->icd.sz) + +/* last we pre-define a few icd for common utarrays of ints and strings */ +static void utarray_str_cpy(void *dst, const void *src) { + char *const *srcc = (char *const *)src; + char **dstc = (char**)dst; + *dstc = (*srcc == NULL) ? NULL : strdup(*srcc); +} +static void utarray_str_dtor(void *elt) { + char **eltc = (char**)elt; + if (*eltc != NULL) free(*eltc); +} +static const UT_icd ut_str_icd UTARRAY_UNUSED = {sizeof(char*),NULL,utarray_str_cpy,utarray_str_dtor}; +static const UT_icd ut_int_icd UTARRAY_UNUSED = {sizeof(int),NULL,NULL,NULL}; +static const UT_icd ut_ptr_icd UTARRAY_UNUSED = {sizeof(void*),NULL,NULL,NULL}; + + +#endif /* UTARRAY_H */ diff --git a/test/uthash-2.3.0/include/uthash.h b/test/uthash-2.3.0/include/uthash.h new file mode 100644 index 0000000..ac78fda --- /dev/null +++ b/test/uthash-2.3.0/include/uthash.h @@ -0,0 +1,1136 @@ +/* +Copyright (c) 2003-2021, Troy D. Hanson http://troydhanson.github.com/uthash/ +All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS +IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED +TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A +PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER +OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, +EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, +PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR +PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF +LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING +NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS +SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +#ifndef UTHASH_H +#define UTHASH_H + +#define UTHASH_VERSION 2.3.0 + +#include <string.h> /* memcmp, memset, strlen */ +#include <stddef.h> /* ptrdiff_t */ +#include <stdlib.h> /* exit */ + +#if defined(HASH_DEFINE_OWN_STDINT) && HASH_DEFINE_OWN_STDINT +/* This codepath is provided for backward compatibility, but I plan to remove it. */ +#warning "HASH_DEFINE_OWN_STDINT is deprecated; please use HASH_NO_STDINT instead" +typedef unsigned int uint32_t; +typedef unsigned char uint8_t; +#elif defined(HASH_NO_STDINT) && HASH_NO_STDINT +#else +#include <stdint.h> /* uint8_t, uint32_t */ +#endif + +/* These macros use decltype or the earlier __typeof GNU extension. + As decltype is only available in newer compilers (VS2010 or gcc 4.3+ + when compiling c++ source) this code uses whatever method is needed + or, for VS2008 where neither is available, uses casting workarounds. */ +#if !defined(DECLTYPE) && !defined(NO_DECLTYPE) +#if defined(_MSC_VER) /* MS compiler */ +#if _MSC_VER >= 1600 && defined(__cplusplus) /* VS2010 or newer in C++ mode */ +#define DECLTYPE(x) (decltype(x)) +#else /* VS2008 or older (or VS2010 in C mode) */ +#define NO_DECLTYPE +#endif +#elif defined(__BORLANDC__) || defined(__ICCARM__) || defined(__LCC__) || defined(__WATCOMC__) +#define NO_DECLTYPE +#else /* GNU, Sun and other compilers */ +#define DECLTYPE(x) (__typeof(x)) +#endif +#endif + +#ifdef NO_DECLTYPE +#define DECLTYPE(x) +#define DECLTYPE_ASSIGN(dst,src) \ +do { \ + char **_da_dst = (char**)(&(dst)); \ + *_da_dst = (char*)(src); \ +} while (0) +#else +#define DECLTYPE_ASSIGN(dst,src) \ +do { \ + (dst) = DECLTYPE(dst)(src); \ +} while (0) +#endif + +#ifndef uthash_malloc +#define uthash_malloc(sz) malloc(sz) /* malloc fcn */ +#endif +#ifndef uthash_free +#define uthash_free(ptr,sz) free(ptr) /* free fcn */ +#endif +#ifndef uthash_bzero +#define uthash_bzero(a,n) memset(a,'\0',n) +#endif +#ifndef uthash_strlen +#define uthash_strlen(s) strlen(s) +#endif + +#ifndef HASH_FUNCTION +#define HASH_FUNCTION(keyptr,keylen,hashv) HASH_JEN(keyptr, keylen, hashv) +#endif + +#ifndef HASH_KEYCMP +#define HASH_KEYCMP(a,b,n) memcmp(a,b,n) +#endif + +#ifndef uthash_noexpand_fyi +#define uthash_noexpand_fyi(tbl) /* can be defined to log noexpand */ +#endif +#ifndef uthash_expand_fyi +#define uthash_expand_fyi(tbl) /* can be defined to log expands */ +#endif + +#ifndef HASH_NONFATAL_OOM +#define HASH_NONFATAL_OOM 0 +#endif + +#if HASH_NONFATAL_OOM +/* malloc failures can be recovered from */ + +#ifndef uthash_nonfatal_oom +#define uthash_nonfatal_oom(obj) do {} while (0) /* non-fatal OOM error */ +#endif + +#define HASH_RECORD_OOM(oomed) do { (oomed) = 1; } while (0) +#define IF_HASH_NONFATAL_OOM(x) x + +#else +/* malloc failures result in lost memory, hash tables are unusable */ + +#ifndef uthash_fatal +#define uthash_fatal(msg) exit(-1) /* fatal OOM error */ +#endif + +#define HASH_RECORD_OOM(oomed) uthash_fatal("out of memory") +#define IF_HASH_NONFATAL_OOM(x) + +#endif + +/* initial number of buckets */ +#define HASH_INITIAL_NUM_BUCKETS 32U /* initial number of buckets */ +#define HASH_INITIAL_NUM_BUCKETS_LOG2 5U /* lg2 of initial number of buckets */ +#define HASH_BKT_CAPACITY_THRESH 10U /* expand when bucket count reaches */ + +/* calculate the element whose hash handle address is hhp */ +#define ELMT_FROM_HH(tbl,hhp) ((void*)(((char*)(hhp)) - ((tbl)->hho))) +/* calculate the hash handle from element address elp */ +#define HH_FROM_ELMT(tbl,elp) ((UT_hash_handle*)(void*)(((char*)(elp)) + ((tbl)->hho))) + +#define HASH_ROLLBACK_BKT(hh, head, itemptrhh) \ +do { \ + struct UT_hash_handle *_hd_hh_item = (itemptrhh); \ + unsigned _hd_bkt; \ + HASH_TO_BKT(_hd_hh_item->hashv, (head)->hh.tbl->num_buckets, _hd_bkt); \ + (head)->hh.tbl->buckets[_hd_bkt].count++; \ + _hd_hh_item->hh_next = NULL; \ + _hd_hh_item->hh_prev = NULL; \ +} while (0) + +#define HASH_VALUE(keyptr,keylen,hashv) \ +do { \ + HASH_FUNCTION(keyptr, keylen, hashv); \ +} while (0) + +#define HASH_FIND_BYHASHVALUE(hh,head,keyptr,keylen,hashval,out) \ +do { \ + (out) = NULL; \ + if (head) { \ + unsigned _hf_bkt; \ + HASH_TO_BKT(hashval, (head)->hh.tbl->num_buckets, _hf_bkt); \ + if (HASH_BLOOM_TEST((head)->hh.tbl, hashval) != 0) { \ + HASH_FIND_IN_BKT((head)->hh.tbl, hh, (head)->hh.tbl->buckets[ _hf_bkt ], keyptr, keylen, hashval, out); \ + } \ + } \ +} while (0) + +#define HASH_FIND(hh,head,keyptr,keylen,out) \ +do { \ + (out) = NULL; \ + if (head) { \ + unsigned _hf_hashv; \ + HASH_VALUE(keyptr, keylen, _hf_hashv); \ + HASH_FIND_BYHASHVALUE(hh, head, keyptr, keylen, _hf_hashv, out); \ + } \ +} while (0) + +#ifdef HASH_BLOOM +#define HASH_BLOOM_BITLEN (1UL << HASH_BLOOM) +#define HASH_BLOOM_BYTELEN (HASH_BLOOM_BITLEN/8UL) + (((HASH_BLOOM_BITLEN%8UL)!=0UL) ? 1UL : 0UL) +#define HASH_BLOOM_MAKE(tbl,oomed) \ +do { \ + (tbl)->bloom_nbits = HASH_BLOOM; \ + (tbl)->bloom_bv = (uint8_t*)uthash_malloc(HASH_BLOOM_BYTELEN); \ + if (!(tbl)->bloom_bv) { \ + HASH_RECORD_OOM(oomed); \ + } else { \ + uthash_bzero((tbl)->bloom_bv, HASH_BLOOM_BYTELEN); \ + (tbl)->bloom_sig = HASH_BLOOM_SIGNATURE; \ + } \ +} while (0) + +#define HASH_BLOOM_FREE(tbl) \ +do { \ + uthash_free((tbl)->bloom_bv, HASH_BLOOM_BYTELEN); \ +} while (0) + +#define HASH_BLOOM_BITSET(bv,idx) (bv[(idx)/8U] |= (1U << ((idx)%8U))) +#define HASH_BLOOM_BITTEST(bv,idx) (bv[(idx)/8U] & (1U << ((idx)%8U))) + +#define HASH_BLOOM_ADD(tbl,hashv) \ + HASH_BLOOM_BITSET((tbl)->bloom_bv, ((hashv) & (uint32_t)((1UL << (tbl)->bloom_nbits) - 1U))) + +#define HASH_BLOOM_TEST(tbl,hashv) \ + HASH_BLOOM_BITTEST((tbl)->bloom_bv, ((hashv) & (uint32_t)((1UL << (tbl)->bloom_nbits) - 1U))) + +#else +#define HASH_BLOOM_MAKE(tbl,oomed) +#define HASH_BLOOM_FREE(tbl) +#define HASH_BLOOM_ADD(tbl,hashv) +#define HASH_BLOOM_TEST(tbl,hashv) (1) +#define HASH_BLOOM_BYTELEN 0U +#endif + +#define HASH_MAKE_TABLE(hh,head,oomed) \ +do { \ + (head)->hh.tbl = (UT_hash_table*)uthash_malloc(sizeof(UT_hash_table)); \ + if (!(head)->hh.tbl) { \ + HASH_RECORD_OOM(oomed); \ + } else { \ + uthash_bzero((head)->hh.tbl, sizeof(UT_hash_table)); \ + (head)->hh.tbl->tail = &((head)->hh); \ + (head)->hh.tbl->num_buckets = HASH_INITIAL_NUM_BUCKETS; \ + (head)->hh.tbl->log2_num_buckets = HASH_INITIAL_NUM_BUCKETS_LOG2; \ + (head)->hh.tbl->hho = (char*)(&(head)->hh) - (char*)(head); \ + (head)->hh.tbl->buckets = (UT_hash_bucket*)uthash_malloc( \ + HASH_INITIAL_NUM_BUCKETS * sizeof(struct UT_hash_bucket)); \ + (head)->hh.tbl->signature = HASH_SIGNATURE; \ + if (!(head)->hh.tbl->buckets) { \ + HASH_RECORD_OOM(oomed); \ + uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \ + } else { \ + uthash_bzero((head)->hh.tbl->buckets, \ + HASH_INITIAL_NUM_BUCKETS * sizeof(struct UT_hash_bucket)); \ + HASH_BLOOM_MAKE((head)->hh.tbl, oomed); \ + IF_HASH_NONFATAL_OOM( \ + if (oomed) { \ + uthash_free((head)->hh.tbl->buckets, \ + HASH_INITIAL_NUM_BUCKETS*sizeof(struct UT_hash_bucket)); \ + uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \ + } \ + ) \ + } \ + } \ +} while (0) + +#define HASH_REPLACE_BYHASHVALUE_INORDER(hh,head,fieldname,keylen_in,hashval,add,replaced,cmpfcn) \ +do { \ + (replaced) = NULL; \ + HASH_FIND_BYHASHVALUE(hh, head, &((add)->fieldname), keylen_in, hashval, replaced); \ + if (replaced) { \ + HASH_DELETE(hh, head, replaced); \ + } \ + HASH_ADD_KEYPTR_BYHASHVALUE_INORDER(hh, head, &((add)->fieldname), keylen_in, hashval, add, cmpfcn); \ +} while (0) + +#define HASH_REPLACE_BYHASHVALUE(hh,head,fieldname,keylen_in,hashval,add,replaced) \ +do { \ + (replaced) = NULL; \ + HASH_FIND_BYHASHVALUE(hh, head, &((add)->fieldname), keylen_in, hashval, replaced); \ + if (replaced) { \ + HASH_DELETE(hh, head, replaced); \ + } \ + HASH_ADD_KEYPTR_BYHASHVALUE(hh, head, &((add)->fieldname), keylen_in, hashval, add); \ +} while (0) + +#define HASH_REPLACE(hh,head,fieldname,keylen_in,add,replaced) \ +do { \ + unsigned _hr_hashv; \ + HASH_VALUE(&((add)->fieldname), keylen_in, _hr_hashv); \ + HASH_REPLACE_BYHASHVALUE(hh, head, fieldname, keylen_in, _hr_hashv, add, replaced); \ +} while (0) + +#define HASH_REPLACE_INORDER(hh,head,fieldname,keylen_in,add,replaced,cmpfcn) \ +do { \ + unsigned _hr_hashv; \ + HASH_VALUE(&((add)->fieldname), keylen_in, _hr_hashv); \ + HASH_REPLACE_BYHASHVALUE_INORDER(hh, head, fieldname, keylen_in, _hr_hashv, add, replaced, cmpfcn); \ +} while (0) + +#define HASH_APPEND_LIST(hh, head, add) \ +do { \ + (add)->hh.next = NULL; \ + (add)->hh.prev = ELMT_FROM_HH((head)->hh.tbl, (head)->hh.tbl->tail); \ + (head)->hh.tbl->tail->next = (add); \ + (head)->hh.tbl->tail = &((add)->hh); \ +} while (0) + +#define HASH_AKBI_INNER_LOOP(hh,head,add,cmpfcn) \ +do { \ + do { \ + if (cmpfcn(DECLTYPE(head)(_hs_iter), add) > 0) { \ + break; \ + } \ + } while ((_hs_iter = HH_FROM_ELMT((head)->hh.tbl, _hs_iter)->next)); \ +} while (0) + +#ifdef NO_DECLTYPE +#undef HASH_AKBI_INNER_LOOP +#define HASH_AKBI_INNER_LOOP(hh,head,add,cmpfcn) \ +do { \ + char *_hs_saved_head = (char*)(head); \ + do { \ + DECLTYPE_ASSIGN(head, _hs_iter); \ + if (cmpfcn(head, add) > 0) { \ + DECLTYPE_ASSIGN(head, _hs_saved_head); \ + break; \ + } \ + DECLTYPE_ASSIGN(head, _hs_saved_head); \ + } while ((_hs_iter = HH_FROM_ELMT((head)->hh.tbl, _hs_iter)->next)); \ +} while (0) +#endif + +#if HASH_NONFATAL_OOM + +#define HASH_ADD_TO_TABLE(hh,head,keyptr,keylen_in,hashval,add,oomed) \ +do { \ + if (!(oomed)) { \ + unsigned _ha_bkt; \ + (head)->hh.tbl->num_items++; \ + HASH_TO_BKT(hashval, (head)->hh.tbl->num_buckets, _ha_bkt); \ + HASH_ADD_TO_BKT((head)->hh.tbl->buckets[_ha_bkt], hh, &(add)->hh, oomed); \ + if (oomed) { \ + HASH_ROLLBACK_BKT(hh, head, &(add)->hh); \ + HASH_DELETE_HH(hh, head, &(add)->hh); \ + (add)->hh.tbl = NULL; \ + uthash_nonfatal_oom(add); \ + } else { \ + HASH_BLOOM_ADD((head)->hh.tbl, hashval); \ + HASH_EMIT_KEY(hh, head, keyptr, keylen_in); \ + } \ + } else { \ + (add)->hh.tbl = NULL; \ + uthash_nonfatal_oom(add); \ + } \ +} while (0) + +#else + +#define HASH_ADD_TO_TABLE(hh,head,keyptr,keylen_in,hashval,add,oomed) \ +do { \ + unsigned _ha_bkt; \ + (head)->hh.tbl->num_items++; \ + HASH_TO_BKT(hashval, (head)->hh.tbl->num_buckets, _ha_bkt); \ + HASH_ADD_TO_BKT((head)->hh.tbl->buckets[_ha_bkt], hh, &(add)->hh, oomed); \ + HASH_BLOOM_ADD((head)->hh.tbl, hashval); \ + HASH_EMIT_KEY(hh, head, keyptr, keylen_in); \ +} while (0) + +#endif + + +#define HASH_ADD_KEYPTR_BYHASHVALUE_INORDER(hh,head,keyptr,keylen_in,hashval,add,cmpfcn) \ +do { \ + IF_HASH_NONFATAL_OOM( int _ha_oomed = 0; ) \ + (add)->hh.hashv = (hashval); \ + (add)->hh.key = (char*) (keyptr); \ + (add)->hh.keylen = (unsigned) (keylen_in); \ + if (!(head)) { \ + (add)->hh.next = NULL; \ + (add)->hh.prev = NULL; \ + HASH_MAKE_TABLE(hh, add, _ha_oomed); \ + IF_HASH_NONFATAL_OOM( if (!_ha_oomed) { ) \ + (head) = (add); \ + IF_HASH_NONFATAL_OOM( } ) \ + } else { \ + void *_hs_iter = (head); \ + (add)->hh.tbl = (head)->hh.tbl; \ + HASH_AKBI_INNER_LOOP(hh, head, add, cmpfcn); \ + if (_hs_iter) { \ + (add)->hh.next = _hs_iter; \ + if (((add)->hh.prev = HH_FROM_ELMT((head)->hh.tbl, _hs_iter)->prev)) { \ + HH_FROM_ELMT((head)->hh.tbl, (add)->hh.prev)->next = (add); \ + } else { \ + (head) = (add); \ + } \ + HH_FROM_ELMT((head)->hh.tbl, _hs_iter)->prev = (add); \ + } else { \ + HASH_APPEND_LIST(hh, head, add); \ + } \ + } \ + HASH_ADD_TO_TABLE(hh, head, keyptr, keylen_in, hashval, add, _ha_oomed); \ + HASH_FSCK(hh, head, "HASH_ADD_KEYPTR_BYHASHVALUE_INORDER"); \ +} while (0) + +#define HASH_ADD_KEYPTR_INORDER(hh,head,keyptr,keylen_in,add,cmpfcn) \ +do { \ + unsigned _hs_hashv; \ + HASH_VALUE(keyptr, keylen_in, _hs_hashv); \ + HASH_ADD_KEYPTR_BYHASHVALUE_INORDER(hh, head, keyptr, keylen_in, _hs_hashv, add, cmpfcn); \ +} while (0) + +#define HASH_ADD_BYHASHVALUE_INORDER(hh,head,fieldname,keylen_in,hashval,add,cmpfcn) \ + HASH_ADD_KEYPTR_BYHASHVALUE_INORDER(hh, head, &((add)->fieldname), keylen_in, hashval, add, cmpfcn) + +#define HASH_ADD_INORDER(hh,head,fieldname,keylen_in,add,cmpfcn) \ + HASH_ADD_KEYPTR_INORDER(hh, head, &((add)->fieldname), keylen_in, add, cmpfcn) + +#define HASH_ADD_KEYPTR_BYHASHVALUE(hh,head,keyptr,keylen_in,hashval,add) \ +do { \ + IF_HASH_NONFATAL_OOM( int _ha_oomed = 0; ) \ + (add)->hh.hashv = (hashval); \ + (add)->hh.key = (const void*) (keyptr); \ + (add)->hh.keylen = (unsigned) (keylen_in); \ + if (!(head)) { \ + (add)->hh.next = NULL; \ + (add)->hh.prev = NULL; \ + HASH_MAKE_TABLE(hh, add, _ha_oomed); \ + IF_HASH_NONFATAL_OOM( if (!_ha_oomed) { ) \ + (head) = (add); \ + IF_HASH_NONFATAL_OOM( } ) \ + } else { \ + (add)->hh.tbl = (head)->hh.tbl; \ + HASH_APPEND_LIST(hh, head, add); \ + } \ + HASH_ADD_TO_TABLE(hh, head, keyptr, keylen_in, hashval, add, _ha_oomed); \ + HASH_FSCK(hh, head, "HASH_ADD_KEYPTR_BYHASHVALUE"); \ +} while (0) + +#define HASH_ADD_KEYPTR(hh,head,keyptr,keylen_in,add) \ +do { \ + unsigned _ha_hashv; \ + HASH_VALUE(keyptr, keylen_in, _ha_hashv); \ + HASH_ADD_KEYPTR_BYHASHVALUE(hh, head, keyptr, keylen_in, _ha_hashv, add); \ +} while (0) + +#define HASH_ADD_BYHASHVALUE(hh,head,fieldname,keylen_in,hashval,add) \ + HASH_ADD_KEYPTR_BYHASHVALUE(hh, head, &((add)->fieldname), keylen_in, hashval, add) + +#define HASH_ADD(hh,head,fieldname,keylen_in,add) \ + HASH_ADD_KEYPTR(hh, head, &((add)->fieldname), keylen_in, add) + +#define HASH_TO_BKT(hashv,num_bkts,bkt) \ +do { \ + bkt = ((hashv) & ((num_bkts) - 1U)); \ +} while (0) + +/* delete "delptr" from the hash table. + * "the usual" patch-up process for the app-order doubly-linked-list. + * The use of _hd_hh_del below deserves special explanation. + * These used to be expressed using (delptr) but that led to a bug + * if someone used the same symbol for the head and deletee, like + * HASH_DELETE(hh,users,users); + * We want that to work, but by changing the head (users) below + * we were forfeiting our ability to further refer to the deletee (users) + * in the patch-up process. Solution: use scratch space to + * copy the deletee pointer, then the latter references are via that + * scratch pointer rather than through the repointed (users) symbol. + */ +#define HASH_DELETE(hh,head,delptr) \ + HASH_DELETE_HH(hh, head, &(delptr)->hh) + +#define HASH_DELETE_HH(hh,head,delptrhh) \ +do { \ + struct UT_hash_handle *_hd_hh_del = (delptrhh); \ + if ((_hd_hh_del->prev == NULL) && (_hd_hh_del->next == NULL)) { \ + HASH_BLOOM_FREE((head)->hh.tbl); \ + uthash_free((head)->hh.tbl->buckets, \ + (head)->hh.tbl->num_buckets * sizeof(struct UT_hash_bucket)); \ + uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \ + (head) = NULL; \ + } else { \ + unsigned _hd_bkt; \ + if (_hd_hh_del == (head)->hh.tbl->tail) { \ + (head)->hh.tbl->tail = HH_FROM_ELMT((head)->hh.tbl, _hd_hh_del->prev); \ + } \ + if (_hd_hh_del->prev != NULL) { \ + HH_FROM_ELMT((head)->hh.tbl, _hd_hh_del->prev)->next = _hd_hh_del->next; \ + } else { \ + DECLTYPE_ASSIGN(head, _hd_hh_del->next); \ + } \ + if (_hd_hh_del->next != NULL) { \ + HH_FROM_ELMT((head)->hh.tbl, _hd_hh_del->next)->prev = _hd_hh_del->prev; \ + } \ + HASH_TO_BKT(_hd_hh_del->hashv, (head)->hh.tbl->num_buckets, _hd_bkt); \ + HASH_DEL_IN_BKT((head)->hh.tbl->buckets[_hd_bkt], _hd_hh_del); \ + (head)->hh.tbl->num_items--; \ + } \ + HASH_FSCK(hh, head, "HASH_DELETE_HH"); \ +} while (0) + +/* convenience forms of HASH_FIND/HASH_ADD/HASH_DEL */ +#define HASH_FIND_STR(head,findstr,out) \ +do { \ + unsigned _uthash_hfstr_keylen = (unsigned)uthash_strlen(findstr); \ + HASH_FIND(hh, head, findstr, _uthash_hfstr_keylen, out); \ +} while (0) +#define HASH_ADD_STR(head,strfield,add) \ +do { \ + unsigned _uthash_hastr_keylen = (unsigned)uthash_strlen((add)->strfield); \ + HASH_ADD(hh, head, strfield[0], _uthash_hastr_keylen, add); \ +} while (0) +#define HASH_REPLACE_STR(head,strfield,add,replaced) \ +do { \ + unsigned _uthash_hrstr_keylen = (unsigned)uthash_strlen((add)->strfield); \ + HASH_REPLACE(hh, head, strfield[0], _uthash_hrstr_keylen, add, replaced); \ +} while (0) +#define HASH_FIND_INT(head,findint,out) \ + HASH_FIND(hh,head,findint,sizeof(int),out) +#define HASH_ADD_INT(head,intfield,add) \ + HASH_ADD(hh,head,intfield,sizeof(int),add) +#define HASH_REPLACE_INT(head,intfield,add,replaced) \ + HASH_REPLACE(hh,head,intfield,sizeof(int),add,replaced) +#define HASH_FIND_PTR(head,findptr,out) \ + HASH_FIND(hh,head,findptr,sizeof(void *),out) +#define HASH_ADD_PTR(head,ptrfield,add) \ + HASH_ADD(hh,head,ptrfield,sizeof(void *),add) +#define HASH_REPLACE_PTR(head,ptrfield,add,replaced) \ + HASH_REPLACE(hh,head,ptrfield,sizeof(void *),add,replaced) +#define HASH_DEL(head,delptr) \ + HASH_DELETE(hh,head,delptr) + +/* HASH_FSCK checks hash integrity on every add/delete when HASH_DEBUG is defined. + * This is for uthash developer only; it compiles away if HASH_DEBUG isn't defined. + */ +#ifdef HASH_DEBUG +#include <stdio.h> /* fprintf, stderr */ +#define HASH_OOPS(...) do { fprintf(stderr, __VA_ARGS__); exit(-1); } while (0) +#define HASH_FSCK(hh,head,where) \ +do { \ + struct UT_hash_handle *_thh; \ + if (head) { \ + unsigned _bkt_i; \ + unsigned _count = 0; \ + char *_prev; \ + for (_bkt_i = 0; _bkt_i < (head)->hh.tbl->num_buckets; ++_bkt_i) { \ + unsigned _bkt_count = 0; \ + _thh = (head)->hh.tbl->buckets[_bkt_i].hh_head; \ + _prev = NULL; \ + while (_thh) { \ + if (_prev != (char*)(_thh->hh_prev)) { \ + HASH_OOPS("%s: invalid hh_prev %p, actual %p\n", \ + (where), (void*)_thh->hh_prev, (void*)_prev); \ + } \ + _bkt_count++; \ + _prev = (char*)(_thh); \ + _thh = _thh->hh_next; \ + } \ + _count += _bkt_count; \ + if ((head)->hh.tbl->buckets[_bkt_i].count != _bkt_count) { \ + HASH_OOPS("%s: invalid bucket count %u, actual %u\n", \ + (where), (head)->hh.tbl->buckets[_bkt_i].count, _bkt_count); \ + } \ + } \ + if (_count != (head)->hh.tbl->num_items) { \ + HASH_OOPS("%s: invalid hh item count %u, actual %u\n", \ + (where), (head)->hh.tbl->num_items, _count); \ + } \ + _count = 0; \ + _prev = NULL; \ + _thh = &(head)->hh; \ + while (_thh) { \ + _count++; \ + if (_prev != (char*)_thh->prev) { \ + HASH_OOPS("%s: invalid prev %p, actual %p\n", \ + (where), (void*)_thh->prev, (void*)_prev); \ + } \ + _prev = (char*)ELMT_FROM_HH((head)->hh.tbl, _thh); \ + _thh = (_thh->next ? HH_FROM_ELMT((head)->hh.tbl, _thh->next) : NULL); \ + } \ + if (_count != (head)->hh.tbl->num_items) { \ + HASH_OOPS("%s: invalid app item count %u, actual %u\n", \ + (where), (head)->hh.tbl->num_items, _count); \ + } \ + } \ +} while (0) +#else +#define HASH_FSCK(hh,head,where) +#endif + +/* When compiled with -DHASH_EMIT_KEYS, length-prefixed keys are emitted to + * the descriptor to which this macro is defined for tuning the hash function. + * The app can #include <unistd.h> to get the prototype for write(2). */ +#ifdef HASH_EMIT_KEYS +#define HASH_EMIT_KEY(hh,head,keyptr,fieldlen) \ +do { \ + unsigned _klen = fieldlen; \ + write(HASH_EMIT_KEYS, &_klen, sizeof(_klen)); \ + write(HASH_EMIT_KEYS, keyptr, (unsigned long)fieldlen); \ +} while (0) +#else +#define HASH_EMIT_KEY(hh,head,keyptr,fieldlen) +#endif + +/* The Bernstein hash function, used in Perl prior to v5.6. Note (x<<5+x)=x*33. */ +#define HASH_BER(key,keylen,hashv) \ +do { \ + unsigned _hb_keylen = (unsigned)keylen; \ + const unsigned char *_hb_key = (const unsigned char*)(key); \ + (hashv) = 0; \ + while (_hb_keylen-- != 0U) { \ + (hashv) = (((hashv) << 5) + (hashv)) + *_hb_key++; \ + } \ +} while (0) + + +/* SAX/FNV/OAT/JEN hash functions are macro variants of those listed at + * http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx */ +#define HASH_SAX(key,keylen,hashv) \ +do { \ + unsigned _sx_i; \ + const unsigned char *_hs_key = (const unsigned char*)(key); \ + hashv = 0; \ + for (_sx_i=0; _sx_i < keylen; _sx_i++) { \ + hashv ^= (hashv << 5) + (hashv >> 2) + _hs_key[_sx_i]; \ + } \ +} while (0) +/* FNV-1a variation */ +#define HASH_FNV(key,keylen,hashv) \ +do { \ + unsigned _fn_i; \ + const unsigned char *_hf_key = (const unsigned char*)(key); \ + (hashv) = 2166136261U; \ + for (_fn_i=0; _fn_i < keylen; _fn_i++) { \ + hashv = hashv ^ _hf_key[_fn_i]; \ + hashv = hashv * 16777619U; \ + } \ +} while (0) + +#define HASH_OAT(key,keylen,hashv) \ +do { \ + unsigned _ho_i; \ + const unsigned char *_ho_key=(const unsigned char*)(key); \ + hashv = 0; \ + for(_ho_i=0; _ho_i < keylen; _ho_i++) { \ + hashv += _ho_key[_ho_i]; \ + hashv += (hashv << 10); \ + hashv ^= (hashv >> 6); \ + } \ + hashv += (hashv << 3); \ + hashv ^= (hashv >> 11); \ + hashv += (hashv << 15); \ +} while (0) + +#define HASH_JEN_MIX(a,b,c) \ +do { \ + a -= b; a -= c; a ^= ( c >> 13 ); \ + b -= c; b -= a; b ^= ( a << 8 ); \ + c -= a; c -= b; c ^= ( b >> 13 ); \ + a -= b; a -= c; a ^= ( c >> 12 ); \ + b -= c; b -= a; b ^= ( a << 16 ); \ + c -= a; c -= b; c ^= ( b >> 5 ); \ + a -= b; a -= c; a ^= ( c >> 3 ); \ + b -= c; b -= a; b ^= ( a << 10 ); \ + c -= a; c -= b; c ^= ( b >> 15 ); \ +} while (0) + +#define HASH_JEN(key,keylen,hashv) \ +do { \ + unsigned _hj_i,_hj_j,_hj_k; \ + unsigned const char *_hj_key=(unsigned const char*)(key); \ + hashv = 0xfeedbeefu; \ + _hj_i = _hj_j = 0x9e3779b9u; \ + _hj_k = (unsigned)(keylen); \ + while (_hj_k >= 12U) { \ + _hj_i += (_hj_key[0] + ( (unsigned)_hj_key[1] << 8 ) \ + + ( (unsigned)_hj_key[2] << 16 ) \ + + ( (unsigned)_hj_key[3] << 24 ) ); \ + _hj_j += (_hj_key[4] + ( (unsigned)_hj_key[5] << 8 ) \ + + ( (unsigned)_hj_key[6] << 16 ) \ + + ( (unsigned)_hj_key[7] << 24 ) ); \ + hashv += (_hj_key[8] + ( (unsigned)_hj_key[9] << 8 ) \ + + ( (unsigned)_hj_key[10] << 16 ) \ + + ( (unsigned)_hj_key[11] << 24 ) ); \ + \ + HASH_JEN_MIX(_hj_i, _hj_j, hashv); \ + \ + _hj_key += 12; \ + _hj_k -= 12U; \ + } \ + hashv += (unsigned)(keylen); \ + switch ( _hj_k ) { \ + case 11: hashv += ( (unsigned)_hj_key[10] << 24 ); /* FALLTHROUGH */ \ + case 10: hashv += ( (unsigned)_hj_key[9] << 16 ); /* FALLTHROUGH */ \ + case 9: hashv += ( (unsigned)_hj_key[8] << 8 ); /* FALLTHROUGH */ \ + case 8: _hj_j += ( (unsigned)_hj_key[7] << 24 ); /* FALLTHROUGH */ \ + case 7: _hj_j += ( (unsigned)_hj_key[6] << 16 ); /* FALLTHROUGH */ \ + case 6: _hj_j += ( (unsigned)_hj_key[5] << 8 ); /* FALLTHROUGH */ \ + case 5: _hj_j += _hj_key[4]; /* FALLTHROUGH */ \ + case 4: _hj_i += ( (unsigned)_hj_key[3] << 24 ); /* FALLTHROUGH */ \ + case 3: _hj_i += ( (unsigned)_hj_key[2] << 16 ); /* FALLTHROUGH */ \ + case 2: _hj_i += ( (unsigned)_hj_key[1] << 8 ); /* FALLTHROUGH */ \ + case 1: _hj_i += _hj_key[0]; /* FALLTHROUGH */ \ + default: ; \ + } \ + HASH_JEN_MIX(_hj_i, _hj_j, hashv); \ +} while (0) + +/* The Paul Hsieh hash function */ +#undef get16bits +#if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \ + || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__) +#define get16bits(d) (*((const uint16_t *) (d))) +#endif + +#if !defined (get16bits) +#define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8) \ + +(uint32_t)(((const uint8_t *)(d))[0]) ) +#endif +#define HASH_SFH(key,keylen,hashv) \ +do { \ + unsigned const char *_sfh_key=(unsigned const char*)(key); \ + uint32_t _sfh_tmp, _sfh_len = (uint32_t)keylen; \ + \ + unsigned _sfh_rem = _sfh_len & 3U; \ + _sfh_len >>= 2; \ + hashv = 0xcafebabeu; \ + \ + /* Main loop */ \ + for (;_sfh_len > 0U; _sfh_len--) { \ + hashv += get16bits (_sfh_key); \ + _sfh_tmp = ((uint32_t)(get16bits (_sfh_key+2)) << 11) ^ hashv; \ + hashv = (hashv << 16) ^ _sfh_tmp; \ + _sfh_key += 2U*sizeof (uint16_t); \ + hashv += hashv >> 11; \ + } \ + \ + /* Handle end cases */ \ + switch (_sfh_rem) { \ + case 3: hashv += get16bits (_sfh_key); \ + hashv ^= hashv << 16; \ + hashv ^= (uint32_t)(_sfh_key[sizeof (uint16_t)]) << 18; \ + hashv += hashv >> 11; \ + break; \ + case 2: hashv += get16bits (_sfh_key); \ + hashv ^= hashv << 11; \ + hashv += hashv >> 17; \ + break; \ + case 1: hashv += *_sfh_key; \ + hashv ^= hashv << 10; \ + hashv += hashv >> 1; \ + break; \ + default: ; \ + } \ + \ + /* Force "avalanching" of final 127 bits */ \ + hashv ^= hashv << 3; \ + hashv += hashv >> 5; \ + hashv ^= hashv << 4; \ + hashv += hashv >> 17; \ + hashv ^= hashv << 25; \ + hashv += hashv >> 6; \ +} while (0) + +/* iterate over items in a known bucket to find desired item */ +#define HASH_FIND_IN_BKT(tbl,hh,head,keyptr,keylen_in,hashval,out) \ +do { \ + if ((head).hh_head != NULL) { \ + DECLTYPE_ASSIGN(out, ELMT_FROM_HH(tbl, (head).hh_head)); \ + } else { \ + (out) = NULL; \ + } \ + while ((out) != NULL) { \ + if ((out)->hh.hashv == (hashval) && (out)->hh.keylen == (keylen_in)) { \ + if (HASH_KEYCMP((out)->hh.key, keyptr, keylen_in) == 0) { \ + break; \ + } \ + } \ + if ((out)->hh.hh_next != NULL) { \ + DECLTYPE_ASSIGN(out, ELMT_FROM_HH(tbl, (out)->hh.hh_next)); \ + } else { \ + (out) = NULL; \ + } \ + } \ +} while (0) + +/* add an item to a bucket */ +#define HASH_ADD_TO_BKT(head,hh,addhh,oomed) \ +do { \ + UT_hash_bucket *_ha_head = &(head); \ + _ha_head->count++; \ + (addhh)->hh_next = _ha_head->hh_head; \ + (addhh)->hh_prev = NULL; \ + if (_ha_head->hh_head != NULL) { \ + _ha_head->hh_head->hh_prev = (addhh); \ + } \ + _ha_head->hh_head = (addhh); \ + if ((_ha_head->count >= ((_ha_head->expand_mult + 1U) * HASH_BKT_CAPACITY_THRESH)) \ + && !(addhh)->tbl->noexpand) { \ + HASH_EXPAND_BUCKETS(addhh,(addhh)->tbl, oomed); \ + IF_HASH_NONFATAL_OOM( \ + if (oomed) { \ + HASH_DEL_IN_BKT(head,addhh); \ + } \ + ) \ + } \ +} while (0) + +/* remove an item from a given bucket */ +#define HASH_DEL_IN_BKT(head,delhh) \ +do { \ + UT_hash_bucket *_hd_head = &(head); \ + _hd_head->count--; \ + if (_hd_head->hh_head == (delhh)) { \ + _hd_head->hh_head = (delhh)->hh_next; \ + } \ + if ((delhh)->hh_prev) { \ + (delhh)->hh_prev->hh_next = (delhh)->hh_next; \ + } \ + if ((delhh)->hh_next) { \ + (delhh)->hh_next->hh_prev = (delhh)->hh_prev; \ + } \ +} while (0) + +/* Bucket expansion has the effect of doubling the number of buckets + * and redistributing the items into the new buckets. Ideally the + * items will distribute more or less evenly into the new buckets + * (the extent to which this is true is a measure of the quality of + * the hash function as it applies to the key domain). + * + * With the items distributed into more buckets, the chain length + * (item count) in each bucket is reduced. Thus by expanding buckets + * the hash keeps a bound on the chain length. This bounded chain + * length is the essence of how a hash provides constant time lookup. + * + * The calculation of tbl->ideal_chain_maxlen below deserves some + * explanation. First, keep in mind that we're calculating the ideal + * maximum chain length based on the *new* (doubled) bucket count. + * In fractions this is just n/b (n=number of items,b=new num buckets). + * Since the ideal chain length is an integer, we want to calculate + * ceil(n/b). We don't depend on floating point arithmetic in this + * hash, so to calculate ceil(n/b) with integers we could write + * + * ceil(n/b) = (n/b) + ((n%b)?1:0) + * + * and in fact a previous version of this hash did just that. + * But now we have improved things a bit by recognizing that b is + * always a power of two. We keep its base 2 log handy (call it lb), + * so now we can write this with a bit shift and logical AND: + * + * ceil(n/b) = (n>>lb) + ( (n & (b-1)) ? 1:0) + * + */ +#define HASH_EXPAND_BUCKETS(hh,tbl,oomed) \ +do { \ + unsigned _he_bkt; \ + unsigned _he_bkt_i; \ + struct UT_hash_handle *_he_thh, *_he_hh_nxt; \ + UT_hash_bucket *_he_new_buckets, *_he_newbkt; \ + _he_new_buckets = (UT_hash_bucket*)uthash_malloc( \ + sizeof(struct UT_hash_bucket) * (tbl)->num_buckets * 2U); \ + if (!_he_new_buckets) { \ + HASH_RECORD_OOM(oomed); \ + } else { \ + uthash_bzero(_he_new_buckets, \ + sizeof(struct UT_hash_bucket) * (tbl)->num_buckets * 2U); \ + (tbl)->ideal_chain_maxlen = \ + ((tbl)->num_items >> ((tbl)->log2_num_buckets+1U)) + \ + ((((tbl)->num_items & (((tbl)->num_buckets*2U)-1U)) != 0U) ? 1U : 0U); \ + (tbl)->nonideal_items = 0; \ + for (_he_bkt_i = 0; _he_bkt_i < (tbl)->num_buckets; _he_bkt_i++) { \ + _he_thh = (tbl)->buckets[ _he_bkt_i ].hh_head; \ + while (_he_thh != NULL) { \ + _he_hh_nxt = _he_thh->hh_next; \ + HASH_TO_BKT(_he_thh->hashv, (tbl)->num_buckets * 2U, _he_bkt); \ + _he_newbkt = &(_he_new_buckets[_he_bkt]); \ + if (++(_he_newbkt->count) > (tbl)->ideal_chain_maxlen) { \ + (tbl)->nonideal_items++; \ + if (_he_newbkt->count > _he_newbkt->expand_mult * (tbl)->ideal_chain_maxlen) { \ + _he_newbkt->expand_mult++; \ + } \ + } \ + _he_thh->hh_prev = NULL; \ + _he_thh->hh_next = _he_newbkt->hh_head; \ + if (_he_newbkt->hh_head != NULL) { \ + _he_newbkt->hh_head->hh_prev = _he_thh; \ + } \ + _he_newbkt->hh_head = _he_thh; \ + _he_thh = _he_hh_nxt; \ + } \ + } \ + uthash_free((tbl)->buckets, (tbl)->num_buckets * sizeof(struct UT_hash_bucket)); \ + (tbl)->num_buckets *= 2U; \ + (tbl)->log2_num_buckets++; \ + (tbl)->buckets = _he_new_buckets; \ + (tbl)->ineff_expands = ((tbl)->nonideal_items > ((tbl)->num_items >> 1)) ? \ + ((tbl)->ineff_expands+1U) : 0U; \ + if ((tbl)->ineff_expands > 1U) { \ + (tbl)->noexpand = 1; \ + uthash_noexpand_fyi(tbl); \ + } \ + uthash_expand_fyi(tbl); \ + } \ +} while (0) + + +/* This is an adaptation of Simon Tatham's O(n log(n)) mergesort */ +/* Note that HASH_SORT assumes the hash handle name to be hh. + * HASH_SRT was added to allow the hash handle name to be passed in. */ +#define HASH_SORT(head,cmpfcn) HASH_SRT(hh,head,cmpfcn) +#define HASH_SRT(hh,head,cmpfcn) \ +do { \ + unsigned _hs_i; \ + unsigned _hs_looping,_hs_nmerges,_hs_insize,_hs_psize,_hs_qsize; \ + struct UT_hash_handle *_hs_p, *_hs_q, *_hs_e, *_hs_list, *_hs_tail; \ + if (head != NULL) { \ + _hs_insize = 1; \ + _hs_looping = 1; \ + _hs_list = &((head)->hh); \ + while (_hs_looping != 0U) { \ + _hs_p = _hs_list; \ + _hs_list = NULL; \ + _hs_tail = NULL; \ + _hs_nmerges = 0; \ + while (_hs_p != NULL) { \ + _hs_nmerges++; \ + _hs_q = _hs_p; \ + _hs_psize = 0; \ + for (_hs_i = 0; _hs_i < _hs_insize; ++_hs_i) { \ + _hs_psize++; \ + _hs_q = ((_hs_q->next != NULL) ? \ + HH_FROM_ELMT((head)->hh.tbl, _hs_q->next) : NULL); \ + if (_hs_q == NULL) { \ + break; \ + } \ + } \ + _hs_qsize = _hs_insize; \ + while ((_hs_psize != 0U) || ((_hs_qsize != 0U) && (_hs_q != NULL))) { \ + if (_hs_psize == 0U) { \ + _hs_e = _hs_q; \ + _hs_q = ((_hs_q->next != NULL) ? \ + HH_FROM_ELMT((head)->hh.tbl, _hs_q->next) : NULL); \ + _hs_qsize--; \ + } else if ((_hs_qsize == 0U) || (_hs_q == NULL)) { \ + _hs_e = _hs_p; \ + if (_hs_p != NULL) { \ + _hs_p = ((_hs_p->next != NULL) ? \ + HH_FROM_ELMT((head)->hh.tbl, _hs_p->next) : NULL); \ + } \ + _hs_psize--; \ + } else if ((cmpfcn( \ + DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl, _hs_p)), \ + DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl, _hs_q)) \ + )) <= 0) { \ + _hs_e = _hs_p; \ + if (_hs_p != NULL) { \ + _hs_p = ((_hs_p->next != NULL) ? \ + HH_FROM_ELMT((head)->hh.tbl, _hs_p->next) : NULL); \ + } \ + _hs_psize--; \ + } else { \ + _hs_e = _hs_q; \ + _hs_q = ((_hs_q->next != NULL) ? \ + HH_FROM_ELMT((head)->hh.tbl, _hs_q->next) : NULL); \ + _hs_qsize--; \ + } \ + if ( _hs_tail != NULL ) { \ + _hs_tail->next = ((_hs_e != NULL) ? \ + ELMT_FROM_HH((head)->hh.tbl, _hs_e) : NULL); \ + } else { \ + _hs_list = _hs_e; \ + } \ + if (_hs_e != NULL) { \ + _hs_e->prev = ((_hs_tail != NULL) ? \ + ELMT_FROM_HH((head)->hh.tbl, _hs_tail) : NULL); \ + } \ + _hs_tail = _hs_e; \ + } \ + _hs_p = _hs_q; \ + } \ + if (_hs_tail != NULL) { \ + _hs_tail->next = NULL; \ + } \ + if (_hs_nmerges <= 1U) { \ + _hs_looping = 0; \ + (head)->hh.tbl->tail = _hs_tail; \ + DECLTYPE_ASSIGN(head, ELMT_FROM_HH((head)->hh.tbl, _hs_list)); \ + } \ + _hs_insize *= 2U; \ + } \ + HASH_FSCK(hh, head, "HASH_SRT"); \ + } \ +} while (0) + +/* This function selects items from one hash into another hash. + * The end result is that the selected items have dual presence + * in both hashes. There is no copy of the items made; rather + * they are added into the new hash through a secondary hash + * hash handle that must be present in the structure. */ +#define HASH_SELECT(hh_dst, dst, hh_src, src, cond) \ +do { \ + unsigned _src_bkt, _dst_bkt; \ + void *_last_elt = NULL, *_elt; \ + UT_hash_handle *_src_hh, *_dst_hh, *_last_elt_hh=NULL; \ + ptrdiff_t _dst_hho = ((char*)(&(dst)->hh_dst) - (char*)(dst)); \ + if ((src) != NULL) { \ + for (_src_bkt=0; _src_bkt < (src)->hh_src.tbl->num_buckets; _src_bkt++) { \ + for (_src_hh = (src)->hh_src.tbl->buckets[_src_bkt].hh_head; \ + _src_hh != NULL; \ + _src_hh = _src_hh->hh_next) { \ + _elt = ELMT_FROM_HH((src)->hh_src.tbl, _src_hh); \ + if (cond(_elt)) { \ + IF_HASH_NONFATAL_OOM( int _hs_oomed = 0; ) \ + _dst_hh = (UT_hash_handle*)(void*)(((char*)_elt) + _dst_hho); \ + _dst_hh->key = _src_hh->key; \ + _dst_hh->keylen = _src_hh->keylen; \ + _dst_hh->hashv = _src_hh->hashv; \ + _dst_hh->prev = _last_elt; \ + _dst_hh->next = NULL; \ + if (_last_elt_hh != NULL) { \ + _last_elt_hh->next = _elt; \ + } \ + if ((dst) == NULL) { \ + DECLTYPE_ASSIGN(dst, _elt); \ + HASH_MAKE_TABLE(hh_dst, dst, _hs_oomed); \ + IF_HASH_NONFATAL_OOM( \ + if (_hs_oomed) { \ + uthash_nonfatal_oom(_elt); \ + (dst) = NULL; \ + continue; \ + } \ + ) \ + } else { \ + _dst_hh->tbl = (dst)->hh_dst.tbl; \ + } \ + HASH_TO_BKT(_dst_hh->hashv, _dst_hh->tbl->num_buckets, _dst_bkt); \ + HASH_ADD_TO_BKT(_dst_hh->tbl->buckets[_dst_bkt], hh_dst, _dst_hh, _hs_oomed); \ + (dst)->hh_dst.tbl->num_items++; \ + IF_HASH_NONFATAL_OOM( \ + if (_hs_oomed) { \ + HASH_ROLLBACK_BKT(hh_dst, dst, _dst_hh); \ + HASH_DELETE_HH(hh_dst, dst, _dst_hh); \ + _dst_hh->tbl = NULL; \ + uthash_nonfatal_oom(_elt); \ + continue; \ + } \ + ) \ + HASH_BLOOM_ADD(_dst_hh->tbl, _dst_hh->hashv); \ + _last_elt = _elt; \ + _last_elt_hh = _dst_hh; \ + } \ + } \ + } \ + } \ + HASH_FSCK(hh_dst, dst, "HASH_SELECT"); \ +} while (0) + +#define HASH_CLEAR(hh,head) \ +do { \ + if ((head) != NULL) { \ + HASH_BLOOM_FREE((head)->hh.tbl); \ + uthash_free((head)->hh.tbl->buckets, \ + (head)->hh.tbl->num_buckets*sizeof(struct UT_hash_bucket)); \ + uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \ + (head) = NULL; \ + } \ +} while (0) + +#define HASH_OVERHEAD(hh,head) \ + (((head) != NULL) ? ( \ + (size_t)(((head)->hh.tbl->num_items * sizeof(UT_hash_handle)) + \ + ((head)->hh.tbl->num_buckets * sizeof(UT_hash_bucket)) + \ + sizeof(UT_hash_table) + \ + (HASH_BLOOM_BYTELEN))) : 0U) + +#ifdef NO_DECLTYPE +#define HASH_ITER(hh,head,el,tmp) \ +for(((el)=(head)), ((*(char**)(&(tmp)))=(char*)((head!=NULL)?(head)->hh.next:NULL)); \ + (el) != NULL; ((el)=(tmp)), ((*(char**)(&(tmp)))=(char*)((tmp!=NULL)?(tmp)->hh.next:NULL))) +#else +#define HASH_ITER(hh,head,el,tmp) \ +for(((el)=(head)), ((tmp)=DECLTYPE(el)((head!=NULL)?(head)->hh.next:NULL)); \ + (el) != NULL; ((el)=(tmp)), ((tmp)=DECLTYPE(el)((tmp!=NULL)?(tmp)->hh.next:NULL))) +#endif + +/* obtain a count of items in the hash */ +#define HASH_COUNT(head) HASH_CNT(hh,head) +#define HASH_CNT(hh,head) ((head != NULL)?((head)->hh.tbl->num_items):0U) + +typedef struct UT_hash_bucket { + struct UT_hash_handle *hh_head; + unsigned count; + + /* expand_mult is normally set to 0. In this situation, the max chain length + * threshold is enforced at its default value, HASH_BKT_CAPACITY_THRESH. (If + * the bucket's chain exceeds this length, bucket expansion is triggered). + * However, setting expand_mult to a non-zero value delays bucket expansion + * (that would be triggered by additions to this particular bucket) + * until its chain length reaches a *multiple* of HASH_BKT_CAPACITY_THRESH. + * (The multiplier is simply expand_mult+1). The whole idea of this + * multiplier is to reduce bucket expansions, since they are expensive, in + * situations where we know that a particular bucket tends to be overused. + * It is better to let its chain length grow to a longer yet-still-bounded + * value, than to do an O(n) bucket expansion too often. + */ + unsigned expand_mult; + +} UT_hash_bucket; + +/* random signature used only to find hash tables in external analysis */ +#define HASH_SIGNATURE 0xa0111fe1u +#define HASH_BLOOM_SIGNATURE 0xb12220f2u + +typedef struct UT_hash_table { + UT_hash_bucket *buckets; + unsigned num_buckets, log2_num_buckets; + unsigned num_items; + struct UT_hash_handle *tail; /* tail hh in app order, for fast append */ + ptrdiff_t hho; /* hash handle offset (byte pos of hash handle in element */ + + /* in an ideal situation (all buckets used equally), no bucket would have + * more than ceil(#items/#buckets) items. that's the ideal chain length. */ + unsigned ideal_chain_maxlen; + + /* nonideal_items is the number of items in the hash whose chain position + * exceeds the ideal chain maxlen. these items pay the penalty for an uneven + * hash distribution; reaching them in a chain traversal takes >ideal steps */ + unsigned nonideal_items; + + /* ineffective expands occur when a bucket doubling was performed, but + * afterward, more than half the items in the hash had nonideal chain + * positions. If this happens on two consecutive expansions we inhibit any + * further expansion, as it's not helping; this happens when the hash + * function isn't a good fit for the key domain. When expansion is inhibited + * the hash will still work, albeit no longer in constant time. */ + unsigned ineff_expands, noexpand; + + uint32_t signature; /* used only to find hash tables in external analysis */ +#ifdef HASH_BLOOM + uint32_t bloom_sig; /* used only to test bloom exists in external analysis */ + uint8_t *bloom_bv; + uint8_t bloom_nbits; +#endif + +} UT_hash_table; + +typedef struct UT_hash_handle { + struct UT_hash_table *tbl; + void *prev; /* prev element in app order */ + void *next; /* next element in app order */ + struct UT_hash_handle *hh_prev; /* previous hh in bucket order */ + struct UT_hash_handle *hh_next; /* next hh in bucket order */ + const void *key; /* ptr to enclosing struct's key */ + unsigned keylen; /* enclosing struct's key len */ + unsigned hashv; /* result of hash-fcn(key) */ +} UT_hash_handle; + +#endif /* UTHASH_H */ diff --git a/test/uthash-2.3.0/include/utlist.h b/test/uthash-2.3.0/include/utlist.h new file mode 100644 index 0000000..6230a67 --- /dev/null +++ b/test/uthash-2.3.0/include/utlist.h @@ -0,0 +1,1073 @@ +/* +Copyright (c) 2007-2021, Troy D. Hanson http://troydhanson.github.com/uthash/ +All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS +IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED +TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A +PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER +OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, +EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, +PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR +PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF +LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING +NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS +SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +#ifndef UTLIST_H +#define UTLIST_H + +#define UTLIST_VERSION 2.3.0 + +#include <assert.h> + +/* + * This file contains macros to manipulate singly and doubly-linked lists. + * + * 1. LL_ macros: singly-linked lists. + * 2. DL_ macros: doubly-linked lists. + * 3. CDL_ macros: circular doubly-linked lists. + * + * To use singly-linked lists, your structure must have a "next" pointer. + * To use doubly-linked lists, your structure must "prev" and "next" pointers. + * Either way, the pointer to the head of the list must be initialized to NULL. + * + * ----------------.EXAMPLE ------------------------- + * struct item { + * int id; + * struct item *prev, *next; + * } + * + * struct item *list = NULL: + * + * int main() { + * struct item *item; + * ... allocate and populate item ... + * DL_APPEND(list, item); + * } + * -------------------------------------------------- + * + * For doubly-linked lists, the append and delete macros are O(1) + * For singly-linked lists, append and delete are O(n) but prepend is O(1) + * The sort macro is O(n log(n)) for all types of single/double/circular lists. + */ + +/* These macros use decltype or the earlier __typeof GNU extension. + As decltype is only available in newer compilers (VS2010 or gcc 4.3+ + when compiling c++ source) this code uses whatever method is needed + or, for VS2008 where neither is available, uses casting workarounds. */ +#if !defined(LDECLTYPE) && !defined(NO_DECLTYPE) +#if defined(_MSC_VER) /* MS compiler */ +#if _MSC_VER >= 1600 && defined(__cplusplus) /* VS2010 or newer in C++ mode */ +#define LDECLTYPE(x) decltype(x) +#else /* VS2008 or older (or VS2010 in C mode) */ +#define NO_DECLTYPE +#endif +#elif defined(__BORLANDC__) || defined(__ICCARM__) || defined(__LCC__) || defined(__WATCOMC__) +#define NO_DECLTYPE +#else /* GNU, Sun and other compilers */ +#define LDECLTYPE(x) __typeof(x) +#endif +#endif + +/* for VS2008 we use some workarounds to get around the lack of decltype, + * namely, we always reassign our tmp variable to the list head if we need + * to dereference its prev/next pointers, and save/restore the real head.*/ +#ifdef NO_DECLTYPE +#define IF_NO_DECLTYPE(x) x +#define LDECLTYPE(x) char* +#define UTLIST_SV(elt,list) _tmp = (char*)(list); {char **_alias = (char**)&(list); *_alias = (elt); } +#define UTLIST_NEXT(elt,list,next) ((char*)((list)->next)) +#define UTLIST_NEXTASGN(elt,list,to,next) { char **_alias = (char**)&((list)->next); *_alias=(char*)(to); } +/* #define UTLIST_PREV(elt,list,prev) ((char*)((list)->prev)) */ +#define UTLIST_PREVASGN(elt,list,to,prev) { char **_alias = (char**)&((list)->prev); *_alias=(char*)(to); } +#define UTLIST_RS(list) { char **_alias = (char**)&(list); *_alias=_tmp; } +#define UTLIST_CASTASGN(a,b) { char **_alias = (char**)&(a); *_alias=(char*)(b); } +#else +#define IF_NO_DECLTYPE(x) +#define UTLIST_SV(elt,list) +#define UTLIST_NEXT(elt,list,next) ((elt)->next) +#define UTLIST_NEXTASGN(elt,list,to,next) ((elt)->next)=(to) +/* #define UTLIST_PREV(elt,list,prev) ((elt)->prev) */ +#define UTLIST_PREVASGN(elt,list,to,prev) ((elt)->prev)=(to) +#define UTLIST_RS(list) +#define UTLIST_CASTASGN(a,b) (a)=(b) +#endif + +/****************************************************************************** + * The sort macro is an adaptation of Simon Tatham's O(n log(n)) mergesort * + * Unwieldy variable names used here to avoid shadowing passed-in variables. * + *****************************************************************************/ +#define LL_SORT(list, cmp) \ + LL_SORT2(list, cmp, next) + +#define LL_SORT2(list, cmp, next) \ +do { \ + LDECLTYPE(list) _ls_p; \ + LDECLTYPE(list) _ls_q; \ + LDECLTYPE(list) _ls_e; \ + LDECLTYPE(list) _ls_tail; \ + IF_NO_DECLTYPE(LDECLTYPE(list) _tmp;) \ + int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \ + if (list) { \ + _ls_insize = 1; \ + _ls_looping = 1; \ + while (_ls_looping) { \ + UTLIST_CASTASGN(_ls_p,list); \ + (list) = NULL; \ + _ls_tail = NULL; \ + _ls_nmerges = 0; \ + while (_ls_p) { \ + _ls_nmerges++; \ + _ls_q = _ls_p; \ + _ls_psize = 0; \ + for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ + _ls_psize++; \ + UTLIST_SV(_ls_q,list); _ls_q = UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); \ + if (!_ls_q) break; \ + } \ + _ls_qsize = _ls_insize; \ + while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \ + if (_ls_psize == 0) { \ + _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q = \ + UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--; \ + } else if (_ls_qsize == 0 || !_ls_q) { \ + _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p = \ + UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--; \ + } else if (cmp(_ls_p,_ls_q) <= 0) { \ + _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p = \ + UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--; \ + } else { \ + _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q = \ + UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--; \ + } \ + if (_ls_tail) { \ + UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,_ls_e,next); UTLIST_RS(list); \ + } else { \ + UTLIST_CASTASGN(list,_ls_e); \ + } \ + _ls_tail = _ls_e; \ + } \ + _ls_p = _ls_q; \ + } \ + if (_ls_tail) { \ + UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,NULL,next); UTLIST_RS(list); \ + } \ + if (_ls_nmerges <= 1) { \ + _ls_looping=0; \ + } \ + _ls_insize *= 2; \ + } \ + } \ +} while (0) + + +#define DL_SORT(list, cmp) \ + DL_SORT2(list, cmp, prev, next) + +#define DL_SORT2(list, cmp, prev, next) \ +do { \ + LDECLTYPE(list) _ls_p; \ + LDECLTYPE(list) _ls_q; \ + LDECLTYPE(list) _ls_e; \ + LDECLTYPE(list) _ls_tail; \ + IF_NO_DECLTYPE(LDECLTYPE(list) _tmp;) \ + int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \ + if (list) { \ + _ls_insize = 1; \ + _ls_looping = 1; \ + while (_ls_looping) { \ + UTLIST_CASTASGN(_ls_p,list); \ + (list) = NULL; \ + _ls_tail = NULL; \ + _ls_nmerges = 0; \ + while (_ls_p) { \ + _ls_nmerges++; \ + _ls_q = _ls_p; \ + _ls_psize = 0; \ + for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ + _ls_psize++; \ + UTLIST_SV(_ls_q,list); _ls_q = UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); \ + if (!_ls_q) break; \ + } \ + _ls_qsize = _ls_insize; \ + while ((_ls_psize > 0) || ((_ls_qsize > 0) && _ls_q)) { \ + if (_ls_psize == 0) { \ + _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q = \ + UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--; \ + } else if ((_ls_qsize == 0) || (!_ls_q)) { \ + _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p = \ + UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--; \ + } else if (cmp(_ls_p,_ls_q) <= 0) { \ + _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p = \ + UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--; \ + } else { \ + _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q = \ + UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--; \ + } \ + if (_ls_tail) { \ + UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,_ls_e,next); UTLIST_RS(list); \ + } else { \ + UTLIST_CASTASGN(list,_ls_e); \ + } \ + UTLIST_SV(_ls_e,list); UTLIST_PREVASGN(_ls_e,list,_ls_tail,prev); UTLIST_RS(list); \ + _ls_tail = _ls_e; \ + } \ + _ls_p = _ls_q; \ + } \ + UTLIST_CASTASGN((list)->prev, _ls_tail); \ + UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,NULL,next); UTLIST_RS(list); \ + if (_ls_nmerges <= 1) { \ + _ls_looping=0; \ + } \ + _ls_insize *= 2; \ + } \ + } \ +} while (0) + +#define CDL_SORT(list, cmp) \ + CDL_SORT2(list, cmp, prev, next) + +#define CDL_SORT2(list, cmp, prev, next) \ +do { \ + LDECLTYPE(list) _ls_p; \ + LDECLTYPE(list) _ls_q; \ + LDECLTYPE(list) _ls_e; \ + LDECLTYPE(list) _ls_tail; \ + LDECLTYPE(list) _ls_oldhead; \ + LDECLTYPE(list) _tmp; \ + int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \ + if (list) { \ + _ls_insize = 1; \ + _ls_looping = 1; \ + while (_ls_looping) { \ + UTLIST_CASTASGN(_ls_p,list); \ + UTLIST_CASTASGN(_ls_oldhead,list); \ + (list) = NULL; \ + _ls_tail = NULL; \ + _ls_nmerges = 0; \ + while (_ls_p) { \ + _ls_nmerges++; \ + _ls_q = _ls_p; \ + _ls_psize = 0; \ + for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ + _ls_psize++; \ + UTLIST_SV(_ls_q,list); \ + if (UTLIST_NEXT(_ls_q,list,next) == _ls_oldhead) { \ + _ls_q = NULL; \ + } else { \ + _ls_q = UTLIST_NEXT(_ls_q,list,next); \ + } \ + UTLIST_RS(list); \ + if (!_ls_q) break; \ + } \ + _ls_qsize = _ls_insize; \ + while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \ + if (_ls_psize == 0) { \ + _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q = \ + UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--; \ + if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \ + } else if (_ls_qsize == 0 || !_ls_q) { \ + _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p = \ + UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--; \ + if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \ + } else if (cmp(_ls_p,_ls_q) <= 0) { \ + _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p = \ + UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--; \ + if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \ + } else { \ + _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q = \ + UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--; \ + if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \ + } \ + if (_ls_tail) { \ + UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,_ls_e,next); UTLIST_RS(list); \ + } else { \ + UTLIST_CASTASGN(list,_ls_e); \ + } \ + UTLIST_SV(_ls_e,list); UTLIST_PREVASGN(_ls_e,list,_ls_tail,prev); UTLIST_RS(list); \ + _ls_tail = _ls_e; \ + } \ + _ls_p = _ls_q; \ + } \ + UTLIST_CASTASGN((list)->prev,_ls_tail); \ + UTLIST_CASTASGN(_tmp,list); \ + UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,_tmp,next); UTLIST_RS(list); \ + if (_ls_nmerges <= 1) { \ + _ls_looping=0; \ + } \ + _ls_insize *= 2; \ + } \ + } \ +} while (0) + +/****************************************************************************** + * singly linked list macros (non-circular) * + *****************************************************************************/ +#define LL_PREPEND(head,add) \ + LL_PREPEND2(head,add,next) + +#define LL_PREPEND2(head,add,next) \ +do { \ + (add)->next = (head); \ + (head) = (add); \ +} while (0) + +#define LL_CONCAT(head1,head2) \ + LL_CONCAT2(head1,head2,next) + +#define LL_CONCAT2(head1,head2,next) \ +do { \ + LDECLTYPE(head1) _tmp; \ + if (head1) { \ + _tmp = (head1); \ + while (_tmp->next) { _tmp = _tmp->next; } \ + _tmp->next=(head2); \ + } else { \ + (head1)=(head2); \ + } \ +} while (0) + +#define LL_APPEND(head,add) \ + LL_APPEND2(head,add,next) + +#define LL_APPEND2(head,add,next) \ +do { \ + LDECLTYPE(head) _tmp; \ + (add)->next=NULL; \ + if (head) { \ + _tmp = (head); \ + while (_tmp->next) { _tmp = _tmp->next; } \ + _tmp->next=(add); \ + } else { \ + (head)=(add); \ + } \ +} while (0) + +#define LL_INSERT_INORDER(head,add,cmp) \ + LL_INSERT_INORDER2(head,add,cmp,next) + +#define LL_INSERT_INORDER2(head,add,cmp,next) \ +do { \ + LDECLTYPE(head) _tmp; \ + if (head) { \ + LL_LOWER_BOUND2(head, _tmp, add, cmp, next); \ + LL_APPEND_ELEM2(head, _tmp, add, next); \ + } else { \ + (head) = (add); \ + (head)->next = NULL; \ + } \ +} while (0) + +#define LL_LOWER_BOUND(head,elt,like,cmp) \ + LL_LOWER_BOUND2(head,elt,like,cmp,next) + +#define LL_LOWER_BOUND2(head,elt,like,cmp,next) \ + do { \ + if ((head) == NULL || (cmp(head, like)) >= 0) { \ + (elt) = NULL; \ + } else { \ + for ((elt) = (head); (elt)->next != NULL; (elt) = (elt)->next) { \ + if (cmp((elt)->next, like) >= 0) { \ + break; \ + } \ + } \ + } \ + } while (0) + +#define LL_DELETE(head,del) \ + LL_DELETE2(head,del,next) + +#define LL_DELETE2(head,del,next) \ +do { \ + LDECLTYPE(head) _tmp; \ + if ((head) == (del)) { \ + (head)=(head)->next; \ + } else { \ + _tmp = (head); \ + while (_tmp->next && (_tmp->next != (del))) { \ + _tmp = _tmp->next; \ + } \ + if (_tmp->next) { \ + _tmp->next = (del)->next; \ + } \ + } \ +} while (0) + +#define LL_COUNT(head,el,counter) \ + LL_COUNT2(head,el,counter,next) \ + +#define LL_COUNT2(head,el,counter,next) \ +do { \ + (counter) = 0; \ + LL_FOREACH2(head,el,next) { ++(counter); } \ +} while (0) + +#define LL_FOREACH(head,el) \ + LL_FOREACH2(head,el,next) + +#define LL_FOREACH2(head,el,next) \ + for ((el) = (head); el; (el) = (el)->next) + +#define LL_FOREACH_SAFE(head,el,tmp) \ + LL_FOREACH_SAFE2(head,el,tmp,next) + +#define LL_FOREACH_SAFE2(head,el,tmp,next) \ + for ((el) = (head); (el) && ((tmp) = (el)->next, 1); (el) = (tmp)) + +#define LL_SEARCH_SCALAR(head,out,field,val) \ + LL_SEARCH_SCALAR2(head,out,field,val,next) + +#define LL_SEARCH_SCALAR2(head,out,field,val,next) \ +do { \ + LL_FOREACH2(head,out,next) { \ + if ((out)->field == (val)) break; \ + } \ +} while (0) + +#define LL_SEARCH(head,out,elt,cmp) \ + LL_SEARCH2(head,out,elt,cmp,next) + +#define LL_SEARCH2(head,out,elt,cmp,next) \ +do { \ + LL_FOREACH2(head,out,next) { \ + if ((cmp(out,elt))==0) break; \ + } \ +} while (0) + +#define LL_REPLACE_ELEM2(head, el, add, next) \ +do { \ + LDECLTYPE(head) _tmp; \ + assert((head) != NULL); \ + assert((el) != NULL); \ + assert((add) != NULL); \ + (add)->next = (el)->next; \ + if ((head) == (el)) { \ + (head) = (add); \ + } else { \ + _tmp = (head); \ + while (_tmp->next && (_tmp->next != (el))) { \ + _tmp = _tmp->next; \ + } \ + if (_tmp->next) { \ + _tmp->next = (add); \ + } \ + } \ +} while (0) + +#define LL_REPLACE_ELEM(head, el, add) \ + LL_REPLACE_ELEM2(head, el, add, next) + +#define LL_PREPEND_ELEM2(head, el, add, next) \ +do { \ + if (el) { \ + LDECLTYPE(head) _tmp; \ + assert((head) != NULL); \ + assert((add) != NULL); \ + (add)->next = (el); \ + if ((head) == (el)) { \ + (head) = (add); \ + } else { \ + _tmp = (head); \ + while (_tmp->next && (_tmp->next != (el))) { \ + _tmp = _tmp->next; \ + } \ + if (_tmp->next) { \ + _tmp->next = (add); \ + } \ + } \ + } else { \ + LL_APPEND2(head, add, next); \ + } \ +} while (0) \ + +#define LL_PREPEND_ELEM(head, el, add) \ + LL_PREPEND_ELEM2(head, el, add, next) + +#define LL_APPEND_ELEM2(head, el, add, next) \ +do { \ + if (el) { \ + assert((head) != NULL); \ + assert((add) != NULL); \ + (add)->next = (el)->next; \ + (el)->next = (add); \ + } else { \ + LL_PREPEND2(head, add, next); \ + } \ +} while (0) \ + +#define LL_APPEND_ELEM(head, el, add) \ + LL_APPEND_ELEM2(head, el, add, next) + +#ifdef NO_DECLTYPE +/* Here are VS2008 / NO_DECLTYPE replacements for a few functions */ + +#undef LL_CONCAT2 +#define LL_CONCAT2(head1,head2,next) \ +do { \ + char *_tmp; \ + if (head1) { \ + _tmp = (char*)(head1); \ + while ((head1)->next) { (head1) = (head1)->next; } \ + (head1)->next = (head2); \ + UTLIST_RS(head1); \ + } else { \ + (head1)=(head2); \ + } \ +} while (0) + +#undef LL_APPEND2 +#define LL_APPEND2(head,add,next) \ +do { \ + if (head) { \ + (add)->next = head; /* use add->next as a temp variable */ \ + while ((add)->next->next) { (add)->next = (add)->next->next; } \ + (add)->next->next=(add); \ + } else { \ + (head)=(add); \ + } \ + (add)->next=NULL; \ +} while (0) + +#undef LL_INSERT_INORDER2 +#define LL_INSERT_INORDER2(head,add,cmp,next) \ +do { \ + if ((head) == NULL || (cmp(head, add)) >= 0) { \ + (add)->next = (head); \ + (head) = (add); \ + } else { \ + char *_tmp = (char*)(head); \ + while ((head)->next != NULL && (cmp((head)->next, add)) < 0) { \ + (head) = (head)->next; \ + } \ + (add)->next = (head)->next; \ + (head)->next = (add); \ + UTLIST_RS(head); \ + } \ +} while (0) + +#undef LL_DELETE2 +#define LL_DELETE2(head,del,next) \ +do { \ + if ((head) == (del)) { \ + (head)=(head)->next; \ + } else { \ + char *_tmp = (char*)(head); \ + while ((head)->next && ((head)->next != (del))) { \ + (head) = (head)->next; \ + } \ + if ((head)->next) { \ + (head)->next = ((del)->next); \ + } \ + UTLIST_RS(head); \ + } \ +} while (0) + +#undef LL_REPLACE_ELEM2 +#define LL_REPLACE_ELEM2(head, el, add, next) \ +do { \ + assert((head) != NULL); \ + assert((el) != NULL); \ + assert((add) != NULL); \ + if ((head) == (el)) { \ + (head) = (add); \ + } else { \ + (add)->next = head; \ + while ((add)->next->next && ((add)->next->next != (el))) { \ + (add)->next = (add)->next->next; \ + } \ + if ((add)->next->next) { \ + (add)->next->next = (add); \ + } \ + } \ + (add)->next = (el)->next; \ +} while (0) + +#undef LL_PREPEND_ELEM2 +#define LL_PREPEND_ELEM2(head, el, add, next) \ +do { \ + if (el) { \ + assert((head) != NULL); \ + assert((add) != NULL); \ + if ((head) == (el)) { \ + (head) = (add); \ + } else { \ + (add)->next = (head); \ + while ((add)->next->next && ((add)->next->next != (el))) { \ + (add)->next = (add)->next->next; \ + } \ + if ((add)->next->next) { \ + (add)->next->next = (add); \ + } \ + } \ + (add)->next = (el); \ + } else { \ + LL_APPEND2(head, add, next); \ + } \ +} while (0) \ + +#endif /* NO_DECLTYPE */ + +/****************************************************************************** + * doubly linked list macros (non-circular) * + *****************************************************************************/ +#define DL_PREPEND(head,add) \ + DL_PREPEND2(head,add,prev,next) + +#define DL_PREPEND2(head,add,prev,next) \ +do { \ + (add)->next = (head); \ + if (head) { \ + (add)->prev = (head)->prev; \ + (head)->prev = (add); \ + } else { \ + (add)->prev = (add); \ + } \ + (head) = (add); \ +} while (0) + +#define DL_APPEND(head,add) \ + DL_APPEND2(head,add,prev,next) + +#define DL_APPEND2(head,add,prev,next) \ +do { \ + if (head) { \ + (add)->prev = (head)->prev; \ + (head)->prev->next = (add); \ + (head)->prev = (add); \ + (add)->next = NULL; \ + } else { \ + (head)=(add); \ + (head)->prev = (head); \ + (head)->next = NULL; \ + } \ +} while (0) + +#define DL_INSERT_INORDER(head,add,cmp) \ + DL_INSERT_INORDER2(head,add,cmp,prev,next) + +#define DL_INSERT_INORDER2(head,add,cmp,prev,next) \ +do { \ + LDECLTYPE(head) _tmp; \ + if (head) { \ + DL_LOWER_BOUND2(head, _tmp, add, cmp, next); \ + DL_APPEND_ELEM2(head, _tmp, add, prev, next); \ + } else { \ + (head) = (add); \ + (head)->prev = (head); \ + (head)->next = NULL; \ + } \ +} while (0) + +#define DL_LOWER_BOUND(head,elt,like,cmp) \ + DL_LOWER_BOUND2(head,elt,like,cmp,next) + +#define DL_LOWER_BOUND2(head,elt,like,cmp,next) \ +do { \ + if ((head) == NULL || (cmp(head, like)) >= 0) { \ + (elt) = NULL; \ + } else { \ + for ((elt) = (head); (elt)->next != NULL; (elt) = (elt)->next) { \ + if ((cmp((elt)->next, like)) >= 0) { \ + break; \ + } \ + } \ + } \ +} while (0) + +#define DL_CONCAT(head1,head2) \ + DL_CONCAT2(head1,head2,prev,next) + +#define DL_CONCAT2(head1,head2,prev,next) \ +do { \ + LDECLTYPE(head1) _tmp; \ + if (head2) { \ + if (head1) { \ + UTLIST_CASTASGN(_tmp, (head2)->prev); \ + (head2)->prev = (head1)->prev; \ + (head1)->prev->next = (head2); \ + UTLIST_CASTASGN((head1)->prev, _tmp); \ + } else { \ + (head1)=(head2); \ + } \ + } \ +} while (0) + +#define DL_DELETE(head,del) \ + DL_DELETE2(head,del,prev,next) + +#define DL_DELETE2(head,del,prev,next) \ +do { \ + assert((head) != NULL); \ + assert((del)->prev != NULL); \ + if ((del)->prev == (del)) { \ + (head)=NULL; \ + } else if ((del)==(head)) { \ + (del)->next->prev = (del)->prev; \ + (head) = (del)->next; \ + } else { \ + (del)->prev->next = (del)->next; \ + if ((del)->next) { \ + (del)->next->prev = (del)->prev; \ + } else { \ + (head)->prev = (del)->prev; \ + } \ + } \ +} while (0) + +#define DL_COUNT(head,el,counter) \ + DL_COUNT2(head,el,counter,next) \ + +#define DL_COUNT2(head,el,counter,next) \ +do { \ + (counter) = 0; \ + DL_FOREACH2(head,el,next) { ++(counter); } \ +} while (0) + +#define DL_FOREACH(head,el) \ + DL_FOREACH2(head,el,next) + +#define DL_FOREACH2(head,el,next) \ + for ((el) = (head); el; (el) = (el)->next) + +/* this version is safe for deleting the elements during iteration */ +#define DL_FOREACH_SAFE(head,el,tmp) \ + DL_FOREACH_SAFE2(head,el,tmp,next) + +#define DL_FOREACH_SAFE2(head,el,tmp,next) \ + for ((el) = (head); (el) && ((tmp) = (el)->next, 1); (el) = (tmp)) + +/* these are identical to their singly-linked list counterparts */ +#define DL_SEARCH_SCALAR LL_SEARCH_SCALAR +#define DL_SEARCH LL_SEARCH +#define DL_SEARCH_SCALAR2 LL_SEARCH_SCALAR2 +#define DL_SEARCH2 LL_SEARCH2 + +#define DL_REPLACE_ELEM2(head, el, add, prev, next) \ +do { \ + assert((head) != NULL); \ + assert((el) != NULL); \ + assert((add) != NULL); \ + if ((head) == (el)) { \ + (head) = (add); \ + (add)->next = (el)->next; \ + if ((el)->next == NULL) { \ + (add)->prev = (add); \ + } else { \ + (add)->prev = (el)->prev; \ + (add)->next->prev = (add); \ + } \ + } else { \ + (add)->next = (el)->next; \ + (add)->prev = (el)->prev; \ + (add)->prev->next = (add); \ + if ((el)->next == NULL) { \ + (head)->prev = (add); \ + } else { \ + (add)->next->prev = (add); \ + } \ + } \ +} while (0) + +#define DL_REPLACE_ELEM(head, el, add) \ + DL_REPLACE_ELEM2(head, el, add, prev, next) + +#define DL_PREPEND_ELEM2(head, el, add, prev, next) \ +do { \ + if (el) { \ + assert((head) != NULL); \ + assert((add) != NULL); \ + (add)->next = (el); \ + (add)->prev = (el)->prev; \ + (el)->prev = (add); \ + if ((head) == (el)) { \ + (head) = (add); \ + } else { \ + (add)->prev->next = (add); \ + } \ + } else { \ + DL_APPEND2(head, add, prev, next); \ + } \ +} while (0) \ + +#define DL_PREPEND_ELEM(head, el, add) \ + DL_PREPEND_ELEM2(head, el, add, prev, next) + +#define DL_APPEND_ELEM2(head, el, add, prev, next) \ +do { \ + if (el) { \ + assert((head) != NULL); \ + assert((add) != NULL); \ + (add)->next = (el)->next; \ + (add)->prev = (el); \ + (el)->next = (add); \ + if ((add)->next) { \ + (add)->next->prev = (add); \ + } else { \ + (head)->prev = (add); \ + } \ + } else { \ + DL_PREPEND2(head, add, prev, next); \ + } \ +} while (0) \ + +#define DL_APPEND_ELEM(head, el, add) \ + DL_APPEND_ELEM2(head, el, add, prev, next) + +#ifdef NO_DECLTYPE +/* Here are VS2008 / NO_DECLTYPE replacements for a few functions */ + +#undef DL_INSERT_INORDER2 +#define DL_INSERT_INORDER2(head,add,cmp,prev,next) \ +do { \ + if ((head) == NULL) { \ + (add)->prev = (add); \ + (add)->next = NULL; \ + (head) = (add); \ + } else if ((cmp(head, add)) >= 0) { \ + (add)->prev = (head)->prev; \ + (add)->next = (head); \ + (head)->prev = (add); \ + (head) = (add); \ + } else { \ + char *_tmp = (char*)(head); \ + while ((head)->next && (cmp((head)->next, add)) < 0) { \ + (head) = (head)->next; \ + } \ + (add)->prev = (head); \ + (add)->next = (head)->next; \ + (head)->next = (add); \ + UTLIST_RS(head); \ + if ((add)->next) { \ + (add)->next->prev = (add); \ + } else { \ + (head)->prev = (add); \ + } \ + } \ +} while (0) +#endif /* NO_DECLTYPE */ + +/****************************************************************************** + * circular doubly linked list macros * + *****************************************************************************/ +#define CDL_APPEND(head,add) \ + CDL_APPEND2(head,add,prev,next) + +#define CDL_APPEND2(head,add,prev,next) \ +do { \ + if (head) { \ + (add)->prev = (head)->prev; \ + (add)->next = (head); \ + (head)->prev = (add); \ + (add)->prev->next = (add); \ + } else { \ + (add)->prev = (add); \ + (add)->next = (add); \ + (head) = (add); \ + } \ +} while (0) + +#define CDL_PREPEND(head,add) \ + CDL_PREPEND2(head,add,prev,next) + +#define CDL_PREPEND2(head,add,prev,next) \ +do { \ + if (head) { \ + (add)->prev = (head)->prev; \ + (add)->next = (head); \ + (head)->prev = (add); \ + (add)->prev->next = (add); \ + } else { \ + (add)->prev = (add); \ + (add)->next = (add); \ + } \ + (head) = (add); \ +} while (0) + +#define CDL_INSERT_INORDER(head,add,cmp) \ + CDL_INSERT_INORDER2(head,add,cmp,prev,next) + +#define CDL_INSERT_INORDER2(head,add,cmp,prev,next) \ +do { \ + LDECLTYPE(head) _tmp; \ + if (head) { \ + CDL_LOWER_BOUND2(head, _tmp, add, cmp, next); \ + CDL_APPEND_ELEM2(head, _tmp, add, prev, next); \ + } else { \ + (head) = (add); \ + (head)->next = (head); \ + (head)->prev = (head); \ + } \ +} while (0) + +#define CDL_LOWER_BOUND(head,elt,like,cmp) \ + CDL_LOWER_BOUND2(head,elt,like,cmp,next) + +#define CDL_LOWER_BOUND2(head,elt,like,cmp,next) \ +do { \ + if ((head) == NULL || (cmp(head, like)) >= 0) { \ + (elt) = NULL; \ + } else { \ + for ((elt) = (head); (elt)->next != (head); (elt) = (elt)->next) { \ + if ((cmp((elt)->next, like)) >= 0) { \ + break; \ + } \ + } \ + } \ +} while (0) + +#define CDL_DELETE(head,del) \ + CDL_DELETE2(head,del,prev,next) + +#define CDL_DELETE2(head,del,prev,next) \ +do { \ + if (((head)==(del)) && ((head)->next == (head))) { \ + (head) = NULL; \ + } else { \ + (del)->next->prev = (del)->prev; \ + (del)->prev->next = (del)->next; \ + if ((del) == (head)) (head)=(del)->next; \ + } \ +} while (0) + +#define CDL_COUNT(head,el,counter) \ + CDL_COUNT2(head,el,counter,next) \ + +#define CDL_COUNT2(head, el, counter,next) \ +do { \ + (counter) = 0; \ + CDL_FOREACH2(head,el,next) { ++(counter); } \ +} while (0) + +#define CDL_FOREACH(head,el) \ + CDL_FOREACH2(head,el,next) + +#define CDL_FOREACH2(head,el,next) \ + for ((el)=(head);el;(el)=(((el)->next==(head)) ? NULL : (el)->next)) + +#define CDL_FOREACH_SAFE(head,el,tmp1,tmp2) \ + CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next) + +#define CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next) \ + for ((el) = (head), (tmp1) = (head) ? (head)->prev : NULL; \ + (el) && ((tmp2) = (el)->next, 1); \ + (el) = ((el) == (tmp1) ? NULL : (tmp2))) + +#define CDL_SEARCH_SCALAR(head,out,field,val) \ + CDL_SEARCH_SCALAR2(head,out,field,val,next) + +#define CDL_SEARCH_SCALAR2(head,out,field,val,next) \ +do { \ + CDL_FOREACH2(head,out,next) { \ + if ((out)->field == (val)) break; \ + } \ +} while (0) + +#define CDL_SEARCH(head,out,elt,cmp) \ + CDL_SEARCH2(head,out,elt,cmp,next) + +#define CDL_SEARCH2(head,out,elt,cmp,next) \ +do { \ + CDL_FOREACH2(head,out,next) { \ + if ((cmp(out,elt))==0) break; \ + } \ +} while (0) + +#define CDL_REPLACE_ELEM2(head, el, add, prev, next) \ +do { \ + assert((head) != NULL); \ + assert((el) != NULL); \ + assert((add) != NULL); \ + if ((el)->next == (el)) { \ + (add)->next = (add); \ + (add)->prev = (add); \ + (head) = (add); \ + } else { \ + (add)->next = (el)->next; \ + (add)->prev = (el)->prev; \ + (add)->next->prev = (add); \ + (add)->prev->next = (add); \ + if ((head) == (el)) { \ + (head) = (add); \ + } \ + } \ +} while (0) + +#define CDL_REPLACE_ELEM(head, el, add) \ + CDL_REPLACE_ELEM2(head, el, add, prev, next) + +#define CDL_PREPEND_ELEM2(head, el, add, prev, next) \ +do { \ + if (el) { \ + assert((head) != NULL); \ + assert((add) != NULL); \ + (add)->next = (el); \ + (add)->prev = (el)->prev; \ + (el)->prev = (add); \ + (add)->prev->next = (add); \ + if ((head) == (el)) { \ + (head) = (add); \ + } \ + } else { \ + CDL_APPEND2(head, add, prev, next); \ + } \ +} while (0) + +#define CDL_PREPEND_ELEM(head, el, add) \ + CDL_PREPEND_ELEM2(head, el, add, prev, next) + +#define CDL_APPEND_ELEM2(head, el, add, prev, next) \ +do { \ + if (el) { \ + assert((head) != NULL); \ + assert((add) != NULL); \ + (add)->next = (el)->next; \ + (add)->prev = (el); \ + (el)->next = (add); \ + (add)->next->prev = (add); \ + } else { \ + CDL_PREPEND2(head, add, prev, next); \ + } \ +} while (0) + +#define CDL_APPEND_ELEM(head, el, add) \ + CDL_APPEND_ELEM2(head, el, add, prev, next) + +#ifdef NO_DECLTYPE +/* Here are VS2008 / NO_DECLTYPE replacements for a few functions */ + +#undef CDL_INSERT_INORDER2 +#define CDL_INSERT_INORDER2(head,add,cmp,prev,next) \ +do { \ + if ((head) == NULL) { \ + (add)->prev = (add); \ + (add)->next = (add); \ + (head) = (add); \ + } else if ((cmp(head, add)) >= 0) { \ + (add)->prev = (head)->prev; \ + (add)->next = (head); \ + (add)->prev->next = (add); \ + (head)->prev = (add); \ + (head) = (add); \ + } else { \ + char *_tmp = (char*)(head); \ + while ((char*)(head)->next != _tmp && (cmp((head)->next, add)) < 0) { \ + (head) = (head)->next; \ + } \ + (add)->prev = (head); \ + (add)->next = (head)->next; \ + (add)->next->prev = (add); \ + (head)->next = (add); \ + UTLIST_RS(head); \ + } \ +} while (0) +#endif /* NO_DECLTYPE */ + +#endif /* UTLIST_H */ diff --git a/test/uthash-2.3.0/include/utringbuffer.h b/test/uthash-2.3.0/include/utringbuffer.h new file mode 100644 index 0000000..cf48131 --- /dev/null +++ b/test/uthash-2.3.0/include/utringbuffer.h @@ -0,0 +1,108 @@ +/* +Copyright (c) 2015-2021, Troy D. Hanson http://troydhanson.github.com/uthash/ +All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS +IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED +TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A +PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER +OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, +EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, +PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR +PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF +LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING +NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS +SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +/* a ring-buffer implementation using macros + */ +#ifndef UTRINGBUFFER_H +#define UTRINGBUFFER_H + +#define UTRINGBUFFER_VERSION 2.3.0 + +#include <stdlib.h> +#include <string.h> +#include "utarray.h" // for "UT_icd" + +typedef struct { + unsigned i; /* index of next available slot; wraps at n */ + unsigned n; /* capacity */ + unsigned char f; /* full */ + UT_icd icd; /* initializer, copy and destructor functions */ + char *d; /* n slots of size icd->sz */ +} UT_ringbuffer; + +#define utringbuffer_init(a, _n, _icd) do { \ + memset(a, 0, sizeof(UT_ringbuffer)); \ + (a)->icd = *(_icd); \ + (a)->n = (_n); \ + if ((a)->n) { (a)->d = (char*)malloc((a)->n * (_icd)->sz); } \ +} while(0) + +#define utringbuffer_clear(a) do { \ + if ((a)->icd.dtor) { \ + if ((a)->f) { \ + unsigned _ut_i; \ + for (_ut_i = 0; _ut_i < (a)->n; ++_ut_i) { \ + (a)->icd.dtor(utringbuffer_eltptr(a, _ut_i)); \ + } \ + } else { \ + unsigned _ut_i; \ + for (_ut_i = 0; _ut_i < (a)->i; ++_ut_i) { \ + (a)->icd.dtor(utringbuffer_eltptr(a, _ut_i)); \ + } \ + } \ + } \ + (a)->i = 0; \ + (a)->f = 0; \ +} while(0) + +#define utringbuffer_done(a) do { \ + utringbuffer_clear(a); \ + free((a)->d); (a)->d = NULL; \ + (a)->n = 0; \ +} while(0) + +#define utringbuffer_new(a,n,_icd) do { \ + a = (UT_ringbuffer*)malloc(sizeof(UT_ringbuffer)); \ + utringbuffer_init(a, n, _icd); \ +} while(0) + +#define utringbuffer_free(a) do { \ + utringbuffer_done(a); \ + free(a); \ +} while(0) + +#define utringbuffer_push_back(a,p) do { \ + if ((a)->icd.dtor && (a)->f) { (a)->icd.dtor(_utringbuffer_internalptr(a,(a)->i)); } \ + if ((a)->icd.copy) { (a)->icd.copy( _utringbuffer_internalptr(a,(a)->i), p); } \ + else { memcpy(_utringbuffer_internalptr(a,(a)->i), p, (a)->icd.sz); }; \ + if (++(a)->i == (a)->n) { (a)->i = 0; (a)->f = 1; } \ +} while(0) + +#define utringbuffer_len(a) ((a)->f ? (a)->n : (a)->i) +#define utringbuffer_empty(a) ((a)->i == 0 && !(a)->f) +#define utringbuffer_full(a) ((a)->f != 0) + +#define _utringbuffer_real_idx(a,j) ((a)->f ? ((j) + (a)->i) % (a)->n : (j)) +#define _utringbuffer_internalptr(a,j) ((void*)((a)->d + ((a)->icd.sz * (j)))) +#define utringbuffer_eltptr(a,j) ((0 <= (j) && (j) < utringbuffer_len(a)) ? _utringbuffer_internalptr(a,_utringbuffer_real_idx(a,j)) : NULL) + +#define _utringbuffer_fake_idx(a,j) ((a)->f ? ((j) + (a)->n - (a)->i) % (a)->n : (j)) +#define _utringbuffer_internalidx(a,e) (((char*)(e) >= (a)->d) ? (((char*)(e) - (a)->d)/(a)->icd.sz) : -1) +#define utringbuffer_eltidx(a,e) _utringbuffer_fake_idx(a, _utringbuffer_internalidx(a,e)) + +#define utringbuffer_front(a) utringbuffer_eltptr(a,0) +#define utringbuffer_next(a,e) ((e)==NULL ? utringbuffer_front(a) : utringbuffer_eltptr(a, utringbuffer_eltidx(a,e)+1)) +#define utringbuffer_prev(a,e) ((e)==NULL ? utringbuffer_back(a) : utringbuffer_eltptr(a, utringbuffer_eltidx(a,e)-1)) +#define utringbuffer_back(a) (utringbuffer_empty(a) ? NULL : utringbuffer_eltptr(a, utringbuffer_len(a) - 1)) + +#endif /* UTRINGBUFFER_H */ diff --git a/test/uthash-2.3.0/include/utstack.h b/test/uthash-2.3.0/include/utstack.h new file mode 100644 index 0000000..2dbfec8 --- /dev/null +++ b/test/uthash-2.3.0/include/utstack.h @@ -0,0 +1,88 @@ +/* +Copyright (c) 2018-2021, Troy D. Hanson http://troydhanson.github.com/uthash/ +All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS +IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED +TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A +PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER +OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, +EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, +PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR +PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF +LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING +NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS +SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +#ifndef UTSTACK_H +#define UTSTACK_H + +#define UTSTACK_VERSION 2.3.0 + +/* + * This file contains macros to manipulate a singly-linked list as a stack. + * + * To use utstack, your structure must have a "next" pointer. + * + * ----------------.EXAMPLE ------------------------- + * struct item { + * int id; + * struct item *next; + * } + * + * struct item *stack = NULL: + * + * int main() { + * int count; + * struct item *tmp; + * struct item *item = malloc(sizeof *item); + * item->id = 42; + * STACK_COUNT(stack, tmp, count); assert(count == 0); + * STACK_PUSH(stack, item); + * STACK_COUNT(stack, tmp, count); assert(count == 1); + * STACK_POP(stack, item); + * free(item); + * STACK_COUNT(stack, tmp, count); assert(count == 0); + * } + * -------------------------------------------------- + */ + +#define STACK_TOP(head) (head) + +#define STACK_EMPTY(head) (!(head)) + +#define STACK_PUSH(head,add) \ + STACK_PUSH2(head,add,next) + +#define STACK_PUSH2(head,add,next) \ +do { \ + (add)->next = (head); \ + (head) = (add); \ +} while (0) + +#define STACK_POP(head,result) \ + STACK_POP2(head,result,next) + +#define STACK_POP2(head,result,next) \ +do { \ + (result) = (head); \ + (head) = (head)->next; \ +} while (0) + +#define STACK_COUNT(head,el,counter) \ + STACK_COUNT2(head,el,counter,next) \ + +#define STACK_COUNT2(head,el,counter,next) \ +do { \ + (counter) = 0; \ + for ((el) = (head); el; (el) = (el)->next) { ++(counter); } \ +} while (0) + +#endif /* UTSTACK_H */ diff --git a/test/uthash-2.3.0/include/utstring.h b/test/uthash-2.3.0/include/utstring.h new file mode 100644 index 0000000..009b4c8 --- /dev/null +++ b/test/uthash-2.3.0/include/utstring.h @@ -0,0 +1,407 @@ +/* +Copyright (c) 2008-2021, Troy D. Hanson http://troydhanson.github.com/uthash/ +All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS +IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED +TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A +PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER +OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, +EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, +PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR +PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF +LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING +NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS +SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +/* a dynamic string implementation using macros + */ +#ifndef UTSTRING_H +#define UTSTRING_H + +#define UTSTRING_VERSION 2.3.0 + +#include <stdlib.h> +#include <string.h> +#include <stdio.h> +#include <stdarg.h> + +#ifdef __GNUC__ +#define UTSTRING_UNUSED __attribute__((__unused__)) +#else +#define UTSTRING_UNUSED +#endif + +#ifdef oom +#error "The name of macro 'oom' has been changed to 'utstring_oom'. Please update your code." +#define utstring_oom() oom() +#endif + +#ifndef utstring_oom +#define utstring_oom() exit(-1) +#endif + +typedef struct { + char *d; /* pointer to allocated buffer */ + size_t n; /* allocated capacity */ + size_t i; /* index of first unused byte */ +} UT_string; + +#define utstring_reserve(s,amt) \ +do { \ + if (((s)->n - (s)->i) < (size_t)(amt)) { \ + char *utstring_tmp = (char*)realloc( \ + (s)->d, (s)->n + (amt)); \ + if (!utstring_tmp) { \ + utstring_oom(); \ + } \ + (s)->d = utstring_tmp; \ + (s)->n += (amt); \ + } \ +} while(0) + +#define utstring_init(s) \ +do { \ + (s)->n = 0; (s)->i = 0; (s)->d = NULL; \ + utstring_reserve(s,100); \ + (s)->d[0] = '\0'; \ +} while(0) + +#define utstring_done(s) \ +do { \ + if ((s)->d != NULL) free((s)->d); \ + (s)->n = 0; \ +} while(0) + +#define utstring_free(s) \ +do { \ + utstring_done(s); \ + free(s); \ +} while(0) + +#define utstring_new(s) \ +do { \ + (s) = (UT_string*)malloc(sizeof(UT_string)); \ + if (!(s)) { \ + utstring_oom(); \ + } \ + utstring_init(s); \ +} while(0) + +#define utstring_renew(s) \ +do { \ + if (s) { \ + utstring_clear(s); \ + } else { \ + utstring_new(s); \ + } \ +} while(0) + +#define utstring_clear(s) \ +do { \ + (s)->i = 0; \ + (s)->d[0] = '\0'; \ +} while(0) + +#define utstring_bincpy(s,b,l) \ +do { \ + utstring_reserve((s),(l)+1); \ + if (l) memcpy(&(s)->d[(s)->i], b, l); \ + (s)->i += (l); \ + (s)->d[(s)->i]='\0'; \ +} while(0) + +#define utstring_concat(dst,src) \ +do { \ + utstring_reserve((dst),((src)->i)+1); \ + if ((src)->i) memcpy(&(dst)->d[(dst)->i], (src)->d, (src)->i); \ + (dst)->i += (src)->i; \ + (dst)->d[(dst)->i]='\0'; \ +} while(0) + +#define utstring_len(s) ((s)->i) + +#define utstring_body(s) ((s)->d) + +UTSTRING_UNUSED static void utstring_printf_va(UT_string *s, const char *fmt, va_list ap) { + int n; + va_list cp; + for (;;) { +#ifdef _WIN32 + cp = ap; +#else + va_copy(cp, ap); +#endif + n = vsnprintf (&s->d[s->i], s->n-s->i, fmt, cp); + va_end(cp); + + if ((n > -1) && ((size_t) n < (s->n-s->i))) { + s->i += n; + return; + } + + /* Else try again with more space. */ + if (n > -1) utstring_reserve(s,n+1); /* exact */ + else utstring_reserve(s,(s->n)*2); /* 2x */ + } +} +#ifdef __GNUC__ +/* support printf format checking (2=the format string, 3=start of varargs) */ +static void utstring_printf(UT_string *s, const char *fmt, ...) + __attribute__ (( format( printf, 2, 3) )); +#endif +UTSTRING_UNUSED static void utstring_printf(UT_string *s, const char *fmt, ...) { + va_list ap; + va_start(ap,fmt); + utstring_printf_va(s,fmt,ap); + va_end(ap); +} + +/******************************************************************************* + * begin substring search functions * + ******************************************************************************/ +/* Build KMP table from left to right. */ +UTSTRING_UNUSED static void _utstring_BuildTable( + const char *P_Needle, + size_t P_NeedleLen, + long *P_KMP_Table) +{ + long i, j; + + i = 0; + j = i - 1; + P_KMP_Table[i] = j; + while (i < (long) P_NeedleLen) + { + while ( (j > -1) && (P_Needle[i] != P_Needle[j]) ) + { + j = P_KMP_Table[j]; + } + i++; + j++; + if (i < (long) P_NeedleLen) + { + if (P_Needle[i] == P_Needle[j]) + { + P_KMP_Table[i] = P_KMP_Table[j]; + } + else + { + P_KMP_Table[i] = j; + } + } + else + { + P_KMP_Table[i] = j; + } + } + + return; +} + + +/* Build KMP table from right to left. */ +UTSTRING_UNUSED static void _utstring_BuildTableR( + const char *P_Needle, + size_t P_NeedleLen, + long *P_KMP_Table) +{ + long i, j; + + i = P_NeedleLen - 1; + j = i + 1; + P_KMP_Table[i + 1] = j; + while (i >= 0) + { + while ( (j < (long) P_NeedleLen) && (P_Needle[i] != P_Needle[j]) ) + { + j = P_KMP_Table[j + 1]; + } + i--; + j--; + if (i >= 0) + { + if (P_Needle[i] == P_Needle[j]) + { + P_KMP_Table[i + 1] = P_KMP_Table[j + 1]; + } + else + { + P_KMP_Table[i + 1] = j; + } + } + else + { + P_KMP_Table[i + 1] = j; + } + } + + return; +} + + +/* Search data from left to right. ( Multiple search mode. ) */ +UTSTRING_UNUSED static long _utstring_find( + const char *P_Haystack, + size_t P_HaystackLen, + const char *P_Needle, + size_t P_NeedleLen, + long *P_KMP_Table) +{ + long i, j; + long V_FindPosition = -1; + + /* Search from left to right. */ + i = j = 0; + while ( (j < (int)P_HaystackLen) && (((P_HaystackLen - j) + i) >= P_NeedleLen) ) + { + while ( (i > -1) && (P_Needle[i] != P_Haystack[j]) ) + { + i = P_KMP_Table[i]; + } + i++; + j++; + if (i >= (int)P_NeedleLen) + { + /* Found. */ + V_FindPosition = j - i; + break; + } + } + + return V_FindPosition; +} + + +/* Search data from right to left. ( Multiple search mode. ) */ +UTSTRING_UNUSED static long _utstring_findR( + const char *P_Haystack, + size_t P_HaystackLen, + const char *P_Needle, + size_t P_NeedleLen, + long *P_KMP_Table) +{ + long i, j; + long V_FindPosition = -1; + + /* Search from right to left. */ + j = (P_HaystackLen - 1); + i = (P_NeedleLen - 1); + while ( (j >= 0) && (j >= i) ) + { + while ( (i < (int)P_NeedleLen) && (P_Needle[i] != P_Haystack[j]) ) + { + i = P_KMP_Table[i + 1]; + } + i--; + j--; + if (i < 0) + { + /* Found. */ + V_FindPosition = j + 1; + break; + } + } + + return V_FindPosition; +} + + +/* Search data from left to right. ( One time search mode. ) */ +UTSTRING_UNUSED static long utstring_find( + UT_string *s, + long P_StartPosition, /* Start from 0. -1 means last position. */ + const char *P_Needle, + size_t P_NeedleLen) +{ + long V_StartPosition; + long V_HaystackLen; + long *V_KMP_Table; + long V_FindPosition = -1; + + if (P_StartPosition < 0) + { + V_StartPosition = s->i + P_StartPosition; + } + else + { + V_StartPosition = P_StartPosition; + } + V_HaystackLen = s->i - V_StartPosition; + if ( (V_HaystackLen >= (long) P_NeedleLen) && (P_NeedleLen > 0) ) + { + V_KMP_Table = (long *)malloc(sizeof(long) * (P_NeedleLen + 1)); + if (V_KMP_Table != NULL) + { + _utstring_BuildTable(P_Needle, P_NeedleLen, V_KMP_Table); + + V_FindPosition = _utstring_find(s->d + V_StartPosition, + V_HaystackLen, + P_Needle, + P_NeedleLen, + V_KMP_Table); + if (V_FindPosition >= 0) + { + V_FindPosition += V_StartPosition; + } + + free(V_KMP_Table); + } + } + + return V_FindPosition; +} + + +/* Search data from right to left. ( One time search mode. ) */ +UTSTRING_UNUSED static long utstring_findR( + UT_string *s, + long P_StartPosition, /* Start from 0. -1 means last position. */ + const char *P_Needle, + size_t P_NeedleLen) +{ + long V_StartPosition; + long V_HaystackLen; + long *V_KMP_Table; + long V_FindPosition = -1; + + if (P_StartPosition < 0) + { + V_StartPosition = s->i + P_StartPosition; + } + else + { + V_StartPosition = P_StartPosition; + } + V_HaystackLen = V_StartPosition + 1; + if ( (V_HaystackLen >= (long) P_NeedleLen) && (P_NeedleLen > 0) ) + { + V_KMP_Table = (long *)malloc(sizeof(long) * (P_NeedleLen + 1)); + if (V_KMP_Table != NULL) + { + _utstring_BuildTableR(P_Needle, P_NeedleLen, V_KMP_Table); + + V_FindPosition = _utstring_findR(s->d, + V_HaystackLen, + P_Needle, + P_NeedleLen, + V_KMP_Table); + + free(V_KMP_Table); + } + } + + return V_FindPosition; +} +/******************************************************************************* + * end substring search functions * + ******************************************************************************/ + +#endif /* UTSTRING_H */ |