Source Code Cross Referenced for BaseHashMap.java in  » Database-DBMS » hsql » org » hsqldb » store » Java Source Code / Java DocumentationJava Source Code and Java Documentation

Java Source Code / Java Documentation
1. 6.0 JDK Core
2. 6.0 JDK Modules
3. 6.0 JDK Modules com.sun
4. 6.0 JDK Modules com.sun.java
5. 6.0 JDK Modules sun
6. 6.0 JDK Platform
7. Ajax
8. Apache Harmony Java SE
9. Aspect oriented
10. Authentication Authorization
11. Blogger System
12. Build
13. Byte Code
14. Cache
15. Chart
16. Chat
17. Code Analyzer
18. Collaboration
19. Content Management System
20. Database Client
21. Database DBMS
22. Database JDBC Connection Pool
23. Database ORM
24. Development
25. EJB Server geronimo
26. EJB Server GlassFish
27. EJB Server JBoss 4.2.1
28. EJB Server resin 3.1.5
29. ERP CRM Financial
30. ESB
31. Forum
32. GIS
33. Graphic Library
34. Groupware
35. HTML Parser
36. IDE
37. IDE Eclipse
38. IDE Netbeans
39. Installer
40. Internationalization Localization
41. Inversion of Control
42. Issue Tracking
43. J2EE
44. JBoss
45. JMS
46. JMX
47. Library
48. Mail Clients
49. Net
50. Parser
51. PDF
52. Portal
53. Profiler
54. Project Management
55. Report
56. RSS RDF
57. Rule Engine
58. Science
59. Scripting
60. Search Engine
61. Security
62. Sevlet Container
63. Source Control
64. Swing Library
65. Template Engine
66. Test Coverage
67. Testing
68. UML
69. Web Crawler
70. Web Framework
71. Web Mail
72. Web Server
73. Web Services
74. Web Services apache cxf 2.0.1
75. Web Services AXIS2
76. Wiki Engine
77. Workflow Engines
78. XML
79. XML UI
Java
Java Tutorial
Java Open Source
Jar File Download
Java Articles
Java Products
Java by API
Photoshop Tutorials
Maya Tutorials
Flash Tutorials
3ds-Max Tutorials
Illustrator Tutorials
GIMP Tutorials
C# / C Sharp
C# / CSharp Tutorial
C# / CSharp Open Source
ASP.Net
ASP.NET Tutorial
JavaScript DHTML
JavaScript Tutorial
JavaScript Reference
HTML / CSS
HTML CSS Reference
C / ANSI-C
C Tutorial
C++
C++ Tutorial
Ruby
PHP
Python
Python Tutorial
Python Open Source
SQL Server / T-SQL
SQL Server / T-SQL Tutorial
Oracle PL / SQL
Oracle PL/SQL Tutorial
PostgreSQL
SQL / MySQL
MySQL Tutorial
VB.Net
VB.Net Tutorial
Flash / Flex / ActionScript
VBA / Excel / Access / Word
XML
XML Tutorial
Microsoft Office PowerPoint 2007 Tutorial
Microsoft Office Excel 2007 Tutorial
Microsoft Office Word 2007 Tutorial
Java Source Code / Java Documentation » Database DBMS » hsql » org.hsqldb.store 
Source Cross Referenced  Class Diagram Java Document (Java Doc) 


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:        }
www.java2java.com | Contact Us
Copyright 2009 - 12 Demo Source and Support. All rights reserved.
All other trademarks are property of their respective owners.