src/rt/ooccache.c

#ifndef lint
static const char RCSid[] = "$Id$";
#endif


/* 
   =======================================================================
   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 2.1 2016/05/17 17:39:47 rschregle Exp $
*/


#if !defined(_WIN32) && !defined(_WIN64) || defined(PMAP_OOC)
/* No Windoze support for now */

#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;
}

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