---

more/gen/recycler.h

Go to the documentation of this file.

//  Copyright (C) 2001--2002  Petter Urkedal
//
//  This file 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 of the License, or
//  (at your option) any later version.
//
//  This file 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.
//
//  You should have received a copy of the GNU General Public License
//  along with this program; if not, write to the Free Software
//  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
//
//  As a special exception, you may use this file as part of a free
//  software library without restriction.  Specifically, if other files
//  instantiate templates or use macros or inline functions from this
//  file, or you compile this file and link it with other files to
//  produce an executable, this file does not by itself cause the
//  resulting executable to be covered by the GNU General Public
//  License.  This exception does not however invalidate any other
//  reasons why the executable file might be covered by the GNU General
//  Public License.
//
//  $Id: recycler.h,v 1.2 2002/08/24 13:56:07 petter_urkedal Exp $


#ifndef MORE_GEN_RECYCLER_H
#define MORE_GEN_RECYCLER_H

#include <more/gen/hook.h>
#include <more/gen/ring.h>
#include <more/gen/functional.h>
#include <list>
#include <stdexcept>
#include <string>
#ifdef MORE_ENABLE_LOGGING
#  include <iostream>
#endif


namespace more {
namespace gen {

  /** To enable some logging, set \c opt_recycler_enable_log to true.
   *  \c MORE_ENABLE_LOGGING must be defined for this to take full effect.
   */
  extern bool opt_recycler_do_log;

  class recycler_base;

  /** \class recycler_group recycler.h more/recycler.h
   *  Shared data for a group of recyclers whose objects reference each other.
   */
  struct recycler_group
  {
      recycler_group() {}
      explicit recycler_group(void (*mark_all)())
      {
          mark_hook.insert(mark_all);
      }
      ~recycler_group();

      /** Register \a mark_all to be called in the mark phase of the
       *  GC.  The set of markers registered are assumed to mark all
       *  objects which have been allocated by recyclers of this group
       *  and which are still in use.
       */
      void register_marker(void (*mark_all)()) { mark_hook.insert(mark_all); }

      /** Force a garbage collection for this group. */
      void collect();

    private:
      hook<> mark_hook;
      std::list<recycler_base*> recyclers;

      friend class recycler_base;
  };

  /** \class recycler_base recycler.h more/recycler.h
   *  Base class for \c recycler.
   *
   *  This is used to communicate between \c recycler template
   *  instantiations.
   */
  struct recycler_base
  {
      typedef unsigned long size_type;

      /** Construct a recycler which is tied to the other recyclers of
       *  \a rg. */
      explicit recycler_base(recycler_group& rg)
          : group(&rg)
      {
          group->recyclers.push_back(this);
      }

      /** Destruct the recycler, and remove it from the group. */
      virtual ~recycler_base();

    protected:
      virtual void clear_marks() = 0;

      void collect() { group->collect(); }

    private:
      recycler_group* group;

      friend class recycler_group;
  };

  /** \class recycler recycler.h more/recycler.h
   *  A type for recycling garbage collected objects.
   *
   *  \pre For any object \c x of type \c T, \c x.unset_mark() must be
   *  valid, and \c x.is_marked() must be valid and return bool.  \c
   *  x.is_marked() shall return \c false after construction of \c x
   *  and after \c x.unset_mark() is called.  After the container has
   *  requested the client to mark all used objects, \c x.is_marked()
   *  shall return true iff the object is referred to by the client.
   *  Note that also the copy assignment of T shall preserve the mark
   *  bit, i.e. it shall \e not copy it.
   *
   *  Presently the recycler never frees chunks of memory, so its
   *  memory usage will stay at its peek.  One method to free chunks,
   *  is to copy all objects unsing a new recycler, and destruct the
   *  old recycler.
   *
   *  \warning The interface of this type may change.  It is intended
   *  for internal use, at least for the moment.
   *
   *  \todo Need a mechanism to merge chunks after a peek memory
   *  consumption.  This will involve copying object, thus T must be
   *  copyable, and renaming pointers, which requires a function
   *  similar to the \c mark_all argument to the ctor.  Also, see if
   *  this class can be isolated from this file, for more general
   *  application.
   */
  template<typename T>
    struct recycler : recycler_base
    {
        typedef std::size_t size_type;
        typedef std::ptrdiff_t difference_type;
        typedef T* pointer;
        typedef T const* const_pointer;
        typedef T& reference;
        typedef T const& const_reference;
        typedef T value_type;
        template<typename U> struct rebind { typedef recycler<U> other; };

        // Since we use a different recycler for each type, keep the
        // value_count low, so that we do not waist too much memory,
        // but still high enough that the per-chunk overhead is
        // negligible.
        static const size_type value_count = 16;

        //@{
        /** The filling of chunks before GC is about \c
         *  filling_num/filling_denom.  This is a compile-time option
         *  which must be set in the source code.
         */
        static const int filling_num = 2;
        static const int filling_denom = 3;
        //@}

