Loading [MathJax]/extensions/TeX/AMSsymbols.js
LAL 7.7.0.1-5e288d3
•All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Modules Pages
LALHeapTest.c
Go to the documentation of this file.
1/*
2 * Copyright (C) 2016 Karl Wette
3 *
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2 of the License, or
7 * (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with with program; see the file COPYING. If not, write to the
16 * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
17 * MA 02110-1301 USA
18 */
19
20#include <stdlib.h>
21#include <gsl/gsl_rng.h>
22#include <lal/LALHeap.h>
23
24#ifdef __GNUC__
25#define UNUSED __attribute__ ((unused))
26#else
27#define UNUSED
28#endif
29
30static void *new_int( int x )
31{
32 return memcpy( XLALMalloc( sizeof( x ) ), &x, sizeof( x ) );
33}
34
35static int cmp_ptr_int( const void *x, const void *y )
36{
37 return *( ( const int * ) x ) - *( ( const int * ) y );
38}
39
40static int cmp_ptr_ptr_int( const void *x, const void *y )
41{
42 return cmp_ptr_int( *( ( const void *const * ) x ), *( ( const void *const * ) y ) );
43}
44
45static int print_ptr_int( UNUSED void *param, const void *x )
46{
47 printf( " %i", *( ( const int * ) x ) );
48 return XLAL_SUCCESS;
49}
50
51static int check_ptr_int( void *param, const void *x )
52{
53 int ***y = ( int ** * ) param;
54 return *( ( const int * ) x ) == **( ( *y )++ ) ? XLAL_SUCCESS : XLAL_FAILURE;
55}
56
57static int reverse_ptr_int( void *param, void *x )
58{
59 *( ( int * ) x ) = *( ( int * ) param ) - *( ( int * ) x );
60 return XLAL_SUCCESS;
61}
62
63int main( void )
64{
65
66 /* Turn off buffering to sync standard output and error printing */
67 setvbuf( stdout, NULL, _IONBF, 0 );
68 setvbuf( stderr, NULL, _IONBF, 0 );
69
70 /* Create heaps for storing integers */
71 LALHeap *minh = XLALHeapCreate( XLALFree, 0, -1, cmp_ptr_int );
72 XLAL_CHECK_MAIN( minh != NULL, XLAL_EFUNC );
73 XLAL_CHECK_MAIN( XLALHeapMaxSize( minh ) == 0, XLAL_EFAILED );
74 LALHeap *maxh = XLALHeapCreate( XLALFree, 0, +1, cmp_ptr_int );
75 XLAL_CHECK_MAIN( maxh != NULL, XLAL_EFUNC );
76 XLAL_CHECK_MAIN( XLALHeapMaxSize( minh ) == 0, XLAL_EFAILED );
77 LALHeap *min10h = XLALHeapCreate( XLALFree, 10, -1, cmp_ptr_int );
78 XLAL_CHECK_MAIN( min10h != NULL, XLAL_EFUNC );
79 XLAL_CHECK_MAIN( XLALHeapMaxSize( min10h ) == 10, XLAL_EFAILED );
80 LALHeap *max10h = XLALHeapCreate( XLALFree, 10, +1, cmp_ptr_int );
81 XLAL_CHECK_MAIN( max10h != NULL, XLAL_EFUNC );
82 XLAL_CHECK_MAIN( XLALHeapMaxSize( min10h ) == 10, XLAL_EFAILED );
83
84 /* Check some properties of empty heaps */
85 xlalErrno = 0;
86 XLAL_CHECK_MAIN( XLALHeapSize( minh ) == 0 && xlalErrno == 0, XLAL_EFAILED );
87 xlalErrno = 0;
88 XLAL_CHECK_MAIN( XLALHeapRoot( minh ) == NULL && xlalErrno == 0, XLAL_EFAILED );
89
90 /* Create an array of 100 random integers for input */
91 int input[100];
92 {
93 gsl_rng *r = gsl_rng_alloc( gsl_rng_mt19937 );
94 XLAL_CHECK_MAIN( r != NULL, XLAL_ESYS );
95 for ( size_t i = 0; i < 100; ++i ) {
96 input[i] = -37 + gsl_rng_uniform_int( r, 100 );
97 }
98 gsl_rng_free( r );
99 }
100
101 /* Add each integer to each heap, and to a sorted reference array */
102 int *ref[100];
103 for ( int i = 0; i < 100; ++i ) {
104 printf( "\n----- i=%i -----\n", i );
105
106 /* Add integer to reference array, and re-sort */
107 {
108 ref[i] = &input[i];
109 qsort( ref, i+1, sizeof( ref[0] ), cmp_ptr_ptr_int );
110 printf( "ref={" );
111 for ( int j = 0; j <= i; ++j ) {
112 printf( " %i", *ref[j] );
113 }
114 printf( " }\n" );
115 }
116
117 /* Add integer to unlimited min-heap, and check properties */
118 {
119 XLAL_CHECK_MAIN( XLALHeapIsFull( minh ) == 0, XLAL_EFAILED );
120 void *x = NULL;
121 x = new_int( input[i] );
122 XLAL_CHECK_MAIN( x != NULL, XLAL_ENOMEM );
123 XLAL_CHECK_MAIN( XLALHeapAdd( minh, &x ) == XLAL_SUCCESS, XLAL_EFUNC );
124 printf( "minh={" );
125 XLAL_CHECK_MAIN( XLALHeapVisit( minh, print_ptr_int, NULL ) == XLAL_SUCCESS, XLAL_EFUNC );
126 printf( " }" );
127 XLAL_CHECK_MAIN( x == NULL, XLAL_EFAILED );
128 XLAL_CHECK_MAIN( XLALHeapSize( minh ) == i+1, XLAL_EFAILED );
129 XLAL_CHECK_MAIN( XLALHeapRoot( minh ) != NULL, XLAL_EFAILED );
130 const int r = *( ( const int * ) XLALHeapRoot( minh ) );
131 const int r_ref = *ref[0];
132 XLAL_CHECK_MAIN( r == r_ref, XLAL_EFAILED, "(root) %i != %i (ref)", r, r_ref );
133 printf( ", root = %i\n", r );
134 {
135 int **ref0 = &ref[0];
136 XLAL_CHECK_MAIN( XLALHeapVisit( minh, check_ptr_int, &ref0 ) == XLAL_SUCCESS, XLAL_EFUNC );
137 }
138 }
139
140 /* Add integer to unlimited max-heap, and check properties */
141 {
142 XLAL_CHECK_MAIN( XLALHeapIsFull( maxh ) == 0, XLAL_EFAILED );
143 void *x = NULL;
144 x = new_int( input[i] );
145 XLAL_CHECK_MAIN( x != NULL, XLAL_ENOMEM );
146 XLAL_CHECK_MAIN( XLALHeapAdd( maxh, &x ) == XLAL_SUCCESS, XLAL_EFUNC );
147 printf( "maxh={" );
148 XLAL_CHECK_MAIN( XLALHeapVisit( maxh, print_ptr_int, NULL ) == XLAL_SUCCESS, XLAL_EFUNC );
149 printf( " }" );
150 XLAL_CHECK_MAIN( x == NULL, XLAL_EFAILED );
151 XLAL_CHECK_MAIN( XLALHeapSize( maxh ) == i+1, XLAL_EFAILED );
152 XLAL_CHECK_MAIN( XLALHeapRoot( maxh ) != NULL, XLAL_EFAILED );
153 const int r = *( ( const int * ) XLALHeapRoot( maxh ) );
154 const int r_ref = *ref[i];
155 XLAL_CHECK_MAIN( r == r_ref, XLAL_EFAILED, "(root) %i != %i (ref)", r, r_ref );
156 printf( ", root = %i\n", r );
157 {
158 int **ref0 = &ref[0];
159 XLAL_CHECK_MAIN( XLALHeapVisit( maxh, check_ptr_int, &ref0 ) == XLAL_SUCCESS, XLAL_EFUNC );
160 }
161 }
162
163 /* Add integer to limited min-heap, and check properties */
164 {
165 XLAL_CHECK_MAIN( XLALHeapIsFull( min10h ) == (i >= 10), XLAL_EFAILED );
166 void *x = new_int( input[i] );
167 XLAL_CHECK_MAIN( x != NULL, XLAL_ENOMEM );
168 XLAL_CHECK_MAIN( XLALHeapAdd( min10h, &x ) == XLAL_SUCCESS, XLAL_EFUNC );
169 printf( "min10h={" );
170 XLAL_CHECK_MAIN( XLALHeapVisit( min10h, print_ptr_int, NULL ) == XLAL_SUCCESS, XLAL_EFUNC );
171 printf( " }" );
172 if ( i < 10 ) {
173 XLAL_CHECK_MAIN( x == NULL, XLAL_EFAILED );
174 XLAL_CHECK_MAIN( XLALHeapSize( min10h ) == i+1, XLAL_EFAILED );
175 XLAL_CHECK_MAIN( XLALHeapRoot( min10h ) != NULL, XLAL_EFAILED );
176 } else {
177 XLAL_CHECK_MAIN( x != NULL, XLAL_EFAILED );
178 XLALFree( x );
179 XLAL_CHECK_MAIN( XLALHeapSize( min10h ) == 10, XLAL_EFAILED );
180 XLAL_CHECK_MAIN( XLALHeapRoot( min10h ) != NULL, XLAL_EFAILED );
181 }
182 const int r = *( ( const int * ) XLALHeapRoot( min10h ) );
183 const int r_ref = *ref[( i < 10 ) ? 0 : i-9];
184 XLAL_CHECK_MAIN( r == r_ref, XLAL_EFAILED, "(root) %i != %i (ref)", r, r_ref );
185 printf( ", root = %i\n", r );
186 {
187 int **ref0 = &ref[( i < 10 ) ? 0 : i-9];
188 XLAL_CHECK_MAIN( XLALHeapVisit( min10h, check_ptr_int, &ref0 ) == XLAL_SUCCESS, XLAL_EFUNC );
189 }
190 }
191
192 /* Add integer to limited max-heap, and check properties */
193 {
194 XLAL_CHECK_MAIN( XLALHeapIsFull( max10h ) == (i >= 10), XLAL_EFAILED );
195 void *x = new_int( input[i] );
196 XLAL_CHECK_MAIN( x != NULL, XLAL_ENOMEM );
197 XLAL_CHECK_MAIN( XLALHeapAdd( max10h, &x ) == XLAL_SUCCESS, XLAL_EFUNC );
198 printf( "max10h={" );
199 XLAL_CHECK_MAIN( XLALHeapVisit( max10h, print_ptr_int, NULL ) == XLAL_SUCCESS, XLAL_EFUNC );
200 printf( " }" );
201 if ( i < 10 ) {
202 XLAL_CHECK_MAIN( x == NULL, XLAL_EFAILED );
203 XLAL_CHECK_MAIN( XLALHeapSize( max10h ) == i+1, XLAL_EFAILED );
204 XLAL_CHECK_MAIN( XLALHeapRoot( max10h ) != NULL, XLAL_EFAILED );
205 } else {
206 XLAL_CHECK_MAIN( x != NULL, XLAL_EFAILED );
207 XLALFree( x );
208 XLAL_CHECK_MAIN( XLALHeapSize( max10h ) == 10, XLAL_EFAILED );
209 XLAL_CHECK_MAIN( XLALHeapRoot( max10h ) != NULL, XLAL_EFAILED );
210 }
211 const int r = *( ( const int * ) XLALHeapRoot( max10h ) );
212 const int r_ref = *ref[( i < 10 ) ? i : 9];
213 XLAL_CHECK_MAIN( r == r_ref, XLAL_EFAILED, "(root) %i != %i (ref)", r, r_ref );
214 printf( ", root = %i\n", r );
215 {
216 int **ref0 = &ref[0];
217 XLAL_CHECK_MAIN( XLALHeapVisit( max10h, check_ptr_int, &ref0 ) == XLAL_SUCCESS, XLAL_EFUNC );
218 }
219 }
220 }
221
222 /* Modify unlimited heaps, and check properties */
223 {
224 printf( "\n----- XLALHeapModify() -----\n" );
225 int param = 77;
226 {
227 for ( int j = 0; j < 100; ++j ) {
228 *ref[j] = param - *ref[j];
229 }
230 qsort( ref, 100, sizeof( ref[0] ), cmp_ptr_ptr_int );
231 printf( "ref={" );
232 for ( int j = 0; j < 100; ++j ) {
233 printf( " %i", *ref[j] );
234 }
235 printf( " }\n" );
236 }
237 {
238 XLAL_CHECK_MAIN( XLALHeapModify( minh, reverse_ptr_int, &param ) == XLAL_SUCCESS, XLAL_EFUNC );
239 printf( "minh={" );
240 XLAL_CHECK_MAIN( XLALHeapVisit( minh, print_ptr_int, NULL ) == XLAL_SUCCESS, XLAL_EFUNC );
241 printf( " }" );
242 const int r = *( ( const int * ) XLALHeapRoot( minh ) );
243 const int r_ref = *ref[0];
244 XLAL_CHECK_MAIN( r == r_ref, XLAL_EFAILED, "(root) %i != %i (ref)", r, r_ref );
245 printf( ", root = %i\n", r );
246 {
247 int **ref0 = &ref[0];
248 XLAL_CHECK_MAIN( XLALHeapVisit( minh, check_ptr_int, &ref0 ) == XLAL_SUCCESS, XLAL_EFUNC );
249 }
250 }
251 {
252 XLAL_CHECK_MAIN( XLALHeapModify( maxh, reverse_ptr_int, &param ) == XLAL_SUCCESS, XLAL_EFUNC );
253 printf( "maxh={" );
254 XLAL_CHECK_MAIN( XLALHeapVisit( maxh, print_ptr_int, NULL ) == XLAL_SUCCESS, XLAL_EFUNC );
255 printf( " }" );
256 const int r = *( ( const int * ) XLALHeapRoot( maxh ) );
257 const int r_ref = *ref[99];
258 XLAL_CHECK_MAIN( r == r_ref, XLAL_EFAILED, "(root) %i != %i (ref)", r, r_ref );
259 printf( ", root = %i\n", r );
260 {
261 int **ref0 = &ref[0];
262 XLAL_CHECK_MAIN( XLALHeapVisit( maxh, check_ptr_int, &ref0 ) == XLAL_SUCCESS, XLAL_EFUNC );
263 }
264 }
265 {
266 XLAL_CHECK_MAIN( XLALHeapModify( min10h, reverse_ptr_int, &param ) == XLAL_SUCCESS, XLAL_EFUNC );
267 printf( "min10h={" );
268 XLAL_CHECK_MAIN( XLALHeapVisit( min10h, print_ptr_int, NULL ) == XLAL_SUCCESS, XLAL_EFUNC );
269 printf( " }" );
270 const int r = *( ( const int * ) XLALHeapRoot( min10h ) );
271 const int r_ref = *ref[0];
272 XLAL_CHECK_MAIN( r == r_ref, XLAL_EFAILED, "(root) %i != %i (ref)", r, r_ref );
273 printf( ", root = %i\n", r );
274 {
275 int **ref0 = &ref[0];
276 XLAL_CHECK_MAIN( XLALHeapVisit( min10h, check_ptr_int, &ref0 ) == XLAL_SUCCESS, XLAL_EFUNC );
277 }
278 }
279 {
280 XLAL_CHECK_MAIN( XLALHeapModify( max10h, reverse_ptr_int, &param ) == XLAL_SUCCESS, XLAL_EFUNC );
281 printf( "max10h={" );
282 XLAL_CHECK_MAIN( XLALHeapVisit( max10h, print_ptr_int, NULL ) == XLAL_SUCCESS, XLAL_EFUNC );
283 printf( " }" );
284 const int r = *( ( const int * ) XLALHeapRoot( max10h ) );
285 const int r_ref = *ref[99];
286 XLAL_CHECK_MAIN( r == r_ref, XLAL_EFAILED, "(root) %i != %i (ref)", r, r_ref );
287 printf( ", root = %i\n", r );
288 {
289 int **ref0 = &ref[90];
290 XLAL_CHECK_MAIN( XLALHeapVisit( max10h, check_ptr_int, &ref0 ) == XLAL_SUCCESS, XLAL_EFUNC );
291 }
292 }
293 }
294
295 /* Resize unlimited heaps, and check properties */
296 {
297 printf( "\n----- XLALHeapResize() -----\n" );
298 {
299 XLAL_CHECK_MAIN( XLALHeapResize( minh, 20 ) == XLAL_SUCCESS, XLAL_EFUNC );
300 int **ref0 = &ref[80];
301 XLAL_CHECK_MAIN( XLALHeapVisit( minh, check_ptr_int, &ref0 ) == XLAL_SUCCESS, XLAL_EFUNC );
302 const int **elems = ( const int ** ) XLALHeapElements( minh );
303 for ( int j = 0; j < XLALHeapSize( minh ); ++j ) {
304 XLAL_CHECK_MAIN( *elems[j] == *ref[80 + j], XLAL_EFAILED, "(elems) %i != %i (ref)", *elems[j], *ref[80 + j] );
305 }
306 XLALFree( elems );
307 }
308 {
309 XLAL_CHECK_MAIN( XLALHeapResize( maxh, 33 ) == XLAL_SUCCESS, XLAL_EFUNC );
310 int **ref0 = &ref[0];
311 XLAL_CHECK_MAIN( XLALHeapVisit( maxh, check_ptr_int, &ref0 ) == XLAL_SUCCESS, XLAL_EFUNC );
312 const int **elems = ( const int ** ) XLALHeapElements( maxh );
313 for ( int j = 0; j < XLALHeapSize( maxh ); ++j ) {
314 XLAL_CHECK_MAIN( *elems[j] == *ref[j], XLAL_EFAILED, "(elems) %i != %i (ref)", *elems[j], *ref[j] );
315 }
316 XLALFree( elems );
317 }
318 }
319
320 /* Clear a heap */
321 XLAL_CHECK_MAIN( XLALHeapClear( minh ) == XLAL_SUCCESS, XLAL_EFUNC );
322 XLAL_CHECK_MAIN( XLALHeapSize( minh ) == 0, XLAL_EFAILED );
323
324 /* Cleanup */
325 {
326 printf( "\n----- cleanup -----\n" );
327 XLALHeapDestroy( minh );
328 XLALHeapDestroy( maxh );
329 XLALHeapDestroy( min10h );
330 XLALHeapDestroy( max10h );
331
332 /* Check for memory leaks */
333 LALCheckMemoryLeaks();
334
335 }
336
337 return EXIT_SUCCESS;
338
339}
reverse_ptr_int
static int reverse_ptr_int(void *param, void *x)
Definition: LALHeapTest.c:57
print_ptr_int
static int print_ptr_int(UNUSED void *param, const void *x)
Definition: LALHeapTest.c:45
main
int main(void)
Definition: LALHeapTest.c:63
cmp_ptr_int
static int cmp_ptr_int(const void *x, const void *y)
Definition: LALHeapTest.c:35
check_ptr_int
static int check_ptr_int(void *param, const void *x)
Definition: LALHeapTest.c:51
new_int
static void * new_int(int x)
Definition: LALHeapTest.c:30
cmp_ptr_ptr_int
static int cmp_ptr_ptr_int(const void *x, const void *y)
Definition: LALHeapTest.c:40
LALCheckMemoryLeaks
void LALCheckMemoryLeaks(void)
Definition: LALMalloc.c:784
XLALHeapResize
int XLALHeapResize(LALHeap *h, int max_size)
Change the maximum size of a heap; if the heap is contracted, excess elements are destroyed.
Definition: LALHeap.c:267
XLALHeapVisit
int XLALHeapVisit(const LALHeap *h, LALHeapVisitFcn visit, void *visit_param)
Visit each element in the heap in the order given by the comparison function.
Definition: LALHeap.c:374
XLALHeapAdd
int XLALHeapAdd(LALHeap *h, void **x)
Add a new element to a heap; if the heap is of fixed size and full, the root element is removed.
Definition: LALHeap.c:289
XLALHeapCreate
LALHeap * XLALHeapCreate(LALHeapDtorFcn dtor, int max_size, int min_or_max_heap, LALHeapCmpFcn cmp)
Create a heap.
Definition: LALHeap.c:146
XLALHeapModify
int XLALHeapModify(LALHeap *h, LALHeapModifyFcn modify, void *modify_param)
Visit (and possibly modify) each element in the heap in the order given by the comparison function.
Definition: LALHeap.c:409
XLALHeapSize
int XLALHeapSize(const LALHeap *h)
Return the size of a heap.
Definition: LALHeap.c:235
XLALHeapRoot
const void * XLALHeapRoot(const LALHeap *h)
Return the root element of a heap.
Definition: LALHeap.c:259
XLALHeapIsFull
int XLALHeapIsFull(const LALHeap *h)
Return >0 if a limited-size heap is full, 0 otherwise (or if heap has unlimited size),...
Definition: LALHeap.c:251
XLALHeapClear
int XLALHeapClear(LALHeap *h)
Clear a heap.
Definition: LALHeap.c:209
XLALHeapElements
const void ** XLALHeapElements(const LALHeap *h)
Allocate and return an array containing all elements in the heap.
Definition: LALHeap.c:465
XLALHeapDestroy
void XLALHeapDestroy(LALHeap *h)
Destroy a heap and its elements.
Definition: LALHeap.c:192
XLALHeapMaxSize
int XLALHeapMaxSize(const LALHeap *h)
Return the maximum size of a heap.
Definition: LALHeap.c:243
XLALMalloc
#define XLALMalloc(n)
Definition: LALMalloc.h:44
XLALFree
#define XLALFree(p)
Definition: LALMalloc.h:47
r
static const INT4 r
Definition: Random.c:82
xlalErrno
#define xlalErrno
Modifiable lvalue containing the XLAL error number.
Definition: XLALError.h:571
XLAL_CHECK_MAIN
#define XLAL_CHECK_MAIN(assertion,...)
Macro to test an assertion and invoke a failure if it is not true in a C main() routine.
Definition: XLALError.h:885
XLAL_ENOMEM
@ XLAL_ENOMEM
Memory allocation error.
Definition: XLALError.h:407
XLAL_SUCCESS
@ XLAL_SUCCESS
Success return value (not an error number)
Definition: XLALError.h:401
XLAL_EFUNC
@ XLAL_EFUNC
Internal function call failed bit: "or" this with existing error number.
Definition: XLALError.h:462
XLAL_ESYS
@ XLAL_ESYS
System error.
Definition: XLALError.h:442
XLAL_EFAILED
@ XLAL_EFAILED
Generic failure.
Definition: XLALError.h:418
XLAL_FAILURE
@ XLAL_FAILURE
Failure return value (not an error number)
Definition: XLALError.h:402
test_iterutils.x
x
Definition: test_iterutils.py:50