git.maemo.org Git - navit-package/blob - navit/cache.c

   1 #include <glib.h>
   2 #ifdef DEBUG_CACHE
   3 #include <stdio.h>
   4 #endif
   5 #include <string.h>
   6 #include "debug.h"
   7 #include "cache.h"
   8
   9 struct cache_entry {
  10         int usage;
  11         int size;
  12         struct cache_entry_list *where;
  13         struct cache_entry *next;
  14         struct cache_entry *prev;
  15         int id[0];
  16 };
  17
  18 struct cache_entry_list {
  19         struct cache_entry *first, *last;
  20         int size;
  21 };
  22
  23 struct cache {
  24         struct cache_entry_list t1,b1,t2,b2,*insert;
  25         int size,id_size,entry_size;
  26         int t1_target;
  27         int misses;
  28         int hits;
  29         GHashTable *hash;
  30 };
  31
  32 static void
  33 cache_entry_dump(struct cache *cache, struct cache_entry *entry)
  34 {
  35         int i,size;
  36         dbg(0,"Usage: %d size %d\n",entry->usage, entry->size);
  37         if (cache)
  38                 size=cache->id_size;
  39         else
  40                 size=5;
  41         for (i = 0 ; i < size ; i++) {
  42                 dbg(0,"0x%x\n", entry->id[i]);
  43         }
  44 }
  45
  46 static void
  47 cache_list_dump(char *str, struct cache *cache, struct cache_entry_list *list)
  48 {
  49         struct cache_entry *first=list->first;
  50         dbg(0,"dump %s %d\n",str, list->size);
  51         while (first) {
  52                 cache_entry_dump(cache, first);
  53                 first=first->next;
  54         }
  55 }
  56
  57 static guint
  58 cache_hash4(gconstpointer key)
  59 {
  60         int *id=(int *)key;
  61         return id[0];
  62 }
  63
  64 static guint
  65 cache_hash20(gconstpointer key)
  66 {
  67         int *id=(int *)key;
  68         return id[0]^id[1]^id[2]^id[3]^id[4];
  69 }
  70
  71 static gboolean
  72 cache_equal4(gconstpointer a, gconstpointer b)
  73 {
  74         int *ida=(int *)a;
  75         int *idb=(int *)b;
  76
  77         return ida[0] == idb[0];
  78 }
  79
  80 static gboolean
  81 cache_equal20(gconstpointer a, gconstpointer b)
  82 {
  83         int *ida=(int *)a;
  84         int *idb=(int *)b;
  85
  86         return(ida[0] == idb[0] &&
  87                ida[1] == idb[1] &&
  88                ida[2] == idb[2] &&
  89                ida[3] == idb[3] &&
  90                ida[4] == idb[4]);
  91 }
  92
  93 struct cache *
  94 cache_new(int id_size, int size)
  95 {
  96         struct cache *cache=g_new0(struct cache, 1);
  97
  98         cache->id_size=id_size/4;
  99         cache->entry_size=cache->id_size*sizeof(int)+sizeof(struct cache_entry);
 100         cache->size=size;
 101         switch (id_size) {
 102         case 4:
 103                 cache->hash=g_hash_table_new(cache_hash4, cache_equal4);
 104                 break;
 105         case 20:
 106                 cache->hash=g_hash_table_new(cache_hash20, cache_equal20);
 107                 break;
 108         default:
 109                 dbg(0,"cache with id_size of %d not supported\n", id_size);
 110                 g_free(cache);
 111                 cache=NULL;
 112         }
 113         return cache;
 114 }
 115
 116 static void
 117 cache_insert_mru(struct cache *cache, struct cache_entry_list *list, struct cache_entry *entry)
 118 {
 119         entry->prev=NULL;
 120         entry->next=list->first;
 121         entry->where=list;
 122         if (entry->next)
 123                 entry->next->prev=entry;
 124         list->first=entry;
 125         if (! list->last)
 126                 list->last=entry;
 127         list->size+=entry->size;
 128         if (cache)
 129                 g_hash_table_insert(cache->hash, (gpointer)entry->id, entry);
 130 }
 131
 132 static void
 133 cache_remove_from_list(struct cache_entry_list *list, struct cache_entry *entry)
 134 {
 135         if (entry->prev)
 136                 entry->prev->next=entry->next;
 137         else
 138                 list->first=entry->next;
 139         if (entry->next)
 140                 entry->next->prev=entry->prev;
 141         else
 142                 list->last=entry->prev;
 143         list->size-=entry->size;
 144 }
 145
 146 static void
 147 cache_remove(struct cache *cache, struct cache_entry *entry)
 148 {
 149         dbg(1,"remove 0x%x 0x%x 0x%x 0x%x 0x%x\n", entry->id[0], entry->id[1], entry->id[2], entry->id[3], entry->id[4]);
 150         g_hash_table_remove(cache->hash, (gpointer)(entry->id));
 151         g_free(entry);
 152 }
 153
 154 static struct cache_entry *
 155 cache_remove_lru_helper(struct cache_entry_list *list)
 156 {
 157         struct cache_entry *last=list->last;
 158         if (! last)
 159                 return NULL;
 160         list->last=last->prev;
 161         if (last->prev)
 162                 last->prev->next=NULL;
 163         else
 164                 list->first=NULL;
 165         list->size-=last->size;
 166         return last;
 167 }
 168
 169 static struct cache_entry *
 170 cache_remove_lru(struct cache *cache, struct cache_entry_list *list)
 171 {
 172         struct cache_entry *last;
 173         int seen=0;
 174         while (list->last && list->last->usage && seen < list->size) {
 175                 last=cache_remove_lru_helper(list);
 176                 cache_insert_mru(NULL, list, last);
 177                 seen+=last->size;
 178         }
 179         last=list->last;
 180         if (! last || last->usage || seen >= list->size)
 181                 return NULL;
 182         dbg(1,"removing %d\n", last->id[0]);
 183         cache_remove_lru_helper(list);
 184         if (cache) {
 185                 cache_remove(cache, last);
 186                 return NULL;
 187         }
 188         return last;
 189 }
 190
 191 void *
 192 cache_entry_new(struct cache *cache, void *id, int size)
 193 {
 194         size+=cache->entry_size;
 195         cache->misses+=size;
 196         struct cache_entry *ret=(struct cache_entry *)g_malloc0(size);
 197         ret->size=size;
 198         ret->usage=1;
 199         memcpy(ret->id, id, cache->id_size*sizeof(int));
 200         return &ret->id[cache->id_size];
 201 }
 202
 203 void
 204 cache_entry_destroy(struct cache *cache, void *data)
 205 {
 206         struct cache_entry *entry=(struct cache_entry *)((char *)data-cache->entry_size);
 207         dbg(1,"destroy 0x%x 0x%x 0x%x 0x%x 0x%x\n", entry->id[0], entry->id[1], entry->id[2], entry->id[3], entry->id[4]);
 208         entry->usage--;
 209 }
 210
 211 static struct cache_entry *
 212 cache_trim(struct cache *cache, struct cache_entry *entry)
 213 {
 214         dbg(1,"trim 0x%x 0x%x 0x%x 0x%x 0x%x\n", entry->id[0], entry->id[1], entry->id[2], entry->id[3], entry->id[4]);
 215         return g_realloc(entry, cache->entry_size);
 216 }
 217
 218 static struct cache_entry *
 219 cache_move(struct cache *cache, struct cache_entry_list *old, struct cache_entry_list *new)
 220 {
 221         struct cache_entry *entry;
 222         entry=cache_remove_lru(NULL, old);
 223         if (! entry)
 224                 return NULL;
 225         entry=cache_trim(cache, entry);
 226         cache_insert_mru(NULL, new, entry);
 227         return entry;
 228 }
 229
 230 static int
 231 cache_replace(struct cache *cache)
 232 {
 233         if (cache->t1.size >= MAX(1,cache->t1_target)) {
 234                 dbg(1,"replace 12\n");
 235                 if (!cache_move(cache, &cache->t1, &cache->b1))
 236                         cache_move(cache, &cache->t2, &cache->b2);
 237         } else {
 238                 dbg(1,"replace t2\n");
 239                 if (!cache_move(cache, &cache->t2, &cache->b2))
 240                         cache_move(cache, &cache->t1, &cache->b1);
 241         }
 242 #if 0
 243         if (! entry) {
 244                 cache_dump(cache);
 245                 exit(0);
 246         }
 247 #endif
 248         return 1;
 249 }
 250
 251 void
 252 cache_flush(struct cache *cache, void *id)
 253 {
 254         struct cache_entry *entry=g_hash_table_lookup(cache->hash, id);
 255         if (entry)
 256                 cache_remove(cache, entry);
 257 }
 258
 259
 260 void *
 261 cache_lookup(struct cache *cache, void *id) {
 262         struct cache_entry *entry;
 263
 264         dbg(1,"get %d\n", ((int *)id)[0]);
 265         entry=g_hash_table_lookup(cache->hash, id);
 266         if (entry == NULL) {
 267                 cache->insert=&cache->t1;
 268 #ifdef DEBUG_CACHE
 269                 fprintf(stderr,"-");
 270 #endif
 271                 dbg(1,"not in cache\n");
 272                 return NULL;
 273         }
 274         dbg(1,"found 0x%x 0x%x 0x%x 0x%x 0x%x\n", entry->id[0], entry->id[1], entry->id[2], entry->id[3], entry->id[4]);
 275         if (entry->where == &cache->t1 || entry->where == &cache->t2) {
 276                 cache->hits+=entry->size;
 277 #ifdef DEBUG_CACHE
 278                 if (entry->where == &cache->t1)
 279                         fprintf(stderr,"h");
 280                 else
 281                         fprintf(stderr,"H");
 282 #endif
 283                 dbg(1,"in cache %s\n", entry->where == &cache->t1 ? "T1" : "T2");
 284                 cache_remove_from_list(entry->where, entry);
 285                 cache_insert_mru(NULL, &cache->t2, entry);
 286                 entry->usage++;
 287                 return &entry->id[cache->id_size];
 288         } else {
 289                 if (entry->where == &cache->b1) {
 290 #ifdef DEBUG_CACHE
 291                         fprintf(stderr,"m");
 292 #endif
 293                         dbg(1,"in phantom cache B1\n");
 294                         cache->t1_target=MIN(cache->t1_target+MAX(cache->b2.size/cache->b1.size, 1),cache->size);
 295                         cache_remove_from_list(&cache->b1, entry);
 296                 } else if (entry->where == &cache->b2) {
 297 #ifdef DEBUG_CACHE
 298                         fprintf(stderr,"M");
 299 #endif
 300                         dbg(1,"in phantom cache B2\n");
 301                         cache->t1_target=MAX(cache->t1_target-MAX(cache->b1.size/cache->b2.size, 1),0);
 302                         cache_remove_from_list(&cache->b2, entry);
 303                 } else {
 304                         dbg(0,"**ERROR** invalid where\n");
 305                 }
 306                 cache_replace(cache);
 307                 cache_remove(cache, entry);
 308                 cache->insert=&cache->t2;
 309                 return NULL;
 310         }
 311 }
 312
 313 void
 314 cache_insert(struct cache *cache, void *data)
 315 {
 316         struct cache_entry *entry=(struct cache_entry *)((char *)data-cache->entry_size);
 317         dbg(1,"insert 0x%x 0x%x 0x%x 0x%x 0x%x\n", entry->id[0], entry->id[1], entry->id[2], entry->id[3], entry->id[4]);
 318         if (cache->insert == &cache->t1) {
 319                 if (cache->t1.size + cache->b1.size >= cache->size) {
 320                         if (cache->t1.size < cache->size) {
 321                                 cache_remove_lru(cache, &cache->b1);
 322                                 cache_replace(cache);
 323                         } else {
 324                                 cache_remove_lru(cache, &cache->t1);
 325                         }
 326                 } else {
 327                         if (cache->t1.size + cache->t2.size + cache->b1.size + cache->b2.size >= cache->size) {
 328                                 if (cache->t1.size + cache->t2.size + cache->b1.size + cache->b2.size >= 2*cache->size)
 329                                         cache_remove_lru(cache, &cache->b2);
 330                                 cache_replace(cache);
 331                         }
 332                 }
 333         }
 334         cache_insert_mru(cache, cache->insert, entry);
 335 }
 336
 337 void *
 338 cache_insert_new(struct cache *cache, void *id, int size)
 339 {
 340         void *data=cache_entry_new(cache, id, size);
 341         cache_insert(cache, data);
 342         return data;
 343 }
 344
 345 static void
 346 cache_stats(struct cache *cache)
 347 {
 348         dbg(0,"hits %d misses %d hitratio %d size %d entry_size %d id_size %d T1 target %d\n", cache->hits, cache->misses, cache->hits*100/(cache->hits+cache->misses), cache->size, cache->entry_size, cache->id_size, cache->t1_target);
 349         dbg(0,"T1:%d B1:%d T2:%d B2:%d\n", cache->t1.size, cache->b1.size, cache->t2.size, cache->b2.size);
 350         cache->hits=0;
 351         cache->misses=0;
 352 }
 353
 354 void
 355 cache_dump(struct cache *cache)
 356 {
 357         struct cache_entry *first;
 358         first=cache->t1.first;
 359         cache_stats(cache);
 360         cache_list_dump("T1", cache, &cache->t1);
 361         cache_list_dump("B1", cache, &cache->b1);
 362         cache_list_dump("T2", cache, &cache->t2);
 363         cache_list_dump("B2", cache, &cache->b2);
 364         dbg(0,"dump end\n");
 365 }
 366