1 /***************************************************************************
2 begin : Sat Nov 15 2003
3 copyright : (C) 2003 by Martin Preuss
4 email : martin@libchipcard.de
5
6 ***************************************************************************
7 * *
8 * This library is free software; you can redistribute it and/or *
9 * modify it under the terms of the GNU Lesser General Public *
10 * License as published by the Free Software Foundation; either *
11 * version 2.1 of the License, or (at your option) any later version. *
12 * *
13 * This library is distributed in the hope that it will be useful, *
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
16 * Lesser General Public License for more details. *
17 * *
18 * You should have received a copy of the GNU Lesser General Public *
19 * License along with this library; if not, write to the Free Software *
20 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, *
21 * MA 02111-1307 USA *
22 * *
23 ***************************************************************************/
24
25
26 #ifdef HAVE_CONFIG_H
27 # include <config.h>
28 #endif
29
30 #include "list1_p.h"
31 #include <gwenhywfar/misc.h>
32 #include <gwenhywfar/debug.h>
33
34
GWEN_List1__defaultSortFn(GWEN_UNUSED const void * a,GWEN_UNUSED const void * b,GWEN_UNUSED int ascending)35 static GWENHYWFAR_CB int GWEN_List1__defaultSortFn(GWEN_UNUSED const void *a, GWEN_UNUSED const void *b,
36 GWEN_UNUSED int ascending)
37 {
38 return 0;
39 }
40
41
42
GWEN_List1_new(void)43 GWEN_LIST1 *GWEN_List1_new(void)
44 {
45 GWEN_LIST1 *l;
46
47 GWEN_NEW_OBJECT(GWEN_LIST1, l);
48 l->sortFunction=GWEN_List1__defaultSortFn;
49 return l;
50 }
51
52
GWEN_List1_free(GWEN_LIST1 * l)53 void GWEN_List1_free(GWEN_LIST1 *l)
54 {
55 if (l) {
56 GWEN_FREE_OBJECT(l);
57 }
58 }
59
60
61
GWEN_List1_GetCount(const GWEN_LIST1 * l)62 int GWEN_List1_GetCount(const GWEN_LIST1 *l)
63 {
64 assert(l);
65 return l->count;
66 }
67
68
69
GWEN_List1_Add(GWEN_LIST1 * l,GWEN_LIST1_ELEMENT * el)70 int GWEN_List1_Add(GWEN_LIST1 *l, GWEN_LIST1_ELEMENT *el)
71 {
72 assert(l);
73 assert(el);
74 if (el->listPtr) {
75 /* element is already part of another list */
76 DBG_ERROR(GWEN_LOGDOMAIN, "Element is already part of a list");
77 assert(0);
78 return -1;
79 }
80
81 if (l->firstElement==0)
82 l->firstElement=el;
83
84 el->prevElement=l->lastElement;
85 if (l->lastElement)
86 l->lastElement->nextElement=el;
87 l->lastElement=el;
88
89 el->listPtr=l;
90 l->count++;
91
92 return 0;
93 }
94
95
96
GWEN_List1_AddList(GWEN_LIST1 * dest,GWEN_LIST1 * l)97 int GWEN_List1_AddList(GWEN_LIST1 *dest, GWEN_LIST1 *l)
98 {
99 GWEN_LIST1_ELEMENT *el;
100
101 assert(dest);
102 assert(l);
103
104 while ((el=l->firstElement)) {
105 GWEN_List1_Del(el);
106 GWEN_List1_Add(dest, el);
107 }
108
109 return 0;
110 }
111
112
113
GWEN_List1_Insert(GWEN_LIST1 * l,GWEN_LIST1_ELEMENT * el)114 int GWEN_List1_Insert(GWEN_LIST1 *l, GWEN_LIST1_ELEMENT *el)
115 {
116 assert(l);
117 assert(el);
118 if (el->listPtr) {
119 /* element is already part of another list */
120 DBG_ERROR(GWEN_LOGDOMAIN, "Element is already part of a list");
121 return -1;
122 }
123
124 el->nextElement=l->firstElement;
125 l->firstElement=el;
126
127 if (l->lastElement==0)
128 l->lastElement=el;
129
130 if (el->nextElement)
131 el->nextElement->prevElement=el;
132
133 el->listPtr=l;
134 l->count++;
135
136 return 0;
137 }
138
139
140
GWEN_List1_Del(GWEN_LIST1_ELEMENT * el)141 int GWEN_List1_Del(GWEN_LIST1_ELEMENT *el)
142 {
143 GWEN_LIST1 *l;
144
145 assert(el);
146 l=el->listPtr;
147
148 if (l==0) {
149 /* not part of any list */
150 DBG_ERROR(GWEN_LOGDOMAIN, "Element is not part of any list");
151 return -1;
152 }
153
154 /* unlink from previous */
155 if (el->prevElement)
156 el->prevElement->nextElement=el->nextElement;
157
158 /* unlink from next */
159 if (el->nextElement)
160 el->nextElement->prevElement=el->prevElement;
161
162 /* unlink from list */
163 if (l->firstElement==el)
164 l->firstElement=el->nextElement;
165 if (l->lastElement==el)
166 l->lastElement=el->prevElement;
167 l->count--;
168
169 el->nextElement=0;
170 el->prevElement=0;
171 el->listPtr=0;
172
173 return 0;
174 }
175
176
177
GWEN_List1_GetFirst(const GWEN_LIST1 * l)178 void *GWEN_List1_GetFirst(const GWEN_LIST1 *l)
179 {
180 if (l->firstElement)
181 return l->firstElement->data;
182 return 0;
183 }
184
185
186
GWEN_List1_GetLast(const GWEN_LIST1 * l)187 void *GWEN_List1_GetLast(const GWEN_LIST1 *l)
188 {
189 if (l->lastElement)
190 return l->lastElement->data;
191 return 0;
192 }
193
194
195
196
197
198
GWEN_List1Element_new(void * d)199 GWEN_LIST1_ELEMENT *GWEN_List1Element_new(void *d)
200 {
201 GWEN_LIST1_ELEMENT *el;
202
203 GWEN_NEW_OBJECT(GWEN_LIST1_ELEMENT, el);
204 el->data=d;
205
206 return el;
207 }
208
209
210
GWEN_List1Element_free(GWEN_LIST1_ELEMENT * el)211 void GWEN_List1Element_free(GWEN_LIST1_ELEMENT *el)
212 {
213 if (el) {
214 if (el->listPtr)
215 GWEN_List1_Del(el);
216 GWEN_FREE_OBJECT(el);
217 }
218 }
219
220
221
GWEN_List1Element_GetData(const GWEN_LIST1_ELEMENT * el)222 void *GWEN_List1Element_GetData(const GWEN_LIST1_ELEMENT *el)
223 {
224 return el->data;
225 }
226
227
228
GWEN_List1Element_GetPrevious(const GWEN_LIST1_ELEMENT * el)229 void *GWEN_List1Element_GetPrevious(const GWEN_LIST1_ELEMENT *el)
230 {
231 if (el->prevElement)
232 return el->prevElement->data;
233 return 0;
234 }
235
236
237
GWEN_List1Element_GetNext(const GWEN_LIST1_ELEMENT * el)238 void *GWEN_List1Element_GetNext(const GWEN_LIST1_ELEMENT *el)
239 {
240 if (el->nextElement)
241 return el->nextElement->data;
242 return 0;
243 }
244
245
246
247 #if 0
248 static int GWEN_List1__compar_asc(const void *a, const void *b)
249 {
250 const GWEN_LIST1_ELEMENT *const *pse1 = a, * const * pse2 = b;
251 const GWEN_LIST1_ELEMENT *se1 = *pse1, *se2 = *pse2;
252
253 return (se1->listPtr->sortFunction)(se1->data, se2->data, 1);
254 }
255
256
257
258 static int GWEN_List1__compar_desc(const void *a, const void *b)
259 {
260 const GWEN_LIST1_ELEMENT *const *pse1 = a, * const * pse2 = b;
261 const GWEN_LIST1_ELEMENT *se1 = *pse1, *se2 = *pse2;
262
263 return (se1->listPtr->sortFunction)(se1->data, se2->data, 0);
264 }
265
266
267
268 GWEN_LIST1_SORT_FN GWEN_List1_SetSortFn(GWEN_LIST1 *l, GWEN_LIST1_SORT_FN fn)
269 {
270 GWEN_LIST1_SORT_FN oldFn;
271
272 assert(l);
273 oldFn=l->sortFunction;
274 l->sortFunction=fn;
275 return oldFn;
276 }
277
278
279
280 void GWEN_List1_Sort(GWEN_LIST1 *l, int ascending)
281 {
282 GWEN_LIST1_ELEMENT **tmpEntries;
283 GWEN_LIST1_ELEMENT *sentry;
284 GWEN_LIST1_ELEMENT **psentry;
285 uint32_t count;
286 uint32_t i;
287
288 if (l->count<1)
289 return;
290
291 count=l->count;
292
293 /* sort entries into a linear pointer list */
294 tmpEntries=(GWEN_LIST1_ELEMENT **)malloc((count+1)* sizeof(GWEN_LIST1_ELEMENT *));
295 assert(tmpEntries);
296 psentry=tmpEntries;
297
298 sentry=l->firstElement;
299 while (sentry) {
300 GWEN_LIST1_ELEMENT *next;
301
302 *(psentry++)=sentry;
303 next=sentry->nextElement;
304 sentry->prevElement=NULL;
305 sentry->nextElement=NULL;
306 sentry->listPtr=l;
307 sentry=next;
308 } /* while */
309 *psentry=NULL;
310
311 /* clear list */
312 l->count=0;
313 l->firstElement=NULL;
314 l->lastElement=NULL;
315
316 /* sort */
317 if (ascending)
318 qsort(tmpEntries, count, sizeof(GWEN_LIST1_ELEMENT *), GWEN_List1__compar_asc);
319 else
320 qsort(tmpEntries, count, sizeof(GWEN_LIST1_ELEMENT *), GWEN_List1__compar_desc);
321
322 /* sort entries back into GWEN_LIST1 according to temporary list */
323 psentry=tmpEntries;
324 /* we use "<=count" because the list contains count+1 elements */
325 for (i=0; i<=count; i++) {
326 if (*psentry) {
327 (*psentry)->listPtr=NULL;
328 GWEN_List1_Add(l, *psentry);
329 }
330 psentry++;
331 } /* for */
332
333 free(tmpEntries);
334 }
335 #endif
336
337
338
339
340
341
342
343
344
345 /* -------------------------------------------------------------------------------------------------
346 * Sort
347 * -------------------------------------------------------------------------------------------------
348 */
349
350
GWEN_List1__compar(const void * a,const void * b)351 static int GWEN_List1__compar(const void *a, const void *b)
352 {
353 const GWEN_LIST1_SORT_ELEM *const *pse1 = a, * const * pse2 = b;
354 const GWEN_LIST1_SORT_ELEM *se1 = *pse1, *se2 = *pse2;
355 const GWEN_LIST1_SORT_CTX *ctx=se1->context;
356
357 const GWEN_LIST1_ELEMENT *e1=se1->element;
358 const GWEN_LIST1_ELEMENT *e2=se2->element;
359
360 return (ctx->list->sortFunction)(e1->data, e2->data, ctx->param);
361 }
362
363
364
GWEN_List1_SetSortFn(GWEN_LIST1 * l,GWEN_LIST1_SORT_FN fn)365 GWEN_LIST1_SORT_FN GWEN_List1_SetSortFn(GWEN_LIST1 *l, GWEN_LIST1_SORT_FN fn)
366 {
367 GWEN_LIST1_SORT_FN oldFn;
368
369 assert(l);
370 oldFn=l->sortFunction;
371 l->sortFunction=fn;
372 return oldFn;
373 }
374
375
376
377
378
379
380
381
382
383
384
385
GWEN_List1_SortCtx_new(GWEN_LIST1 * list,int param)386 GWEN_LIST1_SORT_CTX *GWEN_List1_SortCtx_new(GWEN_LIST1 *list, int param)
387 {
388 GWEN_LIST1_SORT_CTX *ctx;
389
390 GWEN_NEW_OBJECT(GWEN_LIST1_SORT_CTX, ctx);
391 ctx->list=list;
392 ctx->param=param;
393 return ctx;
394 }
395
396
397
GWEN_List1_SortCtx_free(GWEN_LIST1_SORT_CTX * ctx)398 void GWEN_List1_SortCtx_free(GWEN_LIST1_SORT_CTX *ctx)
399 {
400 if (ctx) {
401 GWEN_FREE_OBJECT(ctx);
402 }
403 }
404
405
406
GWEN_List1_SortElem_new(GWEN_LIST1_SORT_CTX * ctx,GWEN_LIST1_ELEMENT * elem)407 GWEN_LIST1_SORT_ELEM *GWEN_List1_SortElem_new(GWEN_LIST1_SORT_CTX *ctx, GWEN_LIST1_ELEMENT *elem)
408 {
409 GWEN_LIST1_SORT_ELEM *e;
410
411 GWEN_NEW_OBJECT(GWEN_LIST1_SORT_ELEM, e);
412 e->context=ctx;
413 e->element=elem;
414 return e;
415 }
416
417
418
GWEN_List1_SortElem_free(GWEN_LIST1_SORT_ELEM * e)419 void GWEN_List1_SortElem_free(GWEN_LIST1_SORT_ELEM *e)
420 {
421 if (e) {
422 GWEN_FREE_OBJECT(e);
423 }
424 }
425
426
427
GWEN_List1_Sort(GWEN_LIST1 * l,int ascending)428 void GWEN_List1_Sort(GWEN_LIST1 *l, int ascending)
429 {
430 GWEN_LIST1_SORT_ELEM **tmpEntries;
431 GWEN_LIST1_SORT_ELEM **psentry;
432 GWEN_LIST1_ELEMENT *sentry;
433 uint32_t count;
434 uint32_t i;
435 GWEN_LIST1_SORT_CTX *sortContext;
436
437 if (l->count<1)
438 return;
439
440 count=l->count;
441
442 sortContext=GWEN_List1_SortCtx_new(l, ascending);
443
444 /* sort entries into a linear pointer list */
445 tmpEntries=(GWEN_LIST1_SORT_ELEM **)malloc((count+1)* sizeof(GWEN_LIST1_SORT_ELEM *));
446 assert(tmpEntries);
447 psentry=tmpEntries;
448
449 sentry=l->firstElement;
450 while (sentry) {
451 GWEN_LIST1_ELEMENT *next;
452 GWEN_LIST1_SORT_ELEM *se;
453
454 se=GWEN_List1_SortElem_new(sortContext, sentry);
455 *(psentry++)=se;
456 next=sentry->nextElement;
457 sentry->prevElement=NULL;
458 sentry->nextElement=NULL;
459 sentry->listPtr=l;
460 sentry=next;
461 } /* while */
462 *psentry=NULL;
463
464 /* clear list */
465 l->count=0;
466 l->firstElement=NULL;
467 l->lastElement=NULL;
468
469 /* sort */
470 qsort(tmpEntries, count, sizeof(GWEN_LIST1_SORT_ELEM *), GWEN_List1__compar);
471
472 /* sort entries back into GWEN_LIST1 according to temporary list */
473 psentry=tmpEntries;
474 /* we use "<=count" because the list contains count+1 elements */
475 for (i=0; i<=count; i++) {
476 GWEN_LIST1_SORT_ELEM *se;
477
478 se=*psentry;
479 if (se) {
480 sentry=se->element;
481 sentry->listPtr=NULL;
482 GWEN_List1_Add(l, sentry);
483 GWEN_List1_SortElem_free(se);
484 *psentry=NULL;
485 }
486 psentry++;
487 } /* for */
488
489 free(tmpEntries);
490 GWEN_List1_SortCtx_free(sortContext);
491 }
492
493
494
495
496
497
498