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 } 217
