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