Homec4science
Diffusion RADIANCE Photon Map (pmapmerge) Browse

RadiancePmap/oocsort.h
290ea18748c4pmapmerge

Last Change
Raw File

oocsort.h
View Options

/*
======================================================================
Header for N-way out-of-core merge sort for records with 3D keys.
Roland Schregle (roland.schregle@{hslu.ch, gmail.com})
(c) Lucerne University of Applied Sciences and Arts,
supported by the Swiss National Science Foundation (SNSF, #147053)
======================================================================
$Id: oocsort.h,v 2.3 2016/05/17 17:39:47 rschregle Exp $
*/
#ifndef OOC_SORT_H
#define OOC_SORT_H
#include "fvect.h"
#include "morton.h"
#include <stdio.h>
/* Priority queue node */
typedef struct {
MortonIdx pri; /* Record's priority (sort key) */
unsigned blk; /* Block containing record */
} OOC_SortQueueNode;
/* Priority queue */
typedef struct {
OOC_SortQueueNode *head;
unsigned len, tail;
} OOC_SortQueue;
/* Additional data for key comparison function.*/
typedef struct {
RREAL *(*key)(const void*); /* Callback to access 3D key in record */
FVECT bbOrg; /* Origin of bbox containing keys */
RREAL mortonScale; /* Scale for generating Morton code */
} OOC_KeyData;
/* Read next record from file; return 0 and record in rec on success,
* else -1 */
int OOC_SortRead (FILE *file, unsigned recSize, char *rec);
/* Return next record from file WITHOUT advancing file position;
* return 0 and record in rec on success, else -1 */
int OOC_SortPeek (FILE *file, unsigned recSize, char *rec);
/* Output record to file; return 0 on success, else -1 */
int OOC_SortWrite (FILE *file, unsigned recSize, const char *rec);
/* Insert specified block index into priority queue; return block index
* or -1 if queue is full */
int OOC_SortPush (OOC_SortQueue *pq, MortonIdx pri, unsigned blk);
/* Remove head of priority queue and return its block index or -1
if queue empty */
int OOC_SortPop (OOC_SortQueue *pq);
/* Sort records in inFile and append to outFile by subdividing inFile
* into small blocks, sorting these in-core, and merging them out-of-core
* via a priority queue.
*
* This is implemented as a recursive (numBlk)-way sort; the input is
* successively split into numBlk smaller blocks until these are of size
* <= blkSize, i.e. small enough for in-core sorting, then merging the
* sorted blocks as the stack unwinds. The in-core sort is parallelised
* over numProc processes.
*
* Parameters are as follows:
* inFile Opened input file containing unsorted records
* outFile Opened output file containing sorted records
* numBlk Number of blocks to divide into / merge from
* blkSize Max block size and size of in-core sort buffer, in bytes
* numProc Number of parallel processes for in-core sort
* recSize Size of input records in bytes
* bbOrg Origin of bounding box containing record keys for Morton code
* bbSize Extent of bounding box containing record keys for Morton code
* key Callback to access 3D coords from records for Morton code
*/
int OOC_Sort (FILE *inFile, FILE *outFile,
unsigned numBlk, unsigned long blkSize, unsigned numProc,
unsigned recSize, FVECT bbOrg, RREAL bbSize,
RREAL *(*key)(const void*));
#endif
c4science · Help