src/math/sort.c

   1 /* PSPP - computes sample statistics.
   2    Copyright (C) 1997-9, 2000 Free Software Foundation, Inc.
   3    Written by Ben Pfaff <blp@gnu.org>.
   4
   5    This program is free software; you can redistribute it and/or
   6    modify it under the terms of the GNU General Public License as
   7    published by the Free Software Foundation; either version 2 of the
   8    License, or (at your option) any later version.
   9
  10    This program is distributed in the hope that it will be useful, but
  11    WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13    General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program; if not, write to the Free Software
  17    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  18    02110-1301, USA. */
  19
  20 #include <config.h>
  21
  22 #include "sort.h"
  23
  24 #include <errno.h>
  25 #include <limits.h>
  26 #include <stdbool.h>
  27 #include <stdio.h>
  28 #include <stdlib.h>
  29
  30 #include <data/case-source.h>
  31 #include <data/case.h>
  32 #include <data/casefile.h>
  33 #include <data/fastfile.h>
  34 #include <data/procedure.h>
  35 #include <data/settings.h>
  36 #include <data/variable.h>
  37 #include <data/storage-stream.h>
  38 #include <language/expressions/public.h>
  39 #include <libpspp/alloc.h>
  40 #include <libpspp/array.h>
  41 #include <libpspp/assertion.h>
  42 #include <libpspp/message.h>
  43 #include <libpspp/message.h>
  44 #include <libpspp/misc.h>
  45 #include <libpspp/str.h>
  46
  47 #include "minmax.h"
  48
  49 #include "gettext.h"
  50 #define _(msgid) gettext (msgid)
  51
  52 /* These should only be changed for testing purposes. */
  53 int min_buffers = 64;
  54 int max_buffers = INT_MAX;
  55 bool allow_internal_sort = true;
  56
  57 static int compare_record (const struct ccase *, const struct ccase *,
  58                            const struct sort_criteria *);
  59 static struct casefile *do_internal_sort (struct casereader *,
  60                                           const struct sort_criteria *);
  61 static struct casefile *do_external_sort (struct casereader *,
  62                                           const struct sort_criteria *);
  63
  64
  65 /* Sorts the active file in-place according to CRITERIA.
  66    Returns true if successful. */
  67 bool
  68 sort_active_file_in_place (struct dataset *ds,
  69                            const struct sort_criteria *criteria)
  70 {
  71   struct casefile *in, *out;
  72
  73   proc_cancel_temporary_transformations (ds);
  74   if (!procedure (ds, NULL, NULL))
  75     return false;
  76
  77   in = proc_capture_output (ds);
  78   out = sort_execute (casefile_get_destructive_reader (in), criteria);
  79   if (out == NULL)
  80     return false;
  81
  82   proc_set_source (ds, storage_source_create (out));
  83   return true;
  84 }
  85
  86 /* Data passed to sort_to_casefile_callback(). */
  87 struct sort_to_casefile_cb_data
  88   {
  89     const struct sort_criteria *criteria;
  90     struct casefile *output;
  91   };
  92
  93 /* Sorts casefile CF according to the criteria in CB_DATA. */
  94 static bool
  95 sort_to_casefile_callback (const struct casefile *cf, void *cb_data_)
  96 {
  97   struct sort_to_casefile_cb_data *cb_data = cb_data_;
  98   cb_data->output = sort_execute (casefile_get_reader (cf, NULL), cb_data->criteria);
  99   return cb_data->output != NULL;
 100 }
 101
 102 /* Sorts the active file to a separate casefile.  If successful,
 103    returns the sorted casefile.  Returns a null pointer on
 104    failure. */
 105 struct casefile *
 106 sort_active_file_to_casefile (struct dataset *ds,
 107                               const struct sort_criteria *criteria)
 108 {
 109   struct sort_to_casefile_cb_data cb_data;
 110
 111   proc_cancel_temporary_transformations (ds);
 112
 113   cb_data.criteria = criteria;
 114   cb_data.output = NULL;
 115   if (!multipass_procedure (ds, sort_to_casefile_callback, &cb_data))
 116     {
 117       casefile_destroy (cb_data.output);
 118       return NULL;
 119     }
 120   return cb_data.output;
 121 }
 122
 123
 124 /* Reads all the cases from READER, which is destroyed.  Sorts
 125    the cases according to CRITERIA.  Returns the sorted cases in
 126    a newly created casefile. */
 127 struct casefile *
 128 sort_execute (struct casereader *reader, const struct sort_criteria *criteria)
 129 {
 130   struct casefile *output = do_internal_sort (reader, criteria);
 131   if (output == NULL)
 132     output = do_external_sort (reader, criteria);
 133   casereader_destroy (reader);
 134   return output;
 135 }
 136 \f
 137 /* A case and its index. */
 138 struct indexed_case
 139   {
 140     struct ccase c;     /* Case. */
 141     unsigned long idx;  /* Index to allow for stable sorting. */
 142   };
 143
 144 static int compare_indexed_cases (const void *, const void *, const void *);
 145
 146 /* If the data is in memory, do an internal sort and return a new
 147    casefile for the data.  Otherwise, return a null pointer. */
 148 static struct casefile *
 149 do_internal_sort (struct casereader *reader,
 150                   const struct sort_criteria *criteria)
 151 {
 152   const struct casefile *src;
 153   struct casefile *dst;
 154   unsigned long case_cnt;
 155
 156   if (!allow_internal_sort)
 157     return NULL;
 158
 159   src = casereader_get_casefile (reader);
 160   if (casefile_get_case_cnt (src) > 1 && !casefile_in_core (src))
 161     return NULL;
 162
 163   case_cnt = casefile_get_case_cnt (src);
 164   dst = fastfile_create (casefile_get_value_cnt (src));
 165   if (case_cnt != 0)
 166     {
 167       struct indexed_case *cases = nmalloc (sizeof *cases, case_cnt);
 168       if (cases != NULL)
 169         {
 170           unsigned long i;
 171
 172           for (i = 0; i < case_cnt; i++)
 173             {
 174               bool ok = casereader_read_xfer (reader, &cases[i].c);
 175               if (!ok)
 176                 NOT_REACHED ();
 177               cases[i].idx = i;
 178             }
 179
 180           sort (cases, case_cnt, sizeof *cases, compare_indexed_cases,
 181                 (void *) criteria);
 182
 183           for (i = 0; i < case_cnt; i++)
 184             casefile_append_xfer (dst, &cases[i].c);
 185           if (casefile_error (dst))
 186             NOT_REACHED ();
 187
 188           free (cases);
 189         }
 190       else
 191         {
 192           /* Failure. */
 193           casefile_destroy (dst);
 194           dst = NULL;
 195         }
 196     }
 197
 198   return dst;
 199 }
 200
 201 /* Compares the variables specified by CRITERIA between the cases
 202    at A and B, with a "last resort" comparison for stability, and
 203    returns a strcmp()-type result. */
 204 static int
 205 compare_indexed_cases (const void *a_, const void *b_, const void *criteria_)
 206 {
 207   const struct sort_criteria *criteria = criteria_;
 208   const struct indexed_case *a = a_;
 209   const struct indexed_case *b = b_;
 210   int result = compare_record (&a->c, &b->c, criteria);
 211   if (result == 0)
 212     result = a->idx < b->idx ? -1 : a->idx > b->idx;
 213   return result;
 214 }
 215 \f
 216 /* External sort. */
 217
 218 /* Maximum order of merge (external sort only).  The maximum
 219    reasonable value is about 7.  Above that, it would be a good
 220    idea to use a heap in merge_once() to select the minimum. */
 221 #define MAX_MERGE_ORDER 7
 222
 223 /* Results of an external sort. */
 224 struct external_sort
 225   {
 226     const struct sort_criteria *criteria; /* Sort criteria. */
 227     size_t value_cnt;                 /* Size of data in `union value's. */
 228     struct casefile **runs;           /* Array of initial runs. */
 229     size_t run_cnt, run_cap;          /* Number of runs, allocated capacity. */
 230   };
 231
 232 /* Prototypes for helper functions. */
 233 static int write_runs (struct external_sort *, struct casereader *);
 234 static struct casefile *merge (struct external_sort *);
 235 static void destroy_external_sort (struct external_sort *);
 236
 237 /* Performs a stable external sort of the active file according
 238    to the specification in SCP.  Forms initial runs using a heap
 239    as a reservoir.  Merges the initial runs according to a
 240    pattern that assures stability. */
 241 static struct casefile *
 242 do_external_sort (struct casereader *reader,
 243                   const struct sort_criteria *criteria)
 244 {
 245   struct external_sort *xsrt;
 246
 247   if (!casefile_to_disk (casereader_get_casefile (reader)))
 248     return NULL;
 249
 250   xsrt = xmalloc (sizeof *xsrt);
 251   xsrt->criteria = criteria;
 252   xsrt->value_cnt = casefile_get_value_cnt (casereader_get_casefile (reader));
 253   xsrt->run_cap = 512;
 254   xsrt->run_cnt = 0;
 255   xsrt->runs = xnmalloc (xsrt->run_cap, sizeof *xsrt->runs);
 256   if (write_runs (xsrt, reader))
 257     {
 258       struct casefile *output = merge (xsrt);
 259       destroy_external_sort (xsrt);
 260       return output;
 261     }
 262   else
 263     {
 264       destroy_external_sort (xsrt);
 265       return NULL;
 266     }
 267 }
 268
 269 /* Destroys XSRT. */
 270 static void
 271 destroy_external_sort (struct external_sort *xsrt)
 272 {
 273   if (xsrt != NULL)
 274     {
 275       int i;
 276
 277       for (i = 0; i < xsrt->run_cnt; i++)
 278         casefile_destroy (xsrt->runs[i]);
 279       free (xsrt->runs);
 280       free (xsrt);
 281     }
 282 }
 283 \f
 284 /* Replacement selection. */
 285
 286 /* Pairs a record with a run number. */
 287 struct record_run
 288   {
 289     int run;                    /* Run number of case. */
 290     struct ccase record;        /* Case data. */
 291     size_t idx;                 /* Case number (for stability). */
 292   };
 293
 294 /* Represents a set of initial runs during an external sort. */
 295 struct initial_run_state
 296   {
 297     struct external_sort *xsrt;
 298
 299     /* Reservoir. */
 300     struct record_run *records; /* Records arranged as a heap. */
 301     size_t record_cnt;          /* Current number of records. */
 302     size_t record_cap;          /* Capacity for records. */
 303
 304     /* Run currently being output. */
 305     int run;                    /* Run number. */
 306     size_t case_cnt;            /* Number of cases so far. */
 307     struct casefile *casefile;  /* Output file. */
 308     struct ccase last_output;   /* Record last output. */
 309
 310     int okay;                   /* Zero if an error has been encountered. */
 311   };
 312
 313 static bool destroy_initial_run_state (struct initial_run_state *);
 314 static void process_case (struct initial_run_state *,
 315                           const struct ccase *, size_t);
 316 static int allocate_cases (struct initial_run_state *);
 317 static void output_record (struct initial_run_state *);
 318 static void start_run (struct initial_run_state *);
 319 static void end_run (struct initial_run_state *);
 320 static int compare_record_run (const struct record_run *,
 321                                const struct record_run *,
 322                                const struct initial_run_state *);
 323 static int compare_record_run_minheap (const void *, const void *,
 324                                        const void *);
 325
 326 /* Reads cases from READER and composes initial runs in XSRT. */
 327 static int
 328 write_runs (struct external_sort *xsrt, struct casereader *reader)
 329 {
 330   struct initial_run_state *irs;
 331   struct ccase c;
 332   size_t idx = 0;
 333   int success = 0;
 334
 335   /* Allocate memory for cases. */
 336   irs = xmalloc (sizeof *irs);
 337   irs->xsrt = xsrt;
 338   irs->records = NULL;
 339   irs->record_cnt = irs->record_cap = 0;
 340   irs->run = 0;
 341   irs->case_cnt = 0;
 342   irs->casefile = NULL;
 343   case_nullify (&irs->last_output);
 344   irs->okay = 1;
 345   if (!allocate_cases (irs))
 346     goto done;
 347
 348   /* Create initial runs. */
 349   start_run (irs);
 350   for (; irs->okay && casereader_read (reader, &c); case_destroy (&c))
 351     process_case (irs, &c, idx++);
 352   while (irs->okay && irs->record_cnt > 0)
 353     output_record (irs);
 354   end_run (irs);
 355
 356   success = irs->okay;
 357
 358  done:
 359   if (!destroy_initial_run_state (irs))
 360     success = false;
 361
 362   return success;
 363 }
 364
 365 /* Add a single case to an initial run. */
 366 static void
 367 process_case (struct initial_run_state *irs, const struct ccase *c,
 368               size_t idx)
 369 {
 370   struct record_run *rr;
 371
 372   /* Compose record_run for this run and add to heap. */
 373   assert (irs->record_cnt < irs->record_cap - 1);
 374   rr = irs->records + irs->record_cnt++;
 375   case_copy (&rr->record, 0, c, 0, irs->xsrt->value_cnt);
 376   rr->run = irs->run;
 377   rr->idx = idx;
 378   if (!case_is_null (&irs->last_output)
 379       && compare_record (c, &irs->last_output, irs->xsrt->criteria) < 0)
 380     rr->run = irs->run + 1;
 381   push_heap (irs->records, irs->record_cnt, sizeof *irs->records,
 382              compare_record_run_minheap, irs);
 383
 384   /* Output a record if the reservoir is full. */
 385   if (irs->record_cnt == irs->record_cap - 1 && irs->okay)
 386     output_record (irs);
 387 }
 388
 389 /* Destroys the initial run state represented by IRS.
 390    Returns true if successful, false if an I/O error occurred. */
 391 static bool
 392 destroy_initial_run_state (struct initial_run_state *irs)
 393 {
 394   int i;
 395   bool ok = true;
 396
 397   if (irs == NULL)
 398     return true;
 399
 400   for (i = 0; i < irs->record_cap; i++)
 401     case_destroy (&irs->records[i].record);
 402   free (irs->records);
 403
 404   if (irs->casefile != NULL)
 405     ok = casefile_sleep (irs->casefile);
 406
 407   free (irs);
 408   return ok;
 409 }
 410
 411 /* Allocates room for lots of cases as a buffer. */
 412 static int
 413 allocate_cases (struct initial_run_state *irs)
 414 {
 415   int approx_case_cost; /* Approximate memory cost of one case in bytes. */
 416   int max_cases;        /* Maximum number of cases to allocate. */
 417   int i;
 418
 419   /* Allocate as many cases as we can within the workspace
 420      limit. */
 421   approx_case_cost = (sizeof *irs->records
 422                       + irs->xsrt->value_cnt * sizeof (union value)
 423                       + 4 * sizeof (void *));
 424   max_cases = get_workspace() / approx_case_cost;
 425   if (max_cases > max_buffers)
 426     max_cases = max_buffers;
 427   irs->records = nmalloc (sizeof *irs->records, max_cases);
 428   if (irs->records != NULL)
 429     for (i = 0; i < max_cases; i++)
 430       if (!case_try_create (&irs->records[i].record, irs->xsrt->value_cnt))
 431         {
 432           max_cases = i;
 433           break;
 434         }
 435   irs->record_cap = max_cases;
 436
 437   /* Fail if we didn't allocate an acceptable number of cases. */
 438   if (irs->records == NULL || max_cases < min_buffers)
 439     {
 440       msg (SE, _("Out of memory.  Could not allocate room for minimum of %d "
 441                  "cases of %d bytes each.  (PSPP workspace is currently "
 442                  "restricted to a maximum of %d KB.)"),
 443            min_buffers, approx_case_cost, get_workspace() / 1024);
 444       return 0;
 445     }
 446   return 1;
 447 }
 448
 449 /* Compares the VAR_CNT variables in VARS[] between the `value's at
 450    A and B, and returns a strcmp()-type result. */
 451 static int
 452 compare_record (const struct ccase *a, const struct ccase *b,
 453                 const struct sort_criteria *criteria)
 454 {
 455   int i;
 456
 457   assert (a != NULL);
 458   assert (b != NULL);
 459
 460   for (i = 0; i < criteria->crit_cnt; i++)
 461     {
 462       const struct sort_criterion *c = &criteria->crits[i];
 463       int result;
 464
 465       if (c->width == 0)
 466         {
 467           double af = case_num (a, c->fv);
 468           double bf = case_num (b, c->fv);
 469
 470           result = af < bf ? -1 : af > bf;
 471         }
 472       else
 473         result = memcmp (case_str (a, c->fv), case_str (b, c->fv), c->width);
 474
 475       if (result != 0)
 476         return c->dir == SRT_ASCEND ? result : -result;
 477     }
 478
 479   return 0;
 480 }
 481
 482 /* Compares record-run tuples A and B on run number first, then
 483    on record, then on case index. */
 484 static int
 485 compare_record_run (const struct record_run *a,
 486                     const struct record_run *b,
 487                     const struct initial_run_state *irs)
 488 {
 489   int result = a->run < b->run ? -1 : a->run > b->run;
 490   if (result == 0)
 491     result = compare_record (&a->record, &b->record, irs->xsrt->criteria);
 492   if (result == 0)
 493     result = a->idx < b->idx ? -1 : a->idx > b->idx;
 494   return result;
 495 }
 496
 497 /* Compares record-run tuples A and B on run number first, then
 498    on the current record according to SCP, but in descending
 499    order. */
 500 static int
 501 compare_record_run_minheap (const void *a, const void *b, const void *irs)
 502 {
 503   return -compare_record_run (a, b, irs);
 504 }
 505
 506 /* Begins a new initial run, specifically its output file. */
 507 static void
 508 start_run (struct initial_run_state *irs)
 509 {
 510   irs->run++;
 511   irs->case_cnt = 0;
 512   irs->casefile = fastfile_create (irs->xsrt->value_cnt);
 513   casefile_to_disk (irs->casefile);
 514   case_nullify (&irs->last_output);
 515 }
 516
 517 /* Ends the current initial run.  */
 518 static void
 519 end_run (struct initial_run_state *irs)
 520 {
 521   struct external_sort *xsrt = irs->xsrt;
 522
 523   /* Record initial run. */
 524   if (irs->casefile != NULL)
 525     {
 526       casefile_sleep (irs->casefile);
 527       if (xsrt->run_cnt >= xsrt->run_cap)
 528         {
 529           xsrt->run_cap *= 2;
 530           xsrt->runs = xnrealloc (xsrt->runs,
 531                                   xsrt->run_cap, sizeof *xsrt->runs);
 532         }
 533       xsrt->runs[xsrt->run_cnt++] = irs->casefile;
 534       if (casefile_error (irs->casefile))
 535         irs->okay = false;
 536       irs->casefile = NULL;
 537     }
 538 }
 539
 540 /* Writes a record to the current initial run. */
 541 static void
 542 output_record (struct initial_run_state *irs)
 543 {
 544   struct record_run *record_run;
 545   struct ccase case_tmp;
 546
 547   /* Extract minimum case from heap. */
 548   assert (irs->record_cnt > 0);
 549   pop_heap (irs->records, irs->record_cnt--, sizeof *irs->records,
 550             compare_record_run_minheap, irs);
 551   record_run = irs->records + irs->record_cnt;
 552
 553   /* Bail if an error has occurred. */
 554   if (!irs->okay)
 555     return;
 556
 557   /* Start new run if necessary. */
 558   assert (record_run->run == irs->run
 559           || record_run->run == irs->run + 1);
 560   if (record_run->run != irs->run)
 561     {
 562       end_run (irs);
 563       start_run (irs);
 564     }
 565   assert (record_run->run == irs->run);
 566   irs->case_cnt++;
 567
 568   /* Write to disk. */
 569   if (irs->casefile != NULL)
 570     casefile_append (irs->casefile, &record_run->record);
 571
 572   /* This record becomes last_output. */
 573   irs->last_output = case_tmp = record_run->record;
 574   record_run->record = irs->records[irs->record_cap - 1].record;
 575   irs->records[irs->record_cap - 1].record = case_tmp;
 576 }
 577 \f
 578 /* Merging. */
 579
 580 static int choose_merge (struct casefile *runs[], int run_cnt, int order);
 581 static struct casefile *merge_once (struct external_sort *,
 582                                     struct casefile *[], size_t);
 583
 584 /* Repeatedly merges run until only one is left,
 585    and returns the final casefile.
 586    Returns a null pointer if an I/O error occurs. */
 587 static struct casefile *
 588 merge (struct external_sort *xsrt)
 589 {
 590   while (xsrt->run_cnt > 1)
 591     {
 592       int order = MIN (MAX_MERGE_ORDER, xsrt->run_cnt);
 593       int idx = choose_merge (xsrt->runs, xsrt->run_cnt, order);
 594       xsrt->runs[idx] = merge_once (xsrt, xsrt->runs + idx, order);
 595       remove_range (xsrt->runs, xsrt->run_cnt, sizeof *xsrt->runs,
 596                     idx + 1, order - 1);
 597       xsrt->run_cnt -= order - 1;
 598
 599       if (xsrt->runs[idx] == NULL)
 600         return NULL;
 601     }
 602   assert (xsrt->run_cnt == 1);
 603   xsrt->run_cnt = 0;
 604   return xsrt->runs[0];
 605 }
 606
 607 /* Chooses ORDER runs out of the RUN_CNT runs in RUNS to merge,
 608    and returns the index of the first one.
 609
 610    For stability, we must merge only consecutive runs.  For
 611    efficiency, we choose the shortest consecutive sequence of
 612    runs. */
 613 static int
 614 choose_merge (struct casefile *runs[], int run_cnt, int order)
 615 {
 616   int min_idx, min_sum;
 617   int cur_idx, cur_sum;
 618   int i;
 619
 620   /* Sum up the length of the first ORDER runs. */
 621   cur_sum = 0;
 622   for (i = 0; i < order; i++)
 623     cur_sum += casefile_get_case_cnt (runs[i]);
 624
 625   /* Find the shortest group of ORDER runs,
 626      using a running total for efficiency. */
 627   min_idx = 0;
 628   min_sum = cur_sum;
 629   for (cur_idx = 1; cur_idx + order <= run_cnt; cur_idx++)
 630     {
 631       cur_sum -= casefile_get_case_cnt (runs[cur_idx - 1]);
 632       cur_sum += casefile_get_case_cnt (runs[cur_idx + order - 1]);
 633       if (cur_sum < min_sum)
 634         {
 635           min_sum = cur_sum;
 636           min_idx = cur_idx;
 637         }
 638     }
 639
 640   return min_idx;
 641 }
 642
 643 /* Merges the RUN_CNT initial runs specified in INPUT_FILES into a
 644    new run, and returns the new run.
 645    Returns a null pointer if an I/O error occurs. */
 646 static struct casefile *
 647 merge_once (struct external_sort *xsrt,
 648             struct casefile **const input_files,
 649             size_t run_cnt)
 650 {
 651   struct run
 652     {
 653       struct casefile *file;
 654       struct casereader *reader;
 655       struct ccase ccase;
 656     }
 657   *runs;
 658
 659   struct casefile *output = NULL;
 660   int i;
 661
 662   /* Open input files. */
 663   runs = xnmalloc (run_cnt, sizeof *runs);
 664   for (i = 0; i < run_cnt; i++)
 665     {
 666       struct run *r = &runs[i];
 667       r->file = input_files[i];
 668       r->reader = casefile_get_destructive_reader (r->file);
 669       if (!casereader_read_xfer (r->reader, &r->ccase))
 670         {
 671           run_cnt--;
 672           i--;
 673         }
 674     }
 675
 676   /* Create output file. */
 677   output = fastfile_create (xsrt->value_cnt);
 678   casefile_to_disk (output);
 679
 680   /* Merge. */
 681   while (run_cnt > 0)
 682     {
 683       struct run *min_run, *run;
 684
 685       /* Find minimum. */
 686       min_run = runs;
 687       for (run = runs + 1; run < runs + run_cnt; run++)
 688         if (compare_record (&run->ccase, &min_run->ccase, xsrt->criteria) < 0)
 689           min_run = run;
 690
 691       /* Write minimum to output file. */
 692       casefile_append_xfer (output, &min_run->ccase);
 693
 694       /* Read another case from minimum run. */
 695       if (!casereader_read_xfer (min_run->reader, &min_run->ccase))
 696         {
 697           if (casefile_error (min_run->file) || casefile_error (output))
 698             goto error;
 699           casereader_destroy (min_run->reader);
 700           casefile_destroy (min_run->file);
 701
 702           remove_element (runs, run_cnt, sizeof *runs, min_run - runs);
 703           run_cnt--;
 704         }
 705     }
 706
 707   if (!casefile_sleep (output))
 708     goto error;
 709   free (runs);
 710
 711   return output;
 712
 713  error:
 714   for (i = 0; i < run_cnt; i++)
 715     casefile_destroy (runs[i].file);
 716   casefile_destroy (output);
 717   free (runs);
 718   return NULL;
 719 }