1 Star 0 Fork 0

Mouri_Naruto / nedtries

加入 Gitee
与超过 600 万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
该仓库未指定开源许可证,未经作者的许可,此代码仅用于学习,不能用于其他用途。
克隆/下载
test.c 5.48 KB
一键复制 编辑 Web IDE 原始数据 按行查看 历史
#include <stdio.h>
#include <string.h>
/*#define NEDTRIEUSEMACROS 1*/
#include "nedtrie.h"
#define RANDOM_NFIND_TEST_KEYMASK 63
#define RANDOM_NFIND_TEST_ITEMS ((RANDOM_NFIND_TEST_KEYMASK+1)/3)
#define ITERATIONS (1<<16)
/* Include the Mersenne twister */
#if !defined(__cplusplus_cli) && (defined(_M_X64) || defined(__x86_64__) || (defined(_M_IX86) && _M_IX86_FP>=2) || (defined(__i386__) && defined(__SSE2__)))
#define HAVE_SSE2 1
#endif
#define MEXP 19937
#include "SFMT.c"
typedef struct foo_s foo_t;
struct foo_s {
NEDTRIE_ENTRY(foo_s) link;
size_t key;
};
typedef struct foo_tree_s foo_tree_t;
NEDTRIE_HEAD(foo_tree_s, foo_s);
static foo_tree_t footree;
size_t fookeyfunct(const foo_t *r)
{
return r->key;
}
NEDTRIE_GENERATE(static, foo_tree_s, foo_s, link, fookeyfunct, NEDTRIE_NOBBLEZEROS(foo_tree_s))
#if defined(__cplusplus) && NEDTRIE_ENABLE_STL_CONTAINERS
struct keyfunct : public std::unary_function<int, size_t>
{
size_t operator()(const int &) const
{
return 5;
}
};
#endif
int main(void)
{
foo_t a, b, c, *r;
printf("General workout of the C API ...\n");
NEDTRIE_INIT(&footree);
a.key=2;
NEDTRIE_INSERT(foo_tree_s, &footree, &a);
b.key=6;
NEDTRIE_INSERT(foo_tree_s, &footree, &b);
r=NEDTRIE_FIND(foo_tree_s, &footree, &b);
assert(r==&b);
c.key=5;
r=NEDTRIE_NFIND(foo_tree_s, &footree, &c);
assert(r==&b); /* NFIND finds next largest. Invert the key function (i.e. 1-key) to find next smallest. */
NEDTRIE_REMOVE(foo_tree_s, &footree, &a);
NEDTRIE_FOREACH(r, foo_tree_s, &footree)
{
printf("%p, %u\n", (void *) r, (unsigned) r->key);
}
assert(!NEDTRIE_PREV(foo_tree_s, &footree, &b));
assert(!NEDTRIE_NEXT(foo_tree_s, &footree, &b));
#if defined(__cplusplus) && NEDTRIE_ENABLE_STL_CONTAINERS
printf("General workout of the C++ API ...\n");
assert(keyfunct()(78)==5);
using namespace nedtries;
trie_map<size_t, size_t, keyfunct> map;
trie_multimap<size_t, size_t, keyfunct> multimap;
map.insert(78);
multimap.insert(78);
map.insert(79); // Replaces 78 with 79
multimap.insert(79); // Pushes the existing 78 backwards so 79 is now in front, so it's LIFO
assert(map.size()==1);
assert(multimap.size()==2);
assert(79==*map.find(5));
trie_multimap<size_t, size_t, keyfunct>::const_iterator it=multimap.find(5);
assert(79==*it);
--it; // NEDTRIE_PREV
assert(78==*it);
#endif
/* From https://github.com/ned14/nedtries/issues/5 */
printf("Testing bug from https://github.com/ned14/nedtries/issues/5 (Nfind does not work in all cases) ...\n");
NEDTRIE_INIT(&footree);
a.key=0x10; /* 16 = 10000 */
NEDTRIE_INSERT(foo_tree_s, &footree, &a);
b.key=0x18; /* 24 = 11000 */
NEDTRIE_INSERT(foo_tree_s, &footree, &b);
c.key=0x11; /* 17 = 10001 */
r=NEDTRIE_NFIND(foo_tree_s, &footree, &c);
assert(r==&b); /* This was failing under the bug */
NEDTRIE_INIT(&footree);
a.key=52; /* 110100 */
NEDTRIE_INSERT(foo_tree_s, &footree, &a);
b.key=40; /* 101000 */
NEDTRIE_INSERT(foo_tree_s, &footree, &b);
c.key=25; /* 011001 */
r=NEDTRIE_NFIND(foo_tree_s, &footree, &c);
assert(r==&b); /* This was failing under the bug */
/* To make sure the above never happens again */
init_gen_rand(1234);
{
int n, m, promoted=0;
foo_t items[RANDOM_NFIND_TEST_ITEMS];
const foo_t *items_sorted[RANDOM_NFIND_TEST_ITEMS];
foo_t *r2;
for(n=0; n<ITERATIONS; n++)
{
const foo_t *max, *min;
int sorted;
NEDTRIE_INIT(&footree);
for(m=0; m<RANDOM_NFIND_TEST_ITEMS; m++)
{
int o;
do
{
items[m].key=gen_rand32() & RANDOM_NFIND_TEST_KEYMASK;
for(o=0; o<m && items[o].key!=items[m].key; o++);
} while(o<m);
items_sorted[m]=&items[m];
NEDTRIE_INSERT(foo_tree_s, &footree, &items[m]);
}
m=0;
NEDTRIE_FOREACH(r2, foo_tree_s, &footree)
{
m++;
}
assert(m==RANDOM_NFIND_TEST_ITEMS);
m=0;
NEDTRIE_FOREACH_REVERSE(r2, foo_tree_s, &footree)
{
m++;
}
assert(m==RANDOM_NFIND_TEST_ITEMS);
do
{
sorted=1;
for(m=0; m<RANDOM_NFIND_TEST_ITEMS-1; m++)
{
if(items_sorted[m+1]->key<items_sorted[m]->key)
{
const foo_t *temp;
sorted=0;
temp=items_sorted[m];
items_sorted[m]=items_sorted[m+1];
items_sorted[m+1]=temp;
}
}
} while(!sorted);
min=items_sorted[0];
max=items_sorted[RANDOM_NFIND_TEST_ITEMS-1];
c.key=gen_rand32() & RANDOM_NFIND_TEST_KEYMASK;
r2=NEDTRIE_CFIND(foo_tree_s, &footree, &c, INT_MAX);
r=NEDTRIE_NFIND(foo_tree_s, &footree, &c);
promoted+=(r!=r2);
if(c.key>max->key)
{ /* If search key is bigger than max key, it must always return zero */
assert(r==0);
}
else
{
assert(r!=0);
if(c.key!=r->key)
{ /* If search key is smaller than min key, it must always return min */
if(c.key<min->key)
{
assert(r==min);
}
else
{ /* Assert it correctly clamped to nearest */
for(m=0; m<RANDOM_NFIND_TEST_ITEMS && items_sorted[m]->key<c.key; m++);
assert(m!=RANDOM_NFIND_TEST_ITEMS);
assert(r==items_sorted[m]);
}
}
}
}
printf("Nfind returned a different item to Cfind %d of %d (%f%%) iterations\n", promoted, ITERATIONS, 100.0*promoted/ITERATIONS);
#if 0
printf("\nPress Return to exit ...\n");
getchar();
#endif
}
return 0;
}

评论 ( 0 )

你可以在登录后,发表评论

1
https://gitee.com/Mouri_Naruto/nedtries.git
git@gitee.com:Mouri_Naruto/nedtries.git
Mouri_Naruto
nedtries
nedtries
master

搜索帮助