| 1 |
|
/* |
| 2 |
< |
================================================================== |
| 3 |
< |
Header for N-way hybrid out-of-core merge sort |
| 2 |
> |
====================================================================== |
| 3 |
> |
Header for N-way out-of-core merge sort for records with 3D keys. |
| 4 |
|
|
| 5 |
|
Roland Schregle (roland.schregle@{hslu.ch, gmail.com}) |
| 6 |
< |
(c) Fraunhofer Institute for Solar Energy Systems, |
| 7 |
< |
Lucerne University of Applied Sciences & Arts |
| 8 |
< |
================================================================== |
| 6 |
> |
(c) Lucerne University of Applied Sciences and Arts, |
| 7 |
> |
supported by the Swiss National Science Foundation (SNSF, #147053) |
| 8 |
> |
====================================================================== |
| 9 |
|
|
| 10 |
< |
$Id $ |
| 10 |
> |
$Id$ |
| 11 |
|
*/ |
| 12 |
|
|
| 13 |
|
#ifndef OOC_SORT_H |
| 14 |
< |
#define OOC_SORT_H |
| 15 |
< |
#include <stdint.h> |
| 14 |
> |
#define OOC_SORT_H |
| 15 |
|
|
| 16 |
< |
#define OOC_SORT_BUFSIZE (1 << 13) /* 8kb */ |
| 16 |
> |
#include "fvect.h" |
| 17 |
> |
#include <stdio.h> |
| 18 |
|
|
| 19 |
– |
typedef uint64_t OOC_Sort_Key; |
| 19 |
|
|
| 20 |
< |
#if 0 |
| 21 |
< |
int OOC_Sort (const char *inFile, const char *outFile, |
| 22 |
< |
unsigned long blkSize, unsigned recSize, |
| 23 |
< |
OOC_Sort_Key (*priority)(const void *)); |
| 24 |
< |
/* Sort records in inFile and output to outFile by (a) internally |
| 25 |
< |
* quicksorting block of blkSize bytes at a time, then (b) merging them |
| 26 |
< |
* via a priority queue. RecSize specifies the size in bytes of each |
| 27 |
< |
* data record. The priority() callback evaluates a record's priority |
| 28 |
< |
* and must be supplied by the caller. */ |
| 29 |
< |
#else |
| 30 |
< |
int OOC_Sort (const char *inFile, const char *outFile, |
| 31 |
< |
unsigned numBlocks, unsigned recSize, |
| 32 |
< |
OOC_Sort_Key (*priority)(const void *)); |
| 33 |
< |
/* Sort records in inFile and output to outFile by (a) internally |
| 34 |
< |
* quicksorting numBlocks blocks at a time, then (b) merging them |
| 35 |
< |
* via a priority queue. RecSize specifies the size in bytes of each |
| 36 |
< |
* data record. The priority() callback evaluates a record's priority |
| 37 |
< |
* (ordinal index) and must be supplied by the caller. */ |
| 38 |
< |
#endif |
| 39 |
< |
|
| 20 |
> |
/* Sort records in inFile and append to outFile by subdividing inFile |
| 21 |
> |
* into small blocks, sorting these in-core, and merging them out-of-core |
| 22 |
> |
* via a priority queue. |
| 23 |
> |
* |
| 24 |
> |
* This is implemented as a recursive (numBlk)-way sort; the input is |
| 25 |
> |
* successively split into numBlk smaller blocks until these are of size |
| 26 |
> |
* <= blkSize, i.e. small enough for in-core sorting, then merging the |
| 27 |
> |
* sorted blocks as the stack unwinds. The in-core sort is parallelised |
| 28 |
> |
* over numProc processes. |
| 29 |
> |
* |
| 30 |
> |
* Parameters are as follows: |
| 31 |
> |
* inFile Opened input file containing unsorted records |
| 32 |
> |
* outFile Opened output file containing sorted records |
| 33 |
> |
* numBlk Number of blocks to divide into / merge from |
| 34 |
> |
* blkSize Max block size and size of in-core sort buffer, in bytes |
| 35 |
> |
* numProc Number of parallel processes for in-core sort |
| 36 |
> |
* recSize Size of input records in bytes |
| 37 |
> |
* bbOrg Origin of bounding box containing record keys for Morton code |
| 38 |
> |
* bbSize Extent of bounding box containing record keys for Morton code |
| 39 |
> |
* key Callback to access 3D coords from records for Morton code |
| 40 |
> |
*/ |
| 41 |
> |
int OOC_Sort (FILE *inFile, FILE *outFile, unsigned numBlk, |
| 42 |
> |
unsigned long blkSize, unsigned numProc, unsigned recSize, |
| 43 |
> |
FVECT bbOrg, RREAL bbSize, RREAL *(*key)(const void*)); |
| 44 |
|
#endif |
