1 |
| package org.drools.util; |
2 |
| |
3 |
| import java.io.Serializable; |
4 |
| import java.util.Arrays; |
5 |
| import java.util.Collection; |
6 |
| |
7 |
| |
8 |
| |
9 |
| |
10 |
| |
11 |
| |
12 |
| |
13 |
| |
14 |
| |
15 |
| |
16 |
| |
17 |
| |
18 |
| |
19 |
| |
20 |
| |
21 |
| |
22 |
| |
23 |
| |
24 |
| |
25 |
| |
26 |
| |
27 |
| |
28 |
| |
29 |
| |
30 |
| |
31 |
| |
32 |
| |
33 |
| |
34 |
| |
35 |
| |
36 |
| |
37 |
| |
38 |
| |
39 |
| |
40 |
| |
41 |
| |
42 |
| |
43 |
| |
44 |
| |
45 |
| |
46 |
| |
47 |
| |
48 |
| |
49 |
| |
50 |
| |
51 |
| public class PrimitiveLongMap |
52 |
| implements |
53 |
| Serializable |
54 |
| { |
55 |
| private final static Object NULL = new Serializable( ) |
56 |
| { |
57 |
| }; |
58 |
| |
59 |
| private final int indexIntervals; |
60 |
| private final int intervalShifts; |
61 |
| private final int midIntervalPoint; |
62 |
| private final int tableSize; |
63 |
| private final int shifts; |
64 |
| private final int doubleShifts; |
65 |
| private final Page firstPage; |
66 |
| private Page lastPage; |
67 |
| private int lastPageId; |
68 |
| private long maxKey; |
69 |
| private Page[] pageIndex; |
70 |
| |
71 |
1
| public PrimitiveLongMap()
|
72 |
| { |
73 |
1
| this( 32,
|
74 |
| 8 ); |
75 |
| } |
76 |
| |
77 |
0
| public PrimitiveLongMap(int tableSize)
|
78 |
| { |
79 |
0
| this( tableSize,
|
80 |
| 8 ); |
81 |
| } |
82 |
| |
83 |
78
| public PrimitiveLongMap(int tableSize,
|
84 |
| int indexIntervals) |
85 |
| { |
86 |
| |
87 |
78
| int i = 1;
|
88 |
78
| int size = 2;
|
89 |
78
| while ( size < indexIntervals )
|
90 |
| { |
91 |
149
| size <<= 1;
|
92 |
149
| ++i;
|
93 |
| } |
94 |
78
| this.indexIntervals = size;
|
95 |
78
| this.intervalShifts = i;
|
96 |
| |
97 |
| |
98 |
78
| i = 1;
|
99 |
78
| size = 2;
|
100 |
78
| while ( size < tableSize )
|
101 |
| { |
102 |
298
| size <<= 1;
|
103 |
298
| ++i;
|
104 |
| } |
105 |
78
| this.tableSize = size;
|
106 |
78
| this.shifts = i;
|
107 |
78
| this.doubleShifts = this.shifts << 1;
|
108 |
| |
109 |
| |
110 |
78
| this.midIntervalPoint = ((this.tableSize << this.shifts) << this.intervalShifts) >> 1;
|
111 |
| |
112 |
78
| this.lastPageId = 0;
|
113 |
| |
114 |
| |
115 |
| |
116 |
| |
117 |
78
| this.firstPage = new Page( null,
|
118 |
| this.lastPageId, |
119 |
| this.tableSize ); |
120 |
78
| this.maxKey = this.lastPageId + 1 << this.doubleShifts;
|
121 |
| |
122 |
78
| pageIndex = new Page[]{this.firstPage};
|
123 |
| |
124 |
| |
125 |
78
| this.lastPage = this.firstPage;
|
126 |
| } |
127 |
| |
128 |
1713
| public Object put(long key,
|
129 |
| Object value) |
130 |
| { |
131 |
1713
| if ( key < 0 )
|
132 |
| { |
133 |
1
| throw new IllegalArgumentException( "-ve keys not supported: " + key );
|
134 |
| } |
135 |
| |
136 |
| |
137 |
| |
138 |
1712
| if ( value == null )
|
139 |
| { |
140 |
0
| value = NULL;
|
141 |
| } |
142 |
| |
143 |
1712
| Page page = findPage( key );
|
144 |
| |
145 |
1712
| Object oldValue = page.put( key,
|
146 |
| value ); |
147 |
| |
148 |
1712
| return oldValue;
|
149 |
| } |
150 |
| |
151 |
380
| public Object remove(long key)
|
152 |
| { |
153 |
380
| if ( key > this.maxKey || key < 0 )
|
154 |
| { |
155 |
2
| return null;
|
156 |
| } |
157 |
| |
158 |
378
| Page page = findPage( key );
|
159 |
| |
160 |
378
| Object oldValue = page.put( key,
|
161 |
| null ); |
162 |
| |
163 |
378
| if ( this.lastPageId != 0 && this.lastPage.isEmpty( ) )
|
164 |
| { |
165 |
3
| shrinkPages( this.lastPageId );
|
166 |
| } |
167 |
| |
168 |
378
| return oldValue;
|
169 |
| } |
170 |
| |
171 |
85204
| public Object get(long key)
|
172 |
| { |
173 |
85204
| if ( key > this.maxKey || key < 0 )
|
174 |
| { |
175 |
1
| return null;
|
176 |
| } |
177 |
| |
178 |
85203
| Object value = findPage( key ).get( key );
|
179 |
| |
180 |
| |
181 |
85203
| if ( value == NULL )
|
182 |
| { |
183 |
0
| value = null;
|
184 |
| } |
185 |
85203
| return value;
|
186 |
| } |
187 |
| |
188 |
24
| public Collection values()
|
189 |
| { |
190 |
24
| CompositeCollection collection = new CompositeCollection( );
|
191 |
24
| Page page = this.firstPage;
|
192 |
24
| while ( page != null && page.getPageId( ) <= this.lastPageId )
|
193 |
| { |
194 |
24
| collection.addComposited( Arrays.asList( page.getValues( ) ) );
|
195 |
24
| page = page.getNextSibling( );
|
196 |
| } |
197 |
24
| return collection;
|
198 |
| } |
199 |
| |
200 |
8
| public boolean containsKey(long key)
|
201 |
| { |
202 |
2
| if ( key < 0 ) return false;
|
203 |
| |
204 |
6
| return get( key ) != null;
|
205 |
| } |
206 |
| |
207 |
| |
208 |
| |
209 |
| |
210 |
6
| public Page expandPages(int toPageId)
|
211 |
| { |
212 |
6
| for ( int x = this.lastPageId; x < toPageId; x++ )
|
213 |
| { |
214 |
13
| this.lastPage = new Page( this.lastPage,
|
215 |
| ++this.lastPageId, |
216 |
| this.tableSize ); |
217 |
| |
218 |
13
| if ( this.lastPage.getPageId( ) % this.indexIntervals == 0 )
|
219 |
| { |
220 |
2
| int newSize = this.pageIndex.length + 1;
|
221 |
2
| resizeIndex( newSize );
|
222 |
2
| this.pageIndex[newSize - 1] = this.lastPage;
|
223 |
| } |
224 |
| } |
225 |
6
| this.maxKey = (this.lastPageId + 1 << this.doubleShifts) - 1;
|
226 |
6
| return this.lastPage;
|
227 |
| } |
228 |
| |
229 |
| |
230 |
| |
231 |
| |
232 |
3
| public void shrinkPages(int toPageId)
|
233 |
| { |
234 |
3
| for ( int x = this.lastPageId; x >= toPageId; x-- )
|
235 |
| { |
236 |
| |
237 |
3
| if ( ( this.lastPageId ) % this.indexIntervals == 0 && this.lastPageId != 0 )
|
238 |
| { |
239 |
1
| resizeIndex( this.pageIndex.length - 1 );
|
240 |
| } |
241 |
| |
242 |
3
| Page page = this.lastPage.getPreviousSibling( );
|
243 |
3
| page.setNextSibling( null );
|
244 |
3
| this.lastPage.clear( );
|
245 |
3
| this.lastPage = page;
|
246 |
3
| this.lastPageId = page.getPageId( );
|
247 |
| |
248 |
| } |
249 |
| } |
250 |
| |
251 |
3
| public void resizeIndex(int newSize)
|
252 |
| { |
253 |
3
| Page[] newIndex = new Page[newSize];
|
254 |
3
| System.arraycopy( this.pageIndex,
|
255 |
| 0, |
256 |
| newIndex, |
257 |
| 0, |
258 |
| newSize - 1 ); |
259 |
3
| this.pageIndex = newIndex;
|
260 |
| } |
261 |
| |
262 |
87293
| private Page findPage(long key)
|
263 |
| { |
264 |
| |
265 |
87293
| int pageId = (int) key >> this.doubleShifts;
|
266 |
87293
| Page page;
|
267 |
| |
268 |
| |
269 |
87293
| if ( pageId == this.lastPageId )
|
270 |
| { |
271 |
87286
| page = this.lastPage;
|
272 |
| } |
273 |
| |
274 |
7
| else if ( pageId == 0 )
|
275 |
| { |
276 |
0
| page = this.firstPage;
|
277 |
| } |
278 |
| |
279 |
7
| else if ( pageId > this.lastPageId )
|
280 |
| { |
281 |
6
| page = expandPages( pageId );
|
282 |
| } |
283 |
| else |
284 |
| { |
285 |
| |
286 |
1
| int offset = pageId >> this.intervalShifts;
|
287 |
| |
288 |
1
| if ( (offset != (this.pageIndex.length - 1)) && ((key - (offset << this.intervalShifts << this.doubleShifts)) > this.midIntervalPoint) )
|
289 |
| { |
290 |
| |
291 |
1
| page = this.pageIndex[offset + 1];
|
292 |
1
| while ( page.getPageId( ) != pageId )
|
293 |
| { |
294 |
1
| page = page.getPreviousSibling( );
|
295 |
| } |
296 |
| } |
297 |
| else |
298 |
| { |
299 |
| |
300 |
0
| page = pageIndex[offset];
|
301 |
0
| while ( page.getPageId( ) != pageId )
|
302 |
| { |
303 |
0
| page = page.getNextSibling( );
|
304 |
| } |
305 |
| } |
306 |
| } |
307 |
| |
308 |
87293
| return page;
|
309 |
| } |
310 |
| |
311 |
| private static class Page |
312 |
| implements |
313 |
| Serializable |
314 |
| { |
315 |
| private final int pageSize; |
316 |
| private final int pageId; |
317 |
| private final int shifts; |
318 |
| private final int tableSize; |
319 |
| private Page nextSibling; |
320 |
| private Page previousSibling; |
321 |
| private Object[][] tables; |
322 |
| private int filledSlots; |
323 |
| |
324 |
91
| Page(Page previousSibling,
|
325 |
| int pageId, |
326 |
| int tableSize) |
327 |
| { |
328 |
| |
329 |
91
| int i = 1;
|
330 |
91
| int size = 2;
|
331 |
91
| while ( size < tableSize )
|
332 |
| { |
333 |
342
| size <<= 1;
|
334 |
342
| ++i;
|
335 |
| } |
336 |
| |
337 |
91
| this.tableSize = size;
|
338 |
91
| this.shifts = i;
|
339 |
| |
340 |
| |
341 |
91
| this.previousSibling = previousSibling;
|
342 |
91
| if ( this.previousSibling != null )
|
343 |
| { |
344 |
13
| this.previousSibling.setNextSibling( this );
|
345 |
| } |
346 |
91
| this.pageId = pageId;
|
347 |
91
| this.pageSize = tableSize << this.shifts;
|
348 |
| } |
349 |
| |
350 |
42
| public int getPageId()
|
351 |
| { |
352 |
42
| return this.pageId;
|
353 |
| } |
354 |
| |
355 |
16
| void setNextSibling(Page nextSibling)
|
356 |
| { |
357 |
16
| this.nextSibling = nextSibling;
|
358 |
| } |
359 |
| |
360 |
24
| public Page getNextSibling()
|
361 |
| { |
362 |
24
| return this.nextSibling;
|
363 |
| } |
364 |
| |
365 |
0
| void setPreviousSibling(Page previousSibling)
|
366 |
| { |
367 |
0
| this.previousSibling = previousSibling;
|
368 |
| } |
369 |
| |
370 |
4
| public Page getPreviousSibling()
|
371 |
| { |
372 |
4
| return this.previousSibling;
|
373 |
| } |
374 |
| |
375 |
85203
| public Object get(long key)
|
376 |
| { |
377 |
85203
| if ( this.tables == null )
|
378 |
| { |
379 |
5
| return null;
|
380 |
| } |
381 |
| |
382 |
85198
| key -= this.pageSize * this.pageId;
|
383 |
| |
384 |
| |
385 |
85198
| int page = (int) key >> this.shifts;
|
386 |
| |
387 |
| |
388 |
85198
| int offset = page << this.shifts;
|
389 |
| |
390 |
| |
391 |
85198
| return this.tables[page][(int) key - offset];
|
392 |
| } |
393 |
| |
394 |
2090
| public Object put(long key,
|
395 |
| Object newValue) |
396 |
| { |
397 |
2090
| if ( this.tables == null )
|
398 |
| { |
399 |
| |
400 |
37
| this.tables = new Object[this.tableSize][this.tableSize];
|
401 |
| } |
402 |
| |
403 |
| |
404 |
2090
| key -= this.pageSize * this.pageId;
|
405 |
| |
406 |
| |
407 |
2090
| int table = (int) key >> this.shifts;
|
408 |
| |
409 |
| |
410 |
2090
| int offset = table << this.shifts;
|
411 |
| |
412 |
| |
413 |
2090
| int slot = (int) key - offset;
|
414 |
| |
415 |
| |
416 |
2090
| Object oldValue = this.tables[table][slot];
|
417 |
2090
| this.tables[table][slot] = newValue;
|
418 |
| |
419 |
| |
420 |
2090
| if ( oldValue == null && newValue != null )
|
421 |
| { |
422 |
1712
| this.filledSlots++;
|
423 |
| } |
424 |
378
| else if ( oldValue != null && newValue == null )
|
425 |
| { |
426 |
375
| this.filledSlots--;
|
427 |
| } |
428 |
| |
429 |
| |
430 |
| |
431 |
2090
| if ( this.filledSlots == 0 )
|
432 |
| { |
433 |
10
| this.tables = null;
|
434 |
| } |
435 |
| |
436 |
2090
| return oldValue;
|
437 |
| } |
438 |
| |
439 |
0
| Object[][] getTables()
|
440 |
| { |
441 |
0
| return this.tables;
|
442 |
| } |
443 |
| |
444 |
24
| Object[] getValues()
|
445 |
| { |
446 |
24
| Object[] values = new Object[this.filledSlots];
|
447 |
24
| if ( values.length == 0 )
|
448 |
| { |
449 |
3
| return values;
|
450 |
| } |
451 |
21
| int x = 0;
|
452 |
21
| Object value;
|
453 |
21
| for ( int i = 0; i < this.tableSize; i++ )
|
454 |
| { |
455 |
672
| for ( int j = 0; j < this.tableSize; j++ )
|
456 |
| { |
457 |
21504
| value = this.tables[i][j];
|
458 |
21504
| if ( value != null )
|
459 |
| { |
460 |
| |
461 |
821
| if ( value == NULL )
|
462 |
| { |
463 |
0
| value = null;
|
464 |
| } |
465 |
821
| values[x] = value;
|
466 |
821
| x++;
|
467 |
| } |
468 |
| } |
469 |
| } |
470 |
21
| return values;
|
471 |
| } |
472 |
| |
473 |
4
| public boolean isEmpty()
|
474 |
| { |
475 |
4
| return this.filledSlots == 0;
|
476 |
| } |
477 |
| |
478 |
3
| void clear()
|
479 |
| { |
480 |
3
| this.previousSibling = null;
|
481 |
3
| this.nextSibling = null;
|
482 |
3
| this.tables = null;
|
483 |
| } |
484 |
| } |
485 |
| } |