2 * UCW Library -- Universal Sorter: Governing Routines
4 * (c) 2007 Martin Mares <mj@ucw.cz>
6 * This software may be freely distributed and used according to the terms
7 * of the GNU Lesser General Public License.
11 #include "lib/fastbuf.h"
12 #include "lib/mempool.h"
13 #include "lib/sorter/common.h"
18 sorter_presort(struct sort_context *ctx, struct sort_bucket *in, struct sort_bucket *out, struct sort_bucket *out_only)
20 sorter_alloc_buf(ctx);
21 if (in->flags & SBF_CUSTOM_PRESORT)
23 struct fastbuf *f = sbuck_write(out);
24 return ctx->custom_presort(f, ctx->big_buf, ctx->big_buf_size); // FIXME: out_only optimization?
26 return ctx->internal_sort(ctx, in, out, out_only);
29 static inline struct sort_bucket *
30 sbuck_join_to(struct sort_bucket *b)
32 if (sorter_debug & SORT_DEBUG_NO_JOIN)
35 struct sort_bucket *out = (struct sort_bucket *) b->n.prev; // Such bucket is guaranteed to exist
36 return (out->flags & SBF_FINAL) ? out : NULL;
40 sorter_join(struct sort_bucket *b)
42 struct sort_bucket *join = (struct sort_bucket *) b->n.prev;
43 ASSERT(join->flags & SBF_FINAL);
46 if (!sbuck_has_file(join))
48 // The final bucket doesn't have any file associated yet, so replace
49 // it with the new bucket.
50 SORT_XTRACE(2, "Replaced final bucket");
51 b->flags |= SBF_FINAL;
56 SORT_TRACE("Copying to output file: %s", F_BSIZE(b));
57 struct fastbuf *src = sbuck_read(b);
58 struct fastbuf *dest = sbuck_write(join);
59 bbcopy(src, dest, ~0U);
65 sorter_twoway(struct sort_context *ctx, struct sort_bucket *b)
67 struct sort_bucket *ins[3] = { NULL }, *outs[3] = { NULL };
68 cnode *list_pos = b->n.prev;
69 struct sort_bucket *join = sbuck_join_to(b);
71 if (!(sorter_debug & SORT_DEBUG_NO_PRESORT) || (b->flags & SBF_CUSTOM_PRESORT))
73 SORT_XTRACE(2, "Presorting");
74 ins[0] = sbuck_new(ctx);
75 if (!sorter_presort(ctx, b, ins[0], join ? : ins[0]))
77 SORT_TRACE("Sorted in memory");
81 clist_insert_after(&ins[0]->n, list_pos);
86 ins[1] = sbuck_new(ctx);
88 while (sorter_presort(ctx, b, ins[i], ins[i]))
94 SORT_XTRACE(2, "Presorting disabled");
98 SORT_XTRACE(2, "Main sorting");
102 if (ins[0]->runs == 1 && ins[1]->runs == 1 && join)
104 // This is guaranteed to produce a single run, so join if possible
107 ctx->twoway_merge(ctx, ins, outs);
108 ASSERT(outs[0]->runs == 2);
110 SORT_TRACE("Mergesort pass %d (final run, %s)", pass, F_BSIZE(outs[0]));
115 outs[0] = sbuck_new(ctx);
116 outs[1] = sbuck_new(ctx);
118 ctx->twoway_merge(ctx, ins, outs);
119 SORT_TRACE("Mergesort pass %d (%d+%d runs, %s+%s)", pass, outs[0]->runs, outs[1]->runs, F_BSIZE(outs[0]), F_BSIZE(outs[1]));
122 memcpy(ins, outs, 3*sizeof(struct sort_bucket *));
123 } while (sbuck_have(ins[1]));
126 clist_insert_after(&ins[0]->n, list_pos);
130 sorter_run(struct sort_context *ctx)
132 ctx->pool = mp_new(4096);
133 clist_init(&ctx->bucket_list);
135 /* FIXME: There should be a way how to detect size of the input file */
136 /* FIXME: Remember to test sorting of empty files */
138 // Create bucket containing the source
139 struct sort_bucket *bin = sbuck_new(ctx);
140 bin->flags = SBF_SOURCE | SBF_OPEN_READ;
141 if (ctx->custom_presort)
142 bin->flags |= SBF_CUSTOM_PRESORT;
144 bin->fb = ctx->in_fb;
147 bin->hash_bits = ctx->hash_bits;
148 clist_add_tail(&ctx->bucket_list, &bin->n);
150 // Create bucket for the output
151 struct sort_bucket *bout = sbuck_new(ctx);
152 bout->flags = SBF_FINAL;
153 bout->fb = ctx->out_fb;
156 clist_add_head(&ctx->bucket_list, &bout->n);
158 struct sort_bucket *b;
159 while (bout = clist_head(&ctx->bucket_list), b = clist_next(&ctx->bucket_list, &bout->n))
163 else if (b->runs == 1)
166 sorter_twoway(ctx, b);
169 sorter_free_buf(ctx);
170 sbuck_write(bout); // Force empty bucket to a file
171 SORT_XTRACE(2, "Final size: %s", F_BSIZE(bout));
172 ctx->out_fb = sbuck_read(bout);