navit/navit/cache.c

/**
 * ZANavi, Zoff Android Navigation system.
 * Copyright (C) 2011-2012 Zoff <zoff@zoff.cc>
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * version 2 as published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the
 * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
 * Boston, MA  02110-1301, USA.
 */

#include "glib_slice.h"
#ifdef DEBUG_CACHE
#include <stdio.h>
#endif
#include <string.h>
#include "debug.h"
#include "cache.h"

struct cache_entry
{
        int usage;
        int size;
        struct cache_entry_list *where;
        struct cache_entry *next;
        struct cache_entry *prev;
        int id[0];
};

struct cache_entry_list
{
        struct cache_entry *first, *last;
        int size;
};

struct cache
{
        struct cache_entry_list t1, b1, t2, b2, *insert;
        int size, id_size, entry_size;
        int t1_target;
        long misses;
        long hits;
        GHashTable *hash;
};

static void cache_entry_dump(struct cache *cache, struct cache_entry *entry)
{
        int i, size;
        //dbg(0,"Usage: %d size %d\n",entry->usage, entry->size);
        if (cache)
                size = cache->id_size;
        else
                size = 5;
        for (i = 0; i < size; i++)
        {
                dbg(0, "0x%x\n", entry->id[i]);
        }
}

static void cache_list_dump(char *str, struct cache *cache, struct cache_entry_list *list)
{
        struct cache_entry *first = list->first;
        dbg(0, "dump %s %d\n", str, list->size);
        while (first)
        {
                cache_entry_dump(cache, first);
                first = first->next;
        }
}

static guint cache_hash4(gconstpointer key)
{
        int *id = (int *) key;
        return id[0];
}

static guint cache_hash20(gconstpointer key)
{
        int *id = (int *) key;
        return id[0] ^ id[1] ^ id[2] ^ id[3] ^ id[4];
}

static gboolean cache_equal4(gconstpointer a, gconstpointer b)
{
        int *ida = (int *) a;
        int *idb = (int *) b;

        return ida[0] == idb[0];
}

static gboolean cache_equal20(gconstpointer a, gconstpointer b)
{
        int *ida = (int *) a;
        int *idb = (int *) b;

        return (ida[0] == idb[0] && ida[1] == idb[1] && ida[2] == idb[2] && ida[3] == idb[3] && ida[4] == idb[4]);
}

struct cache *
cache_new(int id_size, int size)
{
        struct cache *cache=g_new0(struct cache, 1);

        cache->id_size = id_size / 4;
        cache->entry_size = cache->id_size * sizeof(int) + sizeof(struct cache_entry);
        cache->size = size;

        dbg(0, "_c size=%d\n", size);

        switch (id_size)
        {
                case 4:
                        cache->hash = g_hash_table_new(cache_hash4, cache_equal4);
                        break;
                case 20:
                        cache->hash = g_hash_table_new(cache_hash20, cache_equal20);
                        break;
                default:
                        dbg(0, "cache with id_size of %d not supported\n", id_size);
                        g_free(cache);
                        cache = NULL;
        }
        return cache;
}

static void cache_insert_mru(struct cache *cache, struct cache_entry_list *list, struct cache_entry *entry)
{
        entry->prev = NULL;
        entry->next = list->first;
        entry->where = list;
        if (entry->next)
                entry->next->prev = entry;
        list->first = entry;
        if (!list->last)
                list->last = entry;
        list->size += entry->size;
        if (cache)
                g_hash_table_insert(cache->hash, (gpointer) entry->id, entry);
}

static void cache_remove_from_list(struct cache_entry_list *list, struct cache_entry *entry)
{
        if (entry->prev)
                entry->prev->next = entry->next;
        else
                list->first = entry->next;
        if (entry->next)
                entry->next->prev = entry->prev;
        else
                list->last = entry->prev;
        list->size -= entry->size;
}

static void cache_remove(struct cache *cache, struct cache_entry *entry)
{
        // 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]);
        g_hash_table_remove(cache->hash, (gpointer)(entry->id));
        g_slice_free1(entry->size, entry);
}

