src/rt/ooccache.c

/* 
   =======================================================================
   Cache for out-of-core octree.
   
   Uses an LRU page replacement scheme. Page table nodes are stored in
   order of reference in a doubly linked list, with the most recently used
   (MRU) page at the head, and the least recently used (LRU) at the tail.

   Nodes are referenced by the page's base address via a hashtable for
   constant time access (in the absence of hash collisions).  Hash
   collisions can be limited by adjusting the hashtable load factor
   OOC_CACHE_LOAD; this is the fraction of the number of pages that will
   actually be cached.
   
   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: ooccache.c,v 1.12 2015/11/16 13:33:13 taschreg Exp taschreg $
*/


#include <stdlib.h>
#include <unistd.h>
#include "ooccache.h"


static OOC_CacheIdx OOC_PrevPrime (OOC_CacheIdx n)
/* Return largest prime number <= n */
{
   OOC_CacheIdx n2 = n + 1, i;
   
   do {
      n2--;
      for (i = 2; n2 % i && i <= n2 >> 1; i++);
   } while (!(n2 % i));
   
   return n2;
}


int OOC_CacheInit (OOC_Cache *cache, unsigned numPages, 
                   unsigned recPerPage, unsigned recSize)
{
   OOC_CacheIdx i;

   if (!cache)
      return -1;

   /* Clamp number of pages if necessary */
   if (numPages < OOC_CACHE_MINPAGES) {
      numPages = OOC_CACHE_MINPAGES;
      fputs("OOC_CacheInit: clamping num pages to min\n", stderr);
   }
      
   if (numPages >= OOC_CACHEIDX_NULL) {
      numPages = OOC_CACHEIDX_NULL - 1;
      fputs("OOC_CacheInit: clamping num pages to max\n", stderr); 
   }

   /* Round numPages to next prime to reduce hash clustering & collisions */      
   numPages = OOC_PrevPrime(numPages);
      
   cache -> recPerPage = recPerPage;
   cache -> numPages = numPages;
   cache -> recSize = recSize;
   cache -> pageSize = (unsigned long)cache -> recPerPage * 
                       cache -> recSize;
   cache -> pageCnt = 0;
   cache -> numHits = cache -> numReads = cache -> numColl = 
      cache -> numRept = 0;
   cache -> mru = cache -> lru = OOC_CACHEIDX_NULL;
   cache -> lastKey = 0;
   cache -> lastPage = NULL;
   
   /* Allocate & init hashtable */
   if (!(cache -> pageTable = calloc(numPages, sizeof(OOC_CacheNode)))) {
      perror("OOC_InitCache: failed pagetable allocation");
      return -1;
   }
   
   for (i = 0; i < numPages; i++) {
      cache -> pageTable [i].data = NULL;
      cache -> pageTable [i].key = 0;
      cache -> pageTable [i].prev = cache -> pageTable [i].next = 
         OOC_CACHEIDX_NULL;
   }
   
#ifdef OOC_CACHE_STATS
   fprintf(stderr, 
           "OOC_InitCache: caching %d pages @ %d records (%.2f Mb)\n",
           cache -> numPages, cache -> recPerPage, 
           (float)cache -> numPages * cache -> pageSize / (1L << 20));
#endif 
  
   return 0;
}       


static OOC_CacheIdx OOC_CacheFind (OOC_Cache *cache, OOC_CacheKey key)
/* Return index to pagetable node for given key; collisions are resolved
 * via the probe sequence defined by OOC_CACHE_NEXT() */ 
{
   OOC_CacheIdx   idx = OOC_CACHE_HASH(key, cache -> numPages);
   OOC_CacheNode  *page = cache -> pageTable + idx;

   /* Find matching pagetable node starting from idx and stop at the first
    * empty node; a full table would result in an infinite loop! */
   while (page -> data && page -> key != key) {
      idx = OOC_CACHE_NEXT(idx, cache -> numPages);
      page = cache -> pageTable + idx;
      cache -> numColl++;
   }

   return idx;
}


