libav1/dx/vp9dx_linear_allocator.cpp

/*
 * Copyright 2020 Google LLC
 *
 */

/*
 * Copyright (c) 2020, Alliance for Open Media. All rights reserved
 *
 * This source code is subject to the terms of the BSD 2 Clause License and
 * the Alliance for Open Media Patent License 1.0. If the BSD 2 Clause License
 * was not distributed with this source code in the LICENSE file, you can
 * obtain it at www.aomedia.org/license/software. If the Alliance for Open
 * Media Patent License 1.0 was not distributed with this source code in the
 * PATENTS file, you can obtain it at www.aomedia.org/license/patent.
 */

#include "dx/vp9dx_linear_allocator.h"

static void remove_item(AllocItem* items, int items_count, int pos) {
  for (int i = pos + 1; i < items_count; ++i) {
    items[i - 1] = items[i];
  }
}

void la_init(LinearAllocator* allocator, uint8_t* ptr, size_t size) {
  allocator->base_ptr = ptr;
  allocator->free_chunks_count = 1;
  allocator->allocated_item_count = 0;
  allocator->free_mem_chuncks[0].offset = 0;
  allocator->free_mem_chuncks[0].size = size;
}

uint8_t* la_allocate(LinearAllocator* allocator, size_t size) {
  size = (size + BlockAlignment - 1) & (~(BlockAlignment - 1));

  int chunk = -1;
  for (int i = 0; i < allocator->free_chunks_count; ++i) {
    if (allocator->free_mem_chuncks[i].size >= size) {
      chunk = i;
      break;
    }
  }

  if (chunk == -1) return NULL;

  size_t offset = allocator->free_mem_chuncks[chunk].offset;
  allocator->free_mem_chuncks[chunk].offset += size;
  allocator->free_mem_chuncks[chunk].size -= size;

  if (allocator->free_mem_chuncks[chunk].size == 0) {
    remove_item(allocator->free_mem_chuncks, allocator->free_chunks_count, chunk);
    --allocator->free_chunks_count;
  }

  uint8_t* ptr = allocator->base_ptr + offset;

  allocator->allocated_items[allocator->allocated_item_count].size = size;
  allocator->allocated_items[allocator->allocated_item_count].offset = offset;

  ++allocator->allocated_item_count;
  return ptr;
}

void la_free(LinearAllocator* allocator, uint8_t* ptr) {
  size_t offset = (size_t)(ptr - allocator->base_ptr);
  int index = -1;
  for (int i = 0; i < allocator->allocated_item_count; ++i) {
    if (allocator->allocated_items[i].offset == offset) {
      index = i;
      break;
    }
  }

  if (index == -1) {
    return;
  }
  size_t size = allocator->allocated_items[index].size;

  remove_item(allocator->allocated_items, allocator->allocated_item_count, index);
  --allocator->allocated_item_count;

  int next_chunk = -1;
  for (int i = 0; i < allocator->free_chunks_count; ++i) {
    if (allocator->free_mem_chuncks[i].offset > offset) {
      next_chunk = i;
      break;
    }
  }

  int prev_chunk = (next_chunk == -1) ? allocator->free_chunks_count - 1 : next_chunk - 1;

  // add new memory chunk and/or merge with existing chunks
  if (prev_chunk >= 0 &&
      (allocator->free_mem_chuncks[prev_chunk].offset + allocator->free_mem_chuncks[prev_chunk].size) == offset) {
    allocator->free_mem_chuncks[prev_chunk].size += size;
    const size_t chunk_end =
        allocator->free_mem_chuncks[prev_chunk].offset + allocator->free_mem_chuncks[prev_chunk].size;
    if (prev_chunk < (allocator->free_chunks_count - 1) &&
        chunk_end == allocator->free_mem_chuncks[prev_chunk + 1].offset) {
      allocator->free_mem_chuncks[prev_chunk].size += allocator->free_mem_chuncks[prev_chunk + 1].size;
      remove_item(allocator->free_mem_chuncks, allocator->free_chunks_count, prev_chunk + 1);
      --allocator->free_chunks_count;
    }
  } else {
    if (next_chunk != -1 && (offset + size) == allocator->free_mem_chuncks[next_chunk].offset) {
      allocator->free_mem_chuncks[next_chunk].offset = offset;
      allocator->free_mem_chuncks[next_chunk].size += size;
    } else {
      int pos = allocator->free_chunks_count;
      if (next_chunk != -1) {
        pos = next_chunk;
        for (int i = allocator->free_chunks_count; i > next_chunk; --i) {
          allocator->free_mem_chuncks[i] = allocator->free_mem_chuncks[i - 1];
        }
      }
      allocator->free_mem_chuncks[pos].offset = offset;
      allocator->free_mem_chuncks[pos].size = size;
      ++allocator->free_chunks_count;
    }
  }
}