VirtualBox

source: kBuild/trunk/src/kmk/strcache.c@ 2657

Last change on this file since 2657 was 2591, checked in by bird, 13 years ago

kmk: Merged in changes from GNU make 3.82. Previous GNU make base version was gnumake-2008-10-28-CVS.

  • Property svn:eol-style set to native
File size: 7.7 KB
Line 
1/* Constant string caching for GNU Make.
2Copyright (C) 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
3This file is part of GNU Make.
4
5GNU Make is free software; you can redistribute it and/or modify it under the
6terms of the GNU General Public License as published by the Free Software
7Foundation; either version 3 of the License, or (at your option) any later
8version.
9
10GNU Make is distributed in the hope that it will be useful, but WITHOUT ANY
11WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
12A PARTICULAR PURPOSE. See the GNU General Public License for more details.
13
14You should have received a copy of the GNU General Public License along with
15this program. If not, see <http://www.gnu.org/licenses/>. */
16
17#include "make.h"
18#ifndef CONFIG_WITH_STRCACHE2
19
20#include <assert.h>
21
22#include "hash.h"
23
24/* The size (in bytes) of each cache buffer.
25 Try to pick something that will map well into the heap. */
26#define CACHE_BUFFER_SIZE (8192 - 16)
27
28
29/* A string cached here will never be freed, so we don't need to worry about
30 reference counting. We just store the string, and then remember it in a
31 hash so it can be looked up again. */
32
33struct strcache {
34 struct strcache *next; /* The next block of strings. */
35 char *end; /* Pointer to the beginning of the free space. */
36 int count; /* # of strings in this buffer (for stats). */
37 int bytesfree; /* The amount of the buffer that is free. */
38 char buffer[1]; /* The buffer comes after this. */
39};
40
41static int bufsize = CACHE_BUFFER_SIZE;
42static struct strcache *strcache = NULL;
43
44/* Add a new buffer to the cache. Add it at the front to reduce search time.
45 This can also increase the overhead, since it's less likely that older
46 buffers will be filled in. However, GNU make has so many smaller strings
47 that this doesn't seem to be much of an issue in practice.
48 */
49static struct strcache *
50new_cache()
51{
52 struct strcache *new;
53 new = xmalloc (sizeof (*new) + bufsize);
54 new->end = new->buffer;
55 new->count = 0;
56 new->bytesfree = bufsize;
57
58 new->next = strcache;
59 strcache = new;
60
61 return new;
62}
63
64static const char *
65add_string(const char *str, int len)
66{
67 struct strcache *best = NULL;
68 struct strcache *sp;
69 const char *res;
70
71 /* If the string we want is too large to fit into a single buffer, then
72 we're screwed; nothing will ever fit! Change the maximum size of the
73 cache to be big enough. */
74 if (len > bufsize)
75 bufsize = len * 2;
76
77 /* First, find a cache with enough free space. We always look through all
78 the blocks and choose the one with the best fit (the one that leaves the
79 least amount of space free). */
80 for (sp = strcache; sp != NULL; sp = sp->next)
81 if (sp->bytesfree > len && (!best || best->bytesfree > sp->bytesfree))
82 best = sp;
83
84 /* If nothing is big enough, make a new cache. */
85 if (!best)
86 best = new_cache();
87
88 assert (best->bytesfree > len);
89
90 /* Add the string to the best cache. */
91 res = best->end;
92 memcpy (best->end, str, len);
93 best->end += len;
94 *(best->end++) = '\0';
95 best->bytesfree -= len + 1;
96 ++best->count;
97
98 return res;
99}
100
101
102/* Hash table of strings in the cache. */
103
104static unsigned long
105str_hash_1 (const void *key)
106{
107 return_ISTRING_HASH_1 ((const char *) key);
108}
109
110static unsigned long
111str_hash_2 (const void *key)
112{
113 return_ISTRING_HASH_2 ((const char *) key);
114}
115
116static int
117str_hash_cmp (const void *x, const void *y)
118{
119 return_ISTRING_COMPARE ((const char *) x, (const char *) y);
120}
121
122static struct hash_table strings;
123static unsigned long total_adds = 0;
124
125static const char *
126add_hash (const char *str, int len)
127{
128 /* Look up the string in the hash. If it's there, return it. */
129 char *const *slot = (char *const *) hash_find_slot (&strings, str);
130 const char *key = *slot;
131
132 /* Count the total number of adds we performed. */
133 ++total_adds;
134
135 if (!HASH_VACANT (key))
136 return key;
137
138 /* Not there yet so add it to a buffer, then into the hash table. */
139 key = add_string (str, len);
140 hash_insert_at (&strings, key, slot);
141 return key;
142}
143
144/* Returns true if the string is in the cache; false if not. */
145int
146strcache_iscached (const char *str)
147{
148 struct strcache *sp;
149
150 for (sp = strcache; sp != 0; sp = sp->next)
151 if (str >= sp->buffer && str < sp->end)
152 return 1;
153
154 return 0;
155}
156
157/* If the string is already in the cache, return a pointer to the cached
158 version. If not, add it then return a pointer to the cached version.
159 Note we do NOT take control of the string passed in. */
160const char *
161strcache_add (const char *str)
162{
163 return add_hash (str, strlen (str));
164}
165
166const char *
167strcache_add_len (const char *str, int len)
168{
169 /* If we're not given a nul-terminated string we have to create one, because
170 the hashing functions expect it. */
171 if (str[len] != '\0')
172 {
173 char *key = alloca (len + 1);
174 memcpy (key, str, len);
175 key[len] = '\0';
176 str = key;
177 }
178
179 return add_hash (str, len);
180}
181
182int
183strcache_setbufsize(int size)
184{
185 if (size > bufsize)
186 bufsize = size;
187 return bufsize;
188}
189
190void
191strcache_init (void)
192{
193 hash_init (&strings, 8000, str_hash_1, str_hash_2, str_hash_cmp);
194}
195
196
197/* Generate some stats output. */
198
199void
200strcache_print_stats (const char *prefix)
201{
202 int numbuffs = 0, numstrs = 0;
203 int totsize = 0, avgsize, maxsize = 0, minsize = bufsize;
204 int totfree = 0, avgfree, maxfree = 0, minfree = bufsize;
205 int lastused = 0, lastfree = 0;
206
207 if (strcache)
208 {
209 const struct strcache *sp;
210
211 /* Count the first buffer separately since it's not full. */
212 lastused = strcache->end - strcache->buffer;
213 lastfree = strcache->bytesfree;
214
215 for (sp = strcache->next; sp != NULL; sp = sp->next)
216 {
217 int bf = sp->bytesfree;
218 int sz = sp->end - sp->buffer;
219
220 ++numbuffs;
221 numstrs += sp->count;
222
223 totsize += sz;
224 maxsize = (sz > maxsize ? sz : maxsize);
225 minsize = (sz < minsize ? sz : minsize);
226
227 totfree += bf;
228 maxfree = (bf > maxfree ? bf : maxfree);
229 minfree = (bf < minfree ? bf : minfree);
230 }
231 }
232
233 avgsize = numbuffs ? (int)(totsize / numbuffs) : 0;
234 avgfree = numbuffs ? (int)(totfree / numbuffs) : 0;
235
236 printf (_("\n%s # of strings in strcache: %d / lookups = %lu / hits = %lu\n"),
237 prefix, numstrs, total_adds, (total_adds - numstrs));
238 printf (_("%s # of strcache buffers: %d (* %d B/buffer = %d B)\n"),
239 prefix, (numbuffs + 1), bufsize, ((numbuffs + 1) * bufsize));
240 printf (_("%s strcache used: total = %d (%d) / max = %d / min = %d / avg = %d\n"),
241 prefix, totsize, lastused, maxsize, minsize, avgsize);
242 printf (_("%s strcache free: total = %d (%d) / max = %d / min = %d / avg = %d\n"),
243 prefix, totfree, lastfree, maxfree, minfree, avgfree);
244
245 fputs (_("\n# strcache hash-table stats:\n# "), stdout);
246 hash_print_stats (&strings, stdout);
247}
248
249#else /* CONFIG_WITH_STRCACHE2 */
250
251#include "strcache2.h"
252
253const char *suffixes_strcached;
254
255/* The file string cache. */
256struct strcache2 file_strcache;
257
258void strcache_init (void)
259{
260 strcache2_init(&file_strcache,
261 "file", /* name */
262 65536, /* hash size */
263 0, /* default segment size*/
264#ifdef HAVE_CASE_INSENSITIVE_FS
265 1, /* case insensitive */
266#else
267 0, /* case insensitive */
268#endif
269 0); /* thread safe */
270
271 /* .SUFFIXES is referenced in several loops, keep the added pointer in a
272 global var so these can be optimized. */
273
274 suffixes_strcached = strcache_add_len (".SUFFIXES", sizeof (".SUFFIXES")-1);
275}
276
277void
278strcache_print_stats (const char *prefix)
279{
280 strcache2_print_stats (&file_strcache, prefix);
281}
282
283#endif /* CONFIG_WITH_STRCACHE2 */
284
Note: See TracBrowser for help on using the repository browser.

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette