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 *
23 */
24
25 #include "precompiled.hpp"
26 #include "classfile/altHashing.hpp"
27 #include "classfile/javaClasses.hpp"
28 #include "memory/allocation.inline.hpp"
29 #include "memory/filemap.hpp"
30 #include "memory/resourceArea.hpp"
31 #include "oops/oop.inline.hpp"
32 #include "runtime/safepoint.hpp"
33 #include "utilities/dtrace.hpp"
34 #include "utilities/hashtable.hpp"
35 #include "utilities/hashtable.inline.hpp"
36 #include "utilities/numberSeq.hpp"
37
38
39 // This is a generic hashtable, designed to be used for the symbol
40 // and string tables.
41 //
42 // It is implemented as an open hash table with a fixed number of buckets.
43 //
44 // %note:
45 // - HashtableEntrys are allocated in blocks to reduce the space overhead.
46
47 template <MEMFLAGS F> BasicHashtableEntry<F>* BasicHashtable<F>::new_entry(unsigned int hashValue) {
321 tty->cr();
322 entry = entry->next();
323 }
324 }
325 }
326
327
328 template <MEMFLAGS F> void BasicHashtable<F>::verify() {
329 int count = 0;
330 for (int i = 0; i < table_size(); i++) {
331 for (BasicHashtableEntry<F>* p = bucket(i); p != NULL; p = p->next()) {
332 ++count;
333 }
334 }
335 assert(count == number_of_entries(), "number of hashtable entries incorrect");
336 }
337
338
339 #endif // PRODUCT
340
341
342 #ifdef ASSERT
343
344 template <MEMFLAGS F> void BasicHashtable<F>::verify_lookup_length(double load) {
345 if ((double)_lookup_length / (double)_lookup_count > load * 2.0) {
346 warning("Performance bug: SystemDictionary lookup_count=%d "
347 "lookup_length=%d average=%lf load=%f",
348 _lookup_count, _lookup_length,
349 (double) _lookup_length / _lookup_count, load);
350 }
351 }
352
353 #endif
354 // Explicitly instantiate these types
355 template class Hashtable<ConstantPool*, mtClass>;
356 template class Hashtable<Symbol*, mtSymbol>;
357 template class Hashtable<Klass*, mtClass>;
358 template class Hashtable<oop, mtClass>;
359 #if defined(SOLARIS) || defined(CHECK_UNHANDLED_OOPS)
360 template class Hashtable<oop, mtSymbol>;
361 #endif // SOLARIS || CHECK_UNHANDLED_OOPS
362 template class Hashtable<oopDesc*, mtSymbol>;
363 template class Hashtable<Symbol*, mtClass>;
364 template class HashtableEntry<Symbol*, mtSymbol>;
365 template class HashtableEntry<Symbol*, mtClass>;
366 template class HashtableEntry<oop, mtSymbol>;
367 template class BasicHashtableEntry<mtSymbol>;
368 template class BasicHashtableEntry<mtCode>;
369 template class BasicHashtable<mtClass>;
370 template class BasicHashtable<mtSymbol>;
371 template class BasicHashtable<mtCode>;
372 template class BasicHashtable<mtInternal>;
|
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 *
23 */
24
25 #include "precompiled.hpp"
26 #include "classfile/altHashing.hpp"
27 #include "classfile/javaClasses.hpp"
28 #include "code/dependencies.hpp"
29 #include "memory/allocation.inline.hpp"
30 #include "memory/filemap.hpp"
31 #include "memory/resourceArea.hpp"
32 #include "oops/oop.inline.hpp"
33 #include "runtime/safepoint.hpp"
34 #include "utilities/dtrace.hpp"
35 #include "utilities/hashtable.hpp"
36 #include "utilities/hashtable.inline.hpp"
37 #include "utilities/numberSeq.hpp"
38
39
40 // This is a generic hashtable, designed to be used for the symbol
41 // and string tables.
42 //
43 // It is implemented as an open hash table with a fixed number of buckets.
44 //
45 // %note:
46 // - HashtableEntrys are allocated in blocks to reduce the space overhead.
47
48 template <MEMFLAGS F> BasicHashtableEntry<F>* BasicHashtable<F>::new_entry(unsigned int hashValue) {
322 tty->cr();
323 entry = entry->next();
324 }
325 }
326 }
327
328
329 template <MEMFLAGS F> void BasicHashtable<F>::verify() {
330 int count = 0;
331 for (int i = 0; i < table_size(); i++) {
332 for (BasicHashtableEntry<F>* p = bucket(i); p != NULL; p = p->next()) {
333 ++count;
334 }
335 }
336 assert(count == number_of_entries(), "number of hashtable entries incorrect");
337 }
338
339
340 #endif // PRODUCT
341
342 #ifdef ASSERT
343
344 template <MEMFLAGS F> void BasicHashtable<F>::verify_lookup_length(double load) {
345 if ((double)_lookup_length / (double)_lookup_count > load * 2.0) {
346 warning("Performance bug: SystemDictionary lookup_count=%d "
347 "lookup_length=%d average=%lf load=%f",
348 _lookup_count, _lookup_length,
349 (double) _lookup_length / _lookup_count, load);
350 }
351 }
352
353 #endif
354
355
356 template<class T, class M> GenericHashtable<T, M>::GenericHashtable(int size, bool resource_mark, MEMFLAGS memflag) {
357 assert(size > 0, " Invalid hashtable size");
358 _size = size;
359 // Perform subtype-specific resource allocation
360 _elements = (resource_mark) ? NEW_RESOURCE_ARRAY(T*, size) : NEW_C_HEAP_ARRAY(T*, size, memflag);
361 memset(_elements, 0, sizeof(T*) * size);
362 }
363
364
365 /**
366 * Add item to the hashtable. Returns 'true' if an element was added
367 * and false otherwise.
368 */
369 template<class T, class F> bool GenericHashtable<T, F>::add(T* item) {
370 if ((item == NULL) || contains(item)) {
371 return false;
372 }
373
374 uintptr_t hash = item->hash();
375 int idx = hash % size();
376
377 // Add to linked list
378 if (element_at(idx) != NULL) {
379 item->set_next(element_at(idx));
380 }
381
382 set_element_at(item, idx);
383 return true;
384 }
385
386 template<class T, class F> bool GenericHashtable<T, F>::contains(T* element) {
387 if (element == NULL) {
388 return false;
389 }
390
391 uintptr_t hash = element->hash();
392 int idx = hash % size();
393 if (element_at(idx) != NULL) {
394 T* current_element = element_at(idx);
395 while (current_element != NULL) {
396 if (current_element->equals(element)) {
397 return true;
398 }
399 current_element = current_element->next();
400 }
401 }
402 return false;
403 }
404
405
406 // Explicitly instantiate these types
407 template class Hashtable<ConstantPool*, mtClass>;
408 template class Hashtable<Symbol*, mtSymbol>;
409 template class Hashtable<Klass*, mtClass>;
410 template class Hashtable<oop, mtClass>;
411 #if defined(SOLARIS) || defined(CHECK_UNHANDLED_OOPS)
412 template class Hashtable<oop, mtSymbol>;
413 #endif // SOLARIS || CHECK_UNHANDLED_OOPS
414 template class Hashtable<oopDesc*, mtSymbol>;
415 template class Hashtable<Symbol*, mtClass>;
416 template class HashtableEntry<Symbol*, mtSymbol>;
417 template class HashtableEntry<Symbol*, mtClass>;
418 template class HashtableEntry<oop, mtSymbol>;
419 template class BasicHashtableEntry<mtSymbol>;
420 template class BasicHashtableEntry<mtCode>;
421 template class BasicHashtable<mtClass>;
422 template class BasicHashtable<mtSymbol>;
423 template class BasicHashtable<mtCode>;
424 template class BasicHashtable<mtInternal>;
425
426 template class GenericHashtable<DependencySignature, ResourceObj>;
|