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 *
new_cache()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 *
add_string(const char * str,int len)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
str_hash_1(const void * key)98 str_hash_1 (const void *key)
99 {
100 return_ISTRING_HASH_1 ((const char *) key);
101 }
102
103 static unsigned long
str_hash_2(const void * key)104 str_hash_2 (const void *key)
105 {
106 return_ISTRING_HASH_2 ((const char *) key);
107 }
108
109 static int
str_hash_cmp(const void * x,const void * y)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 *
add_hash(const char * str,int len)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
strcache_iscached(const char * str)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 *
strcache_add(const char * str)150 strcache_add (const char *str)
151 {
152 return add_hash (str, strlen (str));
153 }
154
155 const char *
strcache_add_len(const char * str,int len)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
strcache_setbufsize(int size)166 strcache_setbufsize(int size)
167 {
168 if (size > bufsize)
169 bufsize = size;
170 return bufsize;
171 }
172
173 void
strcache_init(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
strcache_print_stats(const char * prefix)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