Changeset 283


Ignore:
Timestamp:
Dec 11, 2002, 2:46:19 PM (18 years ago)
Author:
pooh
Message:
  • Code cleanup. Block header implementation is separated.
Location:
to-imperative/trunk/libp++
Files:
3 added
3 edited

Legend:

Unmodified
Added
Removed

  • to-imperative/trunk/libp++/Makefile

    r276 r283  
    1313  pxx_heap_allocator \
    1414  pxx_default_allocator \
     15  pxx_chunk_allocator_block_header \
    1516  pxx_chunk_allocator
    1617

  • to-imperative/trunk/libp++/pxx_chunk_allocator.hh

    r282 r283  
    2626#include "pxx_allocator.hh"
    2727#include "pxx_default_allocator.hh"
     28#include "pxx_chunk_allocator_block_header.hh"
    2829
    2930namespace pxx
    … …  
    3132
    3233extern size_t chunks_in_block ;
    33 
    34 //
    35 // Memory block header structure
    36 struct BlockHeader
    37 {
    38   //
    39   // Reference counter that is equal to a number of allocated chunks in a
    40   // block
    41   uintptr_t ref_count ;
    42   //
    43   // Pointer to the previous free block
    44   BlockHeader* prev ;
    45   //
    46   // Pointer to the next free block
    47   BlockHeader* next ;
    48   //
    49   //
    50   BlockHeader* left ;
    51   //
    52   //
    53   BlockHeader* right ;
    54   //
    55   //
    56   int balance ;
    57   //
    58   // Constructor
    59   BlockHeader (BlockHeader* _prev, BlockHeader* _next) ;
    60 
    61   NO_COPY_CTOR(BlockHeader)
    62   NO_ASSIGN(BlockHeader)
    63   //
    64   // Remove a memory block from block list
    65   inline void remove () ;
    66 
    67 };
    6834
    6935template <typename type_t>
    … …  
    8753
    8854  };
    89 
    90 
     55  //
     56  // A reference to underlying memory allocator
    9157  Allocator& allocator ;
    92 
    93   BlockHeader block_list ;
    94 
     58  //
     59  // List of memory blocks
     60  CABlockHeader block_list ;
     61  //
     62  // List of ofree chunks
    9563  FreeList free_list ;
    96 
     64  //
     65  // Chunk size
    9766  size_t chunk_size ;
    9867
    … …  
    10170  size_t nchunks ;
    10271
    103   BlockHeader* root ;
     72  CABlockHeader* root ;
    10473
    10574public:
    … …  
    12493private:
    12594
    126   inline BlockHeader* get_block (void* _ptr) ;
    127   inline void init_block (BlockHeader* _ptr) ;
     95  inline CABlockHeader* get_block (void* _ptr) ;
     96  void init_block (CABlockHeader* _ptr) ;
     97  void free_block (CABlockHeader* _ptr) ;
    12898
    12999};

  • to-imperative/trunk/libp++/pxx_chunk_allocator.ih

    r282 r283  
    2525
    2626#include "pxx_chunk_allocator.hh"
     27#include "pxx_chunk_allocator_block_header.ih"
    2728#include "pxx_common.ih"
    2829
    2930namespace pxx
    3031{
    31 
    32 inline BlockHeader::BlockHeader (
    33   BlockHeader* _prev, BlockHeader* _next
    34 ) :
    35   ref_count (0),
    36   prev (_prev),
    37   next (_next),
    38   left (null),
    39   right (null)
    40 {}
    41 
    42 inline void BlockHeader::remove ()
    43 {
    44   prev->next = next;
    45   next->prev = prev;
    46 }
    4732
    4833template <typename type_t>
    … …  
    5944  allocator (_allocator),
    6045  block_list (&block_list, &block_list),
    61   chunk_size (size_align(sizeof(type_t), 2 * sizeof(void*))),
     46  chunk_size (size_align(sizeof(type_t), sizeof(FreeList))),
    6247  root (null)
    6348{
    6449  free_list.prev = free_list.next = &free_list;
    6550  block_size = _allocator.get_real_size(
    66     chunks_in_block * chunk_size + sizeof(BlockHeader)
     51    chunks_in_block * chunk_size + sizeof(CABlockHeader)
    6752  );
    68 printf("block_size: %u\n", block_size);
    69   nchunks = (block_size - sizeof(BlockHeader))/chunk_size;
     53  nchunks = (block_size - sizeof(CABlockHeader))/chunk_size;
    7054}
    7155
    … …  
    7761  allocator (_allocator),
    7862  block_list (&block_list, &block_list),
    79   chunk_size (size_align(sizeof(type_t), 2 * sizeof(void*))),
     63  chunk_size (size_align(sizeof(type_t), sizeof(FreeList))),
    8064  root (null)
    8165{
    8266  free_list.prev = free_list.next = &free_list;
    8367  block_size =
    84     _allocator.get_real_size(_nchunks * chunk_size + sizeof(BlockHeader));
    85 printf("block_size: %u\n", block_size);
    86 printf("features: %08x\n", allocator.get_features());
    87   nchunks = (block_size - sizeof(BlockHeader))/chunk_size;
     68    _allocator.get_real_size(_nchunks * chunk_size + sizeof(CABlockHeader));
     69  nchunks = (block_size - sizeof(CABlockHeader))/chunk_size;
    8870}
    8971
    … …  
    9173inline ChunkAllocator<type_t>::~ChunkAllocator ()
    9274{
    93   BlockHeader* p = block_list.next;
     75  CABlockHeader* p = block_list.next;
    9476  while (p != &block_list) {
    9577    void* q = p;
    … …  
    10587  if (p != &free_list) {
    10688    p->remove();
    107     BlockHeader* b = get_block(p);
    108     if (b != null) b->ref_count++;
     89    CABlockHeader* b = get_block(p);
     90    (b->ref_count)++;
    10991    return (type_t*)p;
    11092  } else {
    111     BlockHeader* p = (BlockHeader*)allocator.allocate(block_size);
     93    CABlockHeader* p = (CABlockHeader*)allocator.allocate(block_size);
    11294//printf("Allocated block at %p\n", p);
    11395    init_block(p);
    11496    return ChunkAllocator::allocate();
    11597  }
    116 }
    117 
    118 static BlockHeader* node_balance (
    119   BlockHeader* _node
    120 );
    121 
    122 static BlockHeader* node_restore_left_balance (
    123   BlockHeader* _node,
    124   int _old_balance
    125 )
    126 {
    127   if (_node->left == null)
    128     _node->balance += 1;
    129   else
    130     if ((_node->left->balance != _old_balance) && (_node->left->balance == 0))
    131       _node->balance += 1;
    132   if (_node->balance > 1) return node_balance(_node);
    133   return _node;
    134 }
    135 
    136 static BlockHeader* node_restore_right_balance (
    137   BlockHeader* _node,
    138   int _old_balance
    139 )
    140 {
    141   if (_node->right == null)
    142     _node->balance -= 1;
    143   else
    144     if ((_node->right->balance != _old_balance) && (_node->right->balance == 0))
    145       _node->balance -= 1;
    146   if (_node->balance < -1) return node_balance(_node);
    147   return _node;
    148 }
    149 
    150 static BlockHeader* node_remove_leftmost (
    151   BlockHeader* _node,
    152   BlockHeader** _leftmost
    153 )
    154 {
    155   int old_balance;
    156   if (_node->left == null) {
    157     *_leftmost = _node;
    158     return _node->right;
    159   }
    160   old_balance = _node->left->balance;
    161   _node->left = node_remove_leftmost(_node->left, _leftmost);
    162   return node_restore_left_balance(_node, old_balance);
    163 }
    164 
    165 static BlockHeader* node_remove (
    166   BlockHeader* _node,
    167   BlockHeader* _key
    168 )
    169 {
    170   int old_balance;
    171   BlockHeader* new_root;
    172   if (_key == _node) {
    173     if (_node->right == null) {
    174       _node = _node->left;
    175     } else {
    176       old_balance = _node->right->balance;
    177       _node->right = node_remove_leftmost(_node->right, &new_root);
    178       new_root->left = _node->left;
    179       new_root->right = _node->right;
    180       new_root->balance = _node->balance;
    181       _node = node_restore_right_balance(new_root, old_balance);
    182     }
    183   } else if (_key < _node) {
    184     if (_node->left != null) {
    185       old_balance = _node->left->balance;
    186       _node->left = node_remove(_node->left, _key);
    187       _node = node_restore_left_balance(_node, old_balance);
    188     }
    189   } else {
    190     if (_node->right != null) {
    191       old_balance = _node->right->balance;
    192       _node->right = node_remove(_node->right, _key);
    193       _node = node_restore_right_balance(_node, old_balance);
    194     }
    195   }
    196   return _node;
    19798}
    19899
    … …  
    204105  p->next = &free_list;
    205106  free_list.prev = free_list.prev->next = p ;
    206   BlockHeader* b = get_block(_ptr);
    207   if ((b != null) && (--(b->ref_count) == 0)) {
    208     FreeList* p = (FreeList*)ptr_add_offset(b, sizeof(BlockHeader));
    209     FreeList* q = (FreeList*)ptr_add_offset(p, nchunks  * chunk_size);
    210     while (p < q) {
    211       p->remove();
    212       p = (FreeList*)ptr_add_offset(p, chunk_size);
    213     }
    214 //printf("Deallocating block at %p\n", b);
    215     b->remove();
    216     if ((allocator.get_features() & ALLOCATOR_HAS_GET_BLOCK_WITH_SIZE) == 0) {
    217       root = node_remove(root, b);
    218     }
    219     allocator.deallocate(b);
    220   }
     107  CABlockHeader* b = get_block(_ptr);
     108  if (--(b->ref_count) != 0) return;
     109  else return free_block(b);
    221110}
    222111
    223112template <typename type_t>
    224 inline BlockHeader* ChunkAllocator<type_t>::get_block (void* _ptr)
     113inline void ChunkAllocator<type_t>::free_block (CABlockHeader* _ptr)
     114{
     115  FreeList* p = (FreeList*)ptr_add_offset(_ptr, sizeof(CABlockHeader));
     116  FreeList* q = (FreeList*)ptr_add_offset(p, nchunks  * chunk_size);
     117  while (p < q) {
     118    p->remove();
     119    p = (FreeList*)ptr_add_offset(p, chunk_size);
     120  }
     121//printf("Deallocating block at %p\n", b);
     122  _ptr->remove();
     123  if ((allocator.get_features() & ALLOCATOR_HAS_GET_BLOCK_WITH_SIZE) == 0) {
     124    root = root->node_remove(_ptr);
     125  }
     126  allocator.deallocate(_ptr);
     127}
     128
     129template <typename type_t>
     130inline CABlockHeader* ChunkAllocator<type_t>::get_block (void* _ptr)
    225131{
    226132  if ((allocator.get_features() & ALLOCATOR_HAS_GET_BLOCK_WITH_SIZE) != 0) {
    227     return (BlockHeader*)(allocator.get_block(_ptr, block_size));
     133    return (CABlockHeader*)(allocator.get_block(_ptr, block_size));
    228134  } else {
    229     BlockHeader* node = root;
     135    CABlockHeader* node = root;
    230136    do {
    231137      if (_ptr < node) {
    … …  
    238144    return null;
    239145  }
    240 #if 0
    241   else {
    242     BlockHeader* p = block_list.next;
    243     while (p != &block_list) {
    244       if ((_ptr >= p) && (_ptr < ptr_add_offset(p, block_size))) return p;
    245     }
    246     return null;
    247   }
    248 #endif
    249 }
    250 
    251 static BlockHeader* node_rotate_left (
    252   BlockHeader* _node
    253 )
    254 {
    255   BlockHeader* right;
    256   int a_bal, b_bal;
    257 
    258   right = _node->right;
    259 
    260   _node->right = right->left;
    261   right->left = _node;
    262 
    263   a_bal = _node->balance;
    264   b_bal = right->balance;
    265 
    266   if (b_bal <= 0) {
    267     if (a_bal >= 1) right->balance = b_bal - 1;
    268     else right->balance = a_bal + b_bal - 2;
    269     _node->balance = a_bal - 1;
    270   } else {
    271     if (a_bal <= b_bal) right->balance = a_bal - 2;
    272     else right->balance = b_bal - 1;
    273     _node->balance = a_bal - b_bal - 1;
    274   }
    275 
    276   return right;
    277 }
    278 
    279 static BlockHeader* node_rotate_right (
    280   BlockHeader* _node
    281 )
    282 {
    283   BlockHeader* left;
    284   int a_bal, b_bal;
    285 
    286   left = _node->left;
    287 
    288   _node->left = left->right;
    289   left->right = _node;
    290 
    291   a_bal = _node->balance;
    292   b_bal = left->balance;
    293 
    294   if (b_bal <= 0) {
    295     if (b_bal > a_bal) left->balance = b_bal + 1;
    296     else left->balance = a_bal + 2;
    297     _node->balance = a_bal - b_bal + 1;
    298   } else {
    299     if (a_bal <= -1) left->balance = b_bal + 1;
    300     else left->balance = a_bal + b_bal + 2;
    301     _node->balance = a_bal + 1;
    302   }
    303 
    304   return left;
    305 }
    306 
    307 static BlockHeader* node_balance (
    308   BlockHeader* _node
    309 )
    310 {
    311   if (_node->balance < -1) {
    312     if (_node->left->balance > 0)
    313       _node->left = node_rotate_left(_node->left);
    314     _node = node_rotate_right(_node);
    315   } else {
    316     if (_node->right->balance < 0)
    317       _node->right = node_rotate_right(_node->right);
    318     _node = node_rotate_left(_node);
    319   }
    320   return _node;
    321 }
    322 
    323 static BlockHeader* node_insert (
    324   BlockHeader* _node,
    325   BlockHeader* _key
    326 )
    327 {
    328   int old_balance;
    329   if (_key < _node) {
    330     if (_node->left != null) {
    331       old_balance = _node->left->balance;
    332       _node->left = node_insert(_node->left, _key);
    333       if ((old_balance != _node->left->balance) && (_node->left->balance != 0))
    334         _node->balance -= 1;
    335     } else {
    336       _node->left = _key;
    337       _node->balance -= 1;
    338     }
    339   } else {
    340     if (_node->right != null) {
    341       old_balance = _node->right->balance;
    342       _node->right = node_insert(_node->right, _key);
    343       if ((old_balance != _node->right->balance) && (_node->right->balance != 0))
    344         _node->balance += 1;
    345     } else {
    346       _node->right = _key;
    347       _node->balance += 1;
    348     }
    349   }
    350   if ((_node->balance < -1) || (_node->balance > 1))
    351     _node = node_balance(_node);
    352   return _node;
    353146}
    354147
    355148template <typename type_t>
    356 inline void ChunkAllocator<type_t>::init_block (BlockHeader* _ptr)
     149void ChunkAllocator<type_t>::init_block (CABlockHeader* _ptr)
    357150{
    358151  _ptr->prev = block_list.prev;
    … …  
    361154  _ptr->ref_count = 0;
    362155
    363   FreeList* p = (FreeList*)ptr_add_offset(_ptr, sizeof(BlockHeader));
     156  FreeList* p = (FreeList*)ptr_add_offset(_ptr, sizeof(CABlockHeader));
    364157  FreeList* q = (FreeList*)ptr_add_offset(p, (nchunks - 1) * chunk_size);
    365158  p->prev = &free_list;
    … …  
    377170    _ptr->balance = 0;
    378171    if (root == null) root = _ptr;
    379     else root = node_insert(root, _ptr);
     172    else root = root->node_insert(_ptr);
    380173  }
    381174}
Note: See TracChangeset for help on using the changeset viewer.