1 |
rschregle |
2.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 |