1 /* Implement a cached obstack.
2 Written by Fred Fish (fnf@cygnus.com)
3 Copyright 1995 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, Boston, MA 02111-1307, USA. */
24 #include "gdb_string.h" /* For memcpy declaration */
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. */
36 unsigned long hashval
;
38 const unsigned char *data
= bytes
;
45 hashval
+= c
+ (c
<< 17);
46 hashval
^= hashval
>> 2;
49 hashval
+= len
+ (len
<< 17);
50 hashval
^= hashval
>> 2;
51 return (hashval
% BCACHE_HASHSIZE
);
55 lookup_cache (bytes
, count
, hashval
, bcachep
)
59 struct bcache
*bcachep
;
61 void *location
= NULL
;
62 struct hashlink
**hashtablep
;
63 struct hashlink
*linkp
;
65 hashtablep
= bcachep
-> indextable
[count
];
66 if (hashtablep
!= NULL
)
68 linkp
= hashtablep
[hashval
];
71 if (memcmp (BCACHE_DATA (linkp
), bytes
, count
) == 0)
73 location
= BCACHE_DATA (linkp
);
76 linkp
= linkp
-> next
;
83 bcache (bytes
, count
, bcachep
)
86 struct bcache
*bcachep
;
90 struct hashlink
*newlink
;
91 struct hashlink
**linkpp
;
92 struct hashlink
***hashtablepp
;
94 if (count
>= BCACHE_MAXLENGTH
)
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
++;
104 hashval
= hash (bytes
, count
);
105 location
= lookup_cache (bytes
, count
, hashval
, bcachep
);
106 if (location
!= NULL
)
108 bcachep
-> cache_savings
+= count
;
109 bcachep
-> cache_hits
++;
113 bcachep
-> cache_misses
++;
114 hashtablepp
= &bcachep
-> indextable
[count
];
115 if (*hashtablepp
== NULL
)
117 *hashtablepp
= (struct hashlink
**)
118 obstack_alloc (&bcachep
->cache
, BCACHE_HASHSIZE
* sizeof (struct hashlink
*));
119 bcachep
-> cache_bytes
+= BCACHE_HASHSIZE
* sizeof (struct hashlink
*);
120 memset (*hashtablepp
, 0, BCACHE_HASHSIZE
* sizeof (struct hashlink
*));
122 linkpp
= &(*hashtablepp
)[hashval
];
123 newlink
= (struct hashlink
*)
124 obstack_alloc (&bcachep
->cache
, BCACHE_DATA_ALIGNMENT
+ count
);
125 bcachep
-> cache_bytes
+= BCACHE_DATA_ALIGNMENT
+ count
;
126 memcpy (BCACHE_DATA (newlink
), bytes
, count
);
127 newlink
-> next
= *linkpp
;
129 location
= BCACHE_DATA (newlink
);
138 print_bcache_statistics (bcachep
, id
)
139 struct bcache
*bcachep
;
142 struct hashlink
**hashtablep
;
143 struct hashlink
*linkp
;
144 int tidx
, tcount
, hidx
, hcount
, lcount
, lmax
, temp
, lmaxt
, lmaxh
;
146 for (lmax
= lcount
= tcount
= hcount
= tidx
= 0; tidx
< BCACHE_MAXLENGTH
; tidx
++)
148 hashtablep
= bcachep
-> indextable
[tidx
];
149 if (hashtablep
!= NULL
)
152 for (hidx
= 0; hidx
< BCACHE_HASHSIZE
; hidx
++)
154 linkp
= hashtablep
[hidx
];
158 for (temp
= 0; linkp
!= NULL
; linkp
= linkp
-> next
)
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
);
176 printf_filtered (" Cache hit ratio: %d%%\n", ((bcachep
-> cache_hits
) * 100) / (bcachep
-> cache_hits
+ bcachep
-> cache_misses
));
177 printf_filtered (" Space used for caching: %d\n", bcachep
-> cache_bytes
);
178 printf_filtered (" Space saved by cache hits: %d\n", bcachep
-> cache_savings
);
179 printf_filtered (" Number of bcache overflows: %d\n", bcachep
-> bcache_overflows
);
180 printf_filtered (" Number of index buckets used: %d\n", tcount
);
181 printf_filtered (" Number of hash table buckets used: %d\n", hcount
);
182 printf_filtered (" Number of chained items: %d\n", lcount
);
183 printf_filtered (" Average hash table population: %d%%\n",
184 (hcount
* 100) / (tcount
* BCACHE_HASHSIZE
));
185 printf_filtered (" Average chain length %d\n", lcount
/ hcount
);
186 printf_filtered (" Maximum chain length %d at %d:%d\n", lmax
, lmaxt
, lmaxh
);
189 #endif /* MAINTENANCE_CMDS */
This page took 0.036244 seconds and 4 git commands to generate.