Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/brotli/c/enc/memory.c @ 2:b50eed0cc0ef upstream

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ADD: MuPDF v1.26.7: the MuPDF source as downloaded by a default build of PyMuPDF 1.26.4. The directory name has changed: no version number in the expanded directory now.
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:43:07 +0200
parents
children
comparison
equal deleted inserted replaced
1:1d09e1dec1d9 2:b50eed0cc0ef
1 /* Copyright 2015 Google Inc. All Rights Reserved.
2
3 Distributed under MIT license.
4 See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
5 */
6
7 /* Algorithms for distributing the literals and commands of a metablock between
8 block types and contexts. */
9
10 #include "memory.h"
11
12 #include <stdlib.h> /* exit, free, malloc */
13 #include <string.h> /* memcpy */
14
15 #include <brotli/types.h>
16
17 #include "../common/platform.h"
18
19 #if defined(__cplusplus) || defined(c_plusplus)
20 extern "C" {
21 #endif
22
23 #define MAX_NEW_ALLOCATED (BROTLI_ENCODER_MEMORY_MANAGER_SLOTS >> 2)
24 #define MAX_NEW_FREED (BROTLI_ENCODER_MEMORY_MANAGER_SLOTS >> 2)
25 #define MAX_PERM_ALLOCATED (BROTLI_ENCODER_MEMORY_MANAGER_SLOTS >> 1)
26
27 #define PERM_ALLOCATED_OFFSET 0
28 #define NEW_ALLOCATED_OFFSET MAX_PERM_ALLOCATED
29 #define NEW_FREED_OFFSET (MAX_PERM_ALLOCATED + MAX_NEW_ALLOCATED)
30
31 void BrotliInitMemoryManager(
32 MemoryManager* m, brotli_alloc_func alloc_func, brotli_free_func free_func,
33 void* opaque) {
34 if (!alloc_func) {
35 m->alloc_func = BrotliDefaultAllocFunc;
36 m->free_func = BrotliDefaultFreeFunc;
37 m->opaque = 0;
38 } else {
39 m->alloc_func = alloc_func;
40 m->free_func = free_func;
41 m->opaque = opaque;
42 }
43 #if !defined(BROTLI_ENCODER_EXIT_ON_OOM)
44 m->is_oom = BROTLI_FALSE;
45 m->perm_allocated = 0;
46 m->new_allocated = 0;
47 m->new_freed = 0;
48 #endif /* BROTLI_ENCODER_EXIT_ON_OOM */
49 }
50
51 #if defined(BROTLI_ENCODER_EXIT_ON_OOM)
52
53 void* BrotliAllocate(MemoryManager* m, size_t n) {
54 void* result = m->alloc_func(m->opaque, n);
55 if (!result) exit(EXIT_FAILURE);
56 return result;
57 }
58
59 void BrotliFree(MemoryManager* m, void* p) {
60 m->free_func(m->opaque, p);
61 }
62
63 void BrotliWipeOutMemoryManager(MemoryManager* m) {
64 BROTLI_UNUSED(m);
65 }
66
67 #else /* BROTLI_ENCODER_EXIT_ON_OOM */
68
69 static void SortPointers(void** items, const size_t n) {
70 /* Shell sort. */
71 /* TODO(eustas): fine-tune for "many slots" case */
72 static const size_t gaps[] = {23, 10, 4, 1};
73 int g = 0;
74 for (; g < 4; ++g) {
75 size_t gap = gaps[g];
76 size_t i;
77 for (i = gap; i < n; ++i) {
78 size_t j = i;
79 void* tmp = items[i];
80 for (; j >= gap && tmp < items[j - gap]; j -= gap) {
81 items[j] = items[j - gap];
82 }
83 items[j] = tmp;
84 }
85 }
86 }
87
88 static size_t Annihilate(void** a, size_t a_len, void** b, size_t b_len) {
89 size_t a_read_index = 0;
90 size_t b_read_index = 0;
91 size_t a_write_index = 0;
92 size_t b_write_index = 0;
93 size_t annihilated = 0;
94 while (a_read_index < a_len && b_read_index < b_len) {
95 if (a[a_read_index] == b[b_read_index]) {
96 a_read_index++;
97 b_read_index++;
98 annihilated++;
99 } else if (a[a_read_index] < b[b_read_index]) {
100 a[a_write_index++] = a[a_read_index++];
101 } else {
102 b[b_write_index++] = b[b_read_index++];
103 }
104 }
105 while (a_read_index < a_len) a[a_write_index++] = a[a_read_index++];
106 while (b_read_index < b_len) b[b_write_index++] = b[b_read_index++];
107 return annihilated;
108 }
109
110 static void CollectGarbagePointers(MemoryManager* m) {
111 size_t annihilated;
112 SortPointers(m->pointers + NEW_ALLOCATED_OFFSET, m->new_allocated);
113 SortPointers(m->pointers + NEW_FREED_OFFSET, m->new_freed);
114 annihilated = Annihilate(
115 m->pointers + NEW_ALLOCATED_OFFSET, m->new_allocated,
116 m->pointers + NEW_FREED_OFFSET, m->new_freed);
117 m->new_allocated -= annihilated;
118 m->new_freed -= annihilated;
119
120 if (m->new_freed != 0) {
121 annihilated = Annihilate(
122 m->pointers + PERM_ALLOCATED_OFFSET, m->perm_allocated,
123 m->pointers + NEW_FREED_OFFSET, m->new_freed);
124 m->perm_allocated -= annihilated;
125 m->new_freed -= annihilated;
126 BROTLI_DCHECK(m->new_freed == 0);
127 }
128
129 if (m->new_allocated != 0) {
130 BROTLI_DCHECK(m->perm_allocated + m->new_allocated <= MAX_PERM_ALLOCATED);
131 memcpy(m->pointers + PERM_ALLOCATED_OFFSET + m->perm_allocated,
132 m->pointers + NEW_ALLOCATED_OFFSET,
133 sizeof(void*) * m->new_allocated);
134 m->perm_allocated += m->new_allocated;
135 m->new_allocated = 0;
136 SortPointers(m->pointers + PERM_ALLOCATED_OFFSET, m->perm_allocated);
137 }
138 }
139
140 void* BrotliAllocate(MemoryManager* m, size_t n) {
141 void* result = m->alloc_func(m->opaque, n);
142 if (!result) {
143 m->is_oom = BROTLI_TRUE;
144 return NULL;
145 }
146 if (m->new_allocated == MAX_NEW_ALLOCATED) CollectGarbagePointers(m);
147 m->pointers[NEW_ALLOCATED_OFFSET + (m->new_allocated++)] = result;
148 return result;
149 }
150
151 void BrotliFree(MemoryManager* m, void* p) {
152 if (!p) return;
153 m->free_func(m->opaque, p);
154 if (m->new_freed == MAX_NEW_FREED) CollectGarbagePointers(m);
155 m->pointers[NEW_FREED_OFFSET + (m->new_freed++)] = p;
156 }
157
158 void BrotliWipeOutMemoryManager(MemoryManager* m) {
159 size_t i;
160 CollectGarbagePointers(m);
161 /* Now all unfreed pointers are in perm-allocated list. */
162 for (i = 0; i < m->perm_allocated; ++i) {
163 m->free_func(m->opaque, m->pointers[PERM_ALLOCATED_OFFSET + i]);
164 }
165 m->perm_allocated = 0;
166 }
167
168 #endif /* BROTLI_ENCODER_EXIT_ON_OOM */
169
170 void* BrotliBootstrapAlloc(size_t size,
171 brotli_alloc_func alloc_func, brotli_free_func free_func, void* opaque) {
172 if (!alloc_func && !free_func) {
173 return malloc(size);
174 } else if (alloc_func && free_func) {
175 return alloc_func(opaque, size);
176 }
177 return NULL;
178 }
179
180 void BrotliBootstrapFree(void* address, MemoryManager* m) {
181 if (!address) {
182 /* Should not happen! */
183 return;
184 } else {
185 /* Copy values, as those would be freed. */
186 brotli_free_func free_func = m->free_func;
187 void* opaque = m->opaque;
188 free_func(opaque, address);
189 }
190 }
191
192 #if defined(__cplusplus) || defined(c_plusplus)
193 } /* extern "C" */
194 #endif