vm/free_list.hpp

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