+ return block_index;
+}
+
+unsigned MemoryAllocator::split_block(unsigned index, size_t head_size)
+{
+ blocks.emplace_back();
+ Block &block = blocks[index];
+ Block &tail = blocks.back();
+ unsigned tail_index = blocks.size()-1;
+
+ tail.region = block.region;
+ tail.offset = block.offset+head_size;
+ tail.size = block.size-head_size;
+ tail.prev = index;
+ tail.next = block.next;
+
+ block.size = head_size;
+ block.next = tail_index;
+
+ return tail_index;
+}
+
+void MemoryAllocator::consolidate(unsigned pool_index)
+{
+ Pool &pool = pools[pool_index];
+
+ vector<unsigned> merged_blocks;
+ unsigned i = 0;
+ for(unsigned j=0; j<pool.free_blocks.size(); ++j)
+ {
+ unsigned block_index = pool.free_blocks[j];
+ Block &block = blocks[block_index];
+ if(!block.allocated)
+ {
+ if(block.prev<0 || blocks[block.prev].allocated)
+ {
+ if(block.next>=0 && !blocks[block.next].allocated)
+ {
+ merge_block_with_next(block_index);
+
+ while(block.next>=0 && !blocks[block.next].allocated)
+ merge_block_with_next(block_index);
+
+ merged_blocks.insert(lower_bound_by_size(merged_blocks, block.size), block_index);
+ }
+ }
+ else
+ continue;
+ }
+
+ if(j!=i)
+ pool.free_blocks[i] = block_index;
+ ++i;
+ }
+
+ pool.free_blocks.resize(i+merged_blocks.size());
+
+ if(!merged_blocks.empty())
+ {
+ unsigned j = merged_blocks.size();
+ for(unsigned k=pool.free_blocks.size()-1; j; --k)
+ {
+ if(!i || blocks[merged_blocks[j-1]].size>blocks[pool.free_blocks[i-1]].size)
+ pool.free_blocks[k] = merged_blocks[--j];
+ else
+ pool.free_blocks[k] = pool.free_blocks[--i];
+ }
+ }
+}
+
+void MemoryAllocator::merge_block_with_next(unsigned index)
+{
+ Block &block = blocks[index];
+
+ Block &next = blocks[block.next];
+ block.size += next.size;
+ block.next = next.next;
+ if(block.next>=0)
+ blocks[block.next].prev = index;
+
+ next = Block();