Libraryless. Click here for Pure Java version (3635L/23K).
1 | sclass FreeList64 {
|
2 | MultiSetMap<Long, LongRange> byLength = multiSetMap_innerCustomCompactTreeSet_outerTreeMap(longRangeComparatorByStart()); |
3 | CompactTreeSet<LongRange> inOrder = new(longRangeComparatorByStart()); |
4 | long totalFree; |
5 | |
6 | void add(LongRange r) {
|
7 | if (empty(r)) ret; |
8 | // only special case here is merging with previous and/or following entry |
9 | LongRange before = inOrder.floor(r), after = inOrder.ceiling(r); |
10 | if (before != null && before.end == r.start) {
|
11 | r = LongRange(before.start, r.end); |
12 | remove(before); |
13 | } |
14 | if (after != null && after.start == r.end) {
|
15 | r = LongRange(r.start, after.end); |
16 | remove(after); |
17 | } |
18 | |
19 | inOrder.add(r); |
20 | byLength.add(r.length(), r); |
21 | totalFree += r.length(); |
22 | } |
23 | |
24 | void remove(LongRange r) {
|
25 | if (empty(r)) ret; |
26 | LongRange r2 = inOrder.floor(r); |
27 | if (r2 == null) fail("User error");
|
28 | if (eq(r, r2)) {
|
29 | inOrder.remove(r2); |
30 | byLength.remove(r2.length(), r2); |
31 | totalFree -= r2.length(); |
32 | ret; |
33 | } |
34 | |
35 | // remove full range, add back left and right remainders |
36 | remove(r2); |
37 | add(LongRange(r2.start, r.start)); |
38 | add(LongRange(r.end, r2.end)); |
39 | } |
40 | |
41 | LongRange findFreeSpace(long minSize) {
|
42 | Map.Entry<Long, Set<LongRange>> e = ((NavigableMap) byLength.data).ceilingEntry(minSize); |
43 | ret e == null ? null : first(e.getValue()); |
44 | } |
45 | |
46 | long totalFree() { ret totalFree; }
|
47 | |
48 | void clear {
|
49 | byLength.clear(); |
50 | inOrder.clear(); |
51 | totalFree = 0; |
52 | } |
53 | |
54 | LongRange highestFreeRange() { ret last(inOrder); }
|
55 | } |
Began life as a copy of #1029228
download show line numbers debug dex old transpilations
Travelled to 7 computer(s): bhatertpkbcr, mqqgnosmbjvj, pyentgdyhuwx, pzhvpgtvlbxg, tvejysmllsmz, vouqrxazstgt, xrpafgyirdlv
No comments. add comment
| Snippet ID: | #1029334 |
| Snippet name: | FreeList64 [64 bit free list] |
| Eternal ID of this version: | #1029334/1 |
| Text MD5: | 871e2f8fe447c0ac3a37aaf09f4f72f4 |
| Transpilation MD5: | 69a5de71d6198a9785077c47de64605d |
| Author: | stefan |
| Category: | javax |
| Type: | JavaX fragment (include) |
| Public (visible to everyone): | Yes |
| Archived (hidden from active list): | No |
| Created/modified: | 2020-07-31 16:35:13 |
| Source code size: | 1621 bytes / 55 lines |
| Pitched / IR pitched: | No / No |
| Views / Downloads: | 134 / 381 |
| Referenced in: | [show references] |