1 |
/* |
2 |
======================================================================= |
3 |
Cache for out-of-core octree. |
4 |
|
5 |
Uses an LRU page replacement scheme. Page table nodes are stored in |
6 |
order of reference in a doubly linked list, with the most recently used |
7 |
(MRU) page at the head, and the least recently used (LRU) at the tail. |
8 |
|
9 |
Nodes are referenced by the page's base address via a hashtable for |
10 |
constant time access (in the absence of hash collisions). Hash |
11 |
collisions can be limited by adjusting the hashtable load factor |
12 |
OOC_CACHE_LOAD; this is the fraction of the number of pages that will |
13 |
actually be cached. |
14 |
|
15 |
Roland Schregle (roland.schregle@{hslu.ch, gmail.com}) |
16 |
(c) Lucerne University of Applied Sciences and Arts, |
17 |
supported by the Swiss National Science Foundation (SNSF, #147053) |
18 |
======================================================================= |
19 |
|
20 |
$Id: ooccache.h,v 1.13 2015/11/16 13:33:08 taschreg Exp taschreg $ |
21 |
*/ |
22 |
|
23 |
|
24 |
#ifndef OOC_CACHE_H |
25 |
#define OOC_CACHE_H |
26 |
|
27 |
#include <stdio.h> |
28 |
#include <stdint.h> |
29 |
|
30 |
|
31 |
|
32 |
/* Hashtable load factor to limit hash collisions */ |
33 |
#define OOC_CACHE_LOAD 0.75 |
34 |
|
35 |
/* Minimum number of cache pages */ |
36 |
#define OOC_CACHE_MINPAGES 8 |
37 |
|
38 |
/* Hashing function for key -> pagetable mapping (assumes n is prime) */ |
39 |
#define OOC_CACHE_PRIME 19603 |
40 |
#define OOC_CACHE_HASH(k,n) ((k) * OOC_CACHE_PRIME % (n)) |
41 |
|
42 |
/* Next index in pagetable probe sequence for collision resolution */ |
43 |
#define OOC_CACHE_NEXT(i,n) (((i) + 1) % (n)) |
44 |
|
45 |
/* Cache key and index types */ |
46 |
typedef uint32_t OOC_CacheKey; |
47 |
typedef uint32_t OOC_CacheIdx; |
48 |
|
49 |
/* Undefined value for cache index */ |
50 |
#define OOC_CACHEIDX_NULL UINT32_MAX |
51 |
|
52 |
|
53 |
|
54 |
typedef struct { |
55 |
OOC_CacheKey key; /* Key to resolve hashing collisions */ |
56 |
OOC_CacheIdx prev, next; /* Previous/next page in history */ |
57 |
void *data; /* Start of page data */ |
58 |
} OOC_CacheNode; |
59 |
|
60 |
typedef struct { |
61 |
unsigned recSize, /* Data record size in bytes */ |
62 |
recPerPage; /* Page size in number of records */ |
63 |
unsigned long pageSize; /* Page size in bytes (precomp) */ |
64 |
OOC_CacheIdx pageCnt, /* Num pages used */ |
65 |
numPages; /* Pagetable size */ |
66 |
|
67 |
/* NOTE: The hashtable load factor limits the number of pages actually |
68 |
* used, such that pageCnt <= OOC_CACHE_LOAD * numPages */ |
69 |
|
70 |
OOC_CacheNode *pageTable; /* Pagetable with numPages nodes */ |
71 |
OOC_CacheIdx mru, lru; /* Most/least recently used page |
72 |
== head/tail of page history */ |
73 |
OOC_CacheKey lastKey; /* Previous key to detect repeat lookups */ |
74 |
OOC_CacheNode *lastPage; /* Previous page for repeat lookups */ |
75 |
|
76 |
unsigned long numReads, /* Statistics counters */ |
77 |
numHits, |
78 |
numColl, |
79 |
numRept; |
80 |
} OOC_Cache; |
81 |
|
82 |
|
83 |
|
84 |
/* Initialise cache containing up to numPages pages; this is rounded up |
85 |
* the next prime number to reduce hash clustering and collisions. The |
86 |
* page size recPerPage is specified in units of records of size recSize |
87 |
* bytes. Returns 0 on success, else -1. */ |
88 |
int OOC_CacheInit (OOC_Cache *cache, unsigned numPages, |
89 |
unsigned recPerPage, unsigned recSize); |
90 |
|
91 |
/* Return pointer to cached record with index recIdx, loading from file |
92 |
* and possibly evicting the LRU page */ |
93 |
void *OOC_CacheData (OOC_Cache *cache, FILE *file, unsigned long recIdx); |
94 |
|
95 |
/* Delete cache and free allocated pages */ |
96 |
void OOC_DeleteCache (OOC_Cache *cache); |
97 |
#endif |