strcache.c

   1 /* Constant string caching for GNU Make.
   2 Copyright (C) 2006 Free Software Foundation, Inc.
   3 This file is part of GNU Make.
   4
   5 GNU Make is free software; you can redistribute it and/or modify it under the
   6 terms of the GNU General Public License as published by the Free Software
   7 Foundation; either version 2, or (at your option) any later version.
   8
   9 GNU Make is distributed in the hope that it will be useful, but WITHOUT ANY
  10 WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
  11 A PARTICULAR PURPOSE.  See the GNU General Public License for more details.
  12
  13 You should have received a copy of the GNU General Public License along with
  14 GNU Make; see the file COPYING.  If not, write to the Free Software
  15 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.  */
  16
  17 #include "make.h"
  18
  19 #include <assert.h>
  20
  21 #include "hash.h"
  22
  23 /* The size (in bytes) of each cache buffer.  */
  24 #define CACHE_BUFFER_SIZE   (4096)
  25
  26
  27 /* A string cached here will never be freed, so we don't need to worry about
  28    reference counting.  We just store the string, and then remember it in a
  29    hash so it can be looked up again. */
  30
  31 struct strcache {
  32   struct strcache *next;    /* The next block of strings.  */
  33   char *end;                /* Pointer to the beginning of the free space.  */
  34   int count;                /* # of strings in this buffer (for stats).  */
  35   int bytesfree;            /* The amount of the buffer that is free.  */
  36   char buffer[1];           /* The buffer comes after this.  */
  37 };
  38
  39 static int bufsize = CACHE_BUFFER_SIZE;
  40 static struct strcache *strcache = NULL;
  41
  42 static struct strcache *
  43 new_cache()
  44 {
  45   struct strcache *new;
  46   new = (struct strcache *) xmalloc (sizeof (*new) + bufsize);
  47   new->end = new->buffer;
  48   new->count = 0;
  49   new->bytesfree = bufsize;
  50
  51   new->next = strcache;
  52   strcache = new;
  53
  54   return new;
  55 }
  56
  57 static const char *
  58 add_string(const char *str, int len)
  59 {
  60   struct strcache *best = NULL;
  61   struct strcache *sp;
  62   const char *res;
  63
  64   /* If the string we want is too large to fit into a single buffer, then we're
  65      screwed; nothing will ever fit!  Change the maximum size of the cache to
  66      be big enough.  */
  67   if (len > bufsize)
  68     bufsize = len * 2;
  69
  70   /* First, find a cache with enough free space.  We always look through all
  71      the blocks and choose the one with the best fit (the one that leaves the
  72      least amount of space free).  */
  73   for (sp = strcache; sp != NULL; sp = sp->next)
  74     if (sp->bytesfree > len && (!best || best->bytesfree > sp->bytesfree))
  75       best = sp;
  76
  77   /* If nothing is big enough, make a new cache.  */
  78   if (!best)
  79     best = new_cache();
  80
  81   assert (best->bytesfree > len);
  82
  83   /* Add the string to the best cache.  */
  84   res = best->end;
  85   memcpy (best->end, str, len);
  86   best->end += len;
  87   *(best->end++) = '\0';
  88   best->bytesfree -= len + 1;
  89   ++best->count;
  90
  91   return res;
  92 }
  93
  94
  95 /* Hash table of strings in the cache.  */
  96
  97 static unsigned long
  98 str_hash_1 (const void *key)
  99 {
 100   return_ISTRING_HASH_1 ((const char *) key);
 101 }
 102
 103 static unsigned long
 104 str_hash_2 (const void *key)
 105 {
 106   return_ISTRING_HASH_2 ((const char *) key);
 107 }
 108
 109 static int
 110 str_hash_cmp (const void *x, const void *y)
 111 {
 112   return_ISTRING_COMPARE ((const char *) x, (const char *) y);
 113 }
 114
 115 static struct hash_table strings;
 116
 117 static const char *
 118 add_hash (const char *str, int len)
 119 {
 120   /* Look up the string in the hash.  If it's there, return it.  */
 121   char **slot = (char **) hash_find_slot (&strings, str);
 122   const char *key = *slot;
 123
 124   if (!HASH_VACANT (key))
 125     return key;
 126
 127   /* Not there yet so add it to a buffer, then into the hash table.  */
 128   key = add_string (str, len);
 129   hash_insert_at (&strings, key, slot);
 130   return key;
 131 }
 132
 133 /* Returns true if the string is in the cache; false if not.  */
 134 int
 135 strcache_iscached (const char *str)
 136 {
 137   struct strcache *sp;
 138
 139   for (sp = strcache; sp != 0; sp = sp->next)
 140     if (str >= sp->buffer && str < sp->end)
 141       return 1;
 142
 143   return 0;
 144 }
 145
 146 /* If the string is already in the cache, return a pointer to the cached
 147    version.  If not, add it then return a pointer to the cached version.
 148    Note we do NOT take control of the string passed in.  */
 149 const char *
 150 strcache_add (const char *str)
 151 {
 152   return add_hash (str, strlen (str));
 153 }
 154
 155 const char *
 156 strcache_add_len (const char *str, int len)
 157 {
 158   char *key = alloca (len + 1);
 159   memcpy (key, str, len);
 160   key[len] = '\0';
 161
 162   return add_hash (key, len);
 163 }
 164
 165 int
 166 strcache_setbufsize(int size)
 167 {
 168   if (size > bufsize)
 169     bufsize = size;
 170   return bufsize;
 171 }
 172
 173 void
 174 strcache_init (void)
 175 {
 176   hash_init (&strings, 1000, str_hash_1, str_hash_2, str_hash_cmp);
 177 }
 178
 179
 180 /* Generate some stats output.  */
 181
 182 void
 183 strcache_print_stats (const char *prefix)
 184 {
 185   int numbuffs = 0, numstrs = 0;
 186   int totsize = 0, avgsize, maxsize = 0, minsize = bufsize;
 187   int totfree = 0, avgfree, maxfree = 0, minfree = bufsize;
 188   const struct strcache *sp;
 189
 190   for (sp = strcache; sp != NULL; sp = sp->next)
 191     {
 192       int bf = sp->bytesfree;
 193       int sz = (sp->end - sp->buffer) + bf;
 194
 195       ++numbuffs;
 196       numstrs += sp->count;
 197
 198       totsize += sz;
 199       maxsize = (sz > maxsize ? sz : maxsize);
 200       minsize = (sz < minsize ? sz : minsize);
 201
 202       totfree += bf;
 203       maxfree = (bf > maxfree ? bf : maxfree);
 204       minfree = (bf < minfree ? bf : minfree);
 205     }
 206
 207   avgsize = numbuffs ? (int)(totsize / numbuffs) : 0;
 208   avgfree = numbuffs ? (int)(totfree / numbuffs) : 0;
 209
 210   printf (_("\n%s # of strings in strcache: %d\n"), prefix, numstrs);
 211   printf (_("%s # of strcache buffers: %d\n"), prefix, numbuffs);
 212   printf (_("%s strcache size: total = %d / max = %d / min = %d / avg = %d\n"),
 213           prefix, totsize, maxsize, minsize, avgsize);
 214   printf (_("%s strcache free: total = %d / max = %d / min = %d / avg = %d\n"),
 215           prefix, totfree, maxfree, minfree, avgfree);
 216 }