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