X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Fmath%2Fsort.c;h=d3e4446d075bc8be8a92cd003c62649e83b021f6;hb=687adf53eae434e88a47bb3409f946f3a26115a4;hp=01e955334c9480cccc47f385519367d490e41d5e;hpb=321aff454c80b141d1d85fc1e3ea0c4eb05ab437;p=pspp-builds.git diff --git a/src/math/sort.c b/src/math/sort.c index 01e95533..d3e4446d 100644 --- a/src/math/sort.c +++ b/src/math/sort.c @@ -1,6 +1,5 @@ /* PSPP - computes sample statistics. - Copyright (C) 1997-9, 2000 Free Software Foundation, Inc. - Written by Ben Pfaff . + Copyright (C) 1997-9, 2000, 2006 Free Software Foundation, Inc. This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as @@ -30,18 +29,23 @@ #include #include #include +#include +#include +#include #include #include #include #include -#include #include #include +#include #include #include #include #include +#include "minmax.h" + #include "gettext.h" #define _(msgid) gettext (msgid) @@ -53,35 +57,35 @@ bool allow_internal_sort = true; static int compare_record (const struct ccase *, const struct ccase *, const struct sort_criteria *); static struct casefile *do_internal_sort (struct casereader *, - const struct sort_criteria *); + const struct sort_criteria *, + struct casefile_factory * + ); static struct casefile *do_external_sort (struct casereader *, - const struct sort_criteria *); + const struct sort_criteria *, + struct casefile_factory * + ); -/* Get ready to sort the active file. */ -static void -prepare_to_sort_active_file (void) -{ - proc_cancel_temporary_transformations (); -} /* Sorts the active file in-place according to CRITERIA. - Returns nonzero if successful. */ -int -sort_active_file_in_place (const struct sort_criteria *criteria) + Returns true if successful. */ +bool +sort_active_file_in_place (struct dataset *ds, + const struct sort_criteria *criteria) { struct casefile *in, *out; - prepare_to_sort_active_file (); - if (!procedure (NULL, NULL)) - return 0; + proc_cancel_temporary_transformations (ds); + if (!procedure (ds, NULL, NULL)) + return false; - in = proc_capture_output (); - out = sort_execute (casefile_get_destructive_reader (in), criteria); + in = proc_capture_output (ds); + out = sort_execute (casefile_get_destructive_reader (in), criteria, + dataset_get_casefile_factory (ds)); if (out == NULL) - return 0; + return false; - proc_set_source (storage_source_create (out)); - return 1; + proc_set_source (ds, storage_source_create (out)); + return true; } /* Data passed to sort_to_casefile_callback(). */ @@ -89,6 +93,7 @@ struct sort_to_casefile_cb_data { const struct sort_criteria *criteria; struct casefile *output; + struct casefile_factory *factory ; }; /* Sorts casefile CF according to the criteria in CB_DATA. */ @@ -96,7 +101,10 @@ static bool sort_to_casefile_callback (const struct casefile *cf, void *cb_data_) { struct sort_to_casefile_cb_data *cb_data = cb_data_; - cb_data->output = sort_execute (casefile_get_reader (cf), cb_data->criteria); + cb_data->output = sort_execute (casefile_get_reader (cf, NULL), + cb_data->criteria, + cb_data->factory + ); return cb_data->output != NULL; } @@ -104,15 +112,17 @@ sort_to_casefile_callback (const struct casefile *cf, void *cb_data_) returns the sorted casefile. Returns a null pointer on failure. */ struct casefile * -sort_active_file_to_casefile (const struct sort_criteria *criteria) +sort_active_file_to_casefile (struct dataset *ds, + const struct sort_criteria *criteria) { struct sort_to_casefile_cb_data cb_data; - prepare_to_sort_active_file (); + proc_cancel_temporary_transformations (ds); cb_data.criteria = criteria; cb_data.output = NULL; - if (!multipass_procedure (sort_to_casefile_callback, &cb_data)) + cb_data.factory = dataset_get_casefile_factory (ds); + if (!multipass_procedure (ds, sort_to_casefile_callback, &cb_data)) { casefile_destroy (cb_data.output); return NULL; @@ -123,14 +133,27 @@ sort_active_file_to_casefile (const struct sort_criteria *criteria) /* Reads all the cases from READER, which is destroyed. Sorts the cases according to CRITERIA. Returns the sorted cases in - a newly created casefile. */ + a newly created casefile, which will be created by FACTORY. + If FACTORY is NULL, then a local fastfile_factory will be used. +*/ struct casefile * -sort_execute (struct casereader *reader, const struct sort_criteria *criteria) +sort_execute (struct casereader *reader, + const struct sort_criteria *criteria, + struct casefile_factory *factory + ) { - struct casefile *output = do_internal_sort (reader, criteria); + struct casefile_factory *local_factory = NULL; + struct casefile *output ; + if ( factory == NULL ) + factory = local_factory = fastfile_factory_create (); + + output = do_internal_sort (reader, criteria, factory); if (output == NULL) - output = do_external_sort (reader, criteria); + output = do_external_sort (reader, criteria, factory); casereader_destroy (reader); + + fastfile_factory_destroy (local_factory); + return output; } @@ -141,13 +164,14 @@ struct indexed_case unsigned long idx; /* Index to allow for stable sorting. */ }; -static int compare_indexed_cases (const void *, const void *, void *); +static int compare_indexed_cases (const void *, const void *, const void *); /* If the data is in memory, do an internal sort and return a new casefile for the data. Otherwise, return a null pointer. */ static struct casefile * do_internal_sort (struct casereader *reader, - const struct sort_criteria *criteria) + const struct sort_criteria *criteria, + struct casefile_factory *factory) { const struct casefile *src; struct casefile *dst; @@ -161,7 +185,7 @@ do_internal_sort (struct casereader *reader, return NULL; case_cnt = casefile_get_case_cnt (src); - dst = casefile_create (casefile_get_value_cnt (src)); + dst = factory->create_casefile (factory, casefile_get_value_cnt (src)); if (case_cnt != 0) { struct indexed_case *cases = nmalloc (sizeof *cases, case_cnt); @@ -173,7 +197,7 @@ do_internal_sort (struct casereader *reader, { bool ok = casereader_read_xfer (reader, &cases[i].c); if (!ok) - abort (); + NOT_REACHED (); cases[i].idx = i; } @@ -183,7 +207,7 @@ do_internal_sort (struct casereader *reader, for (i = 0; i < case_cnt; i++) casefile_append_xfer (dst, &cases[i].c); if (casefile_error (dst)) - abort (); + NOT_REACHED (); free (cases); } @@ -202,9 +226,9 @@ do_internal_sort (struct casereader *reader, at A and B, with a "last resort" comparison for stability, and returns a strcmp()-type result. */ static int -compare_indexed_cases (const void *a_, const void *b_, void *criteria_) +compare_indexed_cases (const void *a_, const void *b_, const void *criteria_) { - struct sort_criteria *criteria = criteria_; + const struct sort_criteria *criteria = criteria_; const struct indexed_case *a = a_; const struct indexed_case *b = b_; int result = compare_record (&a->c, &b->c, criteria); @@ -227,6 +251,7 @@ struct external_sort size_t value_cnt; /* Size of data in `union value's. */ struct casefile **runs; /* Array of initial runs. */ size_t run_cnt, run_cap; /* Number of runs, allocated capacity. */ + struct casefile_factory *factory; /* Factory used to create the result */ }; /* Prototypes for helper functions. */ @@ -240,7 +265,9 @@ static void destroy_external_sort (struct external_sort *); pattern that assures stability. */ static struct casefile * do_external_sort (struct casereader *reader, - const struct sort_criteria *criteria) + const struct sort_criteria *criteria, + struct casefile_factory *factory + ) { struct external_sort *xsrt; @@ -253,6 +280,7 @@ do_external_sort (struct casereader *reader, xsrt->run_cap = 512; xsrt->run_cnt = 0; xsrt->runs = xnmalloc (xsrt->run_cap, sizeof *xsrt->runs); + xsrt->factory = factory; if (write_runs (xsrt, reader)) { struct casefile *output = merge (xsrt); @@ -311,16 +339,17 @@ struct initial_run_state }; static bool destroy_initial_run_state (struct initial_run_state *); -static void process_case (struct initial_run_state *, const struct ccase *, - size_t); +static void process_case (struct initial_run_state *, + const struct ccase *, size_t); static int allocate_cases (struct initial_run_state *); static void output_record (struct initial_run_state *); static void start_run (struct initial_run_state *); static void end_run (struct initial_run_state *); static int compare_record_run (const struct record_run *, const struct record_run *, - struct initial_run_state *); -static int compare_record_run_minheap (const void *, const void *, void *); + const struct initial_run_state *); +static int compare_record_run_minheap (const void *, const void *, + const void *); /* Reads cases from READER and composes initial runs in XSRT. */ static int @@ -363,7 +392,8 @@ write_runs (struct external_sort *xsrt, struct casereader *reader) /* Add a single case to an initial run. */ static void -process_case (struct initial_run_state *irs, const struct ccase *c, size_t idx) +process_case (struct initial_run_state *irs, const struct ccase *c, + size_t idx) { struct record_run *rr; @@ -462,13 +492,14 @@ compare_record (const struct ccase *a, const struct ccase *b, if (c->width == 0) { - double af = case_num (a, c->fv); - double bf = case_num (b, c->fv); + double af = case_num_idx (a, c->fv); + double bf = case_num_idx (b, c->fv); result = af < bf ? -1 : af > bf; } else - result = memcmp (case_str (a, c->fv), case_str (b, c->fv), c->width); + result = memcmp (case_str_idx (a, c->fv), + case_str_idx (b, c->fv), c->width); if (result != 0) return c->dir == SRT_ASCEND ? result : -result; @@ -482,7 +513,7 @@ compare_record (const struct ccase *a, const struct ccase *b, static int compare_record_run (const struct record_run *a, const struct record_run *b, - struct initial_run_state *irs) + const struct initial_run_state *irs) { int result = a->run < b->run ? -1 : a->run > b->run; if (result == 0) @@ -496,7 +527,7 @@ compare_record_run (const struct record_run *a, on the current record according to SCP, but in descending order. */ static int -compare_record_run_minheap (const void *a, const void *b, void *irs) +compare_record_run_minheap (const void *a, const void *b, const void *irs) { return -compare_record_run (a, b, irs); } @@ -507,7 +538,10 @@ start_run (struct initial_run_state *irs) { irs->run++; irs->case_cnt = 0; - irs->casefile = casefile_create (irs->xsrt->value_cnt); + + /* This casefile is internal to the sort, so don't use the factory + to create it. */ + irs->casefile = fastfile_create (irs->xsrt->value_cnt); casefile_to_disk (irs->casefile); case_nullify (&irs->last_output); } @@ -587,7 +621,7 @@ merge (struct external_sort *xsrt) { while (xsrt->run_cnt > 1) { - int order = min (MAX_MERGE_ORDER, xsrt->run_cnt); + int order = MIN (MAX_MERGE_ORDER, xsrt->run_cnt); int idx = choose_merge (xsrt->runs, xsrt->run_cnt, order); xsrt->runs[idx] = merge_once (xsrt, xsrt->runs + idx, order); remove_range (xsrt->runs, xsrt->run_cnt, sizeof *xsrt->runs, @@ -672,7 +706,7 @@ merge_once (struct external_sort *xsrt, } /* Create output file. */ - output = casefile_create (xsrt->value_cnt); + output = xsrt->factory->create_casefile (xsrt->factory, xsrt->value_cnt); casefile_to_disk (output); /* Merge. */