X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Fmath%2Fsort.c;h=a784960420874dd17d0bff8ba8715d824506614b;hb=17d00f9ba94128390819277e5d614a03e98aade0;hp=67aa32d29048fffbb5e7b3c03b371b8db9c88a62;hpb=a1efcf97ca2f75f4be6a0389ff2372c03ed2d4e1;p=pspp diff --git a/src/math/sort.c b/src/math/sort.c index 67aa32d290..a784960420 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 *); @@ -63,20 +61,21 @@ static struct ccase *pqueue_pop (struct pqueue *, casenumber *); static void output_record (struct sort_writer *); 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 @@ -105,6 +104,7 @@ sort_casewriter_destroy (struct casewriter *writer UNUSED, void *sort_) pqueue_destroy (sort->pqueue); casewriter_destroy (sort->run); case_unref (sort->run_end); + caseproto_unref (sort->proto); free (sort); } @@ -117,7 +117,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 +149,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 +166,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) { @@ -195,8 +197,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 +214,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; @@ -250,13 +253,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 +269,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 +296,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; }