ext/OGDF/ogdf/basic/EFreeList.h

   1 /*
   2  * $Revision: 2579 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-11 15:28:17 +0200 (Mi, 11. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declaration and implementation of a simple freelist and an
  11  * index pool which generates unique indices for elements.
  12  *
  13  * \author Martin Gronemann
  14  *
  15  * \par License:
  16  * This file is part of the Open Graph Drawing Framework (OGDF).
  17  *
  18  * \par
  19  * Copyright (C)<br>
  20  * See README.txt in the root directory of the OGDF installation for details.
  21  *
  22  * \par
  23  * This program is free software; you can redistribute it and/or
  24  * modify it under the terms of the GNU General Public License
  25  * Version 2 or 3 as published by the Free Software Foundation;
  26  * see the file LICENSE.txt included in the packaging of this file
  27  * for details.
  28  *
  29  * \par
  30  * This program is distributed in the hope that it will be useful,
  31  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  32  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  33  * GNU General Public License for more details.
  34  *
  35  * \par
  36  * You should have received a copy of the GNU General Public
  37  * License along with this program; if not, write to the Free
  38  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  39  * Boston, MA 02110-1301, USA.
  40  *
  41  * \see  http://www.gnu.org/copyleft/gpl.html
  42  ***************************************************************/
  43
  44
  45 #ifdef _MSC_VER
  46 #pragma once
  47 #endif
  48
  49 #ifndef OGDF_EFREE_LIST_H
  50 #define OGDF_EFREE_LIST_H
  51
  52 #include <ogdf/basic/EList.h>
  53
  54 namespace ogdf {
  55
  56 template<typename E, E* E::*next> class EFreeList;
  57 template<typename E, E* E::*next, int E::*index> class EFreeListIndexPool;
  58
  59 template<typename E, E* E::*next> class EFreeListTypes;
  60
  61
  62 //! Simple implementation of a FreeList which buffers the memory allocation of an embedded list item.
  63 template<typename E, E* E::*next>
  64 class EFreeList
  65 {
  66         friend class EFreeListTypes<E,next>;
  67 public:
  68         //! Constructs a new freelist
  69         inline EFreeList()  { EFreeListTypes<E,next>::FreeStack::init(this); }
  70
  71         //! Destructor. Releases the mem used by the remaining elements on the stack.
  72         ~EFreeList() { this->freeFreeList(); }
  73
  74         //! Returns a new instance of E by either using an instance from the stack or creating a new one.
  75         inline E* alloc()
  76         {
  77                 if (!EFreeListTypes<E,next>::FreeStack::empty(this))
  78                         return EFreeListTypes<E,next>::FreeStack::popRet(this);
  79                 else
  80                         return new E();
  81         }
  82
  83         //! Returns true if the stack is empty.
  84         inline bool empty() const { return EFreeListTypes<E,next>::FreeStack::empty(this); }
  85
  86         //! Frees an item buy putting it onto the stack of free instances
  87         inline void free(E* ptr) { EFreeListTypes<E,next>::FreeStack::push(this, ptr); }
  88
  89 protected:
  90         //! deletes all instances in the list
  91         inline void freeFreeList()
  92         {
  93                 while (!EFreeListTypes<E,next>::FreeStack::empty(this)) { delete EFreeListTypes<E,next>::FreeStack::popRet(this); }
  94         }
  95
  96         //! Top of the stack
  97         E* m_pTop;
  98
  99         //! Typedef for the embedded stack
 100         //typedef EStack<EFreeList<E, next>, E, &EFreeList<E, next>::m_pTop, next> FreeStack;
 101 };
 102
 103 //! Type declarations for EFreeList.
 104 template<typename E, E* E::*next>
 105 class EFreeListTypes
 106 {
 107 public:
 108         typedef EStack<EFreeList<E, next>, E, &EFreeList<E, next>::m_pTop, next> FreeStack;
 109 };
 110
 111
 112 //! More complex implementation of a FreeList, which is able to generate indeices for the elements.
 113 template<typename E, E* E::*next, int E::*index>
 114 class EFreeListIndexPool
 115 {
 116 public:
 117         //! Creates a new IndexPool and a FreeList.
 118         EFreeListIndexPool() : m_nextFreeIndex(0) { }
 119
 120         //! Frees an element using the FreeList
 121         inline void free(E* ptr) { m_freeList.free(ptr); }
 122
 123         //! The value indicates that all indices in 0..numUsedIndices-1 might be in use.
 124         inline int numUsedIndices() const { return m_nextFreeIndex; }
 125
 126         //! Allocates a new Element by either using the free list or allocating a new one with a brand new index.
 127         inline E* alloc()
 128         {
 129                 if (m_freeList.empty())
 130                 {
 131                         E* res = new E();
 132                         res->*index = m_nextFreeIndex++;
 133                         return res;
 134                 } else
 135                 {
 136                         return m_freeList.alloc();
 137                 }
 138         }
 139
 140 protected:
 141         //! The next brand new index.
 142         int m_nextFreeIndex;
 143
 144         //! The free list for allocating the memory.
 145         EFreeList<E, next> m_freeList;
 146 };
 147
 148 } // end of namespace ogdf
 149
 150 #endif