HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_LinkList.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: Utility Library (C++)
7  *
8  * COMMENTS:
9  *
10  * WARNING: OLD CODE
11  *
12  * This class implements a doubly linked list that maintains
13  * a replacement list of nodes.
14  *
15  * This is maintained to support the stuff we don't want to change.
16  * New code should not use it.
17  *
18  */
19 
20 #ifndef __UT_LinkList_h__
21 #define __UT_LinkList_h__
22 
23 #include "UT_API.h"
24 #include "UT_Swap.h"
25 #include <iosfwd>
26 
28 public:
29  // Constructor and destructor:
30  UT_LinkNode() { predNode = succNode = 0; }
31  virtual ~UT_LinkNode();
32 
33  UT_LinkNode(const UT_LinkNode &) = delete;
34  UT_LinkNode &operator=(const UT_LinkNode &) = delete;
35 
36  // Query/set methods:
37  UT_LinkNode *&prev() { return predNode; }
38  UT_LinkNode *&next() { return succNode; }
39  const UT_LinkNode *prev() const { return predNode; }
40  const UT_LinkNode *next() const { return succNode; }
41 
42  // I/O friends:
43  friend std::ostream &operator<<(std::ostream &os, const UT_LinkNode &n)
44  {
45  n.outTo(os);
46  return os;
47  }
48 
49 protected:
50  // Query the name of this class:
51  virtual const char *className() const;
52 
53  // Our own I/O methods, so we can redefine them in derived classes:
54  virtual void outTo (std::ostream &os) const;
55 
56 private:
57  // Pointers to predecessor and successor respectively:
58  UT_LinkNode *predNode;
59  UT_LinkNode *succNode;
60 };
61 
62 
64 public:
65  // Trivial class constructor and destructor. The destructor
66  // deallocates every node in the active and replacement lists.
67  UT_LinkList() { first=last=stashHead=0; count=0; }
68  virtual ~UT_LinkList();
69 
70  void swap( UT_LinkList &other );
71 
72  // Reverse the order of the active nodes:
73  virtual void reverse();
74 
75  // Add nodes to the list, or delete them:
76  // append() appends a node, insert() inserts it at index 'where';
77  // remove() deletes the node from the list and leaves it intact;
78  // destroy() deletes the node from the list and deallocates it.
79  // If the node is not in the list, or if nodeIdx is invalid,
80  // both remove() and destroy() return 0. If the node is 0,
81  // remove() and destroy() will act upon the last element in the
82  // list. None of the functions below checks whether the node
83  // is or is not in the list at the time it is deleted or added.
84  // To check for existence, see inList().
85  void append (UT_LinkNode *node);
86  void insert (UT_LinkNode *node, int where);
87  // node is the node to insert, before and after are the node already
88  // in the list that you wish to insert before/after.
89  void insertBefore(UT_LinkNode *node, UT_LinkNode *before);
90  void insertAfter(UT_LinkNode *node, UT_LinkNode *after);
91 
92  UT_LinkNode *remove (UT_LinkNode *node = 0);
93  UT_LinkNode *remove (int nodeIdx);
94  void destroy(UT_LinkNode *node = 0);
95  void destroy(int nodeIdx);
96 
97  // Take a node from the active list and stash it into the
98  // replacement list. recall() performs the inverse procedure.
99  // If the node parameter is 0, stash and recall will act upon
100  // the last elemenent added to the respective list.
101  UT_LinkNode *stash (UT_LinkNode *node = 0);
102  UT_LinkNode *stash (int nodeIdx);
103  UT_LinkNode *recall(UT_LinkNode *node = 0);
104  UT_LinkNode *recall(UT_LinkNode *node, int nodeIdx);
105 
106  // Return the index of the node in the list or vice-versa.
107  // The first method returns -1 if not found; the 2nd method
108  // returns 0 if unsuccessful.
109  int find(UT_LinkNode *node) const;
110  UT_LinkNode *find(int nodeIdx) const;
111 
112  // Check if the node is in the active list: return 1 if true, o if
113  // false.
114  int inList(UT_LinkNode *node) const;
115 
116 
117  // Return the predecessor or the successor of a node, or the
118  // first or last node in the list respectively.
119  UT_LinkNode *prev(UT_LinkNode *node) const { return node->prev(); }
120  UT_LinkNode *next(UT_LinkNode *node) const { return node->next(); }
121  UT_LinkNode *head() const { return first; }
122  UT_LinkNode *tail() const { return last; }
123 
124  // Some iteration functions, in case you are not using the separate
125  // iterator class:
126  UT_LinkNode *iterateInit() const { return first; }
128  {
129  return curr ? curr->next() : first;
130  }
132  {
133  return curr ? curr->prev() : last;
134  }
135  UT_LinkNode *iterateFastNext(UT_LinkNode *curr) const {return curr->next();}
136  UT_LinkNode *iterateFastPrev(UT_LinkNode *curr) const {return curr->prev();}
137 
138  // Clear the linked list: the list of stashed nodes, the active
139  // list, or both.
140  void clearStashed();
141  void clearActive();
142  void clear() { clearActive(); clearStashed(); }
143 
144  // Return the length of the list or just find out whether it's empty.
145  int length() const { return count; }
146  int isEmpty() const { return count == 0; }
147 
148  // Apply a user-defined function to each element of the linked
149  // list, as long as the function returns zero. If applyFct returns
150  // 0, apply() stops traversing the list and returns the current
151  // node; otherwise, apply() returns 0.
152  UT_LinkNode *apply(int (*applyFct)(UT_LinkNode *n, void *d), void *d);
153 
154  // Prohibit copy construction as we've never implemented one.
155  UT_LinkList(const UT_LinkList &) = delete;
156 
157  // Copy the other list's data into us. The source gets cleared.
159 
160  // Append the other list's data to ours. The source gets cleared.
162 
163  // I/O friends:
164  friend std::ostream &operator<<(std::ostream &os, const UT_LinkList &v)
165  {
166  v.outTo(os);
167  return os;
168  }
169 
170 protected:
171  // Current node of iteration, in case you are not using the iterator class.
172  // Remove a node from the replacement list. Remove the last
173  // one inserted if 0.
174  UT_LinkNode *unStash(UT_LinkNode *node = 0);
175 
176  // Query the stash head:
177  UT_LinkNode *firstStash() const { return stashHead; }
178 
179  // Query the name of this class:
180  virtual const char *className() const;
181 
182  // Our own I/O methods, so we can redefine them in derived classes:
183  virtual void outTo (std::ostream &os) const;
184 
185  // Head of the stash list.
187 
188  // Just reset the state of the link list
189  // Not, this will cause memory leaks unless used with caution,
190  // ie. list sorting
191  void reset() { first = last = 0; count = 0; }
192 
193 
194 private:
195 
196  // DATA
197 
198  // First and last nodes in the active list.
200  UT_LinkNode *last;
201 
202  // Number of nodes in the active list.
203  int count;
204 };
205 
207 
208 #endif
GLint first
Definition: glcorearb.h:405
const GLdouble * v
Definition: glcorearb.h:837
void reverse(I begin, I end)
Definition: pugixml.cpp:7190
void swap(T &lhs, T &rhs)
Definition: pugixml.cpp:7172
#define UT_API
Definition: UT_API.h:14
OIIO_FORCEINLINE vbool4 insert(const vbool4 &a, bool val)
Helper: substitute val for a[i].
Definition: simd.h:3436
GLdouble n
Definition: glcorearb.h:2008
OIIO_FORCEINLINE const vint4 & operator+=(vint4 &a, const vint4 &b)
Definition: simd.h:4369
__hostdev__ uint64_t last(uint32_t i) const
Definition: NanoVDB.h:5976
LeafData & operator=(const LeafData &)=delete
#define UT_SWAPPER_CLASS(T)
Definition: UT_Swap.h:60
GLint GLsizei count
Definition: glcorearb.h:405
FMT_CONSTEXPR auto find(Ptr first, Ptr last, T value, Ptr &out) -> bool
Definition: core.h:2089
GLenum src
Definition: glcorearb.h:1793