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

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

kmk: strcache2_add_file macro for wrapping case sensitive/insenstive hashing, avoiding a couple of checks a lots of inlined code in strcache2.
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 22.5 KB
Line 
1/* $Id: strcache2.c 1885 2008-10-19 21:30:02Z 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
62
63/*******************************************************************************
64* Global Variables *
65*******************************************************************************/
66/* List of initialized string caches. */
67static struct strcache2 *strcache_head;
68
69
70
71static struct strcache2_seg *
72strcache2_new_seg (struct strcache2 *cache, unsigned int minlen)
73{
74 struct strcache2_seg *seg;
75 size_t size;
76
77 size = cache->def_seg_size;
78 if (size < (size_t)minlen + sizeof (struct strcache2_seg))
79 {
80 size = (size_t)minlen * 2;
81 size = (size + 0xfff) & ~(size_t)0xfff;
82 }
83
84 seg = xmalloc (size);
85 seg->cursor = seg->start = (char *)(seg + 1);
86 seg->size = seg->avail = size - sizeof (struct strcache2_seg);
87 assert (seg->size > minlen);
88
89 seg->next = cache->seg_head;
90 cache->seg_head = seg;
91
92 return seg;
93}
94
95MY_INLINE unsigned int
96strcache2_case_sensitive_hash_1 (const char *str, unsigned int len)
97{
98 unsigned int hash = 0;
99 if (MY_PREDICT_TRUE(len >= 2))
100 {
101 unsigned int ch0 = *str++;
102 hash = 0;
103 len--;
104 while (len >= 2)
105 {
106 unsigned int ch1 = *str++;
107 hash += ch0 << (ch1 & 0xf);
108
109 ch0 = *str++;
110 hash += ch1 << (ch0 & 0xf);
111
112 len -= 2;
113 }
114 if (len == 1)
115 {
116 unsigned ch1 = *str;
117 hash += ch0 << (ch1 & 0xf);
118
119 hash += ch1;
120 }
121 else
122 hash += ch0;
123 }
124 else if (len)
125 {
126 hash = *str;
127 hash += hash << (hash & 0xf);
128 }
129 else
130 hash = 0;
131 return hash;
132}
133
134MY_INLINE unsigned int
135strcache2_case_sensitive_hash_2 (const char *str, unsigned int len)
136{
137 unsigned int hash = 0;
138 if (MY_PREDICT_TRUE(len >= 2))
139 {
140 unsigned int ch0 = *str++;
141 hash = 0;
142 len--;
143 while (len >= 2)
144 {
145 unsigned int ch1 = *str++;
146 hash += ch0 << (ch1 & 0x7);
147
148 ch0 = *str++;
149 hash += ch1 << (ch0 & 0x7);
150
151 len -= 2;
152 }
153 if (len == 1)
154 {
155 unsigned ch1 = *str;
156 hash += ch0 << (ch1 & 0x7);
157
158 hash += ch1;
159 }
160 else
161 hash += ch0;
162 }
163 else if (len)
164 {
165 hash = *str;
166 hash += hash << (hash & 0x7);
167 }
168 else
169 hash = 1;
170 hash |= 1;
171 return hash;
172}
173
174MY_INLINE unsigned int
175strcache2_case_insensitive_hash_1 (const char *str, unsigned int len)
176{
177 unsigned int hash = 0;
178 if (MY_PREDICT_TRUE(len >= 2))
179 {
180 unsigned int ch0 = *str++;
181 ch0 = tolower (ch0);
182 hash = 0;
183 len--;
184 while (len >= 2)
185 {
186 unsigned int ch1 = *str++;
187 ch1 = tolower (ch1);
188 hash += ch0 << (ch1 & 0xf);
189
190 ch0 = *str++;
191 ch0 = tolower (ch0);
192 hash += ch1 << (ch0 & 0xf);
193
194 len -= 2;
195 }
196 if (len == 1)
197 {
198 unsigned ch1 = *str;
199 ch1 = tolower (ch1);
200 hash += ch0 << (ch1 & 0xf);
201
202 hash += ch1;
203 }
204 else
205 hash += ch0;
206 }
207 else if (len)
208 {
209 hash = *str;
210 hash += hash << (hash & 0xf);
211 }
212 else
213 hash = 0;
214 return hash;
215}
216
217MY_INLINE unsigned int
218strcache2_case_insensitive_hash_2 (const char *str, unsigned int len)
219{
220 unsigned int hash = 0;
221 if (MY_PREDICT_TRUE(len >= 2))
222 {
223 unsigned int ch0 = *str++;
224 ch0 = tolower (ch0);
225 hash = 0;
226 len--;
227 while (len >= 2)
228 {
229 unsigned int ch1 = *str++;
230 ch1 = tolower (ch1);
231 hash += ch0 << (ch1 & 0x7);
232
233 ch0 = *str++;
234 ch0 = tolower (ch0);
235 hash += ch1 << (ch0 & 0x7);
236
237 len -= 2;
238 }
239 if (len == 1)
240 {
241 unsigned ch1 = *str;
242 ch1 = tolower (ch1);
243 hash += ch0 << (ch1 & 0x7);
244
245 hash += ch1;
246 }
247 else
248 hash += ch0;
249 }
250 else if (len)
251 {
252 hash = *str;
253 hash += hash << (hash & 0x7);
254 }
255 else
256 hash = 1;
257 hash |= 1;
258 return hash;
259}
260
261MY_INLINE int
262strcache2_is_equal (struct strcache2 *cache, struct strcache2_entry const *entry,
263 const char *str, unsigned int length, unsigned int hash1)
264{
265 /* the simple stuff first. */
266 if ( entry == NULL
267 || entry->hash1 != hash1
268 || entry->length != length)
269 return 0;
270
271 return !cache->case_insensitive
272 ? memcmp (entry + 1, str, length) == 0
273#if defined(_MSC_VER) || defined(__OS2__)
274 : _memicmp (entry + 1, str, length) == 0
275#else
276 : strncasecmp ((const char *)(entry + 1), str, length) == 0
277#endif
278 ;
279}
280
281static void
282strcache2_rehash (struct strcache2 *cache)
283{
284 unsigned int src = cache->hash_size;
285 struct strcache2_entry **src_tab = cache->hash_tab;
286 struct strcache2_entry **dst_tab;
287 unsigned int hash_mask;
288
289 /* Allocate a new hash table twice the size of the current. */
290 cache->hash_size <<= 1;
291 cache->hash_mask <<= 1;
292 cache->hash_mask |= 1;
293 cache->rehash_count <<= 1;
294 cache->hash_tab = dst_tab = (struct strcache2_entry **)
295 xmalloc (cache->hash_size * sizeof (struct strcache2_entry *));
296 memset (dst_tab, '\0', cache->hash_size * sizeof (struct strcache2_entry *));
297
298 /* Copy the entries from the old to the new hash table. */
299 hash_mask = cache->hash_mask;
300 while (src-- > 0)
301 {
302 struct strcache2_entry *entry = src_tab[src];
303 if (entry)
304 {
305 unsigned int dst = entry->hash1 & hash_mask;
306 if (dst_tab[dst])
307 {
308 unsigned int hash2 = entry->hash2;
309 if (!hash2)
310 entry->hash2 = hash2 = cache->case_insensitive
311 ? strcache2_case_insensitive_hash_2 ((const char *)(entry + 1), entry->length)
312 : strcache2_case_sensitive_hash_2 ((const char *)(entry + 1), entry->length);
313 dst += hash2;
314 dst &= hash_mask;
315 while (dst_tab[dst])
316 {
317 dst += hash2;
318 dst &= hash_mask;
319 }
320 }
321
322 dst_tab[dst] = entry;
323 }
324 }
325
326 /* That's it, just free the old table and we're done. */
327 free (src_tab);
328}
329
330/* Internal worker that enters a new string into the cache. */
331static const char *
332strcache2_enter_string (struct strcache2 *cache, unsigned int idx,
333 const char *str, unsigned int length,
334 unsigned int hash1, unsigned hash2)
335{
336 struct strcache2_entry *entry;
337 struct strcache2_seg *seg;
338 unsigned int size;
339 char *str_copy;
340
341 /* Allocate space for the string. */
342
343 size = length + 1 + sizeof (struct strcache2_entry);
344 size = (size + sizeof (void *) - 1) & ~(sizeof (void *) - 1U);
345
346 seg = cache->seg_head;
347 if (MY_PREDICT_FALSE(seg->avail < size))
348 {
349 do
350 seg = seg->next;
351 while (seg && seg->avail < size);
352 if (!seg)
353 seg = strcache2_new_seg (cache, size);
354 }
355
356 entry = (struct strcache2_entry *) seg->cursor;
357 seg->cursor += size;
358 seg->avail -= size;
359
360 /* Setup the entry, copy the string and insert it into the hash table. */
361
362 entry->user = NULL;
363 entry->length = length;
364 entry->hash1 = hash1;
365 entry->hash2 = hash2;
366 str_copy = (char *) memcpy (entry + 1, str, length);
367 str_copy[length] = '\0';
368
369 cache->hash_tab[idx] = entry;
370 cache->count++;
371 if (cache->count >= cache->rehash_count)
372 strcache2_rehash (cache);
373
374 return str_copy;
375}
376
377/* The public add/lookup string interface. */
378const char *
379strcache2_add (struct strcache2 *cache, const char *str, unsigned int length)
380{
381 struct strcache2_entry const *entry;
382 unsigned int hash2;
383 unsigned int hash1 = strcache2_case_sensitive_hash_1 (str, length);
384 unsigned int idx;
385
386 assert (!cache->case_insensitive);
387
388
389 cache->lookup_count++;
390
391 /* Lookup the entry in the hash table, hoping for an
392 early match. */
393 idx = hash1 & cache->hash_mask;
394 entry = cache->hash_tab[idx];
395 if (strcache2_is_equal (cache, entry, str, length, hash1))
396 return (const char *)(entry + 1);
397 if (!entry)
398 hash2 = 0;
399 else
400 {
401 cache->collision_1st_count++;
402
403 hash2 = strcache2_case_sensitive_hash_2 (str, length);
404 idx += hash2;
405 idx &= cache->hash_mask;
406 entry = cache->hash_tab[idx];
407 if (strcache2_is_equal (cache, entry, str, length, hash1))
408 return (const char *)(entry + 1);
409
410 if (entry)
411 {
412 cache->collision_2nd_count++;
413 do
414 {
415 idx += hash2;
416 idx &= cache->hash_mask;
417 entry = cache->hash_tab[idx];
418 cache->collision_3rd_count++;
419 if (strcache2_is_equal (cache, entry, str, length, hash1))
420 return (const char *)(entry + 1);
421 }
422 while (entry);
423 }
424 }
425
426 /* Not found, add it at IDX. */
427 return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
428}
429
430/* The public add/lookup string interface for prehashed strings.
431 Use strcache2_hash_str to calculate the hash of a string. */
432const char *
433strcache2_add_hashed (struct strcache2 *cache, const char *str, unsigned int length,
434 unsigned int hash1, unsigned int hash2)
435{
436 struct strcache2_entry const *entry;
437 unsigned int idx;
438#ifndef NDEBUG
439 unsigned correct_hash;
440
441 correct_hash = cache->case_insensitive
442 ? strcache2_case_insensitive_hash_1 (str, length)
443 : strcache2_case_sensitive_hash_1 (str, length);
444 MY_ASSERT_MSG (hash1 == correct_hash, ("%#x != %#x\n", hash1, correct_hash));
445 if (hash2)
446 {
447 correct_hash = cache->case_insensitive
448 ? strcache2_case_insensitive_hash_2 (str, length)
449 : strcache2_case_sensitive_hash_2 (str, length);
450 MY_ASSERT_MSG (hash2 == correct_hash, ("%#x != %#x\n", hash2, correct_hash));
451 }
452#endif /* NDEBUG */
453
454 cache->lookup_count++;
455
456 /* Lookup the entry in the hash table, hoping for an
457 early match. */
458 idx = hash1 & cache->hash_mask;
459 entry = cache->hash_tab[idx];
460 if (strcache2_is_equal (cache, entry, str, length, hash1))
461 return (const char *)(entry + 1);
462 if (entry)
463 {
464 cache->collision_1st_count++;
465
466 if (!hash2)
467 hash2 = cache->case_insensitive
468 ? strcache2_case_insensitive_hash_2 (str, length)
469 : strcache2_case_sensitive_hash_2 (str, length);
470 idx += hash2;
471 idx &= cache->hash_mask;
472 entry = cache->hash_tab[idx];
473 if (strcache2_is_equal (cache, entry, str, length, hash1))
474 return (const char *)(entry + 1);
475
476 if (entry)
477 {
478 cache->collision_2nd_count++;
479 do
480 {
481 idx += hash2;
482 idx &= cache->hash_mask;
483 entry = cache->hash_tab[idx];
484 cache->collision_3rd_count++;
485 if (strcache2_is_equal (cache, entry, str, length, hash1))
486 return (const char *)(entry + 1);
487 }
488 while (entry);
489 }
490 }
491
492 /* Not found, add it at IDX. */
493 return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
494}
495
496#if defined(HAVE_CASE_INSENSITIVE_FS)
497
498/* The public add/lookup string interface for case insensitive strings. */
499const char *
500strcache2_iadd (struct strcache2 *cache, const char *str, unsigned int length)
501{
502 struct strcache2_entry const *entry;
503 unsigned int hash2;
504 unsigned int hash1 = strcache2_case_insensitive_hash_1 (str, length);
505 unsigned int idx;
506
507 assert (cache->case_insensitive);
508 cache->lookup_count++;
509
510 /* Lookup the entry in the hash table, hoping for an
511 early match. */
512 idx = hash1 & cache->hash_mask;
513 entry = cache->hash_tab[idx];
514 if (strcache2_is_equal (cache, entry, str, length, hash1))
515 return (const char *)(entry + 1);
516 if (!entry)
517 hash2 = 0;
518 else
519 {
520 cache->collision_1st_count++;
521
522 hash2 = strcache2_case_insensitive_hash_2 (str, length);
523 idx += hash2;
524 idx &= cache->hash_mask;
525 entry = cache->hash_tab[idx];
526 if (strcache2_is_equal (cache, entry, str, length, hash1))
527 return (const char *)(entry + 1);
528
529 if (entry)
530 {
531 cache->collision_2nd_count++;
532 do
533 {
534 idx += hash2;
535 idx &= cache->hash_mask;
536 entry = cache->hash_tab[idx];
537 cache->collision_3rd_count++;
538 if (strcache2_is_equal (cache, entry, str, length, hash1))
539 return (const char *)(entry + 1);
540 }
541 while (entry);
542 }
543 }
544
545 /* Not found, add it at IDX. */
546 return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
547}
548
549/* strcache_ilookup later */
550
551#endif /* HAVE_CASE_INSENSITIVE_FS */
552
553/* Is the given string cached? returns 1 if it is, 0 if it isn't. */
554int
555strcache2_is_cached (struct strcache2 *cache, const char *str)
556{
557 /* Check mandatory alignment first. */
558 if (!((size_t)str & (sizeof (void *) - 1)))
559 {
560 /* Check the segment list and consider the question answered if the
561 string is within one of them. (Could check it more thoroughly...) */
562 struct strcache2_seg const *seg;
563 for (seg = cache->seg_head; seg; seg = seg->next)
564 if ((size_t)(str - seg->start) < seg->size)
565 return 1;
566 }
567
568 return 0;
569}
570
571
572/* Verify the integrity of the specified string, returning 0 if OK. */
573int
574strcache2_verify_entry (struct strcache2 *cache, const char *str)
575{
576 struct strcache2_entry const *entry;
577 unsigned hash;
578 const char *end;
579
580 if ((size_t)str & (sizeof (void *) - 1))
581 {
582 fprintf (stderr,
583 "strcache2[%s]: missaligned string %p\nstring: %s\n",
584 cache->name, (void *)str, str);
585 return -1;
586 }
587
588 entry = (struct strcache2_entry const *)str - 1;
589 end = memchr (str, '\0', entry->length);
590 if ((size_t)(end - str) == entry->length)
591 {
592 fprintf (stderr,
593 "strcache2[%s]: corrupt entry %p, length: %lu, expected %u;\nstring: %s\n",
594 cache->name, (void *)entry, (unsigned long)(end - str), entry->length, str);
595 return -1;
596 }
597
598 hash = cache->case_insensitive
599 ? strcache2_case_insensitive_hash_1 (str, entry->length)
600 : strcache2_case_sensitive_hash_1 (str, entry->length);
601 if (hash != entry->hash1)
602 {
603 fprintf (stderr,
604 "strcache2[%s]: corrupt entry %p, hash#1: %x, expected %x;\nstring: %s\n",
605 cache->name, (void *)entry, hash, entry->hash1, str);
606 return -1;
607 }
608
609 if (entry->hash2)
610 {
611 hash = cache->case_insensitive
612 ? strcache2_case_insensitive_hash_2 (str, entry->length)
613 : strcache2_case_sensitive_hash_2 (str, entry->length);
614 if (hash != entry->hash2)
615 {
616 fprintf (stderr,
617 "strcache2[%s]: corrupt entry %p, hash#2: %x, expected %x;\nstring: %s\n",
618 cache->name, (void *)entry, hash, entry->hash2, str);
619 return -1;
620 }
621 }
622
623 return 0;
624}
625
626/* Fallback for calculating and returning the 2nd hash. */
627unsigned int
628strcache2_get_hash2_fallback (struct strcache2 *cache, const char *str)
629{
630 struct strcache2_entry *entry = (struct strcache2_entry *) str - 1;
631 unsigned hash2 = cache->case_insensitive
632 ? strcache2_case_insensitive_hash_2 (str, entry->length)
633 : strcache2_case_sensitive_hash_2 (str, entry->length);
634 entry->hash2 = hash2;
635 return hash2;
636}
637
638/* Calculates the case sensitive hash values of the string.
639 The first hash is returned, the other is put at HASH2P. */
640unsigned int strcache2_hash_str (const char *str, unsigned int length, unsigned int *hash2p)
641{
642 *hash2p = strcache2_case_sensitive_hash_2 (str, length);
643 return strcache2_case_sensitive_hash_1 (str, length);
644}
645
646/* Calculates the case insensitive hash values of the string.
647 The first hash is returned, the other is put at HASH2P. */
648unsigned int strcache2_hash_istr (const char *str, unsigned int length, unsigned int *hash2p)
649{
650 *hash2p = strcache2_case_insensitive_hash_2 (str, length);
651 return strcache2_case_insensitive_hash_1 (str, length);
652}
653
654
655
656/* Initalizes a new cache. */
657void
658strcache2_init (struct strcache2 *cache, const char *name, unsigned int size,
659 unsigned int def_seg_size, int case_insensitive, int thread_safe)
660{
661 unsigned hash_shift;
662 assert (!thread_safe);
663
664 /* calc the size as a power of two */
665 if (!size)
666 hash_shift = STRCACHE2_HASH_SHIFT;
667 else
668 {
669 assert (size <= (~0U / 2 + 1));
670 for (hash_shift = 8; (1U << hash_shift) < size; hash_shift++)
671 /* nothing */;
672 }
673
674 /* adjust the default segment size */
675 if (!def_seg_size)
676 def_seg_size = STRCACHE2_SEG_SIZE;
677 else if (def_seg_size < sizeof (struct strcache2_seg) * 10)
678 def_seg_size = sizeof (struct strcache2_seg) * 10;
679 else if ((def_seg_size & 0xfff) < 0xf00)
680 def_seg_size = ((def_seg_size + 0xfff) & ~0xfffU);
681
682
683 /* init the structure. */
684 cache->case_insensitive = case_insensitive;
685 cache->hash_mask = (1U << hash_shift) - 1U;
686 cache->count = 0;
687 cache->lookup_count = 0;
688 cache->collision_1st_count = 0;
689 cache->collision_2nd_count = 0;
690 cache->collision_3rd_count = 0;
691 cache->rehash_count = (1U << hash_shift) / 4 * 3; /* rehash at 75% */
692 cache->init_size = 1U << hash_shift;
693 cache->hash_size = 1U << hash_shift;
694 cache->def_seg_size = def_seg_size;
695 cache->lock = NULL;
696 cache->name = name;
697
698 /* allocate the hash table and first segment. */
699 cache->hash_tab = (struct strcache2_entry **)
700 xmalloc (cache->init_size * sizeof (struct strcache2_entry *));
701 memset (cache->hash_tab, '\0', cache->init_size * sizeof (struct strcache2_entry *));
702 strcache2_new_seg (cache, 0);
703
704 /* link it */
705 cache->next = strcache_head;
706 strcache_head = cache;
707}
708
709
710/* Terminates a string cache, freeing all memory and other
711 associated resources. */
712void
713strcache2_term (struct strcache2 *cache)
714{
715 /* unlink it */
716 if (strcache_head == cache)
717 strcache_head = cache->next;
718 else
719 {
720 struct strcache2 *prev = strcache_head;
721 while (prev->next != cache)
722 prev = prev->next;
723 assert (prev);
724 prev->next = cache->next;
725 }
726
727 /* free the memory segments */
728 do
729 {
730 void *free_it = cache->seg_head;
731 cache->seg_head = cache->seg_head->next;
732 free (free_it);
733 }
734 while (cache->seg_head);
735
736 /* free the hash and clear the structure. */
737 free (cache->hash_tab);
738 memset (cache, '\0', sizeof (struct strcache2));
739}
740
741/* Print statistics a string cache. */
742void
743strcache2_print_stats (struct strcache2 *cache, const char *prefix)
744{
745 unsigned int seg_count = 0;
746 unsigned long seg_total_bytes = 0;
747 unsigned long seg_avg_bytes;
748 unsigned long seg_avail_bytes = 0;
749 unsigned long seg_max_bytes = 0;
750 struct strcache2_seg *seg;
751 unsigned long str_total_len = 0;
752 unsigned int str_avg_len;
753 unsigned int str_min_len = ~0U;
754 unsigned int str_max_len = 0;
755 unsigned int idx;
756 unsigned int rehashes;
757
758 printf (_("\n%s strcache2: %s\n"), prefix, cache->name);
759
760 /* Segment statistics. */
761 for (seg = cache->seg_head; seg; seg = seg->next)
762 {
763 seg_count++;
764 seg_total_bytes += seg->size;
765 seg_avail_bytes += seg->avail;
766 if (seg->size > seg_max_bytes)
767 seg_max_bytes = seg->size;
768 }
769 seg_avg_bytes = seg_total_bytes / seg_count;
770 printf (_("%s %u segments: total = %lu / max = %lu / avg = %lu / def = %u avail = %lu\n"),
771 prefix, seg_count, seg_total_bytes, seg_max_bytes, seg_avg_bytes,
772 cache->def_seg_size, seg_avail_bytes);
773
774 /* String statistics. */
775 idx = cache->hash_size;
776 while (idx-- > 0)
777 {
778 struct strcache2_entry const *entry = cache->hash_tab[idx];
779 if (entry)
780 {
781 unsigned int length = entry->length;
782 str_total_len += length;
783 if (length > str_max_len)
784 str_max_len = length;
785 if (length < str_min_len)
786 str_min_len = length;
787 }
788 }
789 str_avg_len = cache->count ? str_total_len / cache->count : 0;
790 printf (_("%s %u strings: total len = %lu / max = %u / avg = %u / min = %u\n"),
791 prefix, cache->count, str_total_len, str_max_len, str_avg_len, str_min_len);
792
793 /* Hash statistics. */
794 idx = cache->init_size;
795 rehashes = 0;
796 while (idx < cache->hash_size)
797 {
798 idx *= 2;
799 rehashes++;
800 }
801
802 printf (_("%s hash size = %u mask = %#x rehashed %u times lookups = %lu\n"),
803 prefix, cache->hash_size, cache->hash_mask, rehashes, cache->lookup_count);
804 printf (_("%s hash collisions 1st = %lu (%u%%) 2nd = %lu (%u%%) 3rd = %lu (%u%%)\n"),
805 prefix,
806 cache->collision_1st_count, (unsigned int)((float)cache->collision_1st_count * 100 / cache->lookup_count),
807 cache->collision_2nd_count, (unsigned int)((float)cache->collision_2nd_count * 100 / cache->lookup_count),
808 cache->collision_3rd_count, (unsigned int)((float)cache->collision_3rd_count * 100 / cache->lookup_count));
809}
810
811/* Print statistics for all string caches. */
812void
813strcache2_print_stats_all (const char *prefix)
814{
815 struct strcache2 *cur;
816 for (cur = strcache_head; cur; cur = cur->next)
817 strcache2_print_stats (cur, prefix);
818}
819
Note: See TracBrowser for help on using the repository browser.