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 |