source: trunk/src/kmk/strcache2.c@ 1909

Last change on this file since 1909 was 1909, checked in by bird, 17 years ago

strcache2: Implemented collision resolution by chaining instead of open addressing. This is faster than the open addressing approach we're using.
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 40.7 KB
Line 
1/* $Id: strcache2.c 1909 2008-10-22 18:49:48Z bird $ */
2/** @file
3 * strcache2 - New string cache.
4 */
5
6/*
7 * Copyright (c) 2008 knut st. osmundsen <bird-src-spam@anduin.net>
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/** Does the modding / masking of a hash number into an index. */
62#ifdef STRCACHE2_USE_MASK
63# define STRCACHE2_MOD_IT(cache, hash) ((hash) & (cache)->hash_mask)
64#else
65# define STRCACHE2_MOD_IT(cache, hash) ((hash) % (cache)->hash_div)
66#endif
67
68
69/*******************************************************************************
70* Global Variables *
71*******************************************************************************/
72/* List of initialized string caches. */
73static struct strcache2 *strcache_head;
74
75
76
77/** Finds the closest primary number for power of two value (or something else
78 * useful if not support). */
79MY_INLINE unsigned int strcache2_find_prime(unsigned int shift)
80{
81 switch (shift)
82 {
83 case 5: return 31;
84 case 6: return 61;
85 case 7: return 127;
86 case 8: return 251;
87 case 9: return 509;
88 case 10: return 1021;
89 case 11: return 2039;
90 case 12: return 4093;
91 case 13: return 8191;
92 case 14: return 16381;
93 case 15: return 32749;
94 case 16: return 65521;
95 case 17: return 131063;
96 case 18: return 262139;
97 case 19: return 524269;
98 case 20: return 1048573;
99 case 21: return 2097143;
100 case 22: return 4194301;
101 case 23: return 8388593;
102
103 default:
104 assert (0);
105 return (1 << shift) - 1;
106 }
107}
108
109static struct strcache2_seg *
110strcache2_new_seg (struct strcache2 *cache, unsigned int minlen)
111{
112 struct strcache2_seg *seg;
113 size_t size;
114 size_t off;
115
116 size = cache->def_seg_size;
117 if (size < (size_t)minlen + sizeof (struct strcache2_seg) + STRCACHE2_ENTRY_ALIGNMENT)
118 {
119 size = (size_t)minlen * 2;
120 size = (size + 0xfff) & ~(size_t)0xfff;
121 }
122
123 seg = xmalloc (size);
124 seg->start = (char *)(seg + 1);
125 seg->size = size - sizeof (struct strcache2_seg);
126 off = (size_t)seg->start & (STRCACHE2_ENTRY_ALIGNMENT - 1);
127 if (off)
128 {
129 seg->start += off;
130 seg->size -= off;
131 }
132 assert (seg->size > minlen);
133 seg->cursor = seg->start;
134 seg->avail = seg->size;
135
136 seg->next = cache->seg_head;
137 cache->seg_head = seg;
138
139 return seg;
140}
141
142MY_INLINE unsigned int
143strcache2_case_sensitive_hash_1 (const char *str, unsigned int len)
144{
145#if 1
146 /* Note! This implementation is 18% faster than return_STRING_N_HASH_1
147 when running the two 100 times over typical kBuild strings that
148 end up here (did a fprintf here and built kBuild).
149 Compiler was 32-bit gcc 4.0.1, darwin, with -O2. */
150
151 unsigned int hash = 0;
152 if (MY_PREDICT_TRUE(len >= 2))
153 {
154 unsigned int ch0 = *str++;
155 hash = 0;
156 len--;
157 while (len >= 2)
158 {
159 unsigned int ch1 = *str++;
160 hash += ch0 << (ch1 & 0xf);
161
162 ch0 = *str++;
163 hash += ch1 << (ch0 & 0xf);
164
165 len -= 2;
166 }
167 if (len == 1)
168 {
169 unsigned ch1 = *str;
170 hash += ch0 << (ch1 & 0xf);
171
172 hash += ch1;
173 }
174 else
175 hash += ch0;
176 }
177 else if (len)
178 {
179 hash = *str;
180 hash += hash << (hash & 0xf);
181 }
182 else
183 hash = 0;
184 return hash;
185#else
186# if 1
187 /* This is SDBM. This specific form and loop unroll was benchmarked to
188 be 28% faster than return_STRING_N_HASH_1. (Now the weird thing is
189 that putting the (ch) first in the assignment made it noticably slower.)
190
191 However, it is noticably slower in practice, most likely because of more
192 collisions. Hrmpf.
193 */
194# define UPDATE_HASH(ch) hash = (hash << 6) + (hash << 16) - hash + (ch)
195 unsigned int hash = 0;
196# else
197 /* This is DJB2. This specific form/unroll was benchmarked to be 27%
198 fast than return_STRING_N_HASH_1.
199
200 Ditto. 2x Hrmpf */
201# define UPDATE_HASH(ch) hash = (hash << 5) + hash + (ch)
202 unsigned int hash = 5381;
203# endif
204 while (len >= 4)
205 {
206 UPDATE_HASH (str[0]);
207 UPDATE_HASH (str[1]);
208 UPDATE_HASH (str[2]);
209 UPDATE_HASH (str[3]);
210 str += 4;
211 len -= 4;
212 }
213 switch (len)
214 {
215 default:
216 case 0:
217 return hash;
218 case 1:
219 UPDATE_HASH (str[0]);
220 return hash;
221 case 2:
222 UPDATE_HASH (str[0]);
223 UPDATE_HASH (str[1]);
224 return hash;
225 case 3:
226 UPDATE_HASH (str[0]);
227 UPDATE_HASH (str[1]);
228 UPDATE_HASH (str[2]);
229 return hash;
230 }
231#endif
232}
233
234MY_INLINE unsigned int
235strcache2_case_sensitive_hash_2 (const char *str, unsigned int len)
236{
237#ifndef STRCACHE2_USE_CHAINING
238 unsigned int hash = 0;
239 if (MY_PREDICT_TRUE(len >= 2))
240 {
241 unsigned int ch0 = *str++;
242 hash = 0;
243 len--;
244 while (len >= 2)
245 {
246 unsigned int ch1 = *str++;
247 hash += ch0 << (ch1 & 0x7);
248
249 ch0 = *str++;
250 hash += ch1 << (ch0 & 0x7);
251
252 len -= 2;
253 }
254 if (len == 1)
255 {
256 unsigned ch1 = *str;
257 hash += ch0 << (ch1 & 0x7);
258
259 hash += ch1;
260 }
261 else
262 hash += ch0;
263 }
264 else if (len)
265 {
266 hash = *str;
267 hash += hash << (hash & 0x7);
268 }
269 else
270 hash = 1;
271 hash |= 1;
272 return hash;
273#else /* STRCACHE2_USE_CHAINING */
274 return 1;
275#endif /* STRCACHE2_USE_CHAINING */
276}
277
278MY_INLINE unsigned int
279strcache2_case_insensitive_hash_1 (const char *str, unsigned int len)
280{
281 unsigned int hash = 0;
282 if (MY_PREDICT_TRUE(len >= 2))
283 {
284 unsigned int ch0 = *str++;
285 ch0 = tolower (ch0);
286 hash = 0;
287 len--;
288 while (len >= 2)
289 {
290 unsigned int ch1 = *str++;
291 ch1 = tolower (ch1);
292 hash += ch0 << (ch1 & 0xf);
293
294 ch0 = *str++;
295 ch0 = tolower (ch0);
296 hash += ch1 << (ch0 & 0xf);
297
298 len -= 2;
299 }
300 if (len == 1)
301 {
302 unsigned ch1 = *str;
303 ch1 = tolower (ch1);
304 hash += ch0 << (ch1 & 0xf);
305
306 hash += ch1;
307 }
308 else
309 hash += ch0;
310 }
311 else if (len)
312 {
313 hash = *str;
314 hash += hash << (hash & 0xf);
315 }
316 else
317 hash = 0;
318 return hash;
319}
320
321MY_INLINE unsigned int
322strcache2_case_insensitive_hash_2 (const char *str, unsigned int len)
323{
324#ifndef STRCACHE2_USE_CHAINING
325 unsigned int hash = 0;
326 if (MY_PREDICT_TRUE(len >= 2))
327 {
328 unsigned int ch0 = *str++;
329 ch0 = tolower (ch0);
330 hash = 0;
331 len--;
332 while (len >= 2)
333 {
334 unsigned int ch1 = *str++;
335 ch1 = tolower (ch1);
336 hash += ch0 << (ch1 & 0x7);
337
338 ch0 = *str++;
339 ch0 = tolower (ch0);
340 hash += ch1 << (ch0 & 0x7);
341
342 len -= 2;
343 }
344 if (len == 1)
345 {
346 unsigned ch1 = *str;
347 ch1 = tolower (ch1);
348 hash += ch0 << (ch1 & 0x7);
349
350 hash += ch1;
351 }
352 else
353 hash += ch0;
354 }
355 else if (len)
356 {
357 hash = *str;
358 hash += hash << (hash & 0x7);
359 }
360 else
361 hash = 1;
362 hash |= 1;
363 return hash;
364#else /* STRCACHE2_USE_CHAINING */
365 return 1;
366#endif /* STRCACHE2_USE_CHAINING */
367}
368
369#ifdef _MSC_VER
370 typedef unsigned int int32_t;
371#else
372# include <stdint.h>
373#endif
374
375MY_INLINE int
376strcache2_memcmp_inline_short (const char *xs, const char *ys, unsigned int length)
377{
378 if (length <= 8)
379 {
380 /* short string compare - ~50% of the kBuild calls. */
381 assert ( !((size_t)ys & 3) );
382 if (!((size_t)xs & 3))
383 {
384 /* aligned */
385 int result;
386 switch (length)
387 {
388 default: /* memcmp for longer strings */
389 return memcmp (xs, ys, length);
390 case 8:
391 result = *(int32_t*)(xs + 4) - *(int32_t*)(ys + 4);
392 result |= *(int32_t*)xs - *(int32_t*)ys;
393 return result;
394 case 7:
395 result = xs[6] - ys[6];
396 result |= xs[5] - ys[5];
397 result |= xs[4] - ys[4];
398 result |= *(int32_t*)xs - *(int32_t*)ys;
399 return result;
400 case 6:
401 result = xs[5] - ys[5];
402 result |= xs[4] - ys[4];
403 result |= *(int32_t*)xs - *(int32_t*)ys;
404 return result;
405 case 5:
406 result = xs[4] - ys[4];
407 result |= *(int32_t*)xs - *(int32_t*)ys;
408 return result;
409 case 4:
410 return *(int32_t*)xs - *(int32_t*)ys;
411 case 3:
412 result = xs[2] - ys[2];
413 result |= xs[1] - ys[1];
414 result |= xs[0] - ys[0];
415 return result;
416 case 2:
417 result = xs[1] - ys[1];
418 result |= xs[0] - ys[0];
419 return result;
420 case 1:
421 return *xs - *ys;
422 case 0:
423 return 0;
424 }
425 }
426 else
427 {
428 /* unaligned */
429 int result = 0;
430 switch (length)
431 {
432 case 8: result |= xs[7] - ys[7];
433 case 7: result |= xs[6] - ys[6];
434 case 6: result |= xs[5] - ys[5];
435 case 5: result |= xs[4] - ys[4];
436 case 4: result |= xs[3] - ys[3];
437 case 3: result |= xs[2] - ys[2];
438 case 2: result |= xs[1] - ys[1];
439 case 1: result |= xs[0] - ys[0];
440 case 0:
441 return result;
442 }
443 }
444 }
445
446 /* memcmp for longer strings */
447 return memcmp (xs, ys, length);
448}
449
450MY_INLINE int
451strcache2_memcmp_inlined (const char *xs, const char *ys, unsigned int length)
452{
453#ifndef ELECTRIC_HEAP
454 assert ( !((size_t)ys & 3) );
455#endif
456 if (!((size_t)xs & 3))
457 {
458 int result;
459 /* aligned */
460 while (length >= 8)
461 {
462 result = *(int32_t*)xs - *(int32_t*)ys;
463 result |= *(int32_t*)(xs + 4) - *(int32_t*)(ys + 4);
464 if (MY_PREDICT_FALSE(result))
465 return result;
466 xs += 8;
467 ys += 8;
468 length -= 8;
469 }
470 switch (length)
471 {
472 case 7:
473 result = *(int32_t*)xs - *(int32_t*)ys;
474 result |= xs[6] - ys[6];
475 result |= xs[5] - ys[5];
476 result |= xs[4] - ys[4];
477 return result;
478 case 6:
479 result = *(int32_t*)xs - *(int32_t*)ys;
480 result |= xs[5] - ys[5];
481 result |= xs[4] - ys[4];
482 return result;
483 case 5:
484 result = *(int32_t*)xs - *(int32_t*)ys;
485 result |= xs[4] - ys[4];
486 return result;
487 case 4:
488 return *(int32_t*)xs - *(int32_t*)ys;
489 case 3:
490 result = xs[2] - ys[2];
491 result |= xs[1] - ys[1];
492 result |= xs[0] - ys[0];
493 return result;
494 case 2:
495 result = xs[1] - ys[1];
496 result |= xs[0] - ys[0];
497 return result;
498 case 1:
499 return *xs - *ys;
500 default:
501 case 0:
502 return 0;
503 }
504 }
505 else
506 {
507 /* unaligned */
508 int result;
509 while (length >= 8)
510 {
511#if defined(__i386__) || defined(__x86_64__)
512 result = ( ((int32_t)xs[3] << 24)
513 | ((int32_t)xs[2] << 16)
514 | ((int32_t)xs[1] << 8)
515 | xs[0] )
516 - *(int32_t*)ys;
517 result |= ( ((int32_t)xs[7] << 24)
518 | ((int32_t)xs[6] << 16)
519 | ((int32_t)xs[5] << 8)
520 | xs[4] )
521 - *(int32_t*)(ys + 4);
522#else
523 result = xs[3] - ys[3];
524 result |= xs[2] - ys[2];
525 result |= xs[1] - ys[1];
526 result |= xs[0] - ys[0];
527 result |= xs[7] - ys[7];
528 result |= xs[6] - ys[6];
529 result |= xs[5] - ys[5];
530 result |= xs[4] - ys[4];
531#endif
532 if (MY_PREDICT_FALSE(result))
533 return result;
534 xs += 8;
535 ys += 8;
536 length -= 8;
537 }
538 result = 0;
539 switch (length)
540 {
541 case 7: result |= xs[6] - ys[6];
542 case 6: result |= xs[5] - ys[5];
543 case 5: result |= xs[4] - ys[4];
544 case 4: result |= xs[3] - ys[3];
545 case 3: result |= xs[2] - ys[2];
546 case 2: result |= xs[1] - ys[1];
547 case 1: result |= xs[0] - ys[0];
548 return result;
549 default:
550 case 0:
551 return 0;
552 }
553 }
554}
555
556MY_INLINE int
557strcache2_is_equal (struct strcache2 *cache, struct strcache2_entry const *entry,
558 const char *str, unsigned int length, unsigned int hash1)
559{
560 assert (!cache->case_insensitive);
561
562 /* the simple stuff first. */
563 if ( entry == NULL
564 || entry->hash1 != hash1
565 || entry->length != length)
566 return 0;
567
568#if 0
569 return memcmp (str, entry + 1, length) == 0;
570#elif 1
571 return strcache2_memcmp_inlined (str, (const char *)(entry + 1), length) == 0;
572#else
573 return strcache2_memcmp_inline_short (str, (const char *)(entry + 1), length) == 0;
574#endif
575}
576
577MY_INLINE int
578strcache2_is_iequal (struct strcache2 *cache, struct strcache2_entry const *entry,
579 const char *str, unsigned int length, unsigned int hash1)
580{
581 assert (cache->case_insensitive);
582
583 /* the simple stuff first. */
584 if ( entry == NULL
585 || entry->hash1 != hash1
586 || entry->length != length)
587 return 0;
588
589#if defined(_MSC_VER) || defined(__OS2__)
590 return _memicmp (entry + 1, str, length) == 0;
591#else
592 return strncasecmp ((const char *)(entry + 1), str, length) == 0;
593#endif
594}
595
596static void
597strcache2_rehash (struct strcache2 *cache)
598{
599 unsigned int src = cache->hash_size;
600 struct strcache2_entry **src_tab = cache->hash_tab;
601 struct strcache2_entry **dst_tab;
602#ifndef STRCACHE2_USE_MASK
603 unsigned int hash_shift;
604#endif
605
606 /* Allocate a new hash table twice the size of the current. */
607 cache->hash_size <<= 1;
608#ifdef STRCACHE2_USE_MASK
609 cache->hash_mask <<= 1;
610 cache->hash_mask |= 1;
611#else
612 for (hash_shift = 1; (1U << hash_shift) < cache->hash_size; hash_shift++)
613 /* nothing */;
614 cache->hash_div = strcache2_find_prime (hash_shift);
615#endif
616 cache->rehash_count <<= 1;
617 cache->hash_tab = dst_tab = (struct strcache2_entry **)
618 xmalloc (cache->hash_size * sizeof (struct strcache2_entry *));
619 memset (dst_tab, '\0', cache->hash_size * sizeof (struct strcache2_entry *));
620
621 /* Copy the entries from the old to the new hash table. */
622 while (src-- > 0)
623 {
624 struct strcache2_entry *entry = src_tab[src];
625 if (entry)
626 {
627#ifdef STRCACHE2_USE_CHAINING
628assert(!"todo");
629#else
630 unsigned int dst = STRCACHE2_MOD_IT (cache, entry->hash1);
631 if (dst_tab[dst])
632 {
633 unsigned int hash2 = entry->hash2;
634 if (!hash2)
635 entry->hash2 = hash2 = cache->case_insensitive
636 ? strcache2_case_insensitive_hash_2 ((const char *)(entry + 1), entry->length)
637 : strcache2_case_sensitive_hash_2 ((const char *)(entry + 1), entry->length);
638 dst += hash2;
639 dst = STRCACHE2_MOD_IT (cache, dst);
640 while (dst_tab[dst])
641 {
642 dst += hash2;
643 dst = STRCACHE2_MOD_IT (cache, dst);
644 }
645 }
646
647 dst_tab[dst] = entry;
648#endif
649 }
650 }
651
652 /* That's it, just free the old table and we're done. */
653 free (src_tab);
654}
655
656/* Internal worker that enters a new string into the cache. */
657static const char *
658strcache2_enter_string (struct strcache2 *cache, unsigned int idx,
659 const char *str, unsigned int length,
660 unsigned int hash1, unsigned hash2)
661{
662 struct strcache2_entry *entry;
663 struct strcache2_seg *seg;
664 unsigned int size;
665 char *str_copy;
666
667 /* Allocate space for the string. */
668
669 size = length + 1 + sizeof (struct strcache2_entry);
670 size = (size + STRCACHE2_ENTRY_ALIGNMENT - 1) & ~(STRCACHE2_ENTRY_ALIGNMENT - 1U);
671
672 seg = cache->seg_head;
673 if (MY_PREDICT_FALSE(seg->avail < size))
674 {
675 do
676 seg = seg->next;
677 while (seg && seg->avail < size);
678 if (!seg)
679 seg = strcache2_new_seg (cache, size);
680 }
681
682 entry = (struct strcache2_entry *) seg->cursor;
683 assert ((size_t)entry & (STRCACHE2_ENTRY_ALIGNMENT - 1));
684 seg->cursor += size;
685 seg->avail -= size;
686
687 /* Setup the entry, copy the string and insert it into the hash table. */
688
689 entry->user = NULL;
690 entry->length = length;
691 entry->hash1 = hash1;
692#ifndef STRCACHE2_USE_CHAINING
693 entry->hash2 = hash2;
694#endif
695 str_copy = (char *) memcpy (entry + 1, str, length);
696 str_copy[length] = '\0';
697
698#ifndef STRCACHE2_USE_CHAINING
699 cache->hash_tab[idx] = entry;
700#else /* STRCACHE2_USE_CHAINING */
701 if ((entry->next = cache->hash_tab[idx]) == 0)
702 cache->hash_tab[idx] = entry;
703 else
704 {
705 cache->hash_tab[idx] = entry;
706 cache->collision_count++;
707 }
708#endif /* STRCACHE2_USE_CHAINING */
709 cache->count++;
710 if (cache->count >= cache->rehash_count)
711 strcache2_rehash (cache);
712
713 return str_copy;
714}
715
716/* The public add string interface. */
717const char *
718strcache2_add (struct strcache2 *cache, const char *str, unsigned int length)
719{
720 struct strcache2_entry const *entry;
721 unsigned int hash1 = strcache2_case_sensitive_hash_1 (str, length);
722 unsigned int hash2 = 0;
723 unsigned int idx;
724
725 assert (!cache->case_insensitive);
726
727 cache->lookup_count++;
728
729 /* Lookup the entry in the hash table, hoping for an
730 early match. If not found, enter the string at IDX. */
731 idx = STRCACHE2_MOD_IT (cache, hash1);
732 entry = cache->hash_tab[idx];
733 if (!entry)
734 return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
735 if (strcache2_is_equal (cache, entry, str, length, hash1))
736 return (const char *)(entry + 1);
737 cache->collision_1st_count++;
738
739#ifdef STRCACHE2_USE_CHAINING
740 entry = entry->next;
741#else /* !STRCACHE2_USE_CHAINING */
742 hash2 = strcache2_case_sensitive_hash_2 (str, length);
743 idx += hash2;
744 idx = STRCACHE2_MOD_IT (cache, idx);
745 entry = cache->hash_tab[idx];
746#endif /* !STRCACHE2_USE_CHAINING */
747 if (!entry)
748 return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
749 if (strcache2_is_equal (cache, entry, str, length, hash1))
750 return (const char *)(entry + 1);
751 cache->collision_2nd_count++;
752
753 /* (We've established hash2, so we can do a straight loop now.) */
754 for (;;)
755 {
756#ifdef STRCACHE2_USE_CHAINING
757 entry = entry->next;
758#else /* !STRCACHE2_USE_CHAINING */
759 idx += hash2;
760 idx = STRCACHE2_MOD_IT (cache, idx);
761 entry = cache->hash_tab[idx];
762#endif /* !STRCACHE2_USE_CHAINING */
763 if (!entry)
764 return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
765 if (strcache2_is_equal (cache, entry, str, length, hash1))
766 return (const char *)(entry + 1);
767 cache->collision_3rd_count++;
768 }
769 /* not reached */
770}
771
772/* The public add string interface for prehashed strings.
773 Use strcache2_hash_str to calculate the hash of a string. */
774const char *
775strcache2_add_hashed (struct strcache2 *cache, const char *str, unsigned int length,
776 unsigned int hash1, unsigned int hash2)
777{
778 struct strcache2_entry const *entry;
779 unsigned int idx;
780#ifndef NDEBUG
781 unsigned correct_hash;
782
783 assert (!cache->case_insensitive);
784 correct_hash = strcache2_case_sensitive_hash_1 (str, length);
785 MY_ASSERT_MSG (hash1 == correct_hash, ("%#x != %#x\n", hash1, correct_hash));
786 if (hash2)
787 {
788 correct_hash = strcache2_case_sensitive_hash_2 (str, length);
789 MY_ASSERT_MSG (hash2 == correct_hash, ("%#x != %#x\n", hash2, correct_hash));
790 }
791#endif /* NDEBUG */
792
793 cache->lookup_count++;
794
795 /* Lookup the entry in the hash table, hoping for an
796 early match. If not found, enter the string at IDX. */
797 idx = STRCACHE2_MOD_IT (cache, hash1);
798 entry = cache->hash_tab[idx];
799 if (!entry)
800 return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
801 if (strcache2_is_equal (cache, entry, str, length, hash1))
802 return (const char *)(entry + 1);
803 cache->collision_1st_count++;
804
805#ifdef STRCACHE2_USE_CHAINING
806 entry = entry->next;
807#else /* !STRCACHE2_USE_CHAINING */
808 if (!hash2)
809 hash2 = strcache2_case_sensitive_hash_2 (str, length);
810 idx += hash2;
811 idx = STRCACHE2_MOD_IT (cache, idx);
812 entry = cache->hash_tab[idx];
813#endif /* !STRCACHE2_USE_CHAINING */
814 if (!entry)
815 return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
816 if (strcache2_is_equal (cache, entry, str, length, hash1))
817 return (const char *)(entry + 1);
818 cache->collision_2nd_count++;
819
820 /* (We've established hash2, so we can do a straight loop now.) */
821 for (;;)
822 {
823#ifdef STRCACHE2_USE_CHAINING
824 entry = entry->next;
825#else /* !STRCACHE2_USE_CHAINING */
826 idx += hash2;
827 idx = STRCACHE2_MOD_IT (cache, idx);
828 entry = cache->hash_tab[idx];
829#endif /* !STRCACHE2_USE_CHAINING */
830 if (!entry)
831 return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
832 if (strcache2_is_equal (cache, entry, str, length, hash1))
833 return (const char *)(entry + 1);
834 cache->collision_3rd_count++;
835 }
836 /* not reached */
837}
838
839/* The public lookup (case sensitive) string interface. */
840const char *
841strcache2_lookup (struct strcache2 *cache, const char *str, unsigned int length)
842{
843 struct strcache2_entry const *entry;
844 unsigned int hash1 = strcache2_case_sensitive_hash_1 (str, length);
845#ifndef STRCACHE2_USE_CHAINING
846 unsigned int hash2;
847#endif
848 unsigned int idx;
849
850 assert (!cache->case_insensitive);
851
852 cache->lookup_count++;
853
854 /* Lookup the entry in the hash table, hoping for an
855 early match. */
856 idx = STRCACHE2_MOD_IT (cache, hash1);
857 entry = cache->hash_tab[idx];
858 if (!entry)
859 return NULL;
860 if (strcache2_is_equal (cache, entry, str, length, hash1))
861 return (const char *)(entry + 1);
862 cache->collision_1st_count++;
863
864#ifdef STRCACHE2_USE_CHAINING
865 entry = entry->next;
866#else /* !STRCACHE2_USE_CHAINING */
867 hash2 = strcache2_case_sensitive_hash_2 (str, length);
868 idx += hash2;
869 idx = STRCACHE2_MOD_IT (cache, idx);
870 entry = cache->hash_tab[idx];
871#endif /* !STRCACHE2_USE_CHAINING */
872 if (!entry)
873 return NULL;
874 if (strcache2_is_equal (cache, entry, str, length, hash1))
875 return (const char *)(entry + 1);
876 cache->collision_2nd_count++;
877
878 /* (We've established hash2, so we can do a straight loop now.) */
879 for (;;)
880 {
881#ifdef STRCACHE2_USE_CHAINING
882 entry = entry->next;
883#else /* !STRCACHE2_USE_CHAINING */
884 idx += hash2;
885 idx = STRCACHE2_MOD_IT (cache, idx);
886 entry = cache->hash_tab[idx];
887#endif /* !STRCACHE2_USE_CHAINING */
888 if (!entry)
889 return NULL;
890 if (strcache2_is_equal (cache, entry, str, length, hash1))
891 return (const char *)(entry + 1);
892 cache->collision_3rd_count++;
893 }
894 /* not reached */
895}
896
897#if defined(HAVE_CASE_INSENSITIVE_FS)
898
899/* The public add string interface for case insensitive strings. */
900const char *
901strcache2_iadd (struct strcache2 *cache, const char *str, unsigned int length)
902{
903 struct strcache2_entry const *entry;
904 unsigned int hash1 = strcache2_case_insensitive_hash_1 (str, length);
905 unsigned int hash2 = 0;
906 unsigned int idx;
907
908 assert (!cache->case_insensitive);
909
910 cache->lookup_count++;
911
912 /* Lookup the entry in the hash table, hoping for an
913 early match. If not found, enter the string at IDX. */
914 idx = STRCACHE2_MOD_IT (cache, hash1);
915 entry = cache->hash_tab[idx];
916 if (!entry)
917 return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
918 if (strcache2_is_equal (cache, entry, str, length, hash1))
919 return (const char *)(entry + 1);
920 cache->collision_1st_count++;
921
922#ifdef STRCACHE2_USE_CHAINING
923 entry = entry->next;
924#else /* !STRCACHE2_USE_CHAINING */
925 hash2 = strcache2_case_insensitive_hash_2 (str, length);
926 idx += hash2;
927 idx = STRCACHE2_MOD_IT (cache, idx);
928 entry = cache->hash_tab[idx];
929#endif /* !STRCACHE2_USE_CHAINING */
930 if (!entry)
931 return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
932 if (strcache2_is_equal (cache, entry, str, length, hash1))
933 return (const char *)(entry + 1);
934 cache->collision_2nd_count++;
935
936 /* (We've established hash2, so we can do a straight loop now.) */
937 for (;;)
938 {
939#ifdef STRCACHE2_USE_CHAINING
940 entry = entry->next;
941#else /* !STRCACHE2_USE_CHAINING */
942 idx += hash2;
943 idx = STRCACHE2_MOD_IT (cache, idx);
944 entry = cache->hash_tab[idx];
945#endif /* !STRCACHE2_USE_CHAINING */
946 if (!entry)
947 return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
948 if (strcache2_is_equal (cache, entry, str, length, hash1))
949 return (const char *)(entry + 1);
950 cache->collision_3rd_count++;
951 }
952 /* not reached */
953}
954
955/* The public add string interface for prehashed case insensitive strings.
956 Use strcache2_hash_istr to calculate the hash of a string. */
957const char *
958strcache2_iadd_hashed (struct strcache2 *cache, const char *str, unsigned int length,
959 unsigned int hash1, unsigned int hash2)
960{
961 struct strcache2_entry const *entry;
962 unsigned int idx;
963#ifndef NDEBUG
964 unsigned correct_hash;
965
966 assert (!cache->case_insensitive);
967 correct_hash = strcache2_case_insensitive_hash_1 (str, length);
968 MY_ASSERT_MSG (hash1 == correct_hash, ("%#x != %#x\n", hash1, correct_hash));
969 if (hash2)
970 {
971 correct_hash = strcache2_case_insensitive_hash_2 (str, length);
972 MY_ASSERT_MSG (hash2 == correct_hash, ("%#x != %#x\n", hash2, correct_hash));
973 }
974#endif /* NDEBUG */
975
976 cache->lookup_count++;
977
978 /* Lookup the entry in the hash table, hoping for an
979 early match. If not found, enter the string at IDX. */
980 idx = STRCACHE2_MOD_IT (cache, hash1);
981 entry = cache->hash_tab[idx];
982 if (!entry)
983 return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
984 if (strcache2_is_equal (cache, entry, str, length, hash1))
985 return (const char *)(entry + 1);
986 cache->collision_1st_count++;
987
988#ifdef STRCACHE2_USE_CHAINING
989 entry = entry->next;
990#else /* !STRCACHE2_USE_CHAINING */
991 if (!hash2)
992 hash2 = strcache2_case_insensitive_hash_2 (str, length);
993 idx += hash2;
994 idx = STRCACHE2_MOD_IT (cache, idx);
995 entry = cache->hash_tab[idx];
996#endif /* !STRCACHE2_USE_CHAINING */
997 if (!entry)
998 return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
999 if (strcache2_is_equal (cache, entry, str, length, hash1))
1000 return (const char *)(entry + 1);
1001 cache->collision_2nd_count++;
1002
1003 /* (We've established hash2, so we can do a straight loop now.) */
1004 for (;;)
1005 {
1006#ifdef STRCACHE2_USE_CHAINING
1007 entry = entry->next;
1008#else /* !STRCACHE2_USE_CHAINING */
1009 idx += hash2;
1010 idx = STRCACHE2_MOD_IT (cache, idx);
1011 entry = cache->hash_tab[idx];
1012#endif /* !STRCACHE2_USE_CHAINING */
1013 if (!entry)
1014 return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
1015 if (strcache2_is_equal (cache, entry, str, length, hash1))
1016 return (const char *)(entry + 1);
1017 cache->collision_3rd_count++;
1018 }
1019 /* not reached */
1020}
1021
1022/* The public lookup (case insensitive) string interface. */
1023const char *
1024strcache2_ilookup (struct strcache2 *cache, const char *str, unsigned int length)
1025{
1026 struct strcache2_entry const *entry;
1027 unsigned int hash1 = strcache2_case_insensitive_hash_1 (str, length);
1028#ifndef STRCACHE2_USE_CHAINING
1029 unsigned int hash2;
1030#endif
1031 unsigned int idx;
1032
1033 assert (!cache->case_insensitive);
1034
1035 cache->lookup_count++;
1036
1037 /* Lookup the entry in the hash table, hoping for an
1038 early match. */
1039 idx = STRCACHE2_MOD_IT (cache, hash1);
1040 entry = cache->hash_tab[idx];
1041 if (!entry)
1042 return NULL;
1043 if (strcache2_is_equal (cache, entry, str, length, hash1))
1044 return (const char *)(entry + 1);
1045 cache->collision_1st_count++;
1046
1047#ifdef STRCACHE2_USE_CHAINING
1048 entry = entry->next;
1049#else /* !STRCACHE2_USE_CHAINING */
1050 hash2 = strcache2_case_insensitive_hash_2 (str, length);
1051 idx += hash2;
1052 idx = STRCACHE2_MOD_IT (cache, idx);
1053 entry = cache->hash_tab[idx];
1054#endif /* !STRCACHE2_USE_CHAINING */
1055 if (!entry)
1056 return NULL;
1057 if (strcache2_is_equal (cache, entry, str, length, hash1))
1058 return (const char *)(entry + 1);
1059 cache->collision_2nd_count++;
1060
1061 /* (We've established hash2, so we can do a straight loop now.) */
1062 for (;;)
1063 {
1064#ifdef STRCACHE2_USE_CHAINING
1065 entry = entry->next;
1066#else /* !STRCACHE2_USE_CHAINING */
1067 idx += hash2;
1068 idx = STRCACHE2_MOD_IT (cache, idx);
1069 entry = cache->hash_tab[idx];
1070#endif /* !STRCACHE2_USE_CHAINING */
1071 if (!entry)
1072 return NULL;
1073 if (strcache2_is_equal (cache, entry, str, length, hash1))
1074 return (const char *)(entry + 1);
1075 cache->collision_3rd_count++;
1076 }
1077 /* not reached */
1078}
1079
1080#endif /* HAVE_CASE_INSENSITIVE_FS */
1081
1082/* Is the given string cached? returns 1 if it is, 0 if it isn't. */
1083int
1084strcache2_is_cached (struct strcache2 *cache, const char *str)
1085{
1086 /* Check mandatory alignment first. */
1087 if (!((size_t)str & (sizeof (void *) - 1)))
1088 {
1089 /* Check the segment list and consider the question answered if the
1090 string is within one of them. (Could check it more thoroughly...) */
1091 struct strcache2_seg const *seg;
1092 for (seg = cache->seg_head; seg; seg = seg->next)
1093 if ((size_t)(str - seg->start) < seg->size)
1094 return 1;
1095 }
1096
1097 return 0;
1098}
1099
1100
1101/* Verify the integrity of the specified string, returning 0 if OK. */
1102int
1103strcache2_verify_entry (struct strcache2 *cache, const char *str)
1104{
1105 struct strcache2_entry const *entry;
1106 unsigned hash;
1107 const char *end;
1108
1109 if ((size_t)str & (sizeof (void *) - 1))
1110 {
1111 fprintf (stderr,
1112 "strcache2[%s]: missaligned string %p\nstring: %s\n",
1113 cache->name, (void *)str, str);
1114 return -1;
1115 }
1116
1117 entry = (struct strcache2_entry const *)str - 1;
1118 end = memchr (str, '\0', entry->length);
1119 if ((size_t)(end - str) == entry->length)
1120 {
1121 fprintf (stderr,
1122 "strcache2[%s]: corrupt entry %p, length: %lu, expected %u;\nstring: %s\n",
1123 cache->name, (void *)entry, (unsigned long)(end - str), entry->length, str);
1124 return -1;
1125 }
1126
1127 hash = cache->case_insensitive
1128 ? strcache2_case_insensitive_hash_1 (str, entry->length)
1129 : strcache2_case_sensitive_hash_1 (str, entry->length);
1130 if (hash != entry->hash1)
1131 {
1132 fprintf (stderr,
1133 "strcache2[%s]: corrupt entry %p, hash#1: %x, expected %x;\nstring: %s\n",
1134 cache->name, (void *)entry, hash, entry->hash1, str);
1135 return -1;
1136 }
1137
1138#ifndef STRCACHE2_USE_CHAINING
1139 if (entry->hash2)
1140 {
1141 hash = cache->case_insensitive
1142 ? strcache2_case_insensitive_hash_2 (str, entry->length)
1143 : strcache2_case_sensitive_hash_2 (str, entry->length);
1144 if (hash != entry->hash2)
1145 {
1146 fprintf (stderr,
1147 "strcache2[%s]: corrupt entry %p, hash#2: %x, expected %x;\nstring: %s\n",
1148 cache->name, (void *)entry, hash, entry->hash2, str);
1149 return -1;
1150 }
1151 }
1152#endif
1153
1154 return 0;
1155}
1156
1157#ifndef STRCACHE2_USE_CHAINING
1158/* Fallback for calculating and returning the 2nd hash. */
1159unsigned int
1160strcache2_get_hash2_fallback (struct strcache2 *cache, const char *str)
1161{
1162 struct strcache2_entry *entry = (struct strcache2_entry *) str - 1;
1163 unsigned hash2 = cache->case_insensitive
1164 ? strcache2_case_insensitive_hash_2 (str, entry->length)
1165 : strcache2_case_sensitive_hash_2 (str, entry->length);
1166 entry->hash2 = hash2;
1167 return hash2;
1168}
1169#endif /* !STRCACHE2_USE_CHAINING */
1170
1171/* Calculates the case sensitive hash values of the string.
1172 The first hash is returned, the other is put at HASH2P. */
1173unsigned int strcache2_hash_str (const char *str, unsigned int length, unsigned int *hash2p)
1174{
1175#ifndef STRCACHE2_USE_CHAINING
1176 *hash2p = strcache2_case_sensitive_hash_2 (str, length);
1177#else
1178 *hash2p = 1;
1179#endif
1180 return strcache2_case_sensitive_hash_1 (str, length);
1181}
1182
1183/* Calculates the case insensitive hash values of the string.
1184 The first hash is returned, the other is put at HASH2P. */
1185unsigned int strcache2_hash_istr (const char *str, unsigned int length, unsigned int *hash2p)
1186{
1187#ifndef STRCACHE2_USE_CHAINING
1188 *hash2p = strcache2_case_insensitive_hash_2 (str, length);
1189#else
1190 *hash2p = 1;
1191#endif
1192 return strcache2_case_insensitive_hash_1 (str, length);
1193}
1194
1195
1196
1197/* Initalizes a new cache. */
1198void
1199strcache2_init (struct strcache2 *cache, const char *name, unsigned int size,
1200 unsigned int def_seg_size, int case_insensitive, int thread_safe)
1201{
1202 unsigned hash_shift;
1203 assert (!thread_safe);
1204
1205 /* calc the size as a power of two */
1206 if (!size)
1207 hash_shift = STRCACHE2_HASH_SHIFT;
1208 else
1209 {
1210 assert (size <= (~0U / 2 + 1));
1211 for (hash_shift = 8; (1U << hash_shift) < size; hash_shift++)
1212 /* nothing */;
1213 }
1214
1215 /* adjust the default segment size */
1216 if (!def_seg_size)
1217 def_seg_size = STRCACHE2_SEG_SIZE;
1218 else if (def_seg_size < sizeof (struct strcache2_seg) * 10)
1219 def_seg_size = sizeof (struct strcache2_seg) * 10;
1220 else if ((def_seg_size & 0xfff) < 0xf00)
1221 def_seg_size = ((def_seg_size + 0xfff) & ~0xfffU);
1222
1223
1224 /* init the structure. */
1225 cache->case_insensitive = case_insensitive;
1226#ifdef STRCACHE2_USE_MASK
1227 cache->hash_mask = (1U << hash_shift) - 1U;
1228#else
1229 cache->hash_div = strcache2_find_prime(hash_shift);
1230#endif
1231 cache->count = 0;
1232#ifdef STRCACHE2_USE_CHAINING
1233 cache->collision_count = 0;
1234#endif
1235 cache->lookup_count = 0;
1236 cache->collision_1st_count = 0;
1237 cache->collision_2nd_count = 0;
1238 cache->collision_3rd_count = 0;
1239 cache->rehash_count = (1U << hash_shift) / 4 * 3; /* rehash at 75% */
1240 cache->init_size = 1U << hash_shift;
1241 cache->hash_size = 1U << hash_shift;
1242 cache->def_seg_size = def_seg_size;
1243 cache->lock = NULL;
1244 cache->name = name;
1245
1246 /* allocate the hash table and first segment. */
1247 cache->hash_tab = (struct strcache2_entry **)
1248 xmalloc (cache->init_size * sizeof (struct strcache2_entry *));
1249 memset (cache->hash_tab, '\0', cache->init_size * sizeof (struct strcache2_entry *));
1250 strcache2_new_seg (cache, 0);
1251
1252 /* link it */
1253 cache->next = strcache_head;
1254 strcache_head = cache;
1255}
1256
1257
1258/* Terminates a string cache, freeing all memory and other
1259 associated resources. */
1260void
1261strcache2_term (struct strcache2 *cache)
1262{
1263 /* unlink it */
1264 if (strcache_head == cache)
1265 strcache_head = cache->next;
1266 else
1267 {
1268 struct strcache2 *prev = strcache_head;
1269 while (prev->next != cache)
1270 prev = prev->next;
1271 assert (prev);
1272 prev->next = cache->next;
1273 }
1274
1275 /* free the memory segments */
1276 do
1277 {
1278 void *free_it = cache->seg_head;
1279 cache->seg_head = cache->seg_head->next;
1280 free (free_it);
1281 }
1282 while (cache->seg_head);
1283
1284 /* free the hash and clear the structure. */
1285 free (cache->hash_tab);
1286 memset (cache, '\0', sizeof (struct strcache2));
1287}
1288
1289/* Print statistics a string cache. */
1290void
1291strcache2_print_stats (struct strcache2 *cache, const char *prefix)
1292{
1293 unsigned int seg_count = 0;
1294 unsigned long seg_total_bytes = 0;
1295 unsigned long seg_avg_bytes;
1296 unsigned long seg_avail_bytes = 0;
1297 unsigned long seg_max_bytes = 0;
1298 struct strcache2_seg *seg;
1299 unsigned int str_count = 0;
1300 unsigned long str_total_len = 0;
1301 unsigned int str_avg_len;
1302 unsigned int str_min_len = ~0U;
1303 unsigned int str_max_len = 0;
1304 unsigned int idx;
1305 unsigned int rehashes;
1306#ifdef STRCACHE2_USE_CHAINING
1307 unsigned int chain_depths[32];
1308#endif
1309
1310 printf (_("\n%s strcache2: %s\n"), prefix, cache->name);
1311
1312 /* Segment statistics. */
1313 for (seg = cache->seg_head; seg; seg = seg->next)
1314 {
1315 seg_count++;
1316 seg_total_bytes += seg->size;
1317 seg_avail_bytes += seg->avail;
1318 if (seg->size > seg_max_bytes)
1319 seg_max_bytes = seg->size;
1320 }
1321 seg_avg_bytes = seg_total_bytes / seg_count;
1322 printf (_("%s %u segments: total = %lu / max = %lu / avg = %lu / def = %u avail = %lu\n"),
1323 prefix, seg_count, seg_total_bytes, seg_max_bytes, seg_avg_bytes,
1324 cache->def_seg_size, seg_avail_bytes);
1325
1326 /* String statistics. */
1327#ifdef STRCACHE2_USE_CHAINING
1328 memset (chain_depths, '\0', sizeof (chain_depths));
1329#endif
1330 idx = cache->hash_size;
1331 while (idx-- > 0)
1332 {
1333 struct strcache2_entry const *entry = cache->hash_tab[idx];
1334#ifdef STRCACHE2_USE_CHAINING
1335 unsigned int depth = 0;
1336 for (; entry != 0; entry = entry->next, depth++)
1337#else
1338 if (entry)
1339#endif
1340 {
1341 unsigned int length = entry->length;
1342 str_total_len += length;
1343 if (length > str_max_len)
1344 str_max_len = length;
1345 if (length < str_min_len)
1346 str_min_len = length;
1347 str_count++;
1348 }
1349#ifdef STRCACHE2_USE_CHAINING
1350 chain_depths[depth >= 32 ? 31 : depth]++;
1351#endif
1352 }
1353 str_avg_len = cache->count ? str_total_len / cache->count : 0;
1354 printf (_("%s %u strings: total len = %lu / max = %u / avg = %u / min = %u\n"),
1355 prefix, cache->count, str_total_len, str_max_len, str_avg_len, str_min_len);
1356 if (str_count != cache->count)
1357 printf (_("%s string count mismatch! cache->count=%u, actual count is %u\n"), prefix,
1358 cache->count, str_count);
1359
1360 /* Hash statistics. */
1361 idx = cache->init_size;
1362 rehashes = 0;
1363 while (idx < cache->hash_size)
1364 {
1365 idx *= 2;
1366 rehashes++;
1367 }
1368
1369#ifdef STRCACHE2_USE_MASK
1370 printf (_("%s hash size = %u mask = %#x rehashed %u times lookups = %lu\n"),
1371 prefix, cache->hash_size, cache->hash_mask, rehashes, cache->lookup_count);
1372#else
1373 printf (_("%s hash size = %u div = %#x rehashed %u times lookups = %lu\n"),
1374 prefix, cache->hash_size, cache->hash_div, rehashes, cache->lookup_count);
1375#endif
1376 printf (_("%s hash collisions 1st = %lu (%u%%) 2nd = %lu (%u%%) 3rd = %lu (%u%%)\n"),
1377 prefix,
1378 cache->collision_1st_count, (unsigned int)((100.0 * cache->collision_1st_count) / cache->lookup_count),
1379 cache->collision_2nd_count, (unsigned int)((100.0 * cache->collision_2nd_count) / cache->lookup_count),
1380 cache->collision_3rd_count, (unsigned int)((100.0 * cache->collision_3rd_count) / cache->lookup_count));
1381#ifdef STRCACHE2_USE_CHAINING
1382 printf (_("%s hash insert collisions = %u (%u%%)\n"),
1383 prefix, cache->collision_count,(unsigned int)((100.0 * cache->collision_count) / cache->count));
1384 printf (_("%s %5u (%u%%) empty hash table slots\n"),
1385 prefix, chain_depths[0], (unsigned int)((100.0 * chain_depths[0]) / cache->hash_size));
1386 printf (_("%s %5u (%u%%) in used hash table slots\n"),
1387 prefix, chain_depths[1], (unsigned int)((100.0 * chain_depths[1]) / cache->hash_size));
1388 for (idx = 2; idx < 32; idx++)
1389 {
1390 unsigned strs_at_this_depth = chain_depths[idx];
1391 unsigned i;
1392 for (i = idx + 1; i < 32; i++)
1393 strs_at_this_depth += chain_depths[i];
1394 if (strs_at_this_depth)
1395 printf (_("%s %5u (%2u%%) with %u string%s chained on; %5u (%2u%%) strings at depth %u.\n"),
1396 prefix, chain_depths[idx], (unsigned int)((100.0 * chain_depths[idx]) / (cache->count - cache->collision_count)),
1397 idx - 1, idx == 2 ? " " : "s",
1398 strs_at_this_depth, (unsigned int)((100.0 * strs_at_this_depth) / cache->count), idx - 1);
1399 }
1400#endif
1401}
1402
1403/* Print statistics for all string caches. */
1404void
1405strcache2_print_stats_all (const char *prefix)
1406{
1407 struct strcache2 *cur;
1408 for (cur = strcache_head; cur; cur = cur->next)
1409 strcache2_print_stats (cur, prefix);
1410}
1411
Note: See TracBrowser for help on using the repository browser.