Fix GCC 4.3 warning about uninitialized structure member.
[pspp] / tests / libpspp / sparse-array-test.c
1 /* PSPP - a program for statistical analysis.
2    Copyright (C) 2007 Free Software Foundation, Inc.
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 3 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 this program.  If not, see <http://www.gnu.org/licenses/>. */
16
17 /* This is a test program for the sparse array routines defined
18    in sparse-array.c.  This test program aims to be as
19    comprehensive as possible.  "gcov -b" should report 100%
20    coverage of lines and branches in sparse-array.c when compiled
21    with -DNDEBUG.  "valgrind --leak-check=yes
22    --show-reachable=yes" should give a clean report. */
23
24 #ifdef HAVE_CONFIG_H
25 #include <config.h>
26 #endif
27
28 #include <libpspp/sparse-array.h>
29 #include <assert.h>
30 #include <limits.h>
31 #include <stdio.h>
32 #include <stdlib.h>
33 #include <string.h>
34 \f
35 /* Support preliminaries. */
36 #if __GNUC__ >= 2 && !defined UNUSED
37 #define UNUSED __attribute__ ((unused))
38 #else
39 #define UNUSED
40 #endif
41
42 /* Currently running test. */
43 static const char *test_name;
44
45 /* Exit with a failure code.
46    (Place a breakpoint on this function while debugging.) */
47 static void
48 check_die (void)
49 {
50   exit (EXIT_FAILURE);
51 }
52
53 /* If OK is not true, prints a message about failure on the
54    current source file and the given LINE and terminates. */
55 static void
56 check_func (bool ok, int line)
57 {
58   if (!ok)
59     {
60       printf ("%s:%d: Check failed in %s test\n",
61               __FILE__, line, test_name);
62       check_die ();
63     }
64 }
65
66 /* Verifies that EXPR evaluates to true.
67    If not, prints a message citing the calling line number and
68    terminates. */
69 #define check(EXPR) check_func ((EXPR), __LINE__)
70
71 /* Prints a message about memory exhaustion and exits with a
72    failure code. */
73 static void
74 xalloc_die (void)
75 {
76   printf ("virtual memory exhausted\n");
77   exit (EXIT_FAILURE);
78 }
79
80 /* Allocates and returns N bytes of memory. */
81 static void *
82 xmalloc (size_t n)
83 {
84   if (n != 0)
85     {
86       void *p = malloc (n);
87       if (p == NULL)
88         xalloc_die ();
89
90       return p;
91     }
92   else
93     return NULL;
94 }
95
96 /* Returns a malloc()'d duplicate of the N bytes starting at
97    P. */
98 static void *
99 xmemdup (const void *p, size_t n)
100 {
101   void *q = xmalloc (n);
102   memcpy (q, p, n);
103   return q;
104 }
105
106 /* Allocates and returns N * M bytes of memory. */
107 static void *
108 xnmalloc (size_t n, size_t m)
109 {
110   if ((size_t) -1 / m <= n)
111     xalloc_die ();
112   return xmalloc (n * m);
113 }
114 \f
115 /* Compares A and B and returns a strcmp-type return value. */
116 static int
117 compare_unsigned_longs_noaux (const void *a_, const void *b_)
118 {
119   const unsigned long *a = a_;
120   const unsigned long *b = b_;
121
122   return *a < *b ? -1 : *a > *b;
123 }
124
125 /* Checks that SPAR contains the CNT ints in DATA, that its
126    structure is correct, and that certain operations on SPAR
127    produce the expected results. */
128 static void
129 check_sparse_array (struct sparse_array *spar,
130                     const unsigned long data[], size_t cnt)
131 {
132   unsigned long idx;
133   unsigned long *order;
134   unsigned long *p;
135   size_t i;
136
137   check (sparse_array_count (spar) == cnt);
138
139   for (i = 0; i < cnt; i++)
140     {
141       p = sparse_array_get (spar, data[i]);
142       check (p != NULL);
143       check (*p == data[i]);
144     }
145
146   order = xmemdup (data, cnt * sizeof *data);
147   qsort (order, cnt, sizeof *order, compare_unsigned_longs_noaux);
148
149   for (i = 0; i < cnt; i++)
150     {
151       p = sparse_array_get (spar, order[i]);
152       check (p != NULL);
153       check (*p == order[i]);
154     }
155
156   if (cnt > 0 && order[0] - 1 != order[cnt - 1])
157     {
158       check (sparse_array_get (spar, order[0] - 1) == NULL);
159       check (!sparse_array_remove (spar, order[0] - 1));
160     }
161   if (cnt > 0 && order[0] != order[cnt - 1] + 1)
162     {
163       check (sparse_array_get (spar, order[cnt - 1] + 1) == NULL);
164       check (!sparse_array_remove (spar, order[cnt - 1] + 1));
165     }
166
167   for (i = 0, p = sparse_array_scan (spar, NULL, &idx); i < cnt;
168        i++, p = sparse_array_scan (spar, &idx, &idx))
169     {
170       check (p != NULL);
171       check (idx == order[i]);
172       check (*p == order[i]);
173     }
174   check (p == NULL);
175
176   free (order);
177 }
178
179 /* Inserts the CNT values from 0 to CNT - 1 (inclusive) into a
180    sparse array in the order specified by INSERTIONS, then
181    deletes them in the order specified by DELETIONS, checking the
182    array's contents for correctness after each operation. */
183 static void
184 test_insert_delete (const unsigned long insertions[],
185                     const unsigned long deletions[],
186                     size_t cnt)
187 {
188   struct sparse_array *spar;
189   size_t i;
190
191   spar = sparse_array_create (sizeof *insertions);
192   for (i = 0; i < cnt; i++)
193     {
194       unsigned long *p = sparse_array_insert (spar, insertions[i]);
195       *p = insertions[i];
196       check_sparse_array (spar, insertions, i + 1);
197     }
198   for (i = 0; i < cnt; i++)
199     {
200       bool deleted = sparse_array_remove (spar, deletions[i]);
201       check (deleted);
202       check_sparse_array (spar, deletions + i + 1, cnt - (i + 1));
203     }
204   check_sparse_array (spar, NULL, 0);
205   sparse_array_destroy (spar);
206 }
207
208 /* Inserts the CNT values from 0 to CNT - 1 (inclusive) into a
209    sparse array in the order specified by INSERTIONS, then
210    destroys the sparse array, to check that sparse_cases_destroy
211    properly frees all the nodes. */
212 static void
213 test_destroy (const unsigned long insertions[], size_t cnt)
214 {
215   struct sparse_array *spar;
216   size_t i;
217
218   spar = sparse_array_create (sizeof *insertions);
219   for (i = 0; i < cnt; i++)
220     {
221       unsigned long *p = sparse_array_insert (spar, insertions[i]);
222       *p = insertions[i];
223       check_sparse_array (spar, insertions, i + 1);
224     }
225   sparse_array_destroy (spar);
226 }
227
228 /* Randomly shuffles the CNT elements in ARRAY, each of which is
229    SIZE bytes in size. */
230 static void
231 random_shuffle (void *array_, size_t cnt, size_t size)
232 {
233   char *array = array_;
234   char *tmp = xmalloc (size);
235   size_t i;
236
237   for (i = 0; i < cnt; i++)
238     {
239       size_t j = rand () % (cnt - i) + i;
240       if (i != j)
241         {
242           memcpy (tmp, array + j * size, size);
243           memcpy (array + j * size, array + i * size, size);
244           memcpy (array + i * size, tmp, size);
245         }
246     }
247
248   free (tmp);
249 }
250 \f
251 /* Tests inserting and deleting elements whose values are
252    determined by starting from various offsets and skipping
253    across various strides, and doing so in various orders. */
254 static void
255 test_insert_delete_strides (void)
256 {
257   static const unsigned long strides[] =
258     {
259       1, 2, 4, 16, 64, 4096, 262144, 16777216,
260       3, 5, 17, 67, 4099, 262147, 16777259,
261     };
262   const size_t stride_cnt = sizeof strides / sizeof *strides;
263
264   static const unsigned long offsets[] =
265     {
266       0,
267       1024ul * 1024 + 1,
268       1024ul * 1024 * 512 + 23,
269       ULONG_MAX - 59,
270     };
271   const size_t offset_cnt = sizeof offsets / sizeof *offsets;
272
273   int cnt = 100;
274   unsigned long *insertions, *deletions;
275   const unsigned long *stride, *offset;
276
277   insertions = xnmalloc (cnt, sizeof *insertions);
278   deletions = xnmalloc (cnt, sizeof *deletions);
279   for (stride = strides; stride < strides + stride_cnt; stride++)
280     {
281       for (offset = offsets; offset < offsets + offset_cnt; offset++)
282         {
283           int k;
284
285           for (k = 0; k < cnt; k++)
286             insertions[k] = *stride * k + *offset;
287
288           test_insert_delete (insertions, insertions, cnt);
289           test_destroy (insertions, cnt);
290
291           for (k = 0; k < cnt; k++)
292             deletions[k] = insertions[cnt - k - 1];
293           test_insert_delete (insertions, deletions, cnt);
294
295           random_shuffle (insertions, cnt, sizeof *insertions);
296           test_insert_delete (insertions, insertions, cnt);
297           test_insert_delete (insertions, deletions, cnt);
298         }
299       putchar ('.');
300       fflush (stdout);
301     }
302   free (insertions);
303   free (deletions);
304 }
305
306 /* Returns the index in ARRAY of the (CNT+1)th element that has
307    the TARGET value. */
308 static int
309 scan_bools (bool target, bool array[], size_t cnt)
310 {
311   size_t i;
312
313   for (i = 0; ; i++)
314     if (array[i] == target && cnt-- == 0)
315       return i;
316 }
317
318 /* Performs a random sequence of insertions and deletions in a
319    sparse array. */
320 static void
321 test_random_insert_delete (void)
322 {
323   unsigned long int values[] =
324     {
325       0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096,
326       8192, 16384, 32768, 65536, 131072, 262144, 4194304, 8388608,
327       16777216, 33554432, 67108864, 134217728, 268435456, 536870912,
328       1073741824, 2147483648,
329
330       3, 7, 15, 31, 63, 127, 257, 511, 1023, 2047, 4095,
331       8191, 16383, 32767, 65535, 131071, 262143, 4194303, 8388607,
332       16777215, 33554431, 67108863, 134217727, 268435455, 536870911,
333       1073741823, 2147483647, 4294967295,
334     };
335   const int max_values = sizeof values / sizeof *values;
336
337   const int num_actions = 250000;
338   struct sparse_array *spar;
339   bool *has_values;
340   int cnt;
341   int insert_chance;
342   int i;
343
344   has_values = xnmalloc (max_values, sizeof *has_values);
345   memset (has_values, 0, max_values * sizeof *has_values);
346
347   cnt = 0;
348   insert_chance = 5;
349
350   spar = sparse_array_create (sizeof *values);
351   for (i = 0; i < num_actions; i++)
352     {
353       enum { INSERT, DELETE } action;
354       unsigned long *p;
355       int j;
356
357       if (cnt == 0)
358         {
359           action = INSERT;
360           if (insert_chance < 9)
361             insert_chance++;
362         }
363       else if (cnt == max_values)
364         {
365           action = DELETE;
366           if (insert_chance > 0)
367             insert_chance--;
368         }
369       else
370         action = rand () % 10 < insert_chance ? INSERT : DELETE;
371
372       if (action == INSERT)
373         {
374           int ins_index;
375
376           ins_index = scan_bools (false, has_values,
377                                   rand () % (max_values - cnt));
378           assert (has_values[ins_index] == false);
379           has_values[ins_index] = true;
380
381           p = sparse_array_insert (spar, values[ins_index]);
382           check (p != NULL);
383           *p = values[ins_index];
384
385           cnt++;
386         }
387       else if (action == DELETE)
388         {
389           int del_index;
390
391           del_index = scan_bools (true, has_values, rand () % cnt);
392           assert (has_values[del_index] == true);
393           has_values[del_index] = false;
394
395           check (sparse_array_remove (spar, values[del_index]));
396           cnt--;
397         }
398       else
399         abort ();
400
401       check (sparse_array_count (spar) == cnt);
402       for (j = 0; j < max_values; j++)
403         {
404           p = sparse_array_get (spar, values[j]);
405           if (has_values[j])
406             {
407               check (p != NULL);
408               check (*p == values[j]);
409             }
410           else
411             {
412               check (p == NULL);
413               if (rand () % 10 == 0)
414                 sparse_array_remove (spar, values[j]);
415             }
416         }
417     }
418   sparse_array_destroy (spar);
419   free (has_values);
420 }
421
422 /* Main program. */
423
424 /* Runs TEST_FUNCTION and prints a message about NAME. */
425 static void
426 run_test (void (*test_function) (void), const char *name)
427 {
428   test_name = name;
429   putchar ('.');
430   fflush (stdout);
431   test_function ();
432 }
433
434 int
435 main (void)
436 {
437   run_test (test_random_insert_delete,
438             "random insertions and deletions");
439   run_test (test_insert_delete_strides,
440             "insert in ascending order with strides and offset");
441   putchar ('\n');
442
443   return 0;
444 }