1/* 2 * Copyright (c) 1996, 2006, 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. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26#include "Hashtable.h" 27 28Hashtable::Hashtable(const char* name, void (*deleteProc)(void*), 29 int initialCapacity, float loadFactor) { 30 DASSERT ((initialCapacity > 0) && (loadFactor > 0.0)); 31 32 table = (HashtableEntry**) 33 safe_Calloc(initialCapacity, sizeof(HashtableEntry*)); 34 35 capacity = initialCapacity; 36 count = 0; 37 threshold = (int)(capacity * loadFactor); 38 this->loadFactor = loadFactor; 39 m_deleteProc = deleteProc; 40 41#ifdef DEBUG 42 m_name = (char*)name; 43 m_max = 0; 44 m_collisions = 0; 45#else 46 name; // suppress "unused parameter" warning 47#endif 48} 49 50Hashtable::~Hashtable() 51{ 52#ifdef DEBUG 53 DTRACE_PRINTLN3("%s: %d entries, %d maximum entries\n", m_name, count, m_max); 54#endif 55 clear(); 56 free(table); 57} 58 59BOOL Hashtable::contains(void* value) { 60 DASSERT(value != NULL); 61 62 CriticalSection::Lock l(lock); 63 64 for (int i = capacity; i-- > 0;) { 65 for (HashtableEntry* e = table[i] ; e != NULL ; e = e->next) { 66 if (e->value == value) { 67 return TRUE; 68 } 69 } 70 } 71 return FALSE; 72} 73 74BOOL Hashtable::containsKey(void* key) { 75 CriticalSection::Lock l(lock); 76 int index = static_cast<int>(((reinterpret_cast<INT_PTR>(key) << 1) >> 1) 77 % capacity); 78 for (HashtableEntry* e = table[index]; e != NULL; e = e->next) { 79 if (e->hash == (INT_PTR)key && e->key == key) { 80 return TRUE; 81 } 82 } 83 return FALSE; 84} 85 86void* Hashtable::get(void* key) { 87 CriticalSection::Lock l(lock); 88 int index = static_cast<int>(((reinterpret_cast<INT_PTR>(key) << 1) >> 1) 89 % capacity); 90 for (HashtableEntry* e = table[index]; e != NULL; e = e->next) { 91 if (e->hash == (INT_PTR)key && e->key == key) { 92 return e->value; 93 } 94 } 95 return NULL; 96} 97 98void Hashtable::rehash() { 99 int oldCapacity = capacity; 100 HashtableEntry** oldTable = table; 101 102 int newCapacity = oldCapacity * 2 + 1; 103 HashtableEntry** newTable = (HashtableEntry**)safe_Calloc( 104 newCapacity, sizeof(HashtableEntry*)); 105 106 threshold = (int)(newCapacity * loadFactor); 107 table = newTable; 108 capacity = newCapacity; 109 110 for (int i = 0; i < oldCapacity; i++) { 111 for (HashtableEntry* old = oldTable[i] ; old != NULL ; ) { 112 HashtableEntry* e = old; 113 old = old->next; 114 int index = static_cast<int>(((e->hash << 1) >> 1) % newCapacity); 115 e->next = newTable[index]; 116 newTable[index] = e; 117 } 118 } 119 120 free(oldTable); 121} 122 123void* Hashtable::put(void* key, void* value) { 124 DASSERT(value != NULL); 125 CriticalSection::Lock l(lock); 126 HashtableEntry* e; 127 128 // Makes sure the key is not already in the hashtable. 129 int index = (int)(((INT_PTR)key << 1) >> 1) % capacity; 130 for (e = table[index]; e != NULL; e = e->next) { 131#ifdef DEBUG 132 m_collisions++; 133#endif 134 if (e->hash == (INT_PTR)key && e->key == key) { 135 void* old = e->value; 136 e->value = value; 137 return old; 138 } 139 } 140 141 if (count >= threshold) { 142 // Rehash the table if the threshold is exceeded 143 rehash(); 144 return put(key, value); 145 } 146 147 // Creates the new entry. 148 e = new HashtableEntry; 149 e->hash = (INT_PTR)key; 150 e->key = key; 151 e->value = value; 152 e->next = table[index]; 153 table[index] = e; 154 count++; 155#ifdef DEBUG 156 if (count > m_max) { 157 m_max = count; 158 } 159#endif 160 return NULL; 161} 162 163void* Hashtable::remove(void* key) { 164 CriticalSection::Lock l(lock); 165 int index = (int)(((INT_PTR)key << 1) >> 1) % capacity; 166 HashtableEntry* prev = NULL; 167 for (HashtableEntry* e = table[index]; e != NULL ; prev = e, e = e->next) { 168 if (e->key == key) { 169 void* value = e->value; 170 if (prev != NULL) { 171 prev->next = e->next; 172 } else { 173 table[index] = e->next; 174 } 175 count--; 176 delete e; 177 return value; 178 } 179 } 180 return NULL; 181} 182 183void Hashtable::clear() { 184 CriticalSection::Lock l(lock); 185 for (int index = capacity; --index >= 0; ) { 186 HashtableEntry* e = table[index]; 187 while (e != NULL) { 188 HashtableEntry* next = e->next; 189 if (m_deleteProc) { 190 (*m_deleteProc)(e->value); 191 } 192 delete e; 193 e = next; 194 } 195 table[index] = NULL; 196 } 197 count = 0; 198} 199 200HashtableEnumerator::HashtableEnumerator(HashtableEntry* table[], int size, 201 BOOL keys) 202{ 203 this->table = table; 204 this->keys = keys; 205 this->index = size; 206 this->entry = NULL; 207} 208 209BOOL HashtableEnumerator::hasMoreElements() { 210 if (entry != NULL) { 211 return TRUE; 212 } 213 while (index-- > 0) { 214 if ((entry = table[index]) != NULL) { 215 return TRUE; 216 } 217 } 218 return FALSE; 219} 220 221void* HashtableEnumerator::nextElement() { 222 if (entry == NULL) { 223 while ((index-- > 0) && ((entry = table[index]) == NULL)); 224 } 225 if (entry != NULL) { 226 HashtableEntry* e = entry; 227 entry = e->next; 228 return keys ? e->key : e->value; 229 } 230 DASSERT(FALSE); // shouldn't get here 231 return NULL; 232} 233