gwenhywfar  4.6.0beta
list1.c
Go to the documentation of this file.
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 
35 static GWENHYWFAR_CB int GWEN_List1__defaultSortFn(const void *a, const void *b, int ascending) {
36  return 0;
37 }
38 
39 
40 
42  GWEN_LIST1 *l;
43 
45  l->sortFunction=GWEN_List1__defaultSortFn;
46  return l;
47 }
48 
49 
51  if (l) {
53  }
54 }
55 
56 
57 
59  assert(l);
60  return l->count;
61 }
62 
63 
64 
66  assert(l);
67  assert(el);
68  if (el->listPtr) {
69  /* element is already part of another list */
70  DBG_ERROR(GWEN_LOGDOMAIN, "Element is already part of a list");
71  assert(0);
72  return -1;
73  }
74 
75  if (l->firstElement==0)
76  l->firstElement=el;
77 
78  el->prevElement=l->lastElement;
79  if (l->lastElement)
80  l->lastElement->nextElement=el;
81  l->lastElement=el;
82 
83  el->listPtr=l;
84  l->count++;
85 
86  return 0;
87 }
88 
89 
90 
93 
94  assert(dest);
95  assert(l);
96 
97  while((el=l->firstElement)) {
98  GWEN_List1_Del(el);
99  GWEN_List1_Add(dest, el);
100  }
101 
102  return 0;
103 }
104 
105 
106 
108  assert(l);
109  assert(el);
110  if (el->listPtr) {
111  /* element is already part of another list */
112  DBG_ERROR(GWEN_LOGDOMAIN, "Element is already part of a list");
113  return -1;
114  }
115 
116  el->nextElement=l->firstElement;
117  l->firstElement=el;
118 
119  if (l->lastElement==0)
120  l->lastElement=el;
121 
122  if (el->nextElement)
123  el->nextElement->prevElement=el;
124 
125  el->listPtr=l;
126  l->count++;
127 
128  return 0;
129 }
130 
131 
132 
134  GWEN_LIST1 *l;
135 
136  assert(el);
137  l=el->listPtr;
138 
139  if (l==0) {
140  /* not part of any list */
141  DBG_ERROR(GWEN_LOGDOMAIN, "Element is not part of any list");
142  return -1;
143  }
144 
145  /* unlink from previous */
146  if (el->prevElement)
147  el->prevElement->nextElement=el->nextElement;
148 
149  /* unlink from next */
150  if (el->nextElement)
151  el->nextElement->prevElement=el->prevElement;
152 
153  /* unlink from list */
154  if (l->firstElement==el)
155  l->firstElement=el->nextElement;
156  if (l->lastElement==el)
157  l->lastElement=el->prevElement;
158  l->count--;
159 
160  el->nextElement=0;
161  el->prevElement=0;
162  el->listPtr=0;
163 
164  return 0;
165 }
166 
167 
168 
170  if (l->firstElement)
171  return l->firstElement->data;
172  return 0;
173 }
174 
175 
176 
178  if (l->lastElement)
179  return l->lastElement->data;
180  return 0;
181 }
182 
183 
184 
185 
186 
187 
189  GWEN_LIST1_ELEMENT *el;
190 
192  el->data=d;
193 
194  return el;
195 }
196 
197 
198 
200  if (el) {
201  if (el->listPtr)
202  GWEN_List1_Del(el);
203  GWEN_FREE_OBJECT(el);
204  }
205 }
206 
207 
208 
210  return el->data;
211 }
212 
213 
214 
216  if (el->prevElement)
217  return el->prevElement->data;
218  return 0;
219 }
220 
221 
222 
224  if (el->nextElement)
225  return el->nextElement->data;
226  return 0;
227 }
228 
229 
230 
231 #if 0
232 static int GWEN_List1__compar_asc(const void *a, const void *b) {
233  const GWEN_LIST1_ELEMENT * const * pse1 = a, * const * pse2 = b;
234  const GWEN_LIST1_ELEMENT *se1 = *pse1, *se2 = *pse2;
235 
236  return (se1->listPtr->sortFunction)(se1->data, se2->data, 1);
237 }
238 
239 
240 
241 static int GWEN_List1__compar_desc(const void *a, const void *b) {
242  const GWEN_LIST1_ELEMENT * const * pse1 = a, * const * pse2 = b;
243  const GWEN_LIST1_ELEMENT *se1 = *pse1, *se2 = *pse2;
244 
245  return (se1->listPtr->sortFunction)(se1->data, se2->data, 0);
246 }
247 
248 
249 
251  GWEN_LIST1_SORT_FN oldFn;
252 
253  assert(l);
254  oldFn=l->sortFunction;
255  l->sortFunction=fn;
256  return oldFn;
257 }
258 
259 
260 
261 void GWEN_List1_Sort(GWEN_LIST1 *l, int ascending) {
262  GWEN_LIST1_ELEMENT **tmpEntries;
263  GWEN_LIST1_ELEMENT *sentry;
264  GWEN_LIST1_ELEMENT **psentry;
265  uint32_t count;
266  uint32_t i;
267 
268  if (l->count<1)
269  return;
270 
271  count=l->count;
272 
273  /* sort entries into a linear pointer list */
274  tmpEntries=(GWEN_LIST1_ELEMENT **)malloc((count+1)* sizeof(GWEN_LIST1_ELEMENT*));
275  assert(tmpEntries);
276  psentry=tmpEntries;
277 
278  sentry=l->firstElement;
279  while(sentry) {
280  GWEN_LIST1_ELEMENT *next;
281 
282  *(psentry++)=sentry;
283  next=sentry->nextElement;
284  sentry->prevElement=NULL;
285  sentry->nextElement=NULL;
286  sentry->listPtr=l;
287  sentry=next;
288  } /* while */
289  *psentry=NULL;
290 
291  /* clear list */
292  l->count=0;
293  l->firstElement=NULL;
294  l->lastElement=NULL;
295 
296  /* sort */
297  if (ascending)
298  qsort(tmpEntries, count, sizeof(GWEN_LIST1_ELEMENT*), GWEN_List1__compar_asc);
299  else
300  qsort(tmpEntries, count, sizeof(GWEN_LIST1_ELEMENT*), GWEN_List1__compar_desc);
301 
302  /* sort entries back into GWEN_LIST1 according to temporary list */
303  psentry=tmpEntries;
304  /* we use "<=count" because the list contains count+1 elements */
305  for (i=0; i<=count; i++) {
306  if (*psentry) {
307  (*psentry)->listPtr=NULL;
308  GWEN_List1_Add(l, *psentry);
309  }
310  psentry++;
311  } /* for */
312 
313  free(tmpEntries);
314 }
315 #endif
316 
317 
318 
319 
320 
321 
322 
323 
324 
325 /* -------------------------------------------------------------------------------------------------
326  * Sort
327  * -------------------------------------------------------------------------------------------------
328  */
329 
330 
331 static int GWEN_List1__compar(const void *a, const void *b) {
332  const GWEN_LIST1_SORT_ELEM * const * pse1 = a, * const * pse2 = b;
333  const GWEN_LIST1_SORT_ELEM *se1 = *pse1, *se2 = *pse2;
334  const GWEN_LIST1_SORT_CTX *ctx=se1->context;
335 
336  const GWEN_LIST1_ELEMENT * e1=se1->element;
337  const GWEN_LIST1_ELEMENT * e2=se2->element;
338 
339  return (ctx->list->sortFunction)(e1->data, e2->data, ctx->param);
340 }
341 
342 
343 
345  GWEN_LIST1_SORT_FN oldFn;
346 
347  assert(l);
348  oldFn=l->sortFunction;
349  l->sortFunction=fn;
350  return oldFn;
351 }
352 
353 
354 
355 
356 
357 
358 
359 
360 
361 
362 
363 
364 GWEN_LIST1_SORT_CTX *GWEN_List1_SortCtx_new(GWEN_LIST1 *list, int param) {
365  GWEN_LIST1_SORT_CTX *ctx;
366 
367  GWEN_NEW_OBJECT(GWEN_LIST1_SORT_CTX, ctx);
368  ctx->list=list;
369  ctx->param=param;
370  return ctx;
371 }
372 
373 
374 
375 void GWEN_List1_SortCtx_free(GWEN_LIST1_SORT_CTX *ctx) {
376  if (ctx) {
377  GWEN_FREE_OBJECT(ctx);
378  }
379 }
380 
381 
382 
383 GWEN_LIST1_SORT_ELEM *GWEN_List1_SortElem_new(GWEN_LIST1_SORT_CTX *ctx, GWEN_LIST1_ELEMENT *elem) {
384  GWEN_LIST1_SORT_ELEM *e;
385 
386  GWEN_NEW_OBJECT(GWEN_LIST1_SORT_ELEM, e);
387  e->context=ctx;
388  e->element=elem;
389  return e;
390 }
391 
392 
393 
394 void GWEN_List1_SortElem_free(GWEN_LIST1_SORT_ELEM *e) {
395  if (e) {
396  GWEN_FREE_OBJECT(e);
397  }
398 }
399 
400 
401 
402 void GWEN_List1_Sort(GWEN_LIST1 *l, int ascending) {
403  GWEN_LIST1_SORT_ELEM **tmpEntries;
404  GWEN_LIST1_SORT_ELEM **psentry;
405  GWEN_LIST1_ELEMENT *sentry;
406  uint32_t count;
407  uint32_t i;
408  GWEN_LIST1_SORT_CTX *sortContext;
409 
410  if (l->count<1)
411  return;
412 
413  count=l->count;
414 
415  sortContext=GWEN_List1_SortCtx_new(l, ascending);
416 
417  /* sort entries into a linear pointer list */
418  tmpEntries=(GWEN_LIST1_SORT_ELEM **)malloc((count+1)* sizeof(GWEN_LIST1_SORT_ELEM*));
419  assert(tmpEntries);
420  psentry=tmpEntries;
421 
422  sentry=l->firstElement;
423  while(sentry) {
424  GWEN_LIST1_ELEMENT *next;
425  GWEN_LIST1_SORT_ELEM *se;
426 
427  se=GWEN_List1_SortElem_new(sortContext, sentry);
428  *(psentry++)=se;
429  next=sentry->nextElement;
430  sentry->prevElement=NULL;
431  sentry->nextElement=NULL;
432  sentry->listPtr=l;
433  sentry=next;
434  } /* while */
435  *psentry=NULL;
436 
437  /* clear list */
438  l->count=0;
439  l->firstElement=NULL;
440  l->lastElement=NULL;
441 
442  /* sort */
443  qsort(tmpEntries, count, sizeof(GWEN_LIST1_SORT_ELEM*), GWEN_List1__compar);
444 
445  /* sort entries back into GWEN_LIST1 according to temporary list */
446  psentry=tmpEntries;
447  /* we use "<=count" because the list contains count+1 elements */
448  for (i=0; i<=count; i++) {
449  GWEN_LIST1_SORT_ELEM *se;
450 
451  se=*psentry;
452  if (se) {
453  sentry=se->element;
454  sentry->listPtr=NULL;
455  GWEN_List1_Add(l, sentry);
457  *psentry=NULL;
458  }
459  psentry++;
460  } /* for */
461 
462  free(tmpEntries);
463  GWEN_List1_SortCtx_free(sortContext);
464 }
465 
466 
467 
468 
469 
470