blob: cd1cbbabafcd2dd1272ac5fe5e1cdb86252ac8cf [file] [log] [blame]
/* 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 <assert.h>
#include <stdlib.h> /* exit, free, malloc */
#include <string.h> /* memcpy */
#include "../common/types.h"
#include "./port.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)
static void* DefaultAllocFunc(void* opaque, size_t size) {
BROTLI_UNUSED(opaque);
return malloc(size);
}
static void DefaultFreeFunc(void* opaque, void* address) {
BROTLI_UNUSED(opaque);
free(address);
}
void BrotliInitMemoryManager(
MemoryManager* m, brotli_alloc_func alloc_func, brotli_free_func free_func,
void* opaque) {
if (!alloc_func) {
m->alloc_func = DefaultAllocFunc;
m->free_func = DefaultFreeFunc;
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;
assert(m->new_freed == 0);
}
if (m->new_allocated != 0) {
assert(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 */
#if defined(__cplusplus) || defined(c_plusplus)
} /* extern "C" */
#endif