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. */
25 /* FIXME: Incredibly simplistic hash generator. Probably way too expensive
26 (consider long strings) and unlikely to have good distribution across hash
27 values for typical input. */
35 unsigned long hashval
;
37 const unsigned char *data
= bytes
;
44 hashval
+= c
+ (c
<< 17);
45 hashval
^= hashval
>> 2;
48 hashval
+= len
+ (len
<< 17);
49 hashval
^= hashval
>> 2;
50 return (hashval
% BCACHE_HASHSIZE
);
54 lookup_cache (bytes
, count
, hashval
, bcachep
)
58 struct bcache
*bcachep
;
60 void *location
= NULL
;
61 struct hashlink
**hashtablep
;
62 struct hashlink
*linkp
;
64 hashtablep
= bcachep
-> indextable
[count
];
65 if (hashtablep
!= NULL
)
67 linkp
= hashtablep
[hashval
];
70 if (memcmp (linkp
-> data
, bytes
, count
) == 0)
72 location
= linkp
-> data
;
75 linkp
= linkp
-> next
;
82 bcache (bytes
, count
, bcachep
)
85 struct bcache
*bcachep
;
89 struct hashlink
*newlink
;
90 struct hashlink
**linkpp
;
91 struct hashlink
***hashtablepp
;
93 if (count
> BCACHE_MAXLENGTH
)
95 /* Rare enough to just stash unique copies */
96 location
= (void *) obstack_alloc (&bcachep
->cache
, count
);
97 bcachep
-> cache_bytes
+= count
;
98 memcpy (location
, bytes
, count
);
99 bcachep
-> bcache_overflows
++;
103 hashval
= hash (bytes
, count
);
104 location
= lookup_cache (bytes
, count
, hashval
, bcachep
);
105 if (location
!= NULL
)
107 bcachep
-> cache_savings
+= count
;
108 bcachep
-> cache_hits
++;
112 bcachep
-> cache_misses
++;
113 hashtablepp
= &bcachep
-> indextable
[count
];
114 if (*hashtablepp
== NULL
)
116 *hashtablepp
= (struct hashlink
**)
117 obstack_alloc (&bcachep
->cache
, BCACHE_HASHSIZE
* sizeof (struct hashlink
*));
118 bcachep
-> cache_bytes
+= sizeof (struct hashlink
*);
119 memset (*hashtablepp
, 0, BCACHE_HASHSIZE
* sizeof (struct hashlink
*));
121 linkpp
= &(*hashtablepp
)[hashval
];
122 newlink
= (struct hashlink
*)
123 obstack_alloc (&bcachep
->cache
, sizeof (struct hashlink
*) + count
);
124 bcachep
-> cache_bytes
+= sizeof (struct hashlink
*) + count
;
125 memcpy (newlink
-> data
, bytes
, count
);
126 newlink
-> next
= *linkpp
;
128 location
= newlink
-> data
;
137 print_bcache_statistics (bcachep
, id
)
138 struct bcache
*bcachep
;
141 struct hashlink
**hashtablep
;
142 struct hashlink
*linkp
;
143 int tidx
, tcount
, hidx
, hcount
, lcount
, lmax
, temp
, lmaxt
, lmaxh
;
145 for (lmax
= lcount
= tcount
= hcount
= tidx
= 0; tidx
< BCACHE_MAXLENGTH
; tidx
++)
147 hashtablep
= bcachep
-> indextable
[tidx
];
148 if (hashtablep
!= NULL
)
151 for (hidx
= 0; hidx
< BCACHE_HASHSIZE
; hidx
++)
153 linkp
= hashtablep
[hidx
];
157 for (temp
= 0; linkp
!= NULL
; linkp
= linkp
-> next
)
172 printf_filtered (" Cached '%s' statistics:\n", id
);
173 printf_filtered (" Cache hits: %d\n", bcachep
-> cache_hits
);
174 printf_filtered (" Cache misses: %d\n", bcachep
-> cache_misses
);
175 printf_filtered (" Cache hit ratio: %d%%\n", ((bcachep
-> cache_hits
) * 100) / (bcachep
-> cache_hits
+ bcachep
-> cache_misses
));
176 printf_filtered (" Space used for caching: %d\n", bcachep
-> cache_bytes
);
177 printf_filtered (" Space saved by cache hits: %d\n", bcachep
-> cache_savings
);
178 printf_filtered (" Number of bcache overflows: %d\n", bcachep
-> bcache_overflows
);
179 printf_filtered (" Number of index buckets used: %d\n", tcount
);
180 printf_filtered (" Number of hash table buckets used: %d\n", hcount
);
181 printf_filtered (" Number of chained items: %d\n", lcount
);
182 printf_filtered (" Average hash table population: %d%%\n",
183 (hcount
* 100) / (tcount
* BCACHE_HASHSIZE
));
184 printf_filtered (" Average chain length %d\n", lcount
/ hcount
);
185 printf_filtered (" Maximum chain length %d at %d:%d\n", lmax
, lmaxt
, lmaxh
);
188 #endif /* MAINTENANCE_CMDS */
This page took 0.043969 seconds and 4 git commands to generate.