src/bin/bfs_tools/lib/Cache.h

   1 #ifndef CACHE_H
   2 #define CACHE_H
   3 /* Cache - a template cache class
   4 **
   5 ** Copyright 2001 pinc Software. All Rights Reserved.
   6 ** Released under the terms of the MIT license.
   7 */
   8
   9
  10 #include <SupportDefs.h>
  11
  12 #include <stdio.h>
  13
  14
  15 template<class T> class Cache
  16 {
  17         public:
  18                 class Cacheable
  19                 {
  20                         public:
  21                                 Cacheable()
  22                                         :
  23                                         prev(NULL),
  24                                         next(NULL),
  25                                         locked(0L),
  26                                         isDirty(false)
  27                                 {
  28                                 }
  29
  30                                 virtual ~Cacheable()
  31                                 {
  32                                         // perform your "undirty" work here
  33                                 }
  34
  35                                 virtual bool Equals(T) = 0;
  36
  37                                 Cacheable       *prev,*next;
  38                                 int32           locked;
  39                                 bool            isDirty;
  40                 };
  41
  42         public:
  43                 Cache(int32 max = 20)
  44                         :
  45                         fMaxInQueue(max),
  46                         fCount(0),
  47                         fHoldChanges(false),
  48                         fMostRecentlyUsed(NULL),
  49                         fLeastRecentlyUsed(NULL)
  50                 {
  51                 }
  52
  53                 virtual ~Cache()
  54                 {
  55                         Clear(0,true);
  56                 }
  57
  58                 void Clear(int32 targetCount = 0,bool force = false)
  59                 {
  60                         Cacheable *entry = fLeastRecentlyUsed;
  61                         while (entry)
  62                         {
  63                                 Cacheable *prev = entry->prev;
  64                                 if (entry->locked <= 0 || force)
  65                                 {
  66                                         if (entry->next)
  67                                                 entry->next->prev = prev;
  68                                         if (prev)
  69                                                 prev->next = entry->next;
  70
  71                                         if (fLeastRecentlyUsed == entry)
  72                                                 fLeastRecentlyUsed = prev;
  73                                         if (fMostRecentlyUsed == entry)
  74                                                 fMostRecentlyUsed = prev;
  75
  76                                         delete entry;
  77
  78                                         if (--fCount <= targetCount)
  79                                                 break;
  80                                 }
  81
  82                                 entry = prev;
  83                         }
  84                 }
  85
  86                 void SetHoldChanges(bool hold)
  87                 {
  88                         fHoldChanges = hold;
  89                         if (!hold)
  90                                 Clear(fMaxInQueue);
  91                 }
  92
  93                 status_t SetDirty(T data,bool dirty)
  94                 {
  95                         Cacheable *entry = Get(data);
  96                         if (!entry)
  97                                 return B_ENTRY_NOT_FOUND;
  98
  99                         entry->isDirty = dirty;
 100                         return B_OK;
 101                 }
 102
 103                 status_t Lock(T data)
 104                 {
 105                         Cacheable *entry = Get(data);
 106                         if (!entry)
 107                                 return B_ENTRY_NOT_FOUND;
 108
 109                         entry->locked++;
 110                         return B_OK;
 111                 }
 112
 113                 status_t Unlock(T data)
 114                 {
 115                         Cacheable *entry = Get(data);
 116                         if (!entry)
 117                                 return B_ENTRY_NOT_FOUND;
 118
 119                         entry->locked--;
 120                         return B_OK;
 121                 }
 122
 123                 Cacheable *Get(T data)
 124                 {
 125                         Cacheable *entry = GetFromCache(data);
 126                         if (entry)
 127                         {
 128                                 if (fMostRecentlyUsed == entry)
 129                                         return entry;
 130
 131                                 // remove entry from cache (to insert it at top of the MRU list)
 132                                 if (entry->prev)
 133                                         entry->prev->next = entry->next;
 134                                 if (!entry->next)
 135                                 {
 136                                         if (fLeastRecentlyUsed == entry)
 137                                                 fLeastRecentlyUsed = entry->prev;
 138                                         else
 139                                                 fprintf(stderr,"Cache: fatal error, fLeastRecentlyUsed != entry\n");
 140                                 }
 141                                 else
 142                                         entry->next->prev = entry->prev;
 143                         }
 144                         else
 145                         {
 146                                 entry = NewCacheable(data);
 147                                 if (entry)
 148                                         fCount++;
 149                         }
 150
 151                         if (entry)
 152                         {
 153                                 // insert entry at the top of the MRU list
 154                                 entry->next = fMostRecentlyUsed;
 155                                 entry->prev = NULL;
 156
 157                                 if (fMostRecentlyUsed)
 158                                         fMostRecentlyUsed->prev = entry;
 159                                 else if (fLeastRecentlyUsed == NULL)
 160                                         fLeastRecentlyUsed = entry;
 161                                 else
 162                                         fprintf(stderr,"Cache: fatal error, fLeastRecently != NULL!\n");
 163                                 fMostRecentlyUsed = entry;
 164
 165                                 // remove old nodes from of the cache (if possible and necessary)
 166                                 if (!fHoldChanges
 167                                         && fCount > fMaxInQueue
 168                                         && fLeastRecentlyUsed)
 169                                         Clear(fMaxInQueue);
 170                         }
 171                         return entry;
 172                 }
 173
 174         protected:
 175                 Cacheable *GetFromCache(T data)
 176                 {
 177                         Cacheable *entry = fMostRecentlyUsed;
 178                         while (entry)
 179                         {
 180                                 if (entry->Equals(data))
 181                                         return entry;
 182                                 entry = entry->next;
 183                         }
 184                         return NULL;
 185                 }
 186
 187                 virtual Cacheable *NewCacheable(T data) = 0;
 188
 189                 int32           fMaxInQueue, fCount;
 190                 bool            fHoldChanges;
 191                 Cacheable       *fMostRecentlyUsed;
 192                 Cacheable       *fLeastRecentlyUsed;
 193 };
 194
 195 #endif  /* CACHE_H */