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 18void 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*/ 26void 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*/ 37void 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*/ 71void *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*/ 138void 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 165void 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 286void 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*/ 320int 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