home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c221 / 6.ddi / MWHC.006 / M1 < prev    next >
Encoding:
Text File  |  1992-06-07  |  5.3 KB  |  171 lines
  1. #ifndef  __RWISLIST_H__
  2. #define  __RWISLIST_H__
  3. pragma push_align_members(64);
  4.  
  5. /*
  6.  * RWIsvSlist: An intrusive singly-linked list.
  7.  *
  8.  * $Header:   E:/vcs/rw/islist.h_v   1.0   11 Mar 1992 14:10:44   KEFFER  $
  9.  *
  10.  ****************************************************************************
  11.  *
  12.  * Rogue Wave 
  13.  * P.O. Box 2328
  14.  * Corvallis, OR 97339
  15.  * Voice: (503) 754-3010    FAX: (503) 757-6650
  16.  *
  17.  * Copyright (C) 1989, 1990, 1991, 1992. This software is subject to copyright 
  18.  * protection under the laws of the United States and other countries.
  19.  *
  20.  ***************************************************************************
  21.  *
  22.  * See Stroustrup II, Section 8.3.1 for a guide to intrusive lists.
  23.  *
  24.  ***************************************************************************
  25.  *
  26.  * $Log:   E:/vcs/rw/islist.h_v  $
  27.  * 
  28.  *    Rev 1.0   11 Mar 1992 14:10:44   KEFFER
  29.  * Initial revision.
  30.  * 
  31.  */
  32.  
  33. #include "rw/islink.h"
  34.  
  35. /****************************************************************
  36.  *                                *
  37.  *        Declarations for RWIsvSlist            *
  38.  *                                *
  39.  ****************************************************************/
  40.  
  41. class RWExport RWIsvSlist {
  42. friend class RWExport RWIsvSlistIterator;
  43. friend class RWExport RWIsvDlistIterator;
  44.  
  45. protected:
  46.  
  47.   union RWExport {
  48.     RWIsvSlink*        _lastSlink;    // _lastSlink->_nextSlink is head of list
  49.     RWIsvDlink*        _lastDlink;
  50.   };
  51.   unsigned        _nitems;    // Number of entries in the list
  52.  
  53. protected:
  54.  
  55.   RWIsvSlink*        findLeft(const RWIsvSlink*) const;
  56.   void            insertAfterLink(RWIsvSlink*,RWIsvSlink*);
  57.   RWIsvSlink*        removeRight(RWIsvSlink*);  // Remove and return link after the argument
  58.  
  59. private:
  60.  
  61.   /* Copies of intrusive lists are dangerous.  The following two functions
  62.      are private to disallow copies. */
  63.   RWIsvSlist(const RWIsvSlist&);
  64.   void            operator=(const RWIsvSlist& s);
  65.  
  66. public:
  67.  
  68.   RWIsvSlist()        {_lastSlink=rwnil; _nitems=0;}
  69.   RWIsvSlist(RWIsvSlink* a);
  70.   ~RWIsvSlist()        {clear();}
  71.  
  72.   /********************* Member functions **************************/
  73.   void            append(RWIsvSlink* a)    {insertAfterLink(_lastSlink, a);}
  74.   RWIsvSlink*        at(int) const;        // Return nil if out of range
  75.   void            clear();
  76.   RWBoolean        containsReference(const RWIsvSlink*) const;
  77.   unsigned        entries() const    {return _nitems;}
  78.   RWIsvSlink*        first() const;        // Return link at head of list
  79.   RWIsvSlink*        get()            {return removeRight(_lastSlink);}
  80.   void            insert(RWIsvSlink* a)    {append(a);}
  81.   void            insertAfter(int, RWIsvSlink*);
  82.   void            insertAt(int, RWIsvSlink*);
  83.   RWBoolean        isEmpty() const;
  84.   RWIsvSlink*        last() const        {return _lastSlink;}
  85.   unsigned        occurrencesOfReference(const RWIsvSlink*) const;
  86.   void            prepend(RWIsvSlink*);
  87.   RWIsvSlink*        removeAt(int);        // Relatively slow
  88.   RWIsvSlink*         removeFirst()        {return removeRight(_lastSlink);}
  89.   RWIsvSlink*        removeLast();        // Remove and return last link (slow)
  90.   RWIsvSlink*        removeReference(const RWIsvSlink* a);    // Return and remove the link with address "a"
  91. };
  92.  
  93.  
  94.  
  95. /****************************************************************
  96.  *                                *
  97.  *        Declarations for RWIsvSlistIterator        *
  98.  *                                *
  99.  ****************************************************************/
  100.  
  101. // Iterator for singly linked list:
  102.  
  103. class RWExport RWIsvSlistIterator {
  104.  
  105.   // Disallow postfix increment.  Unless we hide it, some compilers will
  106.   // substitute the prefix increment operator in its place.
  107.   RWBoolean        operator++(int);
  108.  
  109. protected:
  110.  
  111.   union {
  112.     RWIsvSlist*        _slist;        // The list over which we are iterating
  113.     RWIsvDlist*        _dlist;
  114.   };
  115.   union {
  116.     RWIsvSlink*        _shere;        // Iterator position
  117.     RWIsvDlink*        _dhere;
  118.   };
  119.  
  120. protected:
  121.  
  122.   void            resetHere();
  123.   RWIsvSlink*        removeRight(RWIsvSlink*);    // Remove link to right of given link
  124.  
  125. public:
  126.  
  127.   // Constructor: starts with iterator positioned at last link.
  128.   RWIsvSlistIterator(RWIsvSlist& s); 
  129.  
  130.   // Operators:
  131.   RWBoolean        operator++();        // Advance iterator one link and test.
  132.   RWBoolean        operator+=(int n);    // Advance iterator n links and test.
  133.   RWIsvSlink*        operator()();        // Advance, test, and return.  For lateral compatibility
  134.  
  135.   RWIsvSlist*        container() const    {return _slist;}
  136.   RWIsvSlink*        findNextReference(const RWIsvSlink*);
  137.   void            insertAfterPoint(RWIsvSlink*);// Insert item after position.
  138.   RWIsvSlink*        key() const;        // Return current item
  139.   RWIsvSlink*         remove();        // Remove current item (slow)
  140.   RWIsvSlink*        removeNextReference(const RWIsvSlink*);
  141.   void            reset();
  142.   void            reset(RWIsvSlist&);    // Reset container to be interated over.
  143. };
  144.  
  145. /************************ RWIsvSlist inlines ******************************/
  146.  
  147. inline RWBoolean
  148. RWIsvSlist::isEmpty() const {return _lastSlink==rwnil;}
  149.  
  150. // Return link at head of list
  151. inline RWIsvSlink* 
  152. RWIsvSlist::first() const
  153. { return _lastSlink==rwnil ? rwnil : _lastSlink->_nextSlink; }
  154.  
  155. /*********************** RWIsvSlistIterator inlines *****************************/
  156.  
  157. // Reset iterator: position it to the "last" link.
  158. // This will be nil if the list is empty.
  159. inline void
  160. RWIsvSlistIterator::reset()
  161. { _shere = _slist->_lastSlink; }
  162.  
  163. // Constructor: start with iterator positioned at last link
  164. inline
  165. RWIsvSlistIterator::RWIsvSlistIterator(RWIsvSlist& s) :
  166.   _slist(&s)
  167. { reset(); } 
  168.  
  169. pragma pop_align_members();
  170. #endif  /* __RWISLIST_H__ */
  171.