-
Notifications
You must be signed in to change notification settings - Fork 0
/
UseNodeList.hpp
128 lines (109 loc) · 2.7 KB
/
UseNodeList.hpp
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
#ifndef _USENODELIST_HPP_
#define _USENODELIST_HPP_
#include "MyStd.hpp"
#include "Node.hpp"
#ifndef _MMEM_CHECK_
//#define _MMEM_CHECK_
#endif
namespace AllocationPolicies
{
/* For this assignment we are required to use our own
version of "free store"--a linked list holding available
nodes. If a node isn't in the free store, then we can
use new to get another node */
/* The linked list here is singly linked since all nodes
are the same for our purposes */
template <class T>
struct UseNodeList {
static Node<T> * newNode( const T& val, Node<T> * nnode, Node<T> * pnode ) {
if( _head == NULL )
return new Node<T>( val, nnode, pnode );
else
{
Node<T> * head = _head;
_head = _head->next();
if( head->_data != NULL )
delete head->_data;
head->_data = new T(val);
head->_next = nnode;
head->_prev = pnode;
#ifdef _MMEM_CHECK_
cout << "Returning node #" << head->id << " from the free store" << endl;
printFreeStore();
#endif
return head;
}
}
static Node<T> * newNode( const T& val, Node<T> * nnode ) {
return newNode( val, nnode, NULL );
}
static Node<T> * newNode( const T& val ) {
return newNode( val, NULL, NULL );
}
#ifdef _MMEM_CHECK_
static void printFreeStore() {
Node<T> * node = _head;
int i = 0;
cout << "Free store: ";
while( node != NULL )
{
cout << node->id << " ";
node = node->next();
++i;
}
cout << endl;
int sze = sizeof(Node<T>);
cout << i << " nodes allocated accounting for: " << i * sze << " bytes." << endl;
}
#endif
/* 'Deletes' a node by adding it to the free store */
static void removeNode( Node<T> * node )
{
#ifdef _MMEM_CHECK_
cout << "Adding node #" << node->id << " to the free store; ";
#endif
node->_next = NULL;
node->_prev = NULL;
if( node->_data != NULL )
{
delete node->_data;
node->_data = NULL;
}
if( _head == NULL )
{
_head = node;
}
else
{
node->_next = _head;
_head = node;
}
#ifdef _MMEM_CHECK_
cout << "Head is now: #" << _head->id << endl;
printFreeStore();
#endif
}
/* I have to add this hacky function because otherwise
this design would lead to a memory leak. */
/* User MUST call this function at the end of the
program */
static void deleteFreeStore()
{
#ifdef _MMEM_CHECK_
cout << "deleteFreeStore()" << endl;
#endif
Node<T> * node = _head;
Node<T> * tmp;
while( node != NULL )
{
tmp = node;
delete node;
node = tmp->next();
}
_head = NULL;
}
static Node<T> * _head;
};
template <class T> Node<T> * UseNodeList<T>::_head = NULL;
}
#endif