hashtable.hpp revision 3863
0N/A/*
3149N/A * Copyright (c) 2003, 2012, Oracle and/or its affiliates. All rights reserved.
0N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
0N/A *
0N/A * This code is free software; you can redistribute it and/or modify it
0N/A * under the terms of the GNU General Public License version 2 only, as
0N/A * published by the Free Software Foundation.
0N/A *
0N/A * This code is distributed in the hope that it will be useful, but WITHOUT
0N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
0N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
0N/A * version 2 for more details (a copy is included in the LICENSE file that
0N/A * accompanied this code).
0N/A *
0N/A * You should have received a copy of the GNU General Public License version
0N/A * 2 along with this work; if not, write to the Free Software Foundation,
0N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
0N/A *
1472N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1472N/A * or visit www.oracle.com if you need additional information or have any
1472N/A * questions.
0N/A *
0N/A */
0N/A
1879N/A#ifndef SHARE_VM_UTILITIES_HASHTABLE_HPP
1879N/A#define SHARE_VM_UTILITIES_HASHTABLE_HPP
1879N/A
1879N/A#include "memory/allocation.hpp"
1879N/A#include "oops/oop.hpp"
2062N/A#include "oops/symbol.hpp"
1879N/A#include "runtime/handles.hpp"
1879N/A
0N/A// This is a generic hashtable, designed to be used for the symbol
0N/A// and string tables.
0N/A//
0N/A// It is implemented as an open hash table with a fixed number of buckets.
0N/A//
0N/A// %note:
0N/A// - TableEntrys are allocated in blocks to reduce the space overhead.
0N/A
0N/A
0N/A
3863N/Atemplate <MEMFLAGS F> class BasicHashtableEntry : public CHeapObj<F> {
0N/A friend class VMStructs;
0N/Aprivate:
0N/A unsigned int _hash; // 32-bit hash for item
0N/A
0N/A // Link to next element in the linked list for this bucket. EXCEPT
0N/A // bit 0 set indicates that this entry is shared and must not be
0N/A // unlinked from the table. Bit 0 is set during the dumping of the
0N/A // archive. Since shared entries are immutable, _next fields in the
0N/A // shared entries will not change. New entries will always be
0N/A // unshared and since pointers are align, bit 0 will always remain 0
0N/A // with no extra effort.
3863N/A BasicHashtableEntry<F>* _next;
0N/A
0N/A // Windows IA64 compiler requires subclasses to be able to access these
0N/Aprotected:
0N/A // Entry objects should not be created, they should be taken from the
0N/A // free list with BasicHashtable.new_entry().
0N/A BasicHashtableEntry() { ShouldNotReachHere(); }
0N/A // Entry objects should not be destroyed. They should be placed on
0N/A // the free list instead with BasicHashtable.free_entry().
0N/A ~BasicHashtableEntry() { ShouldNotReachHere(); }
0N/A
0N/Apublic:
0N/A
0N/A unsigned int hash() const { return _hash; }
0N/A void set_hash(unsigned int hash) { _hash = hash; }
0N/A unsigned int* hash_addr() { return &_hash; }
0N/A
3863N/A static BasicHashtableEntry<F>* make_ptr(BasicHashtableEntry<F>* p) {
0N/A return (BasicHashtableEntry*)((intptr_t)p & -2);
0N/A }
0N/A
3863N/A BasicHashtableEntry<F>* next() const {
0N/A return make_ptr(_next);
0N/A }
0N/A
3863N/A void set_next(BasicHashtableEntry<F>* next) {
0N/A _next = next;
0N/A }
0N/A
3863N/A BasicHashtableEntry<F>** next_addr() {
0N/A return &_next;
0N/A }
0N/A
0N/A bool is_shared() const {
0N/A return ((intptr_t)_next & 1) != 0;
0N/A }
0N/A
0N/A void set_shared() {
3863N/A _next = (BasicHashtableEntry<F>*)((intptr_t)_next | 1);
0N/A }
0N/A};
0N/A
0N/A
0N/A
3863N/Atemplate <class T, MEMFLAGS F> class HashtableEntry : public BasicHashtableEntry<F> {
0N/A friend class VMStructs;
0N/Aprivate:
2062N/A T _literal; // ref to item in table.
0N/A
0N/Apublic:
0N/A // Literal
2062N/A T literal() const { return _literal; }
2062N/A T* literal_addr() { return &_literal; }
2062N/A void set_literal(T s) { _literal = s; }
0N/A
0N/A HashtableEntry* next() const {
3863N/A return (HashtableEntry*)BasicHashtableEntry<F>::next();
0N/A }
0N/A HashtableEntry** next_addr() {
3863N/A return (HashtableEntry**)BasicHashtableEntry<F>::next_addr();
0N/A }
0N/A};
0N/A
0N/A
0N/A
3863N/Atemplate <MEMFLAGS F> class HashtableBucket : public CHeapObj<F> {
0N/A friend class VMStructs;
0N/Aprivate:
0N/A // Instance variable
3863N/A BasicHashtableEntry<F>* _entry;
0N/A
0N/Apublic:
0N/A // Accessing
0N/A void clear() { _entry = NULL; }
0N/A
0N/A // The following methods use order access methods to avoid race
0N/A // conditions in multiprocessor systems.
3863N/A BasicHashtableEntry<F>* get_entry() const;
3863N/A void set_entry(BasicHashtableEntry<F>* l);
0N/A
0N/A // The following method is not MT-safe and must be done under lock.
3863N/A BasicHashtableEntry<F>** entry_addr() { return &_entry; }
0N/A};
0N/A
0N/A
3863N/Atemplate <MEMFLAGS F> class BasicHashtable : public CHeapObj<F> {
0N/A friend class VMStructs;
0N/A
0N/Apublic:
0N/A BasicHashtable(int table_size, int entry_size);
0N/A BasicHashtable(int table_size, int entry_size,
3863N/A HashtableBucket<F>* buckets, int number_of_entries);
0N/A
0N/A // Sharing support.
0N/A void copy_buckets(char** top, char* end);
0N/A void copy_table(char** top, char* end);
0N/A
0N/A // Bucket handling
0N/A int hash_to_index(unsigned int full_hash) {
0N/A int h = full_hash % _table_size;
0N/A assert(h >= 0 && h < _table_size, "Illegal hash value");
0N/A return h;
0N/A }
0N/A
0N/A // Reverse the order of elements in each of the buckets.
0N/A void reverse();
0N/A
0N/Aprivate:
0N/A // Instance variables
0N/A int _table_size;
Error!

 

There was an error!

null

java.lang.NullPointerException