static struct cache_entry *
cache_remove_lru_helper(struct cache_entry_list *list)
{
        struct cache_entry *last = list->last;
        if (!last)
                return NULL;
        list->last = last->prev;
        if (last->prev)
                last->prev->next = NULL;
        else
                list->first = NULL;
        list->size -= last->size;
        return last;
}

static struct cache_entry *
cache_remove_lru(struct cache *cache, struct cache_entry_list *list)
{
        struct cache_entry *last;
        int seen = 0;
        while (list->last && list->last->usage && seen < list->size)
        {
                last = cache_remove_lru_helper(list);
                cache_insert_mru(NULL, list, last);
                seen += last->size;
        }
        last = list->last;
        if (!last || last->usage || seen >= list->size)
        {
                return NULL;
        }
        //dbg(1,"removing %d\n", last->id[0]);
        cache_remove_lru_helper(list);
        if (cache)
        {
                cache_remove(cache, last);
                return NULL;
        }
        return last;
}

void *
cache_entry_new(struct cache *cache, void *id, int size)
{
        struct cache_entry *ret;
        size += cache->entry_size;
        cache->misses += size;
        ret = (struct cache_entry *) g_slice_alloc0(size);
        ret->size = size;
        ret->usage = 1;
        memcpy(ret->id, id, cache->id_size * sizeof(int));
        return &ret->id[cache->id_size];
}

void cache_entry_destroy(struct cache *cache, void *data)
{
        struct cache_entry *entry = (struct cache_entry *) ((char *) data - cache->entry_size);
        // 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]);
        entry->usage--;
}

static struct cache_entry *
cache_trim(struct cache *cache, struct cache_entry *entry)
{
        struct cache_entry *new_entry;
        //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]);
        //dbg(1,"Trim %x from %d -> %d\n", entry->id[0], entry->size, cache->size);
        if (cache->entry_size < entry->size)
        {
                g_hash_table_remove(cache->hash, (gpointer)(entry->id));

                new_entry = g_slice_alloc0(cache->entry_size);
                memcpy(new_entry, entry, cache->entry_size);
                g_slice_free1(entry->size, entry);
                new_entry->size = cache->entry_size;

                g_hash_table_insert(cache->hash, (gpointer) new_entry->id, new_entry);
        }
        else
        {
                new_entry = entry;
        }

        return new_entry;
}

static struct cache_entry *
cache_move(struct cache *cache, struct cache_entry_list *old, struct cache_entry_list *new)
{
        struct cache_entry *entry;
        entry = cache_remove_lru(NULL, old);
        if (!entry)
                return NULL;
        entry = cache_trim(cache, entry);
        cache_insert_mru(NULL, new, entry);
        return entry;
}

static int cache_replace(struct cache *cache)
{
        if (cache->t1.size >= MAX(1, cache->t1_target))
        {
                //dbg(1,"replace 12\n");
                if (!cache_move(cache, &cache->t1, &cache->b1))
                        cache_move(cache, &cache->t2, &cache->b2);
        }
        else
        {
                //dbg(1,"replace t2\n");
                if (!cache_move(cache, &cache->t2, &cache->b2))
                        cache_move(cache, &cache->t1, &cache->b1);
        }
#if 0
        if (! entry)
        {
                cache_dump(cache);
                exit(0);
        }
#endif
        return 1;
}

void cache_flush(struct cache *cache, void *id)
{
        struct cache_entry *entry = g_hash_table_lookup(cache->hash, id);
        if (entry)
        {
                cache_remove_from_list(entry->where, entry);
                cache_remove(cache, entry);
        }
}

void cache_flush_data(struct cache *cache, void *data)
{
        struct cache_entry *entry = (struct cache_entry *) ((char *) data - cache->entry_size);
        if (entry)
        {
                cache_remove_from_list(entry->where, entry);
                cache_remove(cache, entry);
        }
}