static void OOC_CacheUnlink (OOC_Cache *cache, OOC_CacheIdx pageIdx)
/* Unlink page from history chain, updating LRU in cache if necessary */
{
   OOC_CacheNode  *page = cache -> pageTable + pageIdx;
   
   /* Unlink prev/next index */
   if (page -> prev != OOC_CACHEIDX_NULL)
      cache -> pageTable [page -> prev].next = page -> next;
      
   if (page -> next != OOC_CACHEIDX_NULL)
      cache -> pageTable [page -> next].prev = page -> prev;
     
   /* Update LRU index */ 
   if (pageIdx == cache -> lru)
      cache -> lru = page -> prev;
}


static void OOC_CacheRelink (OOC_Cache *cache, OOC_CacheIdx pageIdx)
/* Update history chain with new page index */
{
   OOC_CacheNode  *page = cache -> pageTable + pageIdx;
   
   if (page -> prev != OOC_CACHEIDX_NULL)
      cache -> pageTable [page -> prev].next = pageIdx;
      
   if (page -> next != OOC_CACHEIDX_NULL)
      cache -> pageTable [page -> next].prev = pageIdx;
}      


static void OOC_CacheSetMRU (OOC_Cache *cache, OOC_CacheIdx pageIdx)
/* Set page as most recently used and move to head of history chain */
{
   OOC_CacheNode  *page = cache -> pageTable + pageIdx;
   
   OOC_CacheUnlink(cache, pageIdx);
   page -> prev = OOC_CACHEIDX_NULL;
   page -> next = cache -> mru;
   cache -> pageTable [cache -> mru].prev = pageIdx;
   cache -> mru = pageIdx;
}


static void *OOC_CacheDelete (OOC_Cache *cache, OOC_CacheIdx pageIdx)
/* Delete cache node at pageIdx and tidy up fragmentation in pagetable to
 * minimise collisions.  Returns pointer to deleted node's page data
 *
 * !!! Note cache -> pageCnt is NOT decremented as this is immediately
 * !!! followed by a call to OOC_CacheNew() in OOC_CacheData() */
{
   OOC_CacheNode  *page = cache -> pageTable + pageIdx, *nextPage;
   OOC_CacheIdx   nextIdx;
   void           *delData = page -> data, *nextData;
   
   /* Unlink page from history chain */
   OOC_CacheUnlink(cache, pageIdx);
   
   /* Free pagetable node */
   page -> data = NULL;
   
   nextIdx = OOC_CACHE_NEXT(pageIdx, cache -> numPages);
   nextPage = cache -> pageTable + nextIdx;
   
   /* Close gaps in probe sequence until empty node found */
   while ((nextData = nextPage -> data)) {
      /* Mark next node as free and reprobe for its key */
      nextPage -> data = NULL;
      pageIdx = OOC_CacheFind(cache, nextPage -> key);
      page = cache -> pageTable + pageIdx;
      
      /* Set page data pointer & reactivate page */
      page -> data = nextData;
      
      if (pageIdx != nextIdx) {
         /* Next page maps to freed node; relocate to close gap and update
          * history chain and LRU/MRU if necessary */
         page -> key = nextPage -> key;         /* memcpy() faster ? */
         page -> prev = nextPage -> prev;
         page -> next = nextPage -> next;
         OOC_CacheRelink(cache, pageIdx);
         
         if (cache -> lru == nextIdx)
            cache -> lru = pageIdx;
            
         if (cache -> mru == nextIdx)
            cache -> mru = pageIdx;
      }
            
      nextIdx = OOC_CACHE_NEXT(nextIdx, cache -> numPages);
      nextPage = cache -> pageTable + nextIdx;      
   }
   
   return delData;
}


static OOC_CacheNode *OOC_CacheNew (OOC_Cache *cache, OOC_CacheIdx pageIdx, 
                                    OOC_CacheKey pageKey, void *pageData)
