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