medfall

A super great game engine
Log | Files | Refs

slab_allocator.hpp (4098B)


      1 /*  Relacy Race Detector
      2  *  Copyright (c) 2008-2013, Dmitry S. Vyukov
      3  *  All rights reserved.
      4  *  This software is provided AS-IS with no warranty, either express or implied.
      5  *  This software is distributed under a license and may not be copied,
      6  *  modified or distributed except as expressly authorized under the
      7  *  terms of the license contained in the file LICENSE in this distribution.
      8  */
      9 
     10 #ifndef RL_SLAB_ALLOCATOR_HPP
     11 #define RL_SLAB_ALLOCATOR_HPP
     12 #ifdef _MSC_VER
     13 #   pragma once
     14 #endif
     15 
     16 #include "base.hpp"
     17 
     18 
     19 namespace rl
     20 {
     21 
     22 
     23 template<typename type>
     24 class slab_allocator : nocopy<>
     25 {
     26 public:
     27     slab_allocator()
     28         : freelist_()
     29         , blocks_()
     30         , alloc_count_()
     31     {
     32     }
     33 
     34     ~slab_allocator()
     35     {
     36         char* pos = blocks_;
     37         while (pos)
     38         {
     39             char* const next = *reinterpret_cast<char**>(pos);
     40             ::free(pos);
     41             pos = next;
     42         }
     43     }
     44 
     45     type* alloc(void* ctx = 0)
     46     {
     47         if (freelist_)
     48         {
     49             type* p = freelist_;
     50             freelist_ = *reinterpret_cast<type**>(p);
     51             alloc_count_ += 1;
     52             *(void**)p = ctx;
     53             type* pp = reinterpret_cast<type*>((reinterpret_cast<void**>(p) + 1));
     54             return pp;
     55         }
     56         else
     57         {
     58             return alloc_batch();
     59         }
     60     }
     61 
     62     void free(type* p)
     63     {
     64         type** pos = reinterpret_cast<type**>((reinterpret_cast<void**>(p) - 1));
     65         pos[0] = freelist_;
     66         freelist_ = reinterpret_cast<type*>(pos);
     67         alloc_count_ -= 1;
     68     }
     69 
     70     bool iteration_end()
     71     {
     72 #ifndef RL_GC
     73         return alloc_count_ == 0;
     74 #else
     75         freelist_ = 0;
     76         size_t elem_size = sizeof(void*) + sizeof(type);
     77         elem_size = (elem_size + 15) & ~15;
     78         char* pos = blocks_;
     79         while (pos)
     80         {
     81             char* p = pos;
     82             p += elem_size;
     83             for (size_t i = 0; i != batch_size; ++i)
     84             {
     85                 *reinterpret_cast<type**>(p) = freelist_;
     86                 freelist_ = reinterpret_cast<type*>(p);
     87                 p += elem_size;
     88             }
     89             pos = *reinterpret_cast<char**>(pos);
     90         }
     91         return true;
     92 #endif
     93     }
     94 
     95     void output_allocs(std::ostream& stream)
     96     {
     97         size_t elem_size = sizeof(void*) + sizeof(type);
     98         elem_size = (elem_size + 15) & ~15;
     99         set<void*>::type allocs;
    100         char* pos = blocks_;
    101         while (pos)
    102         {
    103             char* p = pos;
    104             p += elem_size;
    105             for (size_t i = 0; i != batch_size; ++i)
    106             {
    107                 allocs.insert(p);
    108                 p += elem_size;
    109             }
    110             pos = *reinterpret_cast<char**>(pos);
    111         }
    112         set<void*>::type avail;
    113         type* pos2 = freelist_;
    114         while (pos2)
    115         {
    116             avail.insert(pos2);
    117             pos2 = *reinterpret_cast<type**>(pos2);
    118         }
    119         vector<void*>::type diff;
    120         std::set_difference(allocs.begin(), allocs.end(), avail.begin(), avail.end(), std::back_inserter(diff));
    121         for (size_t i = 0; i != diff.size(); ++i)
    122         {
    123             stream << *(void**)diff[i] << std::endl;
    124         }
    125     }
    126 
    127 private:
    128     static size_t const batch_size = 128;
    129     type* freelist_;
    130     char* blocks_;
    131     size_t alloc_count_;
    132 
    133     RL_NOINLINE type* alloc_batch()
    134     {
    135         size_t elem_size = sizeof(void*) + sizeof(type);
    136         elem_size = (elem_size + 15) & ~15;
    137         char* const batch = (char*)(::malloc)(elem_size * (batch_size + 1));
    138         if (0 == batch)
    139             throw std::bad_alloc();
    140         *reinterpret_cast<char**>(batch) = blocks_;
    141         blocks_ = batch;
    142         char* p = batch;
    143         p += elem_size;
    144         for (size_t i = 0; i != batch_size; ++i)
    145         {
    146             *reinterpret_cast<type**>(p) = freelist_;
    147             freelist_ = reinterpret_cast<type*>(p);
    148             p += elem_size;
    149         }
    150         return alloc();
    151     }
    152 };
    153 
    154 
    155 }
    156 
    157 #endif