versadac  1
versadac - Scalable Recorder Firmware
linklist.h
1 /* $Id: linklist.h 4938 2006-10-10 14:20:18Z martinto $ */
2 /*
3  *
4  * Revision 2.1 1997/07/10 16:24:12 davec
5  * DEV1196:DCN001 moved source to CVS
6  *
7  *
8  * Rev 1.1.1.0 24 Jan 1996 15:07:40 PAULT
9  * Branched
10  *
11  * Rev 1.1 24 Jan 1996 12:17:02 PAULT
12  * Consolidated 4100 code merged to trunk
13  *
14  * Rev 1.0.2.0 01 Jun 1995 14:25:44 DAVEH
15  * Branched
16  *
17  * Rev 1.0 12 Apr 1995 17:20:40 COLINL
18  * Initial revision.
19 */
20 /*****************************************************************************
21 FILE : L I N K L I S T . H
22 VERSION : %I%
23 AUTHOR : Colin Law
24 SYSTEM : Turbo C++
25 DESCRIPTION : Header file for linked list template
26 
27 This file provides the template for generating linked lists of objects.
28 Two template classes are provided. LinkedList provides for items allocated
29 on the heap, which are to become the property of the list and are to be
30 deleted when the list is deleted, or the list is instructed to delete an item.
31 LinkedListOfStatics is for use where the items are not on the heap or are to
32 be considered the property of the list user rather than the list. This list
33 will never delete items pointed to.
34 The list templates provide the methods for creating and destroying the
35 LinkedList.
36 The LinkedListWalker template allows movement through the list, insertion of
37 items into 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. The classes generated with
41 these templates assume that the objects exist in dynamically allocated heap
42 space, and that they can be deleted using the delete operator when the list
43 is destroyed.
44 Therefore it is important to ensure that all objects are generated in heap
45 memory before being added to the list. The user must not then delete the
46 object without extracting it from the list again. Also an object should not
47 be put on more than one list at a time.
48 
49 *****************************************************************************/
50 
51 #if !defined(__LINKLIST_H) // skip file if already included
52 
53 #define __LINKLIST_H
54 
55 #include "stdtypes.h"
56 
57 #if !defined __LISTS_H
58  #include "lists.h"
59 #endif
60 
61 
62 /* ##########################################################################
63 CLASS : L I N K E D L I S T
64 DESCRIPTION : This class provides the basic methods for creating and
65  destroying a linked list. Methods are provided for
66  adding items into the front and end of the list. See
67  LinkedListWalker for methods to access the list in more
68  sophisticated ways.
69  This class is derived from List but all accessible methods
70  are described below.
71 
72 EXAMPLE:
73 
74 class froglet
75 {
76  ... ;
77 };
78 
79 LinkedList<froglet> mylist;
80 LinkedListWalker<froglet> mywalker( mylist );
81  ...
82  froglet *frogPtr = new froglet;
83  mylist.add(frogPtr);
84  ...
85  mywalker.top();
86  while( (frogPtr = mywalker.next()) != NULL )
87  {
88  ...
89  }
90 
91 ########################################################################### */
92 
93 template <class T> class LinkedList : public List
94 {
95  public:
96 
97 /*********************************************************************
98  public Methods for L I N K E D L I S T
99 *********************************************************************/
100 
101 /*---------------------------------------------------------------------------
102 FUNCTION : LinkedList C O N S T R U C T O R
103 DESCRIPTION : Constructs an empty list
104 ARGUMENTS : None
105 RETURN : None
106 NOTES :
107 ---------------------------------------------------------------------------*/
108  LinkedList();
109 
110 #if defined LISTS_USER_MALLOC
111 /*---------------------------------------------------------------------------
112 FUNCTION : LinkedList constructor
113 DESCRIPTION : Alternative constructor to be used when the user wishes
114  to provide memory allocation and free routines rather than
115  use new and delete.
116  Constructs an empty list
117 ARGUMENTS : pUserMalloc pointer to user supplied function to be called to
118  allocate memory for list nodes
119  pUserFree pointer to user supplied function to be called to
120  free memory for list nodes
121  pUserItemFree pointer to user supplied function to be called to
122  free up list item memory if deleting data from list
123  userData optional 32 bit value that will be passed to the user
124  alloc and free routines.
125 RETURN : None
126 NOTES :
127 ---------------------------------------------------------------------------*/
128  LinkedList( void* (*pUserMalloc)( size_t, uint32 ),
129  void (*pUserFree)( void*, uint32 ),
130  void (*pUserItemFree)( void*, uint32 ),
131  uint32 userData = 0);
132 #endif
133 
134 /*---------------------------------------------------------------------------
135 FUNCTION : LinkedList D E S T R U C T O R
136 DESCRIPTION : Destroys list
137 ARGUMENTS : None
138 RETURN : None
139 NOTES : None
140 ---------------------------------------------------------------------------*/
141  ~LinkedList()
142  {
143  clear();
144  }
145 
146 /*---------------------------------------------------------------------------
147 FUNCTION : LinkedList A D D
148 DESCRIPTION : Method to add an object onto the end of a list
149 ARGUMENTS : T * data
150  Pointer to object.
151  Note that object is NOT copied but is merely linked into
152  the list. It should normally be in heap memory.
153 RETURN : statusCode OK, or FAIL if unable to complete operation.
154  Failure can only be due to lack of heap memory.
155 NOTES :
156 ---------------------------------------------------------------------------*/
157  statusCode add ( T *data )
158  {
159  return List::add( data );
160  }
161 
162 /*---------------------------------------------------------------------------
163 FUNCTION : LinkedList A D D F R O N T
164 DESCRIPTION : Method to add a object onto the front of a list
165 ARGUMENTS : T * data
166  Pointer to object.
167  Note that object is NOT copied but is merely linked into
168  the list. It should normally be in heap memory.
169 RETURN : statusCode OK, or FAIL if unable to complete operation.
170  Failure can only be due to lack of heap memory.
171 NOTES :
172 ---------------------------------------------------------------------------*/
173  statusCode addFront ( T *data )
174  {
175  return List::addFront( data );
176  }
177 
178 /*---------------------------------------------------------------------------
179 FUNCTION : LinkedList C L E A R
180 DESCRIPTION : Method to empty a list, releasing dynamic memory.
181 
182 ARGUMENTS : None
183 RETURN : None
184 NOTES : Note that this calls destructItem for each item in the list.
185  As these will normally be dynamically allocated this function
186  destroys the items in the list. Any items required for further
187  use should be extracted before the list is cleared.
188  See also LinkedListOfStatics below which is a list for use
189  if the objects are not to be deleted by the list.
190 ---------------------------------------------------------------------------*/
191  // void clear(); Declaration not required as this is
192  // inherited as is from base class
193 
194 /*---------------------------------------------------------------------------
195 FUNCTION : LinkedList I T E R A T E
196 DESCRIPTION : Method to perform a specified function on each object in a list.
197 
198 ARGUMENTS : func - Pointer to a function taking a pointer to a object.
199  This is called for each object
200 NOTES : None
201 ---------------------------------------------------------------------------*/
202  void iterate ( void (*func)(T *) )
203  {
204  List::iterate( (void (*)(void *))func );
205  }
206 
207 #if defined LISTS_USER_MALLOC
208 /*---------------------------------------------------------------------------
209 FUNCTION : L I S T setUserMallocFunctions
210 DESCRIPTION : Service that may be used after the list is constructed to setup
211  user malloc function pointers if it is inconvenient to use
212  the alternative constructor.
213  To be used when the user wishes
214  to provide memory allocation and free routines rather than
215  use new and delete.
216  Constructs an empty list
217 ARGUMENTS : pUserMalloc pointer to user supplied function to be called to
218  allocate memory for list nodes
219  pUserFree pointer to user supplied function to be called to
220  free memory for list nodes
221  pUserItemFree pointer to user supplied function to be called to
222  free up list item memory if deleting data from list
223  userData optional 32 bit value that will be passed to the user
224  alloc and free routines.
225 RETURN : None
226 NOTES :
227 ---------------------------------------------------------------------------*/
228 // setUserMallocFunctions( void* (*pUserMalloc)( size_t, uint32 ),
229 // void (*pUserFree)( void*, uint32 ),
230 // void (*pUserItemFree)( void*, uint32 ),
231 // uint32 userData = 0 );
232 // Declaration above not required as provided by base class
233 #endif
234 
235 
236 /*********************************************************************
237  Protected Methods
238 *********************************************************************/
239 
240  protected:
241 
242 /*---------------------------------------------------------------------------
243 FUNCTION : LinkedList D E S T R U C T I T E M
244 DESCRIPTION : Method to destroy a object in the list
245 ARGUMENTS : void * itemPtr
246  Pointer to object to be destroyed.
247 RETURN : None
248 NOTES : This is declared to take a void pointer in order to correctly
249  overload the base class function. It is not necessary to
250  cast it in the function call.
251 ---------------------------------------------------------------------------*/
252  virtual void destructItem ( void * itemPtr )
253 #if defined __BORLANDC__
254  {
255 #if defined LISTS_USER_MALLOC
256  if ( m_bUseUserMalloc )
257  {
258  m_pUserItemFree( itemPtr );
259  }
260  else
261 #endif
262  {
263  delete (T *)itemPtr;
264  }
265  }
266 #else
267  ;
268 #endif
269 
270 
271  private:
272 
273 
274 }; // class LinkedList
275 
276 #if !CPP_EXTERNAL_TEMPLATES
277 #if !defined __BORLANDC__
278 // Only by separating out this definition do we end up with the correct
279 // delete being called.
280 template <class T> void LinkedList<T>::destructItem ( void * itemPtr )
281 {
282 #if defined LISTS_USER_MALLOC
283  if ( m_bUseUserMalloc )
284  {
285  m_pUserItemFree( itemPtr, m_userData );
286  }
287  else
288 #endif
289  {
290  delete (T *)itemPtr;
291  }
292 }
293 #endif
294 #endif
295 
296 
297 /* ##########################################################################
298 CLASS : L I S T W A L K E R
299 DESCRIPTION : This class provides an object which can walk up and down a
300  LinkedList to allow access to the list items. It also allows
301  selective removal of items, and insertion into the list.
302  A list may have several walkers active in it at once provided
303  they are all just looking. If the list is being modified then
304  only one should be active. This implementation does not
305  prevent the user from doing this however.
306 ########################################################################### */
307 
308 template <class T> class LinkedListWalker : public ListWalker
309 {
310  public:
311 
312 /*********************************************************************
313  Public Methods for L I S T W A L K E R
314 *********************************************************************/
315 
316 /*---------------------------------------------------------------------------
317 FUNCTION : LinkedListWalker C O N S T R U C T O R
318 DESCRIPTION : Constructs a list walker for a given list
319 ARGUMENTS : LinkedList& lst list to be walked
320 RETURN : None
321 NOTES :
322 ---------------------------------------------------------------------------*/
324 
325  // No destructor necessary
326 
327 /*---------------------------------------------------------------------------
328 FUNCTION : LinkedListWalker C U R R E N T
329 DESCRIPTION : Method to return pointer to current item in list
330 ARGUMENTS : none
331 RETURN : Pointer to current item. This is NULL if list empty or
332  currently off the front of the list
333 NOTES :
334 ---------------------------------------------------------------------------*/
335  T *current()
336  {
337  return (T *) ListWalker::current();
338  }
339 
340 /*---------------------------------------------------------------------------
341 FUNCTION : LinkedListWalker D E L E T E C U R R E N T
342 DESCRIPTION : Method to delete the current item in list
343 ARGUMENTS : None
344 RETURN : None
345 NOTES : This calls destructItem to release memory for the item
346  being deleted. The list is shuffled up so that the next item
347  in the list becomes the current one. If the last item in the
348  list is deleted then the walker goes back to off the top of
349  the list.
350 ---------------------------------------------------------------------------*/
351  // void deleteCurrent();
352  // declaration not required as inherited as is from base class.
353 
354 /*---------------------------------------------------------------------------
355 FUNCTION : LinkedListWalker E X T R A C T C U R R E N T
356 DESCRIPTION : Method to extract the current item in list
357 ARGUMENTS : None
358 RETURN : Pointer to item extracted, or NULL if list empty or walker
359  off end of list
360 NOTES : Removes the current item in the list. Shuffles the list up
361  so that walker points to next one in list if any.
362  If last one is deleted then goes back to off top of list
363  Responsibility for deletion of the item itself now resides with
364  the user.
365 ---------------------------------------------------------------------------*/
366  T *extractCurrent()
367  {
368  return (T *) ListWalker::extractCurrent();
369  }
370 
371 
372 /*---------------------------------------------------------------------------
373 FUNCTION : LinkedListWalker F I R S T
374 DESCRIPTION : Method to position walker at first item in list.
375 ARGUMENTS : None
376 RETURN : Pointer to data item, or NULL if list empty
377 NOTES :
378 ---------------------------------------------------------------------------*/
379  T *first()
380  {
381  return (T *)ListWalker::first();
382  }
383 
384 
385 /*---------------------------------------------------------------------------
386 FUNCTION : LinkedListWalker I N S E R T H E R E
387 DESCRIPTION : Method to insert a object into list after current object
388 ARGUMENTS : T * data Pointer to object
389  Note that item is NOT copied but is merely linked into
390  the list.
391 RETURN : statusCode OK, or FAIL if unable to complete operation.
392  Failure can only be due to lack of heap memory.
393 NOTES : The walker is NOT moved on to the new item
394 ---------------------------------------------------------------------------*/
395  statusCode insertHere ( T *ptr )
396  {
397  return ListWalker::insertHere( ptr );
398  }
399 
400 
401 /*---------------------------------------------------------------------------
402 FUNCTION : LinkedListWalker L A S T
403 DESCRIPTION : Method to position walker at last item in list.
404 ARGUMENTS : None
405 RETURN : Pointer to object, or NULL if list empty
406 NOTES :
407 ---------------------------------------------------------------------------*/
408  T *last()
409  {
410  return (T *)ListWalker::last();
411  }
412 
413 /*---------------------------------------------------------------------------
414 FUNCTION : ListWalker L O C A T E
415 DESCRIPTION : Method to position walker at a member item.
416 ARGUMENTS : Data item address.
417 RETURN : If item located, pointer to it as passed in argument.
418  NULL if item not in list.
419 NOTES : If item located, walker positioned at item, otherwise
420  left unchanged.
421 ---------------------------------------------------------------------------*/
422  T *locate( T *itemPtr )
423  {
424  return (T *)ListWalker::locate( itemPtr );
425  }
426 
427 
428 /*---------------------------------------------------------------------------
429 FUNCTION : LinkedListWalker N E X T
430 DESCRIPTION : Method to position walker at next object in list.
431 ARGUMENTS : None
432 RETURN : Pointer to object, or NULL if list empty.
433  If already at end of list, the walker is left at last item and
434  NULL is returned.
435 NOTES :
436 ---------------------------------------------------------------------------*/
437  T *next()
438  {
439  return (T *)ListWalker::next();
440  }
441 
442 
443 /*---------------------------------------------------------------------------
444 FUNCTION : LinkedListWalker P R E V I O U S
445 DESCRIPTION : Method to position walker at previous object in list.
446 ARGUMENTS : None
447 RETURN : Pointer to data item, or NULL if list empty.
448  If walker is at first item in list it is moved off the top and
449  NULL is returned.
450  If it is already off top of list no action is taken and NULL is
451  returned.
452 NOTES :
453 ---------------------------------------------------------------------------*/
454  T *previous()
455  {
456  return (T *)ListWalker::previous();
457  }
458 
459 
460 /*---------------------------------------------------------------------------
461 FUNCTION : LinkedListWalker T O P
462 DESCRIPTION : Method to position walker of the top of the list.
463 ARGUMENTS : None
464 RETURN : None
465 NOTES : A call of next() after top() returns the first item in list
466 ---------------------------------------------------------------------------*/
467  // void top();
468  // declaration not required as inherited as is from base class.
469 
470  private:
471 
472  // The methods below are declared here but never defined. This
473  // prevents the base class functions being used directly rather
474  // than through the public methods above. Direct use would
475  // disable the type checking on the pointer types.
476 
477  statusCode insertHere ( void *data );
478 
479 }; // class LinkedListWalker
480 
481 
482 /* ##########################################################################
483 CLASS : L I N K E D L I S T O F S T A T I C S
484 DESCRIPTION : This class provides the basic methods for creating and
485  destroying a linked list of items which are assumed by the list
486  not to be dynamically allocated. The implication of this is
487  that if the list is deleted or the user deletes an item from
488  the list then the list will not actually delete the item, but
489  just forgets about it, on the assumption that the user will
490  look after it.
491  All public methods are as for LinkedList documented above. A
492  LinkedListWalker can be used as for a LinkedList.
493 
494 ########################################################################### */
495 
496 template <class T> class LinkedListOfStatics : public LinkedList<T>
497 {
498  public:
499 
500 /*---------------------------------------------------------------------------
501 FUNCTION : LinkedList D E S T R U C T O R
502 DESCRIPTION : Destroys list
503 ARGUMENTS : None
504 RETURN : None
505 NOTES : None
506 ---------------------------------------------------------------------------*/
508  {
509  List::clear();
510  }
511 
512  // See LinkedList for public methods
513 
514  protected:
515 
516 /*---------------------------------------------------------------------------
517 FUNCTION : LinkedList D E S T R U C T I T E M
518 DESCRIPTION : Method to destroy a object in the list
519 ARGUMENTS : void * itemPtr
520  Pointer to object to be destroyed.
521 RETURN : None
522 NOTES : For this type of list this does nothing.
523  This is declared to take a void pointer in order to correctly
524  overload the base class function. It is not necessary to
525  cast it in the function call.
526 ---------------------------------------------------------------------------*/
527  virtual void destructItem ( void * itemPtr )
528  {}
529 };
530 
531 
532 /*---------------------------------------------------------------------------
533 FUNCTION : LinkedList C O N S T R U C T O R
534 DESCRIPTION : Constructs an empty list
535 ARGUMENTS : None
536 RETURN : None
537 NOTES :
538 ---------------------------------------------------------------------------*/
539 #if ( __BCPLUSPLUS__ >= 0x0320 )
540 // changed syntax in version 3.2 and above
541 template <class T>LinkedList<T>::LinkedList() : List()
542 {}
543 #else
544 
545 template <class T>
547 {}
548 #endif
549 
550 #if defined LISTS_USER_MALLOC
551 /*---------------------------------------------------------------------------
552 FUNCTION : L I S T constructor
553 DESCRIPTION : Alternative constructor to be used when the user wishes
554  to provide memory allocation and free routines rather than
555  use new and delete.
556  Constructs an empty list
557 ARGUMENTS : pUserMalloc pointer to user supplied function to be called to
558  allocate memory for list nodes
559  pUserFree pointer to user supplied function to be called to
560  free memory for list nodes
561  pUserItemFree pointer to user supplied function to be called to
562  free up list item memory if deleting data from list
563  userData a 32 bit value that will be passed to the user
564  alloc and free routines.
565 RETURN : None
566 NOTES :
567 ---------------------------------------------------------------------------*/
568 #if ( __BCPLUSPLUS__ >= 0x0320 )
569 template <class T>LinkedList<T>::LinkedList(
570  void* (*pUserMalloc)( size_t, uint32 ),
571  void (*pUserFree)( void*, uint32 ),
572  void (*pUserItemFree)( void*, uint32 ),
573  uint32 userData )
574  : List( pUserMalloc, pUserFree, pUserItemFree, userData )
575 {}
576 #else
577 template <class T>
579  void* (*pUserMalloc)( size_t, uint32 ),
580  void (*pUserFree)( void*, uint32 ),
581  void (*pUserItemFree)( void*, uint32 ),
582  uint32 userData )
583  : List( pUserMalloc, pUserFree, pUserItemFree, userData )
584 {}
585 #endif
586 #endif
587 
588 /*---------------------------------------------------------------------------
589 FUNCTION : LinkedListWalker C O N S T R U C T O R
590 DESCRIPTION : Constructs a list walker for a given list
591 ARGUMENTS : LinkedList& lst list to be walked
592 RETURN : None
593 NOTES :
594 ---------------------------------------------------------------------------*/
595 #if ( __BCPLUSPLUS__ >= 0x0320 )
596 // changed syntax in version 4.0 and above
597 template <class T>
599  : ListWalker( lst )
600 {}
601 #else
602 template <class T>
604  : ListWalker( lst )
605 {}
606 #endif
607 
608 #endif
Definition: linklist.h:496
Definition: lists.h:307
Definition: linklist.h:308
Definition: lists.h:91
Definition: linklist.h:93