001: /* Copyright (c) 2001-2005, The HSQL Development Group
002: * All rights reserved.
003: *
004: * Redistribution and use in source and binary forms, with or without
005: * modification, are permitted provided that the following conditions are met:
006: *
007: * Redistributions of source code must retain the above copyright notice, this
008: * list of conditions and the following disclaimer.
009: *
010: * Redistributions in binary form must reproduce the above copyright notice,
011: * this list of conditions and the following disclaimer in the documentation
012: * and/or other materials provided with the distribution.
013: *
014: * Neither the name of the HSQL Development Group nor the names of its
015: * contributors may be used to endorse or promote products derived from this
016: * software without specific prior written permission.
017: *
018: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
019: * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
020: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
021: * ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG,
022: * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
023: * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
024: * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
025: * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
026: * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
027: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
028: * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
029: */
030:
031: package org.hsqldb.store;
032:
033: /**
034: * A chained bucket hash index implementation.
035: *
036: * hashTable and linkTable are arrays of signed integral types. This
037: * implementation uses int as the type but short or byte can be used for
038: * smaller index sizes (cardinality).
039: *
040: * hashTable[index] contains the pointer to the first node with
041: * (index == hash modulo hashTable.length) or -1 if there is no corresponding
042: * node. linkTable[{0,newNodePointer}] (the range between 0 and newNodePointer)
043: * contains either the pointer to the next node or -1 if there is no
044: * such node. reclaimedNodeIndex contains a pointer to an element
045: * of linkTable which is the first element in the list of reclaimed nodes
046: * (nodes no longer in index) or -1 if there is no such node.
047: *
048: * elemenet at and above linkTable[newNodePointer] have never been used
049: * as a node and their contents is not significant.
050: *
051: * @author fredt@users
052: * @version 1.7.2
053: * @since 1.7.2
054: */
055: class HashIndex {
056:
057: int[] hashTable;
058: int[] linkTable;
059: int newNodePointer;
060: int elementCount;
061: int reclaimedNodePointer = -1;
062: boolean fixedSize;
063:
064: HashIndex(int hashTableSize, int capacity, boolean fixedSize) {
065:
066: reset(hashTableSize, capacity);
067:
068: this .fixedSize = fixedSize;
069: }
070:
071: /**
072: * Reset the structure with a new size as empty.
073: *
074: * @param hashTableSize
075: * @param capacity
076: */
077: void reset(int hashTableSize, int capacity) {
078:
079: int[] newHT = new int[hashTableSize];
080: int[] newLT = new int[capacity];
081:
082: // allocate memory before assigning
083: hashTable = newHT;
084: linkTable = newLT;
085:
086: resetTables();
087: }
088:
089: void resetTables() {
090:
091: int to = hashTable.length;
092: int[] intArray = hashTable;
093:
094: while (--to >= 0) {
095: intArray[to] = -1;
096: }
097:
098: newNodePointer = 0;
099: elementCount = 0;
100: reclaimedNodePointer = -1;
101: }
102:
103: /**
104: * Reset the index as empty.
105: */
106: void clear() {
107:
108: int to = linkTable.length;
109: int[] intArray = linkTable;
110:
111: while (--to >= 0) {
112: intArray[to] = 0;
113: }
114:
115: resetTables();
116: }
117:
118: /**
119: * @param hash
120: */
121: int getHashIndex(int hash) {
122: return (hash & 0x7fffffff) % hashTable.length;
123: }
124:
125: /**
126: * Return the array index for a hash.
127: *
128: * @param hash the hash value used for indexing
129: * @return either -1 or the first node for this hash value
130: */
131: int getLookup(int hash) {
132:
133: int index = (hash & 0x7fffffff) % hashTable.length;
134:
135: return hashTable[index];
136: }
137:
138: /**
139: * This looks from a given node, so the parameter is always > -1.
140: *
141: * @param valid lookup node to look from
142: * @return either -1 or the next node from this node
143: */
144: int getNextLookup(int lookup) {
145: return linkTable[lookup];
146: }
147:
148: /**
149: * Link a new node to the end of the linked for a hash index.
150: *
151: * @param index an index into hashTable
152: * @param lastLookup either -1 or the node to which the new node will be linked
153: * @return the new node
154: */
155: int linkNode(int index, int lastLookup) {
156:
157: // get the first reclaimed slot
158: int lookup = reclaimedNodePointer;
159:
160: if (lookup == -1) {
161: lookup = newNodePointer++;
162: } else {
163:
164: // reset the first reclaimed slot
165: reclaimedNodePointer = linkTable[lookup];
166: }
167:
168: // link the node
169: if (lastLookup == -1) {
170: hashTable[index] = lookup;
171: } else {
172: linkTable[lastLookup] = lookup;
173: }
174:
175: linkTable[lookup] = -1;
176:
177: elementCount++;
178:
179: return lookup;
180: }
181:
182: /**
183: * Unlink a node from a linked list and link into the reclaimed list.
184: *
185: * @param index an index into hashTable
186: * @param lastLookup either -1 or the node to which the target node is linked
187: * @param lookup the node to remove
188: */
189: void unlinkNode(int index, int lastLookup, int lookup) {
190:
191: // unlink the node
192: if (lastLookup == -1) {
193: hashTable[index] = linkTable[lookup];
194: } else {
195: linkTable[lastLookup] = linkTable[lookup];
196: }
197:
198: // add to reclaimed list
199: linkTable[lookup] = reclaimedNodePointer;
200: reclaimedNodePointer = lookup;
201:
202: elementCount--;
203: }
204:
205: /**
206: * Remove a node that has already been unlinked. This is not required
207: * for index operations. It is used only when the row needs to be removed
208: * from the data structures that store the actual indexed data and the
209: * nodes need to be contiguous.
210: *
211: * @param lookup the node to remove
212: * @return true if node found in unlinked state
213: */
214: boolean removeEmptyNode(int lookup) {
215:
216: boolean found = false;
217: int lastLookup = -1;
218:
219: for (int i = reclaimedNodePointer; i >= 0; lastLookup = i, i = linkTable[i]) {
220: if (i == lookup) {
221: if (lastLookup == -1) {
222: reclaimedNodePointer = linkTable[lookup];
223: } else {
224: linkTable[lastLookup] = linkTable[lookup];
225: }
226:
227: found = true;
228:
229: break;
230: }
231: }
232:
233: if (!found) {
234: return false;
235: }
236:
237: for (int i = 0; i < newNodePointer; i++) {
238: if (linkTable[i] > lookup) {
239: linkTable[i]--;
240: }
241: }
242:
243: System.arraycopy(linkTable, lookup + 1, linkTable, lookup,
244: newNodePointer - lookup - 1);
245:
246: linkTable[newNodePointer - 1] = 0;
247:
248: newNodePointer--;
249:
250: for (int i = 0; i < hashTable.length; i++) {
251: if (hashTable[i] > lookup) {
252: hashTable[i]--;
253: }
254: }
255:
256: return true;
257: }
258: }
|