1 : /**********************************************************************
2 : * $Id: cpl_list.cpp 14693 2008-06-12 18:21:54Z rouault $
3 : *
4 : * Name: cpl_list.cpp
5 : * Project: CPL - Common Portability Library
6 : * Purpose: List functions.
7 : * Author: Andrey Kiselev, dron@remotesensing.org
8 : *
9 : **********************************************************************
10 : * Copyright (c) 2003, Andrey Kiselev <dron@remotesensing.org>
11 : *
12 : * Permission is hereby granted, free of charge, to any person obtaining a
13 : * copy of this software and associated documentation files (the "Software"),
14 : * to deal in the Software without restriction, including without limitation
15 : * the rights to use, copy, modify, merge, publish, distribute, sublicense,
16 : * and/or sell copies of the Software, and to permit persons to whom the
17 : * Software is furnished to do so, subject to the following conditions:
18 : *
19 : * The above copyright notice and this permission notice shall be included
20 : * in all copies or substantial portions of the Software.
21 : *
22 : * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
23 : * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
24 : * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
25 : * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
26 : * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
27 : * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
28 : * DEALINGS IN THE SOFTWARE.
29 : ****************************************************************************/
30 :
31 : #include "cpl_list.h"
32 : #include "cpl_conv.h"
33 :
34 : CPL_CVSID("$Id: cpl_list.cpp 14693 2008-06-12 18:21:54Z rouault $");
35 :
36 : /*=====================================================================
37 : List manipulation functions.
38 : =====================================================================*/
39 :
40 : /************************************************************************/
41 : /* CPLListAppend() */
42 : /************************************************************************/
43 :
44 : /**
45 : * Append an object list and return a pointer to the modified list.
46 : * If the input list is NULL, then a new list is created.
47 : *
48 : * @param psList pointer to list head.
49 : * @param pData pointer to inserted data object. May be NULL.
50 : *
51 : * @return pointer to the head of modified list.
52 : */
53 :
54 76 : CPLList *CPLListAppend( CPLList *psList, void *pData )
55 : {
56 : CPLList *psLast;
57 :
58 : /* Allocate room for the new object */
59 76 : if ( psList == NULL )
60 : {
61 32 : psLast = psList = (CPLList *)CPLMalloc( sizeof(CPLList) );
62 : }
63 : else
64 : {
65 44 : psLast = CPLListGetLast( psList );
66 44 : psLast = psLast->psNext = (CPLList *)CPLMalloc( sizeof(CPLList) );
67 : }
68 :
69 : /* Append object to the end of list */
70 76 : psLast->pData = pData;
71 76 : psLast->psNext = NULL;
72 :
73 76 : return psList;
74 : }
75 :
76 : /************************************************************************/
77 : /* CPLListInsert() */
78 : /************************************************************************/
79 :
80 : /**
81 : * Insert an object into list at specified position (zero based).
82 : * If the input list is NULL, then a new list is created.
83 : *
84 : * @param psList pointer to list head.
85 : * @param pData pointer to inserted data object. May be NULL.
86 : * @param nPosition position number to insert an object.
87 : *
88 : * @return pointer to the head of modified list.
89 : */
90 :
91 31927 : CPLList *CPLListInsert( CPLList *psList, void *pData, int nPosition )
92 : {
93 : CPLList *psCurrent;
94 : int i, nCount;
95 :
96 31927 : if ( nPosition < 0 )
97 0 : return psList; /* Nothing to do!*/
98 :
99 31927 : nCount = CPLListCount( psList );
100 :
101 31927 : if ( nPosition == 0)
102 : {
103 31924 : CPLList *psNew = (CPLList *)CPLMalloc( sizeof(CPLList) );
104 31924 : psNew->pData = pData;
105 31924 : psNew->psNext = psList;
106 31924 : psList = psNew;
107 : }
108 3 : else if ( nCount < nPosition )
109 : {
110 : /* Allocate room for the new object */
111 0 : CPLList* psLast = CPLListGetLast(psList);
112 0 : for ( i = nCount; i <= nPosition - 1; i++ )
113 : {
114 0 : psLast = CPLListAppend( psLast, NULL );
115 0 : if (psList == NULL)
116 0 : psList = psLast;
117 : else
118 0 : psLast = psLast->psNext;
119 : }
120 0 : psLast = CPLListAppend( psLast, pData );
121 0 : if (psList == NULL)
122 0 : psList = psLast;
123 : }
124 : else
125 : {
126 3 : CPLList *psNew = (CPLList *)CPLMalloc( sizeof(CPLList) );
127 3 : psNew->pData = pData;
128 :
129 3 : psCurrent = psList;
130 18 : for ( i = 0; i < nPosition - 1; i++ )
131 15 : psCurrent = psCurrent->psNext;
132 3 : psNew->psNext = psCurrent->psNext;
133 3 : psCurrent->psNext = psNew;
134 : }
135 :
136 31927 : return psList;
137 : }
138 :
139 : /************************************************************************/
140 : /* CPLListGetLast() */
141 : /************************************************************************/
142 :
143 : /**
144 : * Return the pointer to last element in a list.
145 : *
146 : * @param psList pointer to list head.
147 : *
148 : * @return pointer to last element in a list.
149 : */
150 :
151 44 : CPLList *CPLListGetLast( CPLList *psList )
152 : {
153 44 : CPLList *psCurrent = psList;
154 :
155 44 : if ( psList == NULL )
156 0 : return NULL;
157 :
158 265 : while ( psCurrent->psNext )
159 177 : psCurrent = psCurrent->psNext;
160 :
161 44 : return psCurrent;
162 : }
163 :
164 : /************************************************************************/
165 : /* CPLListGet() */
166 : /************************************************************************/
167 :
168 : /**
169 : * Return the pointer to the specified element in a list.
170 : *
171 : * @param psList pointer to list head.
172 : * @param nPosition the index of the element in the list, 0 being the first element
173 : *
174 : * @return pointer to the specified element in a list.
175 : */
176 :
177 1225 : CPLList *CPLListGet( CPLList *psList, int nPosition )
178 : {
179 1225 : int iItem = 0;
180 1225 : CPLList *psCurrent = psList;
181 :
182 1225 : if ( nPosition < 0 )
183 0 : return NULL;
184 :
185 5118 : while ( iItem < nPosition && psCurrent )
186 : {
187 2668 : psCurrent = psCurrent->psNext;
188 2668 : iItem++;
189 : }
190 :
191 1225 : return psCurrent;
192 : }
193 :
194 : /************************************************************************/
195 : /* CPLListCount() */
196 : /************************************************************************/
197 :
198 : /**
199 : * Return the number of elements in a list.
200 : *
201 : * @param psList pointer to list head.
202 : *
203 : * @return number of elements in a list.
204 : */
205 :
206 32315 : int CPLListCount( CPLList *psList )
207 : {
208 32315 : int nItems = 0;
209 32315 : CPLList *psCurrent = psList;
210 :
211 72015 : while ( psCurrent )
212 : {
213 7385 : nItems++;
214 7385 : psCurrent = psCurrent->psNext;
215 : }
216 :
217 32315 : return nItems;
218 : }
219 :
220 : /************************************************************************/
221 : /* CPLListRemove() */
222 : /************************************************************************/
223 :
224 : /**
225 : * Remove the element from the specified position (zero based) in a list. Data
226 : * object contained in removed element must be freed by the caller first.
227 : *
228 : * @param psList pointer to list head.
229 : * @param nPosition position number to delet an element.
230 : *
231 : * @return pointer to the head of modified list.
232 : */
233 :
234 0 : CPLList *CPLListRemove( CPLList *psList, int nPosition )
235 : {
236 : CPLList *psCurrent, *psRemoved;
237 : int i;
238 :
239 0 : if ( psList == NULL)
240 : {
241 0 : return NULL;
242 : }
243 0 : else if ( nPosition < 0)
244 : {
245 0 : return psList; /* Nothing to do!*/
246 : }
247 0 : else if ( nPosition == 0 )
248 : {
249 0 : psCurrent = psList->psNext;
250 0 : CPLFree( psList );
251 0 : psList = psCurrent;
252 : }
253 : else
254 : {
255 0 : psCurrent = psList;
256 0 : for ( i = 0; i < nPosition - 1; i++ )
257 : {
258 0 : psCurrent = psCurrent->psNext;
259 : /* psCurrent == NULL if nPosition >= CPLListCount(psList) */
260 0 : if (psCurrent == NULL)
261 0 : return psList;
262 : }
263 0 : psRemoved = psCurrent->psNext;
264 : /* psRemoved == NULL if nPosition >= CPLListCount(psList) */
265 0 : if (psRemoved == NULL)
266 0 : return psList;
267 0 : psCurrent->psNext = psRemoved->psNext;
268 0 : CPLFree( psRemoved );
269 : }
270 :
271 0 : return psList;
272 : }
273 :
274 : /************************************************************************/
275 : /* CPLListDestroy() */
276 : /************************************************************************/
277 :
278 : /**
279 : * Destroy a list. Caller responsible for freeing data objects contained in
280 : * list elements.
281 : *
282 : * @param psList pointer to list head.
283 : *
284 : */
285 :
286 206204 : void CPLListDestroy( CPLList *psList )
287 : {
288 : CPLList *psNext;
289 206204 : CPLList *psCurrent = psList;
290 :
291 432413 : while ( psCurrent )
292 : {
293 20005 : psNext = psCurrent->psNext;
294 20005 : CPLFree( psCurrent );
295 20005 : psCurrent = psNext;
296 : }
297 206204 : }
298 :
299 : /************************************************************************/
300 : /* CPLListGetNext() */
301 : /************************************************************************/
302 :
303 : /**
304 : * Return the pointer to next element in a list.
305 : *
306 : * @param psElement pointer to list element.
307 : *
308 : * @return pointer to the list element preceded by the given element.
309 : */
310 :
311 0 : CPLList *CPLListGetNext( CPLList *psElement )
312 : {
313 0 : if ( psElement == NULL )
314 0 : return NULL;
315 : else
316 0 : return psElement->psNext;
317 : }
318 :
319 : /************************************************************************/
320 : /* CPLListGetData() */
321 : /************************************************************************/
322 :
323 : /**
324 : * Return pointer to the data object contained in given list element.
325 : *
326 : * @param psElement pointer to list element.
327 : *
328 : * @return pointer to the data object contained in given list element.
329 : */
330 :
331 1225 : void *CPLListGetData( CPLList *psElement )
332 : {
333 1225 : if ( psElement == NULL )
334 0 : return NULL;
335 : else
336 1225 : return psElement->pData;
337 : }
338 :
|
