VirtualBox

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

Last change on this file since 1166 was 967, checked in by bird, 18 years ago

fixed prop

  • Property svn:eol-style set to native
File size: 6.9 KB
Line 
1/* Constant string caching for GNU Make.
2Copyright (C) 2006 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 2, or (at your option) any later version.
8
9GNU Make is distributed in the hope that it will be useful, but WITHOUT ANY
10WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
11A PARTICULAR PURPOSE. See the GNU General Public License for more details.
12
13You should have received a copy of the GNU General Public License along with
14GNU Make; see the file COPYING. If not, write to the Free Software
15Foundation, 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 Try to pick something that will map well into the heap. */
25#define CACHE_BUFFER_SIZE (8192 - 16)
26
27
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. */
31
32struct 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. */
38};
39
40static int bufsize = CACHE_BUFFER_SIZE;
41static struct strcache *strcache = NULL;
42
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.
47 */
48static struct strcache *
49new_cache()
50{
51 struct strcache *new;
52 new = xmalloc (sizeof (*new) + bufsize);
53 new->end = new->buffer;
54 new->count = 0;
55 new->bytesfree = bufsize;
56
57 new->next = strcache;
58 strcache = new;
59
60 return new;
61}
62
63static const char *
64add_string(const char *str, int len)
65{
66 struct strcache *best = NULL;
67 struct strcache *sp;
68 const char *res;
69
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;
75
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;
82
83 /* If nothing is big enough, make a new cache. */
84 if (!best)
85 best = new_cache();
86
87 assert (best->bytesfree > len);
88
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;
96
97 return res;
98}
99
100
101/* Hash table of strings in the cache. */
102
103static unsigned long
104str_hash_1 (const void *key)
105{
106 return_ISTRING_HASH_1 ((const char *) key);
107}
108
109static unsigned long
110str_hash_2 (const void *key)
111{
112 return_ISTRING_HASH_2 ((const char *) key);
113}
114
115static int
116str_hash_cmp (const void *x, const void *y)
117{
118 return_ISTRING_COMPARE ((const char *) x, (const char *) y);
119}
120
121static struct hash_table strings;
122static unsigned long total_adds = 0;
123
124static const char *
125add_hash (const char *str, int len)
126{
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;
130
131 /* Count the total number of adds we performed. */
132 ++total_adds;
133
134 if (!HASH_VACANT (key))
135 return key;
136
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;
141}
142
143/* Returns true if the string is in the cache; false if not. */
144int
145strcache_iscached (const char *str)
146{
147 struct strcache *sp;
148
149 for (sp = strcache; sp != 0; sp = sp->next)
150 if (str >= sp->buffer && str < sp->end)
151 return 1;
152
153 return 0;
154}
155
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. */
159const char *
160strcache_add (const char *str)
161{
162 return add_hash (str, strlen (str));
163}
164
165const char *
166strcache_add_len (const char *str, int len)
167{
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')
171 {
172 char *key = alloca (len + 1);
173 memcpy (key, str, len);
174 key[len] = '\0';
175 str = key;
176 }
177
178 return add_hash (str, len);
179}
180
181int
182strcache_setbufsize(int size)
183{
184 if (size > bufsize)
185 bufsize = size;
186 return bufsize;
187}
188
189void
190strcache_init (void)
191{
192 hash_init (&strings, 8000, str_hash_1, str_hash_2, str_hash_cmp);
193}
194
195
196/* Generate some stats output. */
197
198void
199strcache_print_stats (const char *prefix)
200{
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;
205
206 if (strcache)
207 {
208 const struct strcache *sp;
209
210 /* Count the first buffer separately since it's not full. */
211 lastused = strcache->end - strcache->buffer;
212 lastfree = strcache->bytesfree;
213
214 for (sp = strcache->next; sp != NULL; sp = sp->next)
215 {
216 int bf = sp->bytesfree;
217 int sz = sp->end - sp->buffer;
218
219 ++numbuffs;
220 numstrs += sp->count;
221
222 totsize += sz;
223 maxsize = (sz > maxsize ? sz : maxsize);
224 minsize = (sz < minsize ? sz : minsize);
225
226 totfree += bf;
227 maxfree = (bf > maxfree ? bf : maxfree);
228 minfree = (bf < minfree ? bf : minfree);
229 }
230 }
231
232 avgsize = numbuffs ? (int)(totsize / numbuffs) : 0;
233 avgfree = numbuffs ? (int)(totfree / numbuffs) : 0;
234
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);
243
244 fputs (_("\n# strcache hash-table stats:\n# "), stdout);
245 hash_print_stats (&strings, stdout);
246}
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