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

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

kmk: strcache2 - some alignment fixes.
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 29.2 KB
Line 
1/* $Id: strcache2.c 1899 2008-10-21 01:51: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
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 size_t off;
77
78 size = cache->def_seg_size;
79 if (size < (size_t)minlen + sizeof (struct strcache2_seg) + STRCACHE2_ENTRY_ALIGNMENT)
80 {
81 size = (size_t)minlen * 2;
82 size = (size + 0xfff) & ~(size_t)0xfff;
83 }
84
85 seg = xmalloc (size);
86 seg->start = (char *)(seg + 1);
87 seg->size = size - sizeof (struct strcache2_seg);
88 off = (size_t)seg->start & (STRCACHE2_ENTRY_ALIGNMENT - 1);
89 if (off)
90 {
91 seg->start += off;
92 seg->size -= off;
93 }
94 assert (seg->size > minlen);
95 seg->cursor = seg->start;
96 seg->avail = seg->size;
97
98 seg->next = cache->seg_head;
99 cache->seg_head = seg;
100
101 return seg;
102}
103
104MY_INLINE unsigned int
105strcache2_case_sensitive_hash_1 (const char *str, unsigned int len)
106{
107 unsigned int hash = 0;
108 if (MY_PREDICT_TRUE(len >= 2))
109 {
110 unsigned int ch0 = *str++;
111 hash = 0;
112 len--;
113 while (len >= 2)
114 {
115 unsigned int ch1 = *str++;
116 hash += ch0 << (ch1 & 0xf);
117
118 ch0 = *str++;
119 hash += ch1 << (ch0 & 0xf);
120
121 len -= 2;
122 }
123 if (len == 1)
124 {
125 unsigned ch1 = *str;
126 hash += ch0 << (ch1 & 0xf);
127
128 hash += ch1;
129 }
130 else
131 hash += ch0;
132 }
133 else if (len)
134 {
135 hash = *str;
136 hash += hash << (hash & 0xf);
137 }
138 else
139 hash = 0;
140 return hash;
141}
142
143MY_INLINE unsigned int
144strcache2_case_sensitive_hash_2 (const char *str, unsigned int len)
145{
146 unsigned int hash = 0;
147 if (MY_PREDICT_TRUE(len >= 2))
148 {
149 unsigned int ch0 = *str++;
150 hash = 0;
151 len--;
152 while (len >= 2)
153 {
154 unsigned int ch1 = *str++;
155 hash += ch0 << (ch1 & 0x7);
156
157 ch0 = *str++;
158 hash += ch1 << (ch0 & 0x7);
159
160 len -= 2;
161 }
162 if (len == 1)
163 {
164 unsigned ch1 = *str;
165 hash += ch0 << (ch1 & 0x7);
166
167 hash += ch1;
168 }
169 else
170 hash += ch0;
171 }
172 else if (len)
173 {
174 hash = *str;
175 hash += hash << (hash & 0x7);
176 }
177 else
178 hash = 1;
179 hash |= 1;
180 return hash;
181}
182
183MY_INLINE unsigned int
184strcache2_case_insensitive_hash_1 (const char *str, unsigned int len)
185{
186 unsigned int hash = 0;
187 if (MY_PREDICT_TRUE(len >= 2))
188 {
189 unsigned int ch0 = *str++;
190 ch0 = tolower (ch0);
191 hash = 0;
192 len--;
193 while (len >= 2)
194 {
195 unsigned int ch1 = *str++;
196 ch1 = tolower (ch1);
197 hash += ch0 << (ch1 & 0xf);
198
199 ch0 = *str++;
200 ch0 = tolower (ch0);
201 hash += ch1 << (ch0 & 0xf);
202
203 len -= 2;
204 }
205 if (len == 1)
206 {
207 unsigned ch1 = *str;
208 ch1 = tolower (ch1);
209 hash += ch0 << (ch1 & 0xf);
210
211 hash += ch1;
212 }
213 else
214 hash += ch0;
215 }
216 else if (len)
217 {
218 hash = *str;
219 hash += hash << (hash & 0xf);
220 }
221 else
222 hash = 0;
223 return hash;
224}
225
226MY_INLINE unsigned int
227strcache2_case_insensitive_hash_2 (const char *str, unsigned int len)
228{
229 unsigned int hash = 0;
230 if (MY_PREDICT_TRUE(len >= 2))
231 {
232 unsigned int ch0 = *str++;
233 ch0 = tolower (ch0);
234 hash = 0;
235 len--;
236 while (len >= 2)
237 {
238 unsigned int ch1 = *str++;
239 ch1 = tolower (ch1);
240 hash += ch0 << (ch1 & 0x7);
241
242 ch0 = *str++;
243 ch0 = tolower (ch0);
244 hash += ch1 << (ch0 & 0x7);
245
246 len -= 2;
247 }
248 if (len == 1)
249 {
250 unsigned ch1 = *str;
251 ch1 = tolower (ch1);
252 hash += ch0 << (ch1 & 0x7);
253
254 hash += ch1;
255 }
256 else
257 hash += ch0;
258 }
259 else if (len)
260 {
261 hash = *str;
262 hash += hash << (hash & 0x7);
263 }
264 else
265 hash = 1;
266 hash |= 1;
267 return hash;
268}
269
270#if 0 /* FIXME: Use this (salvaged from variable.c) */
271
272MY_INLINE int
273variable_hash_cmp_2_memcmp (const char *xs, const char *ys, unsigned int length)
274{
275 /* short string compare - ~50% of the kBuild calls. */
276 assert ( !((size_t)ys & 3) );
277 if (!((size_t)xs & 3))
278 {
279 /* aligned */
280 int result;
281 switch (length)
282 {
283 case 8:
284 result = *(int32_t*)(xs + 4) - *(int32_t*)(ys + 4);
285 result |= *(int32_t*)xs - *(int32_t*)ys;
286 return result;
287 case 7:
288 result = xs[6] - ys[6];
289 result |= xs[5] - ys[5];
290 result |= xs[4] - ys[4];
291 result |= *(int32_t*)xs - *(int32_t*)ys;
292 return result;
293 case 6:
294 result = xs[5] - ys[5];
295 result |= xs[4] - ys[4];
296 result |= *(int32_t*)xs - *(int32_t*)ys;
297 return result;
298 case 5:
299 result = xs[4] - ys[4];
300 result |= *(int32_t*)xs - *(int32_t*)ys;
301 return result;
302 case 4:
303 return *(int32_t*)xs - *(int32_t*)ys;
304 case 3:
305 result = xs[2] - ys[2];
306 result |= xs[1] - ys[1];
307 result |= xs[0] - ys[0];
308 return result;
309 case 2:
310 result = xs[1] - ys[1];
311 result |= xs[0] - ys[0];
312 return result;
313 case 1:
314 return *xs - *ys;
315 case 0:
316 return 0;
317 }
318 }
319 else
320 {
321 /* unaligned */
322 int result = 0;
323 switch (length)
324 {
325 case 8: result |= xs[7] - ys[7];
326 case 7: result |= xs[6] - ys[6];
327 case 6: result |= xs[5] - ys[5];
328 case 5: result |= xs[4] - ys[4];
329 case 4: result |= xs[3] - ys[3];
330 case 3: result |= xs[2] - ys[2];
331 case 2: result |= xs[1] - ys[1];
332 case 1: result |= xs[0] - ys[0];
333 case 0:
334 return result;
335 }
336 }
337
338 /* memcmp for longer strings */
339# ifdef __GNUC__
340 return __builtin_memcmp (xs, ys, length);
341# else
342 return memcmp (xs, ys, length);
343# endif
344}
345
346MY_INLINE int
347variable_hash_cmp_2_inlined (const char *xs, const char *ys, unsigned int length)
348{
349#ifndef ELECTRIC_HEAP
350 assert ( !((size_t)ys & 3) );
351#endif
352 if (!((size_t)xs & 3))
353 {
354 int result;
355 /* aligned */
356 while (length >= 8)
357 {
358 result = *(int32_t*)xs - *(int32_t*)ys;
359 result |= *(int32_t*)(xs + 4) - *(int32_t*)(ys + 4);
360 if (MY_PREDICT_FALSE(result))
361 return result;
362 xs += 8;
363 ys += 8;
364 length -= 8;
365 }
366 switch (length)
367 {
368 case 7:
369 result = *(int32_t*)xs - *(int32_t*)ys;
370 result |= xs[6] - ys[6];
371 result |= xs[5] - ys[5];
372 result |= xs[4] - ys[4];
373 return result;
374 case 6:
375 result = *(int32_t*)xs - *(int32_t*)ys;
376 result |= xs[5] - ys[5];
377 result |= xs[4] - ys[4];
378 return result;
379 case 5:
380 result = *(int32_t*)xs - *(int32_t*)ys;
381 result |= xs[4] - ys[4];
382 return result;
383 case 4:
384 return *(int32_t*)xs - *(int32_t*)ys;
385 case 3:
386 result = xs[2] - ys[2];
387 result |= xs[1] - ys[1];
388 result |= xs[0] - ys[0];
389 return result;
390 case 2:
391 result = xs[1] - ys[1];
392 result |= xs[0] - ys[0];
393 return result;
394 case 1:
395 return *xs - *ys;
396 default:
397 case 0:
398 return 0;
399 }
400 }
401 else
402 {
403 /* unaligned */
404 int result;
405 while (length >= 8)
406 {
407#if defined(__i386__) || defined(__x86_64__)
408 result = ( ((int32_t)xs[3] << 24)
409 | ((int32_t)xs[2] << 16)
410 | ((int32_t)xs[1] << 8)
411 | xs[0] )
412 - *(int32_t*)ys;
413 result |= ( ((int32_t)xs[7] << 24)
414 | ((int32_t)xs[6] << 16)
415 | ((int32_t)xs[5] << 8)
416 | xs[4] )
417 - *(int32_t*)(ys + 4);
418#else
419 result = xs[3] - ys[3];
420 result |= xs[2] - ys[2];
421 result |= xs[1] - ys[1];
422 result |= xs[0] - ys[0];
423 result |= xs[7] - ys[7];
424 result |= xs[6] - ys[6];
425 result |= xs[5] - ys[5];
426 result |= xs[4] - ys[4];
427#endif
428 if (MY_PREDICT_FALSE(result))
429 return result;
430 xs += 8;
431 ys += 8;
432 length -= 8;
433 }
434 result = 0;
435 switch (length)
436 {
437 case 7: result |= xs[6] - ys[6];
438 case 6: result |= xs[5] - ys[5];
439 case 5: result |= xs[4] - ys[4];
440 case 4: result |= xs[3] - ys[3];
441 case 3: result |= xs[2] - ys[2];
442 case 2: result |= xs[1] - ys[1];
443 case 1: result |= xs[0] - ys[0];
444 return result;
445 default:
446 case 0:
447 return 0;
448 }
449 }
450}
451
452#endif
453
454MY_INLINE int
455strcache2_is_equal (struct strcache2 *cache, struct strcache2_entry const *entry,
456 const char *str, unsigned int length, unsigned int hash1)
457{
458 /* the simple stuff first. */
459 if ( entry == NULL
460 || entry->hash1 != hash1
461 || entry->length != length)
462 return 0;
463
464 return !cache->case_insensitive
465 ? memcmp (entry + 1, str, length) == 0
466#if defined(_MSC_VER) || defined(__OS2__)
467 : _memicmp (entry + 1, str, length) == 0
468#else
469 : strncasecmp ((const char *)(entry + 1), str, length) == 0
470#endif
471 ;
472}
473
474static void
475strcache2_rehash (struct strcache2 *cache)
476{
477 unsigned int src = cache->hash_size;
478 struct strcache2_entry **src_tab = cache->hash_tab;
479 struct strcache2_entry **dst_tab;
480 unsigned int hash_mask;
481
482 /* Allocate a new hash table twice the size of the current. */
483 cache->hash_size <<= 1;
484 cache->hash_mask <<= 1;
485 cache->hash_mask |= 1;
486 cache->rehash_count <<= 1;
487 cache->hash_tab = dst_tab = (struct strcache2_entry **)
488 xmalloc (cache->hash_size * sizeof (struct strcache2_entry *));
489 memset (dst_tab, '\0', cache->hash_size * sizeof (struct strcache2_entry *));
490
491 /* Copy the entries from the old to the new hash table. */
492 hash_mask = cache->hash_mask;
493 while (src-- > 0)
494 {
495 struct strcache2_entry *entry = src_tab[src];
496 if (entry)
497 {
498 unsigned int dst = entry->hash1 & hash_mask;
499 if (dst_tab[dst])
500 {
501 unsigned int hash2 = entry->hash2;
502 if (!hash2)
503 entry->hash2 = hash2 = cache->case_insensitive
504 ? strcache2_case_insensitive_hash_2 ((const char *)(entry + 1), entry->length)
505 : strcache2_case_sensitive_hash_2 ((const char *)(entry + 1), entry->length);
506 dst += hash2;
507 dst &= hash_mask;
508 while (dst_tab[dst])
509 {
510 dst += hash2;
511 dst &= hash_mask;
512 }
513 }
514
515 dst_tab[dst] = entry;
516 }
517 }
518
519 /* That's it, just free the old table and we're done. */
520 free (src_tab);
521}
522
523/* Internal worker that enters a new string into the cache. */
524static const char *
525strcache2_enter_string (struct strcache2 *cache, unsigned int idx,
526 const char *str, unsigned int length,
527 unsigned int hash1, unsigned hash2)
528{
529 struct strcache2_entry *entry;
530 struct strcache2_seg *seg;
531 unsigned int size;
532 char *str_copy;
533
534 /* Allocate space for the string. */
535
536 size = length + 1 + sizeof (struct strcache2_entry);
537 size = (size + STRCACHE2_ENTRY_ALIGNMENT - 1) & ~(STRCACHE2_ENTRY_ALIGNMENT - 1U);
538
539 seg = cache->seg_head;
540 if (MY_PREDICT_FALSE(seg->avail < size))
541 {
542 do
543 seg = seg->next;
544 while (seg && seg->avail < size);
545 if (!seg)
546 seg = strcache2_new_seg (cache, size);
547 }
548
549 entry = (struct strcache2_entry *) seg->cursor;
550 assert ((size_t)entry & (STRCACHE2_ENTRY_ALIGNMENT - 1));
551 seg->cursor += size;
552 seg->avail -= size;
553
554 /* Setup the entry, copy the string and insert it into the hash table. */
555
556 entry->user = NULL;
557 entry->length = length;
558 entry->hash1 = hash1;
559 entry->hash2 = hash2;
560 str_copy = (char *) memcpy (entry + 1, str, length);
561 str_copy[length] = '\0';
562
563 cache->hash_tab[idx] = entry;
564 cache->count++;
565 if (cache->count >= cache->rehash_count)
566 strcache2_rehash (cache);
567
568 return str_copy;
569}
570
571/* The public add string interface. */
572const char *
573strcache2_add (struct strcache2 *cache, const char *str, unsigned int length)
574{
575 struct strcache2_entry const *entry;
576 unsigned int hash2;
577 unsigned int hash1 = strcache2_case_sensitive_hash_1 (str, length);
578 unsigned int idx;
579
580 assert (!cache->case_insensitive);
581
582 cache->lookup_count++;
583
584 /* Lookup the entry in the hash table, hoping for an
585 early match. */
586 idx = hash1 & cache->hash_mask;
587 entry = cache->hash_tab[idx];
588 if (strcache2_is_equal (cache, entry, str, length, hash1))
589 return (const char *)(entry + 1);
590 if (!entry)
591 hash2 = 0;
592 else
593 {
594 cache->collision_1st_count++;
595
596 hash2 = strcache2_case_sensitive_hash_2 (str, length);
597 idx += hash2;
598 idx &= cache->hash_mask;
599 entry = cache->hash_tab[idx];
600 if (strcache2_is_equal (cache, entry, str, length, hash1))
601 return (const char *)(entry + 1);
602
603 if (entry)
604 {
605 cache->collision_2nd_count++;
606 do
607 {
608 idx += hash2;
609 idx &= cache->hash_mask;
610 entry = cache->hash_tab[idx];
611 cache->collision_3rd_count++;
612 if (strcache2_is_equal (cache, entry, str, length, hash1))
613 return (const char *)(entry + 1);
614 }
615 while (entry);
616 }
617 }
618
619 /* Not found, add it at IDX. */
620 return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
621}
622
623/* The public add string interface for prehashed strings.
624 Use strcache2_hash_str to calculate the hash of a string. */
625const char *
626strcache2_add_hashed (struct strcache2 *cache, const char *str, unsigned int length,
627 unsigned int hash1, unsigned int hash2)
628{
629 struct strcache2_entry const *entry;
630 unsigned int idx;
631#ifndef NDEBUG
632 unsigned correct_hash;
633
634 correct_hash = cache->case_insensitive
635 ? strcache2_case_insensitive_hash_1 (str, length)
636 : strcache2_case_sensitive_hash_1 (str, length);
637 MY_ASSERT_MSG (hash1 == correct_hash, ("%#x != %#x\n", hash1, correct_hash));
638 if (hash2)
639 {
640 correct_hash = cache->case_insensitive
641 ? strcache2_case_insensitive_hash_2 (str, length)
642 : strcache2_case_sensitive_hash_2 (str, length);
643 MY_ASSERT_MSG (hash2 == correct_hash, ("%#x != %#x\n", hash2, correct_hash));
644 }
645#endif /* NDEBUG */
646
647 cache->lookup_count++;
648
649 /* Lookup the entry in the hash table, hoping for an
650 early match. */
651 idx = hash1 & cache->hash_mask;
652 entry = cache->hash_tab[idx];
653 if (strcache2_is_equal (cache, entry, str, length, hash1))
654 return (const char *)(entry + 1);
655 if (entry)
656 {
657 cache->collision_1st_count++;
658
659 if (!hash2)
660 hash2 = cache->case_insensitive
661 ? strcache2_case_insensitive_hash_2 (str, length)
662 : strcache2_case_sensitive_hash_2 (str, length);
663 idx += hash2;
664 idx &= cache->hash_mask;
665 entry = cache->hash_tab[idx];
666 if (strcache2_is_equal (cache, entry, str, length, hash1))
667 return (const char *)(entry + 1);
668
669 if (entry)
670 {
671 cache->collision_2nd_count++;
672 do
673 {
674 idx += hash2;
675 idx &= cache->hash_mask;
676 entry = cache->hash_tab[idx];
677 cache->collision_3rd_count++;
678 if (strcache2_is_equal (cache, entry, str, length, hash1))
679 return (const char *)(entry + 1);
680 }
681 while (entry);
682 }
683 }
684
685 /* Not found, add it at IDX. */
686 return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
687}
688
689/* The public lookup string interface. */
690const char *
691strcache2_lookup (struct strcache2 *cache, const char *str, unsigned int length)
692{
693 struct strcache2_entry const *entry;
694 unsigned int hash2;
695 unsigned int hash1 = strcache2_case_sensitive_hash_1 (str, length);
696 unsigned int idx;
697
698 assert (!cache->case_insensitive);
699
700 cache->lookup_count++;
701
702 /* Lookup the entry in the hash table, hoping for an
703 early match. */
704 idx = hash1 & cache->hash_mask;
705 entry = cache->hash_tab[idx];
706 if (strcache2_is_equal (cache, entry, str, length, hash1))
707 return (const char *)(entry + 1);
708 if (!entry)
709 hash2 = 0;
710 else
711 {
712 cache->collision_1st_count++;
713
714 hash2 = strcache2_case_sensitive_hash_2 (str, length);
715 idx += hash2;
716 idx &= cache->hash_mask;
717 entry = cache->hash_tab[idx];
718 if (strcache2_is_equal (cache, entry, str, length, hash1))
719 return (const char *)(entry + 1);
720
721 if (entry)
722 {
723 cache->collision_2nd_count++;
724 do
725 {
726 idx += hash2;
727 idx &= cache->hash_mask;
728 entry = cache->hash_tab[idx];
729 cache->collision_3rd_count++;
730 if (strcache2_is_equal (cache, entry, str, length, hash1))
731 return (const char *)(entry + 1);
732 }
733 while (entry);
734 }
735 }
736
737 /* Not found. */
738 return NULL;
739}
740
741#if defined(HAVE_CASE_INSENSITIVE_FS)
742
743/* The public add string interface for case insensitive strings. */
744const char *
745strcache2_iadd (struct strcache2 *cache, const char *str, unsigned int length)
746{
747 struct strcache2_entry const *entry;
748 unsigned int hash2;
749 unsigned int hash1 = strcache2_case_insensitive_hash_1 (str, length);
750 unsigned int idx;
751
752 assert (cache->case_insensitive);
753 cache->lookup_count++;
754
755 /* Lookup the entry in the hash table, hoping for an
756 early match. */
757 idx = hash1 & cache->hash_mask;
758 entry = cache->hash_tab[idx];
759 if (strcache2_is_equal (cache, entry, str, length, hash1))
760 return (const char *)(entry + 1);
761 if (!entry)
762 hash2 = 0;
763 else
764 {
765 cache->collision_1st_count++;
766
767 hash2 = strcache2_case_insensitive_hash_2 (str, length);
768 idx += hash2;
769 idx &= cache->hash_mask;
770 entry = cache->hash_tab[idx];
771 if (strcache2_is_equal (cache, entry, str, length, hash1))
772 return (const char *)(entry + 1);
773
774 if (entry)
775 {
776 cache->collision_2nd_count++;
777 do
778 {
779 idx += hash2;
780 idx &= cache->hash_mask;
781 entry = cache->hash_tab[idx];
782 cache->collision_3rd_count++;
783 if (strcache2_is_equal (cache, entry, str, length, hash1))
784 return (const char *)(entry + 1);
785 }
786 while (entry);
787 }
788 }
789
790 /* Not found, add it at IDX. */
791 return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
792}
793
794/* strcache_ilookup later */
795
796#endif /* HAVE_CASE_INSENSITIVE_FS */
797
798/* Is the given string cached? returns 1 if it is, 0 if it isn't. */
799int
800strcache2_is_cached (struct strcache2 *cache, const char *str)
801{
802 /* Check mandatory alignment first. */
803 if (!((size_t)str & (sizeof (void *) - 1)))
804 {
805 /* Check the segment list and consider the question answered if the
806 string is within one of them. (Could check it more thoroughly...) */
807 struct strcache2_seg const *seg;
808 for (seg = cache->seg_head; seg; seg = seg->next)
809 if ((size_t)(str - seg->start) < seg->size)
810 return 1;
811 }
812
813 return 0;
814}
815
816
817/* Verify the integrity of the specified string, returning 0 if OK. */
818int
819strcache2_verify_entry (struct strcache2 *cache, const char *str)
820{
821 struct strcache2_entry const *entry;
822 unsigned hash;
823 const char *end;
824
825 if ((size_t)str & (sizeof (void *) - 1))
826 {
827 fprintf (stderr,
828 "strcache2[%s]: missaligned string %p\nstring: %s\n",
829 cache->name, (void *)str, str);
830 return -1;
831 }
832
833 entry = (struct strcache2_entry const *)str - 1;
834 end = memchr (str, '\0', entry->length);
835 if ((size_t)(end - str) == entry->length)
836 {
837 fprintf (stderr,
838 "strcache2[%s]: corrupt entry %p, length: %lu, expected %u;\nstring: %s\n",
839 cache->name, (void *)entry, (unsigned long)(end - str), entry->length, str);
840 return -1;
841 }
842
843 hash = cache->case_insensitive
844 ? strcache2_case_insensitive_hash_1 (str, entry->length)
845 : strcache2_case_sensitive_hash_1 (str, entry->length);
846 if (hash != entry->hash1)
847 {
848 fprintf (stderr,
849 "strcache2[%s]: corrupt entry %p, hash#1: %x, expected %x;\nstring: %s\n",
850 cache->name, (void *)entry, hash, entry->hash1, str);
851 return -1;
852 }
853
854 if (entry->hash2)
855 {
856 hash = cache->case_insensitive
857 ? strcache2_case_insensitive_hash_2 (str, entry->length)
858 : strcache2_case_sensitive_hash_2 (str, entry->length);
859 if (hash != entry->hash2)
860 {
861 fprintf (stderr,
862 "strcache2[%s]: corrupt entry %p, hash#2: %x, expected %x;\nstring: %s\n",
863 cache->name, (void *)entry, hash, entry->hash2, str);
864 return -1;
865 }
866 }
867
868 return 0;
869}
870
871/* Fallback for calculating and returning the 2nd hash. */
872unsigned int
873strcache2_get_hash2_fallback (struct strcache2 *cache, const char *str)
874{
875 struct strcache2_entry *entry = (struct strcache2_entry *) str - 1;
876 unsigned hash2 = cache->case_insensitive
877 ? strcache2_case_insensitive_hash_2 (str, entry->length)
878 : strcache2_case_sensitive_hash_2 (str, entry->length);
879 entry->hash2 = hash2;
880 return hash2;
881}
882
883/* Calculates the case sensitive hash values of the string.
884 The first hash is returned, the other is put at HASH2P. */
885unsigned int strcache2_hash_str (const char *str, unsigned int length, unsigned int *hash2p)
886{
887 *hash2p = strcache2_case_sensitive_hash_2 (str, length);
888 return strcache2_case_sensitive_hash_1 (str, length);
889}
890
891/* Calculates the case insensitive hash values of the string.
892 The first hash is returned, the other is put at HASH2P. */
893unsigned int strcache2_hash_istr (const char *str, unsigned int length, unsigned int *hash2p)
894{
895 *hash2p = strcache2_case_insensitive_hash_2 (str, length);
896 return strcache2_case_insensitive_hash_1 (str, length);
897}
898
899
900
901/* Initalizes a new cache. */
902void
903strcache2_init (struct strcache2 *cache, const char *name, unsigned int size,
904 unsigned int def_seg_size, int case_insensitive, int thread_safe)
905{
906 unsigned hash_shift;
907 assert (!thread_safe);
908
909 /* calc the size as a power of two */
910 if (!size)
911 hash_shift = STRCACHE2_HASH_SHIFT;
912 else
913 {
914 assert (size <= (~0U / 2 + 1));
915 for (hash_shift = 8; (1U << hash_shift) < size; hash_shift++)
916 /* nothing */;
917 }
918
919 /* adjust the default segment size */
920 if (!def_seg_size)
921 def_seg_size = STRCACHE2_SEG_SIZE;
922 else if (def_seg_size < sizeof (struct strcache2_seg) * 10)
923 def_seg_size = sizeof (struct strcache2_seg) * 10;
924 else if ((def_seg_size & 0xfff) < 0xf00)
925 def_seg_size = ((def_seg_size + 0xfff) & ~0xfffU);
926
927
928 /* init the structure. */
929 cache->case_insensitive = case_insensitive;
930 cache->hash_mask = (1U << hash_shift) - 1U;
931 cache->count = 0;
932 cache->lookup_count = 0;
933 cache->collision_1st_count = 0;
934 cache->collision_2nd_count = 0;
935 cache->collision_3rd_count = 0;
936 cache->rehash_count = (1U << hash_shift) / 4 * 3; /* rehash at 75% */
937 cache->init_size = 1U << hash_shift;
938 cache->hash_size = 1U << hash_shift;
939 cache->def_seg_size = def_seg_size;
940 cache->lock = NULL;
941 cache->name = name;
942
943 /* allocate the hash table and first segment. */
944 cache->hash_tab = (struct strcache2_entry **)
945 xmalloc (cache->init_size * sizeof (struct strcache2_entry *));
946 memset (cache->hash_tab, '\0', cache->init_size * sizeof (struct strcache2_entry *));
947 strcache2_new_seg (cache, 0);
948
949 /* link it */
950 cache->next = strcache_head;
951 strcache_head = cache;
952}
953
954
955/* Terminates a string cache, freeing all memory and other
956 associated resources. */
957void
958strcache2_term (struct strcache2 *cache)
959{
960 /* unlink it */
961 if (strcache_head == cache)
962 strcache_head = cache->next;
963 else
964 {
965 struct strcache2 *prev = strcache_head;
966 while (prev->next != cache)
967 prev = prev->next;
968 assert (prev);
969 prev->next = cache->next;
970 }
971
972 /* free the memory segments */
973 do
974 {
975 void *free_it = cache->seg_head;
976 cache->seg_head = cache->seg_head->next;
977 free (free_it);
978 }
979 while (cache->seg_head);
980
981 /* free the hash and clear the structure. */
982 free (cache->hash_tab);
983 memset (cache, '\0', sizeof (struct strcache2));
984}
985
986/* Print statistics a string cache. */
987void
988strcache2_print_stats (struct strcache2 *cache, const char *prefix)
989{
990 unsigned int seg_count = 0;
991 unsigned long seg_total_bytes = 0;
992 unsigned long seg_avg_bytes;
993 unsigned long seg_avail_bytes = 0;
994 unsigned long seg_max_bytes = 0;
995 struct strcache2_seg *seg;
996 unsigned long str_total_len = 0;
997 unsigned int str_avg_len;
998 unsigned int str_min_len = ~0U;
999 unsigned int str_max_len = 0;
1000 unsigned int idx;
1001 unsigned int rehashes;
1002
1003 printf (_("\n%s strcache2: %s\n"), prefix, cache->name);
1004
1005 /* Segment statistics. */
1006 for (seg = cache->seg_head; seg; seg = seg->next)
1007 {
1008 seg_count++;
1009 seg_total_bytes += seg->size;
1010 seg_avail_bytes += seg->avail;
1011 if (seg->size > seg_max_bytes)
1012 seg_max_bytes = seg->size;
1013 }
1014 seg_avg_bytes = seg_total_bytes / seg_count;
1015 printf (_("%s %u segments: total = %lu / max = %lu / avg = %lu / def = %u avail = %lu\n"),
1016 prefix, seg_count, seg_total_bytes, seg_max_bytes, seg_avg_bytes,
1017 cache->def_seg_size, seg_avail_bytes);
1018
1019 /* String statistics. */
1020 idx = cache->hash_size;
1021 while (idx-- > 0)
1022 {
1023 struct strcache2_entry const *entry = cache->hash_tab[idx];
1024 if (entry)
1025 {
1026 unsigned int length = entry->length;
1027 str_total_len += length;
1028 if (length > str_max_len)
1029 str_max_len = length;
1030 if (length < str_min_len)
1031 str_min_len = length;
1032 }
1033 }
1034 str_avg_len = cache->count ? str_total_len / cache->count : 0;
1035 printf (_("%s %u strings: total len = %lu / max = %u / avg = %u / min = %u\n"),
1036 prefix, cache->count, str_total_len, str_max_len, str_avg_len, str_min_len);
1037
1038 /* Hash statistics. */
1039 idx = cache->init_size;
1040 rehashes = 0;
1041 while (idx < cache->hash_size)
1042 {
1043 idx *= 2;
1044 rehashes++;
1045 }
1046
1047 printf (_("%s hash size = %u mask = %#x rehashed %u times lookups = %lu\n"),
1048 prefix, cache->hash_size, cache->hash_mask, rehashes, cache->lookup_count);
1049 printf (_("%s hash collisions 1st = %lu (%u%%) 2nd = %lu (%u%%) 3rd = %lu (%u%%)\n"),
1050 prefix,
1051 cache->collision_1st_count, (unsigned int)((float)cache->collision_1st_count * 100 / cache->lookup_count),
1052 cache->collision_2nd_count, (unsigned int)((float)cache->collision_2nd_count * 100 / cache->lookup_count),
1053 cache->collision_3rd_count, (unsigned int)((float)cache->collision_3rd_count * 100 / cache->lookup_count));
1054}
1055
1056/* Print statistics for all string caches. */
1057void
1058strcache2_print_stats_all (const char *prefix)
1059{
1060 struct strcache2 *cur;
1061 for (cur = strcache_head; cur; cur = cur->next)
1062 strcache2_print_stats (cur, prefix);
1063}
1064
Note: See TracBrowser for help on using the repository browser.