Mon, 20 Feb 2017 16:04:14 +0100
adds new test case for sstrsplit: string ends with delimiter but empty string exceeds list bound
universe@56 | 1 | /* |
universe@103 | 2 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. |
universe@56 | 3 | * |
universe@225 | 4 | * Copyright 2016 Olaf Wintermann. All rights reserved. |
universe@103 | 5 | * |
universe@103 | 6 | * Redistribution and use in source and binary forms, with or without |
universe@103 | 7 | * modification, are permitted provided that the following conditions are met: |
universe@103 | 8 | * |
universe@103 | 9 | * 1. Redistributions of source code must retain the above copyright |
universe@103 | 10 | * notice, this list of conditions and the following disclaimer. |
universe@103 | 11 | * |
universe@103 | 12 | * 2. Redistributions in binary form must reproduce the above copyright |
universe@103 | 13 | * notice, this list of conditions and the following disclaimer in the |
universe@103 | 14 | * documentation and/or other materials provided with the distribution. |
universe@103 | 15 | * |
universe@103 | 16 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
universe@103 | 17 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
universe@103 | 18 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
universe@103 | 19 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE |
universe@103 | 20 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
universe@103 | 21 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
universe@103 | 22 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
universe@103 | 23 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
universe@103 | 24 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
universe@103 | 25 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
universe@103 | 26 | * POSSIBILITY OF SUCH DAMAGE. |
universe@56 | 27 | */ |
universe@56 | 28 | |
universe@192 | 29 | #include "avl_tests.h" |
universe@56 | 30 | |
olaf@198 | 31 | #include "ucx/utils.h" |
olaf@198 | 32 | |
olaf@198 | 33 | static int node_height(UcxAVLNode *node) { |
olaf@198 | 34 | if(!node) { |
olaf@198 | 35 | return 0; |
olaf@198 | 36 | } |
olaf@198 | 37 | |
olaf@198 | 38 | int left = 0; |
olaf@198 | 39 | int right = 0; |
olaf@198 | 40 | if(node->left) { |
olaf@198 | 41 | left = node_height(node->left); |
olaf@198 | 42 | } |
olaf@198 | 43 | if(node->right) { |
olaf@198 | 44 | right = node_height(node->right); |
olaf@198 | 45 | } |
olaf@198 | 46 | |
olaf@198 | 47 | return left > right ? left+1 : right+1; |
olaf@198 | 48 | } |
olaf@198 | 49 | |
olaf@198 | 50 | static int check_tree(UcxAVLNode *node) { |
olaf@198 | 51 | if(!node) { |
olaf@198 | 52 | return 1; |
olaf@198 | 53 | } |
olaf@198 | 54 | |
olaf@198 | 55 | int left_height = node_height(node->left); |
olaf@198 | 56 | int right_height = node_height(node->right); |
olaf@198 | 57 | int bf = -left_height + right_height; |
olaf@198 | 58 | if(bf < -1 || bf > 1) { |
olaf@198 | 59 | return 0; |
olaf@198 | 60 | } |
olaf@198 | 61 | int height = left_height > right_height ? left_height : right_height; |
olaf@198 | 62 | height++; |
olaf@198 | 63 | if(height != node->height) { |
olaf@198 | 64 | return 0; |
olaf@198 | 65 | } |
olaf@198 | 66 | |
olaf@198 | 67 | if(!check_tree(node->left)) { |
olaf@198 | 68 | return 0; |
olaf@198 | 69 | } |
olaf@198 | 70 | if(!check_tree(node->right)) { |
olaf@198 | 71 | return 0; |
olaf@198 | 72 | } |
olaf@198 | 73 | |
olaf@198 | 74 | return 1; |
olaf@198 | 75 | } |
olaf@198 | 76 | |
olaf@198 | 77 | UCX_TEST(test_ucx_avl_put) { |
olaf@198 | 78 | UcxAVLTree *tree1 = ucx_avl_new(ucx_ptrcmp); |
olaf@198 | 79 | UcxAVLTree *tree2 = ucx_avl_new(ucx_ptrcmp); |
olaf@198 | 80 | UcxAVLTree *tree3 = ucx_avl_new(ucx_ptrcmp); |
olaf@198 | 81 | UcxAVLTree *tree4 = ucx_avl_new(ucx_ptrcmp); |
olaf@198 | 82 | UcxAVLTree *tree5 = ucx_avl_new(ucx_ptrcmp); |
olaf@198 | 83 | |
olaf@198 | 84 | char *data1 = (char*)"data1"; |
olaf@198 | 85 | char *data2 = (char*)"data2"; |
olaf@198 | 86 | char *data3 = (char*)"data3"; |
olaf@198 | 87 | |
olaf@198 | 88 | UCX_TEST_BEGIN |
olaf@198 | 89 | |
olaf@198 | 90 | ucx_avl_put(tree1, 2, (char*)data2); |
olaf@198 | 91 | ucx_avl_put(tree1, 1, (char*)data1); |
olaf@198 | 92 | ucx_avl_put(tree1, 3, (char*)data3); |
olaf@198 | 93 | |
olaf@198 | 94 | UCX_TEST_ASSERT(check_tree(tree1->root), "check_tree failed (tree1)"); |
olaf@198 | 95 | UCX_TEST_ASSERT(ucx_avl_get(tree1, 1) == data1, "wrong data (tree1)"); |
olaf@198 | 96 | UCX_TEST_ASSERT(ucx_avl_get(tree1, 2) == data2, "wrong data (tree1)"); |
olaf@198 | 97 | UCX_TEST_ASSERT(ucx_avl_get(tree1, 3) == data3, "wrong data (tree1)"); |
olaf@198 | 98 | |
olaf@198 | 99 | for(int i=0;i<100000;i++) { |
olaf@198 | 100 | ucx_avl_put(tree2, i, data1); |
olaf@198 | 101 | } |
olaf@198 | 102 | UCX_TEST_ASSERT(check_tree(tree2->root), "check_tree failed (tree2)"); |
olaf@198 | 103 | |
olaf@198 | 104 | for(int i=100000;i>=0;i--) { |
olaf@198 | 105 | ucx_avl_put(tree3, i, data1); |
olaf@198 | 106 | } |
olaf@198 | 107 | UCX_TEST_ASSERT(check_tree(tree3->root), "check_tree failed (tree3)"); |
olaf@198 | 108 | |
olaf@198 | 109 | for(int i=0;i<100;i++) { |
olaf@198 | 110 | ucx_avl_put(tree4, i, data1); |
olaf@198 | 111 | } |
olaf@198 | 112 | for(int i=400;i<500;i++) { |
olaf@198 | 113 | ucx_avl_put(tree4, i, data2); |
olaf@198 | 114 | } |
olaf@198 | 115 | for(int i=399;i>200;i--) { |
olaf@198 | 116 | ucx_avl_put(tree4, i, data3); |
olaf@198 | 117 | } |
olaf@198 | 118 | for(int i=800;i<1000;i++) { |
olaf@198 | 119 | ucx_avl_put(tree4, i, data1); |
olaf@198 | 120 | } |
olaf@198 | 121 | UCX_TEST_ASSERT(check_tree(tree4->root), "check_tree failed (tree4)"); |
olaf@198 | 122 | UCX_TEST_ASSERT(ucx_avl_get(tree4, 0) == data1, "wrong data for key: 0"); |
olaf@198 | 123 | UCX_TEST_ASSERT(ucx_avl_get(tree4, 1) == data1, "wrong data for key: 1"); |
olaf@198 | 124 | UCX_TEST_ASSERT(ucx_avl_get(tree4, 99) == data1, "wrong data for key: 99"); |
olaf@198 | 125 | UCX_TEST_ASSERT(ucx_avl_get(tree4, 400)==data2, "wrong data for key: 400"); |
olaf@198 | 126 | UCX_TEST_ASSERT(ucx_avl_get(tree4, 410)==data2, "wrong data for key: 410"); |
olaf@198 | 127 | UCX_TEST_ASSERT(ucx_avl_get(tree4, 350)==data3, "wrong data for key: 350"); |
olaf@198 | 128 | UCX_TEST_ASSERT(ucx_avl_get(tree4, 900)==data1, "wrong data for key: 900"); |
olaf@198 | 129 | |
olaf@198 | 130 | int values[] = { 3, 6, 12, 9, 23, 1, 0, 20, 34, 5, 8, 7, 6, 14, 15, 2, 4}; |
olaf@198 | 131 | int len = sizeof(values) / sizeof(int); |
olaf@198 | 132 | for(int i=0;i<len;i++) { |
olaf@198 | 133 | ucx_avl_put(tree5, values[i], NULL); |
olaf@198 | 134 | } |
olaf@198 | 135 | UCX_TEST_ASSERT(check_tree(tree5->root), "check_tree failed (tree5)"); |
olaf@198 | 136 | |
olaf@198 | 137 | UCX_TEST_END |
olaf@198 | 138 | |
olaf@198 | 139 | ucx_avl_free(tree1); |
olaf@198 | 140 | ucx_avl_free(tree2); |
olaf@198 | 141 | ucx_avl_free(tree3); |
olaf@198 | 142 | ucx_avl_free(tree4); |
olaf@198 | 143 | ucx_avl_free(tree5); |
olaf@198 | 144 | } |
olaf@200 | 145 | |
olaf@200 | 146 | UCX_TEST(test_ucx_avl_remove) { |
olaf@200 | 147 | UcxAVLTree *tree1 = ucx_avl_new(ucx_ptrcmp); |
olaf@200 | 148 | UcxAVLTree *tree2 = ucx_avl_new(ucx_ptrcmp); |
olaf@200 | 149 | UcxAVLTree *tree3 = ucx_avl_new(ucx_ptrcmp); |
olaf@200 | 150 | UcxAVLTree *tree4 = ucx_avl_new(ucx_ptrcmp); |
olaf@200 | 151 | |
olaf@200 | 152 | char *data1 = (char*)"data1"; |
olaf@200 | 153 | char *data2 = (char*)"data2"; |
olaf@200 | 154 | char *data3 = (char*)"data3"; |
olaf@200 | 155 | |
olaf@200 | 156 | UCX_TEST_BEGIN |
olaf@200 | 157 | ucx_avl_put(tree1, 2, (char*)data2); |
olaf@200 | 158 | ucx_avl_put(tree1, 1, (char*)data1); |
olaf@200 | 159 | ucx_avl_put(tree1, 3, (char*)data3); |
universe@204 | 160 | void *val; |
universe@204 | 161 | ucx_avl_remove_s(tree1, 3, NULL, &val); |
olaf@200 | 162 | |
olaf@200 | 163 | UCX_TEST_ASSERT(check_tree(tree1->root), "check_tree failed (tree1)"); |
universe@204 | 164 | UCX_TEST_ASSERT(val == data3, |
olaf@201 | 165 | "wrong return value for key: 1 (tree1)"); |
olaf@200 | 166 | UCX_TEST_ASSERT(ucx_avl_get(tree1, 3) == NULL, "value not removed (tree1)"); |
universe@204 | 167 | |
universe@204 | 168 | ucx_avl_remove_s(tree1, 2, NULL, &val); |
universe@204 | 169 | UCX_TEST_ASSERT(val == data2, |
olaf@201 | 170 | "wrong return value for key: 2 (tree1)"); |
olaf@201 | 171 | UCX_TEST_ASSERT(check_tree(tree1->root), "check_tree failed (tree1)"); |
universe@204 | 172 | |
universe@204 | 173 | ucx_avl_remove_s(tree1, 1, NULL, &val); |
universe@204 | 174 | UCX_TEST_ASSERT(val == data1, |
olaf@201 | 175 | "wrong return value for key: 1 (tree1)"); |
olaf@201 | 176 | UCX_TEST_ASSERT(check_tree(tree1->root), "check_tree failed (tree1)"); |
olaf@201 | 177 | UCX_TEST_ASSERT(tree1->root == NULL, "root not NULL (tree1)"); |
olaf@201 | 178 | |
olaf@200 | 179 | |
olaf@200 | 180 | for(int i=0;i<20;i++) { |
olaf@200 | 181 | if(i==10) { |
olaf@200 | 182 | ucx_avl_put(tree2, i, data3); |
olaf@200 | 183 | } else if(i==15) { |
olaf@200 | 184 | ucx_avl_put(tree2, i, data2); |
olaf@200 | 185 | } else { |
olaf@200 | 186 | ucx_avl_put(tree2, i, data1); |
olaf@200 | 187 | } |
olaf@200 | 188 | } |
olaf@200 | 189 | |
universe@204 | 190 | ucx_avl_remove_s(tree2, 10, NULL, &val); |
universe@204 | 191 | UCX_TEST_ASSERT(val == data3, |
olaf@200 | 192 | "wrong return value for key: 10 (tree2)"); |
olaf@200 | 193 | UCX_TEST_ASSERT(check_tree(tree2->root), "check_tree failed (tree2)"); |
olaf@200 | 194 | |
universe@204 | 195 | ucx_avl_remove_s(tree2, 15, NULL, &val); |
universe@204 | 196 | UCX_TEST_ASSERT(val == data2, |
olaf@200 | 197 | "wrong return value for key: 15 (tree2)"); |
olaf@200 | 198 | UCX_TEST_ASSERT(check_tree(tree2->root), "check_tree failed (tree2)"); |
olaf@200 | 199 | |
olaf@200 | 200 | for(int i=0;i<20;i++) { |
olaf@200 | 201 | ucx_avl_remove(tree2, i); |
olaf@200 | 202 | UCX_TEST_ASSERT(check_tree(tree2->root), "check_tree failed (tree2)"); |
olaf@200 | 203 | } |
olaf@203 | 204 | UCX_TEST_ASSERT(tree2->root == NULL, "root not NULL (tree2)"); |
olaf@200 | 205 | |
olaf@200 | 206 | for(int i=0;i<100000;i++) { |
olaf@200 | 207 | ucx_avl_put(tree3, i, data1); |
olaf@200 | 208 | } |
olaf@200 | 209 | for(int i=100000-1;i>=0;i--) { |
olaf@200 | 210 | ucx_avl_remove(tree3, i); |
olaf@200 | 211 | } |
olaf@200 | 212 | UCX_TEST_ASSERT(tree3->root == NULL, "root not NULL (tree3)"); |
olaf@200 | 213 | UCX_TEST_ASSERT(check_tree(tree3->root), "check_tree failed (tree3)"); |
olaf@200 | 214 | |
olaf@200 | 215 | ucx_avl_put(tree4, 1, data1); |
olaf@200 | 216 | ucx_avl_remove(tree4, 1); |
olaf@200 | 217 | UCX_TEST_ASSERT(check_tree(tree4->root), "check_tree failed (tree4)"); |
olaf@200 | 218 | UCX_TEST_ASSERT(tree4->root == NULL, "root not NULL (tree4)"); |
olaf@200 | 219 | UCX_TEST_END |
olaf@200 | 220 | |
olaf@200 | 221 | ucx_avl_free(tree1); |
olaf@200 | 222 | ucx_avl_free(tree2); |
olaf@200 | 223 | ucx_avl_free(tree3); |
olaf@200 | 224 | ucx_avl_free(tree4); |
olaf@200 | 225 | } |