1
/*******************************************************************************
2
* Copyright (c) 2004, 2008 IBM Corporation and others.
3
* All rights reserved. This program and the accompanying materials
4
* are made available under the terms of the Eclipse Public License v1.0
5
* which accompanies this distribution, and is available at
6
* http://www.eclipse.org/legal/epl-v10.html
9
* IBM Corporation - initial API and implementation
10
*******************************************************************************/
12
package org.eclipse.cdt.core.parser.util;
14
import java.util.Comparator;
19
public class HashTable implements Cloneable {
20
protected static final int minHashSize = 2;
21
protected int currEntry = -1;
23
public boolean isEmpty() {
24
return currEntry == -1;
27
final public int size() {
31
protected int[] hashTable;
32
protected int[] nextTable;
34
public HashTable(int initialSize) {
36
while (size < initialSize)
39
if (size > minHashSize) {
40
hashTable = new int[size * 2];
41
nextTable = new int[size];
49
public Object clone() {
50
HashTable newTable = null;
52
newTable = (HashTable) super.clone();
53
} catch (CloneNotSupportedException e) {
54
//shouldn't happen because object supports clone.
58
int size = capacity();
60
if (hashTable != null) {
61
newTable.hashTable = new int[size * 2];
62
newTable.nextTable = new int[size];
63
System.arraycopy(hashTable, 0, newTable.hashTable, 0, hashTable.length);
64
System.arraycopy(nextTable, 0, newTable.nextTable, 0, nextTable.length);
66
newTable.currEntry = currEntry;
70
protected void resize() {
71
resize(capacity() << 1);
78
if (hashTable == null)
81
for (int i = 0; i < capacity(); i++) {
83
hashTable[2 * i + 1] = 0;
87
protected void rehash() {
88
if (nextTable == null)
91
// clear the table (don't call clear() or else the subclasses stuff will be cleared too)
92
for (int i = 0; i < capacity(); i++) {
94
hashTable[2 * i + 1] = 0;
97
// Need to rehash everything
98
for (int i = 0; i <= currEntry; ++i) {
99
linkIntoHashTable(i, hash(i));
102
protected void resize(int size) {
103
if (size > minHashSize) {
104
hashTable = new int[size * 2];
105
nextTable = new int[size];
107
// Need to rehash everything
108
for (int i = 0; i <= currEntry; ++i) {
109
linkIntoHashTable(i, hash(i));
114
protected int hash(int pos) {
115
// return the hash value of the element in the key table
116
throw new UnsupportedOperationException();
119
protected void linkIntoHashTable(int i, int hash) {
120
if (nextTable == null)
123
if (hashTable[hash] == 0) {
124
hashTable[hash] = i + 1;
127
int j = hashTable[hash] - 1;
128
while (nextTable[j] != 0) {
129
// if (nextTable[j] - 1 == j) {
132
j = nextTable[j] - 1;
134
nextTable[j] = i + 1;
138
final public int capacity() {
139
if (nextTable == null)
141
return nextTable.length;
144
protected void removeEntry(int i, int hash) {
145
if (nextTable == null) {
150
// Remove the hash entry
151
if (hashTable[hash] == i + 1) {
152
hashTable[hash] = nextTable[i];
154
// find entry pointing to me
155
int j = hashTable[hash] - 1;
156
while (nextTable[j] != 0 && nextTable[j] != i + 1)
157
j = nextTable[j] - 1;
158
nextTable[j] = nextTable[i];
162
// shift everything over
163
System.arraycopy(nextTable, i + 1, nextTable, i, currEntry - i);
165
// adjust hash and next entries for things that moved
166
for (int j = 0; j < hashTable.length; ++j) {
167
if (hashTable[j] > i + 1)
171
for (int j = 0; j < nextTable.length; ++j) {
172
if (nextTable[j] > i + 1)
177
// last entry is now free
178
nextTable[currEntry] = 0;
182
final public void sort(Comparator<Object> c) {
184
quickSort(c, 0, size() - 1);
188
final private void quickSort(Comparator<Object> c, int p, int r) {
190
int q = partition(c, p, r);
191
if (p < q) quickSort(c, p, q);
192
if (++q < r) quickSort(c, q, r);
196
protected int partition(Comparator<Object> c, int p, int r) {
197
throw new UnsupportedOperationException();
200
public void dumpNexts() {
201
if (nextTable == null)
204
for (int i = 0; i < nextTable.length; ++i) {
205
if (nextTable[i] == 0)
210
for (int j = nextTable[i] - 1; j >= 0; j = nextTable[j] - 1)
211
System.out.print(" -> " + j); //$NON-NLS-1$
213
System.out.println(""); //$NON-NLS-1$