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