KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > smallsql > database > StorePageMap


1 /* =============================================================
2  * SmallSQL : a free Java DBMS library for the Java(tm) platform
3  * =============================================================
4  *
5  * (C) Copyright 2004-2006, by Volker Berlin.
6  *
7  * Project Info: http://www.smallsql.de/
8  *
9  * This library is free software; you can redistribute it and/or modify it
10  * under the terms of the GNU Lesser General Public License as published by
11  * the Free Software Foundation; either version 2.1 of the License, or
12  * (at your option) any later version.
13  *
14  * This library is distributed in the hope that it will be useful, but
15  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
16  * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
17  * License for more details.
18  *
19  * You should have received a copy of the GNU Lesser General Public
20  * License along with this library; if not, write to the Free Software
21  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
22  * USA.
23  *
24  * [Java is a trademark or registered trademark of Sun Microsystems, Inc.
25  * in the United States and other countries.]
26  *
27  * ---------------
28  * StorePageMap.java
29  * ---------------
30  * Author: Volker Berlin
31  *
32  * Created on 13.08.2004
33  */
34 package smallsql.database;
35
36 /**
37  * @author Volker Berlin
38  */
39 class StorePageMap {
40
41
42
43     /**
44      * The table, resized as necessary. Length MUST Always be a power of two.
45      */
46     private Entry[] table;
47
48     /**
49      * The number of key-value mappings contained in this identity hash map.
50      */
51     private int size;
52   
53     /**
54      * The next size value at which to resize (capacity * load factor).
55      * @serial
56      */
57     private int threshold;
58   
59
60
61
62
63     /**
64      * Constructs an empty <tt>HashMap</tt> with the default initial capacity
65      * (16) and the default load factor (0.75).
66      */
67     StorePageMap() {
68         threshold = 12;
69         table = new Entry[17];
70     }
71
72
73
74
75
76  
77     /**
78      * Returns the number of key-value mappings in this map.
79      *
80      * @return the number of key-value mappings in this map.
81      */
82     final int size() {
83         return size;
84     }
85   
86     /**
87      * Returns <tt>true</tt> if this map contains no key-value mappings.
88      *
89      * @return <tt>true</tt> if this map contains no key-value mappings.
90      */
91     final boolean isEmpty() {
92         return size == 0;
93     }
94
95     /**
96      * Returns the first StorePage for the given key.
97      */
98     final TableStorePage get(long key) {
99         int i = (int)(key % table.length);
100         Entry e = table[i];
101         while (true) {
102             if (e == null)
103                 return null;
104             if (e.key == key)
105                 return e.value;
106             e = e.next;
107         }
108     }
109
110     /**
111      * Returns <tt>true</tt> if this map contains a StorePage for the
112      * specified key.
113      *
114      */
115     final boolean containsKey(long key) {
116         return (get(key) != null);
117     }
118
119   
120     /**
121      * Add the StorePage with the key. Multiple StorePage for the same key are valid.
122      * The cause are multiple changes in one transaction. With SavePoints a rollback to a older
123      * StorePage is valid.<p>
124      * The latest StorePage is placed at first pos.
125      */
126     final TableStorePage add(long key, TableStorePage value) {
127         int i = (int)(key % table.length);
128
129         table[i] = new Entry(key, value, table[i]);
130         if (size++ >= threshold)
131             resize(2 * table.length);
132         return null;
133     }
134
135
136     /**
137      * Rehashes the contents of this map into a new array with a
138      * larger capacity. This method is called automatically when the
139      * number of keys in this map reaches its threshold.
140      *
141      * If current capacity is MAXIMUM_CAPACITY, this method does not
142      * resize the map, but but sets threshold to Integer.MAX_VALUE.
143      * This has the effect of preventing future calls.
144      *
145      * @param newCapacity the new capacity, MUST be a power of two;
146      * must be greater than current capacity unless current
147      * capacity is MAXIMUM_CAPACITY (in which case value
148      * is irrelevant).
149      */
150     final private void resize(int newCapacity) {
151
152         Entry[] newTable = new Entry[newCapacity];
153         transfer(newTable);
154         table = newTable;
155         threshold = (int)(newCapacity * 0.75f);
156     }
157
158     /**
159      * Transfer all entries from current table to newTable.
160      */
161     final private void transfer(Entry[] newTable) {
162         Entry[] src = table;
163         int newCapacity = newTable.length;
164         for (int j = 0; j < src.length; j++) {
165             Entry e = src[j];
166             if (e != null) {
167                 src[j] = null;
168                 do {
169                     Entry next = e.next;
170                     e.next = null;
171                     int i = (int)(e.key % newCapacity);
172                     //The order for StorePages with the same key must not change
173 //that we need to find the end of the link list. This is different to a typical HashTable
174 if(newTable[i] == null){
175                         newTable[i] = e;
176                     }else{
177                         Entry entry = newTable[i];
178                         while(entry.next != null) entry = entry.next;
179                         entry.next = e;
180                     }
181                     e = next;
182                 } while (e != null);
183             }
184         }
185     }
186
187   
188     /**
189      * Removes the mapping for this key from this map if present.
190      *
191      * @param key key whose mapping is to be removed from the map.
192      * @return previous value associated with specified key, or <tt>null</tt>
193      * if there was no mapping for key. A <tt>null</tt> return can
194      * also indicate that the map previously associated <tt>null</tt>
195      * with the specified key.
196      */
197     final TableStorePage remove(long key) {
198         int i = (int)(key % table.length);
199         Entry prev = table[i];
200         Entry e = prev;
201
202         while (e != null) {
203             Entry next = e.next;
204             if (e.key == key) {
205                 size--;
206                 if (prev == e)
207                     table[i] = next;
208                 else
209                     prev.next = next;
210                 return e.value;
211             }
212             prev = e;
213             e = next;
214         }
215         return null;
216     }
217
218
219     /**
220      * Removes all mappings from this map.
221      */
222     final void clear() {
223         Entry tab[] = table;
224         for (int i = 0; i < tab.length; i++)
225             tab[i] = null;
226         size = 0;
227     }
228
229     /**
230      * Returns <tt>true</tt> if this map maps one or more keys to the
231      * specified value.
232      *
233      * @param value value whose presence in this map is to be tested.
234      * @return <tt>true</tt> if this map maps one or more keys to the
235      * specified value.
236      */
237     final boolean containsValue(TableStorePage value) {
238         Entry tab[] = table;
239             for (int i = 0; i < tab.length ; i++)
240                 for (Entry e = tab[i] ; e != null ; e = e.next)
241                     if (value.equals(e.value))
242                         return true;
243         return false;
244     }
245
246
247
248     static class Entry{
249         final long key;
250         final TableStorePage value;
251         Entry next;
252
253         /**
254          * Create new entry.
255          */
256         Entry(long k, TableStorePage v, Entry n) {
257             value = v;
258             next = n;
259             key = k;
260         }
261
262     
263     }
264
265
266 }
267
Popular Tags