/* Init new pagetable node with given index, key and data. Returns pointer
 * to new node */
{
   OOC_CacheNode  *page = cache -> pageTable + pageIdx;
   
   page -> prev = page -> next = OOC_CACHEIDX_NULL;
   page -> key = pageKey;
   page -> data = pageData;
   
   return page;
}
 
   
#ifdef OOC_CACHE_CHECK
static int OOC_CacheCheck (OOC_Cache *cache)
/* Run sanity checks on hashtable and page list */
{
   OOC_CacheIdx   i, pageCnt = 0;
   OOC_CacheNode  *page;
   
   /* Check pagetable mapping */
   for (i = 0, page = cache->pageTable; i < cache->numPages; i++, page++)
      if (page -> data) {
         /* Check hash func maps page key to this node */
         if (OOC_CacheFind(cache, page -> key) != i) {
            fputs("OOC_CacheCheck: hashing inconsistency\n", stderr);
            return -1;
         }
         
         pageCnt++;
      }

   if (pageCnt != cache -> pageCnt) {
      fputs("OOC_CacheCheck: pagetable count inconsistency\n", stderr);
      return -1;
   }
      
   if (cache -> mru == OOC_CACHEIDX_NULL || 
       cache -> lru == OOC_CACHEIDX_NULL) {
      fputs("OOC_CacheCheck: undefined MRU/LRU\n", stderr);
      return -1;
   }

   pageCnt = 0;
   i = cache -> mru;
   
   /* Check page history */
   while (i != OOC_CACHEIDX_NULL) {
      /* Check link to previous page (should be none for MRU) */
      page = cache -> pageTable + i;
      
      if (i == cache -> mru)
         if (page -> prev != OOC_CACHEIDX_NULL) {
            fputs("OOC_CacheCheck: MRU inconsistency\n", stderr);
            return -1;
         }
         else;
      else if (page -> prev == OOC_CACHEIDX_NULL || 
               cache -> pageTable [page -> prev].next != i) {
         fputs("OOC_CacheCheck: prev page inconsistency\n", stderr);
         return -1;
      }
      
      /* Check link to next page node (should be none for LRU) */
      if (i == cache -> lru)
         if (page -> next != OOC_CACHEIDX_NULL) {
            fputs("OOC_CacheCheck: LRU inconsistency\n", stderr);
            return -1;
         }
         else;
      else if (page -> next != OOC_CACHEIDX_NULL &&
               cache -> pageTable [page -> next].prev != i) {
         fputs("OOC_CacheCheck: next page inconsistency\n", stderr);
         return -1;
      }
      
      /* Check LRU is at tail of page history */
      if (page -> next == OOC_CACHEIDX_NULL && i != cache -> lru) {
         fputs("OOC_CacheCheck: page history tail not LRU\n", stderr);
         return -1;
      }
      
      i = page -> next;
      pageCnt++;
   }
   
   if (pageCnt != cache -> pageCnt) {
      fputs("OOC_CacheCheck: page history count inconsistency\n", stderr);
      return -1;
   }
   
   return 0;
}
#endif


