1 |
#ifndef lint |
2 |
static const char RCSid[] = "$Id$"; |
3 |
#endif |
4 |
|
5 |
|
6 |
/* |
7 |
========================================================================= |
8 |
N-way out-of-core merge sort for records with 3D keys. Recursively |
9 |
subdivides input into N blocks until these are of sufficiently small size |
10 |
to be sorted in-core according to Z-order (Morton code), then N-way |
11 |
merging them out-of-core using a priority queue as the stack unwinds. |
12 |
|
13 |
Roland Schregle (roland.schregle@{hslu.ch, gmail.com}) |
14 |
(c) Lucerne University of Applied Sciences and Arts, |
15 |
supported by the Swiss National Science Foundation (SNSF, #147053) |
16 |
========================================================================== |
17 |
|
18 |
$Id: oocsort.c,v 2.3 2016/05/17 17:39:47 rschregle Exp $ |
19 |
*/ |
20 |
|
21 |
|
22 |
#if !defined(_WIN32) && !defined(_WIN64) || defined(PMAP_OOC) |
23 |
/* No Windoze support for now */ |
24 |
|
25 |
#include "oocsort.h" |
26 |
#include "oocmorton.h" |
27 |
#include <stdio.h> |
28 |
#include <stdlib.h> |
29 |
#include <unistd.h> |
30 |
#include <fcntl.h> |
31 |
#include <sys/wait.h> |
32 |
|
33 |
|
34 |
/* Priority queue node */ |
35 |
typedef struct { |
36 |
OOC_MortonIdx pri; /* Record's priority (sort key) */ |
37 |
unsigned blk; /* Block containing record */ |
38 |
} OOC_SortQueueNode; |
39 |
|
40 |
|
41 |
/* Priority queue */ |
42 |
typedef struct { |
43 |
OOC_SortQueueNode *node; |
44 |
unsigned len, tail; |
45 |
} OOC_SortQueue; |
46 |
|
47 |
|
48 |
/* Additional data for qsort() compare function. We resort to instancing |
49 |
* this as a global variable instead of passing it to the compare func via |
50 |
* qsort_r(), since the latter is a non-portable GNU extension. */ |
51 |
typedef struct { |
52 |
RREAL *(*key)(const void*); /* Callback to access 3D key in record */ |
53 |
FVECT bbOrg; /* Origin of bbox containing keys */ |
54 |
RREAL mortonScale; /* Scale for generating Morton code */ |
55 |
} OOC_KeyData; |
56 |
|
57 |
static OOC_KeyData keyData; |
58 |
|
59 |
|
60 |
|
61 |
static int OOC_KeyCompare (const void *rec1, const void *rec2) |
62 |
/* Comparison function for in-core quicksort */ |
63 |
{ |
64 |
OOC_MortonIdx pri1, pri2; |
65 |
|
66 |
if (!rec1 || !rec2) |
67 |
return 0; |
68 |
|
69 |
pri1 = OOC_Key2Morton(keyData.key(rec1), keyData.bbOrg, |
70 |
keyData.mortonScale); |
71 |
pri2 = OOC_Key2Morton(keyData.key(rec2), keyData.bbOrg, |
72 |
keyData.mortonScale); |
73 |
|
74 |
if (pri1 < pri2) |
75 |
return -1; |
76 |
else if (pri1 > pri2) |
77 |
return 1; |
78 |
else |
79 |
return 0; |
80 |
} |
81 |
|
82 |
|
83 |
|
84 |
static int OOC_SortRead (FILE *file, unsigned recSize, char *rec) |
85 |
/* Read next record from file; return 0 and record in rec on success, |
86 |
* else -1 */ |
87 |
{ |
88 |
if (!rec || feof(file) || !fread(rec, recSize, 1, file)) |
89 |
return -1; |
90 |
|
91 |
return 0; |
92 |
} |
93 |
|
94 |
|
95 |
|
96 |
static int OOC_SortPeek (FILE *file, unsigned recSize, char *rec) |
97 |
/* Return next record from file WITHOUT advancing file position; |
98 |
* return 0 and record in rec on success, else -1 */ |
99 |
{ |
100 |
const unsigned long filePos = ftell(file); |
101 |
|
102 |
if (OOC_SortRead(file, recSize, rec)) |
103 |
return -1; |
104 |
|
105 |
/* Workaround; fseek(file, -recSize, SEEK_CUR) causes subsequent |
106 |
* fread()'s to fail until rewind() */ |
107 |
rewind(file); |
108 |
if (fseek(file, filePos, SEEK_SET) < 0) |
109 |
return -1; |
110 |
|
111 |
return 0; |
112 |
} |
113 |
|
114 |
|
115 |
|
116 |
static int OOC_SortWrite (FILE *file, unsigned recSize, const char *rec) |
117 |
/* Output record to file; return 0 on success, else -1 */ |
118 |
{ |
119 |
if (!rec || !fwrite(rec, recSize, 1, file)) |
120 |
return -1; |
121 |
|
122 |
return 0; |
123 |
} |
124 |
|
125 |
|
126 |
|
127 |
#ifdef DEBUG_OOC_SORT |
128 |
static int OOC_SortQueueCheck (OOC_SortQueue *pq, unsigned root) |
129 |
/* Priority queue sanity check */ |
130 |
{ |
131 |
unsigned kid; |
132 |
|
133 |
if (root < pq -> tail) { |
134 |
if ((kid = (root << 1) + 1) < pq -> tail) { |
135 |
if (pq -> node [kid].pri < pq -> node [root].pri) |
136 |
return -1; |
137 |
else return OOC_SortQueueCheck(pq, kid); |
138 |
} |
139 |
|
140 |
if ((kid = kid + 1) < pq -> tail) { |
141 |
if (pq -> node [kid].pri < pq -> node [root].pri) |
142 |
return -1; |
143 |
else return OOC_SortQueueCheck(pq, kid); |
144 |
} |
145 |
} |
146 |
|
147 |
return 0; |
148 |
} |
149 |
#endif |
150 |
|
151 |
|
152 |
|
153 |
static int OOC_SortPush (OOC_SortQueue *pq, OOC_MortonIdx pri, unsigned blk) |
154 |
/* Insert specified block index into priority queue; return block index |
155 |
* or -1 if queue is full */ |
156 |
{ |
157 |
OOC_SortQueueNode *pqn = pq -> node; |
158 |
unsigned kid, root; |
159 |
|
160 |
if (pq -> tail >= pq -> len) |
161 |
/* Queue full */ |
162 |
return -1; |
163 |
|
164 |
/* Append node at tail and re-sort */ |
165 |
kid = pq -> tail++; |
166 |
|
167 |
while (kid) { |
168 |
root = (kid - 1) >> 1; |
169 |
|
170 |
/* Compare with parent node and swap if necessary, else terminate */ |
171 |
if (pri < pqn [root].pri) { |
172 |
pqn [kid].pri = pqn [root].pri; |
173 |
pqn [kid].blk = pqn [root].blk; |
174 |
kid = root; |
175 |
} |
176 |
else break; |
177 |
} |
178 |
|
179 |
pqn [kid].pri = pri; |
180 |
pqn [kid].blk = blk; |
181 |
|
182 |
#ifdef DEBUG_OOC_SORT |
183 |
if (OOC_SortQueueCheck(pq, 0) < 0) { |
184 |
fprintf(stderr, "OOC_Sort: priority queue inconsistency\n"); |
185 |
return -1; |
186 |
} |
187 |
#endif |
188 |
|
189 |
return blk; |
190 |
} |
191 |
|
192 |
|
193 |
|
194 |
static int OOC_SortPop (OOC_SortQueue *pq) |
195 |
/* Remove head of priority queue and return its block index |
196 |
or -1 if queue empty */ |
197 |
{ |
198 |
OOC_SortQueueNode *pqn = pq -> node; |
199 |
OOC_MortonIdx pri; |
200 |
unsigned kid, kid2, root = 0, blk, res; |
201 |
|
202 |
if (!pq -> tail) |
203 |
/* Queue empty */ |
204 |
return -1; |
205 |
|
206 |
res = pqn -> blk; |
207 |
pri = pqn [--pq -> tail].pri; |
208 |
blk = pqn [pq -> tail].blk; |
209 |
|
210 |
/* Replace head with tail node and re-sort */ |
211 |
while ((kid = (root << 1) + 1) < pq -> tail) { |
212 |
/* Compare with smaller kid and swap if necessary, else terminate */ |
213 |
if ((kid2 = (kid + 1)) < pq -> tail && pqn [kid2].pri < pqn [kid].pri) |
214 |
kid = kid2; |
215 |
|
216 |
if (pri > pqn [kid].pri) { |
217 |
pqn [root].pri = pqn [kid].pri; |
218 |
pqn [root].blk = pqn [kid].blk; |
219 |
} |
220 |
else break; |
221 |
|
222 |
root = kid; |
223 |
} |
224 |
|
225 |
pqn [root].pri = pri; |
226 |
pqn [root].blk = blk; |
227 |
|
228 |
#ifdef DEBUG_OOC_SORT |
229 |
if (OOC_SortQueueCheck(pq, 0) < 0) { |
230 |
fprintf(stderr, "OOC_Sort: priority queue inconsistency\n"); |
231 |
return -1; |
232 |
} |
233 |
#endif |
234 |
|
235 |
return res; |
236 |
} |
237 |
|
238 |
|
239 |
|
240 |
/* Active subprocess counter updated by parent process; must persist when |
241 |
* recursing into OOC_SortRecurse(), hence global */ |
242 |
static unsigned procCnt = 0; |
243 |
|
244 |
static int OOC_SortRecurse (FILE *in, unsigned long blkLo, |
245 |
unsigned long blkHi, FILE *out, |
246 |
unsigned numBlk, unsigned long maxBlkSize, |
247 |
unsigned numProc, unsigned recSize, |
248 |
char *sortBuf, OOC_SortQueue *pqueue, |
249 |
const OOC_KeyData *keyData) |
250 |
/* Recursive part of OOC_Sort(). Reads block of records from input file |
251 |
* within the interval [blkLo, blkHi] and divides it into numBlk blocks |
252 |
* until the size (in bytes) does not exceed maxBlkSize, then quicksorts |
253 |
* each block into a temporary file. These files are then mergesorted via a |
254 |
* priority queue to the output file as the stack unwinds. NOTE: Critical |
255 |
* sections are prepended with '!!!' |
256 |
* |
257 |
* Parameters are as follows: |
258 |
* in Input file containing unsorted records (assumed to be open) |
259 |
* blkLo Start of current block in input file, in number of records |
260 |
* blkHi End of current block in input file, in number of records |
261 |
* out Output file containing sorted records (assumed to be open) |
262 |
* numBlk Number of blocks to divide into / merge from |
263 |
* maxBlkSize Max block size and size of in-core sort buffer, in bytes |
264 |
* numProc Number of parallel processes for in-core sort |
265 |
* recSize Size of input records in bytes |
266 |
* sortBuf Preallocated in-core sort buffer of size maxBlkSize |
267 |
* pqueue Preallocated priority queue of length numBlk for block merge |
268 |
* keyData Aggregate data for Morton code generation and comparison |
269 |
*/ |
270 |
{ |
271 |
const unsigned long blkLen = blkHi - blkLo + 1, |
272 |
blkSize = blkLen * recSize; |
273 |
int stat; |
274 |
|
275 |
if (!blkLen || blkHi < blkLo) |
276 |
return 0; |
277 |
|
278 |
if (blkSize > maxBlkSize) { |
279 |
unsigned long blkLo2 = blkLo, blkHi2 = blkLo, blkSize2; |
280 |
const double blkLen2 = (double)blkLen / numBlk; |
281 |
FILE *blkFile [numBlk]; /* Violates C89! */ |
282 |
char rec [recSize]; /* Ditto */ |
283 |
OOC_MortonIdx pri; |
284 |
int b, pid; |
285 |
#ifdef DEBUG_OOC_SORT |
286 |
unsigned long pqCnt = 0; |
287 |
#endif |
288 |
|
289 |
/* ====================================================== |
290 |
* Block too large for in-core sort -> divide into numBlk |
291 |
* subblocks and recurse |
292 |
* ====================================================== */ |
293 |
|
294 |
#ifdef DEBUG_OOC_SORT |
295 |
fprintf(stderr, "OOC_Sort: splitting block [%lu - %lu]\n", |
296 |
blkLo, blkHi); |
297 |
#endif |
298 |
|
299 |
for (b = 0; b < numBlk; b++) { |
300 |
/* Open temporary file as output for subblock */ |
301 |
if (!(blkFile [b] = tmpfile())) { |
302 |
perror("OOC_Sort: failed opening temporary block file"); |
303 |
return -1; |
304 |
} |
305 |
|
306 |
/* Subblock interval [blkLo2, blkHi2] of size blkSize2 */ |
307 |
blkHi2 = blkLo + (b + 1) * blkLen2 - 1; |
308 |
blkSize2 = (blkHi2 - blkLo2 + 1) * recSize; |
309 |
|
310 |
if (blkSize2 <= maxBlkSize) { |
311 |
/* !!! Will be in-core sorted on recursion -> fork kid process, |
312 |
* !!! but don't fork more than numProc kids; wait if necessary */ |
313 |
while (procCnt >= numProc && wait(&stat) >= 0) { |
314 |
if (!WIFEXITED(stat) || WEXITSTATUS(stat)) |
315 |
return -1; |
316 |
|
317 |
procCnt--; |
318 |
} |
319 |
|
320 |
/* Now fork kid process */ |
321 |
if (!(pid = fork())) { |
322 |
/* Recurse on subblocks with new input filehandle; */ |
323 |
if (OOC_SortRecurse(in, blkLo2, blkHi2, blkFile [b], numBlk, |
324 |
maxBlkSize, numProc, recSize, sortBuf, |
325 |
pqueue, keyData)) |
326 |
exit(-1); |
327 |
|
328 |
/* !!! Apparently the parent's tmpfile isn't deleted when the |
329 |
* !!! child exits (which is what we want), though some |
330 |
* !!! sources suggest using _Exit() instead; is this |
331 |
* !!! implementation specific? */ |
332 |
exit(0); |
333 |
} |
334 |
else if (pid < 0) { |
335 |
fprintf(stderr, "OOC_Sort: failed to fork subprocess\n"); |
336 |
return -1; |
337 |
} |
338 |
|
339 |
#ifdef DEBUG_OOC_FORK |
340 |
fprintf(stderr, "OOC_Sort: forking kid %d for block %d\n", |
341 |
procCnt, b); |
342 |
#endif |
343 |
|
344 |
/* Parent continues here */ |
345 |
procCnt++; |
346 |
} |
347 |
else { |
348 |
/* Recurse on subblock; without forking */ |
349 |
if (OOC_SortRecurse(in, blkLo2, blkHi2, blkFile [b], numBlk, |
350 |
maxBlkSize, numProc, recSize, sortBuf, |
351 |
pqueue, keyData)) |
352 |
return -1; |
353 |
} |
354 |
|
355 |
/* Prepare for next block */ |
356 |
blkLo2 = blkHi2 + 1; |
357 |
} |
358 |
|
359 |
/* !!! Wait for any forked processes to terminate */ |
360 |
while (procCnt && wait(&stat) >= 0) { |
361 |
if (!WIFEXITED(stat) || WEXITSTATUS(stat)) |
362 |
return -1; |
363 |
|
364 |
procCnt--; |
365 |
} |
366 |
|
367 |
/* =============================================================== |
368 |
* Subblocks are now sorted; prepare priority queue by peeking and |
369 |
* enqueueing first record from corresponding temporary file |
370 |
* =============================================================== */ |
371 |
|
372 |
#ifdef DEBUG_OOC_SORT |
373 |
fprintf(stderr, "OOC_Sort: merging block [%lu - %lu]\n", blkLo, blkHi); |
374 |
#endif |
375 |
|
376 |
for (b = 0; b < numBlk; b++) { |
377 |
#ifdef DEBUG_OOC_SORT |
378 |
fseek(blkFile [b], 0, SEEK_END); |
379 |
if (ftell(blkFile [b]) % recSize) { |
380 |
fprintf(stderr, "OOC_Sort: truncated record in tmp block " |
381 |
"file %d\n", b); |
382 |
return -1; |
383 |
} |
384 |
|
385 |
fprintf(stderr, "OOC_Sort: tmp block file %d contains %ld rec\n", |
386 |
b, ftell(blkFile [b]) / recSize); |
387 |
#endif |
388 |
|
389 |
rewind(blkFile [b]); |
390 |
|
391 |
if (OOC_SortPeek(blkFile [b], recSize, rec)) { |
392 |
fprintf(stderr, "OOC_Sort: error reading from block file\n"); |
393 |
return -1; |
394 |
} |
395 |
|
396 |
/* Enqueue record along with its Morton code as priority */ |
397 |
pri = OOC_Key2Morton(keyData -> key(rec), keyData -> bbOrg, |
398 |
keyData -> mortonScale); |
399 |
|
400 |
if (OOC_SortPush(pqueue, pri, b) < 0) { |
401 |
fprintf(stderr, "OOC_Sort: failed priority queue insertion\n"); |
402 |
return -1; |
403 |
} |
404 |
} |
405 |
|
406 |
/* ========================================================== |
407 |
* Subblocks now sorted and priority queue filled; merge from |
408 |
* temporary files |
409 |
* ========================================================== */ |
410 |
|
411 |
do { |
412 |
/* Get next node in priority queue, read next record in corresponding |
413 |
* block, and send to output */ |
414 |
b = OOC_SortPop(pqueue); |
415 |
|
416 |
if (b >= 0) { |
417 |
/* Priority queue non-empty */ |
418 |
if (OOC_SortRead(blkFile [b], recSize, rec)) { |
419 |
/* Corresponding record should still be in the input block */ |
420 |
fprintf(stderr, "OOC_Sort: unexpected end reading block file\n"); |
421 |
return -1; |
422 |
} |
423 |
|
424 |
if (OOC_SortWrite(out, recSize, rec)) { |
425 |
fprintf(stderr, "OOC_Sort; error writing output file\n"); |
426 |
return -1; |
427 |
} |
428 |
|
429 |
#ifdef DEBUG_OOC_SORT |
430 |
pqCnt++; |
431 |
#endif |
432 |
|
433 |
/* Peek next record from same block and insert in priority queue */ |
434 |
if (!OOC_SortPeek(blkFile [b], recSize, rec)) { |
435 |
/* Block not exhausted */ |
436 |
pri = OOC_Key2Morton(keyData -> key(rec), keyData -> bbOrg, |
437 |
keyData -> mortonScale); |
438 |
|
439 |
if (OOC_SortPush(pqueue, pri, b) < 0) { |
440 |
fprintf(stderr, "OOC_Sort: failed priority queue insert\n"); |
441 |
return -1; |
442 |
} |
443 |
} |
444 |
} |
445 |
} while (b >= 0); |
446 |
|
447 |
#ifdef DEBUG_OOC_SORT |
448 |
fprintf(stderr, "OOC_Sort: dequeued %lu rec\n", pqCnt); |
449 |
fprintf(stderr, "OOC_Sort: merged file contains %lu rec\n", |
450 |
ftell(out) / recSize); |
451 |
#endif |
452 |
|
453 |
/* Priority queue now empty -> done; close temporary subblock files, |
454 |
* causing them to be automatically deleted. */ |
455 |
for (b = 0; b < numBlk; b++) { |
456 |
fclose(blkFile [b]); |
457 |
} |
458 |
|
459 |
/* !!! Commit output file to disk before caller reads it; omitting |
460 |
* !!! this apparently leads to corrupted files (race condition?) when |
461 |
* !!! the caller tries to read them! */ |
462 |
fflush(out); |
463 |
fsync(fileno(out)); |
464 |
} |
465 |
|
466 |
else { |
467 |
/* ====================================== |
468 |
* Block is small enough for in-core sort |
469 |
* ====================================== */ |
470 |
int ifd = fileno(in), ofd = fileno(out); |
471 |
|
472 |
#ifdef DEBUG_OOC_SORT |
473 |
fprintf(stderr, "OOC_Sort: Proc %d (%d/%d) sorting block [%lu - %lu]\n", |
474 |
getpid(), procCnt, numProc - 1, blkLo, blkHi); |
475 |
|
476 |
#endif |
477 |
|
478 |
/* Atomically seek and read block into in-core sort buffer */ |
479 |
/* !!! Unbuffered I/O via pread() avoids potential race conditions |
480 |
* !!! and buffer corruption which can occur with lseek()/fseek() |
481 |
* !!! followed by read()/fread(). */ |
482 |
if (pread(ifd, sortBuf, blkSize, blkLo * recSize) != blkSize) { |
483 |
perror("OOC_Sort: error reading from input file"); |
484 |
return -1; |
485 |
} |
486 |
|
487 |
/* Quicksort block in-core and write to output file */ |
488 |
qsort(sortBuf, blkLen, recSize, OOC_KeyCompare); |
489 |
|
490 |
if (write(ofd, sortBuf, blkSize) != blkSize) { |
491 |
perror("OOC_Sort: error writing to block file"); |
492 |
return -1; |
493 |
} |
494 |
|
495 |
fsync(ofd); |
496 |
|
497 |
#ifdef DEBUG_OOC_SORT |
498 |
fprintf(stderr, "OOC_Sort: proc %d wrote %ld records\n", |
499 |
getpid(), lseek(ofd, 0, SEEK_END) / recSize); |
500 |
#endif |
501 |
} |
502 |
|
503 |
return 0; |
504 |
} |
505 |
|
506 |
|
507 |
|
508 |
int OOC_Sort (FILE *in, FILE *out, unsigned numBlk, |
509 |
unsigned long blkSize, unsigned numProc, unsigned recSize, |
510 |
FVECT bbOrg, RREAL bbSize, RREAL *(*key)(const void*)) |
511 |
/* Sort records in inFile and append to outFile by subdividing inFile into |
512 |
* small blocks, sorting these in-core, and merging them out-of-core via a |
513 |
* priority queue. |
514 |
* |
515 |
* This is implemented as a recursive (numBlk)-way sort; the input is |
516 |
* successively split into numBlk smaller blocks until these are of size <= |
517 |
* blkSize, i.e. small enough for in-core sorting, then merging the sorted |
518 |
* blocks as the stack unwinds. The in-core sort is parallelised over |
519 |
* numProx processes. |
520 |
* |
521 |
* Parameters are as follows: |
522 |
* inFile Opened input file containing unsorted records |
523 |
* outFile Opened output file containing sorted records |
524 |
* numBlk Number of blocks to divide into / merge from |
525 |
* blkSize Max block size and size of in-core sort buffer, in bytes |
526 |
* numProc Number of parallel processes for in-core sort |
527 |
* recSize Size of input records in bytes |
528 |
* bbOrg Origin of bounding box containing record keys for Morton code |
529 |
* bbSize Extent of bounding box containing record keys for Morton code |
530 |
* key Callback to access 3D coords from records for Morton code |
531 |
*/ |
532 |
{ |
533 |
unsigned long numRec; |
534 |
OOC_SortQueue pqueue; |
535 |
char *sortBuf = NULL; |
536 |
int stat; |
537 |
|
538 |
if (numBlk < 1) |
539 |
numBlk = 1; |
540 |
|
541 |
/* Open input file & get size in number of records */ |
542 |
if (fseek(in, 0, SEEK_END) < 0) { |
543 |
fputs("OOC_Sort: failed seek in input file\n", stderr); |
544 |
return -1; |
545 |
} |
546 |
|
547 |
if (!(numRec = ftell(in) / recSize)) { |
548 |
fputs("OOC_Sort: empty input file\n", stderr); |
549 |
return -1; |
550 |
} |
551 |
|
552 |
/* Allocate & init priority queue */ |
553 |
if (!(pqueue.node = calloc(numBlk, sizeof(OOC_SortQueueNode)))) { |
554 |
fputs("OOC_Sort: failure allocating priority queue\n", stderr); |
555 |
return -1; |
556 |
} |
557 |
pqueue.tail = 0; |
558 |
pqueue.len = numBlk; |
559 |
|
560 |
/* Allocate in-core sort buffa */ |
561 |
if (!(sortBuf = malloc(blkSize))) { |
562 |
fprintf(stderr, "OOC_Sort: failure allocating in-core sort buffer"); |
563 |
return -1; |
564 |
} |
565 |
|
566 |
/* Set up key data to pass to qsort()'s comparison func */ |
567 |
keyData.key = key; |
568 |
keyData.mortonScale = OOC_MORTON_MAX / bbSize; |
569 |
VCOPY(keyData.bbOrg, bbOrg); |
570 |
|
571 |
stat = OOC_SortRecurse(in, 0, numRec - 1, out, numBlk, blkSize, numProc, |
572 |
recSize, sortBuf, &pqueue, &keyData); |
573 |
|
574 |
/* Cleanup */ |
575 |
free(pqueue.node); |
576 |
free(sortBuf); |
577 |
|
578 |
return stat; |
579 |
} |
580 |
|
581 |
#endif /* NIX / PMAP_OOC */ |