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