1 /*
2 * Copyright (c) 2014, 2019, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
105 // The table is also dynamically rehashed (using a new hash seed) if it becomes severely
106 // unbalanced, i.e., a hash chain is significantly longer than average.
107 //
108 // All access to the table is protected by the StringDedupTable_lock, except under
109 // safepoints in which case GC workers are allowed to access a table partitions they
110 // have claimed without first acquiring the lock. Note however, that this applies only
111 // the table partition (i.e. a range of elements in _buckets), not other parts of the
112 // table such as the _entries field, statistics counters, etc.
113 //
114 class StringDedupTable : public CHeapObj<mtGC> {
115 private:
116 // The currently active hashtable instance. Only modified when
117 // the table is resizes or rehashed.
118 static StringDedupTable* _table;
119
120 // Cache for reuse and fast alloc/free of table entries.
121 static StringDedupEntryCache* _entry_cache;
122
123 StringDedupEntry** _buckets;
124 size_t _size;
125 uintx _entries;
126 uintx _shrink_threshold;
127 uintx _grow_threshold;
128 bool _rehash_needed;
129
130 // The hash seed also dictates which hash function to use. A
131 // zero hash seed means we will use the Java compatible hash
132 // function (which doesn't use a seed), and a non-zero hash
133 // seed means we use the murmur3 hash function.
134 jint _hash_seed;
135
136 // Constants governing table resize/rehash/cache.
137 static const size_t _min_size;
138 static const size_t _max_size;
139 static const double _grow_load_factor;
140 static const double _shrink_load_factor;
141 static const uintx _rehash_multiple;
142 static const uintx _rehash_threshold;
143 static const double _max_cache_factor;
144
145 // Table statistics, only used for logging.
146 static uintx _entries_added;
147 static uintx _entries_removed;
148 static uintx _resize_count;
149 static uintx _rehash_count;
150
151 static volatile size_t _claimed_index;
152
153 static StringDedupTable* _resized_table;
154 static StringDedupTable* _rehashed_table;
155
156 StringDedupTable(size_t size, jint hash_seed = 0);
157 ~StringDedupTable();
158
159 // Returns the hash bucket at the given index.
160 StringDedupEntry** bucket(size_t index) {
161 return _buckets + index;
162 }
163
164 // Returns the hash bucket index for the given hash code.
165 size_t hash_to_index(unsigned int hash) {
166 return (size_t)hash & (_size - 1);
167 }
|
1 /*
2 * Copyright (c) 2014, 2020, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
105 // The table is also dynamically rehashed (using a new hash seed) if it becomes severely
106 // unbalanced, i.e., a hash chain is significantly longer than average.
107 //
108 // All access to the table is protected by the StringDedupTable_lock, except under
109 // safepoints in which case GC workers are allowed to access a table partitions they
110 // have claimed without first acquiring the lock. Note however, that this applies only
111 // the table partition (i.e. a range of elements in _buckets), not other parts of the
112 // table such as the _entries field, statistics counters, etc.
113 //
114 class StringDedupTable : public CHeapObj<mtGC> {
115 private:
116 // The currently active hashtable instance. Only modified when
117 // the table is resizes or rehashed.
118 static StringDedupTable* _table;
119
120 // Cache for reuse and fast alloc/free of table entries.
121 static StringDedupEntryCache* _entry_cache;
122
123 StringDedupEntry** _buckets;
124 size_t _size;
125 volatile uintx _entries;
126 uintx _shrink_threshold;
127 uintx _grow_threshold;
128 bool _rehash_needed;
129
130 // The hash seed also dictates which hash function to use. A
131 // zero hash seed means we will use the Java compatible hash
132 // function (which doesn't use a seed), and a non-zero hash
133 // seed means we use the murmur3 hash function.
134 jint _hash_seed;
135
136 // Constants governing table resize/rehash/cache.
137 static const size_t _min_size;
138 static const size_t _max_size;
139 static const double _grow_load_factor;
140 static const double _shrink_load_factor;
141 static const uintx _rehash_multiple;
142 static const uintx _rehash_threshold;
143 static const double _max_cache_factor;
144
145 // Table statistics, only used for logging.
146 static uintx _entries_added;
147 static volatile uintx _entries_removed;
148 static uintx _resize_count;
149 static uintx _rehash_count;
150
151 static volatile size_t _claimed_index;
152
153 static StringDedupTable* _resized_table;
154 static StringDedupTable* _rehashed_table;
155
156 StringDedupTable(size_t size, jint hash_seed = 0);
157 ~StringDedupTable();
158
159 // Returns the hash bucket at the given index.
160 StringDedupEntry** bucket(size_t index) {
161 return _buckets + index;
162 }
163
164 // Returns the hash bucket index for the given hash code.
165 size_t hash_to_index(unsigned int hash) {
166 return (size_t)hash & (_size - 1);
167 }
|