test_fheap.c (4237B)
1 #include <stdlib.h> 2 #include <stdio.h> 3 #include <assert.h> 4 #include "fheap.h" 5 6 static void test_fnode_inits() { 7 // test fnode init and clear 8 fnode_t node; 9 uint64_t nodev = 12; 10 uint64_t noded = 15; 11 fnode_init(&node, nodev, &noded); 12 13 assert(node.children == NULL); 14 assert(node.parent == NULL); 15 assert(node.left == &node); 16 assert(node.right == &node); 17 assert(node.nchildren == 0); 18 assert(node.marked == 0); 19 20 assert(node.value == nodev); 21 assert(node.data == &noded); 22 } 23 24 static void test_fnode_clear() { 25 // test fnode init and clear 26 fnode_t *node = malloc(sizeof(*node)); 27 uint64_t nodev = 12; 28 uint64_t noded = 15; 29 fnode_init(node, nodev, &noded); 30 fnode_clear(node); 31 } 32 33 static void test_fnode_sort() { 34 // test to insert and then take out, in increasing order 35 uint64_t values[8] = {1, 5, 7, 0, 10, 3, 4, 11}; 36 uint64_t data[8] = {0, 1, 2, 3, 4, 5, 6, 7}; 37 size_t i; 38 uint64_t *tmp; 39 fheap_t heap; 40 41 fheap_init(&heap); 42 43 for(i = 0; i < 8; i++) { 44 fheap_insert(&heap, values[i], &data[i]); 45 } 46 47 assert(fheap_extract_min((void*) &tmp, &heap) == 0); 48 assert(*tmp == 3); 49 assert(fheap_extract_min((void*) &tmp, &heap) == 1); 50 assert(*tmp == 0); 51 assert(fheap_extract_min((void*) &tmp, &heap) == 3); 52 assert(*tmp == 5); 53 assert(fheap_extract_min((void*) &tmp, &heap) == 4); 54 assert(*tmp == 6); 55 assert(fheap_extract_min((void*) &tmp, &heap) == 5); 56 assert(*tmp == 1); 57 assert(fheap_extract_min((void*) &tmp, &heap) == 7); 58 assert(*tmp == 2); 59 assert(fheap_extract_min((void*) &tmp, &heap) == 10); 60 assert(*tmp == 4); 61 assert(fheap_extract_min((void*) &tmp, &heap) == 11); 62 assert(*tmp == 7); 63 64 // now the heap is empty 65 assert(fheap_extract_min((void*) &tmp, &heap) == UINT64_MAX); 66 assert(tmp == NULL); 67 } 68 69 static void test_fnode_with_decreases() { 70 uint64_t values[8] = {18, 5, 7, 16, 10, 3, 4, 11}; 71 uint64_t data[8] = {32, 1, 2, 11, 4, 5, 6, 7}; 72 size_t i; 73 uint64_t *tmp; 74 fheap_t heap; 75 76 fheap_init(&heap); 77 fnode_t *nodes[8]; 78 79 for(i = 0; i < 8; i++) { 80 nodes[i] = fheap_insert(&heap, values[i], &data[i]); 81 } 82 83 // decrease value of node[0] to 0, making it min 84 fheap_decrease_value(&heap, nodes[0], 0); 85 assert(heap.min == nodes[0]); 86 87 assert(fheap_extract_min((void*) &tmp, &heap) == 0); 88 assert(*tmp == 32); 89 90 // decrease value of node[7] to 8 making it come just 91 // after node[2] (with value 7) 92 fheap_decrease_value(&heap, nodes[7], 8); 93 94 assert(fheap_extract_min((void*) &tmp, &heap) == 3); 95 assert(*tmp == 5); 96 assert(fheap_extract_min((void*) &tmp, &heap) == 4); 97 assert(*tmp == 6); 98 assert(fheap_extract_min((void*) &tmp, &heap) == 5); 99 assert(*tmp == 1); 100 assert(fheap_extract_min((void*) &tmp, &heap) == 7); 101 assert(*tmp == 2); 102 assert(fheap_extract_min((void*) &tmp, &heap) == 8); 103 assert(*tmp == 7); 104 assert(fheap_extract_min((void*) &tmp, &heap) == 10); 105 assert(*tmp == 4); 106 assert(fheap_extract_min((void*) &tmp, &heap) == 16); 107 assert(*tmp == 11); 108 109 // now the heap is empty 110 assert(fheap_extract_min((void*) &tmp, &heap) == UINT64_MAX); 111 assert(tmp == NULL); 112 } 113 114 static void test_fnode_delete() { 115 uint64_t values[8] = {1, 5, 7, 0, 10, 3, 4, 11}; 116 uint64_t data[8] = {0, 1, 2, 3, 4, 5, 6, 7}; 117 size_t i; 118 uint64_t *tmp; 119 fheap_t heap; 120 fnode_t *nodes[8]; 121 122 fheap_init(&heap); 123 124 for(i = 0; i < 8; i++) { 125 nodes[i] = fheap_insert(&heap, values[i], &data[i]); 126 } 127 128 // delete node[2] and node[4] 129 fheap_delete(&heap, nodes[2]); 130 fheap_delete(&heap, nodes[4]); 131 132 assert(fheap_extract_min((void*) &tmp, &heap) == 0); 133 assert(*tmp == 3); 134 assert(fheap_extract_min((void*) &tmp, &heap) == 1); 135 assert(*tmp == 0); 136 assert(fheap_extract_min((void*) &tmp, &heap) == 3); 137 assert(*tmp == 5); 138 assert(fheap_extract_min((void*) &tmp, &heap) == 4); 139 assert(*tmp == 6); 140 assert(fheap_extract_min((void*) &tmp, &heap) == 5); 141 assert(*tmp == 1); 142 assert(fheap_extract_min((void*) &tmp, &heap) == 11); 143 assert(*tmp == 7); 144 145 // now the heap is empty 146 assert(fheap_extract_min((void*) &tmp, &heap) == UINT64_MAX); 147 assert(tmp == NULL); 148 } 149 150 151 int main() { 152 test_fnode_inits(); 153 test_fnode_clear(); 154 test_fnode_sort(); 155 test_fnode_with_decreases(); 156 test_fnode_delete(); 157 158 printf("tests ok\n"); 159 }