vm/free_list.hpp

   1 namespace factor
   2 {
   3
   4 static const cell free_list_count = 32;
   5 static const cell allocation_page_size = 1024;
   6
   7 struct free_heap_block
   8 {
   9         cell header;
  10
  11         bool free_p() const
  12         {
  13                 return (header & 1) == 1;
  14         }
  15
  16         cell size() const
  17         {
  18                 cell size = header & ~7;
  19 #ifdef FACTOR_DEBUG
  20                 assert(size > 0);
  21 #endif
  22                 return size;
  23         }
  24
  25         void make_free(cell size)
  26         {
  27 #ifdef FACTOR_DEBUG
  28                 assert(size > 0);
  29 #endif
  30                 header = size | 1;
  31         }
  32 };
  33
  34 struct block_size_compare {
  35         bool operator()(free_heap_block *a, free_heap_block *b)
  36         {
  37                 return a->size() < b->size();
  38         }
  39 };
  40
  41 typedef std::multiset<free_heap_block *, block_size_compare> large_block_set;
  42
  43 struct free_list {
  44         std::vector<free_heap_block *> small_blocks[free_list_count];
  45         large_block_set large_blocks;
  46         cell free_block_count;
  47         cell free_space;
  48
  49         void clear_free_list();
  50         void initial_free_list(cell start, cell end, cell occupied);
  51         void add_to_free_list(free_heap_block *block);
  52         free_heap_block *find_free_block(cell size);
  53         free_heap_block *split_free_block(free_heap_block *block, cell size);
  54         bool can_allot_p(cell size);
  55         cell largest_free_block();
  56 };
  57
  58 }