X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Fmath%2Fsort.c;h=13642e00ea7b8c0f84e71c2c8c54adec9ed111ad;hb=06ac0c2d623e9ae54c3e22a2d6740219ab357b21;hp=67aa32d29048fffbb5e7b3c03b371b8db9c88a62;hpb=9e0e4996fad6563f0a1ce628b80db5c23ef8279e;p=pspp diff --git a/src/math/sort.c b/src/math/sort.c index 67aa32d290..13642e00ea 100644 --- a/src/math/sort.c +++ b/src/math/sort.c @@ -1,5 +1,5 @@ /* PSPP - a program for statistical analysis. - Copyright (C) 1997-9, 2000, 2006, 2009 Free Software Foundation, Inc. + Copyright (C) 1997-9, 2000, 2006, 2009, 2011, 2012 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 published by @@ -16,24 +16,21 @@ #include -#include "sort.h" +#include "math/sort.h" #include -#include -#include -#include -#include -#include -#include -#include -#include -#include +#include "data/case.h" +#include "data/casereader.h" +#include "data/casewriter-provider.h" +#include "data/casewriter.h" +#include "data/settings.h" +#include "data/subcase.h" +#include "libpspp/array.h" +#include "libpspp/assertion.h" +#include "math/merge.h" -#include "xalloc.h" - -#include "gettext.h" -#define _(msgid) gettext (msgid) +#include "gl/xalloc.h" /* These should only be changed for testing purposes. */ int min_buffers = 64; @@ -41,7 +38,7 @@ int max_buffers = INT_MAX; struct sort_writer { - size_t value_cnt; + struct caseproto *proto; struct subcase ordering; struct merge *merge; struct pqueue *pqueue; @@ -53,7 +50,8 @@ struct sort_writer static struct casewriter_class sort_casewriter_class; -static struct pqueue *pqueue_create (const struct subcase *, size_t); +static struct pqueue *pqueue_create (const struct subcase *, + const struct caseproto *); static void pqueue_destroy (struct pqueue *); static bool pqueue_is_full (const struct pqueue *); static bool pqueue_is_empty (const struct pqueue *); @@ -62,21 +60,25 @@ static struct ccase *pqueue_pop (struct pqueue *, casenumber *); static void output_record (struct sort_writer *); +/* Creates a casewriter that sorts the cases written to it. Once all the cases + have been written, use casewriter_make_reader() to obtain the sorted + results. */ struct casewriter * -sort_create_writer (const struct subcase *ordering, size_t value_cnt) +sort_create_writer (const struct subcase *ordering, + const struct caseproto *proto) { struct sort_writer *sort; sort = xmalloc (sizeof *sort); - sort->value_cnt = value_cnt; + sort->proto = caseproto_ref (proto); subcase_clone (&sort->ordering, ordering); - sort->merge = merge_create (ordering, value_cnt); - sort->pqueue = pqueue_create (ordering, value_cnt); + sort->merge = merge_create (ordering, proto); + sort->pqueue = pqueue_create (ordering, proto); sort->run = NULL; sort->run_id = 0; sort->run_end = NULL; - return casewriter_create (value_cnt, &sort_casewriter_class, sort); + return casewriter_create (proto, &sort_casewriter_class, sort); } static void @@ -100,11 +102,12 @@ sort_casewriter_destroy (struct casewriter *writer UNUSED, void *sort_) { struct sort_writer *sort = sort_; - subcase_destroy (&sort->ordering); + subcase_uninit (&sort->ordering); merge_destroy (sort->merge); pqueue_destroy (sort->pqueue); casewriter_destroy (sort->run); case_unref (sort->run_end); + caseproto_unref (sort->proto); free (sort); } @@ -117,7 +120,7 @@ sort_casewriter_convert_to_reader (struct casewriter *writer, void *sort_) if (sort->run == NULL && sort->run_id == 0) { /* In-core sort. */ - sort->run = mem_writer_create (casewriter_get_value_cnt (writer)); + sort->run = mem_writer_create (sort->proto); sort->run_id = 1; } while (!pqueue_is_empty (sort->pqueue)) @@ -149,7 +152,7 @@ output_record (struct sort_writer *sort) } if (sort->run == NULL) { - sort->run = tmpfile_writer_create (sort->value_cnt); + sort->run = tmpfile_writer_create (sort->proto); sort->run_id = min_run_id; } @@ -166,19 +169,21 @@ static struct casewriter_class sort_casewriter_class = }; /* Reads all the cases from INPUT. Sorts the cases according to - ORDERING. Returns the sorted cases in a new casereader. */ + ORDERING. Returns the sorted cases in a new casereader. + INPUT is destroyed by this function. + */ struct casereader * sort_execute (struct casereader *input, const struct subcase *ordering) { struct casewriter *output = - sort_create_writer (ordering, casereader_get_value_cnt (input)); + sort_create_writer (ordering, casereader_get_proto (input)); casereader_transfer (input, output); return casewriter_make_reader (output); } /* Reads all the cases from INPUT. Sorts the cases in ascending order according to VARIABLE. Returns the sorted cases in a - new casereader. */ + new casereader. INPUT is destroyed by this function. */ struct casereader * sort_execute_1var (struct casereader *input, const struct variable *var) { @@ -187,7 +192,7 @@ sort_execute_1var (struct casereader *input, const struct variable *var) subcase_init_var (&sc, var, SC_ASCEND); reader = sort_execute (input, &sc); - subcase_destroy (&sc); + subcase_uninit (&sc); return reader; } @@ -195,8 +200,9 @@ struct pqueue { struct subcase ordering; struct pqueue_record *records; - size_t record_cnt; - size_t record_cap; + size_t n_records; /* Current number of records. */ + size_t allocated_records; /* Space currently allocated for records. */ + size_t max_records; /* Max space we are willing to allocate. */ casenumber idx; }; @@ -211,20 +217,20 @@ static int compare_pqueue_records_minheap (const void *a, const void *b, const void *pq_); static struct pqueue * -pqueue_create (const struct subcase *ordering, size_t value_cnt) +pqueue_create (const struct subcase *ordering, const struct caseproto *proto) { struct pqueue *pq; pq = xmalloc (sizeof *pq); subcase_clone (&pq->ordering, ordering); - pq->record_cap - = settings_get_workspace_cases (value_cnt); - if (pq->record_cap > max_buffers) - pq->record_cap = max_buffers; - else if (pq->record_cap < min_buffers) - pq->record_cap = min_buffers; - pq->record_cnt = 0; - pq->records = xnmalloc (pq->record_cap, sizeof *pq->records); + pq->max_records = settings_get_workspace_cases (proto); + if (pq->max_records > max_buffers) + pq->max_records = max_buffers; + else if (pq->max_records < min_buffers) + pq->max_records = min_buffers; + pq->n_records = 0; + pq->allocated_records = 0; + pq->records = NULL; pq->idx = 0; return pq; @@ -241,7 +247,7 @@ pqueue_destroy (struct pqueue *pq) struct ccase *c = pqueue_pop (pq, &id); case_unref (c); } - subcase_destroy (&pq->ordering); + subcase_uninit (&pq->ordering); free (pq->records); free (pq); } @@ -250,13 +256,13 @@ pqueue_destroy (struct pqueue *pq) static bool pqueue_is_full (const struct pqueue *pq) { - return pq->record_cnt >= pq->record_cap; + return pq->n_records >= pq->max_records; } static bool pqueue_is_empty (const struct pqueue *pq) { - return pq->record_cnt == 0; + return pq->n_records == 0; } static void @@ -266,12 +272,23 @@ pqueue_push (struct pqueue *pq, struct ccase *c, casenumber id) assert (!pqueue_is_full (pq)); - r = &pq->records[pq->record_cnt++]; + if (pq->n_records >= pq->allocated_records) + { + pq->allocated_records = pq->allocated_records * 2; + if (pq->allocated_records < 16) + pq->allocated_records = 16; + else if (pq->allocated_records > pq->max_records) + pq->allocated_records = pq->max_records; + pq->records = xrealloc (pq->records, + pq->allocated_records * sizeof *pq->records); + } + + r = &pq->records[pq->n_records++]; r->id = id; r->c = c; r->idx = pq->idx++; - push_heap (pq->records, pq->record_cnt, sizeof *pq->records, + push_heap (pq->records, pq->n_records, sizeof *pq->records, compare_pqueue_records_minheap, pq); } @@ -282,10 +299,10 @@ pqueue_pop (struct pqueue *pq, casenumber *id) assert (!pqueue_is_empty (pq)); - pop_heap (pq->records, pq->record_cnt--, sizeof *pq->records, + pop_heap (pq->records, pq->n_records--, sizeof *pq->records, compare_pqueue_records_minheap, pq); - r = &pq->records[pq->record_cnt]; + r = &pq->records[pq->n_records]; *id = r->id; return r->c; }