1 /* Implement a cached obstack.
2 Written by Fred Fish (fnf@cygnus.com)
3 Copyright 1995, 1998 Free Software Foundation, Inc.
5 This file is part of GDB.
7 This program is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software
19 Foundation, Inc., 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
25 #include "gdb_string.h" /* For memcpy declaration */
27 /* Prototypes for local functions. */
29 static unsigned int hash PARAMS ((void *, int));
31 static void *lookup_cache PARAMS ((void *, int, int, struct bcache *));
33 /* FIXME: Incredibly simplistic hash generator. Probably way too expensive
34 (consider long strings) and unlikely to have good distribution across hash
35 values for typical input. */
43 unsigned long hashval;
45 const unsigned char *data = bytes;
52 hashval += c + (c << 17);
53 hashval ^= hashval >> 2;
56 hashval += len + (len << 17);
57 hashval ^= hashval >> 2;
58 return (hashval % BCACHE_HASHSIZE);
62 lookup_cache (bytes, count, hashval, bcachep)
66 struct bcache *bcachep;
68 void *location = NULL;
69 struct hashlink **hashtablep;
70 struct hashlink *linkp;
72 hashtablep = bcachep->indextable[count];
73 if (hashtablep != NULL)
75 linkp = hashtablep[hashval];
78 if (memcmp (BCACHE_DATA (linkp), bytes, count) == 0)
80 location = BCACHE_DATA (linkp);
90 bcache (bytes, count, bcachep)
93 struct bcache *bcachep;
97 struct hashlink *newlink;
98 struct hashlink **linkpp;
99 struct hashlink ***hashtablepp;
101 if (count >= BCACHE_MAXLENGTH)
103 /* Rare enough to just stash unique copies */
104 location = (void *) obstack_alloc (&bcachep->cache, count);
105 bcachep->cache_bytes += count;
106 memcpy (location, bytes, count);
107 bcachep->bcache_overflows++;
111 hashval = hash (bytes, count);
112 location = lookup_cache (bytes, count, hashval, bcachep);
113 if (location != NULL)
115 bcachep->cache_savings += count;
116 bcachep->cache_hits++;
120 bcachep->cache_misses++;
121 hashtablepp = &bcachep->indextable[count];
122 if (*hashtablepp == NULL)
124 *hashtablepp = (struct hashlink **)
125 obstack_alloc (&bcachep->cache, BCACHE_HASHSIZE * sizeof (struct hashlink *));
126 bcachep->cache_bytes += BCACHE_HASHSIZE * sizeof (struct hashlink *);
127 memset (*hashtablepp, 0, BCACHE_HASHSIZE * sizeof (struct hashlink *));
129 linkpp = &(*hashtablepp)[hashval];
130 newlink = (struct hashlink *)
131 obstack_alloc (&bcachep->cache, BCACHE_DATA_ALIGNMENT + count);
132 bcachep->cache_bytes += BCACHE_DATA_ALIGNMENT + count;
133 memcpy (BCACHE_DATA (newlink), bytes, count);
134 newlink->next = *linkpp;
136 location = BCACHE_DATA (newlink);
143 print_bcache_statistics (bcachep, id)
144 struct bcache *bcachep;
147 struct hashlink **hashtablep;
148 struct hashlink *linkp;
149 int tidx, tcount, hidx, hcount, lcount, lmax, temp, lmaxt, lmaxh;
151 for (lmax = lcount = tcount = hcount = tidx = 0; tidx < BCACHE_MAXLENGTH; tidx++)
153 hashtablep = bcachep->indextable[tidx];
154 if (hashtablep != NULL)
157 for (hidx = 0; hidx < BCACHE_HASHSIZE; hidx++)
159 linkp = hashtablep[hidx];
163 for (temp = 0; linkp != NULL; linkp = linkp->next)
178 printf_filtered (" Cached '%s' statistics:\n", id);
179 printf_filtered (" Cache hits: %d\n", bcachep->cache_hits);
180 printf_filtered (" Cache misses: %d\n", bcachep->cache_misses);
181 printf_filtered (" Cache hit ratio: ");
182 if (bcachep->cache_hits + bcachep->cache_misses > 0)
184 printf_filtered ("%d%%\n", ((bcachep->cache_hits) * 100) /
185 (bcachep->cache_hits + bcachep->cache_misses));
189 printf_filtered ("(not applicable)\n");
191 printf_filtered (" Space used for caching: %d\n", bcachep->cache_bytes);
192 printf_filtered (" Space saved by cache hits: %d\n", bcachep->cache_savings);
193 printf_filtered (" Number of bcache overflows: %d\n", bcachep->bcache_overflows);
194 printf_filtered (" Number of index buckets used: %d\n", tcount);
195 printf_filtered (" Number of hash table buckets used: %d\n", hcount);
196 printf_filtered (" Number of chained items: %d\n", lcount);
197 printf_filtered (" Average hash table population: ");
200 printf_filtered ("%d%%\n", (hcount * 100) / (tcount * BCACHE_HASHSIZE));
204 printf_filtered ("(not applicable)\n");
206 printf_filtered (" Average chain length ");
209 printf_filtered ("%d\n", lcount / hcount);
213 printf_filtered ("(not applicable)\n");
215 printf_filtered (" Maximum chain length %d at %d:%d\n", lmax, lmaxt, lmaxh);