Annotation of kernel/bsd/hfs/hfscommon/Misc/GenericMRUCache.c, revision 1.1.1.1

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: 

unix.superglobalmegacorp.com

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.