gdb/bcache.c

   1 /* Implement a cached obstack.
   2    Written by Fred Fish (fnf@cygnus.com)
   3    Copyright 1995 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
  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. */
  28
  29 static unsigned int
  30 hash (bytes, count)
  31      void *bytes;
  32      int count;
  33 {
  34   unsigned int len;
  35   unsigned long hashval;
  36   unsigned int c;
  37   const unsigned char *data = bytes;
  38
  39   hashval = 0;
  40   len = 0;
  41   while (count-- > 0)
  42     {
  43       c = *data++;
  44       hashval += c + (c << 17);
  45       hashval ^= hashval >> 2;
  46       ++len;
  47     }
  48   hashval += len + (len << 17);
  49   hashval ^= hashval >> 2;
  50   return (hashval % BCACHE_HASHSIZE);
  51 }
  52
  53 static void *
  54 lookup_cache (bytes, count, hashval, bcachep)
  55      void *bytes;
  56      int count;
  57      int hashval;
  58      struct bcache *bcachep;
  59 {
  60   void *location = NULL;
  61   struct hashlink **hashtablep;
  62   struct hashlink *linkp;
  63
  64   hashtablep = bcachep -> indextable[count];
  65   if (hashtablep != NULL)
  66     {
  67       linkp = hashtablep[hashval];
  68       while (linkp != NULL)
  69         {
  70           if (memcmp (linkp -> data, bytes, count) == 0)
  71             {
  72               location = linkp -> data;
  73               break;
  74             }
  75           linkp = linkp -> next;
  76         }
  77     }
  78   return (location);
  79 }
  80
  81 void *
  82 bcache (bytes, count, bcachep)
  83      void *bytes;
  84      int count;
  85      struct bcache *bcachep;
  86 {
  87   int hashval;
  88   void *location;
  89   struct hashlink *newlink;
  90   struct hashlink **linkpp;
  91   struct hashlink ***hashtablepp;
  92
  93   if (count > BCACHE_MAXLENGTH)
  94     {
  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++;
 100     }
 101   else
 102     {
 103       hashval = hash (bytes, count);
 104       location = lookup_cache (bytes, count, hashval, bcachep);
 105       if (location != NULL)
 106         {
 107           bcachep -> cache_savings += count;
 108           bcachep -> cache_hits++;
 109         }
 110       else
 111         {
 112           bcachep -> cache_misses++;
 113           hashtablepp = &bcachep -> indextable[count];
 114           if (*hashtablepp == NULL)
 115             {
 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 *));
 120             }
 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;
 127           *linkpp = newlink;
 128           location = newlink -> data;
 129         }
 130     }
 131   return (location);
 132 }
 133
 134 #if MAINTENANCE_CMDS
 135
 136 void
 137 print_bcache_statistics (bcachep, id)
 138      struct bcache *bcachep;
 139      char *id;
 140 {
 141   struct hashlink **hashtablep;
 142   struct hashlink *linkp;
 143   int tidx, tcount, hidx, hcount, lcount, lmax, temp, lmaxt, lmaxh;
 144
 145   for (lmax = lcount = tcount = hcount = tidx = 0; tidx < BCACHE_MAXLENGTH; tidx++)
 146     {
 147       hashtablep = bcachep -> indextable[tidx];
 148       if (hashtablep != NULL)
 149         {
 150           tcount++;
 151           for (hidx = 0; hidx < BCACHE_HASHSIZE; hidx++)
 152             {
 153               linkp = hashtablep[hidx];
 154               if (linkp != NULL)
 155                 {
 156                   hcount++;
 157                   for (temp = 0; linkp != NULL; linkp = linkp -> next)
 158                     {
 159                       lcount++;
 160                       temp++;
 161                     }
 162                   if (temp > lmax)
 163                     {
 164                       lmax = temp;
 165                       lmaxt = tidx;
 166                       lmaxh = hidx;
 167                     }
 168                 }
 169             }
 170         }
 171     }
 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);
 186 }
 187
 188 #endif  /* MAINTENANCE_CMDS */