Crossfire Server, Trunk
check_minheap.cpp
Go to the documentation of this file.
1 /*
2  * This is the unit tests file for common/minheap.c
3  */
4 
5 #include <stdint.h>
6 
7 #include <global.h>
8 #include "minheap.h"
9 #include "compat.h"
10 #include "define.h"
11 
12 #include <check.h>
13 #include <stdlib.h>
14 #include <string.h>
15 
16 #include <toolkit_common.h>
17 
19 
20 static void setup(void) {
21  cctk_setlog(LOGDIR "/unit/common/minheap.out");
22 }
23 
24 static void teardown(void) {
25  // Clean up the minheap after every test.
26  if (test_heap != NULL)
28  test_heap = NULL;
29 }
30 
31 // Define functions that will be needed in order to retrieve values from the heap.
32 int int_measure(const void *ob) {
33  return *((const int *)ob);
34 }
35 
36 // We will also need this in order to qsort the results to ensure it works.
37 // This will tell qsort to sort in ascending order.
38 int qsort_comp_int(const void *a, const void *b) {
39  return *((const int *)a) - *((const int *)b);
40 }
41 
42 // Ensure that allocation works.
43 START_TEST(test_minheap_allocate) {
45  fail_unless(test_heap != NULL, "Failed to allocate minheap of size 1.");
46  fail_unless(test_heap->len == 0, "Initialized empty heap has nonzero length.");
47  fail_unless(test_heap->capacity == 1, "Initialized heap has capacity of %d, not 1.", test_heap->capacity);
48 }
49 END_TEST
50 
51 START_TEST(test_minheap_overfill) {
53  int vals[2] = {4, 3};
54  int result;
55  result = minheap_insert(test_heap, &vals[0]);
56  fail_unless(result == 0, "Minheap should have allowed 1 element, but allowed 0.");
57  result = minheap_insert(test_heap, &vals[1]);
58  fail_unless(result == -1, "Minheap of size 1 allowed 2 elements to be added.");
59 }
60 END_TEST
61 
62 START_TEST(test_minheap_empty_remove) {
64  int *result = static_cast<int *>(minheap_remove(test_heap));
65  fail_unless(result == NULL, "Empty heap should not return a non-null value on remove.");
66  int vals[3] = {1, 2, 3};
67  minheap_insert(test_heap, &vals[0]);
68  result = static_cast<int *>(minheap_remove(test_heap));
69  fail_unless(result == &vals[0], "Heap should have returned the only value it was given (%d)", vals[0]);
70  result = static_cast<int *>(minheap_remove(test_heap));
71  fail_unless(result == NULL, "Heap should be empty, yet we returned a value on removal (len=%d)", test_heap->len);
72  minheap_insert(test_heap, &vals[1]);
73  int insresult = minheap_insert(test_heap, &vals[2]);
74  fail_unless(insresult == -1, "Heap should have been full, but insert was allowed (len=%d)", test_heap->len);
75 }
76 END_TEST
77 
78 START_TEST(test_minheap_insert_remove) {
79  int vals[30] = {4, 6, 23, 7, 343, 12, 1, 1, 33, 76, 4, 34, 8, 7, 90, 123, 2, 3, 55, 65, 4, 6, 77, 65, 5, 7, 6, 5, 4, 1};
80  int expected[30], actual[30];
81  // Copy the values to the expected array and then qsort them.
82  memcpy(expected, vals, sizeof(int)*30);
83  qsort(expected, 30, sizeof(int), qsort_comp_int);
84 
85  // Initialize the minheap.
86  test_heap = minheap_init(30, int_measure, NULL);
87  for (int i = 0; i < 30; ++i) {
88  int result = minheap_insert(test_heap, &vals[i]);
89  fail_unless(result == 0, "Failed to insert to the heap for index %d (%d).", i, vals[i]);
90  }
91  // Now we pull off the heap, which incidentally sorts the values.
92  for (int i = 0; i < 30; ++i) {
93  int *result = static_cast<int *>(minheap_remove(test_heap));
94  fail_unless(result != NULL, "Failed to remove from the heap after %d elements.", i);
95  actual[i] = *result;
96  fail_unless(expected[i] == actual[i], "Heap did not gather data correctly. (%d != %d)", expected[i], actual[i]);
97  }
98 }
99 END_TEST
100 
101 // Now let's do a test that does a struct.
102 typedef struct {
103  int x;
104  int y;
105 } Pos;
106 
107 int measure_pos_distance(const void *ob) {
108  const Pos *p = static_cast<const Pos *>(ob);
109  const int diag = MIN(FABS(p->x), FABS(p->y));
110  const int rem = MAX(FABS(p->x), FABS(p->y)) - diag;
111  return diag * 3 + rem * 2;
112 }
113 
114 int qsort_pos_check(const void *a, const void *b) {
116 }
117 
118 START_TEST(test_minheap_with_struct) {
120  Pos vals[400], expected[400], actual[400];
121  srand(0);
122  // Initialize
123  for (int i = 0; i < 400; ++i) {
124  vals[i].x = rand() & 16535;
125  vals[i].y = rand() & 16535;
126  }
127  // Copy these over to expected, since we will qsort it there.
128  memcpy(expected, vals, 400 * sizeof(Pos));
129  qsort(expected, 400, sizeof(Pos), qsort_pos_check);
130 
131  // And then we will use the heap for sorting into actual
132  for (int i = 0; i < 400; ++i) {
133  int res = minheap_insert(test_heap, &vals[i]);
134  fail_unless(res == 0, "Could not insert into minheap at size %d.", test_heap->len);
135  }
136  // Then remove them from the heap.
137  for (int i = 0; i < 400; ++i) {
138  Pos *res = static_cast<Pos *>(minheap_remove(test_heap));
139  fail_unless(res != NULL, "Minheap emptied before it should have: %d items should be left.", 400-i);
140  actual[i] = *res;
141  // Since we sorted on the distance from (0,0), any ties could be in different orders.
142  fail_unless(measure_pos_distance(&expected[i]) == measure_pos_distance(&actual[i]),
143  "Minheap retrieved wrong value. Expected (%d, %d): %d, got (%d, %d): %d", expected[i].x, expected[i].y,
144  measure_pos_distance(&expected[i]), actual[i].x, actual[i].y, measure_pos_distance(&actual[i]));
145  }
146 }
147 END_TEST
148 
149 START_TEST(test_minheap_static_alloc) {
150 #define HEAP_SIZE 50
151  MinHeap heap;
152  int *heaparr[HEAP_SIZE];
153  minheap_init_static(&heap, (void **)heaparr, HEAP_SIZE, int_measure);
154 
155  // Now we get the data ready.
156  int vals[HEAP_SIZE], expected[HEAP_SIZE];
157  srand(5);
158  for (int i = 0; i < HEAP_SIZE; ++i) {
159  vals[i] = rand() & 32767;
160  }
161  // Copy to expected so we can qsort it.
162  memcpy(expected, vals, HEAP_SIZE * sizeof(int));
163  qsort(expected, HEAP_SIZE, sizeof(int), qsort_comp_int);
164 
165  // Push items onto the heap.
166  for (int i = 0; i < HEAP_SIZE; ++i) {
167  int res = minheap_insert(&heap, &vals[i]);
168  fail_unless(res == 0, "Could not insert into minheap at size %d.", heap.len);
169  }
170 
171  // Pull back off the heap
172  for (int i = 0; i < HEAP_SIZE; ++i) {
173  int *ref = static_cast<int *>(minheap_remove(&heap));
174  fail_unless(ref != NULL, "Minheap emptied before it should have: %d items should be left.", HEAP_SIZE - i);
175  fail_unless(*ref == expected[i], "Minheap retrieved wrong value. Expected %d, got %d.", expected[i], *ref);
176  }
177 }
178 END_TEST
179 
180 static Suite *minheap_suite(void) {
181  Suite *s = suite_create("minheap");
182  TCase *tc_core = tcase_create("Core");
183  tcase_set_timeout(tc_core, 60);
184 
185  /*setup and teardown will be called before each test in testcase 'tc_core' */
186  tcase_add_checked_fixture(tc_core, setup, teardown);
187 
188  suite_add_tcase(s, tc_core);
189  tcase_add_test(tc_core, test_minheap_allocate);
190  tcase_add_test(tc_core, test_minheap_overfill);
191  tcase_add_test(tc_core, test_minheap_empty_remove);
192  tcase_add_test(tc_core, test_minheap_insert_remove);
193  tcase_add_test(tc_core, test_minheap_with_struct);
194  tcase_add_test(tc_core, test_minheap_static_alloc);
195 
196  return s;
197 }
198 
199 int main(void) {
200  int nf;
201  Suite *s = minheap_suite();
202  SRunner *sr = srunner_create(s);
203 
204  /* to debug, uncomment this line */
205  /*srunner_set_fork_status(sr, CK_NOFORK);*/
206 
207  srunner_set_xml(sr, LOGDIR "/unit/common/minheap.xml");
208  srunner_set_log(sr, LOGDIR "/unit/common/minheap.out");
209  srunner_run_all(sr, CK_ENV); /*verbosity from env variable*/
210  nf = srunner_ntests_failed(sr);
211  srunner_free(sr);
212  return (nf == 0) ? EXIT_SUCCESS : EXIT_FAILURE;
213 }
MinHeap::capacity
int capacity
Definition: minheap.h:22
global.h
FABS
#define FABS(x)
Definition: define.h:22
setup
static void setup(void)
Definition: check_minheap.cpp:20
diamondslots.x
x
Definition: diamondslots.py:15
disinfect.a
a
Definition: disinfect.py:13
MinHeap
Definition: minheap.h:16
guildjoin.ob
ob
Definition: guildjoin.py:42
MIN
#define MIN(x, y)
Definition: compat.h:21
test_heap
static MinHeap * test_heap
Definition: check_minheap.cpp:18
MAX
#define MAX(x, y)
Definition: compat.h:24
measure_pos_distance
int measure_pos_distance(const void *ob)
Definition: check_minheap.cpp:107
minheap_free
void minheap_free(MinHeap *to_free)
Definition: minheap.cpp:226
toolkit_common.h
cctk_setlog
void cctk_setlog(const char *logfile)
Definition: toolkit_common.cpp:64
minheap.h
rotate-tower.result
bool result
Definition: rotate-tower.py:13
HEAP_SIZE
#define HEAP_SIZE
compat.h
minheap_init
MinHeap * minheap_init(int amt, int(*measure_func)(const void *), void(*cleanup_func)(void *))
Definition: minheap.cpp:129
Ice.b
b
Definition: Ice.py:48
MinHeap::len
int len
Definition: minheap.h:20
main
int main(void)
Definition: check_minheap.cpp:199
int_measure
int int_measure(const void *ob)
Definition: check_minheap.cpp:32
minheap_remove
void * minheap_remove(MinHeap *heap)
Definition: minheap.cpp:209
qsort_pos_check
int qsort_pos_check(const void *a, const void *b)
Definition: check_minheap.cpp:114
teardown
static void teardown(void)
Definition: check_minheap.cpp:24
define.h
qsort_comp_int
int qsort_comp_int(const void *a, const void *b)
Definition: check_minheap.cpp:38
minheap_suite
static END_TEST Suite * minheap_suite(void)
Definition: check_minheap.cpp:180
diamondslots.y
y
Definition: diamondslots.py:16
Pos::y
int y
Definition: check_minheap.cpp:104
Pos::x
int x
Definition: check_minheap.cpp:103
minheap_init_static
void minheap_init_static(MinHeap *heap, void **arr, int amt, int(*measure_func)(const void *))
Definition: minheap.cpp:162
START_TEST
START_TEST(test_minheap_allocate)
Definition: check_minheap.cpp:43
minheap_insert
int minheap_insert(MinHeap *heap, void *ob)
Definition: minheap.cpp:184
Pos
Definition: check_minheap.cpp:102
altar_valkyrie.res
int res
Definition: altar_valkyrie.py:74