source: SVN/cambria/redboot/packages/infra/current/include/clist.hxx @ 1

Last change on this file since 1 was 1, checked in by Tim Harvey, 2 years ago

restored latest version of files from server backup

Signed-off-by: Tim Harvey <tharvey@…>

File size: 10.2 KB
Line 
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
91class Cyg_DNode
92{
93    friend class Cyg_CList;
94   
95    Cyg_DNode   *next;
96    Cyg_DNode   *prev;
97
98public:
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
157class Cyg_CList
158{
159    Cyg_DNode   *head;                  // list head pointer
160
161public:
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
305template <class T> class Cyg_CList_T
306    : public Cyg_CList
307{
308public:
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
348template <class T> class Cyg_DNode_T
349    : public Cyg_DNode
350{
351public:
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
Note: See TracBrowser for help on using the repository browser.