1 /* 2 * Copyright (c) 1996, 2002, 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 #ifndef HASHTABLE_H 27 #define HASHTABLE_H 28 29 #include "awt.h" 30 #include "awt_Toolkit.h" 31 32 struct HashtableEntry { 33 INT_PTR hash; 34 void* key; 35 void* value; 36 HashtableEntry* next; 37 }; 38 39 class HashtableEnumerator { 40 private: 41 BOOL keys; 42 int index; 43 HashtableEntry** table; 44 HashtableEntry* entry; 45 46 public: 47 HashtableEnumerator(HashtableEntry* table[], int size, BOOL keys); 48 BOOL hasMoreElements(); 49 void* nextElement(); 50 }; 51 52 /** 53 * Hashtable class. Maps keys to values. Any object can be used as 54 * a key and/or value. As you might guess, this was brazenly stolen 55 * from java.util.Hashtable. 56 */ 57 class Hashtable { 58 protected: 59 /* 60 * The hash table data. 61 */ 62 HashtableEntry** table; 63 64 /* 65 * The size of table 66 */ 67 int capacity; 68 69 /* 70 * The total number of entries in the hash table. 71 */ 72 int count; 73 74 /** 75 * Rehashes the table when count exceeds this threshold. 76 */ 77 int threshold; 78 79 /** 80 * The load factor for the hashtable. 81 */ 82 float loadFactor; 83 84 /** 85 * Our C++ synchronizer. 86 */ 87 CriticalSection lock; 88 89 /** 90 * Element deletion routine, if any. 91 */ 92 void (*m_deleteProc)(void*); 93 94 #ifdef DEBUG 95 char* m_name; 96 int m_max; 97 int m_collisions; 98 #endif 99 100 public: 101 /** 102 * Constructs a new, empty hashtable with the specified initial 103 * capacity and the specified load factor. 104 */ 105 Hashtable(const char* name, void (*deleteProc)(void*) = NULL, 106 int initialCapacity = 29, float loadFactor = 0.75); 107 108 virtual ~Hashtable(); 109 110 /** 111 * Returns the number of elements contained in the hashtable. 112 */ size()113 INLINE int size() { 114 return count; 115 } 116 117 /** 118 * Returns true if the hashtable contains no elements. 119 */ isEmpty()120 INLINE BOOL isEmpty() { 121 return count == 0; 122 } 123 124 /** 125 * Returns an enumeration of the hashtable's keys. 126 */ keys()127 INLINE HashtableEnumerator* keys() { 128 CriticalSection::Lock l(lock); 129 return new HashtableEnumerator(table, capacity, TRUE); 130 } 131 132 /** 133 * Returns an enumeration of the elements. Use the Enumeration methods 134 * on the returned object to fetch the elements sequentially. 135 */ elements()136 INLINE HashtableEnumerator* elements() { 137 CriticalSection::Lock l(lock); 138 return new HashtableEnumerator(table, capacity, FALSE); 139 } 140 141 /** 142 * Returns true if the specified object is an element of the hashtable. 143 * This operation is more expensive than the containsKey() method. 144 */ 145 BOOL contains(void* value); 146 147 /** 148 * Returns true if the collection contains an element for the key. 149 */ 150 BOOL containsKey(void* key); 151 152 /** 153 * Gets the object associated with the specified key in the 154 * hashtable. 155 */ 156 void* get(void* key); 157 158 /** 159 * Puts the specified element into the hashtable, using the specified 160 * key. The element may be retrieved by doing a get() with the same key. 161 * The key and the element cannot be null. 162 */ 163 virtual void* put(void* key, void* value); 164 165 /** 166 * Removes the element corresponding to the key. Does nothing if the 167 * key is not present. 168 */ 169 void* remove(void* key); 170 171 /** 172 * Clears the hash table so that it has no more elements in it. 173 */ 174 void clear(); 175 176 protected: 177 /** 178 * Rehashes the content of the table into a bigger table. 179 * This method is called automatically when the hashtable's 180 * size exceeds the threshold. 181 */ 182 void rehash(); 183 }; 184 185 #endif // HASHTABLE_H 186