Not logged in.  Login/Logout/Register | List snippets | | Create snippet | Upload image | Upload data

55
LINES

< > BotCompany Repo | #1029334 - FreeList64 [64 bit free list]

JavaX fragment (include) [tags: use-pretranspiled]

Libraryless. Click here for Pure Java version (3635L/23K).

sclass FreeList64 {
  MultiSetMap<Long, LongRange> byLength = multiSetMap_innerCustomCompactTreeSet_outerTreeMap(longRangeComparatorByStart());
  CompactTreeSet<LongRange> inOrder = new(longRangeComparatorByStart());
  long totalFree;
  
  void add(LongRange r) {
    if (empty(r)) ret;
    // only special case here is merging with previous and/or following entry
    LongRange before = inOrder.floor(r), after = inOrder.ceiling(r);
    if (before != null && before.end == r.start) {
      r = LongRange(before.start, r.end);
      remove(before);
    }
    if (after != null && after.start == r.end) {
      r = LongRange(r.start, after.end);
      remove(after);
    }
      
    inOrder.add(r);
    byLength.add(r.length(), r);
    totalFree += r.length();
  }
  
  void remove(LongRange r) {
    if (empty(r)) ret;
    LongRange r2 = inOrder.floor(r);
    if (r2 == null) fail("User error");
    if (eq(r, r2)) {
      inOrder.remove(r2);
      byLength.remove(r2.length(), r2);
      totalFree -= r2.length();
      ret;
    }
    
    // remove full range, add back left and right remainders
    remove(r2);
    add(LongRange(r2.start, r.start));
    add(LongRange(r.end, r2.end));
  }
  
  LongRange findFreeSpace(long minSize) {
    Map.Entry<Long, Set<LongRange>> e = ((NavigableMap) byLength.data).ceilingEntry(minSize);
    ret e == null ? null : first(e.getValue());
  }
  
  long totalFree() { ret totalFree; }
  
  void clear {
    byLength.clear();
    inOrder.clear();
    totalFree = 0;
  }
  
  LongRange highestFreeRange() { ret last(inOrder); }
}

Author comment

Began life as a copy of #1029228

download  show line numbers  debug dex   

Travelled to 4 computer(s): bhatertpkbcr, mqqgnosmbjvj, pzhvpgtvlbxg, 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: 5 / 17
Referenced in: [show references]

Formerly at http://tinybrain.de/1029334 & http://1029334.tinybrain.de