Update the required version of gettext to get new bugfix macros.
[make.git] / strcache.c
blob3e8d5d870be47e6204e68128a1d9be622a627290
1 /* Constant string caching for GNU Make.
2 Copyright (C) 2006-2012 Free Software Foundation, Inc.
3 This file is part of GNU Make.
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 3 of the License, or (at your option) any later
8 version.
10 GNU Make is distributed in the hope that it will be useful, but WITHOUT ANY
11 WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
12 A PARTICULAR PURPOSE. See the GNU General Public License for more details.
14 You should have received a copy of the GNU General Public License along with
15 this program. If not, see <http://www.gnu.org/licenses/>. */
17 #include "make.h"
19 #include <stddef.h>
20 #include <assert.h>
22 #include "hash.h"
24 /* A string cached here will never be freed, so we don't need to worry about
25 reference counting. We just store the string, and then remember it in a
26 hash so it can be looked up again. */
28 typedef unsigned short int sc_buflen_t;
30 struct strcache {
31 struct strcache *next; /* The next block of strings. Must be first! */
32 sc_buflen_t end; /* Offset to the beginning of free space. */
33 sc_buflen_t bytesfree; /* Free space left in this buffer. */
34 sc_buflen_t count; /* # of strings in this buffer (for stats). */
35 char buffer[1]; /* The buffer comes after this. */
38 /* The size (in bytes) of each cache buffer.
39 Try to pick something that will map well into the heap.
40 This must be able to be represented by a short int (<=65535). */
41 #define CACHE_BUFFER_BASE (8192)
42 #define CACHE_BUFFER_ALLOC(_s) ((_s) - (2 * sizeof (size_t)))
43 #define CACHE_BUFFER_OFFSET (offsetof (struct strcache, buffer))
44 #define CACHE_BUFFER_SIZE(_s) (CACHE_BUFFER_ALLOC(_s) - CACHE_BUFFER_OFFSET)
46 static sc_buflen_t bufsize = CACHE_BUFFER_SIZE (CACHE_BUFFER_BASE);
47 static struct strcache *strcache = NULL;
48 static struct strcache *fullcache = NULL;
50 static unsigned long total_buffers = 0;
51 static unsigned long total_strings = 0;
52 static unsigned long total_size = 0;
54 /* Add a new buffer to the cache. Add it at the front to reduce search time.
55 This can also increase the overhead, since it's less likely that older
56 buffers will be filled in. However, GNU make has so many smaller strings
57 that this doesn't seem to be much of an issue in practice.
59 static struct strcache *
60 new_cache()
62 struct strcache *new;
63 new = xmalloc (bufsize + CACHE_BUFFER_OFFSET);
64 new->end = 0;
65 new->count = 0;
66 new->bytesfree = bufsize;
68 new->next = strcache;
69 strcache = new;
71 ++total_buffers;
72 return new;
75 static const char *
76 add_string (const char *str, unsigned int len)
78 char *res;
79 struct strcache *sp;
80 struct strcache **spp = &strcache;
81 /* We need space for the nul char. */
82 unsigned int sz = len + 1;
84 /* If the string we want is too large to fit into a single buffer, then
85 no existing cache is large enough. Change the maximum size. */
86 if (sz > bufsize)
87 bufsize = CACHE_BUFFER_SIZE ((((sz + 1) / CACHE_BUFFER_BASE) + 1)
88 * CACHE_BUFFER_BASE);
89 else
90 /* Find the first cache with enough free space. */
91 for (; *spp != NULL; spp = &(*spp)->next)
92 if ((*spp)->bytesfree > sz)
93 break;
95 /* If nothing is big enough, make a new cache. */
96 sp = *spp;
97 if (sp == NULL)
99 sp = new_cache ();
100 spp = &sp;
103 /* Add the string to this cache. */
104 res = &sp->buffer[sp->end];
105 memmove (res, str, len);
106 res[len] = '\0';
107 sp->end += sz;
108 sp->bytesfree -= sz;
109 ++sp->count;
111 /* If the amount free in this cache is less than the average string size,
112 consider it full and move it to the full list. */
113 ++total_strings;
114 total_size += sz;
116 if (sp->bytesfree < (total_size / total_strings) + 1)
118 *spp = (*spp)->next;
119 sp->next = fullcache;
120 fullcache = sp;
123 return res;
127 /* Hash table of strings in the cache. */
129 static unsigned long
130 str_hash_1 (const void *key)
132 return_ISTRING_HASH_1 ((const char *) key);
135 static unsigned long
136 str_hash_2 (const void *key)
138 return_ISTRING_HASH_2 ((const char *) key);
141 static int
142 str_hash_cmp (const void *x, const void *y)
144 return_ISTRING_COMPARE ((const char *) x, (const char *) y);
147 static struct hash_table strings;
148 static unsigned long total_adds = 0;
150 static const char *
151 add_hash (const char *str, int len)
153 /* Look up the string in the hash. If it's there, return it. */
154 char *const *slot = (char *const *) hash_find_slot (&strings, str);
155 const char *key = *slot;
157 /* Count the total number of add operations we performed. */
158 ++total_adds;
160 if (!HASH_VACANT (key))
161 return key;
163 /* Not there yet so add it to a buffer, then into the hash table. */
164 key = add_string (str, len);
165 hash_insert_at (&strings, key, slot);
166 return key;
169 /* Returns true if the string is in the cache; false if not. */
171 strcache_iscached (const char *str)
173 struct strcache *sp;
175 for (sp = strcache; sp != 0; sp = sp->next)
176 if (str >= sp->buffer && str < sp->buffer + sp->end)
177 return 1;
178 for (sp = fullcache; sp != 0; sp = sp->next)
179 if (str >= sp->buffer && str < sp->buffer + sp->end)
180 return 1;
182 return 0;
185 /* If the string is already in the cache, return a pointer to the cached
186 version. If not, add it then return a pointer to the cached version.
187 Note we do NOT take control of the string passed in. */
188 const char *
189 strcache_add (const char *str)
191 return add_hash (str, strlen (str));
194 const char *
195 strcache_add_len (const char *str, unsigned int len)
197 /* If we're not given a nul-terminated string we have to create one, because
198 the hashing functions expect it. */
199 if (str[len] != '\0')
201 char *key = alloca (len + 1);
202 memcpy (key, str, len);
203 key[len] = '\0';
204 str = key;
207 return add_hash (str, len);
211 strcache_setbufsize(unsigned int size)
213 if (size > bufsize)
214 bufsize = size;
215 return bufsize;
218 void
219 strcache_init (void)
221 hash_init (&strings, 8000, str_hash_1, str_hash_2, str_hash_cmp);
225 /* Generate some stats output. */
227 void
228 strcache_print_stats (const char *prefix)
230 const struct strcache *sp;
231 unsigned long numbuffs = 0, fullbuffs = 0;
232 unsigned long totfree = 0, maxfree = 0, minfree = bufsize;
234 if (! strcache)
236 printf(_("\n%s No strcache buffers\n"), prefix);
237 return;
240 /* Count the first buffer separately since it's not full. */
241 for (sp = strcache->next; sp != NULL; sp = sp->next)
243 sc_buflen_t bf = sp->bytesfree;
245 totfree += bf;
246 maxfree = (bf > maxfree ? bf : maxfree);
247 minfree = (bf < minfree ? bf : minfree);
249 ++numbuffs;
251 for (sp = fullcache; sp != NULL; sp = sp->next)
253 sc_buflen_t bf = sp->bytesfree;
255 totfree += bf;
256 maxfree = (bf > maxfree ? bf : maxfree);
257 minfree = (bf < minfree ? bf : minfree);
259 ++numbuffs;
260 ++fullbuffs;
263 /* Make sure we didn't lose any buffers. */
264 assert (total_buffers == numbuffs + 1);
266 printf (_("\n%s strcache buffers: %lu (%lu) / strings = %lu / storage = %lu B / avg = %lu B\n"),
267 prefix, numbuffs + 1, fullbuffs, total_strings, total_size,
268 (total_size / total_strings));
270 printf (_("%s current buf: size = %hu B / used = %hu B / count = %hu / avg = %hu B\n"),
271 prefix, bufsize, strcache->end, strcache->count,
272 (strcache->end / strcache->count));
274 if (numbuffs)
276 unsigned long sz = total_size - bufsize;
277 unsigned long cnt = total_strings - strcache->count;
278 sc_buflen_t avgfree = totfree / numbuffs;
280 printf (_("%s other used: total = %lu B / count = %lu / avg = %lu B\n"),
281 prefix, sz, cnt, sz / cnt);
283 printf (_("%s other free: total = %lu B / max = %lu B / min = %lu B / avg = %hu B\n"),
284 prefix, totfree, maxfree, minfree, avgfree);
287 printf (_("\n%s strcache performance: lookups = %lu / hit rate = %lu%%\n"),
288 prefix, total_adds, (long unsigned)(100.0 * (total_adds - total_strings) / total_adds));
289 fputs (_("# hash-table stats:\n# "), stdout);
290 hash_print_stats (&strings, stdout);