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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
|
/*
* PARSEC HEADER: UTL_List.h
*/
#ifndef _UTL_LIST_H_
#define _UTL_LIST_H_
#include <stdio.h>
// type for data in the list --------------------------------------------------
//
typedef void* UTL_listdata;
// struct defining one entry in the UTL_List ----------------------------------
//
template <class T>
class UTL_listentry_s
{
public:
T m_data;
UTL_listentry_s* m_pPrev;
UTL_listentry_s* m_pNext;
};
// class for holding a single linked list -------------------------------------
//
template <class T>
class UTL_List {
protected:
UTL_listentry_s<T>* m_pHead;
UTL_listentry_s<T>* m_pTail;
int m_nNumEntries;
// unlinkg an entry from the list
void _Unlink( UTL_listentry_s<T>* node )
{
ASSERT( node != NULL );
// unlink from list
if ( node->m_pNext != NULL ) {
node->m_pNext->m_pPrev = node->m_pPrev;
}
if ( node->m_pPrev != NULL ) {
node->m_pPrev->m_pNext = node->m_pNext;
}
// correct head/tail pointers
if ( node->m_pPrev == NULL ) {
ASSERT( node == m_pHead );
m_pHead = node->m_pNext;
}
if ( node->m_pNext == NULL ) {
ASSERT( node == m_pTail );
m_pTail = node->m_pPrev;
}
m_nNumEntries--;
}
public:
UTL_List()
{
m_pHead = NULL;
m_pTail = NULL;
m_nNumEntries = 0;
}
~UTL_List()
{
Clear();
}
// clear all entries in the list
void Clear()
{
UTL_listentry_s<T>* next;
for( UTL_listentry_s<T>* node = m_pHead; node != NULL; ) {
next = node->m_pNext;
delete node;
node = next;
}
m_nNumEntries = 0;
m_pHead = NULL;
m_pTail = NULL;
}
void RemoveAll() { Clear(); }
// append an entry at the tail of the list
UTL_listentry_s<T>* AppendTail( T _data )
{
UTL_listentry_s<T>* newentry = new UTL_listentry_s<T>;
newentry->m_data = _data;
newentry->m_pPrev = m_pTail;
newentry->m_pNext = NULL;
if ( m_pTail != NULL ) {
m_pTail->m_pNext = newentry;
m_pTail = newentry;
} else {
ASSERT( m_pHead == NULL );
m_pHead = newentry;
m_pTail = newentry;
}
m_nNumEntries++;
return newentry;
}
// append an entry at the head of the list
UTL_listentry_s<T>* AppendHead( T _data )
{
UTL_listentry_s<T>* newentry = new UTL_listentry_s<T>;
newentry->m_data = _data;
newentry->m_pPrev = NULL;
newentry->m_pNext = m_pHead;
if ( m_pHead != NULL ) {
m_pHead->m_pPrev = newentry;
m_pHead = newentry;
} else {
ASSERT( m_pTail == NULL );
m_pHead = newentry;
m_pTail = newentry;
}
m_nNumEntries++;
return newentry;
}
// return the head entry of the list
UTL_listentry_s<T>* GetHead() const { return m_pHead; }
// return the tail entry of the list
UTL_listentry_s<T>* GetTail() const { return m_pTail; }
// find an entry with a specific data
UTL_listentry_s<T>* Find( T& data ) const
{
for( UTL_listentry_s<T>* node = m_pHead; node != NULL; ) {
if ( node->m_data == data ) {
return node;
}
node = node->m_pNext;
}
return NULL;
}
// remove an entry specified by its data
//FIXME: evt. introduce key into UTL_listentry_s<T>
bool_t Remove( T& _data )
{
UTL_listentry_s<T>* node = Find( _data );
if ( node != NULL ) {
_Unlink( node );
delete node;
return true;
}
return false;
}
// dump contents
void Dump() const
{
int nEntry = 0;
printf( "# of entries: %d", m_nNumEntries );
for( UTL_listentry_s<T>* node = m_pHead; node != NULL; ) {
printf( "%03d: adress: %8x, data: %8x prev: %8x next: %8x\n", nEntry, (int)node, (int)node->m_data, (int)node->m_pPrev, (int)node->m_pNext );
node = node->m_pNext;
nEntry++;
}
}
// return the # of entries
int GetNumEntries() const
{
return m_nNumEntries;
}
// return the entry at a specified index
UTL_listentry_s<T>* GetEntryAtIndex( int nIndex ) const
{
// TODO: MINGW32 fails on this for some reason... might have to look into why...
//ASSERT( ( nIndex >= 0 ) && ( nIndex < m_nNumEntries ) );
int nEntry = 0;
for( UTL_listentry_s<T>* node = m_pHead; node != NULL; ) {
if ( nEntry == nIndex ) {
return node;
}
node = node->m_pNext;
nEntry++;
}
return NULL;
}
// remove entry from list, returns data in entry
T RemoveHead()
{
ASSERT( GetHead() != NULL );
return RemoveEntry( GetHead() );
}
// remove tail entry from list, returns data in entry
T RemoveTail()
{
ASSERT( GetTail() != NULL );
return RemoveEntry( GetTail() );
}
// remove entry from list, returns data in entry
T RemoveEntry( UTL_listentry_s<T>* entry )
{
ASSERT( entry != NULL );
_Unlink( entry );
T data = entry->m_data;
delete entry;
return data;
}
// call a function for each entry in the list, stop iteration upon fuction failing
void ForEach( int (*procfunc)( UTL_listentry_s<T>* node, void* param ), void* param )
{
for( UTL_listentry_s<T>* node = m_pHead; node != NULL; ) {
// call the processing function
if ( (*procfunc) (node, param ) == FALSE ) {
break;
}
node = node->m_pNext;
}
}
};
/*
template <class T>
class UTL_ListWalker
{
protected:
void* m_pData;
public:
UTL_ListWalker( )
virtual void Callback( UTL_listentry_s<T>* entry ) = 0;
};
*/
#endif // _UTL_LIST_H_
|
