#include <gtest/gtest.h>

#include <limits.h>

#include <taosdef.h>

#include <iostream>

#include "os.h"

#include "taosmsg.h"

#include "tskiplist.h"

#include "tutil.h"

namespace {

char* getkey(const void* data) { return (char*)(data); }

void doubleSkipListTest() {

SSkipList* pSkipList = tSkipListCreate(10, TSDB_DATA_TYPE_DOUBLE, sizeof(double), 0, false, true, getkey);

double doubleVal[1000] = {0};

int32_t size = 20000;

printf("generated %d keys is: \n", size);

for (int32_t i = 0; i < size; ++i) {

if (i < 1000) {

doubleVal[i] = i * 0.997;

}

int32_t level = 0;

int32_t size = 0;

tSkipListNewNodeInfo(pSkipList, &level, &size);

auto d = (SSkipListNode*)calloc(1, size + sizeof(double) * 2);

d->level = level;

double* key = (double*)SL_GET_NODE_KEY(pSkipList, d);

key[0] = i * 0.997;

key[1] = i * 0.997;

tSkipListPut(pSkipList, d);

}

printf("the first level of skip list is:\n");

tSkipListPrint(pSkipList, 1);

#if 0

SSkipListNode **pNodes = NULL;

SSkipListKey sk;

for (int32_t i = 0; i < 100; ++i) {

sk.nType = TSDB_DATA_TYPE_DOUBLE;

int32_t idx = abs((i * rand()) % 1000);

sk.dKey = doubleVal[idx];

int32_t size = tSkipListGets(pSkipList, &sk, &pNodes);

printf("the query result size is: %d\n", size);

for (int32_t j = 0; j < size; ++j) {

printf("the result is: %lf\n", pNodes[j]->key.dKey);

}

if (size > 0) {

taosTFree(pNodes);

}

}

#endif

printf("double test end...\n");

tSkipListDestroy(pSkipList);

}

void randKeyTest() {

SSkipList* pSkipList = tSkipListCreate(10, TSDB_DATA_TYPE_INT, sizeof(int32_t), 0, false, true, getkey);

int32_t size = 200000;

srand(time(NULL));

printf("generated %d keys is: \n", size);

for (int32_t i = 0; i < size; ++i) {

int32_t level = 0;

int32_t s = 0;

tSkipListNewNodeInfo(pSkipList, &level, &s);

auto d = (SSkipListNode*)calloc(1, s + sizeof(int32_t) * 2);

d->level = level;

int32_t* key = (int32_t*)SL_GET_NODE_KEY(pSkipList, d);

key[0] = rand() % 1000000000;

key[1] = key[0];

tSkipListPut(pSkipList, d);

}

printf("the first level of skip list is:\n");

tSkipListPrint(pSkipList, 1);

printf("the sec level of skip list is:\n");

tSkipListPrint(pSkipList, 2);

printf("the 5 level of skip list is:\n");

tSkipListPrint(pSkipList, 5);

tSkipListDestroy(pSkipList);

}

void stringKeySkiplistTest() {

const int32_t max_key_size = 12;

SSkipList* pSkipList = tSkipListCreate(10, TSDB_DATA_TYPE_BINARY, max_key_size, 0, false, true, getkey);

int32_t level = 0;

int32_t headsize = 0;

tSkipListNewNodeInfo(pSkipList, &level, &headsize);

auto pNode = (SSkipListNode*)calloc(1, headsize + max_key_size + sizeof(double));

pNode->level = level;

char* d = SL_GET_NODE_DATA(pNode);

strncpy(d, "nyse", 5);

*(double*)(d + max_key_size) = 12;

tSkipListPut(pSkipList, pNode);

tSkipListNewNodeInfo(pSkipList, &level, &headsize);

pNode = (SSkipListNode*)calloc(1, headsize + max_key_size + sizeof(double));

pNode->level = level;

d = SL_GET_NODE_DATA(pNode);

strncpy(d, "beijing", 8);

*(double*)(d + max_key_size) = 911;

tSkipListPut(pSkipList, pNode);

printf("level one------------------\n");

tSkipListPrint(pSkipList, 1);

#if 0

SSkipListNode **pRes = NULL;

int32_t ret = tSkipListGets(pSkipList, &key1, &pRes);

assert(ret == 1);

assert(strcmp(pRes[0]->key.pz, "beijing") == 0);

assert(pRes[0]->key.nType == TSDB_DATA_TYPE_BINARY);

tSkipListDestroyKey(&key1);

tSkipListDestroyKey(&key);

tSkipListDestroy(pSkipList);

free(pRes);

#endif

tSkipListDestroy(pSkipList);

int64_t s = taosGetTimestampUs();

pSkipList = tSkipListCreate(10, TSDB_DATA_TYPE_BINARY, 20, 0, false, true, getkey);

char k[256] = {0};

int32_t total = 10000;

for (int32_t i = 0; i < total; ++i) {

int32_t n = sprintf(k, "abc_%d_%d", i, i);

tSkipListNewNodeInfo(pSkipList, &level, &headsize);

auto pNode = (SSkipListNode*)calloc(1, headsize + 20 + sizeof(double));

pNode->level = level;

char* d = SL_GET_NODE_DATA(pNode);

strncpy(d, k, strlen(k));

tSkipListPut(pSkipList, pNode);

}

int64_t e = taosGetTimestampUs();

printf("elapsed time:%" PRIu64 " us to insert %d data, avg:%f us\n", (e - s), total, (double)(e - s) / total);

printf("level two------------------\n");

tSkipListPrint(pSkipList, 1);

#if 0

SSkipListNode **pres = NULL;

s = taosGetTimestampMs();

for (int32_t j = 0; j < total; ++j) {

int32_t n = sprintf(k, "abc_%d_%d", j, j);

key = tSkipListCreateKey(TSDB_DATA_TYPE_BINARY, k, n);

int32_t num = tSkipListGets(pSkipList, &key, &pres);

assert(num > 0);

// tSkipListRemove(pSkipList, &key);

tSkipListRemoveNode(pSkipList, pres[0]);

if (num > 0) {

taosTFree(pres);

}

}

e = taosGetTimestampMs();

printf("elapsed time:%lldms\n", e - s);

#endif

tSkipListDestroy(pSkipList);

}

void skiplistPerformanceTest() {

SSkipList* pSkipList = tSkipListCreate(10, TSDB_DATA_TYPE_DOUBLE, sizeof(double), 0, false, false, getkey);

int32_t size = 1000000;

int64_t prev = taosGetTimestampMs();

int64_t s = prev;

int32_t level = 0;

int32_t headsize = 0;

int32_t unit = MAX_SKIP_LIST_LEVEL * POINTER_BYTES * 2 + sizeof(double) * 2 + sizeof(int16_t);

char* total = (char*)calloc(1, unit * size);

char* p = total;

for (int32_t i = 0; i < size; ++i) {

tSkipListNewNodeInfo(pSkipList, &level, &headsize);

SSkipListNode* d = (SSkipListNode*)p;

p += headsize + sizeof(double) * 2;

d->level = level;

double* v = (double*)SL_GET_NODE_DATA(d);

v[0] = i * 0.997;

v[1] = i * 0.997;

tSkipListPut(pSkipList, d);

if (i % 100000 == 0) {

int64_t cur = taosGetTimestampMs();

int64_t elapsed = cur - prev;

printf("add %d, elapsed time: %" PRIu64 " ms, avg elapsed:%f ms, total:%d\n", 100000, elapsed, elapsed / 100000.0, i);

prev = cur;

}

}

int64_t e = taosGetTimestampMs();

printf("total:%" PRIu64 " ms, avg:%f\n", e - s, (e - s) / (double)size);

printf("max level of skiplist:%d, actually level:%d\n ", pSkipList->maxLevel, pSkipList->level);

assert(tSkipListGetSize(pSkipList) == size);

// printf("the level of skiplist is:\n");

//

// printf("level two------------------\n");

// tSkipListPrint(pSkipList, 2);

//

// printf("level three------------------\n");

// tSkipListPrint(pSkipList, 3);

//

// printf("level four------------------\n");

// tSkipListPrint(pSkipList, 4);

//

// printf("level nine------------------\n");

// tSkipListPrint(pSkipList, 10);

int64_t st = taosGetTimestampMs();

#if 0

for (int32_t i = 0; i < 100000; i += 1) {

key.dKey = i * 0.997;

tSkipListRemove(pSkipList, &key);

}

#endif

int64_t et = taosGetTimestampMs();

printf("delete %d data from skiplist, elapased time:%" PRIu64 "ms\n", 10000, et - st);

assert(tSkipListGetSize(pSkipList) == size);

tSkipListDestroy(pSkipList);

taosTFree(total);

}

// todo not support duplicated key yet

void duplicatedKeyTest() {

SSkipList *pSkipList = tSkipListCreate(MAX_SKIP_LIST_LEVEL, TSDB_DATA_TYPE_INT, sizeof(int), true, false, true, getkey);

for (int32_t i = 0; i < 200; ++i) {

for (int32_t j = 0; j < 5; ++j) {

int32_t level, size;

tSkipListNewNodeInfo(pSkipList, &level, &size);

SSkipListNode* d = (SSkipListNode*)calloc(1, size + sizeof(int32_t));

d->level = level;

int32_t* key = (int32_t*)SL_GET_NODE_KEY(pSkipList, d);

key[0] = i;

tSkipListPut(pSkipList, d);

}

}

for (int32_t i = 0; i < 100; ++i) {

SSkipListKey key;

SArray* nodes = tSkipListGet(pSkipList, (char*)(&i));

assert( taosArrayGetSize(nodes) == 5 );

taosArrayDestroy(nodes);

}

int32_t key = 101;

uint32_t num = tSkipListRemove(pSkipList, (char*)(&key));

assert(num == 5);

SArray* nodes = tSkipListGet(pSkipList, (char*)(&key));

assert( taosArrayGetSize(nodes) == 0 );

taosArrayDestroy(nodes);

key = 102;

SSkipListIterator* iter = tSkipListCreateIterFromVal(pSkipList, (char*)(&key), TSDB_DATA_TYPE_INT, TSDB_ORDER_ASC);

for(int i = 0; i < 6; i++) {

assert(tSkipListIterNext(iter) == true);

SSkipListNode* node = tSkipListIterGet(iter);

int32_t* val = (int32_t*)SL_GET_NODE_KEY(pSkipList, node);

assert((i < 5) == ((*val) == key));

}

tSkipListDestroyIter(iter);

iter = tSkipListCreateIterFromVal(pSkipList, (char*)(&key), TSDB_DATA_TYPE_INT, TSDB_ORDER_DESC);

for(int i = 0; i < 6; i++) {

assert(tSkipListIterNext(iter) == true);

SSkipListNode* node = tSkipListIterGet(iter);

int32_t* val = (int32_t*)SL_GET_NODE_KEY(pSkipList, node);

assert((i < 5) == ((*val) == key));

}

tSkipListDestroyIter(iter);

tSkipListDestroy(pSkipList);

}

} // namespace

