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
);
This page took 0.045779 seconds and 5 git commands to generate.