1 /**************************************************************************\
2 * Copyright (c) Kongsberg Oil & Gas Technologies AS
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are
7 * met:
8 *
9 * Redistributions of source code must retain the above copyright notice,
10 * this list of conditions and the following disclaimer.
11 *
12 * Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * Neither the name of the copyright holder nor the names of its
17 * contributors may be used to endorse or promote products derived from
18 * this software without specific prior written permission.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
23 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
24 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
25 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
26 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
28 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
30 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 \**************************************************************************/
32
33 /*!
34 \class SbPList SbPList.h Inventor/lists/SbPList.h
35 \brief The SbPList class is a container class for void pointers.
36
37 \ingroup base
38
39 */
40
41
42 #include <Inventor/lists/SbPList.h>
43
44 /*!
45 \fn SbPList::SbPList(const int sizehint)
46
47 This constructor initializes the internal allocated size for the
48 list to \a sizehint. Note that the list will still initially contain
49 zero items.
50
51 */
52
53 /*!
54 \fn void SbPList::append(void * item)
55
56 Append \a item to the end of the list.
57
58 Automatically allocates more items internally if needed.
59 */
60
61 /*!
62 \fn void * SbPList::get(const int index) const
63
64 Returns element at \a index. Does \e not expand array bounds if \a
65 index is outside the list.
66 */
67
68 /*!
69 \fn void SbPList::set(const int index, void * item)
70
71 Index operator to set element at \a index. Does \e not expand array
72 bounds if \a index is outside the list.
73 */
74
75 /*!
76 \fn void SbPList::removeFast(const int index)
77
78 Remove the item at \a index, moving the last item into its place and
79 truncating the list.
80 */
81
82 /*!
83 \fn int SbPList::getLength(void) const
84
85 Returns number of items in the list.
86 */
87
88 /*!
89 \fn void SbPList::truncate(const int length, const int fit)
90
91 Shorten the list to contain \a length elements, removing items from
92 \e index \a length and onwards.
93
94 If \a fit is non-zero, will also shrink the internal size of the
95 allocated array. Note that this is much less efficient than not
96 re-fitting the array size.
97 */
98
99 /*!
100 \fn void ** SbPList::getArrayPtr(const int start = 0) const
101
102 Returns pointer to a non-modifiable array of the lists elements.
103 \a start specifies an index into the array.
104
105 The caller is \e not responsible for freeing up the array, as it is
106 just a pointer into the internal array used by the list.
107 */
108
109 /*!
110 \fn void *& SbPList::operator[](const int index) const
111
112 Returns element at \a index.
113
114 Will automatically expand the size of the internal array if \a index
115 is outside the current bounds of the list. The values of any
116 additional pointers are then set to \c NULL.
117 */
118
119 /*!
120 \fn SbBool SbPList::operator!=(const SbPList & l) const
121
122 Inequality operator. Returns \c TRUE if this list and \a l are not
123 equal.
124 */
125
126 /*!
127 \fn void SbPList::expand(const int size)
128
129 Expand the list to contain \a size items. The new items added at the
130 end have undefined value.
131 */
132
133 /*!
134 \fn int SbPList::getArraySize(void) const
135
136 Return number of items there's allocated space for in the array.
137
138 \sa getLength()
139 */
140
141 /*!
142 Default constructor.
143 */
SbPList(const int sizehint)144 SbPList::SbPList(const int sizehint)
145 : itembuffersize(DEFAULTSIZE), numitems(0), itembuffer(builtinbuffer)
146 {
147 if (sizehint > DEFAULTSIZE) this->grow(sizehint);
148 }
149
150 /*!
151 Copy constructor.
152 */
SbPList(const SbPList & l)153 SbPList::SbPList(const SbPList & l)
154 : itembuffersize(DEFAULTSIZE), numitems(0), itembuffer(builtinbuffer)
155 {
156 this->copy(l);
157 }
158
159 /*!
160 Destructor.
161 */
~SbPList()162 SbPList::~SbPList()
163 {
164 if (this->itembuffer != builtinbuffer) delete[] this->itembuffer;
165 }
166
167 /*!
168 Make this list a copy of \a l.
169 */
170 void
copy(const SbPList & l)171 SbPList::copy(const SbPList & l)
172 {
173 if (this == &l) return;
174 const int n = l.numitems;
175 this->expand(n);
176 for (int i = 0; i < n; i++) this->itembuffer[i] = l.itembuffer[i];
177 }
178
179 /*!
180 Assignment operator
181 */
182 SbPList &
operator =(const SbPList & l)183 SbPList::operator=(const SbPList & l)
184 {
185 this->copy(l);
186 return *this;
187 }
188
189 /*!
190 Fit the allocated array exactly around the length of the list,
191 descarding memory spent on unused pre-allocated array cells.
192
193 You should normally not need or want to call this method, and it is
194 only available for the sake of having the option to optimize memory
195 usage for the unlikely event that you should throw around huge
196 SbList objects within your application.
197 */
198 void
fit(void)199 SbPList::fit(void)
200 {
201 const int items = this->numitems;
202
203 if (items < this->itembuffersize) {
204 void ** newitembuffer = this->builtinbuffer;
205 if (items > DEFAULTSIZE) newitembuffer = new void*[items];
206
207 if (newitembuffer != this->itembuffer) {
208 for (int i = 0; i < items; i++) newitembuffer[i] = this->itembuffer[i];
209 }
210
211 if (this->itembuffer != this->builtinbuffer) delete[] this->itembuffer;
212 this->itembuffer = newitembuffer;
213 this->itembuffersize = items > DEFAULTSIZE ? items : DEFAULTSIZE;
214 }
215 }
216
217 /*!
218 Return index of first occurrence of \a item in the list, or -1 if \a
219 item is not present.
220 */
221 int
find(const void * item) const222 SbPList::find(const void * item) const
223 {
224 for (int i = 0; i < this->numitems; i++)
225 if (this->itembuffer[i] == item) return i;
226 return -1;
227 }
228
229 /*!
230 Insert \a item at index \a insertbefore.
231
232 \a insertbefore should not be larger than the current number of
233 items in the list.
234 */
235 void
insert(void * item,const int insertbefore)236 SbPList::insert(void * item, const int insertbefore) {
237 #ifdef COIN_EXTRA_DEBUG
238 assert(insertbefore >= 0 && insertbefore <= this->numitems);
239 #endif // COIN_EXTRA_DEBUG
240 if (this->numitems == this->itembuffersize) this->grow();
241
242 for (int i = this->numitems; i > insertbefore; i--)
243 this->itembuffer[i] = this->itembuffer[i-1];
244 this->itembuffer[insertbefore] = item;
245 this->numitems++;
246 }
247
248 /*!
249 Removes an \a item from the list. If there are several items with
250 the same value, removes the \a item with the lowest index.
251 */
252 void
removeItem(void * item)253 SbPList::removeItem(void * item)
254 {
255 int idx = this->find(item);
256 #ifdef COIN_EXTRA_DEBUG
257 assert(idx != -1);
258 #endif // COIN_EXTRA_DEBUG
259 if (idx >= 0) {
260 this->remove(idx);
261 }
262 }
263
264 /*!
265 Remove the item at \a index, moving all subsequent items downwards
266 one place in the list.
267 */
268 void
remove(const int index)269 SbPList::remove(const int index)
270 {
271 #ifdef COIN_EXTRA_DEBUG
272 assert(index >= 0 && index < this->numitems);
273 #endif // COIN_EXTRA_DEBUG
274 this->numitems--;
275 for (int i = index; i < this->numitems; i++)
276 this->itembuffer[i] = this->itembuffer[i + 1];
277 }
278
279 /*!
280 Equality operator. Returns \c TRUE if this list and \a l are
281 identical, containing the exact same ordered set of elements.
282 */
283 int
operator ==(const SbPList & l) const284 SbPList::operator==(const SbPList & l) const
285 {
286 if (this == &l) return TRUE;
287 if (this->numitems != l.numitems) return FALSE;
288 for (int i = 0; i < this->numitems; i++)
289 if (this->itembuffer[i] != l.itembuffer[i]) return FALSE;
290 return TRUE;
291 }
292
293 // Expand list to the given size, filling in with NULL pointers.
294 void
expandlist(const int size) const295 SbPList::expandlist(const int size) const
296 {
297 const int oldsize = this->getLength();
298 SbPList * thisp = (SbPList *)this;
299 thisp->expand(size);
300 for (int i = oldsize; i < size; i++) (*thisp)[i] = NULL;
301 }
302
303 // grow allocated array, not number of items
304 void
grow(const int size)305 SbPList::grow(const int size)
306 {
307 // Default behavior is to double array size.
308 if (size == -1) this->itembuffersize <<= 1;
309 else if (size <= this->itembuffersize) return;
310 else { this->itembuffersize = size; }
311
312 void ** newbuffer = new void*[this->itembuffersize];
313 const int n = this->numitems;
314 for (int i = 0; i < n; i++) newbuffer[i] = this->itembuffer[i];
315 if (this->itembuffer != this->builtinbuffer) delete[] this->itembuffer;
316 this->itembuffer = newbuffer;
317 }
318