packages/infra/v2_0/include/clist.hxx

   1 #ifndef CYGONCE_INFRA_CLIST_HXX
   2 #define CYGONCE_INFRA_CLIST_HXX
   3
   4 //==========================================================================
   5 //
   6 //      clist.hxx
   7 //
   8 //      Standard types, and some useful coding macros.
   9 //
  10 //==========================================================================
  11 //####ECOSGPLCOPYRIGHTBEGIN####
  12 // -------------------------------------------
  13 // This file is part of eCos, the Embedded Configurable Operating System.
  14 // Copyright (C) 1998, 1999, 2000, 2001, 2002 Red Hat, Inc.
  15 //
  16 // eCos is free software; you can redistribute it and/or modify it under
  17 // the terms of the GNU General Public License as published by the Free
  18 // Software Foundation; either version 2 or (at your option) any later version.
  19 //
  20 // eCos is distributed in the hope that it will be useful, but WITHOUT ANY
  21 // WARRANTY; without even the implied warranty of MERCHANTABILITY or
  22 // FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  23 // for more details.
  24 //
  25 // You should have received a copy of the GNU General Public License along
  26 // with eCos; if not, write to the Free Software Foundation, Inc.,
  27 // 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.
  28 //
  29 // As a special exception, if other files instantiate templates or use macros
  30 // or inline functions from this file, or you compile this file and link it
  31 // with other works to produce a work based on this file, this file does not
  32 // by itself cause the resulting work to be covered by the GNU General Public
  33 // License. However the source code for this file must still be made available
  34 // in accordance with section (3) of the GNU General Public License.
  35 //
  36 // This exception does not invalidate any other reasons why a work based on
  37 // this file might be covered by the GNU General Public License.
  38 //
  39 // Alternative licenses for eCos may be arranged by contacting Red Hat, Inc.
  40 // at http://sources.redhat.com/ecos/ecos-license/
  41 // -------------------------------------------
  42 //####ECOSGPLCOPYRIGHTEND####
  43 //==========================================================================
  44 //#####DESCRIPTIONBEGIN####
  45 //
  46 // Author(s):     nickg
  47 // Contributors:  nickg
  48 // Date:        2000-11-08
  49 // Purpose:     Simple circular list implementation
  50 // Description: A simple implementation of circular lists.
  51 // Usage:       #include "cyg/infra/clist.hxx"
  52 //              ...
  53 //
  54 //####DESCRIPTIONEND####
  55 //
  56 //==========================================================================
  57
  58 #include <cyg/infra/cyg_type.h>
  59
  60 // -------------------------------------------------------------------------
  61 // Class and structure conversion macros.
  62 // CYG_CLASSFROMFIELD translates a pointer to a field of a struct or
  63 // class into a pointer to the class.
  64 // CYG_OFFSETOFBASE yields the offset of a base class of a derived
  65 // class.
  66 // CYG_CLASSFROMBASE translates a pointer to a base class into a pointer
  67 // to a selected derived class. The base class object _must_ be part of
  68 // the specified derived class. This is essentially a poor mans version
  69 // of the RTTI dynamic_cast operator.
  70 // Caveat: These macros do not work for virtual base classes.
  71
  72 // Note: These definitions are exact duplicates of definitions in
  73 // ktypes.h. If either definition is changed, the other should be too
  74 // to avoid compiler messages.
  75
  76 #define CYG_CLASSFROMFIELD(_type_,_member_,_ptr_)\
  77     ((_type_ *)((char *)(_ptr_)-((char *)&(((_type_ *)0)->_member_))))
  78
  79 #define CYG_OFFSETOFBASE(_type_,_base_)\
  80     ((char *)((_base_ *)((_type_ *)4)) - (char *)4)
  81
  82 # define CYG_CLASSFROMBASE(_class_,_base_,_ptr_)\
  83     ((_class_ *)((char *)(_ptr_) - CYG_OFFSETOFBASE(_class_,_base_)))
  84
  85
  86 // -------------------------------------------------------------------------
  87 // Cyg_DNode class.
  88 // This simply represents a double linked node that is intended to
  89 // be a base member of the class that is being managed.
  90
  91 class Cyg_DNode
  92 {
  93     friend class Cyg_CList;
  94
  95     Cyg_DNode   *next;
  96     Cyg_DNode   *prev;
  97
  98 public:
  99
 100     Cyg_DNode()
 101     {
 102         // Initialize pointers to point here
 103         next = prev = this;
 104     };
 105
 106     // Accessor and test functions
 107     Cyg_DNode *get_next() { return next; };
 108     Cyg_DNode *get_prev() { return prev; };
 109     cyg_bool  in_list() { return next != this; };
 110
 111     // Insert a node into the list before this one,
 112     // so that it becomes this nodes predecessor in
 113     // the list.
 114     void insert( Cyg_DNode *node )
 115     {
 116         node->next = this;
 117         node->prev = prev;
 118         prev->next = node;
 119         prev = node;
 120     };
 121
 122     // Append a node after this one so that it become
 123     // this nodes sucessor in the list.
 124     void append( Cyg_DNode *node )
 125     {
 126         node->prev = this;
 127         node->next = next;
 128         next->prev = node;
 129         next = node;
 130     };
 131
 132     // Unlink this node from it's list. It is safe to apply this to an
 133     // already unlinked node.
 134     void unlink()
 135     {
 136         next->prev = prev;
 137         prev->next = next;
 138         next = prev = this;
 139     };
 140
 141     ~Cyg_DNode()
 142     {
 143         // If this node is still linked, unlink it.
 144         if( next != this )
 145             unlink();
 146     };
 147
 148 };
 149
 150 // -------------------------------------------------------------------------
 151 // Cyg_CList class.
 152
 153 // This is a simple class that manages a circular list of DNodes. This
 154 // object points to the head of the list and provides functions to
 155 // manipulate the head and tail of the list.
 156
 157 class Cyg_CList
 158 {
 159     Cyg_DNode   *head;                  // list head pointer
 160
 161 public:
 162
 163     Cyg_CList()
 164     {
 165         head = NULL;
 166     };
 167
 168     // Accessor and test functions
 169     Cyg_DNode *get_head() { return head; };
 170     Cyg_DNode *get_tail() { return head?head->prev:NULL; };
 171     cyg_bool empty() { return head == NULL; };
 172
 173     // Add a node at the head of the list
 174     void add_head( Cyg_DNode *node )
 175     {
 176         if( head == NULL )
 177             head = node;
 178         else
 179         {
 180             head->insert( node );
 181             head = node;
 182         }
 183     };
 184
 185     // Remove the node at the head of the list
 186     Cyg_DNode *rem_head()
 187     {
 188         Cyg_DNode *node = head;
 189         if( node != NULL )
 190         {
 191             // There is a node available
 192             Cyg_DNode *next = node->next;
 193             if( next == node )
 194             {
 195                 // Only node on list
 196                 head = NULL;
 197             }
 198             else
 199             {
 200                 // remove head node and move head to next.
 201                 node->unlink();
 202                 head = next;
 203             }
 204         }
 205         return node;
 206     };
 207
 208
 209     // Add a node at the tail of the list
 210     void add_tail( Cyg_DNode *node )
 211     {
 212         if( head == NULL )
 213             head = node;
 214         else
 215             head->insert( node );
 216     };
 217
 218     // Remove the node at the tail of the list
 219     Cyg_DNode *rem_tail()
 220     {
 221         if( head == NULL )
 222             return NULL;
 223
 224         Cyg_DNode *node = head->prev;
 225
 226         if( node == head )
 227             head = NULL;
 228         else node->unlink();
 229
 230         return node;
 231     };
 232
 233     // Merge the supplied list into this one, at the tail.
 234     void merge( Cyg_CList& list )
 235     {
 236         if( list.head == NULL )
 237             return;                     // Nothing to do
 238         else if( head == NULL )
 239             head = list.head;           // this is empty, just move it
 240         else
 241         {
 242             // We have a real merge to do. Adjust the pointers
 243             // on the two lists so that they become one.
 244
 245             Cyg_DNode *lh = list.head;
 246             Cyg_DNode *lt = lh->prev;
 247             Cyg_DNode *tail = head->prev;
 248
 249             head->prev = lt;
 250             lt->next = head;
 251             tail->next = lh;
 252             lh->prev = tail;
 253         }
 254         list.head = NULL;
 255     };
 256
 257     // General removal. Deals with what happend if this is only
 258     // object on list, or is the head.
 259     void remove( Cyg_DNode *node )
 260     {
 261         if( node == head )
 262             rem_head();
 263         else node->unlink();
 264     };
 265
 266     // Rotation - move the head to the next node in the list.
 267     void rotate()
 268     {
 269         if( head )
 270             head = head->next;
 271     };
 272
 273     // Move a node to the head of the list. Assumes that the
 274     // node is in this list.
 275     void to_head( Cyg_DNode *node )
 276     {
 277         head = node;
 278     };
 279
 280     // Insert a node before one in this list, and deal with what
 281     // happens if the node happens to be at the head of the list.
 282     void insert( Cyg_DNode *list_node, Cyg_DNode *node )
 283     {
 284         if( list_node == head )
 285         {
 286             head->insert( node );
 287             head = node;
 288         }
 289         else list_node->insert( node );
 290     };
 291
 292     ~Cyg_CList()
 293     {
 294         while( head != NULL )
 295             rem_head();
 296     };
 297
 298 };
 299
 300 // -------------------------------------------------------------------------
 301 // Cyg_CList_T
 302 // Template class that allows us to make use of the CList class in a
 303 // type-specific way.
 304
 305 template <class T> class Cyg_CList_T
 306     : public Cyg_CList
 307 {
 308 public:
 309
 310     Cyg_CList_T() {};
 311     ~Cyg_CList_T() {};
 312
 313     T *get_head()
 314     {
 315         Cyg_DNode *node = Cyg_CList::get_head();
 316         if( node ) return CYG_CLASSFROMBASE( T, Cyg_DNode, node );
 317         return NULL;
 318     };
 319     T *get_tail()
 320     {
 321         Cyg_DNode *node = Cyg_CList::get_tail();
 322         if( node ) return CYG_CLASSFROMBASE( T, Cyg_DNode, node );
 323         return NULL;
 324     };
 325
 326     T *rem_head()
 327     {
 328         Cyg_DNode *node = Cyg_CList::rem_head();
 329         if( node ) return CYG_CLASSFROMBASE( T, Cyg_DNode, node );
 330         return NULL;
 331     };
 332
 333     T *rem_tail()
 334     {
 335         Cyg_DNode *node = Cyg_CList::rem_tail();
 336         if( node ) return CYG_CLASSFROMBASE( T, Cyg_DNode, node );
 337         return NULL;
 338     };
 339
 340     // The rest just default to the Cyg_CList class operations.
 341 };
 342
 343 // -------------------------------------------------------------------------
 344 // Cyg_DNode_T
 345 // Template class that allows us to make use of the DNode class in a
 346 // type-specific way.
 347
 348 template <class T> class Cyg_DNode_T
 349     : public Cyg_DNode
 350 {
 351 public:
 352
 353     Cyg_DNode_T() {};
 354     ~Cyg_DNode_T() {};
 355
 356     T *get_next() { return CYG_CLASSFROMBASE( T, Cyg_DNode, Cyg_DNode::get_next() ); };
 357     T *get_prev() { return CYG_CLASSFROMBASE( T, Cyg_DNode, Cyg_DNode::get_prev() ); };
 358
 359     // The rest just default to the Cyg_DNode class operations.
 360 };
 361
 362 // -------------------------------------------------------------------------
 363 #endif // CYGONCE_INFRA_CLIST_HXX multiple inclusion protection
 364 // EOF clist.hxx
 365