contrib/gdb/gdb/bcache.c

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