00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026 #ifdef HAVE_CONFIG_H
00027 # include <config.h>
00028 #endif
00029
00030 #include "list1_p.h"
00031 #include <gwenhywfar/misc.h>
00032 #include <gwenhywfar/debug.h>
00033
00034
00035 static GWENHYWFAR_CB int GWEN_List1__defaultSortFn(const void *a, const void *b, int ascending) {
00036 return 0;
00037 }
00038
00039
00040
00041 GWEN_LIST1 *GWEN_List1_new(void) {
00042 GWEN_LIST1 *l;
00043
00044 GWEN_NEW_OBJECT(GWEN_LIST1, l);
00045 l->sortFunction=GWEN_List1__defaultSortFn;
00046 return l;
00047 }
00048
00049
00050 void GWEN_List1_free(GWEN_LIST1 *l) {
00051 if (l) {
00052 GWEN_FREE_OBJECT(l);
00053 }
00054 }
00055
00056
00057
00058 int GWEN_List1_GetCount(const GWEN_LIST1 *l) {
00059 assert(l);
00060 return l->count;
00061 }
00062
00063
00064
00065 int GWEN_List1_Add(GWEN_LIST1 *l, GWEN_LIST1_ELEMENT *el) {
00066 assert(l);
00067 assert(el);
00068 if (el->listPtr) {
00069
00070 DBG_ERROR(GWEN_LOGDOMAIN, "Element is already part of a list");
00071 assert(0);
00072 return -1;
00073 }
00074
00075 if (l->firstElement==0)
00076 l->firstElement=el;
00077
00078 el->prevElement=l->lastElement;
00079 if (l->lastElement)
00080 l->lastElement->nextElement=el;
00081 l->lastElement=el;
00082
00083 el->listPtr=l;
00084 l->count++;
00085
00086 return 0;
00087 }
00088
00089
00090
00091 int GWEN_List1_AddList(GWEN_LIST1 *dest, GWEN_LIST1 *l) {
00092 GWEN_LIST1_ELEMENT *el;
00093
00094 assert(dest);
00095 assert(l);
00096
00097 while((el=l->firstElement)) {
00098 GWEN_List1_Del(el);
00099 GWEN_List1_Add(dest, el);
00100 }
00101
00102 return 0;
00103 }
00104
00105
00106
00107 int GWEN_List1_Insert(GWEN_LIST1 *l, GWEN_LIST1_ELEMENT *el) {
00108 assert(l);
00109 assert(el);
00110 if (el->listPtr) {
00111
00112 DBG_ERROR(GWEN_LOGDOMAIN, "Element is already part of a list");
00113 return -1;
00114 }
00115
00116 el->nextElement=l->firstElement;
00117 l->firstElement=el;
00118
00119 if (l->lastElement==0)
00120 l->lastElement=el;
00121
00122 if (el->nextElement)
00123 el->nextElement->prevElement=el;
00124
00125 el->listPtr=l;
00126 l->count++;
00127
00128 return 0;
00129 }
00130
00131
00132
00133 int GWEN_List1_Del(GWEN_LIST1_ELEMENT *el) {
00134 GWEN_LIST1 *l;
00135
00136 assert(el);
00137 l=el->listPtr;
00138
00139 if (l==0) {
00140
00141 DBG_ERROR(GWEN_LOGDOMAIN, "Element is not part of any list");
00142 return -1;
00143 }
00144
00145
00146 if (el->prevElement)
00147 el->prevElement->nextElement=el->nextElement;
00148
00149
00150 if (el->nextElement)
00151 el->nextElement->prevElement=el->prevElement;
00152
00153
00154 if (l->firstElement==el)
00155 l->firstElement=el->nextElement;
00156 if (l->lastElement==el)
00157 l->lastElement=el->prevElement;
00158 l->count--;
00159
00160 el->nextElement=0;
00161 el->prevElement=0;
00162 el->listPtr=0;
00163
00164 return 0;
00165 }
00166
00167
00168
00169 void *GWEN_List1_GetFirst(const GWEN_LIST1 *l) {
00170 if (l->firstElement)
00171 return l->firstElement->data;
00172 return 0;
00173 }
00174
00175
00176
00177 void *GWEN_List1_GetLast(const GWEN_LIST1 *l) {
00178 if (l->lastElement)
00179 return l->lastElement->data;
00180 return 0;
00181 }
00182
00183
00184
00185
00186
00187
00188 GWEN_LIST1_ELEMENT *GWEN_List1Element_new(void *d) {
00189 GWEN_LIST1_ELEMENT *el;
00190
00191 GWEN_NEW_OBJECT(GWEN_LIST1_ELEMENT, el);
00192 el->data=d;
00193
00194 return el;
00195 }
00196
00197
00198
00199 void GWEN_List1Element_free(GWEN_LIST1_ELEMENT *el) {
00200 if (el) {
00201 if (el->listPtr)
00202 GWEN_List1_Del(el);
00203 GWEN_FREE_OBJECT(el);
00204 }
00205 }
00206
00207
00208
00209 void *GWEN_List1Element_GetData(const GWEN_LIST1_ELEMENT *el) {
00210 return el->data;
00211 }
00212
00213
00214
00215 void *GWEN_List1Element_GetPrevious(const GWEN_LIST1_ELEMENT *el){
00216 if (el->prevElement)
00217 return el->prevElement->data;
00218 return 0;
00219 }
00220
00221
00222
00223 void *GWEN_List1Element_GetNext(const GWEN_LIST1_ELEMENT *el){
00224 if (el->nextElement)
00225 return el->nextElement->data;
00226 return 0;
00227 }
00228
00229
00230
00231 #if 0
00232 static int GWEN_List1__compar_asc(const void *a, const void *b) {
00233 const GWEN_LIST1_ELEMENT * const * pse1 = a, * const * pse2 = b;
00234 const GWEN_LIST1_ELEMENT *se1 = *pse1, *se2 = *pse2;
00235
00236 return (se1->listPtr->sortFunction)(se1->data, se2->data, 1);
00237 }
00238
00239
00240
00241 static int GWEN_List1__compar_desc(const void *a, const void *b) {
00242 const GWEN_LIST1_ELEMENT * const * pse1 = a, * const * pse2 = b;
00243 const GWEN_LIST1_ELEMENT *se1 = *pse1, *se2 = *pse2;
00244
00245 return (se1->listPtr->sortFunction)(se1->data, se2->data, 0);
00246 }
00247
00248
00249
00250 GWEN_LIST1_SORT_FN GWEN_List1_SetSortFn(GWEN_LIST1 *l, GWEN_LIST1_SORT_FN fn) {
00251 GWEN_LIST1_SORT_FN oldFn;
00252
00253 assert(l);
00254 oldFn=l->sortFunction;
00255 l->sortFunction=fn;
00256 return oldFn;
00257 }
00258
00259
00260
00261 void GWEN_List1_Sort(GWEN_LIST1 *l, int ascending) {
00262 GWEN_LIST1_ELEMENT **tmpEntries;
00263 GWEN_LIST1_ELEMENT *sentry;
00264 GWEN_LIST1_ELEMENT **psentry;
00265 uint32_t count;
00266 uint32_t i;
00267
00268 if (l->count<1)
00269 return;
00270
00271 count=l->count;
00272
00273
00274 tmpEntries=(GWEN_LIST1_ELEMENT **)malloc((count+1)* sizeof(GWEN_LIST1_ELEMENT*));
00275 assert(tmpEntries);
00276 psentry=tmpEntries;
00277
00278 sentry=l->firstElement;
00279 while(sentry) {
00280 GWEN_LIST1_ELEMENT *next;
00281
00282 *(psentry++)=sentry;
00283 next=sentry->nextElement;
00284 sentry->prevElement=NULL;
00285 sentry->nextElement=NULL;
00286 sentry->listPtr=l;
00287 sentry=next;
00288 }
00289 *psentry=NULL;
00290
00291
00292 l->count=0;
00293 l->firstElement=NULL;
00294 l->lastElement=NULL;
00295
00296
00297 if (ascending)
00298 qsort(tmpEntries, count, sizeof(GWEN_LIST1_ELEMENT*), GWEN_List1__compar_asc);
00299 else
00300 qsort(tmpEntries, count, sizeof(GWEN_LIST1_ELEMENT*), GWEN_List1__compar_desc);
00301
00302
00303 psentry=tmpEntries;
00304
00305 for (i=0; i<=count; i++) {
00306 if (*psentry) {
00307 (*psentry)->listPtr=NULL;
00308 GWEN_List1_Add(l, *psentry);
00309 }
00310 psentry++;
00311 }
00312
00313 free(tmpEntries);
00314 }
00315 #endif
00316
00317
00318
00319
00320
00321
00322
00323
00324
00325
00326
00327
00328
00329
00330
00331 static int GWEN_List1__compar(const void *a, const void *b) {
00332 const GWEN_LIST1_SORT_ELEM * const * pse1 = a, * const * pse2 = b;
00333 const GWEN_LIST1_SORT_ELEM *se1 = *pse1, *se2 = *pse2;
00334 const GWEN_LIST1_SORT_CTX *ctx=se1->context;
00335
00336 const GWEN_LIST1_ELEMENT * e1=se1->element;
00337 const GWEN_LIST1_ELEMENT * e2=se2->element;
00338
00339 return (ctx->list->sortFunction)(e1->data, e2->data, ctx->param);
00340 }
00341
00342
00343
00344 GWEN_LIST1_SORT_FN GWEN_List1_SetSortFn(GWEN_LIST1 *l, GWEN_LIST1_SORT_FN fn) {
00345 GWEN_LIST1_SORT_FN oldFn;
00346
00347 assert(l);
00348 oldFn=l->sortFunction;
00349 l->sortFunction=fn;
00350 return oldFn;
00351 }
00352
00353
00354
00355
00356
00357
00358
00359
00360
00361
00362
00363
00364 GWEN_LIST1_SORT_CTX *GWEN_List1_SortCtx_new(GWEN_LIST1 *list, int param) {
00365 GWEN_LIST1_SORT_CTX *ctx;
00366
00367 GWEN_NEW_OBJECT(GWEN_LIST1_SORT_CTX, ctx);
00368 ctx->list=list;
00369 ctx->param=param;
00370 return ctx;
00371 }
00372
00373
00374
00375 void GWEN_List1_SortCtx_free(GWEN_LIST1_SORT_CTX *ctx) {
00376 if (ctx) {
00377 GWEN_FREE_OBJECT(ctx);
00378 }
00379 }
00380
00381
00382
00383 GWEN_LIST1_SORT_ELEM *GWEN_List1_SortElem_new(GWEN_LIST1_SORT_CTX *ctx, GWEN_LIST1_ELEMENT *elem) {
00384 GWEN_LIST1_SORT_ELEM *e;
00385
00386 GWEN_NEW_OBJECT(GWEN_LIST1_SORT_ELEM, e);
00387 e->context=ctx;
00388 e->element=elem;
00389 return e;
00390 }
00391
00392
00393
00394 void GWEN_List1_SortElem_free(GWEN_LIST1_SORT_ELEM *e) {
00395 if (e) {
00396 GWEN_FREE_OBJECT(e);
00397 }
00398 }
00399
00400
00401
00402 void GWEN_List1_Sort(GWEN_LIST1 *l, int ascending) {
00403 GWEN_LIST1_SORT_ELEM **tmpEntries;
00404 GWEN_LIST1_SORT_ELEM **psentry;
00405 GWEN_LIST1_ELEMENT *sentry;
00406 uint32_t count;
00407 uint32_t i;
00408 GWEN_LIST1_SORT_CTX *sortContext;
00409
00410 if (l->count<1)
00411 return;
00412
00413 count=l->count;
00414
00415 sortContext=GWEN_List1_SortCtx_new(l, ascending);
00416
00417
00418 tmpEntries=(GWEN_LIST1_SORT_ELEM **)malloc((count+1)* sizeof(GWEN_LIST1_SORT_ELEM*));
00419 assert(tmpEntries);
00420 psentry=tmpEntries;
00421
00422 sentry=l->firstElement;
00423 while(sentry) {
00424 GWEN_LIST1_ELEMENT *next;
00425 GWEN_LIST1_SORT_ELEM *se;
00426
00427 se=GWEN_List1_SortElem_new(sortContext, sentry);
00428 *(psentry++)=se;
00429 next=sentry->nextElement;
00430 sentry->prevElement=NULL;
00431 sentry->nextElement=NULL;
00432 sentry->listPtr=l;
00433 sentry=next;
00434 }
00435 *psentry=NULL;
00436
00437
00438 l->count=0;
00439 l->firstElement=NULL;
00440 l->lastElement=NULL;
00441
00442
00443 qsort(tmpEntries, count, sizeof(GWEN_LIST1_SORT_ELEM*), GWEN_List1__compar);
00444
00445
00446 psentry=tmpEntries;
00447
00448 for (i=0; i<=count; i++) {
00449 GWEN_LIST1_SORT_ELEM *se;
00450
00451 se=*psentry;
00452 if (se) {
00453 sentry=se->element;
00454 sentry->listPtr=NULL;
00455 GWEN_List1_Add(l, sentry);
00456 GWEN_List1_SortElem_free(se);
00457 *psentry=NULL;
00458 }
00459 psentry++;
00460 }
00461
00462 free(tmpEntries);
00463 GWEN_List1_SortCtx_free(sortContext);
00464 }
00465
00466
00467
00468
00469
00470