- struct merge_state mrg; /* State of merge. */
- size_t approx_case_cost; /* Approximate memory cost of one case. */
- int max_order; /* Maximum order of merge. */
- size_t dummy_run_cnt; /* Number of dummy runs to insert. */
- int success = 0;
- int i;
-
- mrg.xsrt = xsrt;
-
- /* Allocate as many cases as possible into cases. */
- approx_case_cost = (sizeof *mrg.cases
- + xsrt->value_cnt * sizeof (union value)
- + 4 * sizeof (void *));
- mrg.case_cnt = get_max_workspace() / approx_case_cost;
- mrg.cases = malloc (sizeof *mrg.cases * mrg.case_cnt);
- if (mrg.cases == NULL)
- goto done;
- for (i = 0; i < mrg.case_cnt; i++)
- if (!case_try_create (&mrg.cases[i], xsrt->value_cnt))
- {
- mrg.case_cnt = i;
- break;
- }
- if (mrg.case_cnt < MIN_BUFFER_TOTAL_SIZE_RECS)
- {
- msg (SE, _("Out of memory. Could not allocate room for minimum of %d "
- "cases of %d bytes each. (PSPP workspace is currently "
- "restricted to a maximum of %d KB.)"),
- MIN_BUFFER_TOTAL_SIZE_RECS, approx_case_cost, get_max_workspace() / 1024);
- return 0;
- }
-
- /* Determine maximum order of merge. */
- max_order = MAX_MERGE_ORDER;
- if (mrg.case_cnt / max_order < MIN_BUFFER_SIZE_RECS)
- max_order = mrg.case_cnt / MIN_BUFFER_SIZE_RECS;
- else if (mrg.case_cnt / max_order * xsrt->value_cnt * sizeof (union value)
- < MIN_BUFFER_SIZE_BYTES)
- max_order = mrg.case_cnt / (MIN_BUFFER_SIZE_BYTES
- / (xsrt->value_cnt * sizeof (union value)));
- if (max_order < 2)
- max_order = 2;
- if (max_order > xsrt->run_cnt)
- max_order = xsrt->run_cnt;
-
- /* Repeatedly merge the P shortest existing runs until only one run
- is left. */
- make_heap (xsrt->initial_runs, xsrt->run_cnt, sizeof *xsrt->initial_runs,
- compare_initial_runs, NULL);
- dummy_run_cnt = mod (1 - (int) xsrt->run_cnt, max_order - 1);
-
- assert (max_order > 0);
- assert (max_order <= 2
- || (xsrt->run_cnt + dummy_run_cnt) % (max_order - 1) == 1);