|
1
21 package com.db4o.foundation;
22
23
24
27 public class Hashtable4 implements DeepClone {
28
29 private static final float FILL = 0.5F;
30
31 private int i_tableSize;
32
33 private int i_mask;
34
35 private int i_maximumSize;
36
37 private int i_size;
38
39 private HashtableIntEntry[] i_table;
40
41 public Hashtable4(int a_size) {
42 a_size = newSize(a_size); i_tableSize = 1;
44 while (i_tableSize < a_size) {
45 i_tableSize = i_tableSize << 1;
46 }
47 i_mask = i_tableSize - 1;
48 i_maximumSize = (int) (i_tableSize * FILL);
49 i_table = new HashtableIntEntry[i_tableSize];
50 }
51
52 public Hashtable4() {
53 this(1);
54 }
55
56 protected Hashtable4(DeepClone cloneOnlyCtor) {
57 }
58
59 public int size() {
60 return i_size;
61 }
62
63 public Object  deepClone(Object obj) {
64 return deepCloneInternal(new Hashtable4((DeepClone)null), obj);
65 }
66
67 public void forEachKey(Visitor4 visitor) {
68 for (int i = 0; i < i_table.length; i++) {
69 HashtableIntEntry entry = i_table[i];
70 while (entry != null) {
71 entry.acceptKeyVisitor(visitor);
72 entry = entry.i_next;
73 }
74 }
75 }
76
77 public void forEachKeyForIdentity(Visitor4 visitor, Object a_identity) {
78 for (int i = 0; i < i_table.length; i++) {
79 HashtableIntEntry entry = i_table[i];
80 while (entry != null) {
81 if (entry.i_object == a_identity) {
82 entry.acceptKeyVisitor(visitor);
83 }
84 entry = entry.i_next;
85 }
86 }
87 }
88
89 public void forEachValue(Visitor4 visitor) {
90 for (int i = 0; i < i_table.length; i++) {
91 HashtableIntEntry entry = i_table[i];
92 while (entry != null) {
93 visitor.visit(entry.i_object);
94 entry = entry.i_next;
95 }
96 }
97 }
98
99 public Object get(byte[] key) {
100 int intKey = HashtableByteArrayEntry.hash(key);
101 return getFromObjectEntry(intKey, key);
102 }
103
104 public Object get(int key) {
105 HashtableIntEntry entry = i_table[key & i_mask];
106 while (entry != null) {
107 if (entry.i_key == key) {
108 return entry.i_object;
109 }
110 entry = entry.i_next;
111 }
112 return null;
113 }
114
115 public Object get(Object key) {
116 if (key == null) {
117 return null;
118 }
119 return getFromObjectEntry(key.hashCode(), key);
120 }
121
122 public boolean containsKey(Object key) {
123 if (null == key) {
124 return false;
125 }
126 return null != getObjectEntry(key.hashCode(), key);
127 }
128
129 public void put(byte[] key, Object value) {
130 putEntry(new HashtableByteArrayEntry(key, value));
131 }
132
133 public void put(int key, Object value) {
134 putEntry(new HashtableIntEntry(key, value));
135 }
136
137 public void put(Object key, Object value) {
138 putEntry(new HashtableObjectEntry(key, value));
139 }
140
141 public Object remove(byte[] key) {
142 int intKey = HashtableByteArrayEntry.hash(key);
143 return removeObjectEntry(intKey, key);
144 }
145
146 public void remove(int a_key) {
147 HashtableIntEntry entry = i_table[a_key & i_mask];
148 HashtableIntEntry predecessor = null;
149 while (entry != null) {
150 if (entry.i_key == a_key) {
151 removeEntry(predecessor, entry);
152 return;
153 }
154 predecessor = entry;
155 entry = entry.i_next;
156 }
157 }
158
159 public void remove(Object objectKey) {
160 int intKey = objectKey.hashCode();
161 removeObjectEntry(intKey, objectKey);
162 }
163
164 protected Hashtable4 deepCloneInternal(Hashtable4 ret, Object obj) {
165 ret.i_mask = i_mask;
166 ret.i_maximumSize = i_maximumSize;
167 ret.i_size = i_size;
168 ret.i_tableSize = i_tableSize;
169 ret.i_table = new HashtableIntEntry[i_tableSize];
170 for (int i = 0; i < i_tableSize; i++) {
171 if (i_table[i] != null) {
172 ret.i_table[i] = (HashtableIntEntry) i_table[i].deepClone(obj);
173 }
174 }
175 return ret;
176 }
177
178 private int entryIndex(HashtableIntEntry entry) {
179 return entry.i_key & i_mask;
180 }
181
182 private HashtableIntEntry findWithSameKey(HashtableIntEntry newEntry) {
183 HashtableIntEntry existing = i_table[entryIndex(newEntry)];
184 while (null != existing) {
185 if (existing.sameKeyAs(newEntry)) {
186 return existing;
187 }
188 existing = existing.i_next;
189 }
190 return null;
191 }
192
193 private Object getFromObjectEntry(int intKey, Object objectKey) {
194 final HashtableObjectEntry entry = getObjectEntry(intKey, objectKey);
195 return entry == null ? null : entry.i_object;
196 }
197
198 private HashtableObjectEntry getObjectEntry(int intKey, Object objectKey) {
199 HashtableObjectEntry entry = (HashtableObjectEntry) i_table[intKey & i_mask];
200 while (entry != null) {
201 if (entry.i_key == intKey && entry.hasKey(objectKey)) {
202 return entry;
203 }
204 entry = (HashtableObjectEntry) entry.i_next;
205 }
206 return null;
207 }
208
209 private void increaseSize() {
210 i_tableSize = i_tableSize << 1;
211 i_maximumSize = i_maximumSize << 1;
212 i_mask = i_tableSize - 1;
213 HashtableIntEntry[] temp = i_table;
214 i_table = new HashtableIntEntry[i_tableSize];
215 for (int i = 0; i < temp.length; i++) {
216 reposition(temp[i]);
217 }
218 }
219
220 private void insert(HashtableIntEntry newEntry) {
221 i_size++;
222 if (i_size > i_maximumSize) {
223 increaseSize();
224 }
225 int index = entryIndex(newEntry);
226 newEntry.i_next = i_table[index];
227 i_table[index] = newEntry;
228 }
229
230 private final int newSize(int a_size) {
231 return (int) (a_size / FILL);
232 }
233
234 private void putEntry(HashtableIntEntry newEntry) {
235 HashtableIntEntry existing = findWithSameKey(newEntry);
236 if (null != existing) {
237 replace(existing, newEntry);
238 } else {
239 insert(newEntry);
240 }
241 }
242
243 private void removeEntry(HashtableIntEntry predecessor, HashtableIntEntry entry) {
244 if (predecessor != null) {
245 predecessor.i_next = entry.i_next;
246 } else {
247 i_table[entryIndex(entry)] = entry.i_next;
248 }
249 i_size--;
250 }
251
252 private Object removeObjectEntry(int intKey, Object objectKey) {
253 HashtableObjectEntry entry = (HashtableObjectEntry) i_table[intKey & i_mask];
254 HashtableObjectEntry predecessor = null;
255 while (entry != null) {
256 if (entry.i_key == intKey && entry.hasKey(objectKey)) {
257 removeEntry(predecessor, entry);
258 return entry.i_object;
259 }
260 predecessor = entry;
261 entry = (HashtableObjectEntry) entry.i_next;
262 }
263 return null;
264 }
265
266 private void replace(HashtableIntEntry existing, HashtableIntEntry newEntry) {
267 newEntry.i_next = existing.i_next;
268 HashtableIntEntry entry = i_table[entryIndex(existing)];
269 if (entry == existing) {
270 i_table[entryIndex(existing)] = newEntry;
271 } else {
272 while (entry.i_next != existing) {
273 entry = entry.i_next;
274 }
275 entry.i_next = newEntry;
276 }
277 }
278
279 private void reposition(HashtableIntEntry a_entry) {
280 if (a_entry != null) {
281 reposition(a_entry.i_next);
282 a_entry.i_next = i_table[entryIndex(a_entry)];
283 i_table[entryIndex(a_entry)] = a_entry;
284 }
285 }
286 }
287 |
Popular Tags |
Java API By Example, From Geeks To Geeks.