gc_ptr.h

Go to the documentation of this file.

/*
Copyright (c) 2017 Dr. Matthias Meixner

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
*/

#ifndef GC_PTR_H
#define GC_PTR_H

#include <mutex>
#include <vector>
#include <cstddef>
#include <atomic>

#ifndef DOXYGEN
namespace mxgc {
#endif

class gc_base_ptr;
class gc_object;

 void gc_collect();

extern std::mutex gc_mutex;                  
extern thread_local gc_object *current;      
extern std::vector<gc_object *> all_objects; 
extern long gc_counter;                      
class gc_object {

   template<class T> friend class make_gc;
   friend class gc_base_ptr;
   friend void gc_collect();

 private:
   gc_object(const gc_object &)=delete;
   void operator=(const gc_object &)=delete;

 protected:
   void *end_; 
   void *start() noexcept { return (void *)(this+1); }

   void *end() noexcept { return end_; }

   void (*destructor)(void *s, void *e);

   std::atomic<int> root_ref_cnt;

   std::atomic<gc_base_ptr *> first;

   bool mark;

 public:

   gc_object() noexcept;

   gc_object(void *e,void (*d)(void *,void *)) noexcept;

   ~gc_object();
};

class gc_base_ptr {

   friend void gc_collect();

   static void gc_collect(gc_object *o);

 protected:
   enum PtrType {
      ROOT,    
      GC_HEAP  
   } type; 
   std::atomic<gc_base_ptr *> next;       
   std::atomic<gc_object *>   object;     
 public:
   explicit gc_base_ptr(gc_object *c=nullptr);

   gc_base_ptr(const gc_base_ptr &o) : gc_base_ptr(o.object) {};

   gc_base_ptr(gc_base_ptr &&o);

   void operator=(nullptr_t);

   void operator=(const gc_base_ptr &o);

   void operator=(gc_base_ptr &&o);

   void reset();

