]> mj.ucw.cz Git - libucw.git/blob - lib/sorter.h
Removed FIXME.
[libucw.git] / lib / sorter.h
1 /*
2  *      Sherlock Library -- Universal Sorter
3  *
4  *      (c) 2001 Martin Mares <mj@ucw.cz>
5  */
6
7 /*
8  *  This is not a normal header file, it's a generator of sorting
9  *  routines.  Each time you include it with parameters set in the
10  *  corresponding preprocessor macros, it generates a file sorter
11  *  with the parameters given.
12  *
13  *  Recognized parameter macros: (those marked with [*] are mandatory)
14  *
15  *  SORT_KEY        [*] data type capable of storing a single key
16  *  SORT_PREFIX(x)  [*] add a name prefix (used on all global names
17  *                      defined by the sorter)
18  *  SORT_PRESORT        include an in-core presorting pass
19  *  SORT_UNIFY          merge items with identical keys
20  *  SORT_DELETE_INPUT   a C expression, if true, the input files are
21  *                      deleted as soon as possible
22  *  SORT_INPUT_FILE     input is a file with this name
23  *  SORT_INPUT_FB       input is a fastbuf stream
24  *  SORT_INPUT_FBPAIR   input is a pair of fastbuf streams
25  *                      (not supported by the presorter)
26  *  SORT_OUTPUT_FILE    output is a file with this name
27  *  SORT_OUTPUT_FB      output is a temporary fastbuf stream
28  *
29  *  You also need to define some (usually inline) functions which
30  *  are called by the sorter to process your data:
31  *
32  *  int PREFIX_compare(SORT_KEY *a, *b)
33  *                      compare two keys, result like strcmp
34  *  int PREFIX_fetch_key(struct fastbuf *f, SORT_KEY *k)
35  *                      fetch next key, returns 1=ok, 0=eof
36  *  void PREFIX_copy_data(struct fastbuf *src, *dest, SORT_KEY *k)
37  *                      write just fetched key k to dest and copy all data
38  *                      belonging to this key from src to dest.
39  *  void PREFIX_merge_data(struct fastbuf *src1, *src2, *dest, SORT_KEY *k1, *k2)
40  *                      [used only in case SORT_UNIFY is defined]
41  *                      write just fetched key k to dest and merge data from
42  *                      two records with the same key (k1 and k2 are key occurences
43  *                      in the corresponding streams).
44  *  byte * PREFIX_fetch_item(struct fastbuf *f, SORT_KEY *k, byte *limit)
45  *                      [used only with SORT_PRESORT]
46  *                      fetch data belonging to a just fetched key and store
47  *                      them to memory following the key, but not over limit.
48  *                      Returns a pointer to first byte after the data
49  *                      or NULL if the data don't fit.
50  *                      Important: keys carrying no data must be position
51  *                      independent.
52  *  void PREFIX_store_item(struct fastbuf *f, SORT_KEY *k)
53  *                      [used only with SORT_PRESORT]
54  *                      write key and all its data read with PREFIX_fetch_data
55  *                      to the stream given.
56  *  SORT_KEY * PREFIX_merge_items(SORT_KEY *a, SORT_KEY *b)
57  *                      [used only with SORT_PRESORT && SORT_UNIFY]
58  *                      merge two items with the same key, returns pointer
59  *                      to at most one of the items, the rest will be removed
60  *                      from the list of items, but not deallocated, so
61  *                      the remaining item can freely reference data of the
62  *                      other one.
63  */
64
65 /* Declarations of externals from sorter.c */
66
67 #ifndef SORT_DECLS_READ
68 #define SORT_DECLS_READ
69
70 extern uns sorter_trace;
71 extern uns sorter_presort_bufsize;
72 extern uns sorter_stream_bufsize;
73
74 extern uns sorter_pass_counter, sorter_file_counter;
75 struct fastbuf *sorter_open_tmp(void);
76
77 #endif          /* !SORT_DECLS_READ */
78
79 /* The sorter proper */
80
81 #ifndef SORT_DECLARE_ONLY
82
83 #include "lib/fastbuf.h"
84 #include <unistd.h>
85 #include <fcntl.h>
86 #include <string.h>
87
88 #if !defined(SORT_KEY) || !defined(SORT_PREFIX)
89 #error Some of the mandatory configuration macros are missing.
90 #endif
91
92 #define P(x) SORT_PREFIX(x)
93 #define SWAP(x,y,z) do { z=x; x=y; y=z; } while(0)
94
95 #if defined(SORT_UNIFY) || defined(SORT_UNIQUE)
96 #define LESS <
97 #else
98 #define LESS <=
99 #endif
100
101 static struct fastbuf *
102 P(flush_out)(struct fastbuf *out)
103 {
104   if (out)
105     {
106       bflush(out);
107       bsetpos(out, 0);
108     }
109   return out;
110 }
111
112 static void
113 P(pass)(struct fastbuf **fb1, struct fastbuf **fb2)
114 {
115   struct fastbuf *in1 = *fb1;
116   struct fastbuf *in2 = *fb2;
117   struct fastbuf *out1 = NULL;
118   struct fastbuf *out2 = NULL;
119   SORT_KEY kbuf1, kbuf2, kbuf3, kbuf4;
120   SORT_KEY *kin1 = &kbuf1;
121   SORT_KEY *kprev1 = &kbuf2;
122   SORT_KEY *kin2 = &kbuf3;
123   SORT_KEY *kprev2 = &kbuf4;
124   SORT_KEY *kout = NULL;
125   SORT_KEY *ktmp;
126   int next1, next2, comp;
127   int run1, run2;
128   uns run_count = 0;
129
130   run1 = next1 = in1 ? P(fetch_key)(in1, kin1) : 0;
131   run2 = next2 = in2 ? P(fetch_key)(in2, kin2) : 0;
132   while (next1 || next2)
133     {
134       if (!run1)
135         comp = 1;
136       else if (!run2)
137         comp = -1;
138       else
139         comp = P(compare)(kin1, kin2);
140       ktmp = (comp <= 0) ? kin1 : kin2;
141       if (!kout || !(P(compare)(kout, ktmp) LESS 0))
142         {
143           struct fastbuf *t;
144           SWAP(out1, out2, t);
145           if (!out1)
146             out1 = sorter_open_tmp();
147           run_count++;
148         }
149       if (comp LESS 0)
150         {
151           P(copy_data)(in1, out1, kin1);
152           SWAP(kin1, kprev1, ktmp);
153           next1 = P(fetch_key)(in1, kin1);
154           run1 = next1 && (P(compare)(kprev1, kin1) LESS 0);
155           kout = kprev1;
156         }
157 #ifdef SORT_UNIFY
158       else if (comp == 0)
159         {
160           P(merge_data)(in1, in2, out1, kin1, kin2);
161           SWAP(kin1, kprev1, ktmp);
162           next1 = P(fetch_key)(in1, kin1);
163           run1 = next1 && (P(compare)(kprev1, kin1) LESS 0);
164           SWAP(kin2, kprev2, ktmp);
165           next2 = P(fetch_key)(in2, kin2);
166           run2 = next2 && (P(compare)(kprev2, kin2) LESS 0);
167           kout = kprev2;
168         }
169 #endif
170       else
171         {
172           P(copy_data)(in2, out1, kin2);
173           SWAP(kin2, kprev2, ktmp);
174           next2 = P(fetch_key)(in2, kin2);
175           run2 = next2 && (P(compare)(kprev2, kin2) LESS 0);
176           kout = kprev2;
177         }
178       if (!run1 && !run2)
179         {
180           run1 = next1;
181           run2 = next2;
182         }
183     }
184   bclose(in1);
185   bclose(in2);
186   if (sorter_trace)
187     log(L_INFO, "Pass %d: %d runs, %d+%d KB", sorter_pass_counter, run_count,
188         (out1 ? (int)((btell(out1) + 1023) / 1024) : 0),
189         (out2 ? (int)((btell(out2) + 1023) / 1024) : 0));
190   *fb1 = P(flush_out)(out1);
191   *fb2 = P(flush_out)(out2);
192   sorter_pass_counter++;
193 }
194
195 #ifdef SORT_PRESORT
196
197 #define SORT_NODE struct P(presort_node)
198
199 SORT_NODE {
200   SORT_NODE *next;
201   SORT_KEY key;
202 };
203
204 static SORT_NODE *
205 P(mergesort)(SORT_NODE *x)
206 {
207   SORT_NODE *f1, **l1, *f2, **l2, **l;
208
209   l1 = &f1;
210   l2 = &f2;
211   while (x)
212     {
213       *l1 = x;
214       l1 = &x->next;
215       x = x->next;
216       if (!x)
217         break;
218       *l2 = x;
219       l2 = &x->next;
220       x = x->next;
221     }
222   *l1 = *l2 = NULL;
223
224   if (f1 && f1->next)
225     f1 = P(mergesort)(f1);
226   if (f2 && f2->next)
227     f2 = P(mergesort)(f2);
228   l = &x;
229   while (f1 && f2)
230     {
231       if (P(compare)(&f1->key, &f2->key) <= 0)
232         {
233           *l = f1;
234           l = &f1->next;
235           f1 = f1->next;
236         }
237       else
238         {
239           *l = f2;
240           l = &f2->next;
241           f2 = f2->next;
242         }
243     }
244   *l = f1 ? : f2;
245   return x;
246 }
247
248 static void
249 P(presort)(struct fastbuf **fb1, struct fastbuf **fb2)
250 {
251   struct fastbuf *in = *fb1;
252   struct fastbuf *out1 = NULL;
253   struct fastbuf *out2 = NULL;
254   struct fastbuf *tbuf;
255   byte *buffer, *bufend, *current;
256   SORT_NODE *first, **last, *this, *leftover;
257   int cont = 1;
258   uns run_count = 0;
259   uns giant_count = 0;
260   uns split_count = 0;
261
262   ASSERT(!*fb2);
263   if (sorter_presort_bufsize < 2*sizeof(SORT_NODE))
264     die("PresortBuffer set too low");
265   buffer = xmalloc(sorter_presort_bufsize);
266   bufend = buffer + sorter_presort_bufsize;
267   leftover = NULL;
268   while (cont)
269     {
270       SWAP(out1, out2, tbuf);
271       if (!out1)
272         out1 = sorter_open_tmp();
273       current = buffer;
274       last = &first;
275       if (leftover)
276         {
277           memmove(buffer, leftover, sizeof(SORT_NODE));
278           this = leftover = (SORT_NODE *) buffer;
279           split_count++;
280           goto get_data;
281         }
282       for(;;)
283         {
284           current = (byte *) ALIGN((addr_int_t) current, CPU_STRUCT_ALIGN);
285           if (current + sizeof(*this) > bufend)
286             break;
287           this = (SORT_NODE *) current;
288           cont = P(fetch_key)(in, &this->key);
289           if (!cont)
290             break;
291         get_data:
292           current = P(fetch_item)(in, &this->key, bufend);
293           if (!current)
294             {
295               if (leftover)             /* Single node too large */
296                 {
297                   P(copy_data)(in, out1, &leftover->key);
298                   leftover = NULL;
299                   run_count++;
300                   giant_count++;
301                 }
302               else                      /* Node will be left over to the next phase */
303                 leftover = this;
304               break;
305             }
306           *last = this;
307           last = &this->next;
308           leftover = NULL;
309         }
310       *last = NULL;
311       if (!first)
312         continue;
313
314       first = P(mergesort)(first);
315       run_count++;
316       while (first)
317         {
318 #ifdef SORT_UNIFY
319           SORT_NODE *second = first->next;
320           if (second && !P(compare)(&first->key, &second->key))
321             {
322               SORT_KEY *n = P(merge_items)(&first->key, &second->key);
323               if (n == &first->key)
324                 first->next = second->next;
325               else if (n)
326                 first = first->next;
327               else
328                 first = second->next;
329               continue;
330             }
331 #endif
332           P(store_item)(out1, &first->key);
333           first = first->next;
334         }
335     }
336
337   bclose(in);
338   if (sorter_trace)
339     log(L_INFO, "Pass 0: %d runs (%d giants, %d splits), %d+%d KB",
340         run_count, giant_count, split_count,
341         (out1 ? (int)((btell(out1) + 1023) / 1024) : 0),
342         (out2 ? (int)((btell(out2) + 1023) / 1024) : 0));
343   *fb1 = P(flush_out)(out1);
344   *fb2 = P(flush_out)(out2);
345 }
346
347 #endif          /* SORT_PRESORT */
348
349 static
350 #ifdef SORT_OUTPUT_FB
351 struct fastbuf *
352 #elif defined(SORT_OUTPUT_FILE)
353 void
354 #else
355 #error No output defined.
356 #endif
357 P(sort)(
358 #ifdef SORT_INPUT_FILE
359 byte *inname
360 #elif defined(SORT_INPUT_FB)
361 struct fastbuf *fb1
362 #elif defined(SORT_INPUT_FBPAIR)
363 struct fastbuf *fb1, struct fastbuf *fb2
364 #else
365 #error No input defined.
366 #endif
367 #ifdef SORT_OUTPUT_FILE
368 ,byte *outname
369 #endif
370 )
371 {
372 #ifdef SORT_INPUT_FILE
373   struct fastbuf *fb1, *fb2;
374   fb1 = bopen(inname, O_RDONLY, sorter_stream_bufsize);
375   fb2 = NULL;
376 #elif defined(SORT_INPUT_FB)
377   struct fastbuf *fb2 = NULL;
378 #endif
379
380 #ifdef SORT_DELETE_INPUT
381   fb1->is_temp_file = SORT_DELETE_INPUT;
382 #endif
383   sorter_pass_counter = 1;
384 #ifdef SORT_PRESORT
385   P(presort)(&fb1, &fb2);
386   if (fb2)
387 #endif
388     do P(pass)(&fb1, &fb2); while (fb1 && fb2);
389   if (!fb1)
390     fb1 = sorter_open_tmp();
391
392 #ifdef SORT_OUTPUT_FB
393   return fb1;
394 #else
395   fb1->is_temp_file = 0;
396   if (rename(fb1->name, outname) < 0)
397     die("rename(%s,%s): %m", fb1->name, outname);
398   bclose(fb1);
399 #endif
400 }
401
402 #undef P
403 #undef LESS
404 #undef SWAP
405 #undef SORT_NODE
406
407 #endif          /* !SORT_DECLARE_ONLY */