|
0
|
1 /*
|
|
|
2 * Copyright 2003 Sun Microsystems, Inc. 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
|
|
|
20 * CA 95054 USA or visit www.sun.com if you need additional information or
|
|
|
21 * have any questions.
|
|
|
22 *
|
|
|
23 */
|
|
|
24
|
|
|
25 // Inline function definitions for hashtable.hpp.
|
|
|
26
|
|
|
27
|
|
|
28 // --------------------------------------------------------------------------
|
|
|
29 // Hash function
|
|
|
30
|
|
|
31 // We originally used hashpjw, but hash P(31) gives just as good results
|
|
|
32 // and is slighly faster. We would like a hash function that looks at every
|
|
|
33 // character, since package names have large common prefixes, and also because
|
|
|
34 // hash_or_fail does error checking while iterating.
|
|
|
35
|
|
|
36 // hash P(31) from Kernighan & Ritchie
|
|
|
37
|
|
|
38 inline unsigned int Hashtable::hash_symbol(const char* s, int len) {
|
|
|
39 unsigned int h = 0;
|
|
|
40 while (len-- > 0) {
|
|
|
41 h = 31*h + (unsigned) *s;
|
|
|
42 s++;
|
|
|
43 }
|
|
|
44 return h;
|
|
|
45 }
|
|
|
46
|
|
|
47
|
|
|
48 // --------------------------------------------------------------------------
|
|
|
49
|
|
|
50 // Initialize a table.
|
|
|
51
|
|
|
52 inline BasicHashtable::BasicHashtable(int table_size, int entry_size) {
|
|
|
53 // Called on startup, no locking needed
|
|
|
54 initialize(table_size, entry_size, 0);
|
|
|
55 _buckets = NEW_C_HEAP_ARRAY(HashtableBucket, table_size);
|
|
|
56 for (int index = 0; index < _table_size; index++) {
|
|
|
57 _buckets[index].clear();
|
|
|
58 }
|
|
|
59 }
|
|
|
60
|
|
|
61
|
|
|
62 inline BasicHashtable::BasicHashtable(int table_size, int entry_size,
|
|
|
63 HashtableBucket* buckets,
|
|
|
64 int number_of_entries) {
|
|
|
65 // Called on startup, no locking needed
|
|
|
66 initialize(table_size, entry_size, number_of_entries);
|
|
|
67 _buckets = buckets;
|
|
|
68 }
|
|
|
69
|
|
|
70
|
|
|
71 inline void BasicHashtable::initialize(int table_size, int entry_size,
|
|
|
72 int number_of_entries) {
|
|
|
73 // Called on startup, no locking needed
|
|
|
74 _table_size = table_size;
|
|
|
75 _entry_size = entry_size;
|
|
|
76 _free_list = NULL;
|
|
|
77 _first_free_entry = NULL;
|
|
|
78 _end_block = NULL;
|
|
|
79 _number_of_entries = number_of_entries;
|
|
|
80 #ifdef ASSERT
|
|
|
81 _lookup_count = 0;
|
|
|
82 _lookup_length = 0;
|
|
|
83 #endif
|
|
|
84 }
|
|
|
85
|
|
|
86
|
|
|
87 // The following method is MT-safe and may be used with caution.
|
|
|
88 inline BasicHashtableEntry* BasicHashtable::bucket(int i) {
|
|
|
89 return _buckets[i].get_entry();
|
|
|
90 }
|
|
|
91
|
|
|
92
|
|
|
93 inline void HashtableBucket::set_entry(BasicHashtableEntry* l) {
|
|
|
94 // Warning: Preserve store ordering. The SystemDictionary is read
|
|
|
95 // without locks. The new SystemDictionaryEntry must be
|
|
|
96 // complete before other threads can be allowed to see it
|
|
|
97 // via a store to _buckets[index].
|
|
|
98 OrderAccess::release_store_ptr(&_entry, l);
|
|
|
99 }
|
|
|
100
|
|
|
101
|
|
|
102 inline BasicHashtableEntry* HashtableBucket::get_entry() const {
|
|
|
103 // Warning: Preserve load ordering. The SystemDictionary is read
|
|
|
104 // without locks. The new SystemDictionaryEntry must be
|
|
|
105 // complete before other threads can be allowed to see it
|
|
|
106 // via a store to _buckets[index].
|
|
|
107 return (BasicHashtableEntry*) OrderAccess::load_ptr_acquire(&_entry);
|
|
|
108 }
|
|
|
109
|
|
|
110
|
|
|
111 inline void BasicHashtable::set_entry(int index, BasicHashtableEntry* entry) {
|
|
|
112 _buckets[index].set_entry(entry);
|
|
|
113 }
|
|
|
114
|
|
|
115
|
|
|
116 inline void BasicHashtable::add_entry(int index, BasicHashtableEntry* entry) {
|
|
|
117 entry->set_next(bucket(index));
|
|
|
118 _buckets[index].set_entry(entry);
|
|
|
119 ++_number_of_entries;
|
|
|
120 }
|
|
|
121
|
|
|
122 inline void BasicHashtable::free_entry(BasicHashtableEntry* entry) {
|
|
|
123 entry->set_next(_free_list);
|
|
|
124 _free_list = entry;
|
|
|
125 --_number_of_entries;
|
|
|
126 }
|
