gemrb/core/LRUCache.cpp

   1 /* GemRB - Infinity Engine Emulator
   2  * Copyright (C) 2007
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License
   6  * as published by the Free Software Foundation; either version 2
   7  * of the License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  17  *
  18  *
  19  */
  20
  21 #include "LRUCache.h"
  22
  23 #include <cassert>
  24 #include <cstdio>
  25
  26 struct VarEntry {
  27         VarEntry* prev;
  28         VarEntry* next;
  29         void* data;
  30         char* key;
  31 };
  32
  33 LRUCache::LRUCache() : v(), head(0), tail(0) {
  34         v.SetType(GEM_VARIABLES_POINTER);
  35         v.ParseKey(1);
  36 }
  37
  38 LRUCache::~LRUCache()
  39 {
  40
  41 }
  42
  43 int LRUCache::GetCount() const
  44 {
  45         return v.GetCount();
  46 }
  47
  48 void LRUCache::SetAt(const char* key, void* value)
  49 {
  50         void* p;
  51         if (v.Lookup(key, p)) {
  52                 VarEntry* e = (VarEntry*) p;
  53                 e->data = value;
  54                 Touch(key);
  55                 return;
  56         }
  57
  58         VarEntry* e = new VarEntry();
  59         e->prev = 0;
  60         e->next = head;
  61         e->data = value;
  62         e->key = new char[strlen(key)+1];
  63         strcpy(e->key, key);
  64
  65         if (head)
  66                 head->prev = e;
  67         head = e;
  68         if (tail == 0) tail = head;
  69
  70         v.SetAt(key, (void*)e);
  71 }
  72
  73 bool LRUCache::Lookup(const char* key, void*& value) const
  74 {
  75         void* p;
  76         if (v.Lookup(key, p)) {
  77                 VarEntry* e = (VarEntry*) p;
  78                 value = e->data;
  79                 return true;
  80         }
  81         return false;
  82 }
  83
  84 bool LRUCache::Touch(const char* key)
  85 {
  86         void* p;
  87         if (!v.Lookup(key, p)) return false;
  88         VarEntry* e = (VarEntry*) p;
  89
  90         // already head?
  91         if (!e->prev) return true;
  92
  93         removeFromList(e);
  94
  95         // re-add e as head:
  96         e->prev = 0;
  97         e->next = head;
  98         head->prev = e;
  99         head = e;
 100         if (tail == 0) tail = head;
 101         return true;
 102 }
 103
 104 bool LRUCache::Remove(const char* key)
 105 {
 106         void* p;
 107         if (!v.Lookup(key, p)) return false;
 108         VarEntry* e = (VarEntry*) p;
 109         v.Remove(key);
 110         removeFromList(e);
 111         delete[] e->key;
 112         delete e;
 113         return true;
 114 }
 115
 116 bool LRUCache::getLRU(unsigned int n, const char*& key, void*& value) const
 117 {
 118         VarEntry* e = tail;
 119         for (unsigned int i = 0; i < n; ++i) {
 120                 if (!e) return false;
 121                 e = e->prev;
 122         }
 123         if (!e) return false;
 124
 125         key = e->key;
 126         value = e->data;
 127         return true;
 128 }
 129
 130 void LRUCache::removeFromList(VarEntry* e)
 131 {
 132         if (e->prev) {
 133                 assert(e != head);
 134                 e->prev->next = e->next;
 135         } else {
 136                 assert(e == head);
 137                 head = e->next;
 138         }
 139
 140         if (e->next) {
 141                 assert(e != tail);
 142                 e->next->prev = e->prev;
 143         } else {
 144                 assert(e == tail);
 145                 tail = e->prev;
 146         }
 147
 148         e->prev = e->next = 0;
 149 }
 150
 151
 152 void testLRUCache()
 153 {
 154         int i;
 155         LRUCache c;
 156
 157         int t[100];
 158         for (i = 0; i < 100; ++i) t[i] = 1000+i;
 159         char* k[100];
 160         for (i = 0; i < 100; ++i) {
 161                 k[i] = new char[5];
 162                 sprintf(k[i], "k%03d", i);
 163         }
 164
 165         bool r;
 166         void* p;
 167         const char* k2 = 0;
 168
 169         r = c.Lookup("k050", p);
 170         assert(!r);
 171
 172         c.SetAt("k050", &t[50]);
 173         r = c.Lookup("k050", p);
 174         assert(r);
 175         assert(p == &t[50]);
 176
 177         for (i = 0; i < 100; ++i)
 178                 c.SetAt(k[i], &t[i]);
 179
 180         r = c.getLRU(0, k2, p);
 181         assert(r);
 182         assert(strcmp(k2, "k000") == 0);
 183         assert(p == &t[0]);
 184
 185         c.Touch("k000");
 186         r = c.getLRU(0, k2, p);
 187         assert(r);
 188         assert(strcmp(k2, "k001") == 0);
 189         assert(p == &t[1]);
 190
 191         r = c.getLRU(1, k2, p);
 192         assert(r);
 193         assert(strcmp(k2, "k002") == 0);
 194         assert(p == &t[2]);
 195
 196         c.Remove("k001");
 197
 198         r = c.getLRU(0, k2, p);
 199         assert(r);
 200         assert(strcmp(k2, "k002") == 0);
 201         assert(p == &t[2]);
 202
 203         for (i = 0; i < 98; ++i) {
 204                 r = c.getLRU(0, k2, p);
 205                 assert(r);
 206                 assert(strcmp(k2, k[2+i]) == 0);
 207                 assert(p == &t[2+i]);
 208                 c.Remove(k2);
 209         }
 210
 211         assert(c.GetCount() == 1);
 212
 213         r = c.getLRU(0, k2, p);
 214         assert(r);
 215         assert(strcmp(k2, "k000") == 0);
 216         assert(p == &t[0]);
 217
 218         assert(!c.getLRU(1, k2, p));
 219 }