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
|
#ifndef __DOUBLY_LINKED_LIST_H__
#define __DOUBLY_LINKED_LIST_H__
// This file (C) 2004 Steven Boswell. All rights reserved.
// Released to the public under the GNU General Public License.
// See the file COPYING for more information.
// A cheap doubly-linked-list class. Needs to be the base class for
// whatever type it's parameterized with, in order to work.
template <class TYPE>
class DoublyLinkedList
{
public:
TYPE *m_pForward;
TYPE *m_pBackward;
// Forward/backward pointers.
DoublyLinkedList();
// Default constructor.
~DoublyLinkedList();
// Destructor.
void InsertBefore (TYPE *a_pThis, TYPE *a_pCell);
// Insert the given cell before us in the list.
void InsertAfter (TYPE *a_pThis, TYPE *a_pCell);
// Insert the given cell after us in the list.
void Remove (void);
// Remove ourselves from the list we're in.
};
// Default constructor.
template <class TYPE>
DoublyLinkedList<TYPE>::DoublyLinkedList()
{
// Not part of any list.
m_pForward = m_pBackward = NULL;
}
// Destructor.
template <class TYPE>
DoublyLinkedList<TYPE>::~DoublyLinkedList()
{
// Make sure we're not part of a list any more -- otherwise, our
// destruction will leave dangling references.
assert (m_pForward == NULL);
assert (m_pBackward == NULL);
}
// Insert the given cell before us in the list.
template <class TYPE>
void
DoublyLinkedList<TYPE>::InsertBefore (TYPE *a_pThis, TYPE *a_pCell)
{
// Make sure they passed us a pointer to ourselves, different only
// by type.
assert (a_pThis == this);
// Make sure they gave us a cell to insert.
assert (a_pCell != NULL);
// Make sure the cell doesn't think it's in a list already.
assert (a_pCell->m_pForward == NULL);
assert (a_pCell->m_pBackward == NULL);
// Pretty straightforward.
a_pCell->m_pBackward = m_pBackward;
m_pBackward = a_pCell;
a_pCell->m_pForward = a_pThis;
assert (a_pCell->m_pBackward->m_pForward == a_pThis);
a_pCell->m_pBackward->m_pForward = a_pCell;
}
// Insert the given cell after us in the list.
template <class TYPE>
void
DoublyLinkedList<TYPE>::InsertAfter (TYPE *a_pThis, TYPE *a_pCell)
{
// Make sure they passed us a pointer to ourselves, different only
// by type.
assert (a_pThis == this);
// Make sure they gave us a cell to insert.
assert (a_pCell != NULL);
// Make sure the cell doesn't think it's in a list already.
assert (a_pCell->m_pForward == NULL);
assert (a_pCell->m_pBackward == NULL);
// Pretty straightforward.
a_pCell->m_pForward = m_pForward;
m_pForward = a_pCell;
a_pCell->m_pBackward = a_pThis;
assert (a_pCell->m_pForward->m_pBackward == a_pThis);
a_pCell->m_pForward->m_pBackward = a_pCell;
}
// Remove ourselves from the list we're in.
template <class TYPE>
void
DoublyLinkedList<TYPE>::Remove (void)
{
// Make sure we think we're in a list.
assert (m_pForward != NULL);
assert (m_pBackward != NULL);
// Get the nodes that we'll be pointing to. (We have to do this
// as a separate step, in case we're the last item in a circular
// list.)
TYPE *pForward = m_pForward;
TYPE *pBackward = m_pBackward;
// Remove ourselves from the doubly-linked list we're in.
m_pBackward->m_pForward = pForward;
m_pForward->m_pBackward = pBackward;
// Remove our stale links.
m_pForward = m_pBackward = NULL;
}
#endif // __DOUBLY_LINKED_LIST_H__
|