KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > ozoneDB > core > storage > gammaStore > Loc


1 // You can redistribute this software and/or modify it under the terms of
2
// the Ozone Core License version 1 published by ozone-db.org.
3
//
4
// Copyright (C) 2003-@year@, Leo Mekenkamp. All rights reserved.
5
//
6
// $Id: Loc.java,v 1.1 2004/01/25 20:53:42 leomekenkamp Exp $
7

8 package org.ozoneDB.core.storage.gammaStore;
9
10 import java.io.Serializable JavaDoc;
11
12 /**
13  * <p>Provides a primitive mapping-like meganism in which there is only a key (a
14  * primitive <code>long</code> in this case). This key can be put in and
15  * retrieved by <code>getKey(long)</code> and <code>putKey(long)</code>. Both
16  * methods return a handle, which can be used as a handle or magic cookie, to
17  * find the key. Implementing classes can and should provide their own get and
18  * put methods for each and every object or primitive that is mapped to the key.
19  * </p>
20  * <p>Extending classes should extend <code>move(int, int)</code></p>
21  *
22  * <p>This implementation is very fast when every value passed to <code>putKey(int)</code>
23  * is bigger than all previous passed values (O(1)). If not, it is quite slow
24  * (max O(size)). Because this class is used to store object ids and cluster ids
25  * this means the greatest performance benefits occur in normal 'everyday' use.
26  * Only when the database or OS has crashed (powerfailure) and the index has to
27  * be rebuild does the speed disadvantage make itself known.</p>
28  *
29  * @author <a HREF="mailto:leoATmekenkampD0Tcom">Leo Mekenkamp (mind the anti sp@m)</a>
30  * @version $Id: Loc.java,v 1.1 2004/01/25 20:53:42 leomekenkamp Exp $
31  */

