/* 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 |