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

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: 

unix.superglobalmegacorp.com

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