Index: third_party/brotli/enc/memory.c |
diff --git a/third_party/brotli/enc/memory.c b/third_party/brotli/enc/memory.c |
new file mode 100644 |
index 0000000000000000000000000000000000000000..5aa5a2246b33a7e7ad14b3d2a064a88d14ba8450 |
--- /dev/null |
+++ b/third_party/brotli/enc/memory.c |
@@ -0,0 +1,181 @@ |
+/* 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 <brotli/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 |