1
0

bintree.c 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438
  1. #include <string.h>
  2. #include <stdio.h>
  3. #include "bintree.h"
  4. #include "lub/blockpool.h"
  5. #include "lub/test.h"
  6. /**
  7. \example test/bintree.c
  8. */
  9. /*************************************************************
  10. * TEST CODE
  11. ************************************************************* */
  12. /* create a pool of nodes */
  13. static test_node_t nodes[NUM_TEST_NODES];
  14. static lub_blockpool_t testpool;
  15. static test_node_t duplicate;
  16. static int testseq;
  17. /*--------------------------------------------------------------- */
  18. /*
  19. #define DUMP
  20. */
  21. static void
  22. dump_node(lub_bintree_t *this,
  23. lub_bintree_node_t *node)
  24. {
  25. test_node_t *clientnode = (void *)(((char*)node) - this->node_offset);
  26. test_node_t *leftnode = (void *)(((char*)node->left) - this->node_offset);
  27. test_node_t *rightnode = (void *)(((char*)node->right) - this->node_offset);
  28. if(NULL != node)
  29. {
  30. printf(" %d<--%d-->%d",
  31. leftnode ? leftnode->value : -1,
  32. clientnode->value,
  33. rightnode ? rightnode->value : -1);
  34. if(node->left)
  35. dump_node(this,node->left);
  36. if(node->right)
  37. dump_node(this,node->right);
  38. }
  39. }
  40. extern void dump_tree(lub_bintree_t *tree);
  41. void
  42. dump_tree(lub_bintree_t *tree)
  43. {
  44. printf("\nTREE(0x%p):",(void*)tree);
  45. dump_node(tree,tree->root);
  46. printf("\n");
  47. }
  48. #ifndef DUMP
  49. #define dump_tree(tree)
  50. #endif /* not DUMP */
  51. /*
  52. * Returns a pseudo random number based on the input.
  53. * This will given 2^15 concequtive numbers generate the entire
  54. * number space in a psedo random manner.
  55. */
  56. static int
  57. random(int i)
  58. {
  59. /* multiply the first prime after 2^14 and mask to 15 bits */
  60. return (16411*i) & (32767);
  61. }
  62. /* This operation is invokes to initialise a new instance of a test node
  63. *
  64. * seed - the seed to use for the random details within the instance
  65. */
  66. static void
  67. constructor(test_node_t *this,
  68. int seed)
  69. {
  70. this->value = seed;
  71. this->address[0] = 0x08;
  72. this->address[1] = 0x00;
  73. this->address[2] = 0x4e;
  74. this->address[3] = 0x00;
  75. this->address[4] = ((this->value ) & 0xFF);
  76. this->address[5] = ((this->value >> 8) & 0xFF);
  77. /* initialise the control blocks */
  78. lub_bintree_node_init(&this->bt_node1);
  79. lub_bintree_node_init(&this->bt_node2);
  80. }
  81. /* This operation creates and initialised a new instance of a test node
  82. *
  83. * seed - the seed to use for the random details within the instance
  84. */
  85. static test_node_t *
  86. new(int seed)
  87. {
  88. test_node_t *node = lub_blockpool_alloc(&testpool);
  89. if(NULL != node)
  90. {
  91. /* call the constructor */
  92. constructor(node,seed);
  93. }
  94. return node;
  95. }
  96. /* forward declare these functions */
  97. static lub_bintree_compare_fn test_value_compare;
  98. static lub_bintree_getkey_fn test_value_getkey;
  99. static lub_bintree_compare_fn test_address_compare;
  100. static lub_bintree_getkey_fn test_address_getkey;
  101. /*
  102. * This defines the attributes associated with a tree
  103. */
  104. typedef struct
  105. {
  106. lub_bintree_t tree;
  107. lub_bintree_compare_fn *compare;
  108. lub_bintree_getkey_fn *getkey;
  109. size_t offset;
  110. lub_bintree_key_t nonexistant;
  111. } mapping_t;
  112. typedef struct
  113. {
  114. unsigned char address[6];
  115. } address_key_t;
  116. typedef struct
  117. {
  118. int value;
  119. } value_key_t;
  120. /* This is the main entry point for this executable
  121. */
  122. int main(int argc, const char *argv[])
  123. {
  124. unsigned int i,t;
  125. int status;
  126. /*
  127. * TREE ATTRBUTES
  128. */
  129. address_key_t address_key = {{0xff,0xff,0xff,0xff,0xff,0xff}};
  130. value_key_t value_key = {-1};
  131. mapping_t mapping[2];
  132. lub_test_parse_command_line(argc,argv);
  133. lub_test_begin("lub_bintree");
  134. /*
  135. * define the attributes for each tree
  136. */
  137. /* integer based search */
  138. mapping[0].compare = test_value_compare;
  139. mapping[0].getkey = test_value_getkey;
  140. mapping[0].offset = offsetof(test_node_t,bt_node1);
  141. memcpy(&mapping[0].nonexistant,&value_key,sizeof(value_key));
  142. /* MAC address based search */
  143. mapping[1].compare = test_address_compare;
  144. mapping[1].getkey = test_address_getkey;
  145. mapping[1].offset = offsetof(test_node_t,bt_node2);
  146. memcpy(&mapping[1].nonexistant,&address_key,sizeof(address_key));
  147. /*
  148. * create a duplicate node... (will get the same details as
  149. * the first one from the pool)
  150. */
  151. constructor(&duplicate,0);
  152. /*
  153. * create a blockpool to manage node allocation/deallocation
  154. */
  155. lub_blockpool_init(&testpool,
  156. nodes,
  157. sizeof(test_node_t),
  158. NUM_TEST_NODES);
  159. /*
  160. * test each tree
  161. */
  162. for(t = 0; t < 2; t++)
  163. {
  164. lub_bintree_t *tree = &mapping[t].tree;
  165. /* create the tree */
  166. lub_test_seq_begin(++testseq,"tree(%d)",t);
  167. lub_bintree_init(tree,
  168. mapping[t].offset,
  169. mapping[t].compare,
  170. mapping[t].getkey);
  171. /*------------------------------------------------------------ */
  172. lub_test_check(NULL == lub_bintree_findfirst(tree),
  173. "Check findfirst returns NULL on empty tree");
  174. lub_test_check(NULL == lub_bintree_findlast(tree),
  175. "Check findlast returns NULL on an empty tree");
  176. /*------------------------------------------------------------ */
  177. status = LUB_TEST_PASS;
  178. for(i=0; i < NUM_TEST_NODES;i++)
  179. {
  180. test_node_t *node;
  181. if(0 == t)
  182. {
  183. /* create a test node */
  184. node = new(i);
  185. if(NULL == node)
  186. {
  187. status = LUB_TEST_FAIL;
  188. break;
  189. }
  190. }
  191. else
  192. {
  193. value_key_t key;
  194. key.value = i;
  195. /*
  196. * find the necessary node using the
  197. * first tree (fiddling with one tree
  198. * before inserting into another
  199. */
  200. node = lub_bintree_find(&mapping[0].tree,
  201. &key);
  202. }
  203. /* insert it into the tree */
  204. if(0 != lub_bintree_insert(tree,node))
  205. {
  206. status = LUB_TEST_FAIL;
  207. break;
  208. }
  209. }
  210. lub_test_check(LUB_TEST_PASS == status,
  211. "Inserting %d nodes",
  212. NUM_TEST_NODES);
  213. /*------------------------------------------------------------ */
  214. lub_test_check_int(-1,lub_bintree_insert(tree,&duplicate),
  215. "Inserting duplicate should fail");
  216. /*------------------------------------------------------------ */
  217. lub_bintree_remove(tree,&duplicate);
  218. lub_test_seq_log(LUB_TEST_NORMAL,"Remove original node");
  219. /*------------------------------------------------------------ */
  220. lub_test_check_int(0,lub_bintree_insert(tree,&duplicate),
  221. "Reinsert original node");
  222. /*------------------------------------------------------------ */
  223. status = LUB_TEST_PASS;
  224. for(i=0; i < NUM_TEST_NODES;i++)
  225. {
  226. test_node_t *node;
  227. /*
  228. * find each test node in the tree
  229. */
  230. if (t == 0)
  231. {
  232. /*
  233. * search by integer
  234. */
  235. value_key_t key;
  236. key.value = random(i);
  237. node = lub_bintree_find(tree,&key);
  238. if(node->value != key.value)
  239. {
  240. status = LUB_TEST_FAIL;
  241. break;
  242. }
  243. }
  244. else
  245. {
  246. /*
  247. * search by address
  248. */
  249. address_key_t key;
  250. int rand = random(i);
  251. key.address[0] = 0x08;
  252. key.address[1] = 0x00;
  253. key.address[2] = 0x4e;
  254. key.address[3] = 0x00;
  255. key.address[4] = ((rand ) & 0xFF);
  256. key.address[5] = ((rand >> 8) & 0xFF);
  257. node = lub_bintree_find(tree,&key);
  258. if(memcmp(key.address, node->address,6) != 0)
  259. {
  260. status = LUB_TEST_FAIL;
  261. break;
  262. }
  263. }
  264. }
  265. lub_test_check(LUB_TEST_PASS == status,
  266. "Check lub_bintree_find() can find every node");
  267. /*------------------------------------------------------------ */
  268. /*
  269. * iterate through the tree forwards
  270. */
  271. {
  272. lub_bintree_iterator_t iter;
  273. test_node_t *node = lub_bintree_findfirst(tree);
  274. int j = 0;
  275. status = LUB_TEST_PASS;
  276. for(lub_bintree_iterator_init(&iter,tree,node);
  277. node;
  278. node = lub_bintree_iterator_next(&iter),j++)
  279. {
  280. if(t == 0)
  281. {
  282. /* check that the insertion works in the right order */
  283. if(node->value != j)
  284. {
  285. status = LUB_TEST_FAIL;
  286. break;
  287. }
  288. }
  289. }
  290. lub_test_check(LUB_TEST_PASS == status,
  291. "Iterate forwards checking order",t);
  292. }
  293. /*------------------------------------------------------------ */
  294. /*
  295. * iterate through the tree backwards
  296. */
  297. {
  298. lub_bintree_iterator_t iter;
  299. test_node_t *node = lub_bintree_findlast(tree);
  300. int j = NUM_TEST_NODES - 1;
  301. status = LUB_TEST_PASS;
  302. for(lub_bintree_iterator_init(&iter,tree,node);
  303. node;
  304. node = lub_bintree_iterator_previous(&iter),j--)
  305. {
  306. if(t == 0)
  307. {
  308. /* check that the insertion works in the right order */
  309. if(node->value != j)
  310. {
  311. status = LUB_TEST_FAIL;
  312. break;
  313. }
  314. }
  315. }
  316. }
  317. lub_test_check(LUB_TEST_PASS == status,
  318. "Iterate backwards checking order",t);
  319. /*------------------------------------------------------------ */
  320. lub_test_check(NULL == lub_bintree_find(tree,&mapping[t].nonexistant),
  321. "Check search for non-existant node fails");
  322. /*------------------------------------------------------------ */
  323. lub_test_seq_end();
  324. }
  325. for(t=0;t <2; t++)
  326. {
  327. lub_bintree_t *tree = &mapping[t].tree;
  328. test_node_t *node;
  329. void *(*find_op)(lub_bintree_t *) = lub_bintree_findfirst;
  330. /*------------------------------------------------------------ */
  331. lub_test_seq_begin(++testseq,"tree(%d)",t);
  332. /*
  333. * iterate through the tree removing the nodes
  334. */
  335. i = 0;
  336. while( (node = find_op(tree)) )
  337. {
  338. /* remove from the tree */
  339. lub_bintree_remove(tree,node);
  340. if (t == 1)
  341. {
  342. /* add back to the pool */
  343. lub_blockpool_free(&testpool,node);
  344. }
  345. i++;
  346. if(find_op == lub_bintree_findfirst)
  347. {
  348. find_op = lub_bintree_findlast;
  349. }
  350. else
  351. {
  352. find_op = lub_bintree_findfirst;
  353. }
  354. }
  355. lub_test_check_int(i,NUM_TEST_NODES,"Check removed all nodes");
  356. lub_test_seq_end();
  357. /*------------------------------------------------------------ */
  358. }
  359. /* tidy up */
  360. status = lub_test_get_status();
  361. lub_test_end();
  362. return status;
  363. }
  364. static int
  365. test_value_compare(const void *clientnode,
  366. const void *clientkey)
  367. {
  368. const test_node_t *node = clientnode;
  369. const value_key_t *key = clientkey;
  370. return node->value - key->value;
  371. }
  372. static void
  373. test_value_getkey(const void *clientnode,
  374. lub_bintree_key_t *key)
  375. {
  376. const test_node_t *node = clientnode;
  377. /* fill out the opaque key */
  378. memcpy(key,&node->value,sizeof(int));
  379. }
  380. static int
  381. test_address_compare(const void *clientnode,
  382. const void *clientkey)
  383. {
  384. const test_node_t *node = clientnode;
  385. return memcmp(node->address,clientkey,6);
  386. }
  387. static void
  388. test_address_getkey(const void *clientnode,
  389. lub_bintree_key_t *key)
  390. {
  391. const test_node_t *node = clientnode;
  392. /* fill out the opaque key */
  393. memcpy(key,node->address,6);
  394. }