- Fix broken handling of order-only prereqs in secondary expansion
[make.git] / strcache.c
blob92f27c9a86098ede4322dee118b052637c83a1b8
1 /* Constant string caching for GNU Make.
2 Copyright (C) 2006, 2007 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 <assert.h>
21 #include "hash.h"
23 /* The size (in bytes) of each cache buffer.
24 Try to pick something that will map well into the heap. */
25 #define CACHE_BUFFER_SIZE (8192 - 16)
28 /* A string cached here will never be freed, so we don't need to worry about
29 reference counting. We just store the string, and then remember it in a
30 hash so it can be looked up again. */
32 struct strcache {
33 struct strcache *next; /* The next block of strings. */
34 char *end; /* Pointer to the beginning of the free space. */
35 int count; /* # of strings in this buffer (for stats). */
36 int bytesfree; /* The amount of the buffer that is free. */
37 char buffer[1]; /* The buffer comes after this. */
40 static int bufsize = CACHE_BUFFER_SIZE;
41 static struct strcache *strcache = NULL;
43 /* Add a new buffer to the cache. Add it at the front to reduce search time.
44 This can also increase the overhead, since it's less likely that older
45 buffers will be filled in. However, GNU make has so many smaller strings
46 that this doesn't seem to be much of an issue in practice.
48 static struct strcache *
49 new_cache()
51 struct strcache *new;
52 new = xmalloc (sizeof (*new) + bufsize);
53 new->end = new->buffer;
54 new->count = 0;
55 new->bytesfree = bufsize;
57 new->next = strcache;
58 strcache = new;
60 return new;
63 static const char *
64 add_string(const char *str, int len)
66 struct strcache *best = NULL;
67 struct strcache *sp;
68 const char *res;
70 /* If the string we want is too large to fit into a single buffer, then
71 we're screwed; nothing will ever fit! Change the maximum size of the
72 cache to be big enough. */
73 if (len > bufsize)
74 bufsize = len * 2;
76 /* First, find a cache with enough free space. We always look through all
77 the blocks and choose the one with the best fit (the one that leaves the
78 least amount of space free). */
79 for (sp = strcache; sp != NULL; sp = sp->next)
80 if (sp->bytesfree > len && (!best || best->bytesfree > sp->bytesfree))
81 best = sp;
83 /* If nothing is big enough, make a new cache. */
84 if (!best)
85 best = new_cache();
87 assert (best->bytesfree > len);
89 /* Add the string to the best cache. */
90 res = best->end;
91 memcpy (best->end, str, len);
92 best->end += len;
93 *(best->end++) = '\0';
94 best->bytesfree -= len + 1;
95 ++best->count;
97 return res;
101 /* Hash table of strings in the cache. */
103 static unsigned long
104 str_hash_1 (const void *key)
106 return_ISTRING_HASH_1 ((const char *) key);
109 static unsigned long
110 str_hash_2 (const void *key)
112 return_ISTRING_HASH_2 ((const char *) key);
115 static int
116 str_hash_cmp (const void *x, const void *y)
118 return_ISTRING_COMPARE ((const char *) x, (const char *) y);
121 static struct hash_table strings;
122 static unsigned long total_adds = 0;
124 static const char *
125 add_hash (const char *str, int len)
127 /* Look up the string in the hash. If it's there, return it. */
128 char *const *slot = (char *const *) hash_find_slot (&strings, str);
129 const char *key = *slot;
131 /* Count the total number of adds we performed. */
132 ++total_adds;
134 if (!HASH_VACANT (key))
135 return key;
137 /* Not there yet so add it to a buffer, then into the hash table. */
138 key = add_string (str, len);
139 hash_insert_at (&strings, key, slot);
140 return key;
143 /* Returns true if the string is in the cache; false if not. */
145 strcache_iscached (const char *str)
147 struct strcache *sp;
149 for (sp = strcache; sp != 0; sp = sp->next)
150 if (str >= sp->buffer && str < sp->end)
151 return 1;
153 return 0;
156 /* If the string is already in the cache, return a pointer to the cached
157 version. If not, add it then return a pointer to the cached version.
158 Note we do NOT take control of the string passed in. */
159 const char *
160 strcache_add (const char *str)
162 return add_hash (str, strlen (str));
165 const char *
166 strcache_add_len (const char *str, int len)
168 /* If we're not given a nul-terminated string we have to create one, because
169 the hashing functions expect it. */
170 if (str[len] != '\0')
172 char *key = alloca (len + 1);
173 memcpy (key, str, len);
174 key[len] = '\0';
175 str = key;
178 return add_hash (str, len);
182 strcache_setbufsize(int size)
184 if (size > bufsize)
185 bufsize = size;
186 return bufsize;
189 void
190 strcache_init (void)
192 hash_init (&strings, 8000, str_hash_1, str_hash_2, str_hash_cmp);
196 /* Generate some stats output. */
198 void
199 strcache_print_stats (const char *prefix)
201 int numbuffs = 0, numstrs = 0;
202 int totsize = 0, avgsize, maxsize = 0, minsize = bufsize;
203 int totfree = 0, avgfree, maxfree = 0, minfree = bufsize;
204 int lastused = 0, lastfree = 0;
206 if (strcache)
208 const struct strcache *sp;
210 /* Count the first buffer separately since it's not full. */
211 lastused = strcache->end - strcache->buffer;
212 lastfree = strcache->bytesfree;
214 for (sp = strcache->next; sp != NULL; sp = sp->next)
216 int bf = sp->bytesfree;
217 int sz = sp->end - sp->buffer;
219 ++numbuffs;
220 numstrs += sp->count;
222 totsize += sz;
223 maxsize = (sz > maxsize ? sz : maxsize);
224 minsize = (sz < minsize ? sz : minsize);
226 totfree += bf;
227 maxfree = (bf > maxfree ? bf : maxfree);
228 minfree = (bf < minfree ? bf : minfree);
232 avgsize = numbuffs ? (int)(totsize / numbuffs) : 0;
233 avgfree = numbuffs ? (int)(totfree / numbuffs) : 0;
235 printf (_("\n%s # of strings in strcache: %d / lookups = %lu / hits = %lu\n"),
236 prefix, numstrs, total_adds, (total_adds - numstrs));
237 printf (_("%s # of strcache buffers: %d (* %d B/buffer = %d B)\n"),
238 prefix, (numbuffs + 1), bufsize, ((numbuffs + 1) * bufsize));
239 printf (_("%s strcache used: total = %d (%d) / max = %d / min = %d / avg = %d\n"),
240 prefix, totsize, lastused, maxsize, minsize, avgsize);
241 printf (_("%s strcache free: total = %d (%d) / max = %d / min = %d / avg = %d\n"),
242 prefix, totfree, lastfree, maxfree, minfree, avgfree);
244 fputs (_("\n# strcache hash-table stats:\n# "), stdout);
245 hash_print_stats (&strings, stdout);