1 | /* $Id: strcache2.c 1879 2008-10-17 01:53:05Z bird $ */
|
---|
2 | /** @file
|
---|
3 | * strcache2 - New string cache.
|
---|
4 | */
|
---|
5 |
|
---|
6 | /*
|
---|
7 | * Copyright (c) 2008 knut st. osmundsen <[email protected]>
|
---|
8 | *
|
---|
9 | * This file is part of kBuild.
|
---|
10 | *
|
---|
11 | * kBuild is free software; you can redistribute it and/or modify
|
---|
12 | * it under the terms of the GNU General Public License as published by
|
---|
13 | * the Free Software Foundation; either version 2 of the License, or
|
---|
14 | * (at your option) any later version.
|
---|
15 | *
|
---|
16 | * kBuild is distributed in the hope that it will be useful,
|
---|
17 | * but WITHOUT ANY WARRANTY; without even the implied warranty of
|
---|
18 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
---|
19 | * GNU General Public License for more details.
|
---|
20 | *
|
---|
21 | * You should have received a copy of the GNU General Public License
|
---|
22 | * along with kBuild; if not, write to the Free Software
|
---|
23 | * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
|
---|
24 | *
|
---|
25 | */
|
---|
26 |
|
---|
27 |
|
---|
28 | /*******************************************************************************
|
---|
29 | * Header Files *
|
---|
30 | *******************************************************************************/
|
---|
31 | #include "make.h"
|
---|
32 | #include "strcache2.h"
|
---|
33 |
|
---|
34 | #include <assert.h>
|
---|
35 |
|
---|
36 | #include "debug.h"
|
---|
37 |
|
---|
38 | #ifdef WINDOWS32
|
---|
39 | # include <io.h>
|
---|
40 | # include <process.h>
|
---|
41 | # include <Windows.h>
|
---|
42 | # define PARSE_IN_WORKER
|
---|
43 | #endif
|
---|
44 |
|
---|
45 | #ifdef __OS2__
|
---|
46 | # include <sys/fmutex.h>
|
---|
47 | #endif
|
---|
48 |
|
---|
49 | #ifdef HAVE_PTHREAD
|
---|
50 | # include <pthread.h>
|
---|
51 | #endif
|
---|
52 |
|
---|
53 |
|
---|
54 | /*******************************************************************************
|
---|
55 | * Defined Constants And Macros *
|
---|
56 | *******************************************************************************/
|
---|
57 | /* The default size of a memory segment (1MB). */
|
---|
58 | #define STRCACHE2_SEG_SIZE (1024U*1024U)
|
---|
59 | /* The default hash table shift (hash size give as a power of two). */
|
---|
60 | #define STRCACHE2_HASH_SHIFT 16
|
---|
61 |
|
---|
62 |
|
---|
63 |
|
---|
64 |
|
---|
65 | static struct strcache2_seg *
|
---|
66 | strcache2_new_seg (struct strcache2 *cache, unsigned int minlen)
|
---|
67 | {
|
---|
68 | struct strcache2_seg *seg;
|
---|
69 | size_t size;
|
---|
70 |
|
---|
71 | size = cache->def_seg_size;
|
---|
72 | if (size < (size_t)minlen + sizeof (struct strcache2_seg))
|
---|
73 | {
|
---|
74 | size = (size_t)minlen * 2;
|
---|
75 | size = (size + 0xfff) & ~(size_t)0xfff;
|
---|
76 | }
|
---|
77 |
|
---|
78 | seg = xmalloc (size);
|
---|
79 | seg->cursor = seg->start = (char *)(seg + 1);
|
---|
80 | seg->size = seg->avail = size - sizeof (struct strcache2_seg);
|
---|
81 | assert (seg->size > minlen);
|
---|
82 |
|
---|
83 | seg->next = cache->seg_head;
|
---|
84 | cache->seg_head = seg;
|
---|
85 |
|
---|
86 | return seg;
|
---|
87 | }
|
---|
88 |
|
---|
89 | MY_INLINE unsigned int
|
---|
90 | strcache2_case_sensitive_hash_1 (const char *str, unsigned int len)
|
---|
91 | {
|
---|
92 | unsigned int hash = 0;
|
---|
93 | if (MY_PREDICT_TRUE(len >= 2))
|
---|
94 | {
|
---|
95 | unsigned int ch0 = *str++;
|
---|
96 | hash = 0;
|
---|
97 | len--;
|
---|
98 | while (len >= 2)
|
---|
99 | {
|
---|
100 | unsigned int ch1 = *str++;
|
---|
101 | hash += ch0 << (ch1 & 0xf);
|
---|
102 |
|
---|
103 | ch0 = *str++;
|
---|
104 | hash += ch1 << (ch0 & 0xf);
|
---|
105 |
|
---|
106 | len -= 2;
|
---|
107 | }
|
---|
108 | if (len == 1)
|
---|
109 | {
|
---|
110 | unsigned ch1 = *str;
|
---|
111 | hash += ch0 << (ch1 & 0xf);
|
---|
112 |
|
---|
113 | hash += ch1;
|
---|
114 | }
|
---|
115 | else
|
---|
116 | hash += ch0;
|
---|
117 | }
|
---|
118 | else if (len)
|
---|
119 | {
|
---|
120 | hash = *str;
|
---|
121 | hash += hash << (hash & 0xf);
|
---|
122 | }
|
---|
123 | else
|
---|
124 | hash = 0;
|
---|
125 | return hash;
|
---|
126 | }
|
---|
127 |
|
---|
128 | MY_INLINE unsigned int
|
---|
129 | strcache2_case_sensitive_hash_2 (const char *str, unsigned int len)
|
---|
130 | {
|
---|
131 | unsigned int hash = 0;
|
---|
132 | if (MY_PREDICT_TRUE(len >= 2))
|
---|
133 | {
|
---|
134 | unsigned int ch0 = *str++;
|
---|
135 | hash = 0;
|
---|
136 | len--;
|
---|
137 | while (len >= 2)
|
---|
138 | {
|
---|
139 | unsigned int ch1 = *str++;
|
---|
140 | hash += ch0 << (ch1 & 0x7);
|
---|
141 |
|
---|
142 | ch0 = *str++;
|
---|
143 | hash += ch1 << (ch0 & 0x7);
|
---|
144 |
|
---|
145 | len -= 2;
|
---|
146 | }
|
---|
147 | if (len == 1)
|
---|
148 | {
|
---|
149 | unsigned ch1 = *str;
|
---|
150 | hash += ch0 << (ch1 & 0x7);
|
---|
151 |
|
---|
152 | hash += ch1;
|
---|
153 | }
|
---|
154 | else
|
---|
155 | hash += ch0;
|
---|
156 | }
|
---|
157 | else if (len)
|
---|
158 | {
|
---|
159 | hash = *str;
|
---|
160 | hash += hash << (hash & 0x7);
|
---|
161 | }
|
---|
162 | else
|
---|
163 | hash = 1;
|
---|
164 | hash |= 1;
|
---|
165 | return hash;
|
---|
166 | }
|
---|
167 |
|
---|
168 | MY_INLINE unsigned int
|
---|
169 | strcache2_case_insensitive_hash_1 (const char *str, unsigned int len)
|
---|
170 | {
|
---|
171 | unsigned int hash = 0;
|
---|
172 | if (MY_PREDICT_TRUE(len >= 2))
|
---|
173 | {
|
---|
174 | unsigned int ch0 = *str++;
|
---|
175 | ch0 = tolower (ch0);
|
---|
176 | hash = 0;
|
---|
177 | len--;
|
---|
178 | while (len >= 2)
|
---|
179 | {
|
---|
180 | unsigned int ch1 = *str++;
|
---|
181 | ch1 = tolower (ch1);
|
---|
182 | hash += ch0 << (ch1 & 0xf);
|
---|
183 |
|
---|
184 | ch0 = *str++;
|
---|
185 | ch0 = tolower (ch0);
|
---|
186 | hash += ch1 << (ch0 & 0xf);
|
---|
187 |
|
---|
188 | len -= 2;
|
---|
189 | }
|
---|
190 | if (len == 1)
|
---|
191 | {
|
---|
192 | unsigned ch1 = *str;
|
---|
193 | ch1 = tolower (ch1);
|
---|
194 | hash += ch0 << (ch1 & 0xf);
|
---|
195 |
|
---|
196 | hash += ch1;
|
---|
197 | }
|
---|
198 | else
|
---|
199 | hash += ch0;
|
---|
200 | }
|
---|
201 | else if (len)
|
---|
202 | {
|
---|
203 | hash = *str;
|
---|
204 | hash += hash << (hash & 0xf);
|
---|
205 | }
|
---|
206 | else
|
---|
207 | hash = 0;
|
---|
208 | return hash;
|
---|
209 | }
|
---|
210 |
|
---|
211 | MY_INLINE unsigned int
|
---|
212 | strcache2_case_insensitive_hash_2 (const char *str, unsigned int len)
|
---|
213 | {
|
---|
214 | unsigned int hash = 0;
|
---|
215 | if (MY_PREDICT_TRUE(len >= 2))
|
---|
216 | {
|
---|
217 | unsigned int ch0 = *str++;
|
---|
218 | ch0 = tolower (ch0);
|
---|
219 | hash = 0;
|
---|
220 | len--;
|
---|
221 | while (len >= 2)
|
---|
222 | {
|
---|
223 | unsigned int ch1 = *str++;
|
---|
224 | ch1 = tolower (ch1);
|
---|
225 | hash += ch0 << (ch1 & 0x7);
|
---|
226 |
|
---|
227 | ch0 = *str++;
|
---|
228 | ch0 = tolower (ch0);
|
---|
229 | hash += ch1 << (ch0 & 0x7);
|
---|
230 |
|
---|
231 | len -= 2;
|
---|
232 | }
|
---|
233 | if (len == 1)
|
---|
234 | {
|
---|
235 | unsigned ch1 = *str;
|
---|
236 | ch1 = tolower (ch1);
|
---|
237 | hash += ch0 << (ch1 & 0x7);
|
---|
238 |
|
---|
239 | hash += ch1;
|
---|
240 | }
|
---|
241 | else
|
---|
242 | hash += ch0;
|
---|
243 | }
|
---|
244 | else if (len)
|
---|
245 | {
|
---|
246 | hash = *str;
|
---|
247 | hash += hash << (hash & 0x7);
|
---|
248 | }
|
---|
249 | else
|
---|
250 | hash = 1;
|
---|
251 | hash |= 1;
|
---|
252 | return hash;
|
---|
253 | }
|
---|
254 |
|
---|
255 | MY_INLINE int
|
---|
256 | strcache2_is_equal (struct strcache2 *cache, struct strcache2_entry const *entry,
|
---|
257 | const char *str, unsigned int length, unsigned int hash1)
|
---|
258 | {
|
---|
259 | /* the simple stuff first. */
|
---|
260 | if ( entry == NULL
|
---|
261 | || entry->hash1 != hash1
|
---|
262 | || entry->length != length)
|
---|
263 | return 0;
|
---|
264 |
|
---|
265 | return !cache->case_insensitive
|
---|
266 | ? memcmp (entry + 1, str, length) == 0
|
---|
267 | #if defined(_MSC_VER) || defined(__OS2__)
|
---|
268 | : _memicmp (entry + 1, str, length) == 0
|
---|
269 | #else
|
---|
270 | : strncasecmp ((const char *)(entry + 1), str, length) == 0
|
---|
271 | #endif
|
---|
272 | ;
|
---|
273 | }
|
---|
274 |
|
---|
275 | static void
|
---|
276 | strcache2_rehash (struct strcache2 *cache)
|
---|
277 | {
|
---|
278 | unsigned int src = cache->hash_size;
|
---|
279 | struct strcache2_entry **src_tab = cache->hash_tab;
|
---|
280 | struct strcache2_entry **dst_tab;
|
---|
281 | unsigned int hash_mask;
|
---|
282 |
|
---|
283 | /* Allocate a new hash table twice the size of the current. */
|
---|
284 | cache->hash_size <<= 1;
|
---|
285 | cache->hash_mask <<= 1;
|
---|
286 | cache->hash_mask |= 1;
|
---|
287 | cache->rehash_count <<= 1;
|
---|
288 | cache->hash_tab = dst_tab = (struct strcache2_entry **)
|
---|
289 | xmalloc (cache->hash_size * sizeof (struct strcache2_entry *));
|
---|
290 | memset (dst_tab, '\0', cache->hash_size * sizeof (struct strcache2_entry *));
|
---|
291 |
|
---|
292 | /* Copy the entries from the old to the new hash table. */
|
---|
293 | hash_mask = cache->hash_mask;
|
---|
294 | while (src-- > 0)
|
---|
295 | {
|
---|
296 | struct strcache2_entry *entry = src_tab[src];
|
---|
297 | if (entry)
|
---|
298 | {
|
---|
299 | unsigned int dst = entry->hash1 & hash_mask;
|
---|
300 | if (dst_tab[dst])
|
---|
301 | {
|
---|
302 | unsigned int hash2 = entry->hash2;
|
---|
303 | if (!hash2)
|
---|
304 | entry->hash2 = hash2 = cache->case_insensitive
|
---|
305 | ? strcache2_case_insensitive_hash_2 ((const char *)(entry + 1), entry->length)
|
---|
306 | : strcache2_case_sensitive_hash_2 ((const char *)(entry + 1), entry->length);
|
---|
307 | dst += hash2;
|
---|
308 | dst &= hash_mask;
|
---|
309 | while (dst_tab[dst])
|
---|
310 | {
|
---|
311 | dst += hash2;
|
---|
312 | dst &= hash_mask;
|
---|
313 | }
|
---|
314 | }
|
---|
315 |
|
---|
316 | dst_tab[dst] = entry;
|
---|
317 | }
|
---|
318 | }
|
---|
319 |
|
---|
320 | /* That's it, just free the old table and we're done. */
|
---|
321 | free (src_tab);
|
---|
322 | }
|
---|
323 |
|
---|
324 | /* Internal worker that enters a new string into the cache. */
|
---|
325 | static const char *
|
---|
326 | strcache2_enter_string (struct strcache2 *cache, unsigned int idx,
|
---|
327 | const char *str, unsigned int length,
|
---|
328 | unsigned int hash1, unsigned hash2)
|
---|
329 | {
|
---|
330 | struct strcache2_entry *entry;
|
---|
331 | struct strcache2_seg *seg;
|
---|
332 | unsigned int size;
|
---|
333 | char *str_copy;
|
---|
334 |
|
---|
335 | /* Allocate space for the string. */
|
---|
336 |
|
---|
337 | size = length + 1 + sizeof (struct strcache2_entry);
|
---|
338 | size = (size + sizeof (void *) - 1) & ~(sizeof (void *) - 1U);
|
---|
339 |
|
---|
340 | seg = cache->seg_head;
|
---|
341 | if (MY_PREDICT_FALSE(seg->avail < size))
|
---|
342 | {
|
---|
343 | do
|
---|
344 | seg = seg->next;
|
---|
345 | while (seg && seg->avail < size);
|
---|
346 | if (!seg)
|
---|
347 | seg = strcache2_new_seg (cache, size);
|
---|
348 | }
|
---|
349 |
|
---|
350 | entry = (struct strcache2_entry *) seg->cursor;
|
---|
351 | seg->cursor += size;
|
---|
352 | seg->avail -= size;
|
---|
353 |
|
---|
354 | /* Setup the entry, copy the string and insert it into the hash table. */
|
---|
355 |
|
---|
356 | entry->user = NULL;
|
---|
357 | entry->length = length;
|
---|
358 | entry->hash1 = hash1;
|
---|
359 | entry->hash2 = hash2;
|
---|
360 | str_copy = (char *) memcpy (entry + 1, str, length);
|
---|
361 | str_copy[length] = '\0';
|
---|
362 |
|
---|
363 | cache->hash_tab[idx] = entry;
|
---|
364 | cache->count++;
|
---|
365 | if (cache->count >= cache->rehash_count)
|
---|
366 | strcache2_rehash (cache);
|
---|
367 |
|
---|
368 | return str_copy;
|
---|
369 | }
|
---|
370 |
|
---|
371 | /* The public add/lookup string interface. */
|
---|
372 | const char *
|
---|
373 | strcache2_add (struct strcache2 *cache, const char *str, unsigned int length)
|
---|
374 | {
|
---|
375 | struct strcache2_entry const *entry;
|
---|
376 | unsigned int hash2;
|
---|
377 | unsigned int hash1 = cache->case_insensitive
|
---|
378 | ? strcache2_case_insensitive_hash_1 (str, length)
|
---|
379 | : strcache2_case_sensitive_hash_1 (str, length);
|
---|
380 | unsigned int idx;
|
---|
381 |
|
---|
382 | cache->lookup_count++;
|
---|
383 |
|
---|
384 | /* Lookup the entry in the hash table, hoping for an
|
---|
385 | early match. */
|
---|
386 | idx = hash1 & cache->hash_mask;
|
---|
387 | entry = cache->hash_tab[idx];
|
---|
388 | if (strcache2_is_equal (cache, entry, str, length, hash1))
|
---|
389 | return (const char *)(entry + 1);
|
---|
390 | if (!entry)
|
---|
391 | hash2 = 0;
|
---|
392 | else
|
---|
393 | {
|
---|
394 | cache->collision_1st_count++;
|
---|
395 |
|
---|
396 | hash2 = cache->case_insensitive
|
---|
397 | ? strcache2_case_insensitive_hash_2 (str, length)
|
---|
398 | : strcache2_case_sensitive_hash_2 (str, length);
|
---|
399 | idx += hash2;
|
---|
400 | idx &= cache->hash_mask;
|
---|
401 | entry = cache->hash_tab[idx];
|
---|
402 | if (strcache2_is_equal (cache, entry, str, length, hash1))
|
---|
403 | return (const char *)(entry + 1);
|
---|
404 |
|
---|
405 | if (entry)
|
---|
406 | {
|
---|
407 | cache->collision_2nd_count++;
|
---|
408 | do
|
---|
409 | {
|
---|
410 | idx += hash2;
|
---|
411 | idx &= cache->hash_mask;
|
---|
412 | entry = cache->hash_tab[idx];
|
---|
413 | cache->collision_3rd_count++;
|
---|
414 | if (strcache2_is_equal (cache, entry, str, length, hash1))
|
---|
415 | return (const char *)(entry + 1);
|
---|
416 | }
|
---|
417 | while (entry);
|
---|
418 | }
|
---|
419 | }
|
---|
420 |
|
---|
421 | /* Not found, add it at IDX. */
|
---|
422 | return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
|
---|
423 | }
|
---|
424 |
|
---|
425 | /* The public add/lookup string interface for prehashed strings.
|
---|
426 | Use strcache2_hash_str to calculate the hash of a string. */
|
---|
427 | const char *
|
---|
428 | strcache2_add_hashed (struct strcache2 *cache, const char *str, unsigned int length,
|
---|
429 | unsigned int hash1, unsigned int hash2)
|
---|
430 | {
|
---|
431 | struct strcache2_entry const *entry;
|
---|
432 | unsigned int idx;
|
---|
433 | #ifndef NDEBUG
|
---|
434 | unsigned correct_hash;
|
---|
435 |
|
---|
436 | correct_hash = cache->case_insensitive
|
---|
437 | ? strcache2_case_insensitive_hash_1 (str, length)
|
---|
438 | : strcache2_case_sensitive_hash_1 (str, length);
|
---|
439 | MY_ASSERT_MSG (hash1 == correct_hash, ("%#x != %#x\n", hash1, correct_hash));
|
---|
440 | if (hash2)
|
---|
441 | {
|
---|
442 | correct_hash = cache->case_insensitive
|
---|
443 | ? strcache2_case_insensitive_hash_2 (str, length)
|
---|
444 | : strcache2_case_sensitive_hash_2 (str, length);
|
---|
445 | MY_ASSERT_MSG (hash2 == correct_hash, ("%#x != %#x\n", hash2, correct_hash));
|
---|
446 | }
|
---|
447 | #endif /* NDEBUG */
|
---|
448 |
|
---|
449 | cache->lookup_count++;
|
---|
450 |
|
---|
451 | /* Lookup the entry in the hash table, hoping for an
|
---|
452 | early match. */
|
---|
453 | idx = hash1 & cache->hash_mask;
|
---|
454 | entry = cache->hash_tab[idx];
|
---|
455 | if (strcache2_is_equal (cache, entry, str, length, hash1))
|
---|
456 | return (const char *)(entry + 1);
|
---|
457 | if (entry)
|
---|
458 | {
|
---|
459 | cache->collision_1st_count++;
|
---|
460 |
|
---|
461 | if (!hash2)
|
---|
462 | hash2 = cache->case_insensitive
|
---|
463 | ? strcache2_case_insensitive_hash_2 (str, length)
|
---|
464 | : strcache2_case_sensitive_hash_2 (str, length);
|
---|
465 | idx += hash2;
|
---|
466 | idx &= cache->hash_mask;
|
---|
467 | entry = cache->hash_tab[idx];
|
---|
468 | if (strcache2_is_equal (cache, entry, str, length, hash1))
|
---|
469 | return (const char *)(entry + 1);
|
---|
470 |
|
---|
471 | if (entry)
|
---|
472 | {
|
---|
473 | cache->collision_2nd_count++;
|
---|
474 | do
|
---|
475 | {
|
---|
476 | idx += hash2;
|
---|
477 | idx &= cache->hash_mask;
|
---|
478 | entry = cache->hash_tab[idx];
|
---|
479 | cache->collision_3rd_count++;
|
---|
480 | if (strcache2_is_equal (cache, entry, str, length, hash1))
|
---|
481 | return (const char *)(entry + 1);
|
---|
482 | }
|
---|
483 | while (entry);
|
---|
484 | }
|
---|
485 | }
|
---|
486 |
|
---|
487 | /* Not found, add it at IDX. */
|
---|
488 | return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
|
---|
489 | }
|
---|
490 |
|
---|
491 | /* Is the given string cached? returns 1 if it is, 0 if it isn't. */
|
---|
492 | int
|
---|
493 | strcache2_is_cached (struct strcache2 *cache, const char *str)
|
---|
494 | {
|
---|
495 | /* Check mandatory alignment first. */
|
---|
496 | if (!((size_t)str & (sizeof (void *) - 1)))
|
---|
497 | {
|
---|
498 | /* Check the segment list and consider the question answered if the
|
---|
499 | string is within one of them. (Could check it more thoroughly...) */
|
---|
500 | struct strcache2_seg const *seg;
|
---|
501 | for (seg = cache->seg_head; seg; seg = seg->next)
|
---|
502 | if ((size_t)(str - seg->start) < seg->size)
|
---|
503 | return 1;
|
---|
504 | }
|
---|
505 |
|
---|
506 | return 0;
|
---|
507 | }
|
---|
508 |
|
---|
509 |
|
---|
510 | /* Verify the integrity of the specified string, returning 0 if OK. */
|
---|
511 | int
|
---|
512 | strcache2_verify_entry (struct strcache2 *cache, const char *str)
|
---|
513 | {
|
---|
514 | struct strcache2_entry const *entry;
|
---|
515 | unsigned hash;
|
---|
516 | const char *end;
|
---|
517 |
|
---|
518 | if ((size_t)str & (sizeof (void *) - 1))
|
---|
519 | {
|
---|
520 | fprintf (stderr,
|
---|
521 | "strcache2[%s]: missaligned string %p\nstring: %s\n",
|
---|
522 | cache->name, (void *)str, str);
|
---|
523 | return -1;
|
---|
524 | }
|
---|
525 |
|
---|
526 | entry = (struct strcache2_entry const *)str - 1;
|
---|
527 | end = memchr (str, '\0', entry->length);
|
---|
528 | if ((size_t)(end - str) == entry->length)
|
---|
529 | {
|
---|
530 | fprintf (stderr,
|
---|
531 | "strcache2[%s]: corrupt entry %p, length: %lu, expected %u;\nstring: %s\n",
|
---|
532 | cache->name, (void *)entry, (unsigned long)(end - str), entry->length, str);
|
---|
533 | return -1;
|
---|
534 | }
|
---|
535 |
|
---|
536 | hash = cache->case_insensitive
|
---|
537 | ? strcache2_case_insensitive_hash_1 (str, entry->length)
|
---|
538 | : strcache2_case_sensitive_hash_1 (str, entry->length);
|
---|
539 | if (hash != entry->hash1)
|
---|
540 | {
|
---|
541 | fprintf (stderr,
|
---|
542 | "strcache2[%s]: corrupt entry %p, hash#1: %x, expected %x;\nstring: %s\n",
|
---|
543 | cache->name, (void *)entry, hash, entry->hash1, str);
|
---|
544 | return -1;
|
---|
545 | }
|
---|
546 |
|
---|
547 | if (entry->hash2)
|
---|
548 | {
|
---|
549 | hash = cache->case_insensitive
|
---|
550 | ? strcache2_case_insensitive_hash_2 (str, entry->length)
|
---|
551 | : strcache2_case_sensitive_hash_2 (str, entry->length);
|
---|
552 | if (hash != entry->hash2)
|
---|
553 | {
|
---|
554 | fprintf (stderr,
|
---|
555 | "strcache2[%s]: corrupt entry %p, hash#2: %x, expected %x;\nstring: %s\n",
|
---|
556 | cache->name, (void *)entry, hash, entry->hash2, str);
|
---|
557 | return -1;
|
---|
558 | }
|
---|
559 | }
|
---|
560 |
|
---|
561 | return 0;
|
---|
562 | }
|
---|
563 |
|
---|
564 | /* Fallback for calculating and returning the 2nd hash. */
|
---|
565 | unsigned int
|
---|
566 | strcache2_get_hash2_fallback (struct strcache2 *cache, const char *str)
|
---|
567 | {
|
---|
568 | struct strcache2_entry *entry = (struct strcache2_entry *) str - 1;
|
---|
569 | unsigned hash2 = cache->case_insensitive
|
---|
570 | ? strcache2_case_insensitive_hash_2 (str, entry->length)
|
---|
571 | : strcache2_case_sensitive_hash_2 (str, entry->length);
|
---|
572 | entry->hash2 = hash2;
|
---|
573 | return hash2;
|
---|
574 | }
|
---|
575 |
|
---|
576 | /* Calculates the case sensitive hash values of the string.
|
---|
577 | The first hash is returned, the other is put at HASH2P. */
|
---|
578 | unsigned int strcache2_hash_str (const char *str, unsigned int length, unsigned int *hash2p)
|
---|
579 | {
|
---|
580 | *hash2p = strcache2_case_sensitive_hash_2 (str, length);
|
---|
581 | return strcache2_case_sensitive_hash_1 (str, length);
|
---|
582 | }
|
---|
583 |
|
---|
584 | /* Calculates the case insensitive hash values of the string.
|
---|
585 | The first hash is returned, the other is put at HASH2P. */
|
---|
586 | unsigned int strcache2_hash_istr (const char *str, unsigned int length, unsigned int *hash2p)
|
---|
587 | {
|
---|
588 | *hash2p = strcache2_case_insensitive_hash_2 (str, length);
|
---|
589 | return strcache2_case_insensitive_hash_1 (str, length);
|
---|
590 | }
|
---|
591 |
|
---|
592 |
|
---|
593 | /* List of initialized string caches. */
|
---|
594 | static struct strcache2 *strcache_head;
|
---|
595 |
|
---|
596 | /* Initalizes a new cache. */
|
---|
597 | void
|
---|
598 | strcache2_init (struct strcache2 *cache, const char *name, unsigned int size,
|
---|
599 | unsigned int def_seg_size, int case_insensitive, int thread_safe)
|
---|
600 | {
|
---|
601 | unsigned hash_shift;
|
---|
602 | assert (!thread_safe);
|
---|
603 |
|
---|
604 | /* calc the size as a power of two */
|
---|
605 | if (!size)
|
---|
606 | hash_shift = STRCACHE2_HASH_SHIFT;
|
---|
607 | else
|
---|
608 | {
|
---|
609 | assert (size <= (~0U / 2 + 1));
|
---|
610 | for (hash_shift = 8; (1U << hash_shift) < size; hash_shift++)
|
---|
611 | /* nothing */;
|
---|
612 | }
|
---|
613 |
|
---|
614 | /* adjust the default segment size */
|
---|
615 | if (!def_seg_size)
|
---|
616 | def_seg_size = STRCACHE2_SEG_SIZE;
|
---|
617 | else if (def_seg_size < sizeof (struct strcache2_seg) * 10)
|
---|
618 | def_seg_size = sizeof (struct strcache2_seg) * 10;
|
---|
619 | else if ((def_seg_size & 0xfff) < 0xf00)
|
---|
620 | def_seg_size = ((def_seg_size + 0xfff) & ~0xfffU);
|
---|
621 |
|
---|
622 |
|
---|
623 | /* init the structure. */
|
---|
624 | cache->case_insensitive = case_insensitive;
|
---|
625 | cache->hash_mask = (1U << hash_shift) - 1U;
|
---|
626 | cache->count = 0;
|
---|
627 | cache->lookup_count = 0;
|
---|
628 | cache->collision_1st_count = 0;
|
---|
629 | cache->collision_2nd_count = 0;
|
---|
630 | cache->collision_3rd_count = 0;
|
---|
631 | cache->rehash_count = (1U << hash_shift) / 4 * 3; /* rehash at 75% */
|
---|
632 | cache->init_size = 1U << hash_shift;
|
---|
633 | cache->hash_size = 1U << hash_shift;
|
---|
634 | cache->def_seg_size = def_seg_size;
|
---|
635 | cache->lock = NULL;
|
---|
636 | cache->name = name;
|
---|
637 |
|
---|
638 | /* allocate the hash table and first segment. */
|
---|
639 | cache->hash_tab = (struct strcache2_entry **)
|
---|
640 | xmalloc (cache->init_size * sizeof (struct strcache2_entry *));
|
---|
641 | memset (cache->hash_tab, '\0', cache->init_size * sizeof (struct strcache2_entry *));
|
---|
642 | strcache2_new_seg (cache, 0);
|
---|
643 |
|
---|
644 | /* link it */
|
---|
645 | cache->next = strcache_head;
|
---|
646 | strcache_head = cache;
|
---|
647 | }
|
---|
648 |
|
---|
649 |
|
---|
650 | /* Terminates a string cache, freeing all memory and other
|
---|
651 | associated resources. */
|
---|
652 | void
|
---|
653 | strcache2_term (struct strcache2 *cache)
|
---|
654 | {
|
---|
655 | /* unlink it */
|
---|
656 | if (strcache_head == cache)
|
---|
657 | strcache_head = cache->next;
|
---|
658 | else
|
---|
659 | {
|
---|
660 | struct strcache2 *prev = strcache_head;
|
---|
661 | while (prev->next != cache)
|
---|
662 | prev = prev->next;
|
---|
663 | assert (prev);
|
---|
664 | prev->next = cache->next;
|
---|
665 | }
|
---|
666 |
|
---|
667 | /* free the memory segments */
|
---|
668 | do
|
---|
669 | {
|
---|
670 | void *free_it = cache->seg_head;
|
---|
671 | cache->seg_head = cache->seg_head->next;
|
---|
672 | free (free_it);
|
---|
673 | }
|
---|
674 | while (cache->seg_head);
|
---|
675 |
|
---|
676 | /* free the hash and clear the structure. */
|
---|
677 | free (cache->hash_tab);
|
---|
678 | memset (cache, '\0', sizeof (struct strcache2));
|
---|
679 | }
|
---|
680 |
|
---|
681 | /* Print statistics a string cache. */
|
---|
682 | void
|
---|
683 | strcache2_print_stats (struct strcache2 *cache, const char *prefix)
|
---|
684 | {
|
---|
685 | unsigned int seg_count = 0;
|
---|
686 | unsigned long seg_total_bytes = 0;
|
---|
687 | unsigned long seg_avg_bytes;
|
---|
688 | unsigned long seg_avail_bytes = 0;
|
---|
689 | unsigned long seg_max_bytes = 0;
|
---|
690 | struct strcache2_seg *seg;
|
---|
691 | unsigned long str_total_len = 0;
|
---|
692 | unsigned int str_avg_len;
|
---|
693 | unsigned int str_min_len = ~0U;
|
---|
694 | unsigned int str_max_len = 0;
|
---|
695 | unsigned int idx;
|
---|
696 | unsigned int rehashes;
|
---|
697 |
|
---|
698 | printf (_("\n%s strcache2: %s\n"), prefix, cache->name);
|
---|
699 |
|
---|
700 | /* Segment statistics. */
|
---|
701 | for (seg = cache->seg_head; seg; seg = seg->next)
|
---|
702 | {
|
---|
703 | seg_count++;
|
---|
704 | seg_total_bytes += seg->size;
|
---|
705 | seg_avail_bytes += seg->avail;
|
---|
706 | if (seg->size > seg_max_bytes)
|
---|
707 | seg_max_bytes = seg->size;
|
---|
708 | }
|
---|
709 | seg_avg_bytes = seg_total_bytes / seg_count;
|
---|
710 | printf (_("%s %u segments: total = %lu / max = %lu / avg = %lu / def = %u avail = %lu\n"),
|
---|
711 | prefix, seg_count, seg_total_bytes, seg_max_bytes, seg_avg_bytes,
|
---|
712 | cache->def_seg_size, seg_avail_bytes);
|
---|
713 |
|
---|
714 | /* String statistics. */
|
---|
715 | idx = cache->hash_size;
|
---|
716 | while (idx-- > 0)
|
---|
717 | {
|
---|
718 | struct strcache2_entry const *entry = cache->hash_tab[idx];
|
---|
719 | if (entry)
|
---|
720 | {
|
---|
721 | unsigned int length = entry->length;
|
---|
722 | str_total_len += length;
|
---|
723 | if (length > str_max_len)
|
---|
724 | str_max_len = length;
|
---|
725 | if (length < str_min_len)
|
---|
726 | str_min_len = length;
|
---|
727 | }
|
---|
728 | }
|
---|
729 | str_avg_len = cache->count ? str_total_len / cache->count : 0;
|
---|
730 | printf (_("%s %u strings: total len = %lu / max = %u / avg = %u / min = %u\n"),
|
---|
731 | prefix, cache->count, str_total_len, str_max_len, str_avg_len, str_min_len);
|
---|
732 |
|
---|
733 | /* Hash statistics. */
|
---|
734 | idx = cache->init_size;
|
---|
735 | rehashes = 0;
|
---|
736 | while (idx < cache->hash_size)
|
---|
737 | {
|
---|
738 | idx *= 2;
|
---|
739 | rehashes++;
|
---|
740 | }
|
---|
741 |
|
---|
742 | printf (_("%s hash size = %u mask = %#x rehashed %u times lookups = %lu\n"),
|
---|
743 | prefix, cache->hash_size, cache->hash_mask, rehashes, cache->lookup_count);
|
---|
744 | printf (_("%s hash collisions 1st = %lu (%u%%) 2nd = %lu (%u%%) 3rd = %lu (%u%%)\n"),
|
---|
745 | prefix,
|
---|
746 | cache->collision_1st_count, (unsigned int)((float)cache->collision_1st_count * 100 / cache->lookup_count),
|
---|
747 | cache->collision_2nd_count, (unsigned int)((float)cache->collision_2nd_count * 100 / cache->lookup_count),
|
---|
748 | cache->collision_3rd_count, (unsigned int)((float)cache->collision_3rd_count * 100 / cache->lookup_count));
|
---|
749 | }
|
---|
750 |
|
---|
751 | /* Print statistics for all string caches. */
|
---|
752 | void
|
---|
753 | strcache2_print_stats_all (const char *prefix)
|
---|
754 | {
|
---|
755 | struct strcache2 *cur;
|
---|
756 | for (cur = strcache_head; cur; cur = cur->next)
|
---|
757 | strcache2_print_stats (cur, prefix);
|
---|
758 | }
|
---|
759 |
|
---|