void *
cache_lookup(struct cache *cache, void *id)
{
        struct cache_entry *entry;

        //dbg(1,"get %d\n", ((int *)id)[0]);
        entry = g_hash_table_lookup(cache->hash, id);
        if (entry == NULL)
        {
                cache->insert = &cache->t1;
#ifdef DEBUG_CACHE
                fprintf(stderr,"-");
#endif
                //dbg(1,"not in cache\n");
                return NULL;
        }

        // 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]);
        if (entry->where == &cache->t1 || entry->where == &cache->t2)
        {
                cache->hits += entry->size;
#ifdef DEBUG_CACHE
                if (entry->where == &cache->t1)
                {
                        fprintf(stderr,"h");
                }
                else
                {
                        fprintf(stderr,"H");
                }
#endif
                // dbg(1,"in cache %s\n", entry->where == &cache->t1 ? "T1" : "T2");
                cache_remove_from_list(entry->where, entry);
                cache_insert_mru(NULL, &cache->t2, entry);
                entry->usage++;
                return &entry->id[cache->id_size];
        }
        else
        {
                if (entry->where == &cache->b1)
                {
#ifdef DEBUG_CACHE
                        fprintf(stderr,"m");
#endif
                        //dbg(1,"in phantom cache B1\n");
                        cache->t1_target = MIN(cache->t1_target + MAX(cache->b2.size / cache->b1.size, 1), cache->size);
                        cache_remove_from_list(&cache->b1, entry);
                }
                else if (entry->where == &cache->b2)
                {
#ifdef DEBUG_CACHE
                        fprintf(stderr,"M");
#endif
                        //dbg(1,"in phantom cache B2\n");
                        cache->t1_target = MAX(cache->t1_target - MAX(cache->b1.size / cache->b2.size, 1), 0);
                        cache_remove_from_list(&cache->b2, entry);
                }
                else
                {
                        //dbg(0,"**ERROR** invalid where\n");
                }
                cache_replace(cache);
                cache_remove(cache, entry);
                cache->insert = &cache->t2;
                return NULL;
        }
}

void cache_insert(struct cache *cache, void *data)
{
        struct cache_entry *entry = (struct cache_entry *) ((char *) data - cache->entry_size);
        //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]);
        if (cache->insert == &cache->t1)
        {
                if (cache->t1.size + cache->b1.size >= cache->size)
                {
                        if (cache->t1.size < cache->size)
                        {
                                cache_remove_lru(cache, &cache->b1);
                                cache_replace(cache);
                        }
                        else
                        {
                                cache_remove_lru(cache, &cache->t1);
                        }
                }
                else
                {
                        if (cache->t1.size + cache->t2.size + cache->b1.size + cache->b2.size >= cache->size)
                        {
                                if (cache->t1.size + cache->t2.size + cache->b1.size + cache->b2.size >= 2 * cache->size)
                                        cache_remove_lru(cache, &cache->b2);
                                cache_replace(cache);
                        }
                }
        }
        cache_insert_mru(cache, cache->insert, entry);
}

void *
cache_insert_new(struct cache *cache, void *id, int size)
{
        void *data = cache_entry_new(cache, id, size);
        cache_insert(cache, data);
        return data;
}

void cache_stats(struct cache *cache)
{
        unsigned long c_ratio = 0;
        if ((cache->hits + cache->misses) > 0)
        {
                c_ratio = (long) (cache->hits) * (long) (100L);
                //dbg(0,"1 c_ratio=%lu\n", c_ratio);
                c_ratio = c_ratio / (long) (cache->hits + cache->misses);
                //dbg(0,"2 c_ratio=%lu\n", c_ratio);

                dbg(0, "hits %d misses %lu hitratio %d size %d entry_size %d id_size %d T1 target %d\n", cache->hits, cache->misses, c_ratio, cache->size, cache->entry_size, cache->id_size, cache->t1_target);
                // dbg(0,"T1:%d B1:%d T2:%d B2:%d\n", cache->t1.size, cache->b1.size, cache->t2.size, cache->b2.size);

                // if numbers are too big, reset them
                if ((cache->hits > 1000000000) || (cache->misses > 1000000000))
                {
                        cache->hits = 0;
                        cache->misses = 0;
                }
        }
}

void cache_dump(struct cache *cache)
{
        struct cache_entry *first;
        first = cache->t1.first;
        cache_stats(cache);
        cache_list_dump("T1", cache, &cache->t1);
        cache_list_dump("B1", cache, &cache->b1);
        cache_list_dump("T2", cache, &cache->t2);
        cache_list_dump("B2", cache, &cache->b2);
        dbg(0, "dump end\n");
}

