/* Copyright (c) 1997-2006
   Ewgenij Gawrilow, Michael Joswig (Technische Universitaet Berlin, Germany)
   http://www.math.tu-berlin.de/polymake,  mailto:polymake@math.tu-berlin.de

   This program is free software; you can redistribute it and/or modify it
   under the terms of the GNU General Public License as published by the
   Free Software Foundation; either version 2, or (at your option) any
   later version: http://www.gnu.org/licenses/gpl.txt.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
*/

#ifndef _POLYMAKE_SHARED_OBJECT_H
#define _POLYMAKE_SHARED_OBJECT_H "$Project: polymake $$Id: shared_object.h 7439 2006-10-05 21:10:59Z gawrilow $"

#include <algorithm>
#include <memory>

#ifndef _POLYMAKE_CONSTRUCTORS_H
#  include <constructors.h>
#endif
#ifndef _POLYMAKE_ITERATORS_H
#  include <iterators.h>
#endif

namespace pm {

template <typename Owner>
class alias_to_shared {
protected:
   const Owner* ptr;
public:
   alias_to_shared(const Owner* ptr_arg)
      : ptr(ptr_arg) {
      ++(ptr->data_member().aliascnt);
   }
   alias_to_shared(const alias_to_shared& other)
      : ptr(other.ptr) {
      ++(ptr->data_member().aliascnt);
   }
   alias_to_shared& operator= (const alias_to_shared& other) {
      ++(other.ptr->data_member().aliascnt);
      --(ptr->data_member().aliascnt);
      ptr=other.ptr;
      return *this;
   }
   ~alias_to_shared() {
      --(ptr->data_member().aliascnt);
   }

   const Owner* get_owner() const { return ptr; }
};

template <bool copy_on_write=true>
class shared_base {
   template <typename Owner> friend class alias_to_shared;
   mutable int aliascnt;
protected:
   shared_base() : aliascnt(0) { }

   int get_aliases() const { return aliascnt; }
   void reset_aliases() { aliascnt=0; }
};

template <>
class shared_base<false> {
protected:
   int get_aliases() const { return 0; }
   void reset_aliases() { }
};

template <typename> class Nullable;
template <typename> class CopyOnWrite;

class shared_object_secrets {
protected:
   struct rep {
      /// reference counter: number of hosts
      long refc;
      /// number of objects
      size_t size;

      // prevent from being ever destroyed
      rep() : refc(1), size(0) {}
   };

   static rep empty_rep;
};

class shared_pointer_secrets {
protected:
   struct rep {
      void *obj;
      long refc;

      // prevent from being ever destroyed
      rep() : obj(0), refc(1) {}
   };

