| 58 | } |
| 59 | |
| 60 | void* Arena::alloc(size_t size) |
| 61 | { |
| 62 | // Round to next multiple of alignment |
| 63 | size = align_up(size, alignment); |
| 64 | |
| 65 | // Don't handle zero-sized chunks |
| 66 | if (size == 0) |
| 67 | return nullptr; |
| 68 | |
| 69 | // Pick a large enough free-chunk. Returns an iterator pointing to the first element that is not less than key. |
| 70 | // This allocation strategy is best-fit. According to "Dynamic Storage Allocation: A Survey and Critical Review", |
| 71 | // Wilson et. al. 1995, https://www.scs.stanford.edu/14wi-cs140/sched/readings/wilson.pdf, best-fit and first-fit |
| 72 | // policies seem to work well in practice. |
| 73 | auto size_ptr_it = size_to_free_chunk.lower_bound(size); |
| 74 | if (size_ptr_it == size_to_free_chunk.end()) |
| 75 | return nullptr; |
| 76 | |
| 77 | // Create the used-chunk, taking its space from the end of the free-chunk |
| 78 | const size_t size_remaining = size_ptr_it->first - size; |
| 79 | auto allocated = chunks_used.emplace(size_ptr_it->second + size_remaining, size).first; |
| 80 | chunks_free_end.erase(size_ptr_it->second + size_ptr_it->first); |
| 81 | if (size_ptr_it->first == size) { |
| 82 | // whole chunk is used up |
| 83 | chunks_free.erase(size_ptr_it->second); |
| 84 | } else { |
| 85 | // still some memory left in the chunk |
| 86 | auto it_remaining = size_to_free_chunk.emplace(size_remaining, size_ptr_it->second); |
| 87 | chunks_free[size_ptr_it->second] = it_remaining; |
| 88 | chunks_free_end.emplace(size_ptr_it->second + size_remaining, it_remaining); |
| 89 | } |
| 90 | size_to_free_chunk.erase(size_ptr_it); |
| 91 | |
| 92 | return reinterpret_cast<void*>(allocated->first); |
| 93 | } |
| 94 | |
| 95 | void Arena::free(void *ptr) |
| 96 | { |