| 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 |
