![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to GenericMRUCache.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Apple Darwin 0.x] / kernel / bsd / hfs / hfscommon / Misc|
Return to GenericMRUCache.c CVS log | Up to [Apple Darwin 0.x] / kernel / bsd / hfs / hfscommon / Misc |
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.