vpx_mem/memory_manager/include/hmm_intrnl.h

   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 #ifndef HMM_INTRNL_H_
  17 #define HMM_INTRNL_H_
  18
  19 #ifdef __uClinux__
  20 # include <lddk.h>
  21 #endif
  22
  23 #include "heapmm.h"
  24
  25 #define U(BASE) HMM_UNIQUE(BASE)
  26
  27 /* Mask of high bit of variable of size_bau type. */
  28 #define HIGH_BIT_BAU_SIZE \
  29     ((U(size_bau)) ~ (((U(size_bau)) ~ (U(size_bau)) 0) >> 1))
  30
  31 /* Add a given number of AAUs to pointer. */
  32 #define AAUS_FORWARD(PTR, AAU_OFFSET) \
  33     (((char *) (PTR)) + ((AAU_OFFSET) * ((U(size_aau)) HMM_ADDR_ALIGN_UNIT)))
  34
  35 /* Subtract a given number of AAUs from pointer. */
  36 #define AAUS_BACKWARD(PTR, AAU_OFFSET) \
  37     (((char *) (PTR)) - ((AAU_OFFSET) * ((U(size_aau)) HMM_ADDR_ALIGN_UNIT)))
  38
  39 /* Add a given number of BAUs to a pointer. */
  40 #define BAUS_FORWARD(PTR, BAU_OFFSET) \
  41     AAUS_FORWARD((PTR), (BAU_OFFSET) * ((U(size_aau)) HMM_BLOCK_ALIGN_UNIT))
  42
  43 /* Subtract a given number of BAUs to a pointer. */
  44 #define BAUS_BACKWARD(PTR, BAU_OFFSET) \
  45     AAUS_BACKWARD((PTR), (BAU_OFFSET) * ((U(size_aau)) HMM_BLOCK_ALIGN_UNIT))
  46
  47 typedef struct head_struct
  48 {
  49     /* Sizes in Block Alignment Units. */
  50     HMM_UNIQUE(size_bau) previous_block_size, block_size;
  51 }
  52 head_record;
  53
  54 typedef struct ptr_struct
  55 {
  56     struct ptr_struct *self, *prev, *next;
  57 }
  58 ptr_record;
  59
  60 /* Divide and round up any fraction to the next whole number. */
  61 #define DIV_ROUND_UP(NUMER, DENOM) (((NUMER) + (DENOM) - 1) / (DENOM))
  62
  63 /* Number of AAUs in a block head. */
  64 #define HEAD_AAUS DIV_ROUND_UP(sizeof(head_record), HMM_ADDR_ALIGN_UNIT)
  65
  66 /* Number of AAUs in a block pointer record. */
  67 #define PTR_RECORD_AAUS DIV_ROUND_UP(sizeof(ptr_record), HMM_ADDR_ALIGN_UNIT)
  68
  69 /* Number of BAUs in a dummy end record (at end of chunk). */
  70 #define DUMMY_END_BLOCK_BAUS DIV_ROUND_UP(HEAD_AAUS, HMM_BLOCK_ALIGN_UNIT)
  71
  72 /* Minimum number of BAUs in a block (allowing room for the pointer record. */
  73 #define MIN_BLOCK_BAUS \
  74     DIV_ROUND_UP(HEAD_AAUS + PTR_RECORD_AAUS, HMM_BLOCK_ALIGN_UNIT)
  75
  76 /* Return number of BAUs in block (masking off high bit containing block
  77 ** status). */
  78 #define BLOCK_BAUS(HEAD_PTR) \
  79     (((head_record *) (HEAD_PTR))->block_size & ~HIGH_BIT_BAU_SIZE)
  80
  81 /* Return number of BAUs in previous block (masking off high bit containing
  82 ** block status). */
  83 #define PREV_BLOCK_BAUS(HEAD_PTR) \
  84     (((head_record *) (HEAD_PTR))->previous_block_size & ~HIGH_BIT_BAU_SIZE)
  85
  86 /* Set number of BAUs in previous block, preserving high bit containing
  87 ** block status. */
  88 #define SET_PREV_BLOCK_BAUS(HEAD_PTR, N_BAUS) \
  89     { register head_record *h_ptr = (head_record *) (HEAD_PTR); \
  90         h_ptr->previous_block_size &= HIGH_BIT_BAU_SIZE; \
  91         h_ptr->previous_block_size |= (N_BAUS); }
  92
  93 /* Convert pointer to pointer record of block to pointer to block's head
  94 ** record. */
  95 #define PTR_REC_TO_HEAD(PTR_REC_PTR) \
  96     ((head_record *) AAUS_BACKWARD(PTR_REC_PTR, HEAD_AAUS))
  97
  98 /* Convert pointer to block head to pointer to block's pointer record. */
  99 #define HEAD_TO_PTR_REC(HEAD_PTR) \
 100     ((ptr_record *) AAUS_FORWARD(HEAD_PTR, HEAD_AAUS))
 101
 102 /* Returns non-zero if block is allocated. */
 103 #define IS_BLOCK_ALLOCATED(HEAD_PTR) \
 104     (((((head_record *) (HEAD_PTR))->block_size | \
 105        ((head_record *) (HEAD_PTR))->previous_block_size) & \
 106       HIGH_BIT_BAU_SIZE) == 0)
 107
 108 #define MARK_BLOCK_ALLOCATED(HEAD_PTR) \
 109     { register head_record *h_ptr = (head_record *) (HEAD_PTR); \
 110         h_ptr->block_size &= ~HIGH_BIT_BAU_SIZE; \
 111         h_ptr->previous_block_size &= ~HIGH_BIT_BAU_SIZE; }
 112
 113 /* Mark a block as free when it is not the first block in a bin (and
 114 ** therefore not a node in the AVL tree). */
 115 #define MARK_SUCCESSIVE_BLOCK_IN_FREE_BIN(HEAD_PTR) \
 116     { register head_record *h_ptr = (head_record *) (HEAD_PTR); \
 117         h_ptr->block_size |= HIGH_BIT_BAU_SIZE; }
 118
 119 /* Prototypes for internal functions implemented in one file and called in
 120 ** another.
 121 */
 122
 123 void U(into_free_collection)(U(descriptor) *desc, head_record *head_ptr);
 124
 125 void U(out_of_free_collection)(U(descriptor) *desc, head_record *head_ptr);
 126
 127 void *U(alloc_from_bin)(
 128     U(descriptor) *desc, ptr_record *bin_front_ptr, U(size_bau) n_baus);
 129
 130 #ifdef HMM_AUDIT_FAIL
 131
 132 /* Simply contains a reference to the HMM_AUDIT_FAIL macro and a
 133 ** dummy return. */
 134 int U(audit_block_fail_dummy_return)(void);
 135
 136
 137 /* Auditing a block consists of checking that the size in its head
 138 ** matches the previous block size in the head of the next block. */
 139 #define AUDIT_BLOCK_AS_EXPR(HEAD_PTR) \
 140     ((BLOCK_BAUS(HEAD_PTR) == \
 141       PREV_BLOCK_BAUS(BAUS_FORWARD(HEAD_PTR, BLOCK_BAUS(HEAD_PTR)))) ? \
 142      0 : U(audit_block_fail_dummy_return)())
 143
 144 #define AUDIT_BLOCK(HEAD_PTR) \
 145     { void *h_ptr = (HEAD_PTR); AUDIT_BLOCK_AS_EXPR(h_ptr); }
 146
 147 #endif
 148
 149 /* Interface to AVL tree generic package instantiation. */
 150
 151 #define AVL_UNIQUE(BASE) U(avl_ ## BASE)
 152
 153 #define AVL_HANDLE ptr_record *
 154
 155 #define AVL_KEY U(size_bau)
 156
 157 #define AVL_MAX_DEPTH 64
 158
 159 #include "cavl_if.h"
 160
 161 #endif /* Include once. */