blob: 2ebb99e9be6c31f1b9c9e8379e03e1435c98d50c [file] [log] [blame]
// Copyright 2017 Google Inc. All Rights Reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
#include "cobalt/renderer/rasterizer/egl/rect_allocator.h"
#include <algorithm>
namespace cobalt {
namespace renderer {
namespace rasterizer {
namespace egl {
namespace {
// Sort by descending area then width and height. This will place smaller
// blocks at the end of the free list. Allocations will use the block with
// the smallest area of sufficient dimensions in order to minimize waste.
bool FirstRectIsBigger(const math::Rect& a, const math::Rect& b) {
const float area_a = a.width() * a.height();
const float area_b = b.width() * b.height();
return (area_a > area_b) ||
(area_a == area_b && (a.width() > b.width() ||
a.height() > b.height()));
}
} // namespace
RectAllocator::RectAllocator() {
Reset(math::Size(0, 0));
}
RectAllocator::RectAllocator(const math::Size& total_size) {
Reset(total_size);
}
void RectAllocator::Reset(const math::Size& total_size) {
total_size_ = total_size;
unused_.clear();
unused_.push_back(
math::Rect(0, 0, total_size_.width(), total_size_.height()));
}
math::Rect RectAllocator::Allocate(const math::Size& alloc_size) {
math::Rect allocation(0, 0, alloc_size.width(), alloc_size.height());
// Find the first block that is too small for the requested allocation.
MemoryList::iterator pos = std::upper_bound(
unused_.begin(), unused_.end(), allocation, FirstRectIsBigger);
// All blocks before "pos" will have sufficient area, but a sequential search
// must be used to find a block of sufficient width and height.
while (pos != unused_.begin()) {
--pos;
if (pos->width() >= allocation.width() &&
pos->height() >= allocation.height()) {
// Found an unused block big enough for the allocation.
math::Rect memory = *pos;
unused_.erase(pos);
// Use top-left of memory block for the allocation, and return the
// bottom and right portions as unused blocks. The split can be done
// in one of two ways:
// +-------+-------+ +-------+-------+
// | Alloc | Right | | Alloc | |
// +-------+-------+ or +-------+ Right +
// | Bottom | |Bottom | |
// +---------------+ +-------+-------+
allocation.set_x(memory.x());
allocation.set_y(memory.y());
if (memory.width() != allocation.width()) {
if (memory.height() != allocation.height()) {
// Return bottom and right of memory block as unused.
// Preserve the largest block.
const float remaining_width = memory.width() - allocation.width();
const float remaining_height = memory.height() - allocation.height();
if (memory.width() * remaining_height >=
remaining_width * memory.height()) {
// Bottom portion is bigger.
math::Rect right(memory.x() + allocation.width(), memory.y(),
remaining_width, allocation.height());
memory.set_y(memory.y() + allocation.height());
memory.set_height(remaining_height);
AddUnused(memory);
AddUnused(right);
} else {
// Right portion is bigger.
math::Rect bottom(memory.x(), memory.y() + allocation.height(),
allocation.width(), remaining_height);
memory.set_x(memory.x() + allocation.width());
memory.set_width(remaining_width);
AddUnused(memory);
AddUnused(bottom);
}
} else {
// Return right of memory block as unused.
memory.set_x(memory.x() + allocation.width());
memory.set_width(memory.width() - allocation.width());
AddUnused(memory);
}
} else if (memory.height() != allocation.height()) {
// Return bottom of memory block as unused.
memory.set_y(memory.y() + allocation.height());
memory.set_height(memory.height() - allocation.height());
AddUnused(memory);
}
return allocation;
}
}
// Not enough unused space for the allocation.
return math::Rect(0, 0, 0, 0);
}
void RectAllocator::AddUnused(const math::Rect& memory) {
DCHECK_LE(memory.right(), total_size_.width());
DCHECK_LE(memory.bottom(), total_size_.height());
MemoryList::iterator pos = std::lower_bound(
unused_.begin(), unused_.end(), memory, FirstRectIsBigger);
unused_.insert(pos, memory);
}
} // namespace egl
} // namespace rasterizer
} // namespace renderer
} // namespace cobalt