TEST(testCase, skiplist_test) {

assert(sizeof(SSkipListKey) == 8);

srand(time(NULL));

stringKeySkiplistTest();

doubleSkipListTest();

skiplistPerformanceTest();

duplicatedKeyTest();

randKeyTest();

// tSKipListQueryCond q;

// q.upperBndRelOptr = true;

// q.lowerBndRelOptr = true;

// q.upperBnd.nType = TSDB_DATA_TYPE_DOUBLE;

// q.lowerBnd.nType = TSDB_DATA_TYPE_DOUBLE;

// q.lowerBnd.dKey = 120;

// q.upperBnd.dKey = 171.989;

/*

int32_t size = tSkipListQuery(pSkipList, &q, &pNodes);

for (int32_t i = 0; i < size; ++i) {

printf("-----%lf\n", pNodes[i]->key.dKey);

}

printf("the range query result size is: %d\n", size);

taosTFree(pNodes);

SSkipListKey *pKeys = malloc(sizeof(SSkipListKey) * 20);

for (int32_t i = 0; i < 8; i += 2) {

pKeys[i].dKey = i * 0.997;

pKeys[i].nType = TSDB_DATA_TYPE_DOUBLE;

printf("%lf ", pKeys[i].dKey);

}

int32_t r = tSkipListPointQuery(pSkipList, pKeys, 8, EXCLUDE_POINT_QUERY, &pNodes);

printf("\nthe exclude query result is: %d\n", r);

for (int32_t i = 0; i < r; ++i) {

// printf("%lf ", pNodes[i]->key.dKey);

}

taosTFree(pNodes);

free(pKeys);*/

}