      private:
        struct chunk {
            chunk() {}
          private:
            chunk(chunk const&) {}
          public:
            value_type array[value_count];
        };

      public:
        /** Construct a new recycler.
         *
         *  \param mark_all is called during a GC to mark the objects,
         *  and it is assumed that it marks all used objects in this
         *  recycler and in all recyclers tied to it.
         *
         *  \param tied if supplied means that there are references
         *  between this recycler and tied, so that that GC must be
         *  synchronized.
         */
        explicit recycler(recycler_group& x)
            : recycler_base(x),
              n_allocs_since_gc(0),
              n_chunks_since_gc(0) {
            r_chunk.push_front();
            it_chunk = r_chunk.principal();
            v_cur = it_chunk->array;
            v_end = v_cur + value_count;
            v_gc = v_cur;
        }
      private: // XXX these must be implemented
        recycler(recycler const& rcyc) {}
        template<typename U> recycler(recycler<U> const&) {}
      public:

        /** Returns \c &r. */
        pointer address(reference r) const { return &r; }
        /** Returns \c &r. */
        const_pointer address(const_reference r) const { return &r; }

        /** Return an object which is no longer in use.  Note that it
         *  may contain and old value, so is may be necessary to clear
         *  it.  This can be done by assigning a new value using
         *  \c construct. */
        T* allocate(size_type n, const_pointer p = 0) {
#ifndef MORE_NDEBUG
            if (n != 1)
                throw std::logic_error("more::recycler: This allocator can "
                                       "not handle arrays.");
#endif
            while (v_cur != v_end) {
                if (!v_cur->is_marked()) {
                    ++n_allocs_since_gc;
                    return v_cur++;
                }
                ++v_cur;
            }
            return expand_and_allocate();
        }

        /** Does nothing. */
        void deallocate(pointer p, size_type n) {}

        /** Does <tt>p->~T(); new((void*)p) T;</tt> . */
        void construct(T* p) { p->~T(); new((void*)p) T; }

        /** Does <tt>p->~T(); new((void*)p) T(x);</tt> . */
        void construct(T* p, T const& x) { p->~T(); new((void*)p) T(x); }

        /** Does nothing. */
        void destroy(T*) {}

        /** Returns 1. */
        size_type max_size() { return 1; }

        template<typename Function>
          void for_each(Function f) {
              chunk_iterator it = it_chunk;
              do {
                  for (value_type* v = it->array;
                       v != it->array + value_count; ++v)
                      f(v);
              } while (++it != it_chunk);
          }

      private:
        typedef ring<chunk> chunk_container;
        typedef typename chunk_container::iterator chunk_iterator;

        T* expand_and_allocate() {
            while (v_cur != v_gc) {
                ++it_chunk;
                ++n_chunks_since_gc;
                v_cur = it_chunk->array;
                v_end = v_cur + value_count;
                if (v_cur <= v_gc && v_gc < v_end)
                    v_end = v_gc;

              redo:
                while (v_cur != v_end) {
                    if (!v_cur->is_marked()) {
                        ++n_allocs_since_gc;
                        return v_cur++;
                    }
                    ++v_cur;
                }
            }
            // n_skips = n_allocs + n_misses
            size_type n_skips
                = n_chunks_since_gc*value_count
                + (v_cur - it_chunk->array);
#ifdef MORE_ENABLE_LOGGING
            if (opt_recycler_do_log)
                std::clog << "more::recycler: Availability ratio = "
                          << n_allocs_since_gc << '/' << n_skips
                          << ". ";
#endif
            if (n_allocs_since_gc*filling_denom
                >= n_skips*(filling_denom - filling_num)) {
#ifdef MORE_ENABLE_LOGGING
                std::clog << "Collecting.\n";
                std::clog.flush();
#endif
                collect();
                goto redo;
            }
            else {
#ifdef MORE_ENABLE_LOGGING
                std::clog << "Expanding.\n";
                std::clog.flush();
#endif
                it_chunk = r_chunk.insert(it_chunk);
                v_cur = it_chunk->array;
                v_end = v_cur + value_count;
                ++n_allocs_since_gc;
                return v_cur++;
            }
        }

        virtual void clear_marks() {
            chunk_iterator it = it_chunk;
            do {
                for (value_type* v = it->array;
                     v != it->array + value_count; ++v)
                    v->unset_mark();
            } while (++it != it_chunk);
            n_allocs_since_gc = 0;
            n_chunks_since_gc = 0;
            v_gc = v_cur;
            v_end = it_chunk->array + value_count;
        }

        static void clear_marks_helper(chunk* ch) {
            while (ch) {
                for (value_type* v = ch->array;
                     v != ch->array + value_count; ++v)
                    v->unset_mark();
                ch = ch->prev;
            }
        }

        chunk_container r_chunk;
        chunk_iterator  it_chunk;

        value_type* v_cur;
        value_type* v_end;
        value_type* v_gc;

        size_type n_allocs_since_gc;
        size_type n_chunks_since_gc;
    };
}} // more::gen

#endif

---