Return to GenericMRUCache.c CVS log

Up to [Apple XNU] / XNU / bsd / hfs / hfscommon / Misc

Annotation of XNU/bsd/hfs/hfscommon/Misc/GenericMRUCache.c, revision 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: 

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