1	zoff99	27	/**
2			* ZANavi, Zoff Android Navigation system.
3			* Copyright (C) 2011-2012 Zoff <zoff@zoff.cc>
4			*
5			* This program is free software; you can redistribute it and/or
6			* modify it under the terms of the GNU General Public License
7			* version 2 as published by the Free Software Foundation.
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
16			* Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
17			* Boston, MA 02110-1301, USA.
18			*/
19
20	zoff99	2	#include "glib_slice.h"
21			#ifdef DEBUG_CACHE
22			#include <stdio.h>
23			#endif
24			#include <string.h>
25			#include "debug.h"
26			#include "cache.h"
27
28	zoff99	27	struct cache_entry
29			{
30	zoff99	2	int usage;
31			int size;
32			struct cache_entry_list *where;
33			struct cache_entry *next;
34			struct cache_entry *prev;
35			int id[0];
36			};
37
38	zoff99	27	struct cache_entry_list
39			{
40	zoff99	2	struct cache_entry first, last;
41			int size;
42			};
43
44	zoff99	27	struct cache
45			{
46			struct cache_entry_list t1, b1, t2, b2, *insert;
47			int size, id_size, entry_size;
48	zoff99	2	int t1_target;
49	zoff99	27	long misses;
50			long hits;
51	zoff99	2	GHashTable *hash;
52			};
53
54	zoff99	27	static void cache_entry_dump(struct cache cache, struct cache_entry entry)
55	zoff99	2	{
56	zoff99	27	int i, size;
57			//dbg(0,"Usage: %d size %d\n",entry->usage, entry->size);
58	zoff99	2	if (cache)
59	zoff99	27	size = cache->id_size;
60	zoff99	2	else
61	zoff99	27	size = 5;
62			for (i = 0; i < size; i++)
63			{
64			dbg(0, "0x%x\n", entry->id[i]);
65	zoff99	2	}
66			}
67
68	zoff99	27	static void cache_list_dump(char str, struct cache cache, struct cache_entry_list *list)
69	zoff99	2	{
70	zoff99	27	struct cache_entry *first = list->first;
71			dbg(0, "dump %s %d\n", str, list->size);
72			while (first)
73			{
74	zoff99	2	cache_entry_dump(cache, first);
75	zoff99	27	first = first->next;
76	zoff99	2	}
77			}
78
79	zoff99	27	static guint cache_hash4(gconstpointer key)
80	zoff99	2	{
81	zoff99	27	int id = (int ) key;
82	zoff99	2	return id[0];
83			}
84
85	zoff99	27	static guint cache_hash20(gconstpointer key)
86	zoff99	2	{
87	zoff99	27	int id = (int ) key;
88			return id[0] ^ id[1] ^ id[2] ^ id[3] ^ id[4];
89	zoff99	2	}
90
91	zoff99	27	static gboolean cache_equal4(gconstpointer a, gconstpointer b)
92	zoff99	2	{
93	zoff99	27	int ida = (int ) a;
94			int idb = (int ) b;
95	zoff99	2
96			return ida[0] == idb[0];
97			}
98
99	zoff99	27	static gboolean cache_equal20(gconstpointer a, gconstpointer b)
100	zoff99	2	{
101	zoff99	27	int ida = (int ) a;
102			int idb = (int ) b;
103	zoff99	2
104	zoff99	27	return (ida[0] == idb[0] && ida[1] == idb[1] && ida[2] == idb[2] && ida[3] == idb[3] && ida[4] == idb[4]);
105	zoff99	2	}
106
107			struct cache *
108			cache_new(int id_size, int size)
109			{
110			struct cache *cache=g_new0(struct cache, 1);
111	zoff99	27
112			cache->id_size = id_size / 4;
113			cache->entry_size = cache->id_size * sizeof(int) + sizeof(struct cache_entry);
114			cache->size = size;
115
116			dbg(0, "_c size=%d\n", size);
117
118			switch (id_size)
119			{
120			case 4:
121			cache->hash = g_hash_table_new(cache_hash4, cache_equal4);
122			break;
123			case 20:
124			cache->hash = g_hash_table_new(cache_hash20, cache_equal20);
125			break;
126			default:
127			dbg(0, "cache with id_size of %d not supported\n", id_size);
128			g_free(cache);
129			cache = NULL;
130	zoff99	2	}
131			return cache;
132			}
133
134	zoff99	27	static void cache_insert_mru(struct cache cache, struct cache_entry_list list, struct cache_entry *entry)
135	zoff99	2	{
136	zoff99	27	entry->prev = NULL;
137			entry->next = list->first;
138			entry->where = list;
139	zoff99	2	if (entry->next)
140	zoff99	27	entry->next->prev = entry;
141			list->first = entry;
142			if (!list->last)
143			list->last = entry;
144			list->size += entry->size;
145			if (cache)
146			g_hash_table_insert(cache->hash, (gpointer) entry->id, entry);
147	zoff99	2	}
148
149	zoff99	27	static void cache_remove_from_list(struct cache_entry_list list, struct cache_entry entry)
150	zoff99	2	{
151	zoff99	27	if (entry->prev)
152			entry->prev->next = entry->next;
153	zoff99	2	else
154	zoff99	27	list->first = entry->next;
155	zoff99	2	if (entry->next)
156	zoff99	27	entry->next->prev = entry->prev;
157	zoff99	2	else
158	zoff99	27	list->last = entry->prev;
159			list->size -= entry->size;
160	zoff99	2	}
161
162	zoff99	27	static void cache_remove(struct cache cache, struct cache_entry entry)
163	zoff99	2	{
164	zoff99	27	// 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]);
165	zoff99	2	g_hash_table_remove(cache->hash, (gpointer)(entry->id));
166			g_slice_free1(entry->size, entry);
167			}
168
169			static struct cache_entry *
170			cache_remove_lru_helper(struct cache_entry_list *list)
171			{
172	zoff99	27	struct cache_entry *last = list->last;
173			if (!last)
174	zoff99	2	return NULL;
175	zoff99	27	list->last = last->prev;
176	zoff99	2	if (last->prev)
177	zoff99	27	last->prev->next = NULL;
178	zoff99	2	else
179	zoff99	27	list->first = NULL;
180			list->size -= last->size;
181	zoff99	2	return last;
182			}
183
184			static struct cache_entry *
185			cache_remove_lru(struct cache cache, struct cache_entry_list list)
186			{
187			struct cache_entry *last;
188	zoff99	27	int seen = 0;
189			while (list->last && list->last->usage && seen < list->size)
190			{
191			last = cache_remove_lru_helper(list);
192	zoff99	2	cache_insert_mru(NULL, list, last);
193	zoff99	27	seen += last->size;
194	zoff99	2	}
195	zoff99	27	last = list->last;
196			if (!last \|\| last->usage \|\| seen >= list->size)
197			{
198	zoff99	2	return NULL;
199	zoff99	27	}
200			//dbg(1,"removing %d\n", last->id[0]);
201	zoff99	2	cache_remove_lru_helper(list);
202	zoff99	27	if (cache)
203			{
204	zoff99	2	cache_remove(cache, last);
205			return NULL;
206			}
207			return last;
208			}
209
210			void *
211			cache_entry_new(struct cache cache, void id, int size)
212			{
213			struct cache_entry *ret;
214	zoff99	27	size += cache->entry_size;
215			cache->misses += size;
216			ret = (struct cache_entry *) g_slice_alloc0(size);
217			ret->size = size;
218			ret->usage = 1;
219			memcpy(ret->id, id, cache->id_size * sizeof(int));
220	zoff99	2	return &ret->id[cache->id_size];
221			}
222
223	zoff99	27	void cache_entry_destroy(struct cache cache, void data)
224	zoff99	2	{
225	zoff99	27	struct cache_entry entry = (struct cache_entry ) ((char *) data - cache->entry_size);
226			// 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]);
227	zoff99	2	entry->usage--;
228			}
229
230			static struct cache_entry *
231			cache_trim(struct cache cache, struct cache_entry entry)
232			{
233			struct cache_entry *new_entry;
234	zoff99	27	//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]);
235			//dbg(1,"Trim %x from %d -> %d\n", entry->id[0], entry->size, cache->size);
236			if (cache->entry_size < entry->size)
237	zoff99	2	{
238	zoff99	27	g_hash_table_remove(cache->hash, (gpointer)(entry->id));
239	zoff99	2
240	zoff99	27	new_entry = g_slice_alloc0(cache->entry_size);
241			memcpy(new_entry, entry, cache->entry_size);
242			g_slice_free1(entry->size, entry);
243			new_entry->size = cache->entry_size;
244	zoff99	2
245	zoff99	27	g_hash_table_insert(cache->hash, (gpointer) new_entry->id, new_entry);
246	zoff99	2	}
247			else
248			{
249	zoff99	27	new_entry = entry;
250	zoff99	2	}
251	zoff99	27
252	zoff99	2	return new_entry;
253			}
254
255			static struct cache_entry *
256			cache_move(struct cache cache, struct cache_entry_list old, struct cache_entry_list *new)
257			{
258			struct cache_entry *entry;
259	zoff99	27	entry = cache_remove_lru(NULL, old);
260			if (!entry)
261	zoff99	2	return NULL;
262	zoff99	27	entry = cache_trim(cache, entry);
263	zoff99	2	cache_insert_mru(NULL, new, entry);
264			return entry;
265			}
266
267	zoff99	27	static int cache_replace(struct cache *cache)
268	zoff99	2	{
269	zoff99	27	if (cache->t1.size >= MAX(1, cache->t1_target))
270			{
271			//dbg(1,"replace 12\n");
272	zoff99	2	if (!cache_move(cache, &cache->t1, &cache->b1))
273			cache_move(cache, &cache->t2, &cache->b2);
274	zoff99	27	}
275			else
276			{
277			//dbg(1,"replace t2\n");
278	zoff99	2	if (!cache_move(cache, &cache->t2, &cache->b2))
279			cache_move(cache, &cache->t1, &cache->b1);
280			}
281			#if 0
282	zoff99	27	if (! entry)
283			{
284	zoff99	2	cache_dump(cache);
285			exit(0);
286			}
287			#endif
288			return 1;
289			}
290
291	zoff99	27	void cache_flush(struct cache cache, void id)
292	zoff99	2	{
293	zoff99	27	struct cache_entry *entry = g_hash_table_lookup(cache->hash, id);
294			if (entry)
295			{
296	zoff99	2	cache_remove_from_list(entry->where, entry);
297			cache_remove(cache, entry);
298			}
299			}
300
301	zoff99	27	void cache_flush_data(struct cache cache, void data)
302	zoff99	2	{
303	zoff99	27	struct cache_entry entry = (struct cache_entry ) ((char *) data - cache->entry_size);
304			if (entry)
305			{
306	zoff99	2	cache_remove_from_list(entry->where, entry);
307			cache_remove(cache, entry);
308			}
309			}
310
311			void *
312	zoff99	27	cache_lookup(struct cache cache, void id)
313			{
314	zoff99	2	struct cache_entry *entry;
315
316	zoff99	27	//dbg(1,"get %d\n", ((int *)id)[0]);
317			entry = g_hash_table_lookup(cache->hash, id);
318			if (entry == NULL)
319			{
320			cache->insert = &cache->t1;
321	zoff99	2	#ifdef DEBUG_CACHE
322			fprintf(stderr,"-");
323			#endif
324	zoff99	27	//dbg(1,"not in cache\n");
325	zoff99	2	return NULL;
326			}
327	zoff99	27
328			// 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]);
329			if (entry->where == &cache->t1 \|\| entry->where == &cache->t2)
330			{
331			cache->hits += entry->size;
332	zoff99	2	#ifdef DEBUG_CACHE
333			if (entry->where == &cache->t1)
334	zoff99	27	{
335	zoff99	2	fprintf(stderr,"h");
336	zoff99	27	}
337	zoff99	2	else
338	zoff99	27	{
339	zoff99	2	fprintf(stderr,"H");
340	zoff99	27	}
341	zoff99	2	#endif
342	zoff99	27	// dbg(1,"in cache %s\n", entry->where == &cache->t1 ? "T1" : "T2");
343	zoff99	2	cache_remove_from_list(entry->where, entry);
344			cache_insert_mru(NULL, &cache->t2, entry);
345			entry->usage++;
346			return &entry->id[cache->id_size];
347	zoff99	27	}
348			else
349			{
350			if (entry->where == &cache->b1)
351			{
352	zoff99	2	#ifdef DEBUG_CACHE
353			fprintf(stderr,"m");
354			#endif
355	zoff99	27	//dbg(1,"in phantom cache B1\n");
356			cache->t1_target = MIN(cache->t1_target + MAX(cache->b2.size / cache->b1.size, 1), cache->size);
357	zoff99	2	cache_remove_from_list(&cache->b1, entry);
358	zoff99	27	}
359			else if (entry->where == &cache->b2)
360			{
361	zoff99	2	#ifdef DEBUG_CACHE
362			fprintf(stderr,"M");
363			#endif
364	zoff99	27	//dbg(1,"in phantom cache B2\n");
365			cache->t1_target = MAX(cache->t1_target - MAX(cache->b1.size / cache->b2.size, 1), 0);
366	zoff99	2	cache_remove_from_list(&cache->b2, entry);
367			}
368	zoff99	27	else
369			{
370			//dbg(0,"ERROR invalid where\n");
371			}
372	zoff99	2	cache_replace(cache);
373			cache_remove(cache, entry);
374	zoff99	27	cache->insert = &cache->t2;
375	zoff99	2	return NULL;
376			}
377			}
378
379	zoff99	27	void cache_insert(struct cache cache, void data)
380	zoff99	2	{
381	zoff99	27	struct cache_entry entry = (struct cache_entry ) ((char *) data - cache->entry_size);
382			//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]);
383			if (cache->insert == &cache->t1)
384			{
385			if (cache->t1.size + cache->b1.size >= cache->size)
386			{
387			if (cache->t1.size < cache->size)
388			{
389	zoff99	2	cache_remove_lru(cache, &cache->b1);
390			cache_replace(cache);
391	zoff99	27	}
392			else
393			{
394	zoff99	2	cache_remove_lru(cache, &cache->t1);
395			}
396	zoff99	27	}
397			else
398			{
399			if (cache->t1.size + cache->t2.size + cache->b1.size + cache->b2.size >= cache->size)
400			{
401			if (cache->t1.size + cache->t2.size + cache->b1.size + cache->b2.size >= 2 * cache->size)
402	zoff99	2	cache_remove_lru(cache, &cache->b2);
403			cache_replace(cache);
404			}
405			}
406			}
407			cache_insert_mru(cache, cache->insert, entry);
408			}
409
410			void *
411			cache_insert_new(struct cache cache, void id, int size)
412			{
413	zoff99	27	void *data = cache_entry_new(cache, id, size);
414	zoff99	2	cache_insert(cache, data);
415	zoff99	27	return data;
416	zoff99	2	}
417
418	zoff99	27	void cache_stats(struct cache *cache)
419	zoff99	2	{
420	zoff99	27	unsigned long c_ratio = 0;
421			if ((cache->hits + cache->misses) > 0)
422			{
423			c_ratio = (long) (cache->hits) * (long) (100L);
424			//dbg(0,"1 c_ratio=%lu\n", c_ratio);
425			c_ratio = c_ratio / (long) (cache->hits + cache->misses);
426			//dbg(0,"2 c_ratio=%lu\n", c_ratio);
427
428			dbg(0, "hits %d misses %lu hitratio %d size %d entry_size %d id_size %d T1 target %d\n", cache->hits, cache->misses, c_ratio, cache->size, cache->entry_size, cache->id_size, cache->t1_target);
429			// dbg(0,"T1:%d B1:%d T2:%d B2:%d\n", cache->t1.size, cache->b1.size, cache->t2.size, cache->b2.size);
430
431			// if numbers are too big, reset them
432			if ((cache->hits > 1000000000) \|\| (cache->misses > 1000000000))
433			{
434			cache->hits = 0;
435			cache->misses = 0;
436			}
437			}
438	zoff99	2	}
439
440	zoff99	27	void cache_dump(struct cache *cache)
441	zoff99	2	{
442			struct cache_entry *first;
443	zoff99	27	first = cache->t1.first;
444	zoff99	2	cache_stats(cache);
445			cache_list_dump("T1", cache, &cache->t1);
446			cache_list_dump("B1", cache, &cache->b1);
447			cache_list_dump("T2", cache, &cache->t2);
448			cache_list_dump("B2", cache, &cache->b2);
449	zoff99	27	dbg(0, "dump end\n");
450	zoff99	2	}
451