1 // Copyright 2009 The Archiveopteryx Developers <info@aox.org>
2
3 #include "list.h"
4
5 #include "allocator.h"
6 #include "estring.h"
7
8 #include <stdlib.h>
9
10
listSortHelper(void * a,size_t n,size_t s,int (* c)(const void *,const void *))11 void listSortHelper( void * a, size_t n, size_t s,
12 int(*c)(const void *, const void *))
13 {
14 ::qsort( a, n, s, c );
15 }
16
17
listAllocatorBouncer(size_t s)18 void * listAllocatorBouncer( size_t s )
19 {
20 return Allocator::alloc( s );
21 }
22
23
24 /*! \class List list.h
25 A generic template class for a doubly-linked list of pointers-to-T.
26
27 A new List isEmpty(), and elements can be added using append(),
28 prepend() or insert(). The list knows its first() and last()
29 elements, and can find() specific ones. You can take() any
30 element away, as well as count() or clear() the entire List.
31
32 This class never deletes the List elements themselves. That is the
33 caller's responsibility.
34
35 There is also a SortedList template.
36 */
37
38
39 /*! \fn List::List()
40 Creates an empty list.
41 */
42
43
44 /*! \fn List::~List()
45 Destroys the list without affecting its contents.
46 */
47
48
49 /*! \fn bool List::isEmpty() const
50 Returns true only if the List contains no elements.
51 */
52
53
54 /*! \fn uint List::count() const
55 Returns the number of elements in the list.
56 */
57
58
59 /*! \fn void List::clear()
60 Empties the list by simply forgetting about all of its elements.
61 */
62
63
64 /*! \fn T *List::firstElement() const
65 This function returns the contents of the first element in the List,
66 without the need to create and dereference an Iterator with first().
67 Returns 0 if the list isEmpty().
68 */
69
70
71 /*! \fn T *List::lastElement() const
72 This function returns the contents of the last element in the List,
73 without the need to create and dereference an Iterator with last().
74 Returns 0 if the list isEmpty().
75 */
76
77
78 /*! \fn Iterator &List::first() const
79 Returns an Iterator that points to the first element in the List.
80 The Iterator evaluates to 0 if the list isEmpty().
81 */
82
83
84 /*! \fn Iterator &List::last() const
85 Returns an Iterator that points to the last element in the List.
86 The Iterator evaluates to 0 if the list isEmpty().
87 */
88
89
90 /*! \fn Iterator &List::end() const
91 Returns an Iterator that points beyond the last element in the List.
92 In a boolean context, this Iterator evaluates to false.
93 */
94
95
96 /*! \fn T *List::take( Iterator &i )
97 Removes the element pointed to by \a i from the List, and returns it
98 after incrementing \a i to point to the next element in the List. If
99 \a i does not point to a list element (e.g. end()), take() returns 0
100 and does nothing.
101 */
102
103
104 /*! \fn T *List::pop()
105 Removes the last element from the List and returns it, or 0 if there
106 is no element to remove. Equivalent to take( last() ).
107 */
108
109
110 /*! \fn T *List::shift()
111 Removes the first element from the List and returns it, or 0 if the
112 list isEmpty(). This is equivalent to take( first() ), but doesn't
113 allocate as much memory.
114 */
115
116
117 /*! \fn void List::insert( const Iterator &i, T *d )
118 Inserts \a d before the element pointed to by \a i.
119 */
120
121
122 /*! \fn void List::append( T *d )
123 Adds \a d to the end of the List.
124 */
125
126
127 /* \fn void List::append( List<T> * other )
128 Appends all elements in \a other to this List.
129 */
130
131
132 /*! \fn void List::prepend( T *d )
133 Adds \a d to the beginning of the List.
134
135 */
136
137
138 /*! \fn Iterator &List::find( const T *d )
139 Returns an Iterator pointing to the position of the first element in
140 the List that is equal to \a d.
141 */
142
143
144 /*! \fn Iterator &List::find( const EString &d )
145 Returns an Iterator pointing to the position of the first element in
146 the List that points to an object that is equal to the EString \a d.
147
148 */
149
150 /*! \fn T *List::remove( const T *d )
151 This function is equivalent to take( find( d ) ), in that it finds
152 the position of the first element in the List equal to \a d, then
153 removes that element. Its advantage is that it performs no memory
154 allocation. It returns a pointer to the removed element, or 0 if
155 it was not found in the List.
156 */
157
158 /*! \fn T *List::remove( const Iterator & d )
159 Removes \a d from the list and returns it as a pointer.
160
161 \a d remains valid and can be dereferenced.
162 */
163
164 /*! \fn List<T> * List::sorted( Comparator * comparator )
165
166 Returns a list containing the same items as in this list, sorted
167 as \a comparator says to. \a comparator has the same meaning as
168 for qsort(3).
169 */
170
171
172
173 /*-! \class List::Iterator list.h
174 This class can be used to iterate over the elements of a List<T>.
175
176 An Iterator behaves like a pointer to an element in the List. In a
177 boolean context, an Iterator is true if it points to an element in
178 the List, and false if it has been incremented or decremented past
179 one of its ends.
180
181 If the Iterator is true, it can be dereferenced (with * and ->) or
182 incremented to point to the next element, or decremented to point
183 to the previous one. It can also be compared to another Iterator.
184
185 The list must not contain null pointers.
186 */
187
188
189 /*! \class SortedList list.h
190 A List of pointers-to-T sorted in an ascending order defined by T.
191
192 This is a subclass of the generic List<T> that uses T::operator <=()
193 to insert each element in ascending order, after any elements it is
194 equal to. It behaves like the generic List<T> in all other respects.
195
196 This sorted insert behaviour occurs only when the insert() function
197 is passed a single pointer. Using prepend(), append(), and insert()
198 with an Iterator will still insert elements into specific positions
199 irrespective of their value.
200 */
201
202 /*! \fn Iterator & SortedList::insert( T *d )
203 This function inserts the object \a d into a SortedList, and returns
204 a reference to an Iterator pointing to it.
205 */
206