void *OOC_CacheData (OOC_Cache *cache, FILE *file, unsigned long recIdx)
{
   const  OOC_CacheKey  pageKey = recIdx / cache -> recPerPage;
   OOC_CacheNode        *page = NULL;

   /* We assume locality of reference, and that it's likely the same page
    * will therefore be accessed sequentially; in this case we just reuse
    * the pagetable index */
   if (pageKey != cache -> lastKey || !cache -> pageCnt) {
      OOC_CacheIdx   pageIdx = OOC_CacheFind(cache, pageKey);
      void           *pageData;
      
      page = cache -> pageTable + pageIdx;
      
      if (!page -> data) {
         /* Page not cached; insert in pagetable */
         const unsigned long  filePos = cache -> pageSize * pageKey;
            
         if (cache -> pageCnt < OOC_CACHE_LOAD * cache -> numPages) {
            /* Cache not fully loaded; allocate new page data */
            if (!(pageData = calloc(cache -> recPerPage, cache -> recSize))) {
               perror("OOC_CacheData: failed page allocation");
               return NULL;
            }
            
            /* Init LRU and MRU if necessary */
            if (cache -> mru == OOC_CACHEIDX_NULL ||  
                cache -> lru == OOC_CACHEIDX_NULL)
               cache -> mru = cache -> lru = pageIdx;
               
            cache -> pageCnt++;
         }
         else {
            /* Cache fully loaded; adding more entries would aggravate
             * hash collisions, so evict LRU page. We reuse its
             * allocated page data and then overwrite it. */
            pageData = OOC_CacheDelete(cache, cache -> lru);
            
            /* Update page index as it may have moved forward in probe
             * sequence after deletion */
            pageIdx = OOC_CacheFind(cache, pageKey);
         }
         
         /* Init new pagetable node, will be linked in history below */
         page = OOC_CacheNew(cache, pageIdx, pageKey, pageData);
         
         /* Load page data from file; the last page may be truncated */
         if (!pread(fileno(file), page -> data, cache -> pageSize, filePos)) {
            fputs("OOC_CacheData: failed seek/read from data stream", stderr);
            return NULL;
         }
      }
      else 
         /* Page in cache */
         cache -> numHits++;

      if (cache -> mru != pageIdx)
         /* Cached page is now most recently used; unlink and move to front
          * of history chain and update MRU */
         OOC_CacheSetMRU(cache, pageIdx);
      
      /* Update last page to detect repeat accesses */
      cache -> lastKey = pageKey;
      cache -> lastPage = page;
   }
   else {
      /* Repeated page, skip hashing and just reuse last page */
      page = cache -> lastPage;
      cache -> numHits++;
      cache -> numRept++;
   }
   
   cache -> numReads++;

#ifdef OOC_CACHE_CHECK
   if (OOC_CacheCheck(cache))
      return NULL;
#endif
           
   /* Return pointer to record within cached page */
   return page -> data + (recIdx % cache -> recPerPage) * cache -> recSize;
}

   
void OOC_DeleteCache (OOC_Cache *cache)
{
   OOC_CacheIdx   i;

   for (i = 0; i < cache -> numPages; i++)
      if (cache -> pageTable [i].data)
         free(cache -> pageTable [i].data);
         
   free(cache -> pageTable);
   cache -> pageTable = NULL;
   cache -> pageCnt = 0;
   cache -> mru = cache -> lru = OOC_CACHEIDX_NULL;
}
Revision:	2.1
Committed:	Tue May 17 17:39:47 2016 UTC (9 years, 5 months ago) by rschregle
Content type:	text/plain
Branch:	MAIN
Log Message:	Initial import of ooC photon map
#	User	Rev	Content
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.c,v 1.12 2015/11/16 13:33:13 taschreg Exp taschreg $
21			*/
22
23
24			#include <stdlib.h>
25			#include <unistd.h>
26			#include "ooccache.h"
27
28
29
30			static OOC_CacheIdx OOC_PrevPrime (OOC_CacheIdx n)
31			/* Return largest prime number <= n */
32			{
33			OOC_CacheIdx n2 = n + 1, i;
34
35			do {
36			n2--;
37			for (i = 2; n2 % i && i <= n2 >> 1; i++);
38			} while (!(n2 % i));
39
40			return n2;
41			}
42
43
44
45			int OOC_CacheInit (OOC_Cache *cache, unsigned numPages,
46			unsigned recPerPage, unsigned recSize)
47			{
48			OOC_CacheIdx i;
49
50			if (!cache)
51			return -1;
52
53			/* Clamp number of pages if necessary */
54			if (numPages < OOC_CACHE_MINPAGES) {
55			numPages = OOC_CACHE_MINPAGES;
56			fputs("OOC_CacheInit: clamping num pages to min\n", stderr);
57			}
58
59			if (numPages >= OOC_CACHEIDX_NULL) {
60			numPages = OOC_CACHEIDX_NULL - 1;
61			fputs("OOC_CacheInit: clamping num pages to max\n", stderr);
62			}
63
64			/* Round numPages to next prime to reduce hash clustering & collisions */
65			numPages = OOC_PrevPrime(numPages);
66
67			cache -> recPerPage = recPerPage;
68			cache -> numPages = numPages;
69			cache -> recSize = recSize;
70			cache -> pageSize = (unsigned long)cache -> recPerPage *
71			cache -> recSize;
72			cache -> pageCnt = 0;
73			cache -> numHits = cache -> numReads = cache -> numColl =
74			cache -> numRept = 0;
75			cache -> mru = cache -> lru = OOC_CACHEIDX_NULL;
76			cache -> lastKey = 0;
77			cache -> lastPage = NULL;
78
79			/* Allocate & init hashtable */
80			if (!(cache -> pageTable = calloc(numPages, sizeof(OOC_CacheNode)))) {
81			perror("OOC_InitCache: failed pagetable allocation");
82			return -1;
83			}
84
85			for (i = 0; i < numPages; i++) {
86			cache -> pageTable [i].data = NULL;
87			cache -> pageTable [i].key = 0;
88			cache -> pageTable [i].prev = cache -> pageTable [i].next =
89			OOC_CACHEIDX_NULL;
90			}
91
92			#ifdef OOC_CACHE_STATS
93			fprintf(stderr,
94			"OOC_InitCache: caching %d pages @ %d records (%.2f Mb)\n",
95			cache -> numPages, cache -> recPerPage,
96			(float)cache -> numPages * cache -> pageSize / (1L << 20));
97			#endif
98
99			return 0;
100			}
101
102
103
104			static OOC_CacheIdx OOC_CacheFind (OOC_Cache *cache, OOC_CacheKey key)
105			/* Return index to pagetable node for given key; collisions are resolved
106			* via the probe sequence defined by OOC_CACHE_NEXT() */
107			{
108			OOC_CacheIdx idx = OOC_CACHE_HASH(key, cache -> numPages);
109			OOC_CacheNode *page = cache -> pageTable + idx;
110
111			/* Find matching pagetable node starting from idx and stop at the first
112			* empty node; a full table would result in an infinite loop! */
113			while (page -> data && page -> key != key) {
114			idx = OOC_CACHE_NEXT(idx, cache -> numPages);
115			page = cache -> pageTable + idx;
116			cache -> numColl++;
117			}
118
119			return idx;
120			}
121
122
123
124			static void OOC_CacheUnlink (OOC_Cache *cache, OOC_CacheIdx pageIdx)
125			/* Unlink page from history chain, updating LRU in cache if necessary */
126			{
127			OOC_CacheNode *page = cache -> pageTable + pageIdx;
128
129			/* Unlink prev/next index */
130			if (page -> prev != OOC_CACHEIDX_NULL)
131			cache -> pageTable [page -> prev].next = page -> next;
132
133			if (page -> next != OOC_CACHEIDX_NULL)
134			cache -> pageTable [page -> next].prev = page -> prev;
135
136			/* Update LRU index */
137			if (pageIdx == cache -> lru)
138			cache -> lru = page -> prev;
139			}
140
141
142
143			static void OOC_CacheRelink (OOC_Cache *cache, OOC_CacheIdx pageIdx)
144			/* Update history chain with new page index */
145			{
146			OOC_CacheNode *page = cache -> pageTable + pageIdx;
147
148			if (page -> prev != OOC_CACHEIDX_NULL)
149			cache -> pageTable [page -> prev].next = pageIdx;
150
151			if (page -> next != OOC_CACHEIDX_NULL)
152			cache -> pageTable [page -> next].prev = pageIdx;
153			}
154
155
156
157			static void OOC_CacheSetMRU (OOC_Cache *cache, OOC_CacheIdx pageIdx)
158			/* Set page as most recently used and move to head of history chain */
159			{
160			OOC_CacheNode *page = cache -> pageTable + pageIdx;
161
162			OOC_CacheUnlink(cache, pageIdx);
163			page -> prev = OOC_CACHEIDX_NULL;
164			page -> next = cache -> mru;
165			cache -> pageTable [cache -> mru].prev = pageIdx;
166			cache -> mru = pageIdx;
167			}
168
169
170
171			static void OOC_CacheDelete (OOC_Cache cache, OOC_CacheIdx pageIdx)
172			/* Delete cache node at pageIdx and tidy up fragmentation in pagetable to
173			* minimise collisions. Returns pointer to deleted node's page data
174			*
175			* !!! Note cache -> pageCnt is NOT decremented as this is immediately
176			* !!! followed by a call to OOC_CacheNew() in OOC_CacheData() */
177			{
178			OOC_CacheNode page = cache -> pageTable + pageIdx, nextPage;
179			OOC_CacheIdx nextIdx;
180			void delData = page -> data, nextData;
181
182			/* Unlink page from history chain */
183			OOC_CacheUnlink(cache, pageIdx);
184
185			/* Free pagetable node */
186			page -> data = NULL;
187
188			nextIdx = OOC_CACHE_NEXT(pageIdx, cache -> numPages);
189			nextPage = cache -> pageTable + nextIdx;
190
191			/* Close gaps in probe sequence until empty node found */
192			while ((nextData = nextPage -> data)) {
193			/* Mark next node as free and reprobe for its key */
194			nextPage -> data = NULL;
195			pageIdx = OOC_CacheFind(cache, nextPage -> key);
196			page = cache -> pageTable + pageIdx;
197
198			/* Set page data pointer & reactivate page */
199			page -> data = nextData;
200
201			if (pageIdx != nextIdx) {
202			/* Next page maps to freed node; relocate to close gap and update
203			* history chain and LRU/MRU if necessary */
204			page -> key = nextPage -> key; /* memcpy() faster ? */
205			page -> prev = nextPage -> prev;
206			page -> next = nextPage -> next;
207			OOC_CacheRelink(cache, pageIdx);
208
209			if (cache -> lru == nextIdx)
210			cache -> lru = pageIdx;
211
212			if (cache -> mru == nextIdx)
213			cache -> mru = pageIdx;
214			}
215
216			nextIdx = OOC_CACHE_NEXT(nextIdx, cache -> numPages);
217			nextPage = cache -> pageTable + nextIdx;
218			}
219
220			return delData;
221			}
222
223
224
225			static OOC_CacheNode OOC_CacheNew (OOC_Cache cache, OOC_CacheIdx pageIdx,
226			OOC_CacheKey pageKey, void *pageData)
227			/* Init new pagetable node with given index, key and data. Returns pointer
228			* to new node */
229			{
230			OOC_CacheNode *page = cache -> pageTable + pageIdx;
231
232			page -> prev = page -> next = OOC_CACHEIDX_NULL;
233			page -> key = pageKey;
234			page -> data = pageData;
235
236			return page;
237			}
238
239
240
241			#ifdef OOC_CACHE_CHECK
242			static int OOC_CacheCheck (OOC_Cache *cache)
243			/* Run sanity checks on hashtable and page list */
244			{
245			OOC_CacheIdx i, pageCnt = 0;
246			OOC_CacheNode *page;
247
248			/* Check pagetable mapping */
249			for (i = 0, page = cache->pageTable; i < cache->numPages; i++, page++)
250			if (page -> data) {
251			/* Check hash func maps page key to this node */
252			if (OOC_CacheFind(cache, page -> key) != i) {
253			fputs("OOC_CacheCheck: hashing inconsistency\n", stderr);
254			return -1;
255			}
256
257			pageCnt++;
258			}
259
260			if (pageCnt != cache -> pageCnt) {
261			fputs("OOC_CacheCheck: pagetable count inconsistency\n", stderr);
262			return -1;
263			}
264
265			if (cache -> mru == OOC_CACHEIDX_NULL \|\|
266			cache -> lru == OOC_CACHEIDX_NULL) {
267			fputs("OOC_CacheCheck: undefined MRU/LRU\n", stderr);
268			return -1;
269			}
270
271			pageCnt = 0;
272			i = cache -> mru;
273
274			/* Check page history */
275			while (i != OOC_CACHEIDX_NULL) {
276			/* Check link to previous page (should be none for MRU) */
277			page = cache -> pageTable + i;
278
279			if (i == cache -> mru)
280			if (page -> prev != OOC_CACHEIDX_NULL) {
281			fputs("OOC_CacheCheck: MRU inconsistency\n", stderr);
282			return -1;
283			}
284			else;
285			else if (page -> prev == OOC_CACHEIDX_NULL \|\|
286			cache -> pageTable [page -> prev].next != i) {
287			fputs("OOC_CacheCheck: prev page inconsistency\n", stderr);
288			return -1;
289			}
290
291			/* Check link to next page node (should be none for LRU) */
292			if (i == cache -> lru)
293			if (page -> next != OOC_CACHEIDX_NULL) {
294			fputs("OOC_CacheCheck: LRU inconsistency\n", stderr);
295			return -1;
296			}
297			else;
298			else if (page -> next != OOC_CACHEIDX_NULL &&
299			cache -> pageTable [page -> next].prev != i) {
300			fputs("OOC_CacheCheck: next page inconsistency\n", stderr);
301			return -1;
302			}
303
304			/* Check LRU is at tail of page history */
305			if (page -> next == OOC_CACHEIDX_NULL && i != cache -> lru) {
306			fputs("OOC_CacheCheck: page history tail not LRU\n", stderr);
307			return -1;
308			}
309
310			i = page -> next;
311			pageCnt++;
312			}
313
314			if (pageCnt != cache -> pageCnt) {
315			fputs("OOC_CacheCheck: page history count inconsistency\n", stderr);
316			return -1;
317			}
318
319			return 0;
320			}
321			#endif
322
323
324
325			void OOC_CacheData (OOC_Cache cache, FILE *file, unsigned long recIdx)
326			{
327			const OOC_CacheKey pageKey = recIdx / cache -> recPerPage;
328			OOC_CacheNode *page = NULL;
329
330			/* We assume locality of reference, and that it's likely the same page
331			* will therefore be accessed sequentially; in this case we just reuse
332			* the pagetable index */
333			if (pageKey != cache -> lastKey \|\| !cache -> pageCnt) {
334			OOC_CacheIdx pageIdx = OOC_CacheFind(cache, pageKey);
335			void *pageData;
336
337			page = cache -> pageTable + pageIdx;
338
339			if (!page -> data) {
340			/* Page not cached; insert in pagetable */
341			const unsigned long filePos = cache -> pageSize * pageKey;
342
343			if (cache -> pageCnt < OOC_CACHE_LOAD * cache -> numPages) {
344			/* Cache not fully loaded; allocate new page data */
345			if (!(pageData = calloc(cache -> recPerPage, cache -> recSize))) {
346			perror("OOC_CacheData: failed page allocation");
347			return NULL;
348			}
349
350			/* Init LRU and MRU if necessary */
351			if (cache -> mru == OOC_CACHEIDX_NULL \|\|
352			cache -> lru == OOC_CACHEIDX_NULL)
353			cache -> mru = cache -> lru = pageIdx;
354
355			cache -> pageCnt++;
356			}
357			else {
358			/* Cache fully loaded; adding more entries would aggravate
359			* hash collisions, so evict LRU page. We reuse its
360			* allocated page data and then overwrite it. */
361			pageData = OOC_CacheDelete(cache, cache -> lru);
362
363			/* Update page index as it may have moved forward in probe
364			* sequence after deletion */
365			pageIdx = OOC_CacheFind(cache, pageKey);
366			}
367
368			/* Init new pagetable node, will be linked in history below */
369			page = OOC_CacheNew(cache, pageIdx, pageKey, pageData);
370
371			/* Load page data from file; the last page may be truncated */
372			if (!pread(fileno(file), page -> data, cache -> pageSize, filePos)) {
373			fputs("OOC_CacheData: failed seek/read from data stream", stderr);
374			return NULL;
375			}
376			}
377			else
378			/* Page in cache */
379			cache -> numHits++;
380
381			if (cache -> mru != pageIdx)
382			/* Cached page is now most recently used; unlink and move to front
383			* of history chain and update MRU */
384			OOC_CacheSetMRU(cache, pageIdx);
385
386			/* Update last page to detect repeat accesses */
387			cache -> lastKey = pageKey;
388			cache -> lastPage = page;
389			}
390			else {
391			/* Repeated page, skip hashing and just reuse last page */
392			page = cache -> lastPage;
393			cache -> numHits++;
394			cache -> numRept++;
395			}
396
397			cache -> numReads++;
398
399			#ifdef OOC_CACHE_CHECK
400			if (OOC_CacheCheck(cache))
401			return NULL;
402			#endif
403
404			/* Return pointer to record within cached page */
405			return page -> data + (recIdx % cache -> recPerPage) * cache -> recSize;
406			}
407
408
409
410			void OOC_DeleteCache (OOC_Cache *cache)
411			{
412			OOC_CacheIdx i;
413
414			for (i = 0; i < cache -> numPages; i++)
415			if (cache -> pageTable [i].data)
416			free(cache -> pageTable [i].data);
417
418			free(cache -> pageTable);
419			cache -> pageTable = NULL;
420			cache -> pageCnt = 0;
421			cache -> mru = cache -> lru = OOC_CACHEIDX_NULL;
422			}