   static rep null_rep;
};


/** Automatic pointer to shared data

    This class implements an automatic pointer to a data object that can be shared
    among several hosts. The data instance remains shared as far as all hosts it is attached to
    don't attempt to change it (read-only access). The host that wants to get read-write access
    to the data automatically obtains a new copy, while its former partners continue
    sharing the old one.

    In that way, a copy of the host always shares the data instance with the original host.
    Assignment to a host causes it to detach the old data instance and share the new one with
    the host being assigned from.

    The data instance is destroyed together with the last host is is attached to.

    @tmplparam Object type of the attached object
    @index tools Automatic Pointers
*/
template <typename Object, typename Params=void>
class shared_object
   : public shared_base<extract_bool_param<Params, CopyOnWrite, true>::value>,
     protected shared_object_secrets {
protected:
   static const bool
      copy_on_write=extract_bool_param<Params, CopyOnWrite, true>::value,
      nullable=extract_bool_param<Params, Nullable, false>::value;

   struct rep {
      /// the attached object itself
      Object obj;
      /// reference counter: number of hosts
      long refc;
   private:
      static rep* allocate()
      {
	 std::allocator<rep> alloc;
	 rep *r=(rep*)alloc.allocate(1);
	 r->refc=1;
	 return r;
      }

      static void deallocate(rep *r)
      {
	 std::allocator<rep> alloc;
	 alloc.deallocate(r,1);
      }

      static void empty(shared_object *owner)
      {
	 if (owner) {
	    if (nullable) {
	       owner->body=0;
	    } else {
	       rep* r=reverse_cast(&empty_rep.refc, &rep::refc);
	       ++r->refc;
	       owner->body=r;
	    }
	 }
      }

      template <typename PointedObject>
      static void destroy(PointedObject *o)
      {
	 o->~PointedObject();
      }

      template <typename PointedObject>
      static void destroy(PointedObject** o)
      {
	 delete *o;
      }

   public:
      static rep* init(rep *r, const Object& o, shared_object *owner)
      {
	 try {
	    new(&r->obj) Object(o);
	 } catch (...) {
	    deallocate(r);
	    empty(owner);
	    throw;
	 }
	 return r;
      }

      template <typename Fptr>
      static rep* init(rep *r, const constructor<Fptr>& c, shared_object *owner)
      {
	 try {
	    c(&r->obj);
	 } catch (...) {
	    deallocate(r);
	    empty(owner);
	    throw;
	 }
	 return r;
      }

      template <typename Arg>
      static rep* construct(const Arg& arg, shared_object *owner=0)
      {
	 return init(allocate(), arg, owner);
      }

      void destroy()
      {
	 destroy(&obj);
      }

      static void destruct(rep *r)
      {
	 r->destroy();
	 deallocate(r);
      }
   };

   rep *body;

   // Detache the object or delete it.
   void leave()
   {
      if (nullable && !body) return;
      if (! --body->refc) rep::destruct(body);
   }

   // Create an own object instance and decrease the reference counter of the old one.
   void divorce();

   shared_object(rep* p) : body(p) {}
public:
   /// Create the attached object with its default constructor.
   shared_object()
      : body(rep::construct(constructor<Object()>())) {}

   // Create the attached object with its copy constructor.
   shared_object(const Object& obj_arg)
      : body(rep::construct(obj_arg)) {}

   template <typename Fptr>
   shared_object(const constructor<Fptr>& c)
      : body(rep::construct(c)) {}

   // Share the object attached to @c s.
   shared_object(const shared_object& s)
      : body(s.body)
   {
      ++body->refc;
   }

   ~shared_object() { leave(); }

   // Detach or delete the old instance, shares the one attached to @c s.
   shared_object& operator= (const shared_object& s)
   {
      ++s.body->refc;
      leave();
      body=s.body;
      return *this;
   }

   template <typename Fptr>
   shared_object& operator= (const constructor<Fptr>& c)
   {
      if (body->refc > 1) {
	 --body->refc;
	 body=rep::construct(c, this);
      } else {
	 body->destroy();
	 rep::init(body, c, this);
      }
      return *this;
   }

   void clear()
   {
      if (body->refc > 1) {
	 --body->refc;
	 body=rep::construct(constructor<Object()>(), this);
      } else {
	 body->obj.clear();
      }
   }

   void swap(shared_object& s2)
   {
      std::swap(body,s2.body);
   }

   friend void relocate(shared_object* from, shared_object* to)
   {
      to->body=from->body;
      to->reset_aliases();
   }

   bool has_aliases() const { return this->get_aliases(); }
   long get_refcnt() const { return body->refc; }
   bool is_shared() const { return this->get_aliases() + body->refc > 1; }

   Object* operator-> ()
   {
      if (copy_on_write && body->refc > 1) divorce();
      return &body->obj;
   }
   Object& operator* ()
   {
      if (copy_on_write && body->refc > 1) divorce();
      return body->obj;
   }

   Object* get()
   {
      return &body->obj;
   }

   const Object* operator-> () const
   {
      return &body->obj;
   }
   const Object& operator* () const
   {
      return body->obj;
   }
};

template <typename Object>
class nullable_shared_object
   : public shared_object<Object, list( Nullable<True>, CopyOnWrite<False> )> {
   typedef shared_object<Object, list( Nullable<True>, CopyOnWrite<False> )> super;
public:
   nullable_shared_object() : super((typename super::rep*)0) { }
   nullable_shared_object(const Object& obj_arg) : super(obj_arg) { }

   nullable_shared_object(const nullable_shared_object& s) : super((void*)0)
   {
      if (s.body) {
	 this->body=s.body;
	 ++this->body->refc;
      }
   }

   nullable_shared_object& operator= (const nullable_shared_object& s)
   {
      if (s.body) ++s.body->refc;
      if (this->body) this->leave();
      this->body=s.body;
      return *this;
   }

   void clear()
   {
      if (this->body) this->leave();
      this->body=0;
   }

   operator bool() const { return this->body != 0; }
   bool operator! () const { return this->body == 0; }
};

/** Like in boost, but not MT-safe (and hence without overhead) */
template <typename Object>
class shared_pointer
   : public shared_object<Object*, CopyOnWrite<False> >,
     protected shared_pointer_secrets {
   typedef shared_object<Object*, CopyOnWrite<False> > super;
   typedef typename super::rep rep;
public:
   shared_pointer()
      : super(reinterpret_cast<rep*>(&null_rep)) { ++this->body->refc; }

   shared_pointer(Object *o)
      : super(o) {}

   shared_pointer& operator= (Object *o)
   {
      if (__builtin_expect(o!=0,1)) {
	 if (this->body->refc==1) {
	    this->body->destroy();
	    this->body->obj=o;
	 } else {
	    --this->body->refc;
	    this->body=rep::construct(o);
	 }
      } else {
	 this->leave();
	 this->body=reinterpret_cast<rep*>(&null_rep);
	 ++this->body->refc;
      }
      return *this;
   }

   Object& operator* () { return *this->body->obj; }
   const Object& operator* () const { return *this->body->obj; }
   Object* operator-> () { return this->body->obj; }
   const Object* operator-> () const { return this->body->obj; }

   operator Object* () { return this->body->obj; }
   operator const Object* () const { return this->body->obj; }

   bool operator== (const shared_pointer& other) const { return this->body->obj == other.body->obj; }
   bool operator!= (const shared_pointer& other) const { return this->body->obj != other.body->obj; }

   template <typename OtherObject>
   typename enable_if< shared_pointer<OtherObject>&, derived_from<OtherObject,Object>::value ||
                                                     derived_from<Object,OtherObject>::value>::type
   cast()
   {
      return reinterpret_cast<shared_pointer<OtherObject>&>(*this);
   }

   template <typename OtherObject>
   typename enable_if<const shared_pointer<OtherObject>&, derived_from<OtherObject,Object>::value ||
                                                          derived_from<Object,OtherObject>::value>::type
   cast() const
   {
      return reinterpret_cast<const shared_pointer<OtherObject>&>(*this);
   }

   static shared_pointer new_object() { return new Object; }
};

template <typename T>
struct deref_ptr< shared_pointer<T> > : deref_ptr<T> { };

template <typename T>
struct deref_ptr< const shared_pointer<T> > : deref_ptr<const T> { };

/** Automatic pointer to a shared data array

    It has the same semantics as @see shared_object, with the main difference that
    there are several data objects packed in the array instance that is being shared.

    @tmplparam Object type of the object in the array
*/
template <typename Object, typename Params=void>
class shared_array
   : public shared_base<extract_bool_param<Params, CopyOnWrite, true>::value>,
     protected shared_object_secrets {
protected:
   static const bool copy_on_write=extract_bool_param<Params, CopyOnWrite, true>::value;

   /// Attached objects plus housekeeping
   struct rep : shared_object_secrets::rep {
      /// data objects
      Object obj[1];
   private:
      static size_t total_size(size_t n)
      {
	 return sizeof(rep)-sizeof(Object)+n*sizeof(Object);
      }

      static rep* allocate(size_t n)
      {
	 allocator alloc;
	 rep *r=(rep*)alloc.allocate(total_size(n));
	 r->refc=1;
	 r->size=n;
	 return r;
      }

      static void deallocate(rep *r)
      {
	 allocator alloc;
	 alloc.deallocate(reinterpret_cast<allocator::value_type*>(r),total_size(r->size));
      }

      static void destroy(Object *end, Object *first)
      {
	 if (!has_trivial_destructor<Object>::value)
	    while (end > first)
	       (--end)->~Object();
      }

      static void empty(shared_array *owner)
      {
	 if (owner) owner->body=construct();
      }

      /// Initialize array elements with a constructor
      template <typename Ftpr>
      static Object* init(rep *r, Object *dst, Object *end, const constructor<Ftpr>& c, shared_array *owner)
      {
	 try {
	    for (; dst != end; ++dst)
	       c(dst);
	    return dst;
	 }
	 catch (...) {
	    destroy(dst,r->obj);
	    deallocate(r);
	    empty(owner);
	    throw;
	 }
      }

      /// Initialize array elements with values from a sequence
      template <typename Iterator>
      static Object* init(rep *r, Object *dst, Object *end, Iterator src, shared_array *owner)
      {
	 try {
	    for (; dst != end; ++src, ++dst)
	       new(dst) Object(*src);
	    return dst;
	 }
	 catch (...) {
	    destroy(dst,r->obj);
	    deallocate(r);
	    empty(owner);
	    throw;
	 }
      }

      template <typename Iterator>
      static Object* init(rep *r, Object *dst, const Iterator& src, True, shared_array *owner)
      {
	 try {
	    new(dst) Object(*src);
	    ++dst;
	    return dst;
	 }
	 catch (...) {
	    destroy(dst,r->obj);
	    deallocate(r);
	    empty(owner);
	    throw;
	 }
      }

      template <typename Iterator>
      static Object* init(rep *r, Object *dst, const Iterator& src, False, shared_array *owner)
      {
	 try {
	    typedef typename ensure_features<typename iterator_traits<Iterator>::value_type,
	                                     cons<end_sensitive, dense> >::const_iterator
	       sub_iterator;
	    for (sub_iterator it=ensure(*src, (cons<end_sensitive, dense>*)0).begin();
		 !it.at_end(); ++it)
	       dst=init(r, dst, it, bool2type<isomorphic_types<Object, typename iterator_traits<sub_iterator>::value_type>::value>(), owner);
	    return dst;
	 }
	 catch (...) {
	    destroy(dst,r->obj);
	    deallocate(r);
	    empty(owner);
	    throw;
	 }
      }

   public:
      static rep* construct()
      {
	 rep *r=static_cast<rep*>(&empty_rep);
	 ++r->refc;
	 return r;
      }

      template <typename Init>
      static rep* construct(size_t n, const Init& src, shared_array *owner=0)
      {
	 rep *r=allocate(n);
	 init(r, r->obj, r->obj+n, src, owner);
	 return r;
      }

      /// relocate or copy
      template <typename Init>
      static rep* resize(size_t n, rep* old, const Init& src, shared_array *owner)
      {
	 rep *r=allocate(n);
	 const size_t n_copy=std::min(n,old->size);
	 Object *dst=r->obj, *middle=dst+n_copy, *end=dst+n;

	 if (old->refc > 0) {
	    init(r, dst, middle, const_cast<const Object*>(old->obj), owner);
	 } else {
	    Object *src_copy=old->obj, *src_end=src_copy+old->size;
	    for (; dst!=middle;  ++src_copy, ++dst)
	       relocate(src_copy,dst);
	    destroy(src_end, src_copy);
	    deallocate(old);
	 }
	 init(r, middle, end, src, owner);
	 return r;
      }

      template <typename Iterator>
      static rep* weave(size_t n, size_t slice, rep *old, Iterator& src, shared_array *owner)
      {
	 rep *r=allocate(n);
	 Object *dst=r->obj, *end=dst+n;

	 if (old->refc > 0) {
	    const Object *src_copy=old->obj;
	    while (dst != end) {
	       dst=init(r, dst, dst+slice, src_copy, owner);
	       src_copy+=slice;
	       dst=init(r, dst, src, bool2type<isomorphic_types<Object, typename iterator_traits<Iterator>::value_type>::value>(), owner);
	       ++src;
	    }
	 } else {
	    Object *src_copy=old->obj;
	    while (dst != end) {
	       for (Object *slice_end=dst+slice; dst!=slice_end; ++src_copy, ++dst)
		  relocate(src_copy,dst);
	       dst=init(r, dst, src, bool2type<isomorphic_types<Object, typename iterator_traits<Iterator>::value_type>::value>(), owner);
	       ++src;
	    }
	    deallocate(old);
	 }
	 return r;
      }

      static void destruct(rep *r)
      {
	 destroy(r->obj+r->size, r->obj);
	 deallocate(r);
      }
   };

   /// Pointer to the attached array.
   rep *body;

   /// Detach the array or deletes it.
   void leave()
   {
      if (! --body->refc) rep::destruct(body);
   }

   /// Create an own array instance and decreases the reference counter of the old one.
   void divorce();
public:
   /// Create an empty array.
   shared_array()
      : body(rep::construct()) { }

   /// Create an array with @c n elements initialized with default constructor
   explicit shared_array(size_t n)
      : body(rep::construct(n, constructor<Object()>())) { }

   template <typename Iterator>
   shared_array(size_t n, const Iterator& src)
      : body(rep::construct(n, src)) { }

   /// Shares the data array attached to @c s.
   shared_array(const shared_array& s)
      : body(s.body) { ++body->refc; }

   /// Returns the current size of the array.
   size_t size() const { return body->size; }

   ~shared_array() { leave(); }

   /// Detach or destroy the old array, attach the new one.
   shared_array& operator= (const shared_array& s)
   {
      ++s.body->refc;
      leave();
      body=s.body;
      return *this;
   }

   void swap(shared_array& a) { std::swap(body, a.body); }

   friend void relocate(shared_array* from, shared_array* to)
   {
      to->body=from->body;
      to->reset_aliases();
   }

   void clear()
   {
      if (size()) {
	 leave();
	 body=rep::construct();
      }
   }

   /** Change the size of the array.
       If $n$ is less than the actual size, the first $n$ elements are copied to 
       a new location, the trailing ones are destroyed.
       Otherwise, new elements are appended and initialized with default constructor.
   */
   void resize(size_t n)
   {
      if (n != body->size) {
	 --body->refc;
	 body=rep::resize(n,body,constructor<Object()>(),this);
      }
   }

   template <typename Iterator>
   void append(size_t n, Iterator src)
   {
      if (n) {
	 --body->refc;
	 body=rep::resize(n+body->size,body,src,this);
      }
   }

   template <typename Iterator>
   void weave(size_t n, size_t slice, Iterator src)
   {
      if (n) {
	 --body->refc;
	 body=rep::weave(n+body->size,slice,body,src,this);
      }
   }

   bool has_aliases() const { return this->get_aliases(); }
   long get_refcnt() const { return body->refc; }
   bool is_shared() const { return this->get_aliases() + body->refc > 1; }

   /** Assign the values from an input dense sequence.
       If the attached array instance is shared or its size is not equal to \\n\\,
       it is detached rsp. destroyed and a new one is created and initialized from the
       input sequence. Otherwise assigns the input data to the array elements.
   */
   template <typename Iterator>
   void assign(size_t n, Iterator src)
   {
      if (has_aliases() || body->size != n) {
	 rep *newbody=rep::construct(n,src);
	 leave();
	 body=newbody;
      } else {
	 for (Object *dst=body->obj, *end=dst+n;  dst!=end;  ++src, ++dst)
	    *dst = *src;
      }
   }

   /** Return a read-write pointer to the first element of the attached array.
       If it is shared, a new instance is created with the copy constructor and
       attached instead.
   */
   Object* operator* ()
   {
      if (copy_on_write && body->refc > 1) divorce();
      return body->obj;
   }

   /** Return a read-only pointer to the first element of the attached array.
       The shared state of the array remains unchanged.
   */
   const Object* operator* () const
   {
      return body->obj;
   }
};

template <typename Object, typename Params>
void shared_object<Object,Params>::divorce()
{
   --body->refc;
   body=rep::construct(body->obj, this);
}

template <typename Object, typename Params>
void shared_array<Object,Params>::divorce()
{
   --body->refc;
   const Object *src=body->obj;
   body=rep::construct(body->size, src, this);
}

} // end namespace pm

namespace std {
   template <typename Object, typename Params> inline
   void swap(pm::shared_object<Object,Params>& s1, pm::shared_object<Object,Params>& s2) {
      s1.swap(s2);
   }

   template <typename Object, typename Params> inline
   void swap(pm::shared_array<Object,Params>& a1, pm::shared_array<Object,Params>& a2) {
      a1.swap(a2);
   }
} // end namespace std

#endif // _POLYMAKE_SHARED_OBJECT_H

// Local Variables:
// mode:C++
// End:
