]> mj.ucw.cz Git - libucw.git/blob - ucw/sorter/s-fixint.h
The big move. Step #1: Move whole lib/ to ucw/.
[libucw.git] / ucw / sorter / s-fixint.h
1 /*
2  *      UCW Library -- Universal Sorter: Fixed-Size Internal Sorting Module
3  *
4  *      (c) 2007 Martin Mares <mj@ucw.cz>
5  *
6  *      This software may be freely distributed and used according to the terms
7  *      of the GNU Lesser General Public License.
8  */
9
10 #include "ucw/stkstring.h"
11
12 #define ASORT_PREFIX(x) SORT_PREFIX(array_##x)
13 #define ASORT_KEY_TYPE P(key)
14 #define ASORT_LT(x,y) (P(compare)(&(x), &(y)) < 0)
15 #ifdef SORT_INTERNAL_RADIX
16 #  define ASORT_HASH(x) P(hash)(&(x))
17 #    ifdef SORT_LONG_HASH
18 #      define ASORT_LONG_HASH
19 #    endif
20 #endif
21 #include "ucw/sorter/array.h"
22
23 /*
24  *  This is a more efficient implementation of the internal sorter,
25  *  which runs under the following assumptions:
26  *
27  *     - the keys have fixed (and small) size
28  *     - no data are present after the key
29  *     - unification does not require any workspace
30  */
31
32 static size_t P(internal_workspace)(void)
33 {
34   size_t workspace = 0;
35 #ifdef SORT_UNIFY
36   workspace = sizeof(P(key) *);
37 #endif
38 #ifdef SORT_INTERNAL_RADIX
39   workspace = MAX(workspace, sizeof(P(key)));
40 #endif
41   return workspace;
42 }
43
44 static uns P(internal_num_keys)(struct sort_context *ctx)
45 {
46   size_t bufsize = ctx->big_buf_size;
47   size_t workspace = P(internal_workspace)();
48   if (workspace)
49     bufsize -= CPU_PAGE_SIZE;
50   u64 maxkeys = bufsize / (sizeof(P(key)) + workspace);
51   return MIN(maxkeys, ~0U);                                     // The number of records must fit in uns
52 }
53
54 static int P(internal)(struct sort_context *ctx, struct sort_bucket *bin, struct sort_bucket *bout, struct sort_bucket *bout_only)
55 {
56   sorter_alloc_buf(ctx);
57   struct fastbuf *in = sbuck_read(bin);
58   P(key) *buf = ctx->big_buf;
59   uns maxkeys = P(internal_num_keys)(ctx);
60
61   SORT_XTRACE(5, "s-fixint: Reading (maxkeys=%u, hash_bits=%d)", maxkeys, bin->hash_bits);
62   uns n = 0;
63   while (n < maxkeys && P(read_key)(in, &buf[n]))
64     n++;
65   if (!n)
66     return 0;
67   void *workspace UNUSED = ALIGN_PTR(&buf[n], CPU_PAGE_SIZE);
68
69   SORT_XTRACE(4, "s-fixint: Sorting %u items (%s items, %s workspace)",
70         n,
71         stk_fsize(n * sizeof(P(key))),
72         stk_fsize(n * P(internal_workspace)()));
73   timestamp_t timer;
74   init_timer(&timer);
75   buf = P(array_sort)(buf, n
76 #ifdef SORT_INTERNAL_RADIX
77     , workspace, bin->hash_bits
78 #endif
79     );
80   if ((void *)buf != ctx->big_buf)
81     workspace = ctx->big_buf;
82   ctx->total_int_time += get_timer(&timer);
83
84   SORT_XTRACE(5, "s-fixint: Writing");
85   if (n < maxkeys)
86     bout = bout_only;
87   struct fastbuf *out = sbuck_write(bout);
88   bout->runs++;
89   uns merged UNUSED = 0;
90   for (uns i=0; i<n; i++)
91     {
92 #ifdef SORT_UNIFY
93       if (i < n-1 && !P(compare)(&buf[i], &buf[i+1]))
94         {
95           P(key) **keys = workspace;
96           uns n = 2;
97           keys[0] = &buf[i];
98           keys[1] = &buf[i+1];
99           while (!P(compare)(&buf[i], &buf[i+n]))
100             {
101               keys[n] = &buf[i+n];
102               n++;
103             }
104           P(write_merged)(out, keys, NULL, n, NULL);
105           merged += n - 1;
106           i += n - 1;
107           continue;
108         }
109 #endif
110 #ifdef SORT_ASSERT_UNIQUE
111       ASSERT(i == n-1 || P(compare)(&buf[i], &buf[i+1]) < 0);
112 #endif
113       P(write_key)(out, &buf[i]);
114     }
115 #ifdef SORT_UNIFY
116   SORT_XTRACE(4, "Merging reduced %u records", merged);
117 #endif
118
119   return (n == maxkeys);
120 }
121
122 static u64
123 P(internal_estimate)(struct sort_context *ctx, struct sort_bucket *b UNUSED)
124 {
125   return P(internal_num_keys)(ctx) * sizeof(P(key)) - 1;        // -1 since if the buffer is full, we don't recognize EOF
126 }