versadac  1
versadac - Scalable Recorder Firmware
lists.h
1 /* $Id: lists.h 4938 2006-10-10 14:20:18Z martinto $ */
2 /*
3  *
4  * Revision 2.1 1997/07/10 16:24:13 davec
5  * DEV1196:DCN001 moved source to CVS
6  *
7  *
8  * Rev 1.1.1.2 22 Jul 1996 13:58:06 DAVEH
9  * DEV1156:DCN098- remove the word hacked
10  *
11  * Rev 1.1.1.1 03 Jul 1996 14:22:48 DAVEH
12  * DEV1156:DCN076-Memory saving exercise
13  *
14  * Rev 1.1.1.0 24 Jan 1996 15:07:40 PAULT
15  * Branched
16  *
17  * Rev 1.1 24 Jan 1996 12:17:02 PAULT
18  * Consolidated 4100 code merged to trunk
19  *
20  * Rev 1.0.2.0 01 Jun 1995 14:25:46 DAVEH
21  * Branched
22  *
23  * Rev 1.0 12 Apr 1995 17:20:38 COLINL
24  * Initial revision.
25 */
26 /*****************************************************************************
27 FILE : L I S T S . H
28 VERSION : %I%
29 AUTHOR : Colin Law
30 SYSTEM : Turbo C++
31 DESCRIPTION : Header file for linked list base classes
32 
33 Classes defined in this file provide a base from which to inherit linked
34 lists of various types.
35 Class List provides the methods for creating and destroying the List.
36 Class ListWalker allows movement through the list, insertion of items into
37 it, extraction from it, etc.
38 
39 Note that when items are added to a list they are merely linked into it
40 rather than copied to a new memory location. Therefore it is important
41 to ensure that items added to the list remain in scope through the life of
42 the list. It is generally advisable to pass items to the list in dynamically
43 allocated memory rather than in named variables. Items should then be
44 considered to belong to the list once they have been added to it. In
45 particular the item must not be deleted without extracting it from the list.
46 To cope with automatic list destruction all derived classes must provide a
47 function to destroy individual items, as the list does not know how to do
48 this. This is the virtual function List::destructItem which is given a
49 pointer to an item in the list to be destroyed. Items should not normally
50 be put on more than one list at a time unless the user fully understands the
51 implementation.
52 
53 See strlists.h and .cpp for example of how to derive ListOfThingies
54 
55 *****************************************************************************/
56 
57 #if !defined(__LISTS_H)
58 
59 #define __LISTS_H
60 
61 #if defined ISE_PNL_MEMORY
62 #include "pnl_mem.pc"
63 #endif
64 
65 #if defined LISTS_USER_MALLOC
66 #include <stdlib.h>
67 #endif
68 
69 extern "C"
70 {
71 #include "stdtypes.h"
72 }
73 
74 enum statusCode
75 {
76  STATUS_OK,
77  STATUS_FAIL
78 };
79 
80 class ListNode; // declaration needed for declaration of class List
81  // ListNode is defined in lists.cpp
82 
83 /* ##########################################################################
84 CLASS : L I S T
85 DESCRIPTION : This class provides the basic methods for creating and
86  destroying a linked list. Methods are provided for adding
87  items into the front and end of the list. See ListWalker
88  for methods to access the list in more sophisticated ways.
89 ########################################################################### */
90 
91 class List
92 #if defined ISE_PNL_MEMORY
93  : public CpnlMem
94 #endif
95 {
96  friend class ListWalker;
97  friend class ListNode;
98 
99  public:
100 
101 /*********************************************************************
102  Public Methods for L I S T
103 *********************************************************************/
104 
105 /*---------------------------------------------------------------------------
106 FUNCTION : L I S T constructor
107 DESCRIPTION : Constructs an empty list
108 ARGUMENTS : None
109 RETURN : None
110 NOTES :
111 ---------------------------------------------------------------------------*/
112  List();
113 
114 #if defined LISTS_USER_MALLOC
115 /*---------------------------------------------------------------------------
116 FUNCTION : L I S T constructor
117 DESCRIPTION : Alternative constructor to be used when the user wishes
118  to provide memory allocation and free routines rather than
119  use new and delete.
120  Constructs an empty list
121 ARGUMENTS : pUserMalloc pointer to user supplied function to be called to
122  allocate memory for list nodes
123  pUserFree pointer to user supplied function to be called to
124  free memory for list nodes
125  pUserItemFree pointer to user supplied function to be called to
126  free up list item memory if deleting data from list
127  userData a 32 bit value that will be passed to the user
128  alloc and free routines.
129 RETURN : None
130 NOTES :
131 ---------------------------------------------------------------------------*/
132  List( void* (*pUserMalloc)( size_t, uint32 ),
133  void (*pUserFree)( void*, uint32 ),
134  void (*pUserItemFree)( void*, uint32 ),
135  uint32 userData );
136 #endif
137 
138 /*---------------------------------------------------------------------------
139 FUNCTION : L I S T destructor
140 DESCRIPTION : Destroys list
141 ARGUMENTS : None
142 RETURN : None
143 NOTES : This is declared as a pure virtual function in order to ensure
144  that all derived classes supply a destructor. The derived
145  class destructor must call clear() which then calls the virtual
146  destroyItem() function for each item in the list. It is not
147  possible for List::~List to call clear itself as functions are
148  de-virtualised when called in destructors.
149 ---------------------------------------------------------------------------*/
150  virtual ~List() = 0;
151 
152 /*---------------------------------------------------------------------------
153 FUNCTION : List C L E A R
154 DESCRIPTION : Method to empty a list, releasing dynamic memory.
155 
156 ARGUMENTS : None
157 RETURN : None
158 NOTES : Note that this calls destructItem for each item in the list.
159  As these will normally be dynamically allocated this function
160  destroys the items in the list. Any items required for further
161  use should be extracted before the list is cleared.
162 ---------------------------------------------------------------------------*/
163  void clear();
164 
165 /*---------------------------------------------------------------------------
166 FUNCTION : List I T E M C O U N T
167 DESCRIPTION : Method returning number of items currently on list
168 
169 ARGUMENTS : None
170 RETURN : Number of items
171 NOTES :
172 ---------------------------------------------------------------------------*/
173  uint32 itemCount();
174 
175 #if defined LISTS_USER_MALLOC
176 /*---------------------------------------------------------------------------
177 FUNCTION : L I S T setUserMallocFunctions
178 DESCRIPTION : Service that may be used after the list is constructed to setup
179  user malloc function pointers if it is inconvenient to use
180  the alternative constructor.
181  To be used when the user wishes
182  to provide memory allocation and free routines rather than
183  use new and delete.
184  Constructs an empty list
185 ARGUMENTS : pUserMalloc pointer to user supplied function to be called to
186  allocate memory for list nodes
187  pUserFree pointer to user supplied function to be called to
188  free memory for list nodes
189  pUserItemFree pointer to user supplied function to be called to
190  free up list item memory if deleting data from list
191  userData optional 32 bit value that will be passed to the user
192  alloc and free routines.
193 RETURN : None
194 NOTES :
195 ---------------------------------------------------------------------------*/
196  void setUserMallocFunctions( void* (*pUserMalloc)( size_t, uint32 ),
197  void (*pUserFree)( void*, uint32 ),
198  void (*pUserItemFree)( void*, uint32 ),
199  uint32 userData = 0 );
200 #endif
201 
202  protected:
203 
204 /*********************************************************************
205  Protected Methods for L I S T
206 *********************************************************************/
207 
208 /*---------------------------------------------------------------------------
209 FUNCTION : List A D D
210 DESCRIPTION : Method to add an item onto the end of a list
211 ARGUMENTS : void * data
212  Pointer to data item. In derived classes this is
213  overridden by method specifying a pointer to the object
214  type to be added.
215  Note that item is NOT copied but is merely linked into
216  the list.
217 RETURN : statusCode OK, or FAIL if unable to complete operation.
218  Failure can only be due to lack of heap memory.
219 NOTES :
220 ---------------------------------------------------------------------------*/
221  statusCode add ( void *data );
222 
223 /*---------------------------------------------------------------------------
224 FUNCTION : List A D D F R O N T
225 DESCRIPTION : Method to add an item onto the front of a list
226 ARGUMENTS : void * data
227  Pointer to data item. In derived classes this is
228  overridden by method specifying a pointer to the object
229  type to be added.
230  Note that item is NOT copied but is merely linked into
231  the list.
232 RETURN : statusCode OK, or FAIL if unable to complete operation.
233  Failure can only be due to lack of heap memory.
234 NOTES :
235 ---------------------------------------------------------------------------*/
236  statusCode addFront ( void *data );
237 
238 /*---------------------------------------------------------------------------
239 FUNCTION : List D E S T R U C T I T E M
240 DESCRIPTION : Pure virtual method to destroy an item in the list
241 ARGUMENTS : void * itemPtr
242  Pointer to item to be destroyed.
243 RETURN : None
244 NOTES : This is declared here as a pure virtual function which must
245  be supplied by the derived class .
246  See strlists.h and .cpp for example of this function.
247 ---------------------------------------------------------------------------*/
248  virtual void destructItem ( void * itemPtr ) = 0 ;
249 
250 /*---------------------------------------------------------------------------
251 FUNCTION : List I T E R A T E
252 DESCRIPTION : Method to perform a specified function on each item in a list.
253 
254 ARGUMENTS : func - Pointer to a function taking a pointer to the item
255  ie to a void in this base class
256 NOTES : In derived classes this is overridden by method specifying a
257  pointer to a function taking a pointer to the object type in
258  the list.
259 ---------------------------------------------------------------------------*/
260  void iterate ( void (*func)(void *) );
261 
262 #if defined LISTS_USER_MALLOC
263  bool m_bUseUserMalloc; // indicates whether to use user supplied
264  // malloc and free instead of new and delete
265  // user supplied malloc to be used for listnode malloc
266  void* (*m_pUserMalloc)( size_t, uint32 );
267  // user supplied free to be used for listnode free
268  void (*m_pUserFree)( void*, uint32 );
269  // user supplied free to be used for item free
270  void (*m_pUserItemFree)( void*, uint32 );
271  // user supplied value to be passed to user malloc and free functions
272  uint32 m_userData;
273 #endif
274 
275  private:
276  // both below NULL if empty list
277  ListNode *firstnode; // pointer to first node in list
278  ListNode *lastnode; // pointer to last node in list
279 
280  uint32 count; // number of items currently in list
281 
282  // Copy constructor and assignment operator declared private
283  // and not defined to prevent compiler from generating bitwise
284  // copiers.
285  List( const List& );
286  List& operator=( const List& );
287 
288 
289 }; // class List
290 
291 
292 
293 
294 /* ##########################################################################
295 CLASS : L I S T W A L K E R
296 DESCRIPTION : This class provides an object which can walk up and down a
297  List to allow access to the list items. It also allows
298  selective removal of items, and insertion into the list.
299  See strlists.h and .cpp for example of how to derive a
300  ThingyListWalker.
301  A list may have several walkers active in it at once provided
302  they are all just looking. If the list is being modified then
303  only one should be active. This implementation does not
304  prevent the user from doing this however.
305 ########################################################################### */
306 
308 #if defined ISE_PNL_MEMORY
309  : public CpnlMem
310 #endif
311 {
312  public:
313 
314 /*********************************************************************
315  Public Methods for L I S T W A L K E R
316 *********************************************************************/
317 
318 /*---------------------------------------------------------------------------
319 FUNCTION : L I S T W A L K E R constructor
320 DESCRIPTION : Constructs a list walker for a given list
321 ARGUMENTS : List& lst list to be walked
322 RETURN : None
323 NOTES :
324 ---------------------------------------------------------------------------*/
325  ListWalker( List& lst ) ;
326 
327  // No destructor necessary
328 
329 /*---------------------------------------------------------------------------
330 FUNCTION : ListWalker C U R R E N T
331 DESCRIPTION : Method to return pointer to current item in list
332 ARGUMENTS : none
333 RETURN : Pointer to current item. This is NULL if list empty or
334  currently off the front of the list
335 NOTES :
336 ---------------------------------------------------------------------------*/
337  void *current();
338 
339 /*---------------------------------------------------------------------------
340 FUNCTION : ListWalker D E L E T E C U R R E N T
341 DESCRIPTION : Method to delete the current item in list
342 ARGUMENTS : None
343 RETURN : None
344 NOTES : This calls List::destructItem to release memory for the item
345  being deleted. The list is shuffled up so that the next item
346  in the list becomes the current one. If the last item in the
347  list is deleted then the walker goes back to off the top of
348  the list.
349 ---------------------------------------------------------------------------*/
350  void deleteCurrent();
351 
352 /*---------------------------------------------------------------------------
353 FUNCTION : ListWalker E X T R A C T C U R R E N T
354 DESCRIPTION : Method to extract the current item in list
355 ARGUMENTS : None
356 RETURN : Pointer to item extracted, or NULL if list empty or walker
357  off end of list
358 NOTES : Removes the current item in the list. Shuffles the list up
359  so that walker points to next one in list if any.
360  If last one is deleted then goes back to off top of list
361  Responsibility for deletion of the item itself now resides with
362  the user.
363 ---------------------------------------------------------------------------*/
364  void *extractCurrent();
365 
366 /*---------------------------------------------------------------------------
367 FUNCTION : ListWalker F I R S T
368 DESCRIPTION : Method to position walker at first item in list.
369 ARGUMENTS : None
370 RETURN : Pointer to data item, or NULL if list empty
371 NOTES :
372 ---------------------------------------------------------------------------*/
373  void *first();
374 
375 /*---------------------------------------------------------------------------
376 FUNCTION : ListWalker I N S E R T H E R E
377 DESCRIPTION : Method to insert an item into list after current item
378 ARGUMENTS : void * data
379  Pointer to data item. In derived classes this is
380  overridden by method specifying a pointer to the object
381  type to be added.
382  Note that item is NOT copied but is merely linked into
383  the list.
384 RETURN : statusCode OK, or FAIL if unable to complete operation.
385  Failure can only be due to lack of heap memory.
386 NOTES : The walker is NOT moved on to the new item
387 ---------------------------------------------------------------------------*/
388  statusCode insertHere ( void *data );
389 
390 /*---------------------------------------------------------------------------
391 FUNCTION : ListWalker L A S T
392 DESCRIPTION : Method to position walker at last item in list.
393 ARGUMENTS : None
394 RETURN : Pointer to data item, or NULL if list empty
395 NOTES :
396 ---------------------------------------------------------------------------*/
397  void *last();
398 
399 /*---------------------------------------------------------------------------
400 FUNCTION : ListWalker L O C A T E
401 DESCRIPTION : Method to position walker at a member item.
402 ARGUMENTS : Data item address.
403 RETURN : If item located, pointer to it as passed in argument.
404  NULL if item not in list.
405 NOTES : If item located, walker positioned at item, otherwise
406  left unchanged.
407 ---------------------------------------------------------------------------*/
408  void *locate( void *itemPtr );
409 
410 /*---------------------------------------------------------------------------
411 FUNCTION : ListWalker N E X T
412 DESCRIPTION : Method to position walker at next item in list.
413 ARGUMENTS : None
414 RETURN : Pointer to data item, or NULL if list empty.
415  If already at end of list, the walker is left at last item and
416  NULL is returned.
417 NOTES :
418 ---------------------------------------------------------------------------*/
419  void *next();
420 
421 /*---------------------------------------------------------------------------
422 FUNCTION : ListWalker P R E V I O U S
423 DESCRIPTION : Method to position walker at previous item in list.
424 ARGUMENTS : None
425 RETURN : Pointer to data item, or NULL if list empty.
426  If walker is at first item in list it is moved off the top and
427  NULL is returned.
428  If it is already off top of list no action is taken and NULL is
429  returned.
430 NOTES :
431 ---------------------------------------------------------------------------*/
432  void *previous();
433 
434 /*---------------------------------------------------------------------------
435 FUNCTION : ListWalker T O P
436 DESCRIPTION : Method to position walker of the top of the list.
437 ARGUMENTS : None
438 RETURN : None
439 NOTES : A call of next() after top() returns the first item in list
440 ---------------------------------------------------------------------------*/
441  void top();
442 
443  private:
444  List *thisList;
445  ListNode *currnode;
446 
447 
448 }; // class ListWalker
449 
450 
451 /*********************************************************************
452  Inline public Methods for L I S T
453 *********************************************************************/
454 
455 /*---------------------------------------------------------------------------
456 FUNCTION : List I T E M C O U N T
457 DESCRIPTION : Method returning number of items currently on list
458 
459 ARGUMENTS : None
460 RETURN : Number of items
461 NOTES :
462 ---------------------------------------------------------------------------*/
463 inline uint32 List::itemCount()
464 {
465  return count;
466 }
467 
468 
469 
470 /*********************************************************************
471  Inline public Methods for L I S T W A L K E R
472 *********************************************************************/
473 
474 
475 /*---------------------------------------------------------------------------
476 FUNCTION : ListWalker T O P
477 DESCRIPTION : Method to position walker of the top of the list.
478 ARGUMENTS : None
479 RETURN : None
480 NOTES : A call of next() after top() returns the first item in list
481 ---------------------------------------------------------------------------*/
482 inline void ListWalker::top()
483 {
484  // only necessary to set currnode to NULL indicating not pointing to
485  // any valid node
486  currnode = NULL;
487 } // ListWalker::top()
488 
489 
490 #endif
Definition: listn.h:59
Definition: lists.h:307
Definition: lists.h:91