allocate_nearest.c

static bool find_smallest_nearby_buffer(struct range_finder *restrict range) {
  struct selected_range current = {0, SIZE_MAX};
  size_t pickiness_boundary =
      (range->index + 1) * 64 +
      // the bigger the request range, the less we care about locality
      +range->size_required;

  while (find_next(range)) {
    if (range->size_required == range->selection.size_available)
      return true;
    if (current.size_available > range->selection.size_available) {
      current = range->selection;
    }
    if (range->selection.position > pickiness_boundary) {
      // We have gone too far? Stop being choosy
      if (current.size_available < range->selection.size_available) {
        range->selection = current;
      }
      return true;
    }
  }

  range->selection = current;

  return current.size_available != SIZE_MAX;
}

static bool find_best_buffer(uint64_t *bitmap, size_t bitmap_size,
                             size_t size_required, size_t near_pos,
                             size_t *bit_pos) {
  if (!size_required || near_pos / 64 >= bitmap_size)
    return false;

  size_t high = near_pos / 64;

  struct range_finder range;
  init_range(bitmap + high, bitmap_size - high, size_required, &range);

  if (find_smallest_nearby_buffer(&range)) {
    *bit_pos = range.selection.position + high * 64;
    return true;
  }
  if (!high) {
    return false; // already scanned it all
  }

  // we search _high_, couldn't find anything, maybe lower?
  init_range(bitmap, high, size_required, &range);
  if (find_next(&range)) {
    *bit_pos = range.selection.position;
    return true;
  }

  return false;
}