   ~gc_base_ptr();
};


template<class T> class gc_ptr: public gc_base_ptr {
   template<class U> friend class gc_ptr;
 protected:
   T *ptr; 
 public:


   gc_ptr():gc_base_ptr() { ptr=nullptr;  }

   gc_ptr(nullptr_t):gc_base_ptr() { ptr=nullptr; }

   gc_ptr(const gc_ptr &o):gc_base_ptr(o) {  ptr=o.ptr; }

   gc_ptr(gc_ptr &&o):gc_base_ptr(std::move(o)) {  ptr=o.ptr; }

   gc_ptr(const gc_base_ptr &o, T *p):gc_base_ptr(o) { ptr=p; }


   template<class U> gc_ptr(const gc_ptr<U> &o):gc_base_ptr(o) {
      ptr=o.ptr;
   }


   gc_ptr &operator=(const gc_ptr &o) {
      gc_base_ptr::operator=(o);
      ptr=o.ptr;
      return *this;
   }

   gc_ptr &operator=(gc_ptr &&o) {
      gc_base_ptr::operator=(std::move(o));
      ptr=o.ptr;
      return *this;
   }

   gc_ptr &operator=(nullptr_t) {
      gc_base_ptr::operator=(nullptr);
      ptr=nullptr;
      return *this;
   }



   T *get() const noexcept {return ptr;}

   operator T*() const noexcept { return ptr; }

   T &operator*() const noexcept {return *ptr;}

   T *operator->() const noexcept {return ptr;}

   T &operator[](int idx) const noexcept { return ptr[idx]; }

   void reset() { ptr=nullptr; gc_base_ptr::reset(); }

   gc_ptr<T> &operator++() noexcept { ++ptr; return *this; }

   gc_ptr<T> &operator--() noexcept { --ptr; return *this; }

   gc_ptr<T> operator++(int) noexcept { gc_ptr<T> r(*this); ptr++; return r; }

   gc_ptr<T> operator--(int) noexcept { gc_ptr<T> r(*this); ptr--; return r; }


   template<class U> gc_ptr<T> &operator+=(const U &z) noexcept { ptr+=z; return *this; }

   template<class U> gc_ptr<T> &operator-=(const U &z) noexcept { ptr-=z; return *this; }
};


template<class T> class make_gc: public gc_ptr<T>
{
 public:
   template <class... Args> make_gc(Args&&... args)
   {
      // allocate memory for control object and T object
      char *mem=(char*)::operator new(sizeof(gc_object)+sizeof(T));

      // creating the control object and pushing it on the stack requires a lock
      gc_mutex.lock();

      if(gc_counter--==0) {
         gc_mutex.unlock();
         gc_collect();
         gc_mutex.lock();
      }

      // construct control object in allocated memory
      gc_object *new_object=new(mem) gc_object(mem+sizeof(gc_object)+sizeof(T),
                                             [](void *s, void *e) { T *t=(T*)s; t->~T(); });
      gc_base_ptr::object.store(new_object,std::memory_order_relaxed);


      // increment reference count if needed
      if(gc_base_ptr::type==gc_base_ptr::ROOT) new_object->root_ref_cnt.store(1,std::memory_order_relaxed);

      // push object on object list
      all_objects.push_back(new_object);

      gc_mutex.unlock();

      // store old current object in case we are in a recursion
      // and set up new current object
      gc_object *parent=current;
      current=new_object;

      // set up pointer
      gc_ptr<T>::ptr=(T*)new_object->start();

      // run the constructor of the allocated object
      try {
         new(new_object->start()) T(std::forward<Args>(args)...);
      }
      catch(...) {
         // if it fails, release reference, so that GC will clean it up
         if(gc_base_ptr::type==gc_base_ptr::ROOT) new_object->root_ref_cnt--;
         gc_base_ptr::object=nullptr;
         gc_ptr<T>::ptr=nullptr;
         current=parent;
         throw; // re-throw exception
      }

      current=parent;
   }
};

template<class T> class make_gc<T[]>: public gc_ptr<T>
{
 public:
   make_gc(unsigned size)
   {
      // allocate memory for control object and T object
      char *mem=(char*)::operator new(sizeof(gc_object)+size*sizeof(T));

      // creating the control object and pushing it on the stack requires a lock
      gc_mutex.lock();

      if(gc_counter--==0) {
         gc_mutex.unlock();
         gc_collect();
         gc_mutex.lock();
      }

      gc_object *new_object=new(mem) gc_object(mem+sizeof(gc_object)+size*sizeof(T),
                                             [](void *s, void *e) { for(T *t=(T*)e;--t>=s;) t->~T(); });
      gc_base_ptr::object.store(new_object,std::memory_order_relaxed);


      // increment reference count if needed
      if(gc_base_ptr::type==gc_base_ptr::ROOT) new_object->root_ref_cnt.store(1,std::memory_order_relaxed);

      // push object on object list
      all_objects.push_back(new_object);

      gc_mutex.unlock();

      // store old current object in case we are in a recursion
      // and set up new current object
      gc_object *parent=current;
      current=new_object;

      T *start=(T*)new_object->start();
      T *end=(T*)new_object->end();

      gc_ptr<T>::ptr=start;
      T *i;
      // run the constructor of the allocated object
      try {
         for(i=start;i!=end;i++) new(i) T();
      }
      catch(...) {
         for(T *j=i;--j>=start;) j->~T();
         if(gc_base_ptr::type==gc_base_ptr::ROOT) new_object->root_ref_cnt--;
         gc_base_ptr::object=nullptr;
         gc_ptr<T>::ptr=nullptr;
         current=parent;
         throw; // re-throw exception
      }

      current=parent;
   }
};


// comparison operators

template <class T, class U>  bool operator==(const gc_ptr<T>& lhs, const gc_ptr<U>& rhs) noexcept
{
   return lhs.get()==rhs.get();
}

template <class T> bool operator==(const gc_ptr<T>& lhs, nullptr_t n) noexcept
{
   return lhs.get()==0;
}

template <class T> bool operator==(nullptr_t n, const gc_ptr<T>& rhs) noexcept
{
   return 0==rhs.get();
}

template <class T, class U>  bool operator!=(const gc_ptr<T>& lhs, const gc_ptr<U>& rhs) noexcept
{
   return lhs.get()!=rhs.get();
}

template <class T> bool operator!=(const gc_ptr<T>& lhs, nullptr_t n) noexcept
{
   return lhs.get()!=0;
}

template <class T> bool operator!=(nullptr_t n, const gc_ptr<T>& rhs) noexcept
{
   return 0!=rhs.get();
}

template <class T, class U> bool operator<(const gc_ptr<T>& lhs, const gc_ptr<U>& rhs) noexcept
{
   return lhs.get()<rhs.get();
}

template <class T> bool operator<(const gc_ptr<T>& lhs, nullptr_t n) noexcept
{
   return lhs.get()<0;
}

template <class T> bool operator<(nullptr_t n, const gc_ptr<T>& rhs) noexcept
{
   return 0<rhs.get();
}

template <class T> bool operator<=(const gc_ptr<T>& lhs, const gc_ptr<T>& rhs) noexcept
{
   return lhs.get()<=rhs.get();
}

template <class T> bool operator<=(const gc_ptr<T>& lhs, nullptr_t n) noexcept
{
   return lhs.get()<=0;
}

template <class T> bool operator<=(nullptr_t n, const gc_ptr<T>& rhs) noexcept
{
   return 0<=rhs.get();
}

template <class T> bool operator>(const gc_ptr<T>& lhs, const gc_ptr<T>& rhs) noexcept
{
   return lhs.get()>rhs.get();
}

template <class T> bool operator>(const gc_ptr<T>& lhs, nullptr_t n) noexcept
{
   return lhs.get()>0;
}

template <class T> bool operator>(nullptr_t n, const gc_ptr<T>& rhs) noexcept
{
   return 0>rhs.get();
}

template <class T> bool operator>=(const gc_ptr<T>& lhs,  const gc_ptr<T>& rhs) noexcept
{
   return lhs.get()>=rhs.get();
}

template <class T> bool operator>=(const gc_ptr<T>& lhs, nullptr_t n) noexcept
{
   return lhs.get()>=0;
}

template <class T> bool operator>=(nullptr_t n, const gc_ptr<T>& rhs) noexcept
{
   return 0>=rhs.get();
}


template<class T, class U> gc_ptr<T> operator+(const gc_ptr<T> &a, const U &b) noexcept
{
   return gc_ptr<T>(a,a.get()+b);
}

template<class T, class U> gc_ptr<T> operator+(const U &a, const gc_ptr<T> &b) noexcept
{
   return gc_ptr<T>(b,b.get()+a);
}

template<class T, class U> gc_ptr<T> operator-(const gc_ptr<T> &a, const U &b) noexcept
{
   return gc_ptr<T>(a,a.get()-b);
}

template<class T>  auto operator-(const gc_ptr<T> &a, const gc_ptr<T> &b) noexcept -> decltype(a.get()-b.get())
{
   return a.get()-b.get();
}


template <class T, class U>  gc_ptr<T> static_pointer_cast(const gc_ptr<U>& p) noexcept
{
   return gc_ptr<T>(p,static_cast<T*>(p.get()));
}

template <class T, class U>  gc_ptr<T> dynamic_pointer_cast(const gc_ptr<U>& p) noexcept
{
   return gc_ptr<T>(p,dynamic_cast<T*>(p.get()));
}

template <class T, class U>  gc_ptr<T> const_pointer_cast(const gc_ptr<U>& p) noexcept
{
   return gc_ptr<T>(p,const_cast<T*>(p.get()));
}

template <class T, class U>  gc_ptr<T> reinterpret_pointer_cast(const gc_ptr<U>& p) noexcept
{
   return gc_ptr<T>(p,reinterpret_cast<T*>(p.get()));
}

template <class T, class U>  gc_ptr<T> pointer_cast(const gc_ptr<U>& p) noexcept
{
   return gc_ptr<T>(p,(T*)(p.get()));
}

#ifndef DOXYGEN
} // namespace
#endif

#endif