1 /*
2 * Copyright (c) 2010 The WebM project authors. All Rights Reserved.
3 *
4 * Use of this source code is governed by a BSD-style license
5 * that can be found in the LICENSE file in the root of the source
6 * tree. An additional intellectual property rights grant can be found
7 * in the file PATENTS. All contributing project authors may
8 * be found in the AUTHORS file in the root of the source tree.
9 */
10
11
12 /* This code is in the public domain.
13 ** Version: 1.1 Author: Walt Karas
14 */
15
16 #include "hmm_intrnl.h"
17
U(init)18 void U(init)(U(descriptor) *desc) {
19 desc->avl_tree_root = 0;
20 desc->last_freed = 0;
21 }
22
23 /* Remove a free block from a bin's doubly-linked list when it is not,
24 ** the first block in the bin.
25 */
U(dll_remove)26 void U(dll_remove)(
27 /* Pointer to pointer record in the block to be removed. */
28 ptr_record *to_remove) {
29 to_remove->prev->next = to_remove->next;
30
31 if (to_remove->next)
32 to_remove->next->prev = to_remove->prev;
33 }
34
35 /* Put a block into the free collection of a heap.
36 */
U(into_free_collection)37 void U(into_free_collection)(
38 /* Pointer to heap descriptor. */
39 U(descriptor) *desc,
40 /* Pointer to head record of block. */
41 head_record *head_ptr) {
42 ptr_record *ptr_rec_ptr = HEAD_TO_PTR_REC(head_ptr);
43
44 ptr_record *bin_front_ptr =
45 U(avl_insert)((U(avl_avl) *) & (desc->avl_tree_root), ptr_rec_ptr);
46
47 if (bin_front_ptr != ptr_rec_ptr) {
48 /* The block was not inserted into the AVL tree because there is
49 ** already a bin for the size of the block. */
50
51 MARK_SUCCESSIVE_BLOCK_IN_FREE_BIN(head_ptr)
52 ptr_rec_ptr->self = ptr_rec_ptr;
53
54 /* Make the block the new second block in the bin's doubly-linked
55 ** list. */
56 ptr_rec_ptr->prev = bin_front_ptr;
57 ptr_rec_ptr->next = bin_front_ptr->next;
58 bin_front_ptr->next = ptr_rec_ptr;
59
60 if (ptr_rec_ptr->next)
61 ptr_rec_ptr->next->prev = ptr_rec_ptr;
62 } else
63 /* Block is first block in new bin. */
64 ptr_rec_ptr->next = 0;
65 }
66
67 /* Allocate a block from a given bin. Returns a pointer to the payload
68 ** of the removed block. The "last freed" pointer must be null prior
69 ** to calling this function.
70 */
U(alloc_from_bin)71 void *U(alloc_from_bin)(
72 /* Pointer to heap descriptor. */
73 U(descriptor) *desc,
74 /* Pointer to pointer record of first block in bin. */
75 ptr_record *bin_front_ptr,
76 /* Number of BAUs needed in the allocated block. If the block taken
77 ** from the bin is significantly larger than the number of BAUs needed,
78 ** the "extra" BAUs are split off to form a new free block. */
79 U(size_bau) n_baus) {
80 head_record *head_ptr;
81 U(size_bau) rem_baus;
82
83 if (bin_front_ptr->next) {
84 /* There are multiple blocks in this bin. Use the 2nd block in
85 ** the bin to avoid needless change to the AVL tree.
86 */
87
88 ptr_record *ptr_rec_ptr = bin_front_ptr->next;
89 head_ptr = PTR_REC_TO_HEAD(ptr_rec_ptr);
90
91 #ifdef AUDIT_FAIL
92 AUDIT_BLOCK(head_ptr)
93 #endif
94
95 U(dll_remove)(ptr_rec_ptr);
96 } else {
97 /* There is only one block in the bin, so it has to be removed
98 ** from the AVL tree.
99 */
100
101 head_ptr = PTR_REC_TO_HEAD(bin_front_ptr);
102
103 U(avl_remove)(
104 (U(avl_avl) *) & (desc->avl_tree_root), BLOCK_BAUS(head_ptr));
105 }
106
107 MARK_BLOCK_ALLOCATED(head_ptr)
108
109 rem_baus = BLOCK_BAUS(head_ptr) - n_baus;
110
111 if (rem_baus >= MIN_BLOCK_BAUS) {
112 /* Since there are enough "extra" BAUs, split them off to form
113 ** a new free block.
114 */
115
116 head_record *rem_head_ptr =
117 (head_record *) BAUS_FORWARD(head_ptr, n_baus);
118
119 /* Change the next block's header to reflect the fact that the
120 ** block preceeding it is now smaller.
121 */
122 SET_PREV_BLOCK_BAUS(
123 BAUS_FORWARD(head_ptr, head_ptr->block_size), rem_baus)
124
125 head_ptr->block_size = n_baus;
126
127 rem_head_ptr->previous_block_size = n_baus;
128 rem_head_ptr->block_size = rem_baus;
129
130 desc->last_freed = rem_head_ptr;
131 }
132
133 return(HEAD_TO_PTR_REC(head_ptr));
134 }
135
136 /* Take a block out of the free collection.
137 */
U(out_of_free_collection)138 void U(out_of_free_collection)(
139 /* Descriptor of heap that block is in. */
140 U(descriptor) *desc,
141 /* Pointer to head of block to take out of free collection. */
142 head_record *head_ptr) {
143 ptr_record *ptr_rec_ptr = HEAD_TO_PTR_REC(head_ptr);
144
145 if (ptr_rec_ptr->self == ptr_rec_ptr)
146 /* Block is not the front block in its bin, so all we have to
147 ** do is take it out of the bin's doubly-linked list. */
148 U(dll_remove)(ptr_rec_ptr);
149 else {
150 ptr_record *next = ptr_rec_ptr->next;
151
152 if (next)
153 /* Block is the front block in its bin, and there is at least
154 ** one other block in the bin. Substitute the next block for
155 ** the front block. */
156 U(avl_subst)((U(avl_avl) *) & (desc->avl_tree_root), next);
157 else
158 /* Block is the front block in its bin, but there is no other
159 ** block in the bin. Eliminate the bin. */
160 U(avl_remove)(
161 (U(avl_avl) *) & (desc->avl_tree_root), BLOCK_BAUS(head_ptr));
162 }
163 }
164
U(free)165 void U(free)(U(descriptor) *desc, void *payload_ptr) {
166 /* Flags if coalesce with adjacent block. */
167 int coalesce;
168
169 head_record *fwd_head_ptr;
170 head_record *free_head_ptr = PTR_REC_TO_HEAD(payload_ptr);
171
172 desc->num_baus_can_shrink = 0;
173
174 #ifdef HMM_AUDIT_FAIL
175
176 AUDIT_BLOCK(free_head_ptr)
177
178 /* Make sure not freeing an already free block. */
179 if (!IS_BLOCK_ALLOCATED(free_head_ptr))
180 HMM_AUDIT_FAIL
181
182 if (desc->avl_tree_root)
183 /* Audit root block in AVL tree. */
184 AUDIT_BLOCK(PTR_REC_TO_HEAD(desc->avl_tree_root))
185
186 #endif
187
188 fwd_head_ptr =
189 (head_record *) BAUS_FORWARD(free_head_ptr, free_head_ptr->block_size);
190
191 if (free_head_ptr->previous_block_size) {
192 /* Coalesce with backward block if possible. */
193
194 head_record *bkwd_head_ptr =
195 (head_record *) BAUS_BACKWARD(
196 free_head_ptr, free_head_ptr->previous_block_size);
197
198 #ifdef HMM_AUDIT_FAIL
199 AUDIT_BLOCK(bkwd_head_ptr)
200 #endif
201
202 if (bkwd_head_ptr == (head_record *)(desc->last_freed)) {
203 desc->last_freed = 0;
204 coalesce = 1;
205 } else if (IS_BLOCK_ALLOCATED(bkwd_head_ptr))
206 coalesce = 0;
207 else {
208 U(out_of_free_collection)(desc, bkwd_head_ptr);
209 coalesce = 1;
210 }
211
212 if (coalesce) {
213 bkwd_head_ptr->block_size += free_head_ptr->block_size;
214 SET_PREV_BLOCK_BAUS(fwd_head_ptr, BLOCK_BAUS(bkwd_head_ptr))
215 free_head_ptr = bkwd_head_ptr;
216 }
217 }
218
219 if (fwd_head_ptr->block_size == 0) {
220 /* Block to be freed is last block before dummy end-of-chunk block. */
221 desc->end_of_shrinkable_chunk =
222 BAUS_FORWARD(fwd_head_ptr, DUMMY_END_BLOCK_BAUS);
223 desc->num_baus_can_shrink = BLOCK_BAUS(free_head_ptr);
224
225 if (PREV_BLOCK_BAUS(free_head_ptr) == 0)
226 /* Free block is the entire chunk, so shrinking can eliminate
227 ** entire chunk including dummy end block. */
228 desc->num_baus_can_shrink += DUMMY_END_BLOCK_BAUS;
229 } else {
230 /* Coalesce with forward block if possible. */
231
232 #ifdef HMM_AUDIT_FAIL
233 AUDIT_BLOCK(fwd_head_ptr)
234 #endif
235
236 if (fwd_head_ptr == (head_record *)(desc->last_freed)) {
237 desc->last_freed = 0;
238 coalesce = 1;
239 } else if (IS_BLOCK_ALLOCATED(fwd_head_ptr))
240 coalesce = 0;
241 else {
242 U(out_of_free_collection)(desc, fwd_head_ptr);
243 coalesce = 1;
244 }
245
246 if (coalesce) {
247 free_head_ptr->block_size += fwd_head_ptr->block_size;
248
249 fwd_head_ptr =
250 (head_record *) BAUS_FORWARD(
251 fwd_head_ptr, BLOCK_BAUS(fwd_head_ptr));
252
253 SET_PREV_BLOCK_BAUS(fwd_head_ptr, BLOCK_BAUS(free_head_ptr))
254
255 if (fwd_head_ptr->block_size == 0) {
256 /* Coalesced block to be freed is last block before dummy
257 ** end-of-chunk block. */
258 desc->end_of_shrinkable_chunk =
259 BAUS_FORWARD(fwd_head_ptr, DUMMY_END_BLOCK_BAUS);
260 desc->num_baus_can_shrink = BLOCK_BAUS(free_head_ptr);
261
262 if (PREV_BLOCK_BAUS(free_head_ptr) == 0)
263 /* Free block is the entire chunk, so shrinking can
264 ** eliminate entire chunk including dummy end block. */
265 desc->num_baus_can_shrink += DUMMY_END_BLOCK_BAUS;
266 }
267 }
268 }
269
270 if (desc->last_freed) {
271 /* There is a last freed block, but it is not adjacent to the
272 ** block being freed by this call to free, so put the last
273 ** freed block into the free collection.
274 */
275
276 #ifdef HMM_AUDIT_FAIL
277 AUDIT_BLOCK(desc->last_freed)
278 #endif
279
280 U(into_free_collection)(desc, (head_record *)(desc->last_freed));
281 }
282
283 desc->last_freed = free_head_ptr;
284 }
285
U(new_chunk)286 void U(new_chunk)(U(descriptor) *desc, void *start, U(size_bau) n_baus) {
287 #ifdef HMM_AUDIT_FAIL
288
289 if (desc->avl_tree_root)
290 /* Audit root block in AVL tree. */
291 AUDIT_BLOCK(PTR_REC_TO_HEAD(desc->avl_tree_root))
292 #endif
293
294 #undef HEAD_PTR
295 #define HEAD_PTR ((head_record *) start)
296
297 /* Make the chunk one big free block followed by a dummy end block.
298 */
299
300 n_baus -= DUMMY_END_BLOCK_BAUS;
301
302 HEAD_PTR->previous_block_size = 0;
303 HEAD_PTR->block_size = n_baus;
304
305 U(into_free_collection)(desc, HEAD_PTR);
306
307 /* Set up the dummy end block. */
308 start = BAUS_FORWARD(start, n_baus);
309 HEAD_PTR->previous_block_size = n_baus;
310 HEAD_PTR->block_size = 0;
311
312 #undef HEAD_PTR
313 }
314
315 #ifdef HMM_AUDIT_FAIL
316
317 /* Function that does audit fail actions defined my preprocessor symbol,
318 ** and returns a dummy integer value.
319 */
U(audit_block_fail_dummy_return)320 int U(audit_block_fail_dummy_return)(void) {
321 HMM_AUDIT_FAIL
322
323 /* Dummy return. */
324 return(0);
325 }
326
327 #endif
328
329 /* AVL Tree instantiation. */
330
331 #ifdef HMM_AUDIT_FAIL
332
333 /* The AVL tree generic package passes an ACCESS of 1 when it "touches"
334 ** a child node for the first time during a particular operation. I use
335 ** this feature to audit only one time (per operation) the free blocks
336 ** that are tree nodes. Since the root node is not a child node, it has
337 ** to be audited directly.
338 */
339
340 /* The pain you feel while reading these macros will not be in vain. It
341 ** will remove all doubt from you mind that C++ inline functions are
342 ** a very good thing.
343 */
344
345 #define AVL_GET_LESS(H, ACCESS) \
346 (((ACCESS) ? AUDIT_BLOCK_AS_EXPR(PTR_REC_TO_HEAD(H)) : 0), (H)->self)
347 #define AVL_GET_GREATER(H, ACCESS) \
348 (((ACCESS) ? AUDIT_BLOCK_AS_EXPR(PTR_REC_TO_HEAD(H)) : 0), (H)->prev)
349
350 #else
351
352 #define AVL_GET_LESS(H, ACCESS) ((H)->self)
353 #define AVL_GET_GREATER(H, ACCESS) ((H)->prev)
354
355 #endif
356
357 #define AVL_SET_LESS(H, LH) (H)->self = (LH);
358 #define AVL_SET_GREATER(H, GH) (H)->prev = (GH);
359
360 /* high bit of high bit of
361 ** block_size previous_block_size balance factor
362 ** ----------- ------------------- --------------
363 ** 0 0 n/a (block allocated)
364 ** 0 1 1
365 ** 1 0 -1
366 ** 1 1 0
367 */
368
369 #define AVL_GET_BALANCE_FACTOR(H) \
370 ((((head_record *) (PTR_REC_TO_HEAD(H)))->block_size & \
371 HIGH_BIT_BAU_SIZE) ? \
372 (((head_record *) (PTR_REC_TO_HEAD(H)))->previous_block_size & \
373 HIGH_BIT_BAU_SIZE ? 0 : -1) : 1)
374
375 #define AVL_SET_BALANCE_FACTOR(H, BF) \
376 { \
377 register head_record *p = \
378 (head_record *) PTR_REC_TO_HEAD(H); \
379 register int bal_f = (BF); \
380 \
381 if (bal_f <= 0) \
382 p->block_size |= HIGH_BIT_BAU_SIZE; \
383 else \
384 p->block_size &= ~HIGH_BIT_BAU_SIZE; \
385 if (bal_f >= 0) \
386 p->previous_block_size |= HIGH_BIT_BAU_SIZE; \
387 else \
388 p->previous_block_size &= ~HIGH_BIT_BAU_SIZE; \
389 }
390
391 #define COMPARE_KEY_KEY(K1, K2) ((K1) == (K2) ? 0 : ((K1) > (K2) ? 1 : -1))
392
393 #define AVL_COMPARE_KEY_NODE(K, H) \
394 COMPARE_KEY_KEY(K, BLOCK_BAUS(PTR_REC_TO_HEAD(H)))
395
396 #define AVL_COMPARE_NODE_NODE(H1, H2) \
397 COMPARE_KEY_KEY(BLOCK_BAUS(PTR_REC_TO_HEAD(H1)), \
398 BLOCK_BAUS(PTR_REC_TO_HEAD(H2)))
399
400 #define AVL_NULL ((ptr_record *) 0)
401
402 #define AVL_IMPL_MASK \
403 ( AVL_IMPL_INSERT | AVL_IMPL_SEARCH | AVL_IMPL_REMOVE | AVL_IMPL_SUBST )
404
405 #include "cavl_impl.h"
406