32 public class Loc implements Serializable JavaDoc {
33     
34     protected long[] keys;
35     private int[] inUse;
36     private int capacity;
37     private int size;
38     private int handleToLast;
39
40     public Loc(int capacity, int slack) {
41         this.capacity = capacity;
42         keys = new long[capacity + slack];
43         int inUseSize = keys.length / 32;
44         if (keys.length % 32 != 0) {
45             inUseSize++;
46         }
47         inUse = new int[inUseSize];
48         handleToLast = -1;
49     }
50     
51     public Loc(int capacity, float relSlack) {
52         this(capacity, (int) (relSlack * capacity) > 0 ? (int) (relSlack * capacity) : 1);
53     }
54
55     /**
56      * Returns a handle to the given value. If there is no such value, then
57      * the return value is negative. The returned handle is only valid until
58      * the next call to <code>putKey(long)</code> or <code>compress()</code>.
59      */

60     public int getKeyPos(long key) {
61         int result = search(key);
62         
63         if (!isInUse(result) || key != keys[result]) {
64             result = -1;
65         }
66         return result;
67     }
68     
69     /** Returns the key found at the specified location.
70      * @param pos position to get the key from
71      * @return key at that location
72      * @throws IllegalArgumentException the specified position is not in use
73      */

74     public long getKey(int pos) {
75         if (!isInUse(pos)) {
76             throw new IllegalArgumentException JavaDoc("position not in use");
77         }
78         return keys[pos];
79     }
80     
81     /**
82      * Returns a handle to the given key, or, if that key does not exist, to
83      * the smallest key larger than specified key. If there is no such value,
84      * then the return value is negative. The returned handle is only valid
85      * until the next call to <code>putKey(long)</code> or <code>compress()</code>.
86      */

87     public int getKeyPosOrNearestGreater(long key) {
88         int result = -1;
89         for(int handle = search(key); handle <= handleToLast; handle++) {
90             if (isInUse(handle) && keys[handle] >= key) {
91                 result = handle;
92                 break;
93             }
94         }
95         return result;
96     }
97     
98     /**
99      * Returns a handle to the given key, or, if that key does not exist, to
100      * the largest key smaller than specified key. If there is no such value,
101      * then the return value is negative. The returned handle is only valid
102      * until the next call to <code>putKey(long)</code> or <code>compress()</code>.
103      */

104     public int getKeyPosOrNearestSmaller(long key) {
105         int result = -1;
106         for(int handle = search(key); handle >= 0; handle--) {
107             if (isInUse(handle) && keys[handle] <= key) {
108                 result = handle;
109                 break;
110             }
111         }
112         return result;
113     }
114     
115     /**
116      * Returns a handle to the given value and removes that key. If there is no
117      * such key, then the return value is negative. The returned handle is only
118      * valid until the next call to <code>putKey(long)</code> or <code>compress()</code>.
119      * The returned handle can also never be retrieved again.
120      */

121     public int removeKey(long key) {
122         int result = getKeyPos(key);
123         if (result < 0) {
124             return -1;
125         }
126         removePos(result);
127         return result;
128     }
129     
130     /**
131      * <p>Inserts (or overwrites) a key and returns a handle to it. The returned
132      * handle is only valid until the next call to <code>putKey(long)</code> or
133      * <code>compress()</code>.</p>
134      * <p>This method is highly optimized for keys that are bigger than any
135      * other key in this instance; performance is then O(1). When this is not
136      * the case, thus the keys are inserted in random fashion (2,7,4,8,9,1
137      * instead of 1,2,4,7,8,9) performance can be up to O(size)</p>
138      *
139      * @throws IndexOutOfBoundsException maximum size has already been reached
140      */

141     public int putKey(long key) {
142         if (handleToLast == -1 || keys[handleToLast] < key) {
143             if (handleToLast == keys.length - 1) {
144                 compress();
145             }
146             // since the key is bigger than all others, append to end of array
147
if (size >= capacity) {
148                 throw new IndexOutOfBoundsException JavaDoc("cannot grow any larger");
149             }
150             handleToLast++;
151             keys[handleToLast] = key;
152             setInUse(handleToLast, true);
153             size++;
154             return handleToLast;
155         }
156
157         // Ouch, we got a key that is not the largest in this instance; we have
158
// to do a (costly) insert. Must do a compress to make sure that keys
159
// do not appear twice or more times (one time as inUse and possible
160
// others not inUse...
161
compress();
162         int result = getKeyPosOrNearestGreater(key);
163         if (result >= 0) {
164             if (isInUse(result) && keys[result] == key) {
165                 return result;
166             }
167         } else {
168             result = handleToLast >= 0 ? handleToLast : 0;
169         }
170         
171         if (size >= capacity) {
172             throw new IndexOutOfBoundsException JavaDoc("cannot grow any larger (size = " + size + ", capacity = " + capacity);
173         }
174         
175         for (int i = handleToLast; i >= result; i--) {
176             // note that handleToLast + 1 is never in use here, because
177
// of the compress() at the start of this method
178
move(i, i + 1);
179         }
180         handleToLast++;
181         keys[result] = key;
182         setInUse(result, true);
183         size++;
184         return result;
185     }
186     
187     /**
188      * Returns the handle to the key that is the smallest of all larger keys.
189      * Returns < 0 if there is no such key. Note that if handle <0 then the
190      * first handle in use is returned (which may of course be < 0 if there is
191      * no key in this instance
192      */

193     public int next(int handle) {
194         if (handle >= 0 && !isInUse(handle)) {
195             throw new IllegalArgumentException JavaDoc("handle is not in use");
196         }
197         handle++;
198         int result;
199         for(result = -1; result < 0 && handle <= handleToLast; handle++) {
200             if (isInUse(handle)) {
201                 result = handle;
202             }
203         }
204         return result;
205     }
206     
207     /**
208      * Returns true iff the given handle is in use
209      */

210     protected final boolean isInUse(int handle) {
211         if (handle < 0 || handle >= keys.length) {
212             throw new IllegalArgumentException JavaDoc("handle should be >= 0 and < " + keys.length + ", is " + handle);
213         }
214         int pos = handle / 32;
215         int mask = 1 << (handle % 32);
216         return (inUse[pos] & mask ) != 0;
217     }
218     
219     /**
220      * Returns the previous value.
221      */

222     private boolean setInUse(int handle, boolean inUse) {
223         int pos = handle / 32;
224         int mask = 1 << (handle % 32);
225         boolean result = (this.inUse[pos] | mask) != 0;
226         if (inUse) {
227             this.inUse[pos] |= mask;
228         } else {
229             this.inUse[pos] &= ~mask;
230         }
231         return result;
232     }
233     
234     /**
235      * Deletes the entry at given position.
236      * @throws IllegalArgumentException if already invalidated/removed
237      */

238     public void removePos(int handle) {
239         if (!setInUse(handle, false)) {
240             throw new IllegalArgumentException JavaDoc("pos " + handle + " has already been removed");
241         }
242         size--;
243         // takes car of the case handle == handleToLast
244
while (handleToLast >= 0 && !isInUse(handleToLast)) {
245             handleToLast--;
246         }
247     }
248     
249     /**
250      * Searches for the given value. If the value could not be found then one of
251      * the handles of the nearest value is returned. Note that the returned
252      * handle may not be in use.
253      */

254     private int search(long key) {
255         return (handleToLast < 0) ? 0 : search(key, 0, handleToLast);
256     }
257     
258     /**
259      * note: searching beyond high > index is NOT supported and may yield
260      * strange results. Search may return a handle to either 1) the specified
261      * key, or if that key does not exist: 2) the greatest key smaller
262      * than the specified key; or: 3) the smallest key greater than
263      * the specified key. Returned handle may be invalid!
264      */

265     private int search(long key, int low, int high) {
266         if (low > high) {
267             throw new IllegalArgumentException JavaDoc("low should be <= high; low == " + low + ", high == " + high + ", key == " + key + ", handleToLast == " + handleToLast);
268         }
269         for(;;) {
270             int result = (low + high) / 2;
271             if (low >= high || keys[result] == key) {
272                 return result;
273             }
274             if (key < keys[result]) {
275                 high = result - 1;
276             } else {
277                 low = result + 1;
278             }
279         }
280     }
281     
282     /**
283      * Moves all keys to remove unused (deleted) slots.
284      */

285     private void compress() {
286         handleToLast = -1;
287         for(int i = 0; i < keys.length; i++) {
288             if (isInUse(i)) {
289                 handleToLast++;
290                 if (i > handleToLast) {
291                     move(i, handleToLast);
292                 }
293             } else {
294                 // Having a lot of 0s in a row makes for better compression when this
295
// instance is serialized and put through a compressing stream.
296
keys[i] = 0;
297             }
298         }
299     }
300     
301     /**
302      * Extending classes _must_ implement their own move() and call this one
303      * as well.
304      */

305     protected void move(int handleFrom, int handleTo) {
306         if (!isInUse(handleFrom)) {
307             throw new IllegalArgumentException JavaDoc("handleFrom (" + handleFrom + ") must be in use");
308         }
309         if (isInUse(handleTo)) {
310             throw new IllegalArgumentException JavaDoc("handleTo (" + handleTo + ") must not be in use");
311         }
312         keys[handleTo] = keys[handleFrom];
313         // Having a lot of 0s in a row makes for better compression when this
314
// instance is serialized and put through a compressing stream.
315
keys[handleFrom] = 0;
316         setInUse(handleFrom, false);
317         setInUse(handleTo, true);
318     }
319     
320     public String JavaDoc toString() {
321         StringBuffer JavaDoc result = new StringBuffer JavaDoc("handleToLast=");
322         result.append(handleToLast).append("; [");
323         for (int i = 0; i < keys.length; i++) {
324             result.append(keys[i]);
325             if (!isInUse(i)) {
326                 result.append("D");
327             }
328             if (i < keys.length - 1) {
329                 result.append(", ");
330             } else {
331                 result.append("]");
332             }
333         }
334         return result.toString();
335     }
336     
337     /**
338      * Returns the number of keys in use.
339      */

340     public int size() {
341         return size;
342     }
343     
344     public long getMinKey() {
345         return keys[getMinPos()];
346     }
347
348     public long getMaxKey() {
349         return keys[getMaxPos()];
350     }
351         
352     public int getMinPos() {
353         for (int i = 0; i < keys.length; i++) {
354             if (isInUse(i)) {
355                 return i;
356             }
357         }
358         throw new RuntimeException JavaDoc("may not call getMinKey() when empty");
359     }
360
361     public int getMaxPos() {
362         for (int i = handleToLast; i >= 0; i--) {
363             if (isInUse(i)) {
364                 return i;
365             }
366         }
367         throw new RuntimeException JavaDoc("may not call getMaxKey() when empty");
368     }
369         
370 }
371
Popular Tags