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