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) {
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 C_heap, MEMFLAGS memflag) {
357 assert(size > 0, " Invalid hashtable size");
358 _size = size;
359 _C_heap = C_heap;
360 _memflag = memflag;
361 // Perform subtype-specific resource allocation
362 _items = (C_heap) ? NEW_C_HEAP_ARRAY(T*, size, memflag) : NEW_RESOURCE_ARRAY(T*, size);
363 memset(_items, 0, sizeof(T*) * size);
364
365 DEBUG_ONLY(_num_items = 0;)
366 }
367
368 template<class T, class M> GenericHashtable<T, M>::~GenericHashtable() {
369 if (on_C_heap()) {
370 // Check backing array
371 for (int i = 0; i < size(); i++) {
372 T* item = head(i);
373 // Delete all items in linked list
374 while (item != NULL) {
375 T* next_item = item->next();
376 delete item;
377 DEBUG_ONLY(_num_items--);
378 item = next_item;
379 }
380 }
381 FREE_C_HEAP_ARRAY(T*, _items, _memflag);
382 _items = NULL;
383 assert (_num_items == 0, "Not all memory released");
384 }
385 }
386
387 /**
388 * Return a pointer to the item 'I' that is stored in the hashtable for
389 * which match_item->equals(I) == true. If no such item is found, NULL
390 * is returned.
391 */
392 template<class T, class F> T* GenericHashtable<T, F>::contains(T* match_item) {
393 if (match_item != NULL) {
394 int idx = index(match_item);
395 return contains_impl(match_item, idx);
396 }
397 return NULL;
398 }
399
400 /**
401 * Add item to the hashtable. Return 'true' if the item was added
402 * and false otherwise.
403 */
404 template<class T, class F> bool GenericHashtable<T, F>::add(T* item) {
405 if (item != NULL) {
406 int idx = index(item);
407 T* found_item = contains_impl(item, idx);
408 if (found_item == NULL) {
409 T* list_head = head(idx);
410 item->set_next(list_head);
411 item->set_prev(NULL);
412
413 if (list_head != NULL) {
414 list_head->set_prev(item);
415 }
416 set_head(item, idx);
417 DEBUG_ONLY(_num_items++);
418 return true;
419 }
420 }
421 return false;
422 }
423
424 /**
425 * Removes an item 'I' from the hashtable, if present. 'I' is removed, if
426 * match_item->equals(I) == true. Removing an item from the hashtable does
427 * not free memory.
428 */
429 template<class T, class F> T* GenericHashtable<T, F>::remove(T* match_item) {
430 if (match_item != NULL) {
431 int idx = index(match_item);
432 T* found_item = contains_impl(match_item, idx);
433 if (found_item != NULL) {
434 // Remove item from linked list
435 T* prev = found_item->prev();
436 T* next = found_item->next();
437 if (prev != NULL) {
438 prev->set_next(next);
439 } else {
440 set_head(next, idx);
441 }
442 if (next != NULL) {
443 next->set_prev(prev);
444 }
445
446 DEBUG_ONLY(_num_items--);
447 return found_item;
448 }
449 }
450 return NULL;
451 }
452
453
454 template<class T, class F> T* GenericHashtable<T, F>::contains_impl(T* item, int idx) {
455 T* current_item = head(idx);
456 while (current_item != NULL) {
457 if (current_item->equals(item)) {
458 return current_item;
459 }
460 current_item = current_item->next();
461 }
462 return NULL;
463 }
464
465
466 // Explicitly instantiate these types
467 template class Hashtable<ConstantPool*, mtClass>;
468 template class Hashtable<Symbol*, mtSymbol>;
469 template class Hashtable<Klass*, mtClass>;
470 template class Hashtable<oop, mtClass>;
471 #if defined(SOLARIS) || defined(CHECK_UNHANDLED_OOPS)
472 template class Hashtable<oop, mtSymbol>;
473 #endif // SOLARIS || CHECK_UNHANDLED_OOPS
474 template class Hashtable<oopDesc*, mtSymbol>;
475 template class Hashtable<Symbol*, mtClass>;
476 template class HashtableEntry<Symbol*, mtSymbol>;
477 template class HashtableEntry<Symbol*, mtClass>;
478 template class HashtableEntry<oop, mtSymbol>;
479 template class BasicHashtableEntry<mtSymbol>;
480 template class BasicHashtableEntry<mtCode>;
481 template class BasicHashtable<mtClass>;
482 template class BasicHashtable<mtSymbol>;
483 template class BasicHashtable<mtCode>;
484 template class BasicHashtable<mtInternal>;
485
486 template class GenericHashtable<DependencySignature, ResourceObj>;
|
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) {
335 assert(count == number_of_entries(), "number of hashtable entries incorrect");
336 }
337
338
339 #endif // PRODUCT
340
341 #ifdef ASSERT
342
343 template <MEMFLAGS F> void BasicHashtable<F>::verify_lookup_length(double load) {
344 if ((double)_lookup_length / (double)_lookup_count > load * 2.0) {
345 warning("Performance bug: SystemDictionary lookup_count=%d "
346 "lookup_length=%d average=%lf load=%f",
347 _lookup_count, _lookup_length,
348 (double) _lookup_length / _lookup_count, load);
349 }
350 }
351
352 #endif
353
354
355 // Explicitly instantiate these types
356 template class Hashtable<ConstantPool*, mtClass>;
357 template class Hashtable<Symbol*, mtSymbol>;
358 template class Hashtable<Klass*, mtClass>;
359 template class Hashtable<oop, mtClass>;
360 #if defined(SOLARIS) || defined(CHECK_UNHANDLED_OOPS)
361 template class Hashtable<oop, mtSymbol>;
362 #endif // SOLARIS || CHECK_UNHANDLED_OOPS
363 template class Hashtable<oopDesc*, mtSymbol>;
364 template class Hashtable<Symbol*, mtClass>;
365 template class HashtableEntry<Symbol*, mtSymbol>;
366 template class HashtableEntry<Symbol*, mtClass>;
367 template class HashtableEntry<oop, mtSymbol>;
368 template class BasicHashtableEntry<mtSymbol>;
369 template class BasicHashtableEntry<mtCode>;
370 template class BasicHashtable<mtClass>;
371 template class BasicHashtable<mtSymbol>;
372 template class BasicHashtable<mtCode>;
373 template class BasicHashtable<mtInternal>;
|