Changeset 271


Ignore:
Timestamp:
Dec 9, 2002, 5:17:24 PM (18 years ago)
Author:
pooh
Message:
  • Massive code cleanups and bug fixes.
Location:
to-imperative/trunk/libp++
Files:
1 added
3 edited

Legend:

Unmodified
Added
Removed
  • to-imperative/trunk/libp++/Makefile

    r257 r271  
    33include $(TOPDIR)/rules.mk
    44
     5PXX_AMODULES = \
     6  pxx_allocator
     7
    58PXX_MODULES = \
     9  pxx_sys_error \
     10  pxx_malloc_allocator \
     11  pxx_heap \
     12  pxx_heap_allocator \
    613  pxx_common
    714
     15PXX_AHEADERS = $(PXX_AMODULES:=.hh)
    816PXX_SOURCES = $(PXX_MODULES:=.cc)
    917PXX_HEADERS = $(PXX_MODULES:=.hh)
     
    1523DEPS = $(ALL_SOURCES:.cc=.dep)
    1624
    17 LIBDXX = libp++.a
     25LIBPXX = libp++.a
    1826
    1927DISTFILES = Makefile
     
    2129DISTFILES += $(PXX_HEADERS)
    2230DISTFILES += $(PXX_IHEADERS)
     31DISTFILES += $(PXX_AHEADERS)
    2332
    2433all:: $(LIBPXX)
    2534
    26 $(LIBDOE): $(DOE_OBJECTS) $(PXX_OBJECTS)
     35$(LIBPXX): $(PXX_OBJECTS)
    2736        ar cru $@ $^
    2837
     
    3847
    3948clean::
    40         rm -f $(LIBDOE) *.o *.dep
     49        rm -f $(LIBPXX) *.o *.dep
    4150
    4251-include $(DEPS)
  • to-imperative/trunk/libp++/pxx_heap_allocator.cc

    r121 r271  
    11//
    2 // Copyright (C) 2000, 2001 Andrey Slepuhin <pooh@msu.ru>
     2// Copyright (C) 2000-2002 Andrey Slepuhin <pooh@msu.ru>
    33//
    44// libp++ is free software; you can redistribute it and/or modify
     
    2121// Author: Andrey Slepuhin <pooh@msu.ru>
    2222
    23 #include "pxx_heap_allocator.hh"
     23#include "pxx_heap_allocator.ih"
     24#include "pxx_common.ih"
    2425
    2526#include <new>
     
    3132{
    3233
     34size_t HeapAllocator::min_free_size =
     35  (1 << get_order(sizeof(HeapAllocator::BlockHeader)));
     36
    3337HeapAllocator::HeapAllocator (
    34   void* const _start,
    35   size_t const _heap_size,
    36   int _fd = 0,
    37   bool _need_remap = true
     38  size_t _init_size /* = 0 */,      // Initial heap size, page size by default
     39  size_t const _max_size /* = 0 */, // Maximum size, not limited by default
     40  void* const _start /* = null */,
     41  int _fd /* = -1 */
    3842) :
    39   Heap (_start, _heap_size, 0, _fd, _need_remap),
    40   min_free_size (1 << get_order(sizeof(BlockInfo)))
    41 {
    42   BlockInfo* p = reinterpret_cast<BlockInfo*>(start);
    43   (lists + get_order(page_size))->insert(p, page_size);
     43  Heap (_init_size, _max_size, _start, _fd)
     44{
     45  for (unsigned i = 0; i < sizeof(size_t) * 8; i++)
     46    lists[i].size = exps_of_two[i];
     47  BlockHeader* p = reinterpret_cast<BlockHeader*>(start_addr);
     48  (lists + get_order(current_size))->put(p);
    4449}
    4550
     
    5055{
    5156  //
    52   // first try to allocate a block within current heap
     57  // First try to allocate a block within current heap
     58  // Advance allocated size by number of bytes reserved for length
     59  _size += sizeof(uintptr_t);
     60  //
     61  // We cannot allocate less than minimal free size
     62  if (_size < min_free_size) _size = min_free_size ;
     63  //
     64  // Walk through apropriate block lists
     65  FreeBlockList* first = lists + get_order(_size);
     66  FreeBlockList* last = lists + cur_size_log;
     67  for (FreeBlockList* p = first; p <= last; p++) {
     68    //
     69    // Try to get free block from the list
     70    BlockHeader* q = p->get();
     71    //
     72    // Ok, we got one
     73    if (q != null) {
     74      while (p-- > first) {
     75        p->put(ptr_add_offset(q, p->size));
     76      }
     77      //
     78      // Set a size of allocated block
     79      q->set_size(first->size);
     80      //
     81      // And return shifted pointer
     82      return user_ptr(q);
     83    }
     84  }
     85  //
     86  // Here we did not find any non-empty free block list, or we want to
     87  // allocate too large amount of memory, so we should expand a heap
    5388  {
    54     size_t order, i;
    55     //
    56     // advance allocated size by number of bytes reserved for length
    57     _size += sizeof(uintptr_t);
    58     //
    59     // we cannot allocate less than minimal free size
    60     if (_size < min_free_size) _size = min_free_size ;
    61     //
    62     // choose first appropriate block list
    63     order = get_order(_size);
    64     _size = rounds[order];
    65     i = order;
    66     //
    67     // walk through apropriate block lists
    68     while (i <= current_order) {
    69       FreeBlockList* p = lists + i;
    70       BlockInfo* q = p->next;
    71       //
    72       // ok, we found non-empty free block list
    73       if (q != p) {
    74         //
    75         // remove its first element
    76         q->remove();
    77         unsigned s = rounds[i];
    78         while (s > _size) {
    79           s >>= 1;
    80           (--p)->insert(ptr_add(q, s), s);
    81         }
    82         //
    83         // set a size of allocated block
    84         q->set_size(_size);
    85         //
    86         // and return shifted pointer
    87         return user_ptr(q);
    88       }
    89       i++;
    90     }
    91   }
    92   //
    93   // if current heap exhausted try to expand it
    94   {
    95     //
    96     // here we did not find any non-empty free block list,
    97     // so we should expand a heap
    98     size_t old_size = current_size;
    99     size_t old_order = current_order;
    10089    expand();
    101     BlockInfo* p = static_cast<BlockInfo*>(start);
    102     if (p->size == old_size) {
    103       p->remove();
    104       (lists + current_order)->insert(p, current_size);
     90    // If heap consists of a single free block then expand it, otherwise
     91    // insert another one
     92    BlockHeader* p = last->get();
     93    if (p != null) {
     94      (last + 1)->put(p);
    10595    } else {
    106       (lists + old_order)->insert(ptr_add(p, old_size), old_size);
    107     }
     96      p = reinterpret_cast<BlockHeader*>(start_addr);
     97      last->put(ptr_add_offset(p, last->size));
     98    }
     99    //
     100    // Retry to allocate memory
    108101    return HeapAllocator::allocate(_size - sizeof(uintptr_t));
    109102  }
     
    113106{
    114107  //
    115   // shift a pointer to a true value
    116   BlockInfo* p = true_ptr(_ptr);
    117   //
    118   // get physical length of allocated block
     108  // Shift a pointer to a real start of memory block
     109  BlockHeader* p = true_ptr(_ptr);
     110  //
     111  // Get physical length of allocated block
    119112  size_t size = p->get_size();
    120113  //
    121   // loop and glue adjacent free blocks
    122   do {
    123     //
    124     // get a pointer to appropriate adjacent block
    125 //    BlockInfo* q = (sub_ptr(p, start) & size) != 0
    126 //      ? ptr_sub(p, size)
    127 //      : ptr_add(p, size);
    128     BlockInfo* q = (BlockInfo*)ptr_add(start, (sub_ptr(p, start) ^ size));
    129     //
    130     // if it is free...
     114  // Loop and glue adjacent free blocks
     115  while (size < current_size) {
     116    //
     117    // Get a pointer to appropriate adjacent block
     118    BlockHeader* q =
     119      (BlockHeader*)ptr_add_offset(start_addr, (ptr_sub(p, start_addr) ^ size));
     120    //
     121    // If it is free...
    131122    if (q->size == size) {
    132123      //
    133       // delete it from list
     124      // ...delete it from list
    134125      q->remove();
    135126      //
    136       // obtain a pointer to combined free block
    137       p = (BlockInfo*)ptr_add(start, sub_ptr(p, start) & sub_ptr(q, start));
    138       //
    139       // advance a size
     127      // Obtain a pointer to combined free block
     128      p = (BlockHeader*)ptr_add_offset(start_addr,
     129        ptr_sub(p, start_addr) & ptr_sub(q, start_addr));
     130      //
     131      // Advance a size
    140132      size <<= 1;
    141133    }
    142134    //
    143     // if it is busy...
     135    // If it is allocated...
    144136    else break;
    145   } while (size < current_size);
    146   //
    147   // insert it into appropriate free blocks list
    148   (lists + get_order(size))->insert(p, size);
     137  }
     138  //
     139  // Insert a block into appropriate free block list
     140  (lists + get_order(size))->put(p);
    149141}
    150142
     
    153145)
    154146{
    155   void* p = allocate(_size - sizeof(uintptr_t));
     147  void* p = HeapAllocator::allocate(_size - sizeof(uintptr_t));
    156148  memcpy(p, _ptr, _oldsize - sizeof(uintptr_t));
    157   deallocate(_ptr);
     149  HeapAllocator::deallocate(_ptr);
    158150  return p;
    159151}
     
    163155  size_t oldsize;
    164156  //
    165   // shift a pointer to a true value
    166   BlockInfo* p = true_ptr(_ptr);
    167   //
    168   // advance allocated size by number of bytes reserved for length
     157  // Shift a pointer to a real start of memory block
     158  BlockHeader* p = true_ptr(_ptr);
     159  //
     160  // Advance allocated size by number of bytes reserved for length
    169161  _size += sizeof(uintptr_t);
    170   _size = rounds[get_order(_size)];
    171   //
    172   // get physical length of allocated block
     162  _size = exps_of_two[get_order(_size)];
     163  //
     164  // Get physical length of allocated block
    173165  oldsize = p->get_size();
    174166  if (_size > oldsize) {
    175     if ((sub_ptr(p, start) & (_size - 1)) == 0) {
     167    if ((ptr_sub(p, start_addr) & (_size - 1)) == 0) {
    176168      size_t s = oldsize;
    177169      while (s < _size) {
    178         if ((ptr_add(p, s))->size != s)
     170        if ((ptr_add_offset(p, s))->size != s)
    179171        {
    180172          return _reallocate(_ptr, _size, oldsize);
    181173        } else {
    182           (ptr_add(p, s))->remove();
     174          (ptr_add_offset(p, s))->remove();
    183175          s <<= 1;
    184176          p->set_size(s);
     
    192184    while (_size < oldsize) {
    193185      oldsize >>= 1;
    194       (lists + get_order(oldsize))->insert(ptr_add(p, oldsize), oldsize);
     186      (lists + get_order(oldsize))->put(ptr_add_offset(p, oldsize));
    195187    }
    196188    p->set_size(_size);
     
    201193}
    202194
    203 #if DEBUG
    204 
    205 #include <stdio.h>
    206 
    207195void HeapAllocator::memory_dump ()
    208196{
    209197  {
    210     BlockInfo* p = (BlockInfo*)(start);
     198    BlockHeader* p = (BlockHeader*)(start_addr);
    211199    printf("Heap at %p\n", p);
    212200    do {
    213201      if ((p->size & 0x01) != 0) {
    214202        printf("a:%u ", p->get_size());
    215         p = ptr_add(p, p->get_size());
     203        p = ptr_add_offset(p, p->get_size());
    216204      } else {
    217205        printf("f:%u ", p->get_size());
    218         p = ptr_add(p, p->get_size());
    219       }
    220     } while ((size_t)((char*)p - (char*)start) < current_size);
     206        p = ptr_add_offset(p, p->get_size());
     207      }
     208    } while ((size_t)((char*)p - (char*)start_addr) < current_size);
    221209    printf("\n\n");
    222210  }
    223211  {
    224212    unsigned i;
    225     BlockInfo* p;
     213    BlockHeader* p;
    226214    for (i = get_order(min_free_size);
    227215         i <= get_order(current_size);
    228216         i++)
    229217    {
    230       BlockInfo* q;
    231       printf("%4u:", rounds[i]);
     218      BlockHeader* q;
     219      printf("%4u:", exps_of_two[i]);
    232220      p = lists + i;
    233221      q = p->next;
     
    244232}
    245233
    246 #endif // DEBUG
    247 
    248 }
     234}
  • to-imperative/trunk/libp++/pxx_heap_allocator.hh

    r103 r271  
    2525
    2626#include "pxx_heap.hh"
    27 #include "pxx_i_allocator.hh"
     27#include "pxx_allocator.hh"
    2828
    2929namespace pxx {
    3030
    3131//
    32 // heap allocator class
     32// Heap-based allocator class. This allocator uses a modification of
     33// D.E.Knuth's twins algorithm.
    3334class HeapAllocator :
    34   public I_Allocator,
    35   protected Heap
     35  public Allocator,
     36  public Heap
    3637{
    3738
    3839private:
    3940  //
    40   // memory block header structure
    41   struct BlockInfo
     41  // Free memory block header structure
     42  struct BlockHeader
    4243  {
    43     uintptr_t size ;            // size of block
    44     BlockInfo* prev ;           // pointer to previous free block
    45     BlockInfo* next ;           // pointer to next free block
     44    //
     45    // Block size
     46    uintptr_t size ;
     47    //
     48    // Pointer to the previous free block
     49    BlockHeader* prev ;
     50    //
     51    // Pointer to the next free block
     52    BlockHeader* next ;
     53    //
     54    // Constructor
     55    BlockHeader (BlockHeader* _prev, BlockHeader* _next, size_t _size = 0) ;
    4656
    47     BlockInfo (BlockInfo* _prev, BlockInfo* _next, size_t _size = 0) :
    48       size (_size),
    49       prev (_prev),
    50       next (_next)
    51     {}
     57    NO_COPY_CTOR(BlockHeader)
     58    NO_ASSIGN(BlockHeader)
    5259
    53     inline void remove ()
    54     {
    55       prev->next = next;
    56       next->prev = prev;
    57     }
    58 
    59     inline uintptr_t get_size () const
    60     {
    61       return size & ~((uintptr_t)(0x01));
    62     }
    63 
    64     inline void set_size (uintptr_t _size)
    65     {
    66       size = _size | 0x01;
    67     }
     60    //
     61    // Remove a memory block from free list
     62    inline void remove () ;
     63    //
     64    // Get a size of free memory block
     65    inline uintptr_t get_size () const ;
     66    //
     67    // Set a size of free memory block
     68    inline void set_size (uintptr_t _size) ;
    6869
    6970  };
    7071
     72  //
     73  // Double linked list of free memory blocks
    7174  struct FreeBlockList :
    72     public BlockInfo
     75    public BlockHeader
    7376  {
     77    //
     78    // A size of blocks in the list
     79    size_t size ;
     80    //
     81    // Constructor
     82    inline FreeBlockList () ;
    7483
    75     FreeBlockList () :
    76       BlockInfo (this, this)
    77     {}
     84    NO_COPY_CTOR(FreeBlockList)
     85    NO_ASSIGN(FreeBlockList)
    7886
    79     void insert (BlockInfo* _block, size_t _size)
    80     {
    81       BlockInfo* last = prev;
    82       _block->next = this;
    83       _block->prev = last;
    84       last->next = _block;
    85       this->prev = _block;
    86       _block->size = _size;
    87     }
     87    inline BlockHeader* get () ;
     88    inline void put (BlockHeader* _block) ;
    8889
    8990  };
    9091
    91   size_t min_free_size ;
     92  //
     93  // Minimum allowed size of a free block
     94  static size_t min_free_size ;
     95  //
     96  // An array of free block lists ;
    9297  FreeBlockList lists [sizeof(size_t) * 8] ;
     98
     99  NO_COPY_CTOR(HeapAllocator)
     100  NO_ASSIGN(HeapAllocator)
    93101
    94102public:
    95103  //
    96   // constructor
     104  // Constructor
    97105  HeapAllocator (
    98     void* const _start,
    99     size_t const _heap_size,
    100     int _fd = 0,
    101     bool _need_remap = true
     106    size_t _init_size = 0,      // Initial heap size, page size by default
     107    size_t const _max_size = 0, // Maximum size, not limited by default
     108    void* const _start = null,
     109    int _fd = -1
    102110  ) ;
    103111  //
    104   // destructor
     112  // Destructor
    105113  ~HeapAllocator () ;
    106114  //
    107   // allocate memory block of _size bytes
     115  // Allocate memory block of _size bytes
    108116  void* allocate (size_t _size) ;
    109117  //
    110   // free memory block at _ptr
     118  // Free memory block at _ptr
    111119  void deallocate (void* _ptr) ;
    112120  //
    113   // resize memory block at _ptr to _size bytes
     121  // Resize memory block at _ptr to _size bytes
    114122  void* reallocate (void* _ptr, size_t _size) ;
    115123  //
     124  // Get a size of allocated memory block
     125  inline size_t get_size (void* _ptr) ;
    116126  //
    117   inline static size_t get_size (void* _ptr)
    118   {
    119     return ((BlockInfo*)ptr_sub(_ptr, sizeof(uintptr_t)))->get_size();
    120   }
    121 
    122 #if DEBUG
    123   //
    124   // dump memory map
     127  // Dump memory map
    125128  void memory_dump () ;
    126 #endif // DEBUG
    127129
    128130private:
     
    132134  inline void* user_ptr (void* _ptr) const
    133135  {
    134     return ptr_add(_ptr, sizeof(uintptr_t));
     136    return ptr_add_offset(_ptr, sizeof(uintptr_t));
    135137  }
    136138
    137   inline BlockInfo* true_ptr (void* _ptr) const
     139  inline BlockHeader* true_ptr (void* _ptr) const
    138140  {
    139     return (BlockInfo*)ptr_sub(_ptr, sizeof(uintptr_t));
     141    return (BlockHeader*)ptr_sub_offset(_ptr, sizeof(uintptr_t));
    140142  }
    141143
Note: See TracChangeset for help on using the changeset viewer.