test_binary_heap.c (6026B)
1 /* Copyright (C) 2013-2023, 2025 Vincent Forest (vaplv@free.fr) 2 * 3 * The RSys library is free software: you can redistribute it and/or modify 4 * it under the terms of the GNU General Public License as published 5 * by the Free Software Foundation, either version 3 of the License, or 6 * (at your option) any later version. 7 * 8 * The RSys library is distributed in the hope that it will be useful, 9 * but WITHOUT ANY WARRANTY; without even the implied warranty of 10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 11 * GNU General Public License for more details. 12 * 13 * You should have received a copy of the GNU General Public License 14 * along with the RSys library. If not, see <http://www.gnu.org/licenses/>. */ 15 16 #include "binary_heap.h" 17 #include "str.h" 18 #include "test_utils.h" 19 20 #define BHEAP_NAME u64 21 #define BHEAP_DATA uint64_t 22 #include "binary_heap.h" 23 24 static void 25 test_primitive_type(void) 26 { 27 struct mem_allocator allocator_proxy; 28 struct bheap_u64 heap; 29 uint64_t i; 30 31 mem_init_proxy_allocator(&allocator_proxy, &mem_default_allocator); 32 33 bheap_u64_init(&allocator_proxy, &heap); 34 CHK(bheap_u64_is_empty(&heap) == 1); 35 bheap_u64_clear(&heap); 36 CHK(bheap_u64_is_empty(&heap) == 1); 37 38 CHK(bheap_u64_is_empty(&heap) == 1); 39 CHK(bheap_u64_top(&heap, &i) == 0); 40 CHK(bheap_u64_pop(&heap, &i) == 0); 41 i = 48; CHK(bheap_u64_insert(&heap, &i) == RES_OK); 42 i = 51; CHK(bheap_u64_insert(&heap, &i) == RES_OK); 43 i = 1; CHK(bheap_u64_insert(&heap, &i) == RES_OK); 44 i = 7; CHK(bheap_u64_insert(&heap, &i) == RES_OK); 45 i = 78; CHK(bheap_u64_insert(&heap, &i) == RES_OK); 46 i = 4; CHK(bheap_u64_insert(&heap, &i) == RES_OK); 47 i = 61; CHK(bheap_u64_insert(&heap, &i) == RES_OK); 48 i = 72; CHK(bheap_u64_insert(&heap, &i) == RES_OK); 49 CHK(bheap_u64_is_empty(&heap) == 0); 50 51 CHK(bheap_u64_top(&heap, &i) != 0); 52 CHK(i == 1); 53 CHK(bheap_u64_top(&heap, &i) != 0); 54 CHK(i == 1); 55 CHK(bheap_u64_pop(&heap, &i) != 0); 56 CHK(i == 1); 57 CHK(bheap_u64_pop(&heap, &i) != 0); 58 CHK(i == 4); 59 CHK(bheap_u64_pop(&heap, &i) != 0); 60 CHK(i == 7); 61 CHK(bheap_u64_pop(&heap, &i) != 0); 62 CHK(i == 48); 63 64 i = 5; CHK(bheap_u64_insert(&heap, &i) == RES_OK); 65 i = 50; CHK(bheap_u64_insert(&heap, &i) == RES_OK); 66 i = 51; CHK(bheap_u64_insert(&heap, &i) == RES_OK); 67 CHK(bheap_u64_top(&heap, &i) != 0); 68 CHK(i == 5); 69 CHK(bheap_u64_pop(&heap, &i) != 0); 70 CHK(i == 5); 71 CHK(bheap_u64_pop(&heap, &i) != 0); 72 CHK(i == 50); 73 CHK(bheap_u64_pop(&heap, &i) != 0); 74 CHK(i == 51); 75 CHK(bheap_u64_pop(&heap, &i) != 0); 76 CHK(i == 51); 77 CHK(bheap_u64_pop(&heap, &i) != 0); 78 CHK(i == 61); 79 CHK(bheap_u64_pop(&heap, &i) != 0); 80 CHK(i == 72); 81 CHK(bheap_u64_pop(&heap, &i) != 0); 82 CHK(i == 78); 83 CHK(bheap_u64_pop(&heap, &i) == 0); 84 85 CHK(bheap_u64_is_empty(&heap) == 1); 86 87 FOR_EACH(i, 0, 17689) { 88 const uint64_t j = (uint64_t)rand(); 89 CHK(bheap_u64_insert(&heap, &j) == RES_OK); 90 } 91 CHK(bheap_u64_is_empty(&heap) == 0); 92 CHK(bheap_u64_pop(&heap, &i) != 0); 93 while(bheap_u64_is_empty(&heap)) { 94 uint64_t j = 0; 95 CHK(bheap_u64_pop(&heap, &j) != 0); 96 CHK(j >= i); 97 i = j; 98 } 99 100 bheap_u64_release(&heap); 101 check_memory_allocator(&allocator_proxy); 102 mem_shutdown_proxy_allocator(&allocator_proxy); 103 } 104 105 #define BHEAP_NAME str 106 #define BHEAP_DATA struct str 107 #define BHEAP_FUNCTOR_INIT str_init 108 #define BHEAP_FUNCTOR_COPY str_copy 109 #define BHEAP_FUNCTOR_RELEASE str_release 110 #define BHEAP_FUNCTOR_COPY_AND_RELEASE str_copy_and_release 111 #define BHEAP_FUNCTOR_COMPARE str_cmp 112 #include "binary_heap.h" 113 114 static void 115 test_struct(void) 116 { 117 struct mem_allocator allocator_proxy; 118 struct bheap_str heap; 119 struct str str; 120 size_t i; 121 const char* strs[] = { 122 "Rcvfbqr", "1,", "XARR-QRRC", "VA", "GUR", "QRNQ:\n", 123 "---------------------------------", "BAPR", "LBH", "ORNG", "GUR", "OVT", 124 "ONQNFFRF", "NAQ", "PYRNA", "BHG", "GUR", "ZBBA", "ONFR", "LBH'ER", 125 "FHCCBFRQ", "GB\n", "JVA", "NERA'G", "LBH?", "NERA'G", "LBH?", "JURER'F", 126 "LBHE", "SNG", "ERJNEQ", "NAQ", "GVPXRG", "UBZR?", "JUNG\n", "GUR", "URYY", 127 "VF", "GUVF?", "VG'F", "ABG", "FHCCBFRQ", "GB", "RAQ", "GUVF", "JNL!", "VG", 128 "FGVAXF", "YVXR", "EBGGRA", "ZRNG,", "OHG", "YBBXF", "YVXR", "GUR", "YBFG", 129 "QRVZBF", "ONFR.", "YBBXF", "YVXR\n", "LBH'ER", "FGHPX", "BA", "GUR", 130 "FUBERF", "BS", "URYY.", "GUR", "BAYL", "JNL", "BHG", "VF", "GUEBHTU.", "GB", 131 "PBAGVAHR", "GUR", "QBBZ", "RKCREVRAPR,", "CYNL", "GUR", "FUBERF", "BS", 132 "URYY", "NAQ", "VGF", "NZNMVAT\n", "FRDHRY,", "VASREAB!", 133 134 "Rcvfbqr 2, GUR FUBERF BS URYY:\n\ 135 ------------------------------\n\ 136 \n\ 137 LBH'IR QBAR VG! GUR UVQRBHF PLORE- QRZBA YBEQ GUNG EHYRQ GUR YBFG QRVZBF ZBBA\n\ 138 ONFR UNF ORRA FYNVA NAQ LBH NER GEVHZCUNAG! OHG ... JURER NER LBH? LBH\n\ 139 PYNZORE GB GUR RQTR BS GUR ZBBA NAQ YBBX QBJA GB FRR GUR NJSHY GEHGU.\n\ 140 \n", 141 142 "QRVZBF SYBNGF NOBIR URYY VGFRYS! LBH'IR ARIRE URNEQ BS NALBAR RFPNCVAT SEBZ\n\ 143 URYY, OHG LBH'YY ZNXR GUR ONFGNEQF FBEEL GURL RIRE URNEQ BS LBH! DHVPXYL, LBH\n\ 144 ENCCRY QBJA GB GUR FHESNPR BS URYY.\n\ 145 \n\ 146 ABJ, VG'F BA GB GUR SVANY PUNCGRE BS QBBZ! -- VASREAB." 147 }; 148 const size_t nstrs = sizeof(strs)/sizeof(const char*); 149 150 mem_init_proxy_allocator(&allocator_proxy, &mem_default_allocator); 151 str_init(&allocator_proxy, &str); 152 153 bheap_str_init(&allocator_proxy, &heap); 154 FOR_EACH(i, 0, nstrs) { 155 str_set(&str, strs[i]); 156 bheap_str_insert(&heap, &str); 157 } 158 159 CHK(bheap_str_pop(&heap, &str) != 0); 160 while(bheap_str_is_empty(&heap)) { 161 struct str str2; 162 str_init(&allocator_proxy, &str2); 163 CHK(bheap_str_pop(&heap, &str2) != 0); 164 CHK(strcmp(str_cget(&str), str_cget(&str2)) == -1); 165 str_set(&str, str_cget(&str2)); 166 str_release(&str2); 167 } 168 169 str_release(&str); 170 bheap_str_release(&heap); 171 172 check_memory_allocator(&allocator_proxy); 173 mem_shutdown_proxy_allocator(&allocator_proxy); 174 } 175 176 int 177 main(int argc, char** argv) 178 { 179 (void)argc, (void)argv; 180 test_primitive_type(); 181 test_struct(); 182 CHK(mem_allocated_size() == 0); 183 return 0; 184 }