001: /* Copyright (C) 2004 - 2007 db4objects Inc. http://www.db4o.com
002:
003: This file is part of the db4o open source object database.
004:
005: db4o is free software; you can redistribute it and/or modify it under
006: the terms of version 2 of the GNU General Public License as published
007: by the Free Software Foundation and as clarified by db4objects' GPL
008: interpretation policy, available at
009: http://www.db4o.com/about/company/legalpolicies/gplinterpretation/
010: Alternatively you can write to db4objects, Inc., 1900 S Norfolk Street,
011: Suite 350, San Mateo, CA 94403, USA.
012:
013: db4o is distributed in the hope that it will be useful, but WITHOUT ANY
014: WARRANTY; without even the implied warranty of MERCHANTABILITY or
015: FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
016: for more details.
017:
018: You should have received a copy of the GNU General Public License along
019: with this program; if not, write to the Free Software Foundation, Inc.,
020: 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
021: package com.db4o.foundation;
022:
023: /**
024: * @exclude
025: */
026: public class Hashtable4 implements DeepClone {
027:
028: private static final float FILL = 0.5F;
029:
030: // FIELDS ARE PUBLIC SO THEY CAN BE REFLECTED ON IN JDKs <= 1.1
031:
032: public int _tableSize;
033:
034: public int _mask;
035:
036: public int _maximumSize;
037:
038: public int _size;
039:
040: public HashtableIntEntry[] _table;
041:
042: public Hashtable4(int size) {
043: size = newSize(size); // legacy for .NET conversion
044: _tableSize = 1;
045: while (_tableSize < size) {
046: _tableSize = _tableSize << 1;
047: }
048: _mask = _tableSize - 1;
049: _maximumSize = (int) (_tableSize * FILL);
050: _table = new HashtableIntEntry[_tableSize];
051: }
052:
053: public Hashtable4() {
054: this (1);
055: }
056:
057: /** @param cloneOnlyCtor */
058: protected Hashtable4(DeepClone cloneOnlyCtor) {
059: }
060:
061: public int size() {
062: return _size;
063: }
064:
065: public Object deepClone(Object obj) {
066: return deepCloneInternal(new Hashtable4((DeepClone) null), obj);
067: }
068:
069: public void forEachKeyForIdentity(Visitor4 visitor, Object obj) {
070: for (int i = 0; i < _table.length; i++) {
071: HashtableIntEntry entry = _table[i];
072: while (entry != null) {
073: if (entry._object == obj) {
074: visitor.visit(entry.key());
075: }
076: entry = entry._next;
077: }
078: }
079: }
080:
081: public Object get(byte[] key) {
082: int intKey = HashtableByteArrayEntry.hash(key);
083: return getFromObjectEntry(intKey, key);
084: }
085:
086: public Object get(int key) {
087: HashtableIntEntry entry = _table[key & _mask];
088: while (entry != null) {
089: if (entry._key == key) {
090: return entry._object;
091: }
092: entry = entry._next;
093: }
094: return null;
095: }
096:
097: public Object get(Object key) {
098: if (key == null) {
099: return null;
100: }
101: return getFromObjectEntry(key.hashCode(), key);
102: }
103:
104: /**
105: * Iterates through all the {@link Entry4 entries}.
106: *
107: * @return {@link Entry4} iterator
108: */
109: public Iterator4 iterator() {
110: return new HashtableIterator(_table);
111: }
112:
113: /**
114: * Iterates through all the keys.
115: *
116: * @return key iterator
117: */
118: public Iterator4 keys() {
119: return Iterators.map(iterator(), new Function4() {
120: public Object apply(Object current) {
121: return ((Entry4) current).key();
122: }
123: });
124: }
125:
126: /**
127: * Iterates through all the values.
128: *
129: * @return value iterator
130: */
131: public Iterator4 values() {
132: return Iterators.map(iterator(), new Function4() {
133: public Object apply(Object current) {
134: return ((Entry4) current).value();
135: }
136: });
137: }
138:
139: public boolean containsKey(Object key) {
140: if (null == key) {
141: return false;
142: }
143: return null != getObjectEntry(key.hashCode(), key);
144: }
145:
146: public void put(byte[] key, Object value) {
147: putEntry(new HashtableByteArrayEntry(key, value));
148: }
149:
150: public void put(int key, Object value) {
151: putEntry(new HashtableIntEntry(key, value));
152: }
153:
154: public void put(Object key, Object value) {
155: if (null == key) {
156: throw new ArgumentNullException();
157: }
158: putEntry(new HashtableObjectEntry(key, value));
159: }
160:
161: public Object remove(byte[] key) {
162: int intKey = HashtableByteArrayEntry.hash(key);
163: return removeObjectEntry(intKey, key);
164: }
165:
166: public void remove(int key) {
167: HashtableIntEntry entry = _table[key & _mask];
168: HashtableIntEntry predecessor = null;
169: while (entry != null) {
170: if (entry._key == key) {
171: removeEntry(predecessor, entry);
172: return;
173: }
174: predecessor = entry;
175: entry = entry._next;
176: }
177: }
178:
179: public void remove(Object objectKey) {
180: int intKey = objectKey.hashCode();
181: removeObjectEntry(intKey, objectKey);
182: }
183:
184: protected Hashtable4 deepCloneInternal(Hashtable4 ret, Object obj) {
185: ret._mask = _mask;
186: ret._maximumSize = _maximumSize;
187: ret._size = _size;
188: ret._tableSize = _tableSize;
189: ret._table = new HashtableIntEntry[_tableSize];
190: for (int i = 0; i < _tableSize; i++) {
191: if (_table[i] != null) {
192: ret._table[i] = (HashtableIntEntry) _table[i]
193: .deepClone(obj);
194: }
195: }
196: return ret;
197: }
198:
199: private int entryIndex(HashtableIntEntry entry) {
200: return entry._key & _mask;
201: }
202:
203: private HashtableIntEntry findWithSameKey(HashtableIntEntry newEntry) {
204: HashtableIntEntry existing = _table[entryIndex(newEntry)];
205: while (null != existing) {
206: if (existing.sameKeyAs(newEntry)) {
207: return existing;
208: }
209: existing = existing._next;
210: }
211: return null;
212: }
213:
214: private Object getFromObjectEntry(int intKey, Object objectKey) {
215: final HashtableObjectEntry entry = getObjectEntry(intKey,
216: objectKey);
217: return entry == null ? null : entry._object;
218: }
219:
220: private HashtableObjectEntry getObjectEntry(int intKey,
221: Object objectKey) {
222: HashtableObjectEntry entry = (HashtableObjectEntry) _table[intKey
223: & _mask];
224: while (entry != null) {
225: if (entry._key == intKey && entry.hasKey(objectKey)) {
226: return entry;
227: }
228: entry = (HashtableObjectEntry) entry._next;
229: }
230: return null;
231: }
232:
233: private void increaseSize() {
234: _tableSize = _tableSize << 1;
235: _maximumSize = _maximumSize << 1;
236: _mask = _tableSize - 1;
237: HashtableIntEntry[] temp = _table;
238: _table = new HashtableIntEntry[_tableSize];
239: for (int i = 0; i < temp.length; i++) {
240: reposition(temp[i]);
241: }
242: }
243:
244: private void insert(HashtableIntEntry newEntry) {
245: _size++;
246: if (_size > _maximumSize) {
247: increaseSize();
248: }
249: int index = entryIndex(newEntry);
250: newEntry._next = _table[index];
251: _table[index] = newEntry;
252: }
253:
254: private final int newSize(int size) {
255: return (int) (size / FILL);
256: }
257:
258: private void putEntry(HashtableIntEntry newEntry) {
259: HashtableIntEntry existing = findWithSameKey(newEntry);
260: if (null != existing) {
261: replace(existing, newEntry);
262: } else {
263: insert(newEntry);
264: }
265: }
266:
267: private void removeEntry(HashtableIntEntry predecessor,
268: HashtableIntEntry entry) {
269: if (predecessor != null) {
270: predecessor._next = entry._next;
271: } else {
272: _table[entryIndex(entry)] = entry._next;
273: }
274: _size--;
275: }
276:
277: private Object removeObjectEntry(int intKey, Object objectKey) {
278: HashtableObjectEntry entry = (HashtableObjectEntry) _table[intKey
279: & _mask];
280: HashtableObjectEntry predecessor = null;
281: while (entry != null) {
282: if (entry._key == intKey && entry.hasKey(objectKey)) {
283: removeEntry(predecessor, entry);
284: return entry._object;
285: }
286: predecessor = entry;
287: entry = (HashtableObjectEntry) entry._next;
288: }
289: return null;
290: }
291:
292: private void replace(HashtableIntEntry existing,
293: HashtableIntEntry newEntry) {
294: newEntry._next = existing._next;
295: HashtableIntEntry entry = _table[entryIndex(existing)];
296: if (entry == existing) {
297: _table[entryIndex(existing)] = newEntry;
298: } else {
299: while (entry._next != existing) {
300: entry = entry._next;
301: }
302: entry._next = newEntry;
303: }
304: }
305:
306: private void reposition(HashtableIntEntry entry) {
307: if (entry != null) {
308: reposition(entry._next);
309: entry._next = _table[entryIndex(entry)];
310: _table[entryIndex(entry)] = entry;
311: }
312: }
313: }
|