| /* Implement a cached obstack. |
| Written by Fred Fish (fnf@cygnus.com) |
| Copyright 1995, 1998 Free Software Foundation, Inc. |
| |
| This file is part of GDB. |
| |
| This program is free software; you can redistribute it and/or modify |
| it under the terms of the GNU General Public License as published by |
| the Free Software Foundation; either version 2 of the License, or |
| (at your option) any later version. |
| |
| This program is distributed in the hope that it will be useful, |
| but WITHOUT ANY WARRANTY; without even the implied warranty of |
| MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| GNU General Public License for more details. |
| |
| You should have received a copy of the GNU General Public License |
| along with this program; if not, write to the Free Software |
| Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ |
| |
| #include "defs.h" |
| #include "obstack.h" |
| #include "bcache.h" |
| #include "gdb_string.h" /* For memcpy declaration */ |
| |
| /* Prototypes for local functions. */ |
| |
| static unsigned int hash PARAMS ((void *, int)); |
| |
| static void *lookup_cache PARAMS ((void *, int, int, struct bcache *)); |
| |
| /* FIXME: Incredibly simplistic hash generator. Probably way too expensive |
| (consider long strings) and unlikely to have good distribution across hash |
| values for typical input. */ |
| |
| static unsigned int |
| hash (bytes, count) |
| void *bytes; |
| int count; |
| { |
| unsigned int len; |
| unsigned long hashval; |
| unsigned int c; |
| const unsigned char *data = bytes; |
| |
| hashval = 0; |
| len = 0; |
| while (count-- > 0) |
| { |
| c = *data++; |
| hashval += c + (c << 17); |
| hashval ^= hashval >> 2; |
| ++len; |
| } |
| hashval += len + (len << 17); |
| hashval ^= hashval >> 2; |
| return (hashval % BCACHE_HASHSIZE); |
| } |
| |
| static void * |
| lookup_cache (bytes, count, hashval, bcachep) |
| void *bytes; |
| int count; |
| int hashval; |
| struct bcache *bcachep; |
| { |
| void *location = NULL; |
| struct hashlink **hashtablep; |
| struct hashlink *linkp; |
| |
| hashtablep = bcachep -> indextable[count]; |
| if (hashtablep != NULL) |
| { |
| linkp = hashtablep[hashval]; |
| while (linkp != NULL) |
| { |
| if (memcmp (BCACHE_DATA (linkp), bytes, count) == 0) |
| { |
| location = BCACHE_DATA (linkp); |
| break; |
| } |
| linkp = linkp -> next; |
| } |
| } |
| return (location); |
| } |
| |
| void * |
| bcache (bytes, count, bcachep) |
| void *bytes; |
| int count; |
| struct bcache *bcachep; |
| { |
| int hashval; |
| void *location; |
| struct hashlink *newlink; |
| struct hashlink **linkpp; |
| struct hashlink ***hashtablepp; |
| |
| if (count >= BCACHE_MAXLENGTH) |
| { |
| /* Rare enough to just stash unique copies */ |
| location = (void *) obstack_alloc (&bcachep->cache, count); |
| bcachep -> cache_bytes += count; |
| memcpy (location, bytes, count); |
| bcachep -> bcache_overflows++; |
| } |
| else |
| { |
| hashval = hash (bytes, count); |
| location = lookup_cache (bytes, count, hashval, bcachep); |
| if (location != NULL) |
| { |
| bcachep -> cache_savings += count; |
| bcachep -> cache_hits++; |
| } |
| else |
| { |
| bcachep -> cache_misses++; |
| hashtablepp = &bcachep -> indextable[count]; |
| if (*hashtablepp == NULL) |
| { |
| *hashtablepp = (struct hashlink **) |
| obstack_alloc (&bcachep->cache, BCACHE_HASHSIZE * sizeof (struct hashlink *)); |
| bcachep -> cache_bytes += BCACHE_HASHSIZE * sizeof (struct hashlink *); |
| memset (*hashtablepp, 0, BCACHE_HASHSIZE * sizeof (struct hashlink *)); |
| } |
| linkpp = &(*hashtablepp)[hashval]; |
| newlink = (struct hashlink *) |
| obstack_alloc (&bcachep->cache, BCACHE_DATA_ALIGNMENT + count); |
| bcachep -> cache_bytes += BCACHE_DATA_ALIGNMENT + count; |
| memcpy (BCACHE_DATA (newlink), bytes, count); |
| newlink -> next = *linkpp; |
| *linkpp = newlink; |
| location = BCACHE_DATA (newlink); |
| } |
| } |
| return (location); |
| } |
| |
| void |
| print_bcache_statistics (bcachep, id) |
| struct bcache *bcachep; |
| char *id; |
| { |
| struct hashlink **hashtablep; |
| struct hashlink *linkp; |
| int tidx, tcount, hidx, hcount, lcount, lmax, temp, lmaxt, lmaxh; |
| |
| for (lmax = lcount = tcount = hcount = tidx = 0; tidx < BCACHE_MAXLENGTH; tidx++) |
| { |
| hashtablep = bcachep -> indextable[tidx]; |
| if (hashtablep != NULL) |
| { |
| tcount++; |
| for (hidx = 0; hidx < BCACHE_HASHSIZE; hidx++) |
| { |
| linkp = hashtablep[hidx]; |
| if (linkp != NULL) |
| { |
| hcount++; |
| for (temp = 0; linkp != NULL; linkp = linkp -> next) |
| { |
| lcount++; |
| temp++; |
| } |
| if (temp > lmax) |
| { |
| lmax = temp; |
| lmaxt = tidx; |
| lmaxh = hidx; |
| } |
| } |
| } |
| } |
| } |
| printf_filtered (" Cached '%s' statistics:\n", id); |
| printf_filtered (" Cache hits: %d\n", bcachep -> cache_hits); |
| printf_filtered (" Cache misses: %d\n", bcachep -> cache_misses); |
| printf_filtered (" Cache hit ratio: "); |
| if (bcachep -> cache_hits + bcachep -> cache_misses > 0) |
| { |
| printf_filtered ("%d%%\n", ((bcachep -> cache_hits) * 100) / |
| (bcachep -> cache_hits + bcachep -> cache_misses)); |
| } |
| else |
| { |
| printf_filtered ("(not applicable)\n"); |
| } |
| printf_filtered (" Space used for caching: %d\n", bcachep -> cache_bytes); |
| printf_filtered (" Space saved by cache hits: %d\n", bcachep -> cache_savings); |
| printf_filtered (" Number of bcache overflows: %d\n", bcachep -> bcache_overflows); |
| printf_filtered (" Number of index buckets used: %d\n", tcount); |
| printf_filtered (" Number of hash table buckets used: %d\n", hcount); |
| printf_filtered (" Number of chained items: %d\n", lcount); |
| printf_filtered (" Average hash table population: "); |
| if (tcount > 0) |
| { |
| printf_filtered ("%d%%\n", (hcount * 100) / (tcount * BCACHE_HASHSIZE)); |
| } |
| else |
| { |
| printf_filtered ("(not applicable)\n"); |
| } |
| printf_filtered (" Average chain length "); |
| if (hcount > 0) |
| { |
| printf_filtered ("%d\n", lcount / hcount); |
| } |
| else |
| { |
| printf_filtered ("(not applicable)\n"); |
| } |
| printf_filtered (" Maximum chain length %d at %d:%d\n", lmax, lmaxt, lmaxh); |
| } |