Compaction based garbage collection about faster HOT 3 CLOSED

void garbage_collect(Segment segment, List<Segment> laterSegments) {
  List<Record> liveRecords;
  Bitmap U = new Bitmap();
  foreach(Segment other in laterSegments) {
    U.union(other.GetBitmap());
  }
  Bitmap B = segment.GetBitmap();
  Bitmap non_live_keys = B.intersect(U);
  for(Record record in segment reverse order) {
    if(!non_live_keys.Exists(record.key)) {
      liveRecords.Add(record);
      // we need only the latest value mapping in the segment
      non_live_keys.Insert(record.key); 
    }
  }
}

void garbage_collect(Segment segment, List<Segment> laterSegments) {
// Build a set of keys in the page/segment to be GCed
Set<Key> keys;
foreach(Record record in segment) {
  if(!keys.Has(record.key)) {
    keys.Insert(record.key);
  }
}

BloomFilter current = segment.GetBloomFilter();
for(auto other : laterSegments) {
  BloomFilter otherBF = other.GetBloomFilter();
  auto common = otherBF.intersection(current);
  auto check = false;
  if(!common.Empty()) {
    for(auto key: keys) {
      if(common.Exists(key)) {
        check = true;
        break;
      }
    }
    // our bloom filter check tells us that there might be some 
    // keys in this page that can make invalidate some live keys
    if(check) {
      for(Record rec in other) {
        if(keys.Has(rec.key)) {
          keys.Delete(rec.key);
        }
      }
      // update our bloom filter for the new set of keys
      // hmm this is inefficient - we could use a counting filter
      // that supports delete. 
      current = new BloomFilter();
      for(auto key: keys) {
        current.Add(key);
      }
    }
  }
}
}

hashTable = create hash table from segments[0].keys file to {valid, invalid}
for(int i = 1; i <= n; i++) {
  other = segments[i].keys;
  foreach(var key in other) {
    if(hashTable[key] == 'valid') {
      hashTable[key] = 'invalid';
    }
  }
}

foreach(var key in hashTable.keys) {
  if(hashTable[key] == 'invalid') {
    create corresponding record at tail;
  }
}

res = segments[0].sorted_keys;
for(int i = 1; i <= n; i++) {
 seg = res;
 res.clear();
 other = segments[1].sorted_keys;
 seg.begin();
 other.begin();
 while(seg.hasNext() && other.hasNext()) {
   if(seg.front() == other.front()) {
    seg.next();
    other.next();
   } else if (seg.front() < other.front()) {
    res.add(seg.front());
    seg.next();
   } else {
    other.next();
   }
 }
 while(seg.hasNext()) {
  res.add(seg.next());
 }
 seg.close();
 other.close();
 res.close();
}