VirtualBox

source: kBuild/trunk/src/kmk/strcache2.h@ 2132

Last change on this file since 2132 was 2019, checked in by bird, 16 years ago

GPLv2 -> GPLv3. See Ticket #44 for clarifications. Fixes #44.

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 6.8 KB
Line 
1/* $Id: strcache2.h 2019 2008-11-02 00:21:05Z bird $ */
2/** @file
3 * strcache - New string cache.
4 */
5
6/*
7 * Copyright (c) 2006-2008 knut st. osmundsen <[email protected]>
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. */
36struct 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. */
46struct 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
70struct 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
96void strcache2_init (struct strcache2 *cache, const char *name, unsigned int size,
97 unsigned int def_seg_size, int case_insensitive, int thread_safe);
98void strcache2_term (struct strcache2 *cache);
99void strcache2_print_stats (struct strcache2 *cache, const char *prefix);
100void strcache2_print_stats_all (const char *prefix);
101const char *strcache2_add (struct strcache2 *cache, const char *str, unsigned int length);
102const char *strcache2_iadd (struct strcache2 *cache, const char *str, unsigned int length);
103const char *strcache2_add_hashed (struct strcache2 *cache, const char *str,
104 unsigned int length, unsigned int hash);
105const char *strcache2_iadd_hashed (struct strcache2 *cache, const char *str,
106 unsigned int length, unsigned int hash);
107const char *strcache2_lookup (struct strcache2 *cache, const char *str, unsigned int length);
108const 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
118int strcache2_is_cached (struct strcache2 *cache, const char *str);
119int strcache2_verify_entry (struct strcache2 *cache, const char *str);
120unsigned int strcache2_get_hash2_fallback (struct strcache2 *cache, const char *str);
121unsigned int strcache2_hash_str (const char *str, unsigned int length, unsigned int *hash2p);
122unsigned int strcache2_hash_istr (const char *str, unsigned int length, unsigned int *hash2p);
123
124/* Get the hash table entry pointer. */
125MY_INLINE struct strcache2_entry const *
126strcache2_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. */
135MY_INLINE unsigned int
136strcache2_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. */
142MY_INLINE unsigned int
143strcache2_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. */
156MY_INLINE unsigned int
157strcache2_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. */
164MY_INLINE void *
165strcache2_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. */
171MY_INLINE void
172strcache2_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
Note: See TracBrowser for help on using the repository browser.

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette