Commit | Line | Data |
---|---|---|
c906108c SS |
1 | /* Implement a cached obstack. |
2 | Written by Fred Fish (fnf@cygnus.com) | |
3 | Copyright 1995, 1998 Free Software Foundation, Inc. | |
4 | ||
c5aa993b | 5 | This file is part of GDB. |
c906108c | 6 | |
c5aa993b JM |
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. | |
c906108c | 11 | |
c5aa993b JM |
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. | |
c906108c | 16 | |
c5aa993b JM |
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. */ | |
c906108c SS |
21 | |
22 | #include "defs.h" | |
23 | #include "obstack.h" | |
24 | #include "bcache.h" | |
25 | #include "gdb_string.h" /* For memcpy declaration */ | |
26 | ||
27 | /* Prototypes for local functions. */ | |
28 | ||
29 | static unsigned int hash PARAMS ((void *, int)); | |
30 | ||
31 | static void *lookup_cache PARAMS ((void *, int, int, struct bcache *)); | |
32 | ||
33 | /* FIXME: Incredibly simplistic hash generator. Probably way too expensive | |
c5aa993b JM |
34 | (consider long strings) and unlikely to have good distribution across hash |
35 | values for typical input. */ | |
c906108c SS |
36 | |
37 | static unsigned int | |
38 | hash (bytes, count) | |
39 | void *bytes; | |
40 | int count; | |
41 | { | |
42 | unsigned int len; | |
43 | unsigned long hashval; | |
44 | unsigned int c; | |
45 | const unsigned char *data = bytes; | |
46 | ||
47 | hashval = 0; | |
48 | len = 0; | |
49 | while (count-- > 0) | |
50 | { | |
51 | c = *data++; | |
52 | hashval += c + (c << 17); | |
53 | hashval ^= hashval >> 2; | |
54 | ++len; | |
55 | } | |
56 | hashval += len + (len << 17); | |
57 | hashval ^= hashval >> 2; | |
58 | return (hashval % BCACHE_HASHSIZE); | |
59 | } | |
60 | ||
61 | static void * | |
62 | lookup_cache (bytes, count, hashval, bcachep) | |
63 | void *bytes; | |
64 | int count; | |
65 | int hashval; | |
66 | struct bcache *bcachep; | |
67 | { | |
68 | void *location = NULL; | |
69 | struct hashlink **hashtablep; | |
70 | struct hashlink *linkp; | |
71 | ||
c5aa993b | 72 | hashtablep = bcachep->indextable[count]; |
c906108c SS |
73 | if (hashtablep != NULL) |
74 | { | |
75 | linkp = hashtablep[hashval]; | |
76 | while (linkp != NULL) | |
77 | { | |
78 | if (memcmp (BCACHE_DATA (linkp), bytes, count) == 0) | |
79 | { | |
80 | location = BCACHE_DATA (linkp); | |
81 | break; | |
82 | } | |
c5aa993b | 83 | linkp = linkp->next; |
c906108c SS |
84 | } |
85 | } | |
86 | return (location); | |
87 | } | |
88 | ||
89 | void * | |
90 | bcache (bytes, count, bcachep) | |
91 | void *bytes; | |
92 | int count; | |
93 | struct bcache *bcachep; | |
94 | { | |
95 | int hashval; | |
96 | void *location; | |
97 | struct hashlink *newlink; | |
98 | struct hashlink **linkpp; | |
99 | struct hashlink ***hashtablepp; | |
100 | ||
101 | if (count >= BCACHE_MAXLENGTH) | |
102 | { | |
103 | /* Rare enough to just stash unique copies */ | |
104 | location = (void *) obstack_alloc (&bcachep->cache, count); | |
c5aa993b | 105 | bcachep->cache_bytes += count; |
c906108c | 106 | memcpy (location, bytes, count); |
c5aa993b | 107 | bcachep->bcache_overflows++; |
c906108c SS |
108 | } |
109 | else | |
110 | { | |
111 | hashval = hash (bytes, count); | |
112 | location = lookup_cache (bytes, count, hashval, bcachep); | |
113 | if (location != NULL) | |
114 | { | |
c5aa993b JM |
115 | bcachep->cache_savings += count; |
116 | bcachep->cache_hits++; | |
c906108c SS |
117 | } |
118 | else | |
119 | { | |
c5aa993b JM |
120 | bcachep->cache_misses++; |
121 | hashtablepp = &bcachep->indextable[count]; | |
c906108c SS |
122 | if (*hashtablepp == NULL) |
123 | { | |
124 | *hashtablepp = (struct hashlink **) | |
125 | obstack_alloc (&bcachep->cache, BCACHE_HASHSIZE * sizeof (struct hashlink *)); | |
c5aa993b | 126 | bcachep->cache_bytes += BCACHE_HASHSIZE * sizeof (struct hashlink *); |
c906108c SS |
127 | memset (*hashtablepp, 0, BCACHE_HASHSIZE * sizeof (struct hashlink *)); |
128 | } | |
129 | linkpp = &(*hashtablepp)[hashval]; | |
130 | newlink = (struct hashlink *) | |
131 | obstack_alloc (&bcachep->cache, BCACHE_DATA_ALIGNMENT + count); | |
c5aa993b | 132 | bcachep->cache_bytes += BCACHE_DATA_ALIGNMENT + count; |
c906108c | 133 | memcpy (BCACHE_DATA (newlink), bytes, count); |
c5aa993b | 134 | newlink->next = *linkpp; |
c906108c SS |
135 | *linkpp = newlink; |
136 | location = BCACHE_DATA (newlink); | |
137 | } | |
138 | } | |
139 | return (location); | |
140 | } | |
141 | ||
c906108c SS |
142 | void |
143 | print_bcache_statistics (bcachep, id) | |
144 | struct bcache *bcachep; | |
145 | char *id; | |
146 | { | |
147 | struct hashlink **hashtablep; | |
148 | struct hashlink *linkp; | |
149 | int tidx, tcount, hidx, hcount, lcount, lmax, temp, lmaxt, lmaxh; | |
150 | ||
151 | for (lmax = lcount = tcount = hcount = tidx = 0; tidx < BCACHE_MAXLENGTH; tidx++) | |
152 | { | |
c5aa993b | 153 | hashtablep = bcachep->indextable[tidx]; |
c906108c SS |
154 | if (hashtablep != NULL) |
155 | { | |
156 | tcount++; | |
157 | for (hidx = 0; hidx < BCACHE_HASHSIZE; hidx++) | |
158 | { | |
159 | linkp = hashtablep[hidx]; | |
160 | if (linkp != NULL) | |
161 | { | |
162 | hcount++; | |
c5aa993b | 163 | for (temp = 0; linkp != NULL; linkp = linkp->next) |
c906108c SS |
164 | { |
165 | lcount++; | |
166 | temp++; | |
167 | } | |
168 | if (temp > lmax) | |
169 | { | |
170 | lmax = temp; | |
171 | lmaxt = tidx; | |
172 | lmaxh = hidx; | |
173 | } | |
174 | } | |
175 | } | |
176 | } | |
177 | } | |
178 | printf_filtered (" Cached '%s' statistics:\n", id); | |
c5aa993b JM |
179 | printf_filtered (" Cache hits: %d\n", bcachep->cache_hits); |
180 | printf_filtered (" Cache misses: %d\n", bcachep->cache_misses); | |
c906108c | 181 | printf_filtered (" Cache hit ratio: "); |
c5aa993b | 182 | if (bcachep->cache_hits + bcachep->cache_misses > 0) |
c906108c | 183 | { |
c5aa993b JM |
184 | printf_filtered ("%d%%\n", ((bcachep->cache_hits) * 100) / |
185 | (bcachep->cache_hits + bcachep->cache_misses)); | |
c906108c SS |
186 | } |
187 | else | |
188 | { | |
189 | printf_filtered ("(not applicable)\n"); | |
190 | } | |
c5aa993b JM |
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); | |
c906108c SS |
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: "); | |
198 | if (tcount > 0) | |
199 | { | |
200 | printf_filtered ("%d%%\n", (hcount * 100) / (tcount * BCACHE_HASHSIZE)); | |
201 | } | |
202 | else | |
203 | { | |
204 | printf_filtered ("(not applicable)\n"); | |
205 | } | |
206 | printf_filtered (" Average chain length "); | |
207 | if (hcount > 0) | |
208 | { | |
209 | printf_filtered ("%d\n", lcount / hcount); | |
210 | } | |
211 | else | |
212 | { | |
213 | printf_filtered ("(not applicable)\n"); | |
214 | } | |
215 | printf_filtered (" Maximum chain length %d at %d:%d\n", lmax, lmaxt, lmaxh); | |
216 | } |