|
|
1.1 root 1: /*
2: * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
3: *
4: * @APPLE_LICENSE_HEADER_START@
5: *
6: * Portions Copyright (c) 1999 Apple Computer, Inc. All Rights
7: * Reserved. This file contains Original Code and/or Modifications of
8: * Original Code as defined in and that are subject to the Apple Public
9: * Source License Version 1.1 (the "License"). You may not use this file
10: * except in compliance with the License. Please obtain a copy of the
11: * License at http://www.apple.com/publicsource and read it before using
12: * this file.
13: *
14: * The Original Code and all software distributed under the License are
15: * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
16: * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
17: * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
18: * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
19: * License for the specific language governing rights and limitations
20: * under the License.
21: *
22: * @APPLE_LICENSE_HEADER_END@
23: */
24:
25: /*
26: File: GenericMRUCache.c
27:
28: Contains: Contains cache accessor routines based on MRU / LRU ordering.
29:
30: Version: HFS+ 1.0
31:
32: Copyright: � 1997-1998 by Apple Computer, Inc., all rights reserved.
33:
34: File Ownership:
35:
36: DRI: Deric Horn
37:
38: Other Contact: Don Brady
39:
40: Technology: HFS+
41:
42: Writers:
43:
44: (DSH) Deric Horn
45:
46: Change History (most recent first):
47:
48: <CS2> 1/29/98 DSH Add TrashMRUCache for TrashAllFSCaches API support.
49: <CS1> 7/25/97 DSH first checked in
50: */
51:
52: #if ( PRAGMA_LOAD_SUPPORTED )
53: #pragma load PrecompiledHeaders
54: #else
55: #if TARGET_OS_MAC
56: #include <MacMemory.h>
57: #include <stddef.h>
58: #else
59: #include "../headers/system/MacOSStubs.h"
60: #endif /* TARGET_OS_MAC */
61: #endif /* PRAGMA_LOAD_SUPPORTED */
62:
63: #include "../headers/FileMgrInternal.h"
64:
65: enum {
66: // error codes
67: errNotInCache = -123,
68: errInvalidKey = -124
69: };
70:
71:
72: struct CacheBlock {
73: struct CacheBlock *nextMRU; // next node in MRU order
74: struct CacheBlock *nextLRU; // next node in LRU order
75: UInt32 flags; // status flags
76: UInt32 key; // comparrison Key
77: char buffer[1]; // user defineable data
78: };
79: typedef struct CacheBlock CacheBlock;
80:
81: struct CacheGlobals {
82: UInt32 cacheBlockSize; // Size of CacheBlock structure including the buffer
83: UInt32 cacheBufferSize; // Size of cache buffer
84: UInt32 numCacheBlocks; // Number of blocks in cache
85: CacheBlock *mru;
86: CacheBlock *lru;
87: };
88: typedef struct CacheGlobals CacheGlobals;
89:
90:
91: //
92: // Internal routines
93: //
94: static void InsertAsMRU ( CacheGlobals *cacheGlobals, CacheBlock *cacheBlock );
95: static void InsertAsLRU ( CacheGlobals *cacheGlobals, CacheBlock *cacheBlock );
96:
97:
98: //
99: // Diagram of Cache structures
100: //
101: // _______ ________ ________ ________
102: // |data | | buff | | buff | | buff |
103: // | mru |-----> | nMRU |-----> | nMRU |--> ��� --->| nMRU |-->�
104: // | lru |-\ �<-| nLRU | <-----| nLRU |<-- ��� <---| nLRU |
105: // ------- \ -------- -------- --------
106: // \ |
107: // \-----------------------------------------/
108: // CacheGlobals CacheBlock's
109:
110:
111:
112:
113: //�������������������������������������������������������������������������������
114: // Routine: InitMRUCache
115: //
116: // Function: Allocates cache, and initializes all the cache structures.
117: //
118: //�������������������������������������������������������������������������������
119: OSErr InitMRUCache( UInt32 bufferSize, UInt32 numCacheBlocks, Ptr *cachePtr )
120: {
121: OSErr err;
122: short i, lastBuffer;
123: CacheBlock *cacheBlock;
124: CacheGlobals *cacheGlobals;
125: UInt32 cacheBlockSize = offsetof( CacheBlock, buffer ) + bufferSize;
126:
127: cacheGlobals = (CacheGlobals *) NewPtrSysClear( sizeof( CacheGlobals ) + ( numCacheBlocks * cacheBlockSize ) );
128: err = MemError();
129:
130: if ( err == noErr )
131: {
132: cacheGlobals->cacheBlockSize = cacheBlockSize;
133: cacheGlobals->cacheBufferSize = bufferSize;
134: cacheGlobals->numCacheBlocks = numCacheBlocks;
135:
136: lastBuffer = numCacheBlocks - 1; // last buffer number, since they start at 0
137:
138: // Initialize the LRU order for the cache
139: cacheGlobals->lru = (CacheBlock *)((Ptr)cacheGlobals + sizeof( CacheGlobals ) + (lastBuffer * cacheBlockSize));
140: cacheGlobals->lru->nextMRU = nil;
141:
142: // Initialize the MRU order for the cache
143: cacheGlobals->mru = (CacheBlock *)( (Ptr)cacheGlobals + sizeof( CacheGlobals ) ); // points to 1st cache block
144: cacheGlobals->mru->nextLRU = nil;
145:
146: // Traverse nodes, setting initial mru, lru, and default values
147: for ( i=0, cacheBlock=cacheGlobals->mru; i<lastBuffer ; i++ )
148: {
149: cacheBlock->key = kInvalidMRUCacheKey; // initialize key to illegal while we're at it
150: cacheBlock->flags = 0;
151: cacheBlock->nextMRU = (CacheBlock *) ( (Ptr)cacheBlock + cacheBlockSize );
152: cacheBlock = cacheBlock->nextMRU;
153: }
154: // And the last Block
155: cacheGlobals->lru->key = kInvalidMRUCacheKey;
156: cacheBlock->flags = 0;
157:
158: for ( i=0, cacheBlock=cacheGlobals->lru; i<lastBuffer ; i++ )
159: {
160: cacheBlock->nextLRU = (CacheBlock *) ( (Ptr)cacheBlock - cacheBlockSize );
161: cacheBlock = cacheBlock->nextLRU;
162: }
163:
164: *cachePtr = (Ptr) cacheGlobals; // return cacheGlobals to user
165: }
166: else
167: {
168: *cachePtr = nil;
169: }
170:
171: return( err );
172: }
173:
174:
175: //�������������������������������������������������������������������������������
176: // Routine: DisposeMRUCache
177: //
178: // Function: Dispose of all memory allocated by the cache
179: //
180: //�������������������������������������������������������������������������������
181: OSErr DisposeMRUCache( Ptr cachePtr )
182: {
183: OSErr err;
184:
185: DisposePtr( cachePtr );
186: err = MemError();
187:
188: return( err );
189: }
190:
191:
192: //�������������������������������������������������������������������������������
193: // Routine: TrashMRUCache
194: //
195: // Function: Invalidates all entries in the MRU cache pointed to by cachePtr.
196: //
197: //�������������������������������������������������������������������������������
198: void TrashMRUCache( Ptr cachePtr )
199: {
200: CacheGlobals *cacheGlobals = (CacheGlobals *) cachePtr;
201: CacheBlock *cacheBlock;
202:
203: for ( cacheBlock = cacheGlobals->mru ; cacheBlock != nil ; cacheBlock = cacheBlock->nextMRU )
204: {
205: cacheBlock->flags = 0; // Clear the flags
206: cacheBlock->key = kInvalidMRUCacheKey; // Make it an illegal value
207: }
208: }
209:
210:
211: //�������������������������������������������������������������������������������
212: // Routine: GetMRUCacheBlock
213: //
214: // Function: Return buffer associated with the passed in key.
215: // Search the cache in MRU order
216: // � We can insert the found cache block at the head of mru automatically
217: //
218: //�������������������������������������������������������������������������������
219: OSErr GetMRUCacheBlock( UInt32 key, Ptr cachePtr, Ptr *buffer )
220: {
221: CacheBlock *cacheBlock;
222: CacheGlobals *cacheGlobals = (CacheGlobals *) cachePtr;
223:
224: // if ( key == kInvalidMRUCacheKey ) // removed for performance
225: // return( errInvalidKey );
226:
227: for ( cacheBlock = cacheGlobals->mru ; (cacheBlock != nil) && (cacheBlock->key != kInvalidMRUCacheKey) ; cacheBlock = cacheBlock->nextMRU )
228: {
229: if ( cacheBlock->key == key )
230: {
231: InsertAsMRU( cacheGlobals, cacheBlock );
232: *buffer = (Ptr) cacheBlock->buffer;
233: return( noErr );
234: }
235: }
236:
237: return( errNotInCache );
238: }
239:
240:
241:
242: //�������������������������������������������������������������������������������
243: // Routine: InvalidateMRUCacheBlock
244: //
245: // Function: Place the cache block at the head of the lru queue and mark it invalid
246: //
247: //�������������������������������������������������������������������������������
248: void InvalidateMRUCacheBlock( Ptr cachePtr, Ptr buffer )
249: {
250: CacheGlobals *cacheGlobals = (CacheGlobals *) cachePtr;
251: CacheBlock *cacheBlock;
252:
253: cacheBlock = (CacheBlock *) (buffer - offsetof( CacheBlock, buffer ));
254: cacheBlock->flags = 0; // Clear the flags
255: cacheBlock->key = kInvalidMRUCacheKey; // Make it an illegal value
256: InsertAsLRU( cacheGlobals, cacheBlock );
257: }
258:
259:
260: //�������������������������������������������������������������������������������
261: // Routine: InsertMRUCacheBlock
262: //
263: // Function: Place the CacheBlock associated with the passed in key at the
264: // head of the mru queue and replace the buffer with the passed in buffer
265: //
266: //�������������������������������������������������������������������������������
267: void InsertMRUCacheBlock( Ptr cachePtr, UInt32 key, Ptr buffer )
268: {
269: CacheBlock *cacheBlock = NULL;
270: Ptr cacheBuffer;
271: OSErr err;
272: CacheGlobals *cacheGlobals = (CacheGlobals *) cachePtr;
273: UInt32 cacheBufferSize;
274:
275: err = GetMRUCacheBlock( key, cachePtr, &cacheBuffer );
276: if ( err == errNotInCache )
277: cacheBlock = cacheGlobals->lru;
278: else if ( err == noErr )
279: cacheBlock = (CacheBlock *) (cacheBuffer - offsetof( CacheBlock, buffer ));
280:
281: cacheBufferSize = cacheGlobals->cacheBufferSize;
282: if ( cacheBufferSize == sizeof(UInt32) )
283: *(UInt32*)cacheBlock->buffer = *(UInt32*)buffer;
284: else
285: BlockMoveData( buffer, cacheBlock->buffer, cacheBufferSize );
286: InsertAsMRU( cacheGlobals, cacheBlock );
287:
288: cacheBlock->flags = 0;
289: cacheBlock->key = key;
290: }
291:
292:
293:
294:
295: //�������������������������������������������������������������������������������
296: // Routine: InsertMRUCacheBlock
297: //
298: // Function: Moves cache block to head of mru order in double linked list of cached blocks
299: //
300: //�������������������������������������������������������������������������������
301: static void InsertAsMRU ( CacheGlobals *cacheGlobals, CacheBlock *cacheBlock )
302: {
303: CacheBlock *swapBlock;
304:
305: if ( cacheGlobals->mru != cacheBlock ) // if it's not already the mru cacheBlock
306: {
307: swapBlock = cacheGlobals->mru; // put it in the front of the double queue
308: cacheGlobals->mru = cacheBlock;
309: cacheBlock->nextLRU->nextMRU = cacheBlock->nextMRU;
310: if ( cacheBlock->nextMRU != nil )
311: cacheBlock->nextMRU->nextLRU = cacheBlock->nextLRU;
312: else
313: cacheGlobals->lru= cacheBlock->nextLRU;
314: cacheBlock->nextMRU = swapBlock;
315: cacheBlock->nextLRU = nil;
316: swapBlock->nextLRU = cacheBlock;
317: }
318: }
319:
320:
321: //�������������������������������������������������������������������������������
322: // Routine: InsertMRUCacheBlock
323: //
324: // Function: Moves cache block to head of lru order in double linked list of cached blocks
325: //
326: //�������������������������������������������������������������������������������
327: static void InsertAsLRU ( CacheGlobals *cacheGlobals, CacheBlock *cacheBlock )
328: {
329: CacheBlock *swapBlock;
330:
331: if ( cacheGlobals->lru != cacheBlock )
332: {
333: swapBlock = cacheGlobals->lru;
334: cacheGlobals->lru = cacheBlock;
335: cacheBlock->nextMRU->nextLRU = cacheBlock->nextLRU;
336: if ( cacheBlock->nextLRU != nil )
337: cacheBlock->nextLRU->nextMRU = cacheBlock->nextMRU;
338: else
339: cacheGlobals->mru= cacheBlock->nextMRU;
340: cacheBlock->nextLRU = swapBlock;
341: cacheBlock->nextMRU = nil;
342: swapBlock->nextMRU = cacheBlock;
343: }
344: }
345:
346:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.