|
1
8 package org.ozoneDB.core.storage.gammaStore;
9
10 import java.io.Serializable  ;
11
12
32 public class LongLoc implements Serializable {
33
34 protected long[] keys;
35 private int[] inUse;
36 private int capacity;
37 private int size;
38 private int handleToLast;
39
40 public LongLoc(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 LongLoc(int capacity, float relSlack) {
52 this(capacity, (int) (relSlack * capacity) > 0 ? (int) (relSlack * capacity) : 1);
53 }
54
55
60 public int getKeyPos(long key) {
61 int result = search(key);
62 if (!isInUse(result) || key != keys[result]) {
63 result = -1;
64 }
65 return result;
66 }
67
68
73 public long getKey(int pos) {
74 if (!isInUse(pos)) {
75 throw new IllegalArgumentException ("position not in use");
76 }
77 return keys[pos];
78 }
79
80
86 public int getKeyPosOrNearestGreater(long key) {
87 int result = -1;
88 for(int handle = search(key); handle <= handleToLast; handle++) {
89 if (isInUse(handle) && keys[handle] >= key) {
90 result = handle;
91 break;
92 }
93 }
94 return result;
95 }
96
97
103 public int getKeyPosOrNearestSmaller(long key) {
104 int result = -1;
105 for(int handle = search(key); handle >= 0; handle--) {
106 if (isInUse(handle) && keys[handle] <= key) {
107 result = handle;
108 break;
109 }
110 }
111 return result;
112 }
113
114
120 public int removeKey(long key) {
121 int result = getKeyPos(key);
122 if (result < 0) {
123 throw new IllegalArgumentException ("key not found");
124 }
125 setInUse(result, false);
126 size--;
127 return result;
128 }
129
130
139 public int putKey(long key) {
140 if (handleToLast == -1 || keys[handleToLast] < key) {
141 if (handleToLast == keys.length - 1) {
142 compress();
143 }
144 if (size >= capacity) {
146 throw new IndexOutOfBoundsException ("cannot grow any larger");
147 }
148 handleToLast++;
149 keys[handleToLast] = key;
150 setInUse(handleToLast, true);
151 size++;
152 return handleToLast;
153 }
154
155 compress();
160 int result = getKeyPosOrNearestGreater(key);
161 if (result >= 0) {
162 if (isInUse(result) || keys[result] == key) {
163 return result;
164 }
165 } else {
166 result = handleToLast;
167 }
168
169 if (size >= capacity) {
170 throw new IndexOutOfBoundsException ("cannot grow any larger");
171 }
172
173 for (int i = keys.length - 2; i >= result; i--) {
174 if (isInUse(i)) {
175 move(i, i + 1);
178 if (handleToLast <= i) {
179 handleToLast = i + 1;
180 }
181 }
182 }
183 keys[result] = key;
184 setInUse(result, true);
185 size++;
186 return result;
187 }
188
189
195 public int next(int handle) {
196 if (handle >= 0 && !isInUse(handle)) {
197 throw new IllegalArgumentException ("handle is not in use");
198 }
199 handle++;
200 int result;
201 for(result = -1; result < 0 && handle <= handleToLast; handle++) {
202 if (isInUse(handle)) {
203 result = handle;
204 }
205 }
206 return result;
207 }
208
209
212 private boolean isInUse(int handle) {
213 int pos = handle / 32;
214 int mask = 1 << (handle % 32);
215 return (inUse[pos] & mask ) != 0;
216 }
217
218 private void setInUse(int handle, boolean inUse) {
219 int pos = handle / 32;
220 int mask = 1 << (handle % 32);
221 if (inUse) {
222 this.inUse[pos] |= mask;
223 } else {
224 this.inUse[pos] &= ~mask;
225 }
226 }
227
228
233 private int search(long key) {
234 return (handleToLast < 0) ? 0 : search(key, 0, handleToLast);
235 }
236
237
244 private int search(long key, int low, int high) {
245 if (low > high) {
246 throw new IllegalArgumentException ("low should be <= high; low == " + low + ", high == " + high + ", key == " + key + ", handleToLast == " + handleToLast);
247 }
248 for(;;) {
249 int result = (low + high) / 2;
250 if (low >= high || keys[result] == key) {
251 return result;
252 }
253 if (key < keys[result]) {
254 high = result - 1;
255 } else {
256 low = result + 1;
257 }
258 }
259 }
260
261
264 private void compress() {
265 handleToLast = -1;
266 for(int i = 0; i < keys.length; i++) {
267 if (isInUse(i)) {
268 handleToLast++;
269 if (i > handleToLast) {
270 move(i, handleToLast);
271 }
272 } else {
273 keys[i] = 0;
276 }
277 }
278 }
279
280 protected void move(int handleFrom, int handleTo) {
281 if (!isInUse(handleFrom) || isInUse(handleTo)) {
282 throw new IllegalArgumentException ("handleFrom must be in use and handleTo must not");
283 }
284 keys[handleTo] = keys[handleFrom];
285 keys[handleFrom] = 0;
288 setInUse(handleFrom, false);
289 setInUse(handleTo, true);
290 }
291
292 public String toString() {
293 StringBuffer result = new StringBuffer ("[handleToLast=");
294 result.append(handleToLast).append(";");
295 for (int i = 0; i < keys.length; i++) {
296 result.append(keys[i]);
297 if (!isInUse(i)) {
298 result.append("D");
299 }
300 result.append(",");
301 }
302 return result.toString();
303 }
304
305
308 public int size() {
309 return size;
310 }
311
312
314 }
358 |
Popular Tags |
Java API By Example, From Geeks To Geeks.