0001: /* Copyright (c) 2001-2005, The HSQL Development Group
0002: * All rights reserved.
0003: *
0004: * Redistribution and use in source and binary forms, with or without
0005: * modification, are permitted provided that the following conditions are met:
0006: *
0007: * Redistributions of source code must retain the above copyright notice, this
0008: * list of conditions and the following disclaimer.
0009: *
0010: * Redistributions in binary form must reproduce the above copyright notice,
0011: * this list of conditions and the following disclaimer in the documentation
0012: * and/or other materials provided with the distribution.
0013: *
0014: * Neither the name of the HSQL Development Group nor the names of its
0015: * contributors may be used to endorse or promote products derived from this
0016: * software without specific prior written permission.
0017: *
0018: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
0019: * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
0020: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
0021: * ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG,
0022: * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
0023: * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
0024: * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
0025: * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
0026: * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
0027: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
0028: * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
0029: */
0030:
0031: package org.hsqldb.store;
0032:
0033: import java.util.NoSuchElementException;
0034:
0035: import org.hsqldb.lib.ArrayCounter;
0036:
0037: public class BaseHashMap {
0038:
0039: /**
0040: * Base class for hash tables or sets. The exact type of the structure is
0041: * defined by the constructor. Each instance has at least a keyTable array
0042: * and a HashIndex instance for looking up the keys into this table. Instances
0043: * that are maps also have a valueTable the same size as the keyTable.
0044: *
0045: * Special getOrAddXXX() methods are used for object maps in some subclasses.
0046: *
0047: * @author fredt@users
0048: * @version 1.8.0
0049: * @since 1.7.2
0050: */
0051: /*
0052:
0053: data store:
0054: keys: {array of primitive | array of object}
0055: values: {none | array of primitive | array of object} same size as keys
0056: objects support : hashCode(), equals()
0057:
0058: implemented types of keyTable:
0059: {objectKeyTable: variable size Object[] array for keys |
0060: intKeyTable: variable size int[] for keys |
0061: longKeyTable: variable size long[] for keys }
0062:
0063: implemented types of valueTable:
0064: {objectValueTable: variable size Object[] array for values |
0065: intValueTable: variable size int[] for values |
0066: longValueTable: variable size long[] for values}
0067:
0068: valueTable does not exist for sets or for object pools
0069:
0070: hash index:
0071: hashTable: fixed size int[] array for hash lookup into keyTable
0072: linkTable: pointer to the next key ; size equal or larger than hashTable
0073: but equal to the valueTable
0074:
0075: access count table:
0076: {none |
0077: variable size int[] array for access count} same size as xxxKeyTable
0078: */
0079:
0080: //
0081: boolean isIntKey;
0082: boolean isLongKey;
0083: boolean isObjectKey;
0084: boolean isNoValue;
0085: boolean isIntValue;
0086: boolean isLongValue;
0087: boolean isObjectValue;
0088:
0089: //
0090: protected HashIndex hashIndex;
0091:
0092: //
0093: protected int[] intKeyTable;
0094: protected Object[] objectKeyTable;
0095: protected long[] longKeyTable;
0096:
0097: //
0098: protected int[] intValueTable;
0099: protected Object[] objectValueTable;
0100: protected long[] longValueTable;
0101:
0102: //
0103: int accessMin;
0104: int accessCount;
0105: int[] accessTable;
0106:
0107: //
0108: final float loadFactor;
0109: final int initialCapacity;
0110: int threshold;
0111: int maxCapacity;
0112: protected int purgePolicy = NO_PURGE;
0113: protected boolean minimizeOnEmpty;
0114:
0115: //
0116: boolean hasZeroKey;
0117: int zeroKeyIndex = -1;
0118:
0119: // keyOrValueTypes
0120: protected static final int noKeyOrValue = 0;
0121: protected static final int intKeyOrValue = 1;
0122: protected static final int longKeyOrValue = 2;
0123: protected static final int objectKeyOrValue = 3;
0124:
0125: // purgePolicy
0126: protected static final int NO_PURGE = 0;
0127: protected static final int PURGE_ALL = 1;
0128: protected static final int PURGE_HALF = 2;
0129: protected static final int PURGE_QUARTER = 3;
0130:
0131: protected BaseHashMap(int initialCapacity, float loadFactor,
0132: int keyType, int valueType, boolean hasAccessCount)
0133: throws IllegalArgumentException {
0134:
0135: if (initialCapacity <= 0 || loadFactor <= 0.0) {
0136: throw new IllegalArgumentException();
0137: }
0138:
0139: this .loadFactor = loadFactor;
0140: this .initialCapacity = initialCapacity;
0141: threshold = initialCapacity;
0142:
0143: if (threshold < 3) {
0144: threshold = 3;
0145: }
0146:
0147: int hashtablesize = (int) (initialCapacity * loadFactor);
0148:
0149: if (hashtablesize < 3) {
0150: hashtablesize = 3;
0151: }
0152:
0153: hashIndex = new HashIndex(hashtablesize, initialCapacity, true);
0154:
0155: int arraySize = threshold;
0156:
0157: if (keyType == BaseHashMap.intKeyOrValue) {
0158: isIntKey = true;
0159: intKeyTable = new int[arraySize];
0160: } else if (keyType == BaseHashMap.objectKeyOrValue) {
0161: isObjectKey = true;
0162: objectKeyTable = new Object[arraySize];
0163: } else {
0164: isLongKey = true;
0165: longKeyTable = new long[arraySize];
0166: }
0167:
0168: if (valueType == BaseHashMap.intKeyOrValue) {
0169: isIntValue = true;
0170: intValueTable = new int[arraySize];
0171: } else if (valueType == BaseHashMap.objectKeyOrValue) {
0172: isObjectValue = true;
0173: objectValueTable = new Object[arraySize];
0174: } else if (valueType == BaseHashMap.longKeyOrValue) {
0175: isLongValue = true;
0176: longValueTable = new long[arraySize];
0177: } else {
0178: isNoValue = true;
0179: }
0180:
0181: if (hasAccessCount) {
0182: accessTable = new int[arraySize];
0183: }
0184: }
0185:
0186: protected int getLookup(Object key, int hash) {
0187:
0188: int lookup = hashIndex.getLookup(hash);
0189: Object tempKey;
0190:
0191: for (; lookup >= 0; lookup = hashIndex.getNextLookup(lookup)) {
0192: tempKey = objectKeyTable[lookup];
0193:
0194: if (key.equals(tempKey)) {
0195: return lookup;
0196: }
0197: }
0198:
0199: return lookup;
0200: }
0201:
0202: protected int getLookup(int key) {
0203:
0204: int lookup = hashIndex.getLookup(key);
0205: int tempKey;
0206:
0207: for (; lookup >= 0; lookup = hashIndex.getNextLookup(lookup)) {
0208: tempKey = intKeyTable[lookup];
0209:
0210: if (key == tempKey) {
0211: return lookup;
0212: }
0213: }
0214:
0215: return lookup;
0216: }
0217:
0218: protected int getLookup(long key) {
0219:
0220: int lookup = hashIndex.getLookup((int) key);
0221: long tempKey;
0222:
0223: for (; lookup >= 0; lookup = hashIndex.getNextLookup(lookup)) {
0224: tempKey = longKeyTable[lookup];
0225:
0226: if (key == tempKey) {
0227: return lookup;
0228: }
0229: }
0230:
0231: return lookup;
0232: }
0233:
0234: /**
0235: * generic method for adding or removing keys
0236: */
0237: protected Object addOrRemove(long longKey, long longValue,
0238: Object objectKey, Object objectValue, boolean remove) {
0239:
0240: int hash = (int) longKey;
0241:
0242: if (isObjectKey) {
0243: if (objectKey == null) {
0244: return null;
0245: }
0246:
0247: hash = objectKey.hashCode();
0248: }
0249:
0250: int index = hashIndex.getHashIndex(hash);
0251: int lookup = hashIndex.hashTable[index];
0252: int lastLookup = -1;
0253: Object returnValue = null;
0254:
0255: for (; lookup >= 0; lastLookup = lookup, lookup = hashIndex
0256: .getNextLookup(lookup)) {
0257: if (isObjectKey) {
0258: if (objectKeyTable[lookup].equals(objectKey)) {
0259: break;
0260: }
0261: } else if (isIntKey) {
0262: if (longKey == intKeyTable[lookup]) {
0263: break;
0264: }
0265: } else if (isLongKey) {
0266: if (longKey == longKeyTable[lookup]) {
0267: break;
0268: }
0269: }
0270: }
0271:
0272: if (lookup >= 0) {
0273: if (remove) {
0274: if (isObjectKey) {
0275: objectKeyTable[lookup] = null;
0276: } else {
0277: if (longKey == 0) {
0278: hasZeroKey = false;
0279: zeroKeyIndex = -1;
0280: }
0281:
0282: if (isIntKey) {
0283: intKeyTable[lookup] = 0;
0284: } else {
0285: longKeyTable[lookup] = 0;
0286: }
0287: }
0288:
0289: if (isObjectValue) {
0290: returnValue = objectValueTable[lookup];
0291: objectValueTable[lookup] = null;
0292: } else if (isIntValue) {
0293: intValueTable[lookup] = 0;
0294: } else if (isLongValue) {
0295: longValueTable[lookup] = 0;
0296: }
0297:
0298: hashIndex.unlinkNode(index, lastLookup, lookup);
0299:
0300: if (accessTable != null) {
0301: accessTable[lookup] = 0;
0302: }
0303:
0304: if (minimizeOnEmpty && hashIndex.elementCount == 0) {
0305: rehash(initialCapacity);
0306: }
0307:
0308: return returnValue;
0309: }
0310:
0311: if (isObjectValue) {
0312: returnValue = objectValueTable[lookup];
0313: objectValueTable[lookup] = objectValue;
0314: } else if (isIntValue) {
0315: intValueTable[lookup] = (int) longValue;
0316: } else if (isLongValue) {
0317: longValueTable[lookup] = longValue;
0318: }
0319:
0320: if (accessTable != null) {
0321: accessTable[lookup] = accessCount++;
0322: }
0323:
0324: return returnValue;
0325: }
0326:
0327: // not found
0328: if (remove) {
0329: return null;
0330: }
0331:
0332: if (hashIndex.elementCount >= threshold) {
0333:
0334: // should throw maybe, if reset returns false?
0335: if (reset()) {
0336: return addOrRemove(longKey, longValue, objectKey,
0337: objectValue, remove);
0338: } else {
0339: return null;
0340: }
0341: }
0342:
0343: lookup = hashIndex.linkNode(index, lastLookup);
0344:
0345: // type dependent block
0346: if (isObjectKey) {
0347: objectKeyTable[lookup] = objectKey;
0348: } else if (isIntKey) {
0349: intKeyTable[lookup] = (int) longKey;
0350:
0351: if (longKey == 0) {
0352: hasZeroKey = true;
0353: zeroKeyIndex = lookup;
0354: }
0355: } else if (isLongKey) {
0356: longKeyTable[lookup] = longKey;
0357:
0358: if (longKey == 0) {
0359: hasZeroKey = true;
0360: zeroKeyIndex = lookup;
0361: }
0362: }
0363:
0364: if (isObjectValue) {
0365: objectValueTable[lookup] = objectValue;
0366: } else if (isIntValue) {
0367: intValueTable[lookup] = (int) longValue;
0368: } else if (isLongValue) {
0369: longValueTable[lookup] = longValue;
0370: }
0371:
0372: //
0373: if (accessTable != null) {
0374: accessTable[lookup] = accessCount++;
0375: }
0376:
0377: return returnValue;
0378: }
0379:
0380: /**
0381: * type-specific method for adding or removing keys in int->Object maps
0382: */
0383: protected Object addOrRemove(int intKey, Object objectValue,
0384: boolean remove) {
0385:
0386: int hash = intKey;
0387: int index = hashIndex.getHashIndex(hash);
0388: int lookup = hashIndex.hashTable[index];
0389: int lastLookup = -1;
0390: Object returnValue = null;
0391:
0392: for (; lookup >= 0; lastLookup = lookup, lookup = hashIndex
0393: .getNextLookup(lookup)) {
0394: if (intKey == intKeyTable[lookup]) {
0395: break;
0396: }
0397: }
0398:
0399: if (lookup >= 0) {
0400: if (remove) {
0401: if (intKey == 0) {
0402: hasZeroKey = false;
0403: zeroKeyIndex = -1;
0404: }
0405:
0406: intKeyTable[lookup] = 0;
0407: returnValue = objectValueTable[lookup];
0408: objectValueTable[lookup] = null;
0409:
0410: hashIndex.unlinkNode(index, lastLookup, lookup);
0411:
0412: if (accessTable != null) {
0413: accessTable[lookup] = 0;
0414: }
0415:
0416: return returnValue;
0417: }
0418:
0419: if (isObjectValue) {
0420: returnValue = objectValueTable[lookup];
0421: objectValueTable[lookup] = objectValue;
0422: }
0423:
0424: if (accessTable != null) {
0425: accessTable[lookup] = accessCount++;
0426: }
0427:
0428: return returnValue;
0429: }
0430:
0431: // not found
0432: if (remove) {
0433: return returnValue;
0434: }
0435:
0436: if (hashIndex.elementCount >= threshold) {
0437: if (reset()) {
0438: return addOrRemove(intKey, objectValue, remove);
0439: } else {
0440: return null;
0441: }
0442: }
0443:
0444: lookup = hashIndex.linkNode(index, lastLookup);
0445: intKeyTable[lookup] = intKey;
0446:
0447: if (intKey == 0) {
0448: hasZeroKey = true;
0449: zeroKeyIndex = lookup;
0450: }
0451:
0452: objectValueTable[lookup] = objectValue;
0453:
0454: if (accessTable != null) {
0455: accessTable[lookup] = accessCount++;
0456: }
0457:
0458: return returnValue;
0459: }
0460:
0461: /**
0462: * type specific method for Object sets or Object->Object maps
0463: */
0464: protected Object removeObject(Object objectKey) {
0465:
0466: if (objectKey == null) {
0467: return null;
0468: }
0469:
0470: int hash = objectKey.hashCode();
0471: int index = hashIndex.getHashIndex(hash);
0472: int lookup = hashIndex.hashTable[index];
0473: int lastLookup = -1;
0474: Object returnValue = null;
0475:
0476: for (; lookup >= 0; lastLookup = lookup, lookup = hashIndex
0477: .getNextLookup(lookup)) {
0478: if (objectKeyTable[lookup].equals(objectKey)) {
0479: objectKeyTable[lookup] = null;
0480:
0481: hashIndex.unlinkNode(index, lastLookup, lookup);
0482:
0483: if (isObjectValue) {
0484: returnValue = objectValueTable[lookup];
0485: objectValueTable[lookup] = null;
0486: }
0487:
0488: return returnValue;
0489: }
0490: }
0491:
0492: // not found
0493: return returnValue;
0494: }
0495:
0496: protected boolean reset() {
0497:
0498: if (maxCapacity == 0 || maxCapacity > threshold) {
0499: rehash(hashIndex.hashTable.length * 2);
0500:
0501: return true;
0502: } else if (purgePolicy == PURGE_ALL) {
0503: clear();
0504:
0505: return true;
0506: } else if (purgePolicy == PURGE_QUARTER) {
0507: clear(threshold / 4, threshold >> 8);
0508:
0509: return true;
0510: } else if (purgePolicy == PURGE_HALF) {
0511: clear(threshold / 2, threshold >> 8);
0512:
0513: return true;
0514: } else if (purgePolicy == NO_PURGE) {
0515: return false;
0516: }
0517:
0518: return false;
0519: }
0520:
0521: /**
0522: * rehash uses existing key and element arrays. key / value pairs are
0523: * put back into the arrays from the top, removing any gaps. any redundant
0524: * key / value pairs duplicated at the end of the array are then cleared.
0525: *
0526: * newCapacity must be larger or equal to existing number of elements.
0527: */
0528: protected void rehash(int newCapacity) {
0529:
0530: int limitLookup = hashIndex.newNodePointer;
0531: boolean oldZeroKey = hasZeroKey;
0532: int oldZeroKeyIndex = zeroKeyIndex;
0533:
0534: if (newCapacity < hashIndex.elementCount) {
0535: return;
0536: }
0537:
0538: hashIndex.reset((int) (newCapacity * loadFactor), newCapacity);
0539:
0540: hasZeroKey = false;
0541: zeroKeyIndex = -1;
0542: threshold = newCapacity;
0543:
0544: for (int lookup = -1; (lookup = nextLookup(lookup, limitLookup,
0545: oldZeroKey, oldZeroKeyIndex)) < limitLookup;) {
0546: long longKey = 0;
0547: long longValue = 0;
0548: Object objectKey = null;
0549: Object objectValue = null;
0550:
0551: if (isObjectKey) {
0552: objectKey = objectKeyTable[lookup];
0553: } else if (isIntKey) {
0554: longKey = intKeyTable[lookup];
0555: } else {
0556: longKey = longKeyTable[lookup];
0557: }
0558:
0559: if (isObjectValue) {
0560: objectValue = objectValueTable[lookup];
0561: } else if (isIntValue) {
0562: longValue = intValueTable[lookup];
0563: } else if (isLongValue) {
0564: longValue = longValueTable[lookup];
0565: }
0566:
0567: addOrRemove(longKey, longValue, objectKey, objectValue,
0568: false);
0569:
0570: if (accessTable != null) {
0571: accessTable[hashIndex.elementCount - 1] = accessTable[lookup];
0572: }
0573: }
0574:
0575: resizeElementArrays(hashIndex.newNodePointer, newCapacity);
0576: }
0577:
0578: /**
0579: * resize the arrays contianing the key / value data
0580: */
0581: private void resizeElementArrays(int dataLength, int newLength) {
0582:
0583: Object temp;
0584: int usedLength = newLength > dataLength ? dataLength
0585: : newLength;
0586:
0587: if (isIntKey) {
0588: temp = intKeyTable;
0589: intKeyTable = new int[newLength];
0590:
0591: System.arraycopy(temp, 0, intKeyTable, 0, usedLength);
0592: }
0593:
0594: if (isIntValue) {
0595: temp = intValueTable;
0596: intValueTable = new int[newLength];
0597:
0598: System.arraycopy(temp, 0, intValueTable, 0, usedLength);
0599: }
0600:
0601: if (isLongKey) {
0602: temp = longKeyTable;
0603: longKeyTable = new long[newLength];
0604:
0605: System.arraycopy(temp, 0, longKeyTable, 0, usedLength);
0606: }
0607:
0608: if (isLongValue) {
0609: temp = longValueTable;
0610: longValueTable = new long[newLength];
0611:
0612: System.arraycopy(temp, 0, longValueTable, 0, usedLength);
0613: }
0614:
0615: if (isObjectKey) {
0616: temp = objectKeyTable;
0617: objectKeyTable = new Object[newLength];
0618:
0619: System.arraycopy(temp, 0, objectKeyTable, 0, usedLength);
0620: }
0621:
0622: if (isObjectValue) {
0623: temp = objectValueTable;
0624: objectValueTable = new Object[newLength];
0625:
0626: System.arraycopy(temp, 0, objectValueTable, 0, usedLength);
0627: }
0628:
0629: if (accessTable != null) {
0630: temp = accessTable;
0631: accessTable = new int[newLength];
0632:
0633: System.arraycopy(temp, 0, accessTable, 0, usedLength);
0634: }
0635: }
0636:
0637: /**
0638: * clear all the key / value data in a range.
0639: */
0640: private void clearElementArrays(final int from, final int to) {
0641:
0642: if (isIntKey) {
0643: int counter = to;
0644:
0645: while (--counter >= from) {
0646: intKeyTable[counter] = 0;
0647: }
0648: }
0649:
0650: if (isLongKey) {
0651: int counter = to;
0652:
0653: while (--counter >= from) {
0654: longKeyTable[counter] = 0;
0655: }
0656: }
0657:
0658: if (isObjectKey) {
0659: int counter = to;
0660:
0661: while (--counter >= from) {
0662: objectKeyTable[counter] = null;
0663: }
0664: }
0665:
0666: if (isIntValue) {
0667: int counter = to;
0668:
0669: while (--counter >= from) {
0670: intValueTable[counter] = 0;
0671: }
0672: }
0673:
0674: if (isLongValue) {
0675: int counter = to;
0676:
0677: while (--counter >= from) {
0678: longValueTable[counter] = 0;
0679: }
0680: }
0681:
0682: if (isObjectValue) {
0683: int counter = to;
0684:
0685: while (--counter >= from) {
0686: objectValueTable[counter] = null;
0687: }
0688: }
0689:
0690: if (accessTable != null) {
0691: int counter = to;
0692:
0693: while (--counter >= from) {
0694: accessTable[counter] = 0;
0695: }
0696: }
0697: }
0698:
0699: /**
0700: * move the elements after a removed key / value pair to fill the gap
0701: */
0702: void removeFromElementArrays(int lookup) {
0703:
0704: int arrayLength = hashIndex.linkTable.length;
0705:
0706: if (isIntKey) {
0707: Object array = intKeyTable;
0708:
0709: System.arraycopy(array, lookup + 1, array, lookup,
0710: arrayLength - lookup - 1);
0711:
0712: intKeyTable[arrayLength - 1] = 0;
0713: }
0714:
0715: if (isLongKey) {
0716: Object array = longKeyTable;
0717:
0718: System.arraycopy(array, lookup + 1, array, lookup,
0719: arrayLength - lookup - 1);
0720:
0721: longKeyTable[arrayLength - 1] = 0;
0722: }
0723:
0724: if (isObjectKey) {
0725: Object array = objectKeyTable;
0726:
0727: System.arraycopy(array, lookup + 1, array, lookup,
0728: arrayLength - lookup - 1);
0729:
0730: objectKeyTable[arrayLength - 1] = null;
0731: }
0732:
0733: if (isIntValue) {
0734: Object array = intValueTable;
0735:
0736: System.arraycopy(array, lookup + 1, array, lookup,
0737: arrayLength - lookup - 1);
0738:
0739: intValueTable[arrayLength - 1] = 0;
0740: }
0741:
0742: if (isLongValue) {
0743: Object array = longValueTable;
0744:
0745: System.arraycopy(array, lookup + 1, array, lookup,
0746: arrayLength - lookup - 1);
0747:
0748: longValueTable[arrayLength - 1] = 0;
0749: }
0750:
0751: if (isObjectValue) {
0752: Object array = objectValueTable;
0753:
0754: System.arraycopy(array, lookup + 1, array, lookup,
0755: arrayLength - lookup - 1);
0756:
0757: objectValueTable[arrayLength - 1] = null;
0758: }
0759: }
0760:
0761: /**
0762: * find the next lookup in the key/value tables with an entry
0763: * allows the use of old limit and zero int key attributes
0764: */
0765: int nextLookup(int lookup, int limitLookup, boolean hasZeroKey,
0766: int zeroKeyIndex) {
0767:
0768: for (++lookup; lookup < limitLookup; lookup++) {
0769: if (isObjectKey) {
0770: if (objectKeyTable[lookup] != null) {
0771: return lookup;
0772: }
0773: } else if (isIntKey) {
0774: if (intKeyTable[lookup] != 0) {
0775: return lookup;
0776: } else if (hasZeroKey && lookup == zeroKeyIndex) {
0777: return lookup;
0778: }
0779: } else {
0780: if (longKeyTable[lookup] != 0) {
0781: return lookup;
0782: } else if (hasZeroKey && lookup == zeroKeyIndex) {
0783: return lookup;
0784: }
0785: }
0786: }
0787:
0788: return lookup;
0789: }
0790:
0791: /**
0792: * find the next lookup in the key/value tables with an entry
0793: * uses current limits and zero integer key state
0794: */
0795: protected int nextLookup(int lookup) {
0796:
0797: for (++lookup; lookup < hashIndex.newNodePointer; lookup++) {
0798: if (isObjectKey) {
0799: if (objectKeyTable[lookup] != null) {
0800: return lookup;
0801: }
0802: } else if (isIntKey) {
0803: if (intKeyTable[lookup] != 0) {
0804: return lookup;
0805: } else if (hasZeroKey && lookup == zeroKeyIndex) {
0806: return lookup;
0807: }
0808: } else {
0809: if (longKeyTable[lookup] != 0) {
0810: return lookup;
0811: } else if (hasZeroKey && lookup == zeroKeyIndex) {
0812: return lookup;
0813: }
0814: }
0815: }
0816:
0817: return lookup;
0818: }
0819:
0820: /**
0821: * row must already been freed of key / element
0822: */
0823: protected void removeRow(int lookup) {
0824: hashIndex.removeEmptyNode(lookup);
0825: removeFromElementArrays(lookup);
0826: }
0827:
0828: protected Object removeLookup(int lookup) {
0829:
0830: if (isObjectKey) {
0831: return addOrRemove(0, 0, objectKeyTable[lookup], null, true);
0832: } else {
0833: return addOrRemove(intKeyTable[lookup], 0, null, null, true);
0834: }
0835: }
0836:
0837: /**
0838: * Clear the map completely.
0839: */
0840: public void clear() {
0841:
0842: accessCount = 0;
0843: accessMin = accessCount;
0844: hasZeroKey = false;
0845: zeroKeyIndex = -1;
0846:
0847: clearElementArrays(0, hashIndex.linkTable.length);
0848: hashIndex.clear();
0849:
0850: if (minimizeOnEmpty) {
0851: rehash(initialCapacity);
0852: }
0853: }
0854:
0855: /**
0856: * Return the max accessCount value for count elements with the lowest
0857: * access count. Always return at least accessMin + 1
0858: */
0859: protected int getAccessCountCeiling(int count, int margin) {
0860: return ArrayCounter.rank(accessTable, hashIndex.newNodePointer,
0861: count, accessMin + 1, accessCount, margin);
0862: }
0863:
0864: /**
0865: * Clear approximately count elements from the map, starting with
0866: * those with low accessTable ranking.
0867: *
0868: * Only for maps with Object key table
0869: */
0870: protected void clear(int count, int margin) {
0871:
0872: if (margin < 64) {
0873: margin = 64;
0874: }
0875:
0876: int maxlookup = hashIndex.newNodePointer;
0877: int accessBase = getAccessCountCeiling(count, margin);
0878:
0879: for (int lookup = 0; lookup < maxlookup; lookup++) {
0880: Object o = objectKeyTable[lookup];
0881:
0882: if (o != null && accessTable[lookup] < accessBase) {
0883: removeObject(o);
0884: }
0885: }
0886:
0887: accessMin = accessBase;
0888: }
0889:
0890: void resetAccessCount() {
0891:
0892: if (accessCount < Integer.MAX_VALUE) {
0893: return;
0894: }
0895:
0896: accessMin >>= 2;
0897: accessCount >>= 2;
0898:
0899: int i = accessTable.length;
0900:
0901: while (--i >= 0) {
0902: accessTable[i] >>= 2;
0903: }
0904: }
0905:
0906: public int size() {
0907: return hashIndex.elementCount;
0908: }
0909:
0910: public boolean isEmpty() {
0911: return hashIndex.elementCount == 0;
0912: }
0913:
0914: protected boolean containsKey(Object key) {
0915:
0916: if (key == null) {
0917: return false;
0918: }
0919:
0920: int lookup = getLookup(key, key.hashCode());
0921:
0922: return lookup == -1 ? false : true;
0923: }
0924:
0925: protected boolean containsKey(int key) {
0926:
0927: int lookup = getLookup(key);
0928:
0929: return lookup == -1 ? false : true;
0930: }
0931:
0932: protected boolean containsKey(long key) {
0933:
0934: int lookup = getLookup(key);
0935:
0936: return lookup == -1 ? false : true;
0937: }
0938:
0939: protected boolean containsValue(Object value) {
0940:
0941: int lookup = 0;
0942:
0943: if (value == null) {
0944: for (; lookup < hashIndex.newNodePointer; lookup++) {
0945: if (objectValueTable[lookup] == null) {
0946: if (isObjectKey) {
0947: if (objectKeyTable[lookup] != null) {
0948: return true;
0949: }
0950: } else if (isIntKey) {
0951: if (intKeyTable[lookup] != 0) {
0952: return true;
0953: } else if (hasZeroKey && lookup == zeroKeyIndex) {
0954: return true;
0955: }
0956: } else {
0957: if (longKeyTable[lookup] != 0) {
0958: return true;
0959: } else if (hasZeroKey && lookup == zeroKeyIndex) {
0960: return true;
0961: }
0962: }
0963: }
0964: }
0965: } else {
0966: for (; lookup < hashIndex.newNodePointer; lookup++) {
0967: if (value.equals(objectValueTable[lookup])) {
0968: return true;
0969: }
0970: }
0971: }
0972:
0973: return false;
0974: }
0975:
0976: /**
0977: * Iterator returns Object, int or long and is used both for keys and
0978: * values
0979: */
0980: protected class BaseHashIterator implements org.hsqldb.lib.Iterator {
0981:
0982: boolean keys;
0983: int lookup = -1;
0984: int counter;
0985: boolean removed;
0986:
0987: /**
0988: * default is iterator for values
0989: */
0990: public BaseHashIterator() {
0991: }
0992:
0993: public BaseHashIterator(boolean keys) {
0994: this .keys = keys;
0995: }
0996:
0997: public boolean hasNext() {
0998: return counter < hashIndex.elementCount;
0999: }
1000:
1001: public Object next() throws NoSuchElementException {
1002:
1003: if ((keys && !isObjectKey) || (!keys && !isObjectValue)) {
1004: throw new NoSuchElementException("Hash Iterator");
1005: }
1006:
1007: removed = false;
1008:
1009: if (hasNext()) {
1010: counter++;
1011:
1012: lookup = nextLookup(lookup);
1013:
1014: if (keys) {
1015: return objectKeyTable[lookup];
1016: } else {
1017: return objectValueTable[lookup];
1018: }
1019: }
1020:
1021: throw new NoSuchElementException("Hash Iterator");
1022: }
1023:
1024: public int nextInt() throws NoSuchElementException {
1025:
1026: if ((keys && !isIntKey) || (!keys && !isIntValue)) {
1027: throw new NoSuchElementException("Hash Iterator");
1028: }
1029:
1030: removed = false;
1031:
1032: if (hasNext()) {
1033: counter++;
1034:
1035: lookup = nextLookup(lookup);
1036:
1037: if (keys) {
1038: return intKeyTable[lookup];
1039: } else {
1040: return intValueTable[lookup];
1041: }
1042: }
1043:
1044: throw new NoSuchElementException("Hash Iterator");
1045: }
1046:
1047: public long nextLong() throws NoSuchElementException {
1048:
1049: if ((!isLongKey || !keys)) {
1050: throw new NoSuchElementException("Hash Iterator");
1051: }
1052:
1053: removed = false;
1054:
1055: if (hasNext()) {
1056: counter++;
1057:
1058: lookup = nextLookup(lookup);
1059:
1060: if (keys) {
1061: return longKeyTable[lookup];
1062: } else {
1063: return longValueTable[lookup];
1064: }
1065: }
1066:
1067: throw new NoSuchElementException("Hash Iterator");
1068: }
1069:
1070: public void remove() throws NoSuchElementException {
1071:
1072: if (removed) {
1073: throw new NoSuchElementException("Hash Iterator");
1074: }
1075:
1076: counter--;
1077:
1078: removed = true;
1079:
1080: BaseHashMap.this .removeLookup(lookup);
1081: }
1082:
1083: public int getAccessCount() {
1084:
1085: if (removed || accessTable == null) {
1086: throw new NoSuchElementException();
1087: }
1088:
1089: return accessTable[lookup];
1090: }
1091: }
1092: }
|