KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > hsqldb > store > HashIndex


1 /* Copyright (c) 2001-2005, The HSQL Development Group
2  * All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions are met:
6  *
7  * Redistributions of source code must retain the above copyright notice, this
8  * list of conditions and the following disclaimer.
9  *
10  * Redistributions in binary form must reproduce the above copyright notice,
11  * this list of conditions and the following disclaimer in the documentation
12  * and/or other materials provided with the distribution.
13  *
14  * Neither the name of the HSQL Development Group nor the names of its
15  * contributors may be used to endorse or promote products derived from this
16  * software without specific prior written permission.
17  *
18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
19  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21  * ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG,
22  * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
23  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
24  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
25  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
26  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
28  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29  */
30
31
32 package org.hsqldb.store;
33
34 /**
35  * A chained bucket hash index implementation.
36  *
37  * hashTable and linkTable are arrays of signed integral types. This
38  * implementation uses int as the type but short or byte can be used for
39  * smaller index sizes (cardinality).
40  *
41  * hashTable[index] contains the pointer to the first node with
42  * (index == hash modulo hashTable.length) or -1 if there is no corresponding
43  * node. linkTable[{0,newNodePointer}] (the range between 0 and newNodePointer)
44  * contains either the pointer to the next node or -1 if there is no
45  * such node. reclaimedNodeIndex contains a pointer to an element
46  * of linkTable which is the first element in the list of reclaimed nodes
47  * (nodes no longer in index) or -1 if there is no such node.
48  *
49  * elemenet at and above linkTable[newNodePointer] have never been used
50  * as a node and their contents is not significant.
51  *
52  * @author fredt@users
53  * @version 1.7.2
54  * @since 1.7.2
55  */
56 class HashIndex {
57
58     int[] hashTable;
59     int[] linkTable;
60     int newNodePointer;
61     int elementCount;
62     int reclaimedNodePointer = -1;
63     boolean fixedSize;
64
65     HashIndex(int hashTableSize, int capacity, boolean fixedSize) {
66
67         reset(hashTableSize, capacity);
68
69         this.fixedSize = fixedSize;
70     }
71
72     /**
73      * Reset the structure with a new size as empty.
74      *
75      * @param hashTableSize
76      * @param capacity
77      */
78     void reset(int hashTableSize, int capacity) {
79
80         int[] newHT = new int[hashTableSize];
81         int[] newLT = new int[capacity];
82
83         // allocate memory before assigning
84 hashTable = newHT;
85         linkTable = newLT;
86
87         resetTables();
88     }
89
90     void resetTables() {
91
92         int to = hashTable.length;
93         int[] intArray = hashTable;
94
95         while (--to >= 0) {
96             intArray[to] = -1;
97         }
98
99         newNodePointer = 0;
100         elementCount = 0;
101         reclaimedNodePointer = -1;
102     }
103
104     /**
105      * Reset the index as empty.
106      */
107     void clear() {
108
109         int to = linkTable.length;
110         int[] intArray = linkTable;
111
112         while (--to >= 0) {
113             intArray[to] = 0;
114         }
115
116         resetTables();
117     }
118
119     /**
120      * @param hash
121      */
122     int getHashIndex(int hash) {
123         return (hash & 0x7fffffff) % hashTable.length;
124     }
125
126     /**
127      * Return the array index for a hash.
128      *
129      * @param hash the hash value used for indexing
130      * @return either -1 or the first node for this hash value
131      */
132     int getLookup(int hash) {
133
134         int index = (hash & 0x7fffffff) % hashTable.length;
135
136         return hashTable[index];
137     }
138
139     /**
140      * This looks from a given node, so the parameter is always > -1.
141      *
142      * @param valid lookup node to look from
143      * @return either -1 or the next node from this node
144      */
145     int getNextLookup(int lookup) {
146         return linkTable[lookup];
147     }
148
149     /**
150      * Link a new node to the end of the linked for a hash index.
151      *
152      * @param index an index into hashTable
153      * @param lastLookup either -1 or the node to which the new node will be linked
154      * @return the new node
155      */
156     int linkNode(int index, int lastLookup) {
157
158         // get the first reclaimed slot
159 int lookup = reclaimedNodePointer;
160
161         if (lookup == -1) {
162             lookup = newNodePointer++;
163         } else {
164
165             // reset the first reclaimed slot
166 reclaimedNodePointer = linkTable[lookup];
167         }
168
169         // link the node
170 if (lastLookup == -1) {
171             hashTable[index] = lookup;
172         } else {
173             linkTable[lastLookup] = lookup;
174         }
175
176         linkTable[lookup] = -1;
177
178         elementCount++;
179
180         return lookup;
181     }
182
183     /**
184      * Unlink a node from a linked list and link into the reclaimed list.
185      *
186      * @param index an index into hashTable
187      * @param lastLookup either -1 or the node to which the target node is linked
188      * @param lookup the node to remove
189      */
190     void unlinkNode(int index, int lastLookup, int lookup) {
191
192         // unlink the node
193 if (lastLookup == -1) {
194             hashTable[index] = linkTable[lookup];
195         } else {
196             linkTable[lastLookup] = linkTable[lookup];
197         }
198
199         // add to reclaimed list
200 linkTable[lookup] = reclaimedNodePointer;
201         reclaimedNodePointer = lookup;
202
203         elementCount--;
204     }
205
206     /**
207      * Remove a node that has already been unlinked. This is not required
208      * for index operations. It is used only when the row needs to be removed
209      * from the data structures that store the actual indexed data and the
210      * nodes need to be contiguous.
211      *
212      * @param lookup the node to remove
213      * @return true if node found in unlinked state
214      */
215     boolean removeEmptyNode(int lookup) {
216
217         boolean found = false;
218         int lastLookup = -1;
219
220         for (int i = reclaimedNodePointer; i >= 0;
221                 lastLookup = i, i = linkTable[i]) {
222             if (i == lookup) {
223                 if (lastLookup == -1) {
224                     reclaimedNodePointer = linkTable[lookup];
225                 } else {
226                     linkTable[lastLookup] = linkTable[lookup];
227                 }
228
229                 found = true;
230
231                 break;
232             }
233         }
234
235         if (!found) {
236             return false;
237         }
238
239         for (int i = 0; i < newNodePointer; i++) {
240             if (linkTable[i] > lookup) {
241                 linkTable[i]--;
242             }
243         }
244
245         System.arraycopy(linkTable, lookup + 1, linkTable, lookup,
246                          newNodePointer - lookup - 1);
247
248         linkTable[newNodePointer - 1] = 0;
249
250         newNodePointer--;
251
252         for (int i = 0; i < hashTable.length; i++) {
253             if (hashTable[i] > lookup) {
254                 hashTable[i]--;
255             }
256         }
257
258         return true;
259     }
260 }
261
Popular Tags