idlist.c

Go to the documentation of this file.
00001 /***************************************************************************
00002  $RCSfile$
00003                              -------------------
00004     cvs         : $Id$
00005     begin       : Mon Mar 01 2004
00006     copyright   : (C) 2004 by Martin Preuss
00007     email       : martin@libchipcard.de
00008 
00009  ***************************************************************************
00010  *                                                                         *
00011  *   This library is free software; you can redistribute it and/or         *
00012  *   modify it under the terms of the GNU Lesser General Public            *
00013  *   License as published by the Free Software Foundation; either          *
00014  *   version 2.1 of the License, or (at your option) any later version.    *
00015  *                                                                         *
00016  *   This library is distributed in the hope that it will be useful,       *
00017  *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
00018  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU     *
00019  *   Lesser General Public License for more details.                       *
00020  *                                                                         *
00021  *   You should have received a copy of the GNU Lesser General Public      *
00022  *   License along with this library; if not, write to the Free Software   *
00023  *   Foundation, Inc., 59 Temple Place, Suite 330, Boston,                 *
00024  *   MA  02111-1307  USA                                                   *
00025  *                                                                         *
00026  ***************************************************************************/
00027 
00028 
00029 
00030 #ifdef HAVE_CONFIG_H
00031 # include <config.h>
00032 #endif
00033 
00034 
00035 #include "idlist_p.h"
00036 #include <gwenhywfar/debug.h>
00037 
00038 
00039 #include <stdlib.h>
00040 #include <assert.h>
00041 #include <string.h>
00042 
00043 
00044 GWEN_LIST_FUNCTIONS(GWEN_IDTABLE, GWEN_IdTable)
00045 /* No trailing semicolon here because this is a macro call */
00046 
00047 
00048 
00049 GWEN_IDTABLE *GWEN_IdTable_new(){
00050   GWEN_IDTABLE *idt;
00051 
00052   GWEN_NEW_OBJECT(GWEN_IDTABLE, idt);
00053   GWEN_LIST_INIT(GWEN_IDTABLE, idt);
00054 
00055   idt->freeEntries=GWEN_IDTABLE_MAXENTRIES;
00056   return idt;
00057 }
00058 
00059 
00060 
00061 void GWEN_IdTable_free(GWEN_IDTABLE *idt){
00062   if (idt) {
00063     GWEN_LIST_FINI(GWEN_IDTABLE, idt);
00064     GWEN_FREE_OBJECT(idt);
00065   }
00066 }
00067 
00068 
00069 
00070 int GWEN_IdTable_AddId(GWEN_IDTABLE *idt, uint32_t id){
00071   unsigned int i;
00072 
00073   assert(idt);
00074   assert(id);
00075 
00076   for (i=0; i<GWEN_IDTABLE_MAXENTRIES; i++) {
00077     if (idt->entries[i]==0) {
00078       idt->entries[i]=id;
00079       idt->freeEntries--;
00080       return 0;
00081     }
00082   } /* for */
00083   return -1;
00084 }
00085 
00086 
00087 
00088 int GWEN_IdTable_HasId(const GWEN_IDTABLE *idt, uint32_t id){
00089   unsigned int i;
00090 
00091   assert(idt);
00092   assert(id);
00093 
00094   for (i=0; i<GWEN_IDTABLE_MAXENTRIES; i++) {
00095     if (idt->entries[i]==id) {
00096       return 1;
00097     }
00098   } /* for */
00099   return 0;
00100 }
00101 
00102 
00103 
00104 int GWEN_IdTable_DelId(GWEN_IDTABLE *idt, uint32_t id){
00105   unsigned int i;
00106 
00107   assert(idt);
00108   assert(id);
00109 
00110   for (i=0; i<GWEN_IDTABLE_MAXENTRIES; i++) {
00111     if (idt->entries[i]==id) {
00112       idt->entries[i]=0;
00113       idt->freeEntries++;
00114       return 0;
00115     }
00116   } /* for */
00117   return -1;
00118 }
00119 
00120 
00121 
00122 int GWEN_IdTable_IsEmpty(const GWEN_IDTABLE *idt){
00123   assert(idt);
00124   return GWEN_IDTABLE_MAXENTRIES==idt->freeEntries;
00125 }
00126 
00127 
00128 
00129 int GWEN_IdTable_IsFull(const GWEN_IDTABLE *idt){
00130   assert(idt);
00131   return idt->freeEntries==0;
00132 }
00133 
00134 
00135 
00136 unsigned int GWEN_IdTable_GetCount(const GWEN_IDTABLE *idt){
00137   assert(idt);
00138   return GWEN_IDTABLE_MAXENTRIES-idt->freeEntries;
00139 }
00140 
00141 
00142 
00143 uint32_t GWEN_IdTable_GetFirstId(GWEN_IDTABLE *idt){
00144   unsigned int i;
00145 
00146   assert(idt);
00147   idt->current=0;
00148   for (i=0; i<GWEN_IDTABLE_MAXENTRIES; i++) {
00149     if (idt->entries[i]!=0) {
00150       idt->current=i;
00151       return idt->entries[i];
00152     }
00153   } /* for */
00154   return 0;
00155 }
00156 
00157 
00158 
00159 uint32_t GWEN_IdTable_GetNextId(GWEN_IDTABLE *idt){
00160   unsigned int i;
00161 
00162   assert(idt);
00163 
00164   for (i=idt->current+1; i<GWEN_IDTABLE_MAXENTRIES; i++) {
00165     if (idt->entries[i]!=0) {
00166       idt->current=i;
00167       return idt->entries[i];
00168     }
00169   } /* for */
00170   idt->current=GWEN_IDTABLE_MAXENTRIES;
00171   return 0;
00172 }
00173 
00174 
00175 
00176 uint32_t GWEN_IdTable_GetFirstId2(const GWEN_IDTABLE *idt,
00177                                           uint32_t *tabIdx){
00178   unsigned int i;
00179 
00180   assert(idt);
00181   for (i=0; i<GWEN_IDTABLE_MAXENTRIES; i++) {
00182     if (idt->entries[i]!=0) {
00183       *tabIdx=i;
00184       return idt->entries[i];
00185     }
00186   } /* for */
00187   return 0;
00188 }
00189 
00190 
00191 
00192 uint32_t GWEN_IdTable_GetNextId2(const GWEN_IDTABLE *idt,
00193                                          uint32_t *tabIdx){
00194   unsigned int i;
00195 
00196   assert(idt);
00197 
00198   for (i=(*tabIdx)+1; i<GWEN_IDTABLE_MAXENTRIES; i++) {
00199     if (idt->entries[i]!=0) {
00200       *tabIdx=i;
00201       return idt->entries[i];
00202     }
00203   } /* for */
00204   return 0;
00205 }
00206 
00207 
00208 
00209 
00210 
00211 
00212 GWEN_IDLIST *GWEN_IdList_new(){
00213   GWEN_IDLIST *idl;
00214 
00215   GWEN_NEW_OBJECT(GWEN_IDLIST, idl);
00216   idl->idTables=GWEN_IdTable_List_new();
00217   return idl;
00218 }
00219 
00220 
00221 
00222 void GWEN_IdList_free(GWEN_IDLIST *idl){
00223   if (idl) {
00224     GWEN_IdTable_List_free(idl->idTables);
00225     GWEN_FREE_OBJECT(idl);
00226   }
00227 }
00228 
00229 
00230 
00231 int GWEN_IdList_AddId(GWEN_IDLIST *idl, uint32_t id){
00232   GWEN_IDTABLE *idt;
00233 
00234   assert(idl);
00235 
00236   idl->current=0;
00237   idt=GWEN_IdTable_List_First(idl->idTables);
00238   /* find free table */
00239   while(idt) {
00240     if (!GWEN_IdTable_IsFull(idt))
00241       break;
00242     idt=GWEN_IdTable_List_Next(idt);
00243   } /* while */
00244 
00245   if (!idt) {
00246     idt=GWEN_IdTable_new();
00247     GWEN_IdTable_List_Add(idt, idl->idTables);;
00248   }
00249 
00250   GWEN_IdTable_AddId(idt, id);
00251   idl->entryCount++;
00252   return 0;
00253 }
00254 
00255 
00256 
00257 int GWEN_IdList_DelId(GWEN_IDLIST *idl, uint32_t id){
00258   GWEN_IDTABLE *idt;
00259 
00260   assert(idl);
00261 
00262   idl->current=0;
00263   idt=GWEN_IdTable_List_First(idl->idTables);
00264   /* find table */
00265   while(idt) {
00266     if (!GWEN_IdTable_DelId(idt, id)) {
00267       /* found a table which had this id */
00268       GWEN_IdList_Clean(idl);
00269       idl->entryCount--;
00270       return 0;
00271     }
00272     idt=GWEN_IdTable_List_Next(idt);
00273   } /* while */
00274   return -1;
00275 }
00276 
00277 
00278 
00279 int GWEN_IdList_HasId(const GWEN_IDLIST *idl, uint32_t id){
00280   GWEN_IDTABLE *idt;
00281 
00282   assert(idl);
00283 
00284   idt=GWEN_IdTable_List_First(idl->idTables);
00285   /* find free table */
00286   while(idt) {
00287     if (GWEN_IdTable_HasId(idt, id))
00288       return 1;
00289     idt=GWEN_IdTable_List_Next(idt);
00290   } /* while */
00291   return 0;
00292 }
00293 
00294 
00295 
00296 void GWEN_IdList_Clean(GWEN_IDLIST *idl) {
00297   GWEN_IDTABLE *idt;
00298 
00299   assert(idl);
00300   idl->current=0;
00301   idt=GWEN_IdTable_List_First(idl->idTables);
00302   /* find free table */
00303   while(idt) {
00304     GWEN_IDTABLE *next;
00305 
00306     next=GWEN_IdTable_List_Next(idt);
00307     if (GWEN_IdTable_IsEmpty(idt)) {
00308       GWEN_IdTable_List_Del(idt);
00309       GWEN_IdTable_free(idt);
00310     }
00311     idt=next;
00312   } /* while */
00313 }
00314 
00315 
00316 
00317 uint32_t GWEN_IdList_GetFirstId(GWEN_IDLIST *idl){
00318   GWEN_IDTABLE *idt;
00319 
00320   assert(idl);
00321 
00322   idt=GWEN_IdTable_List_First(idl->idTables);
00323   /* find free table */
00324   while(idt) {
00325     GWEN_IDTABLE *next;
00326     uint32_t id;
00327 
00328     next=GWEN_IdTable_List_Next(idt);
00329     id=GWEN_IdTable_GetFirstId(idt);
00330     if (id) {
00331       idl->current=idt;
00332       return id;
00333     }
00334     idt=next;
00335   } /* while */
00336 
00337   return 0;
00338 }
00339 
00340 
00341 
00342 uint32_t GWEN_IdList_GetNextId(GWEN_IDLIST *idl){
00343   GWEN_IDTABLE *idt;
00344   uint32_t id;
00345 
00346   assert(idl);
00347 
00348   idt=idl->current;
00349   if (idt) {
00350     id=GWEN_IdTable_GetNextId(idt);
00351     if (id) {
00352       idl->current=idt;
00353       return id;
00354     }
00355   }
00356   else {
00357     idl->current=0;
00358     return 0;
00359   }
00360 
00361   idt=GWEN_IdTable_List_Next(idt);
00362   while (idt) {
00363     id=GWEN_IdTable_GetFirstId(idt);
00364     if (id) {
00365       idl->current=idt;
00366       return id;
00367     }
00368     idt=GWEN_IdTable_List_Next(idt);
00369   } /* while */
00370 
00371   idl->current=0;
00372   return 0;
00373 }
00374 
00375 
00376 
00377 int GWEN_IdList_Sort(GWEN_IDLIST *idl){
00378   GWEN_IDTABLE *idt;
00379   unsigned int cnt;
00380   uint32_t *ptr;
00381   unsigned int i;
00382 
00383   assert(idl);
00384 
00385   /* count ids */
00386   idt=GWEN_IdTable_List_First(idl->idTables);
00387   cnt=0;
00388   while(idt) {
00389     GWEN_IDTABLE *next;
00390 
00391     next=GWEN_IdTable_List_Next(idt);
00392     cnt+=GWEN_IdTable_GetCount(idt);
00393     idt=next;
00394   } /* while */
00395 
00396   if (!cnt)
00397     return 0;
00398 
00399   /* move ids to a temporary list */
00400   ptr=(uint32_t*)malloc(sizeof(uint32_t)*cnt);
00401   assert(ptr);
00402 
00403   for (i=0; i<cnt; i++) {
00404     uint32_t id;
00405 
00406     if (i==0)
00407       id=GWEN_IdList_GetFirstId(idl);
00408     else
00409       id=GWEN_IdList_GetNextId(idl);
00410     assert(id);
00411     ptr[i]=id;
00412   } /* for */
00413 
00414   GWEN_IdTable_List_Clear(idl->idTables);
00415   idl->current=0;
00416 
00417   /* sort temporary list */
00418   while(1) {
00419     int rpl;
00420 
00421     rpl=0;
00422     for (i=0; i<(cnt-1); i++) {
00423       if (ptr[i]>ptr[i+1]) {
00424         uint32_t id;
00425 
00426         id=ptr[i];
00427         ptr[i]=ptr[i+1];
00428         ptr[i+1]=id;
00429         rpl=1;
00430       }
00431     } /* for */
00432     if (!rpl)
00433       break;
00434   } /* while */
00435 
00436   /* move back from temporary list */
00437   for (i=0; i<cnt; i++) {
00438     GWEN_IdList_AddId(idl, ptr[i]);
00439   }
00440   free(ptr);
00441 
00442   return 0;
00443 }
00444 
00445 
00446 
00447 void GWEN_IdList_Clear(GWEN_IDLIST *idl){
00448   assert(idl);
00449   GWEN_IdTable_List_Clear(idl->idTables);
00450   idl->entryCount=0;
00451   idl->current=0;
00452 }
00453 
00454 
00455 
00456 GWEN_IDLIST *GWEN_IdList_dup(const GWEN_IDLIST *idl){
00457   GWEN_IDLIST *nidl;
00458   GWEN_IDTABLE *idt;
00459 
00460   assert(idl);
00461   nidl=GWEN_IdList_new();
00462 
00463   idt=GWEN_IdTable_List_First(idl->idTables);
00464   while(idt) {
00465     if (idt->freeEntries!=GWEN_IDTABLE_MAXENTRIES){
00466       int i;
00467 
00468       for (i=0; i<GWEN_IDTABLE_MAXENTRIES; i++) {
00469         if (idt->entries[i]!=0)
00470           GWEN_IdList_AddId(nidl, idt->entries[i]);
00471       }
00472     }
00473     idt=GWEN_IdTable_List_Next(idt);
00474   }
00475 
00476   return nidl;
00477 }
00478 
00479 
00480 
00481 uint32_t GWEN_IdList_GetFirstId2(const GWEN_IDLIST *idl,
00482                                          uint32_t *pos){
00483   GWEN_IDTABLE *idt;
00484   int tabNum=0;
00485 
00486   assert(idl);
00487 
00488   idt=GWEN_IdTable_List_First(idl->idTables);
00489   /* find free table */
00490   while(idt) {
00491     GWEN_IDTABLE *next;
00492     uint32_t id;
00493     uint32_t tabIdx;
00494 
00495     next=GWEN_IdTable_List_Next(idt);
00496     id=GWEN_IdTable_GetFirstId2(idt, &tabIdx);
00497     if (id) {
00498       *pos=(tabNum*GWEN_IDTABLE_MAXENTRIES)+tabIdx;
00499       return id;
00500     }
00501     tabNum++;
00502     idt=next;
00503   } /* while */
00504 
00505   return 0;
00506 }
00507 
00508 
00509 
00510 uint32_t GWEN_IdList_GetNextId2(const GWEN_IDLIST *idl,
00511                                         uint32_t *pos){
00512   GWEN_IDTABLE *idt;
00513   int i;
00514   int tabNum;
00515   uint32_t tabIdx;
00516 
00517   assert(idl);
00518   tabNum=(*pos)/GWEN_IDTABLE_MAXENTRIES;
00519   tabIdx=(*pos)%GWEN_IDTABLE_MAXENTRIES;
00520 
00521   /* seek table */
00522   i=tabNum;
00523   idt=GWEN_IdTable_List_First(idl->idTables);
00524   while(i--) idt=GWEN_IdTable_List_Next(idt);
00525   assert(idt);
00526 
00527   while(idt) {
00528     GWEN_IDTABLE *next;
00529     uint32_t id;
00530 
00531     next=GWEN_IdTable_List_Next(idt);
00532     id=GWEN_IdTable_GetNextId2(idt, &tabIdx);
00533     if (id) {
00534       *pos=(tabNum*GWEN_IDTABLE_MAXENTRIES)+tabIdx;
00535       return id;
00536     }
00537     tabNum++;
00538     idt=next;
00539   } /* while */
00540 
00541   return 0;
00542 }
00543 
00544 
00545 
00546 
00547 
00548 
00549 
00550 
00551 
00552 
00553 

Generated on Mon Jan 25 12:56:01 2010 for gwenhywfar by  doxygen 1.5.6