FIX: added missing org.eclipse.pde.runtime_3.1.1.jar reference
[phpeclipse.git] / net.sourceforge.phpeclipse / src / net / sourceforge / phpdt / internal / compiler / util / HashtableOfObject.java
1 /*******************************************************************************
2  * Copyright (c) 2000, 2003 IBM Corporation and others.
3  * All rights reserved. This program and the accompanying materials 
4  * are made available under the terms of the Common Public License v1.0
5  * which accompanies this distribution, and is available at
6  * http://www.eclipse.org/legal/cpl-v10.html
7  * 
8  * Contributors:
9  *     IBM Corporation - initial API and implementation
10  *******************************************************************************/
11 package net.sourceforge.phpdt.internal.compiler.util;
12
13 import net.sourceforge.phpdt.core.compiler.CharOperation;
14
15 /**
16  * Hashtable of {char[] --> Object }
17  */
18 public final class HashtableOfObject implements Cloneable {
19         
20         // to avoid using Enumerations, walk the individual tables skipping nulls
21         public char[] keyTable[];
22         public Object valueTable[];
23
24         public int elementSize; // number of elements in the table
25         int threshold;
26
27         public HashtableOfObject() {
28                 this(13);
29         }
30
31         public HashtableOfObject(int size) {
32
33                 this.elementSize = 0;
34                 this.threshold = size; // size represents the expected number of elements
35                 int extraRoom = (int) (size * 1.75f);
36                 if (this.threshold == extraRoom)
37                         extraRoom++;
38                 this.keyTable = new char[extraRoom][];
39                 this.valueTable = new Object[extraRoom];
40         }
41
42         public Object clone() throws CloneNotSupportedException {
43                 HashtableOfObject result = (HashtableOfObject) super.clone();
44                 result.elementSize = this.elementSize;
45                 result.threshold = this.threshold;
46
47                 int length = this.keyTable.length;
48                 result.keyTable = new char[length][];
49                 System.arraycopy(this.keyTable, 0, result.keyTable, 0, length);
50
51                 length = this.valueTable.length;
52                 result.valueTable = new Object[length];
53                 System.arraycopy(this.valueTable, 0, result.valueTable, 0, length);
54                 return result;
55         }
56
57         public boolean containsKey(char[] key) {
58
59                 int index = CharOperation.hashCode(key) % valueTable.length;
60                 int keyLength = key.length;
61                 char[] currentKey;
62                 while ((currentKey = keyTable[index]) != null) {
63                         if (currentKey.length == keyLength
64                                 && CharOperation.prefixEquals(currentKey, key))
65                                 return true;
66                         index = (index + 1) % keyTable.length;
67                 }
68                 return false;
69         }
70
71         public Object get(char[] key) {
72
73                 int index = CharOperation.hashCode(key) % valueTable.length;
74                 int keyLength = key.length;
75                 char[] currentKey;
76                 while ((currentKey = keyTable[index]) != null) {
77                         if (currentKey.length == keyLength
78                                 && CharOperation.prefixEquals(currentKey, key))
79                                 return valueTable[index];
80                         index = (index + 1) % keyTable.length;
81                 }
82                 return null;
83         }
84
85         public Object put(char[] key, Object value) {
86
87                 int index = CharOperation.hashCode(key) % valueTable.length;
88                 int keyLength = key.length;
89                 char[] currentKey;
90                 while ((currentKey = keyTable[index]) != null) {
91                         if (currentKey.length == keyLength
92                                 && CharOperation.prefixEquals(currentKey, key))
93                                 return valueTable[index] = value;
94                         index = (index + 1) % keyTable.length;
95                 }
96                 keyTable[index] = key;
97                 valueTable[index] = value;
98
99                 // assumes the threshold is never equal to the size of the table
100                 if (++elementSize > threshold)
101                         rehash();
102                 return value;
103         }
104
105         public Object removeKey(char[] key) {
106
107                 int index = CharOperation.hashCode(key) % valueTable.length;
108                 int keyLength = key.length;
109                 char[] currentKey;
110                 while ((currentKey = keyTable[index]) != null) {
111                         if (currentKey.length == keyLength
112                                 && CharOperation.prefixEquals(currentKey, key)) {
113                                         Object value = valueTable[index];
114                                         elementSize--;
115                                         keyTable[index] = null;
116                                         valueTable[index] = null;
117                                         rehash();
118                                         return value;
119                                 }
120                         index = (index + 1) % keyTable.length;
121                 }
122                 return null;
123         }
124
125         private void rehash() {
126
127                 HashtableOfObject newHashtable = new HashtableOfObject(elementSize * 2);                // double the number of expected elements
128                 char[] currentKey;
129                 for (int i = keyTable.length; --i >= 0;)
130                         if ((currentKey = keyTable[i]) != null)
131                                 newHashtable.put(currentKey, valueTable[i]);
132
133                 this.keyTable = newHashtable.keyTable;
134                 this.valueTable = newHashtable.valueTable;
135                 this.threshold = newHashtable.threshold;
136         }
137
138         public int size() {
139                 return elementSize;
140         }
141
142         public String toString() {
143                 String s = ""; //$NON-NLS-1$
144                 Object object;
145                 for (int i = 0, length = valueTable.length; i < length; i++)
146                         if ((object = valueTable[i]) != null)
147                                 s += new String(keyTable[i]) + " -> " + object.toString() + "\n";       //$NON-NLS-2$ //$NON-NLS-1$
148                 return s;
149         }
150 }