/* Copyright 2015 Google Inc. All Rights Reserved.

   Distributed under MIT license.

   See file LICENSE for detail or copy at https://opensource.org/licenses/MIT

*/

/* Algorithms for distributing the literals and commands of a metablock between

   block types and contexts. */

#include "memory.h"

#include <stdlib.h>  /* exit, free, malloc */

#include <string.h>  /* memcpy */

#include <brotli/types.h>

#include "../common/platform.h"

#if defined(__cplusplus) || defined(c_plusplus)

extern "C" {

#endif

#define MAX_PERM_ALLOCATED 128

#define MAX_NEW_ALLOCATED 64

#define MAX_NEW_FREED 64

#define PERM_ALLOCATED_OFFSET 0

#define NEW_ALLOCATED_OFFSET MAX_PERM_ALLOCATED

#define NEW_FREED_OFFSET (MAX_PERM_ALLOCATED + MAX_NEW_ALLOCATED)

void BrotliInitMemoryManager(

    MemoryManager* m, brotli_alloc_func alloc_func, brotli_free_func free_func,

    void* opaque) {

  if (!alloc_func) {

    m->alloc_func = BrotliDefaultAllocFunc;

    m->free_func = BrotliDefaultFreeFunc;

    m->opaque = 0;

  } else {

    m->alloc_func = alloc_func;

    m->free_func = free_func;

    m->opaque = opaque;

  }

#if !defined(BROTLI_ENCODER_EXIT_ON_OOM)

  m->is_oom = BROTLI_FALSE;

  m->perm_allocated = 0;

  m->new_allocated = 0;

  m->new_freed = 0;

#endif  /* BROTLI_ENCODER_EXIT_ON_OOM */

}

#if defined(BROTLI_ENCODER_EXIT_ON_OOM)

void* BrotliAllocate(MemoryManager* m, size_t n) {

  void* result = m->alloc_func(m->opaque, n);

  if (!result) exit(EXIT_FAILURE);

  return result;

}

void BrotliFree(MemoryManager* m, void* p) {

  m->free_func(m->opaque, p);

}

void BrotliWipeOutMemoryManager(MemoryManager* m) {

  BROTLI_UNUSED(m);

}

#else  /* BROTLI_ENCODER_EXIT_ON_OOM */

static void SortPointers(void** items, const size_t n) {

  /* Shell sort. */

  static const size_t gaps[] = {23, 10, 4, 1};

  int g = 0;

  for (; g < 4; ++g) {

    size_t gap = gaps[g];

    size_t i;

    for (i = gap; i < n; ++i) {

      size_t j = i;

      void* tmp = items[i];

      for (; j >= gap && tmp < items[j - gap]; j -= gap) {

        items[j] = items[j - gap];

      }

      items[j] = tmp;

    }

  }

}

static size_t Annihilate(void** a, size_t a_len, void** b, size_t b_len) {

  size_t a_read_index = 0;

  size_t b_read_index = 0;

  size_t a_write_index = 0;

  size_t b_write_index = 0;

  size_t annihilated = 0;

  while (a_read_index < a_len && b_read_index < b_len) {

    if (a[a_read_index] == b[b_read_index]) {

      a_read_index++;

      b_read_index++;

      annihilated++;

    } else if (a[a_read_index] < b[b_read_index]) {

      a[a_write_index++] = a[a_read_index++];

    } else {

      b[b_write_index++] = b[b_read_index++];

    }

  }

  while (a_read_index < a_len) a[a_write_index++] = a[a_read_index++];

  while (b_read_index < b_len) b[b_write_index++] = b[b_read_index++];

  return annihilated;

}

static void CollectGarbagePointers(MemoryManager* m) {

  size_t annihilated;

  SortPointers(m->pointers + NEW_ALLOCATED_OFFSET, m->new_allocated);

  SortPointers(m->pointers + NEW_FREED_OFFSET, m->new_freed);

  annihilated = Annihilate(

      m->pointers + NEW_ALLOCATED_OFFSET, m->new_allocated,

      m->pointers + NEW_FREED_OFFSET, m->new_freed);

  m->new_allocated -= annihilated;

  m->new_freed -= annihilated;

  if (m->new_freed != 0) {

    annihilated = Annihilate(

        m->pointers + PERM_ALLOCATED_OFFSET, m->perm_allocated,

        m->pointers + NEW_FREED_OFFSET, m->new_freed);

    m->perm_allocated -= annihilated;

    m->new_freed -= annihilated;

    BROTLI_DCHECK(m->new_freed == 0);

  }

  if (m->new_allocated != 0) {

    BROTLI_DCHECK(m->perm_allocated + m->new_allocated <= MAX_PERM_ALLOCATED);

    memcpy(m->pointers + PERM_ALLOCATED_OFFSET + m->perm_allocated,

           m->pointers + NEW_ALLOCATED_OFFSET,

           sizeof(void*) * m->new_allocated);

    m->perm_allocated += m->new_allocated;

    m->new_allocated = 0;

    SortPointers(m->pointers + PERM_ALLOCATED_OFFSET, m->perm_allocated);

  }

}

void* BrotliAllocate(MemoryManager* m, size_t n) {

  void* result = m->alloc_func(m->opaque, n);

  if (!result) {

    m->is_oom = BROTLI_TRUE;

    return NULL;

  }

  if (m->new_allocated == MAX_NEW_ALLOCATED) CollectGarbagePointers(m);

  m->pointers[NEW_ALLOCATED_OFFSET + (m->new_allocated++)] = result;

  return result;

}

void BrotliFree(MemoryManager* m, void* p) {

  if (!p) return;

  m->free_func(m->opaque, p);

  if (m->new_freed == MAX_NEW_FREED) CollectGarbagePointers(m);

  m->pointers[NEW_FREED_OFFSET + (m->new_freed++)] = p;

}

void BrotliWipeOutMemoryManager(MemoryManager* m) {

  size_t i;

  CollectGarbagePointers(m);

  /* Now all unfreed pointers are in perm-allocated list. */

  for (i = 0; i < m->perm_allocated; ++i) {

    m->free_func(m->opaque, m->pointers[PERM_ALLOCATED_OFFSET + i]);

  }

  m->perm_allocated = 0;

}

#endif  /* BROTLI_ENCODER_EXIT_ON_OOM */

void* BrotliBootstrapAlloc(size_t size,

    brotli_alloc_func alloc_func, brotli_free_func free_func, void* opaque) {

  if (!alloc_func && !free_func) {

    return malloc(size);

  } else if (alloc_func && free_func) {

    return alloc_func(opaque, size);

  }

  return NULL;

}

void BrotliBootstrapFree(void* address, MemoryManager* m) {

  if (!address) {

    /* Should not happen! */

    return;

  } else {

    /* Copy values, as those would be freed. */

    brotli_free_func free_func = m->free_func;

    void* opaque = m->opaque;

    free_func(opaque, address);

  }

}

#if defined(__cplusplus) || defined(c_plusplus)

}  /* extern "C" */

#endif