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

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

strcache2: some cleanup.
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 32.8 KB
Line 
1/* $Id: strcache2.c 1903 2008-10-21 04:25:19Z 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#ifdef _MSC_VER
271 typedef unsigned int int32_t;
272#else
273# include <stdint.h>
274#endif
275
276MY_INLINE int
277strcache2_memcmp_inline_short (const char *xs, const char *ys, unsigned int length)
278{
279 /* short string compare - ~50% of the kBuild calls. */
280 assert ( !((size_t)ys & 3) );
281 if (!((size_t)xs & 3))
282 {
283 /* aligned */
284 int result;
285 switch (length)
286 {
287 case 8:
288 result = *(int32_t*)(xs + 4) - *(int32_t*)(ys + 4);
289 result |= *(int32_t*)xs - *(int32_t*)ys;
290 return result;
291 case 7:
292 result = xs[6] - ys[6];
293 result |= xs[5] - ys[5];
294 result |= xs[4] - ys[4];
295 result |= *(int32_t*)xs - *(int32_t*)ys;
296 return result;
297 case 6:
298 result = xs[5] - ys[5];
299 result |= xs[4] - ys[4];
300 result |= *(int32_t*)xs - *(int32_t*)ys;
301 return result;
302 case 5:
303 result = xs[4] - ys[4];
304 result |= *(int32_t*)xs - *(int32_t*)ys;
305 return result;
306 case 4:
307 return *(int32_t*)xs - *(int32_t*)ys;
308 case 3:
309 result = xs[2] - ys[2];
310 result |= xs[1] - ys[1];
311 result |= xs[0] - ys[0];
312 return result;
313 case 2:
314 result = xs[1] - ys[1];
315 result |= xs[0] - ys[0];
316 return result;
317 case 1:
318 return *xs - *ys;
319 case 0:
320 return 0;
321 }
322 }
323 else
324 {
325 /* unaligned */
326 int result = 0;
327 switch (length)
328 {
329 case 8: result |= xs[7] - ys[7];
330 case 7: result |= xs[6] - ys[6];
331 case 6: result |= xs[5] - ys[5];
332 case 5: result |= xs[4] - ys[4];
333 case 4: result |= xs[3] - ys[3];
334 case 3: result |= xs[2] - ys[2];
335 case 2: result |= xs[1] - ys[1];
336 case 1: result |= xs[0] - ys[0];
337 case 0:
338 return result;
339 }
340 }
341
342 /* memcmp for longer strings */
343# ifdef __GNUC__
344 return __builtin_memcmp (xs, ys, length);
345# else
346 return memcmp (xs, ys, length);
347# endif
348}
349
350MY_INLINE int
351strcache2_memcmp_inlined (const char *xs, const char *ys, unsigned int length)
352{
353#ifndef ELECTRIC_HEAP
354 assert ( !((size_t)ys & 3) );
355#endif
356 if (!((size_t)xs & 3))
357 {
358 int result;
359 /* aligned */
360 while (length >= 8)
361 {
362 result = *(int32_t*)xs - *(int32_t*)ys;
363 result |= *(int32_t*)(xs + 4) - *(int32_t*)(ys + 4);
364 if (MY_PREDICT_FALSE(result))
365 return result;
366 xs += 8;
367 ys += 8;
368 length -= 8;
369 }
370 switch (length)
371 {
372 case 7:
373 result = *(int32_t*)xs - *(int32_t*)ys;
374 result |= xs[6] - ys[6];
375 result |= xs[5] - ys[5];
376 result |= xs[4] - ys[4];
377 return result;
378 case 6:
379 result = *(int32_t*)xs - *(int32_t*)ys;
380 result |= xs[5] - ys[5];
381 result |= xs[4] - ys[4];
382 return result;
383 case 5:
384 result = *(int32_t*)xs - *(int32_t*)ys;
385 result |= xs[4] - ys[4];
386 return result;
387 case 4:
388 return *(int32_t*)xs - *(int32_t*)ys;
389 case 3:
390 result = xs[2] - ys[2];
391 result |= xs[1] - ys[1];
392 result |= xs[0] - ys[0];
393 return result;
394 case 2:
395 result = xs[1] - ys[1];
396 result |= xs[0] - ys[0];
397 return result;
398 case 1:
399 return *xs - *ys;
400 default:
401 case 0:
402 return 0;
403 }
404 }
405 else
406 {
407 /* unaligned */
408 int result;
409 while (length >= 8)
410 {
411#if defined(__i386__) || defined(__x86_64__)
412 result = ( ((int32_t)xs[3] << 24)
413 | ((int32_t)xs[2] << 16)
414 | ((int32_t)xs[1] << 8)
415 | xs[0] )
416 - *(int32_t*)ys;
417 result |= ( ((int32_t)xs[7] << 24)
418 | ((int32_t)xs[6] << 16)
419 | ((int32_t)xs[5] << 8)
420 | xs[4] )
421 - *(int32_t*)(ys + 4);
422#else
423 result = xs[3] - ys[3];
424 result |= xs[2] - ys[2];
425 result |= xs[1] - ys[1];
426 result |= xs[0] - ys[0];
427 result |= xs[7] - ys[7];
428 result |= xs[6] - ys[6];
429 result |= xs[5] - ys[5];
430 result |= xs[4] - ys[4];
431#endif
432 if (MY_PREDICT_FALSE(result))
433 return result;
434 xs += 8;
435 ys += 8;
436 length -= 8;
437 }
438 result = 0;
439 switch (length)
440 {
441 case 7: result |= xs[6] - ys[6];
442 case 6: result |= xs[5] - ys[5];
443 case 5: result |= xs[4] - ys[4];
444 case 4: result |= xs[3] - ys[3];
445 case 3: result |= xs[2] - ys[2];
446 case 2: result |= xs[1] - ys[1];
447 case 1: result |= xs[0] - ys[0];
448 return result;
449 default:
450 case 0:
451 return 0;
452 }
453 }
454}
455
456MY_INLINE int
457strcache2_is_equal (struct strcache2 *cache, struct strcache2_entry const *entry,
458 const char *str, unsigned int length, unsigned int hash1)
459{
460 assert (!cache->case_insensitive);
461
462 /* the simple stuff first. */
463 if ( entry == NULL
464 || entry->hash1 != hash1
465 || entry->length != length)
466 return 0;
467
468#if 1
469 return memcmp (entry + 1, str, length) == 0;
470#elif 0
471 return strcache2_memcmp_inlined (entry + 1, str, length) == 0;
472#else
473 return strcache2_memcmp_inline_short (entry + 1, str, length) == 0;
474#endif
475}
476
477MY_INLINE int
478strcache2_is_iequal (struct strcache2 *cache, struct strcache2_entry const *entry,
479 const char *str, unsigned int length, unsigned int hash1)
480{
481 assert (cache->case_insensitive);
482
483 /* the simple stuff first. */
484 if ( entry == NULL
485 || entry->hash1 != hash1
486 || entry->length != length)
487 return 0;
488
489#if defined(_MSC_VER) || defined(__OS2__)
490 return _memicmp (entry + 1, str, length) == 0;
491#else
492 return strncasecmp ((const char *)(entry + 1), str, length) == 0;
493#endif
494}
495
496static void
497strcache2_rehash (struct strcache2 *cache)
498{
499 unsigned int src = cache->hash_size;
500 struct strcache2_entry **src_tab = cache->hash_tab;
501 struct strcache2_entry **dst_tab;
502 unsigned int hash_mask;
503
504 /* Allocate a new hash table twice the size of the current. */
505 cache->hash_size <<= 1;
506 cache->hash_mask <<= 1;
507 cache->hash_mask |= 1;
508 cache->rehash_count <<= 1;
509 cache->hash_tab = dst_tab = (struct strcache2_entry **)
510 xmalloc (cache->hash_size * sizeof (struct strcache2_entry *));
511 memset (dst_tab, '\0', cache->hash_size * sizeof (struct strcache2_entry *));
512
513 /* Copy the entries from the old to the new hash table. */
514 hash_mask = cache->hash_mask;
515 while (src-- > 0)
516 {
517 struct strcache2_entry *entry = src_tab[src];
518 if (entry)
519 {
520 unsigned int dst = entry->hash1 & hash_mask;
521 if (dst_tab[dst])
522 {
523 unsigned int hash2 = entry->hash2;
524 if (!hash2)
525 entry->hash2 = hash2 = cache->case_insensitive
526 ? strcache2_case_insensitive_hash_2 ((const char *)(entry + 1), entry->length)
527 : strcache2_case_sensitive_hash_2 ((const char *)(entry + 1), entry->length);
528 dst += hash2;
529 dst &= hash_mask;
530 while (dst_tab[dst])
531 {
532 dst += hash2;
533 dst &= hash_mask;
534 }
535 }
536
537 dst_tab[dst] = entry;
538 }
539 }
540
541 /* That's it, just free the old table and we're done. */
542 free (src_tab);
543}
544
545/* Internal worker that enters a new string into the cache. */
546static const char *
547strcache2_enter_string (struct strcache2 *cache, unsigned int idx,
548 const char *str, unsigned int length,
549 unsigned int hash1, unsigned hash2)
550{
551 struct strcache2_entry *entry;
552 struct strcache2_seg *seg;
553 unsigned int size;
554 char *str_copy;
555
556 /* Allocate space for the string. */
557
558 size = length + 1 + sizeof (struct strcache2_entry);
559 size = (size + STRCACHE2_ENTRY_ALIGNMENT - 1) & ~(STRCACHE2_ENTRY_ALIGNMENT - 1U);
560
561 seg = cache->seg_head;
562 if (MY_PREDICT_FALSE(seg->avail < size))
563 {
564 do
565 seg = seg->next;
566 while (seg && seg->avail < size);
567 if (!seg)
568 seg = strcache2_new_seg (cache, size);
569 }
570
571 entry = (struct strcache2_entry *) seg->cursor;
572 assert ((size_t)entry & (STRCACHE2_ENTRY_ALIGNMENT - 1));
573 seg->cursor += size;
574 seg->avail -= size;
575
576 /* Setup the entry, copy the string and insert it into the hash table. */
577
578 entry->user = NULL;
579 entry->length = length;
580 entry->hash1 = hash1;
581 entry->hash2 = hash2;
582 str_copy = (char *) memcpy (entry + 1, str, length);
583 str_copy[length] = '\0';
584
585 cache->hash_tab[idx] = entry;
586 cache->count++;
587 if (cache->count >= cache->rehash_count)
588 strcache2_rehash (cache);
589
590 return str_copy;
591}
592
593/* The public add string interface. */
594const char *
595strcache2_add (struct strcache2 *cache, const char *str, unsigned int length)
596{
597 struct strcache2_entry const *entry;
598 unsigned int hash2;
599 unsigned int hash1 = strcache2_case_sensitive_hash_1 (str, length);
600 unsigned int idx;
601
602 assert (!cache->case_insensitive);
603
604 cache->lookup_count++;
605
606 /* Lookup the entry in the hash table, hoping for an
607 early match. */
608 idx = hash1 & cache->hash_mask;
609 entry = cache->hash_tab[idx];
610 if (strcache2_is_equal (cache, entry, str, length, hash1))
611 return (const char *)(entry + 1);
612 if (!entry)
613 hash2 = 0;
614 else
615 {
616 cache->collision_1st_count++;
617
618 hash2 = strcache2_case_sensitive_hash_2 (str, length);
619 idx += hash2;
620 idx &= cache->hash_mask;
621 entry = cache->hash_tab[idx];
622 if (strcache2_is_equal (cache, entry, str, length, hash1))
623 return (const char *)(entry + 1);
624
625 if (entry)
626 {
627 cache->collision_2nd_count++;
628 do
629 {
630 idx += hash2;
631 idx &= cache->hash_mask;
632 entry = cache->hash_tab[idx];
633 cache->collision_3rd_count++;
634 if (strcache2_is_equal (cache, entry, str, length, hash1))
635 return (const char *)(entry + 1);
636 }
637 while (entry);
638 }
639 }
640
641 /* Not found, add it at IDX. */
642 return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
643}
644
645/* The public add string interface for prehashed strings.
646 Use strcache2_hash_str to calculate the hash of a string. */
647const char *
648strcache2_add_hashed (struct strcache2 *cache, const char *str, unsigned int length,
649 unsigned int hash1, unsigned int hash2)
650{
651 struct strcache2_entry const *entry;
652 unsigned int idx;
653#ifndef NDEBUG
654 unsigned correct_hash;
655
656 assert (!cache->case_insensitive);
657 correct_hash = strcache2_case_sensitive_hash_1 (str, length);
658 MY_ASSERT_MSG (hash1 == correct_hash, ("%#x != %#x\n", hash1, correct_hash));
659 if (hash2)
660 {
661 correct_hash = strcache2_case_sensitive_hash_2 (str, length);
662 MY_ASSERT_MSG (hash2 == correct_hash, ("%#x != %#x\n", hash2, correct_hash));
663 }
664#endif /* NDEBUG */
665
666 cache->lookup_count++;
667
668 /* Lookup the entry in the hash table, hoping for an
669 early match. */
670 idx = hash1 & cache->hash_mask;
671 entry = cache->hash_tab[idx];
672 if (strcache2_is_equal (cache, entry, str, length, hash1))
673 return (const char *)(entry + 1);
674 if (entry)
675 {
676 cache->collision_1st_count++;
677
678 if (!hash2)
679 hash2 = cache->case_insensitive
680 ? strcache2_case_insensitive_hash_2 (str, length)
681 : strcache2_case_sensitive_hash_2 (str, length);
682 idx += hash2;
683 idx &= cache->hash_mask;
684 entry = cache->hash_tab[idx];
685 if (strcache2_is_equal (cache, entry, str, length, hash1))
686 return (const char *)(entry + 1);
687
688 if (entry)
689 {
690 cache->collision_2nd_count++;
691 do
692 {
693 idx += hash2;
694 idx &= cache->hash_mask;
695 entry = cache->hash_tab[idx];
696 cache->collision_3rd_count++;
697 if (strcache2_is_equal (cache, entry, str, length, hash1))
698 return (const char *)(entry + 1);
699 }
700 while (entry);
701 }
702 }
703
704 /* Not found, add it at IDX. */
705 return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
706}
707
708/* The public lookup (case sensitive) string interface. */
709const char *
710strcache2_lookup (struct strcache2 *cache, const char *str, unsigned int length)
711{
712 struct strcache2_entry const *entry;
713 unsigned int hash2;
714 unsigned int hash1 = strcache2_case_sensitive_hash_1 (str, length);
715 unsigned int idx;
716
717 assert (!cache->case_insensitive);
718
719 cache->lookup_count++;
720
721 /* Lookup the entry in the hash table, hoping for an
722 early match. */
723 idx = hash1 & cache->hash_mask;
724 entry = cache->hash_tab[idx];
725 if (strcache2_is_equal (cache, entry, str, length, hash1))
726 return (const char *)(entry + 1);
727 if (!entry)
728 hash2 = 0;
729 else
730 {
731 cache->collision_1st_count++;
732
733 hash2 = strcache2_case_sensitive_hash_2 (str, length);
734 idx += hash2;
735 idx &= cache->hash_mask;
736 entry = cache->hash_tab[idx];
737 if (strcache2_is_equal (cache, entry, str, length, hash1))
738 return (const char *)(entry + 1);
739
740 if (entry)
741 {
742 cache->collision_2nd_count++;
743 do
744 {
745 idx += hash2;
746 idx &= cache->hash_mask;
747 entry = cache->hash_tab[idx];
748 cache->collision_3rd_count++;
749 if (strcache2_is_equal (cache, entry, str, length, hash1))
750 return (const char *)(entry + 1);
751 }
752 while (entry);
753 }
754 }
755
756 /* Not found. */
757 return NULL;
758}
759
760#if defined(HAVE_CASE_INSENSITIVE_FS)
761
762/* The public add string interface for case insensitive strings. */
763const char *
764strcache2_iadd (struct strcache2 *cache, const char *str, unsigned int length)
765{
766 struct strcache2_entry const *entry;
767 unsigned int hash2;
768 unsigned int hash1 = strcache2_case_insensitive_hash_1 (str, length);
769 unsigned int idx;
770
771 assert (cache->case_insensitive);
772 cache->lookup_count++;
773
774 /* Lookup the entry in the hash table, hoping for an
775 early match. */
776 idx = hash1 & cache->hash_mask;
777 entry = cache->hash_tab[idx];
778 if (strcache2_is_iequal (cache, entry, str, length, hash1))
779 return (const char *)(entry + 1);
780 if (!entry)
781 hash2 = 0;
782 else
783 {
784 cache->collision_1st_count++;
785
786 hash2 = strcache2_case_insensitive_hash_2 (str, length);
787 idx += hash2;
788 idx &= cache->hash_mask;
789 entry = cache->hash_tab[idx];
790 if (strcache2_is_iequal (cache, entry, str, length, hash1))
791 return (const char *)(entry + 1);
792
793 if (entry)
794 {
795 cache->collision_2nd_count++;
796 do
797 {
798 idx += hash2;
799 idx &= cache->hash_mask;
800 entry = cache->hash_tab[idx];
801 cache->collision_3rd_count++;
802 if (strcache2_is_iequal (cache, entry, str, length, hash1))
803 return (const char *)(entry + 1);
804 }
805 while (entry);
806 }
807 }
808
809 /* Not found, add it at IDX. */
810 return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
811}
812
813/* The public add string interface for prehashed case insensitive strings.
814 Use strcache2_hash_istr to calculate the hash of a string. */
815const char *
816strcache2_iadd_hashed (struct strcache2 *cache, const char *str, unsigned int length,
817 unsigned int hash1, unsigned int hash2)
818{
819 struct strcache2_entry const *entry;
820 unsigned int idx;
821#ifndef NDEBUG
822 unsigned correct_hash;
823
824 assert (cache->case_insensitive);
825 correct_hash = strcache2_case_insensitive_hash_1 (str, length);
826 MY_ASSERT_MSG (hash1 == correct_hash, ("%#x != %#x\n", hash1, correct_hash));
827 if (hash2)
828 {
829 correct_hash = strcache2_case_insensitive_hash_2 (str, length);
830 MY_ASSERT_MSG (hash2 == correct_hash, ("%#x != %#x\n", hash2, correct_hash));
831 }
832#endif /* NDEBUG */
833
834 cache->lookup_count++;
835
836 /* Lookup the entry in the hash table, hoping for an
837 early match. */
838 idx = hash1 & cache->hash_mask;
839 entry = cache->hash_tab[idx];
840 if (strcache2_is_iequal (cache, entry, str, length, hash1))
841 return (const char *)(entry + 1);
842 if (entry)
843 {
844 cache->collision_1st_count++;
845
846 if (!hash2)
847 hash2 = strcache2_case_insensitive_hash_2 (str, length);
848 idx += hash2;
849 idx &= cache->hash_mask;
850 entry = cache->hash_tab[idx];
851 if (strcache2_is_iequal (cache, entry, str, length, hash1))
852 return (const char *)(entry + 1);
853
854 if (entry)
855 {
856 cache->collision_2nd_count++;
857 do
858 {
859 idx += hash2;
860 idx &= cache->hash_mask;
861 entry = cache->hash_tab[idx];
862 cache->collision_3rd_count++;
863 if (strcache2_is_iequal (cache, entry, str, length, hash1))
864 return (const char *)(entry + 1);
865 }
866 while (entry);
867 }
868 }
869
870 /* Not found, add it at IDX. */
871 return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
872}
873
874/* The public lookup (case insensitive) string interface. */
875const char *
876strcache2_lookup (struct strcache2 *cache, const char *str, unsigned int length)
877{
878 struct strcache2_entry const *entry;
879 unsigned int hash2;
880 unsigned int hash1 = strcache2_case_insensitive_hash_1 (str, length);
881 unsigned int idx;
882
883 assert (cache->case_insensitive);
884
885 cache->lookup_count++;
886
887 /* Lookup the entry in the hash table, hoping for an
888 early match. */
889 idx = hash1 & cache->hash_mask;
890 entry = cache->hash_tab[idx];
891 if (strcache2_is_iequal (cache, entry, str, length, hash1))
892 return (const char *)(entry + 1);
893 if (!entry)
894 hash2 = 0;
895 else
896 {
897 cache->collision_1st_count++;
898
899 hash2 = strcache2_case_insensitive_hash_2 (str, length);
900 idx += hash2;
901 idx &= cache->hash_mask;
902 entry = cache->hash_tab[idx];
903 if (strcache2_is_iequal (cache, entry, str, length, hash1))
904 return (const char *)(entry + 1);
905
906 if (entry)
907 {
908 cache->collision_2nd_count++;
909 do
910 {
911 idx += hash2;
912 idx &= cache->hash_mask;
913 entry = cache->hash_tab[idx];
914 cache->collision_3rd_count++;
915 if (strcache2_is_iequal (cache, entry, str, length, hash1))
916 return (const char *)(entry + 1);
917 }
918 while (entry);
919 }
920 }
921
922 /* Not found. */
923 return NULL;
924}
925
926#endif /* HAVE_CASE_INSENSITIVE_FS */
927
928/* Is the given string cached? returns 1 if it is, 0 if it isn't. */
929int
930strcache2_is_cached (struct strcache2 *cache, const char *str)
931{
932 /* Check mandatory alignment first. */
933 if (!((size_t)str & (sizeof (void *) - 1)))
934 {
935 /* Check the segment list and consider the question answered if the
936 string is within one of them. (Could check it more thoroughly...) */
937 struct strcache2_seg const *seg;
938 for (seg = cache->seg_head; seg; seg = seg->next)
939 if ((size_t)(str - seg->start) < seg->size)
940 return 1;
941 }
942
943 return 0;
944}
945
946
947/* Verify the integrity of the specified string, returning 0 if OK. */
948int
949strcache2_verify_entry (struct strcache2 *cache, const char *str)
950{
951 struct strcache2_entry const *entry;
952 unsigned hash;
953 const char *end;
954
955 if ((size_t)str & (sizeof (void *) - 1))
956 {
957 fprintf (stderr,
958 "strcache2[%s]: missaligned string %p\nstring: %s\n",
959 cache->name, (void *)str, str);
960 return -1;
961 }
962
963 entry = (struct strcache2_entry const *)str - 1;
964 end = memchr (str, '\0', entry->length);
965 if ((size_t)(end - str) == entry->length)
966 {
967 fprintf (stderr,
968 "strcache2[%s]: corrupt entry %p, length: %lu, expected %u;\nstring: %s\n",
969 cache->name, (void *)entry, (unsigned long)(end - str), entry->length, str);
970 return -1;
971 }
972
973 hash = cache->case_insensitive
974 ? strcache2_case_insensitive_hash_1 (str, entry->length)
975 : strcache2_case_sensitive_hash_1 (str, entry->length);
976 if (hash != entry->hash1)
977 {
978 fprintf (stderr,
979 "strcache2[%s]: corrupt entry %p, hash#1: %x, expected %x;\nstring: %s\n",
980 cache->name, (void *)entry, hash, entry->hash1, str);
981 return -1;
982 }
983
984 if (entry->hash2)
985 {
986 hash = cache->case_insensitive
987 ? strcache2_case_insensitive_hash_2 (str, entry->length)
988 : strcache2_case_sensitive_hash_2 (str, entry->length);
989 if (hash != entry->hash2)
990 {
991 fprintf (stderr,
992 "strcache2[%s]: corrupt entry %p, hash#2: %x, expected %x;\nstring: %s\n",
993 cache->name, (void *)entry, hash, entry->hash2, str);
994 return -1;
995 }
996 }
997
998 return 0;
999}
1000
1001/* Fallback for calculating and returning the 2nd hash. */
1002unsigned int
1003strcache2_get_hash2_fallback (struct strcache2 *cache, const char *str)
1004{
1005 struct strcache2_entry *entry = (struct strcache2_entry *) str - 1;
1006 unsigned hash2 = cache->case_insensitive
1007 ? strcache2_case_insensitive_hash_2 (str, entry->length)
1008 : strcache2_case_sensitive_hash_2 (str, entry->length);
1009 entry->hash2 = hash2;
1010 return hash2;
1011}
1012
1013/* Calculates the case sensitive hash values of the string.
1014 The first hash is returned, the other is put at HASH2P. */
1015unsigned int strcache2_hash_str (const char *str, unsigned int length, unsigned int *hash2p)
1016{
1017 *hash2p = strcache2_case_sensitive_hash_2 (str, length);
1018 return strcache2_case_sensitive_hash_1 (str, length);
1019}
1020
1021/* Calculates the case insensitive hash values of the string.
1022 The first hash is returned, the other is put at HASH2P. */
1023unsigned int strcache2_hash_istr (const char *str, unsigned int length, unsigned int *hash2p)
1024{
1025 *hash2p = strcache2_case_insensitive_hash_2 (str, length);
1026 return strcache2_case_insensitive_hash_1 (str, length);
1027}
1028
1029
1030
1031/* Initalizes a new cache. */
1032void
1033strcache2_init (struct strcache2 *cache, const char *name, unsigned int size,
1034 unsigned int def_seg_size, int case_insensitive, int thread_safe)
1035{
1036 unsigned hash_shift;
1037 assert (!thread_safe);
1038
1039 /* calc the size as a power of two */
1040 if (!size)
1041 hash_shift = STRCACHE2_HASH_SHIFT;
1042 else
1043 {
1044 assert (size <= (~0U / 2 + 1));
1045 for (hash_shift = 8; (1U << hash_shift) < size; hash_shift++)
1046 /* nothing */;
1047 }
1048
1049 /* adjust the default segment size */
1050 if (!def_seg_size)
1051 def_seg_size = STRCACHE2_SEG_SIZE;
1052 else if (def_seg_size < sizeof (struct strcache2_seg) * 10)
1053 def_seg_size = sizeof (struct strcache2_seg) * 10;
1054 else if ((def_seg_size & 0xfff) < 0xf00)
1055 def_seg_size = ((def_seg_size + 0xfff) & ~0xfffU);
1056
1057
1058 /* init the structure. */
1059 cache->case_insensitive = case_insensitive;
1060 cache->hash_mask = (1U << hash_shift) - 1U;
1061 cache->count = 0;
1062 cache->lookup_count = 0;
1063 cache->collision_1st_count = 0;
1064 cache->collision_2nd_count = 0;
1065 cache->collision_3rd_count = 0;
1066 cache->rehash_count = (1U << hash_shift) / 4 * 3; /* rehash at 75% */
1067 cache->init_size = 1U << hash_shift;
1068 cache->hash_size = 1U << hash_shift;
1069 cache->def_seg_size = def_seg_size;
1070 cache->lock = NULL;
1071 cache->name = name;
1072
1073 /* allocate the hash table and first segment. */
1074 cache->hash_tab = (struct strcache2_entry **)
1075 xmalloc (cache->init_size * sizeof (struct strcache2_entry *));
1076 memset (cache->hash_tab, '\0', cache->init_size * sizeof (struct strcache2_entry *));
1077 strcache2_new_seg (cache, 0);
1078
1079 /* link it */
1080 cache->next = strcache_head;
1081 strcache_head = cache;
1082}
1083
1084
1085/* Terminates a string cache, freeing all memory and other
1086 associated resources. */
1087void
1088strcache2_term (struct strcache2 *cache)
1089{
1090 /* unlink it */
1091 if (strcache_head == cache)
1092 strcache_head = cache->next;
1093 else
1094 {
1095 struct strcache2 *prev = strcache_head;
1096 while (prev->next != cache)
1097 prev = prev->next;
1098 assert (prev);
1099 prev->next = cache->next;
1100 }
1101
1102 /* free the memory segments */
1103 do
1104 {
1105 void *free_it = cache->seg_head;
1106 cache->seg_head = cache->seg_head->next;
1107 free (free_it);
1108 }
1109 while (cache->seg_head);
1110
1111 /* free the hash and clear the structure. */
1112 free (cache->hash_tab);
1113 memset (cache, '\0', sizeof (struct strcache2));
1114}
1115
1116/* Print statistics a string cache. */
1117void
1118strcache2_print_stats (struct strcache2 *cache, const char *prefix)
1119{
1120 unsigned int seg_count = 0;
1121 unsigned long seg_total_bytes = 0;
1122 unsigned long seg_avg_bytes;
1123 unsigned long seg_avail_bytes = 0;
1124 unsigned long seg_max_bytes = 0;
1125 struct strcache2_seg *seg;
1126 unsigned long str_total_len = 0;
1127 unsigned int str_avg_len;
1128 unsigned int str_min_len = ~0U;
1129 unsigned int str_max_len = 0;
1130 unsigned int idx;
1131 unsigned int rehashes;
1132
1133 printf (_("\n%s strcache2: %s\n"), prefix, cache->name);
1134
1135 /* Segment statistics. */
1136 for (seg = cache->seg_head; seg; seg = seg->next)
1137 {
1138 seg_count++;
1139 seg_total_bytes += seg->size;
1140 seg_avail_bytes += seg->avail;
1141 if (seg->size > seg_max_bytes)
1142 seg_max_bytes = seg->size;
1143 }
1144 seg_avg_bytes = seg_total_bytes / seg_count;
1145 printf (_("%s %u segments: total = %lu / max = %lu / avg = %lu / def = %u avail = %lu\n"),
1146 prefix, seg_count, seg_total_bytes, seg_max_bytes, seg_avg_bytes,
1147 cache->def_seg_size, seg_avail_bytes);
1148
1149 /* String statistics. */
1150 idx = cache->hash_size;
1151 while (idx-- > 0)
1152 {
1153 struct strcache2_entry const *entry = cache->hash_tab[idx];
1154 if (entry)
1155 {
1156 unsigned int length = entry->length;
1157 str_total_len += length;
1158 if (length > str_max_len)
1159 str_max_len = length;
1160 if (length < str_min_len)
1161 str_min_len = length;
1162 }
1163 }
1164 str_avg_len = cache->count ? str_total_len / cache->count : 0;
1165 printf (_("%s %u strings: total len = %lu / max = %u / avg = %u / min = %u\n"),
1166 prefix, cache->count, str_total_len, str_max_len, str_avg_len, str_min_len);
1167
1168 /* Hash statistics. */
1169 idx = cache->init_size;
1170 rehashes = 0;
1171 while (idx < cache->hash_size)
1172 {
1173 idx *= 2;
1174 rehashes++;
1175 }
1176
1177 printf (_("%s hash size = %u mask = %#x rehashed %u times lookups = %lu\n"),
1178 prefix, cache->hash_size, cache->hash_mask, rehashes, cache->lookup_count);
1179 printf (_("%s hash collisions 1st = %lu (%u%%) 2nd = %lu (%u%%) 3rd = %lu (%u%%)\n"),
1180 prefix,
1181 cache->collision_1st_count, (unsigned int)((float)cache->collision_1st_count * 100 / cache->lookup_count),
1182 cache->collision_2nd_count, (unsigned int)((float)cache->collision_2nd_count * 100 / cache->lookup_count),
1183 cache->collision_3rd_count, (unsigned int)((float)cache->collision_3rd_count * 100 / cache->lookup_count));
1184}
1185
1186/* Print statistics for all string caches. */
1187void
1188strcache2_print_stats_all (const char *prefix)
1189{
1190 struct strcache2 *cur;
1191 for (cur = strcache_head; cur; cur = cur->next)
1192 strcache2_print_stats (cur, prefix);
1193}
1194
Note: See TracBrowser for help on using the repository browser.