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