dllist.h
1 /*
2  * dllist.h
3  *
4  * Copyright 2007 Joey Durham <joey@engineering.ucsb.edu>
5  *
6  * This program is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License as published by
8  * the Free Software Foundation; either version 2 of the License, or
9  * (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software
18  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
19  */
20 
21 
22 #ifndef DLLIST_H
23 #define DLLIST_H
24 
25 #include <iostream>
26 #include <assert.h>
27 
28 template <class tVARTYPE> class DLList;
29 
30 
31 
32 template <class tVARTYPE> class DLLNode
33 {
34  friend class DLList<tVARTYPE>;
35 
36  protected :
37  DLLNode<tVARTYPE>* m_pNext;
38  DLLNode<tVARTYPE>* m_pPrev;
39 
40  public :
41  tVARTYPE m_data;
42 
43  DLLNode(const tVARTYPE& val)
44  {
45  m_data = val;
46 
47  m_pNext = NULL;
48  m_pPrev = NULL;
49  }
50  virtual ~DLLNode() {}
51 
52 };
53 template <class tVARTYPE> class DLList
54 {
55 
56 public:
57 
58  DLList();
59  virtual ~DLList();
60 
61  void clear();
62 
63  void insertAtBeginning(const tVARTYPE& val);
64  void insertAtEnd(const tVARTYPE& val);
65  void insertBefore(const tVARTYPE& val, DLLNode<tVARTYPE>* pThisNode);
66  void insertAfter(const tVARTYPE& val, DLLNode<tVARTYPE>* pThisNode);
67  DLLNode<tVARTYPE>* deleteNode(DLLNode<tVARTYPE>* pNode);
68  void moveToEnd(DLLNode<tVARTYPE>* pThisNode);
69 
70  DLLNode<tVARTYPE>* next(DLLNode<tVARTYPE>* pNode) const;
71  DLLNode<tVARTYPE>* prev(DLLNode<tVARTYPE>* pNode) const;
72 
73  DLLNode<tVARTYPE>* nodeNum(int iNum) const;
74 
75  int getLength() const
76  {
77  return m_iLength;
78  }
79 
80  DLLNode<tVARTYPE>* head() const
81  {
82  return m_pHead;
83  }
84 
85  DLLNode<tVARTYPE>* tail() const
86  {
87  return m_pTail;
88  }
89 
90 protected:
91  int m_iLength;
92 
93  DLLNode<tVARTYPE>* m_pHead;
94  DLLNode<tVARTYPE>* m_pTail;
95 };
96 
97 
98 
99 //constructor
100 //resets local vars
101 template <class tVARTYPE>
103 {
104  m_iLength = 0;
105 
106  m_pHead = NULL;
107  m_pTail = NULL;
108 }
109 
110 
111 //Destructor
112 //resets local vars
113 template <class tVARTYPE>
115 {
116  clear();
117 }
118 
119 
120 template <class tVARTYPE>
121 inline void DLList<tVARTYPE>::clear()
122 {
123  DLLNode<tVARTYPE>* pCurrNode;
124  DLLNode<tVARTYPE>* pNextNode;
125 
126  pCurrNode = m_pHead;
127  while (pCurrNode != NULL)
128  {
129  pNextNode = pCurrNode->m_pNext;
130  delete pCurrNode;
131  pCurrNode = pNextNode;
132  }
133 
134  m_iLength = 0;
135 
136  m_pHead = NULL;
137  m_pTail = NULL;
138 }
139 
140 
141 //inserts at the tail of the list
142 template <class tVARTYPE>
143 inline void DLList<tVARTYPE>::insertAtBeginning(const tVARTYPE& val)
144 {
145  DLLNode<tVARTYPE>* pNode;
146 
147  assert((m_pHead == NULL) || (m_iLength > 0));
148 
149  pNode = new DLLNode<tVARTYPE>(val);
150 
151  if (m_pHead != NULL)
152  {
153  m_pHead->m_pPrev = pNode;
154  pNode->m_pNext = m_pHead;
155  m_pHead = pNode;
156  }
157  else
158  {
159  m_pHead = pNode;
160  m_pTail = pNode;
161  }
162 
163  m_iLength++;
164 }
165 
166 
167 //inserts at the tail of the list
168 template <class tVARTYPE>
169 inline void DLList<tVARTYPE>::insertAtEnd(const tVARTYPE& val)
170 {
171  DLLNode<tVARTYPE>* pNode;
172 
173  assert((m_pHead == NULL) || (m_iLength > 0));
174 
175  pNode = new DLLNode<tVARTYPE>(val);
176 
177  if (m_pTail != NULL)
178  {
179  m_pTail->m_pNext = pNode;
180  pNode->m_pPrev = m_pTail;
181  m_pTail = pNode;
182  }
183  else
184  {
185  m_pHead = pNode;
186  m_pTail = pNode;
187  }
188 
189  m_iLength++;
190 }
191 
192 
193 //inserts before the specified node
194 template <class tVARTYPE>
195 inline void DLList<tVARTYPE>::insertBefore(const tVARTYPE& val, DLLNode<tVARTYPE>* pThisNode)
196 {
197  DLLNode<tVARTYPE>* pNode;
198 
199  assert((m_pHead == NULL) || (m_iLength > 0));
200 
201  if ((pThisNode == NULL) || (pThisNode->m_pPrev == NULL))
202  {
203  insertAtBeginning(val);
204  return;
205  }
206 
207  pNode = new DLLNode<tVARTYPE>(val);
208 
209  pThisNode->m_pPrev->m_pNext = pNode;
210  pNode->m_pPrev = pThisNode->m_pPrev;
211  pThisNode->m_pPrev = pNode;
212  pNode->m_pNext = pThisNode;
213 
214  m_iLength++;
215 }
216 
217 
218 //inserts after the specified node
219 template <class tVARTYPE>
220 inline void DLList<tVARTYPE>::insertAfter(const tVARTYPE& val, DLLNode<tVARTYPE>* pThisNode)
221 {
222  DLLNode<tVARTYPE>* pNode;
223 
224  assert((m_pHead == NULL) || (m_iLength > 0));
225 
226  if ((pThisNode == NULL) || (pThisNode->m_pNext == NULL))
227  {
228  insertAtEnd(val);
229  return;
230  }
231 
232  pNode = new DLLNode<tVARTYPE>(val);
233 
234  pThisNode->m_pNext->m_pPrev = pNode;
235  pNode->m_pNext = pThisNode->m_pNext;
236  pThisNode->m_pNext = pNode;
237  pNode->m_pPrev = pThisNode;
238 
239  m_iLength++;
240 }
241 
242 
243 template <class tVARTYPE>
245 {
246  DLLNode<tVARTYPE>* pPrevNode;
247  DLLNode<tVARTYPE>* pNextNode;
248 
249  assert(pNode != NULL);
250 
251  pPrevNode = pNode->m_pPrev;
252  pNextNode = pNode->m_pNext;
253 
254  if ((pPrevNode != NULL) && (pNextNode != NULL))
255  {
256  pPrevNode->m_pNext = pNextNode;
257  pNextNode->m_pPrev = pPrevNode;
258  }
259  else if (pPrevNode != NULL)
260  {
261  pPrevNode->m_pNext = NULL;
262  m_pTail = pPrevNode;
263  }
264  else if (pNextNode != NULL)
265  {
266  pNextNode->m_pPrev = NULL;
267  m_pHead = pNextNode;
268  }
269  else
270  {
271  m_pHead = NULL;
272  m_pTail = NULL;
273  }
274 
275  delete pNode;
276 
277  m_iLength--;
278 
279  return pNextNode;
280 }
281 
282 
283 template <class tVARTYPE>
285 {
286  DLLNode<tVARTYPE>* pPrevNode;
287  DLLNode<tVARTYPE>* pNextNode;
288 
289  assert(pNode != NULL);
290 
291  if (getLength() == 1)
292  {
293  return;
294  }
295 
296  if (pNode == m_pTail)
297  {
298  return;
299  }
300 
301  pPrevNode = pNode->m_pPrev;
302  pNextNode = pNode->m_pNext;
303 
304  if ((pPrevNode != NULL) && (pNextNode != NULL))
305  {
306  pPrevNode->m_pNext = pNextNode;
307  pNextNode->m_pPrev = pPrevNode;
308  }
309  else if (pPrevNode != NULL)
310  {
311  pPrevNode->m_pNext = NULL;
312  m_pTail = pPrevNode;
313  }
314  else if (pNextNode != NULL)
315  {
316  pNextNode->m_pPrev = NULL;
317  m_pHead = pNextNode;
318  }
319  else
320  {
321  m_pHead = NULL;
322  m_pTail = NULL;
323  }
324 
325  pNode->m_pNext = NULL;
326  m_pTail->m_pNext = pNode;
327  pNode->m_pPrev = m_pTail;
328  m_pTail = pNode;
329 }
330 
331 
332 template <class tVARTYPE>
334 {
335  assert(pNode != NULL);
336 
337  return pNode->m_pNext;
338 }
339 
340 
341 template <class tVARTYPE>
343 {
344  assert(pNode != NULL);
345 
346  return pNode->m_pPrev;
347 }
348 
349 
350 template <class tVARTYPE>
351 inline DLLNode<tVARTYPE>* DLList<tVARTYPE>::nodeNum(int iNum) const
352 {
353  DLLNode<tVARTYPE>* pNode;
354  int iCount;
355 
356  iCount = 0;
357  pNode = m_pHead;
358 
359  while (pNode != NULL)
360  {
361  if (iCount == iNum)
362  {
363  return pNode;
364  }
365 
366  iCount++;
367  pNode = pNode->m_pNext;
368  }
369 
370  return NULL;
371 }
372 
373 
374 #endif //LINKEDLIST_H
virtual int Subscribe(player_devaddr_t addr)
Subscribe to this driver.
static bool MatchMessage(player_msghdr_t *hdr, int type, int subtype, player_devaddr_t addr)
Helper for message processing.
Definition: message.h:159
Definition: dllist.h:28
double ReadFloat(int section, const char *name, double value)
Read a floating point (double) value.
Generic message header.
Definition: player.h:162
virtual int Subscribe(QueuePointer &, player_devaddr_t)
Subscribe to this driver.
Definition: driver.h:343
virtual int MainSetup(void)
Sets up the resources needed by the driver thread.
Definition: driver.h:658
virtual void MainQuit(void)
Cleanup method for driver thread (called when main exits)
Definition: driver.h:664
Encapsulates a device (i.e., a driver bound to an interface)
Definition: device.h:75
const char * ReadString(int section, const char *name, const char *value)
Read a string value.
virtual void Main(void)=0
Main method for driver thread.
int ReadInt(int section, const char *name, int value)
Read an integer value.
#define PLAYER_MSGTYPE_DATA
A data message.
Definition: player.h:95
virtual int ProcessMessage(QueuePointer &resp_queue, player_msghdr *hdr, void *data)
Message handler.
static bool MatchDeviceAddress(player_devaddr_t addr1, player_devaddr_t addr2)
Compare two addresses.
Definition: device.h:201
int ReadDeviceAddr(player_devaddr_t *addr, int section, const char *name, int code, int index, const char *key)
Read a device id.
int GetTupleCount(int section, const char *name)
Get the number of values in a tuple.
Class for loading configuration file information.
Definition: configfile.h:197
virtual int Setup()
Initialize the driver.
Definition: driver.h:386
A device address.
Definition: player.h:146
An autopointer for the message queue.
Definition: message.h:74
#define PLAYER_ERROR(msg)
Error message macros.
Definition: error.h:81
Base class for drivers which oeprate with a thread.
Definition: driver.h:553
Definition: dllist.h:33
#define PLAYER_WARN(msg)
Warning message macros.
Definition: error.h:89
#define PLAYER_MSGTYPE_CMD
A command message.
Definition: player.h:99
virtual int Shutdown()
Finalize the driver.
Definition: driver.h:393
Base class for all drivers.
Definition: driver.h:109
#define PLAYER_MSGQUEUE_DEFAULT_MAXLEN
Default maximum length for a message queue.
Definition: player.h:76