gwenhywfar  4.3.3
list1.c
Go to the documentation of this file.
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