1 /* $Id: strcache2.h 2413 2010-09-11 17:43:04Z bird $ */
2 /** @file
3 * strcache - New string cache.
4 */
5
6 /*
7 * Copyright (c) 2006-2010 knut st. osmundsen <bird-kBuild-spamx@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 3 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, see <http://www.gnu.org/licenses/>
23 *
24 */
25
26 #ifndef ___strcache2_h
27 #define ___strcache2_h
28
29 #ifndef CHAR_BIT
30 # error "include after make.h!"
31 #endif
32
33 #define STRCACHE2_USE_MASK 1
34
35 /* string cache memory segment. */
36 struct strcache2_seg
37 {
38 struct strcache2_seg *next; /* The next cache segment. */
39 char *start; /* The first byte in the segment. */
40 size_t size; /* The size of the segment. */
41 size_t avail; /* The number of available bytes. */
42 char *cursor; /* Allocation cursor. */
43 };
44
45 /* string cache hash table entry. */
46 struct strcache2_entry
47 {
48 struct strcache2_entry *next; /* Collision chain. */
49 void *user;
50 unsigned int hash;
51 unsigned int length;
52 };
53
54 /* The entry alignment, cacheline size if it's known & sensible.
55
56 On x86/AMD64 we assume a 64-byte cacheline size. As it is difficult to
57 guess other right now, these default 16 chars as that shouldn't cause
58 much trouble, even if it not the most optimial value. Override, or modify
59 for other platforms. */
60 #ifndef STRCACHE2_ENTRY_ALIGN_SHIFT
61 # if defined (__i386__) || defined(__x86_64__)
62 # define STRCACHE2_ENTRY_ALIGN_SHIFT 6
63 # else
64 # define STRCACHE2_ENTRY_ALIGN_SHIFT 4
65 # endif
66 #endif
67 #define STRCACHE2_ENTRY_ALIGNMENT (1 << STRCACHE2_ENTRY_ALIGN_SHIFT)
68
69
70 struct strcache2
71 {
72 struct strcache2_entry **hash_tab; /* The hash table. */
73 int case_insensitive; /* case insensitive or not. */
74 #ifdef STRCACHE2_USE_MASK
75 unsigned int hash_mask; /* The AND mask matching hash_size.*/
76 #else
77 unsigned int hash_div; /* The number (prime) to mod by. */
78 #endif
79 unsigned long lookup_count; /* The number of lookups. */
80 unsigned long collision_1st_count; /* The number of 1st level collisions. */
81 unsigned long collision_2nd_count; /* The number of 2nd level collisions. */
82 unsigned long collision_3rd_count; /* The number of 3rd level collisions. */
83 unsigned int count; /* Number entries in the cache. */
84 unsigned int collision_count; /* Number of entries in chains. */
85 unsigned int rehash_count; /* When to rehash the table. */
86 unsigned int init_size; /* The initial hash table size. */
87 unsigned int hash_size; /* The hash table size. */
88 unsigned int def_seg_size; /* The default segment size. */
89 void *lock; /* The lock handle. */
90 struct strcache2_seg *seg_head; /* The memory segment list. */
91 struct strcache2 *next; /* The next string cache. */
92 const char *name; /* Cache name. */
93 };
94
95
96 void strcache2_init (struct strcache2 *cache, const char *name, unsigned int size,
97 unsigned int def_seg_size, int case_insensitive, int thread_safe);
98 void strcache2_term (struct strcache2 *cache);
99 void strcache2_print_stats (struct strcache2 *cache, const char *prefix);
100 void strcache2_print_stats_all (const char *prefix);
101 const char *strcache2_add (struct strcache2 *cache, const char *str, unsigned int length);
102 const char *strcache2_iadd (struct strcache2 *cache, const char *str, unsigned int length);
103 const char *strcache2_add_hashed (struct strcache2 *cache, const char *str,
104 unsigned int length, unsigned int hash);
105 const char *strcache2_iadd_hashed (struct strcache2 *cache, const char *str,
106 unsigned int length, unsigned int hash);
107 const char *strcache2_lookup (struct strcache2 *cache, const char *str, unsigned int length);
108 const char *strcache2_ilookup (struct strcache2 *cache, const char *str, unsigned int length);
109 #ifdef HAVE_CASE_INSENSITIVE_FS
110 # define strcache2_add_file strcache2_iadd
111 # define strcache2_add_hashed_file strcache2_iadd_hashed
112 # define strcache2_lookup_file strcache2_ilookup
113 #else
114 # define strcache2_add_file strcache2_add
115 # define strcache2_add_hashed_file strcache2_add_hashed
116 # define strcache2_lookup_file strcache2_lookup
117 #endif
118 int strcache2_is_cached (struct strcache2 *cache, const char *str);
119 int strcache2_verify_entry (struct strcache2 *cache, const char *str);
120 unsigned int strcache2_get_hash2_fallback (struct strcache2 *cache, const char *str);
121 unsigned int strcache2_hash_str (const char *str, unsigned int length, unsigned int *hash2p);
122 unsigned int strcache2_hash_istr (const char *str, unsigned int length, unsigned int *hash2p);
123
124 /* Get the hash table entry pointer. */
125 MY_INLINE struct strcache2_entry const *
strcache2_get_entry(struct strcache2 * cache,const char * str)126 strcache2_get_entry (struct strcache2 *cache, const char *str)
127 {
128 #ifndef NDEBUG
129 strcache2_verify_entry (cache, str);
130 #endif
131 return (struct strcache2_entry const *)str - 1;
132 }
133
134 /* Get the string length. */
135 MY_INLINE unsigned int
strcache2_get_len(struct strcache2 * cache,const char * str)136 strcache2_get_len (struct strcache2 *cache, const char *str)
137 {
138 return strcache2_get_entry (cache, str)->length;
139 }
140
141 /* Get the first hash value for the string. */
142 MY_INLINE unsigned int
strcache2_get_hash(struct strcache2 * cache,const char * str)143 strcache2_get_hash (struct strcache2 *cache, const char *str)
144 {
145 return strcache2_get_entry (cache, str)->hash;
146 }
147
148 /* Calc the pointer hash value for the string.
149
150 This takes the string address, shift out the bits that are always zero
151 due to alignment, and then returns the unsigned integer value of it.
152
153 The results from using this is generally better than for any of the
154 other hash values. It is also sligtly faster code as it does not
155 involve any memory accesses, just a right SHIFT and an optional AND. */
156 MY_INLINE unsigned int
strcache2_calc_ptr_hash(struct strcache2 * cache,const char * str)157 strcache2_calc_ptr_hash (struct strcache2 *cache, const char *str)
158 {
159 (void)cache;
160 return (size_t)str >> STRCACHE2_ENTRY_ALIGN_SHIFT;
161 }
162
163 /* Get the user value for the string. */
164 MY_INLINE void *
strcache2_get_user_val(struct strcache2 * cache,const char * str)165 strcache2_get_user_val (struct strcache2 *cache, const char *str)
166 {
167 return strcache2_get_entry (cache, str)->user;
168 }
169
170 /* Get the user value for the string. */
171 MY_INLINE void
strcache2_set_user_val(struct strcache2 * cache,const char * str,void * value)172 strcache2_set_user_val (struct strcache2 *cache, const char *str, void *value)
173 {
174 struct strcache2_entry *entry = (struct strcache2_entry *)str - 1;
175 #ifndef NDEBUG
176 strcache2_verify_entry (cache, str);
177 #endif
178 entry->user = value;
179 }
180
181 #endif
182
183