comparison: test/avl_tests.c
test/avl_tests.c
- changeset 198
- b0f4fb043b47
- parent 192
- 1e51558b9d09
- child 200
- e3aad99d2d80
equal
deleted
inserted
replaced
| 197:a82f3456b76d | 198:b0f4fb043b47 |
|---|---|
| 26 * POSSIBILITY OF SUCH DAMAGE. | 26 * POSSIBILITY OF SUCH DAMAGE. |
| 27 */ | 27 */ |
| 28 | 28 |
| 29 #include "avl_tests.h" | 29 #include "avl_tests.h" |
| 30 | 30 |
| 31 #include "ucx/utils.h" | |
| 32 | |
| 33 static int node_height(UcxAVLNode *node) { | |
| 34 if(!node) { | |
| 35 return 0; | |
| 36 } | |
| 37 | |
| 38 int left = 0; | |
| 39 int right = 0; | |
| 40 if(node->left) { | |
| 41 left = node_height(node->left); | |
| 42 } | |
| 43 if(node->right) { | |
| 44 right = node_height(node->right); | |
| 45 } | |
| 46 | |
| 47 return left > right ? left+1 : right+1; | |
| 48 } | |
| 49 | |
| 50 static int check_tree(UcxAVLNode *node) { | |
| 51 if(!node) { | |
| 52 return 1; | |
| 53 } | |
| 54 | |
| 55 int left_height = node_height(node->left); | |
| 56 int right_height = node_height(node->right); | |
| 57 int bf = -left_height + right_height; | |
| 58 if(bf < -1 || bf > 1) { | |
| 59 return 0; | |
| 60 } | |
| 61 int height = left_height > right_height ? left_height : right_height; | |
| 62 height++; | |
| 63 if(height != node->height) { | |
| 64 return 0; | |
| 65 } | |
| 66 | |
| 67 if(!check_tree(node->left)) { | |
| 68 return 0; | |
| 69 } | |
| 70 if(!check_tree(node->right)) { | |
| 71 return 0; | |
| 72 } | |
| 73 | |
| 74 return 1; | |
| 75 } | |
| 76 | |
| 77 UCX_TEST(test_ucx_avl_put) { | |
| 78 UcxAVLTree *tree1 = ucx_avl_new(ucx_ptrcmp); | |
| 79 UcxAVLTree *tree2 = ucx_avl_new(ucx_ptrcmp); | |
| 80 UcxAVLTree *tree3 = ucx_avl_new(ucx_ptrcmp); | |
| 81 UcxAVLTree *tree4 = ucx_avl_new(ucx_ptrcmp); | |
| 82 UcxAVLTree *tree5 = ucx_avl_new(ucx_ptrcmp); | |
| 83 | |
| 84 char *data1 = (char*)"data1"; | |
| 85 char *data2 = (char*)"data2"; | |
| 86 char *data3 = (char*)"data3"; | |
| 87 | |
| 88 UCX_TEST_BEGIN | |
| 89 | |
| 90 ucx_avl_put(tree1, 2, (char*)data2); | |
| 91 ucx_avl_put(tree1, 1, (char*)data1); | |
| 92 ucx_avl_put(tree1, 3, (char*)data3); | |
| 93 | |
| 94 UCX_TEST_ASSERT(check_tree(tree1->root), "check_tree failed (tree1)"); | |
| 95 UCX_TEST_ASSERT(ucx_avl_get(tree1, 1) == data1, "wrong data (tree1)"); | |
| 96 UCX_TEST_ASSERT(ucx_avl_get(tree1, 2) == data2, "wrong data (tree1)"); | |
| 97 UCX_TEST_ASSERT(ucx_avl_get(tree1, 3) == data3, "wrong data (tree1)"); | |
| 98 | |
| 99 for(int i=0;i<100000;i++) { | |
| 100 ucx_avl_put(tree2, i, data1); | |
| 101 } | |
| 102 UCX_TEST_ASSERT(check_tree(tree2->root), "check_tree failed (tree2)"); | |
| 103 | |
| 104 for(int i=100000;i>=0;i--) { | |
| 105 ucx_avl_put(tree3, i, data1); | |
| 106 } | |
| 107 UCX_TEST_ASSERT(check_tree(tree3->root), "check_tree failed (tree3)"); | |
| 108 | |
| 109 for(int i=0;i<100;i++) { | |
| 110 ucx_avl_put(tree4, i, data1); | |
| 111 } | |
| 112 for(int i=400;i<500;i++) { | |
| 113 ucx_avl_put(tree4, i, data2); | |
| 114 } | |
| 115 for(int i=399;i>200;i--) { | |
| 116 ucx_avl_put(tree4, i, data3); | |
| 117 } | |
| 118 for(int i=800;i<1000;i++) { | |
| 119 ucx_avl_put(tree4, i, data1); | |
| 120 } | |
| 121 UCX_TEST_ASSERT(check_tree(tree4->root), "check_tree failed (tree4)"); | |
| 122 UCX_TEST_ASSERT(ucx_avl_get(tree4, 0) == data1, "wrong data for key: 0"); | |
| 123 UCX_TEST_ASSERT(ucx_avl_get(tree4, 1) == data1, "wrong data for key: 1"); | |
| 124 UCX_TEST_ASSERT(ucx_avl_get(tree4, 99) == data1, "wrong data for key: 99"); | |
| 125 UCX_TEST_ASSERT(ucx_avl_get(tree4, 400)==data2, "wrong data for key: 400"); | |
| 126 UCX_TEST_ASSERT(ucx_avl_get(tree4, 410)==data2, "wrong data for key: 410"); | |
| 127 UCX_TEST_ASSERT(ucx_avl_get(tree4, 350)==data3, "wrong data for key: 350"); | |
| 128 UCX_TEST_ASSERT(ucx_avl_get(tree4, 900)==data1, "wrong data for key: 900"); | |
| 129 | |
| 130 int values[] = { 3, 6, 12, 9, 23, 1, 0, 20, 34, 5, 8, 7, 6, 14, 15, 2, 4}; | |
| 131 int len = sizeof(values) / sizeof(int); | |
| 132 for(int i=0;i<len;i++) { | |
| 133 ucx_avl_put(tree5, values[i], NULL); | |
| 134 } | |
| 135 UCX_TEST_ASSERT(check_tree(tree5->root), "check_tree failed (tree5)"); | |
| 136 | |
| 137 UCX_TEST_END | |
| 138 | |
| 139 ucx_avl_free(tree1); | |
| 140 ucx_avl_free(tree2); | |
| 141 ucx_avl_free(tree3); | |
| 142 ucx_avl_free(tree4); | |
| 143 ucx_avl_free(tree5); | |
| 144 } |
