gwenhywfar
4.3.3
|
00001 /*************************************************************************** 00002 begin : Sat Nov 15 2003 00003 copyright : (C) 2003 by Martin Preuss 00004 email : martin@libchipcard.de 00005 00006 *************************************************************************** 00007 * * 00008 * This library is free software; you can redistribute it and/or * 00009 * modify it under the terms of the GNU Lesser General Public * 00010 * License as published by the Free Software Foundation; either * 00011 * version 2.1 of the License, or (at your option) any later version. * 00012 * * 00013 * This library is distributed in the hope that it will be useful, * 00014 * but WITHOUT ANY WARRANTY; without even the implied warranty of * 00015 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * 00016 * Lesser General Public License for more details. * 00017 * * 00018 * You should have received a copy of the GNU Lesser General Public * 00019 * License along with this library; if not, write to the Free Software * 00020 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, * 00021 * MA 02111-1307 USA * 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 /* element is already part of another list */ 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 /* element is already part of another list */ 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 /* not part of any list */ 00141 DBG_ERROR(GWEN_LOGDOMAIN, "Element is not part of any list"); 00142 return -1; 00143 } 00144 00145 /* unlink from previous */ 00146 if (el->prevElement) 00147 el->prevElement->nextElement=el->nextElement; 00148 00149 /* unlink from next */ 00150 if (el->nextElement) 00151 el->nextElement->prevElement=el->prevElement; 00152 00153 /* unlink from list */ 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 /* sort entries into a linear pointer list */ 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 } /* while */ 00289 *psentry=NULL; 00290 00291 /* clear list */ 00292 l->count=0; 00293 l->firstElement=NULL; 00294 l->lastElement=NULL; 00295 00296 /* sort */ 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 /* sort entries back into GWEN_LIST1 according to temporary list */ 00303 psentry=tmpEntries; 00304 /* we use "<=count" because the list contains count+1 elements */ 00305 for (i=0; i<=count; i++) { 00306 if (*psentry) { 00307 (*psentry)->listPtr=NULL; 00308 GWEN_List1_Add(l, *psentry); 00309 } 00310 psentry++; 00311 } /* for */ 00312 00313 free(tmpEntries); 00314 } 00315 #endif 00316 00317 00318 00319 00320 00321 00322 00323 00324 00325 /* ------------------------------------------------------------------------------------------------- 00326 * Sort 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 /* sort entries into a linear pointer list */ 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 } /* while */ 00435 *psentry=NULL; 00436 00437 /* clear list */ 00438 l->count=0; 00439 l->firstElement=NULL; 00440 l->lastElement=NULL; 00441 00442 /* sort */ 00443 qsort(tmpEntries, count, sizeof(GWEN_LIST1_SORT_ELEM*), GWEN_List1__compar); 00444 00445 /* sort entries back into GWEN_LIST1 according to temporary list */ 00446 psentry=tmpEntries; 00447 /* we use "<=count" because the list contains count+1 elements */ 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 } /* for */ 00461 00462 free(tmpEntries); 00463 GWEN_List1_SortCtx_free(sortContext); 00464 } 00465 00466 00467 00468 00469 00470