idlist64.c

Go to the documentation of this file.
00001 /***************************************************************************
00002  $RCSfile$
00003                              -------------------
00004     cvs         : $Id: idlist64.c 1102 2006-12-30 19:39:37Z martin $
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 "idlist64_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_IDTABLE64, GWEN_IdTable64)
00045 /* No trailing semicolon here because this is a macro call */
00046 
00047 
00048 
00049 GWEN_IDTABLE64 *GWEN_IdTable64_new(){
00050   GWEN_IDTABLE64 *idt;
00051 
00052   GWEN_NEW_OBJECT(GWEN_IDTABLE64, idt);
00053   idt->refCount=1;
00054   GWEN_LIST_INIT(GWEN_IDTABLE64, idt);
00055 
00056   idt->freeEntries=GWEN_IDTABLE64_MAXENTRIES;
00057   return idt;
00058 }
00059 
00060 
00061 
00062 void GWEN_IdTable64_free(GWEN_IDTABLE64 *idt){
00063   if (idt) {
00064     assert(idt->refCount);
00065     if (--(idt->refCount)==0) {
00066       GWEN_LIST_FINI(GWEN_IDTABLE64, idt);
00067       GWEN_FREE_OBJECT(idt);
00068     }
00069   }
00070 }
00071 
00072 
00073 
00074 void GWEN_IdTable64_Attach(GWEN_IDTABLE64 *idt){
00075   assert(idt);
00076   assert(idt->refCount);
00077   idt->refCount++;
00078 }
00079 
00080 
00081 
00082 int GWEN_IdTable64_AddId(GWEN_IDTABLE64 *idt, uint64_t id){
00083   unsigned int i;
00084 
00085   assert(idt);
00086   assert(id);
00087 
00088   for (i=0; i<GWEN_IDTABLE64_MAXENTRIES; i++) {
00089     if (idt->entries[i]==0) {
00090       idt->entries[i]=id;
00091       idt->freeEntries--;
00092       return 0;
00093     }
00094   } /* for */
00095   return -1;
00096 }
00097 
00098 
00099 
00100 int GWEN_IdTable64_HasId(const GWEN_IDTABLE64 *idt, uint64_t id){
00101   unsigned int i;
00102 
00103   assert(idt);
00104   assert(id);
00105 
00106   for (i=0; i<GWEN_IDTABLE64_MAXENTRIES; i++) {
00107     if (idt->entries[i]==id) {
00108       return 1;
00109     }
00110   } /* for */
00111   return 0;
00112 }
00113 
00114 
00115 
00116 int GWEN_IdTable64_DelId(GWEN_IDTABLE64 *idt, uint64_t id){
00117   unsigned int i;
00118 
00119   assert(idt);
00120   assert(id);
00121 
00122   for (i=0; i<GWEN_IDTABLE64_MAXENTRIES; i++) {
00123     if (idt->entries[i]==id) {
00124       idt->entries[i]=0;
00125       idt->freeEntries++;
00126       return 0;
00127     }
00128   } /* for */
00129   return -1;
00130 }
00131 
00132 
00133 
00134 int GWEN_IdTable64_IsEmpty(const GWEN_IDTABLE64 *idt){
00135   assert(idt);
00136   return GWEN_IDTABLE64_MAXENTRIES==idt->freeEntries;
00137 }
00138 
00139 
00140 
00141 int GWEN_IdTable64_IsFull(const GWEN_IDTABLE64 *idt){
00142   assert(idt);
00143   return idt->freeEntries==0;
00144 }
00145 
00146 
00147 
00148 unsigned int GWEN_IdTable64_GetCount(const GWEN_IDTABLE64 *idt){
00149   assert(idt);
00150   return GWEN_IDTABLE64_MAXENTRIES-idt->freeEntries;
00151 }
00152 
00153 
00154 
00155 uint64_t GWEN_IdTable64_GetFirstId(GWEN_IDTABLE64 *idt){
00156   unsigned int i;
00157 
00158   assert(idt);
00159   idt->current=0;
00160   for (i=0; i<GWEN_IDTABLE64_MAXENTRIES; i++) {
00161     if (idt->entries[i]!=0) {
00162       idt->current=i;
00163       return idt->entries[i];
00164     }
00165   } /* for */
00166   return 0;
00167 }
00168 
00169 
00170 
00171 uint64_t GWEN_IdTable64_GetNextId(GWEN_IDTABLE64 *idt){
00172   unsigned int i;
00173 
00174   assert(idt);
00175 
00176   for (i=idt->current+1; i<GWEN_IDTABLE64_MAXENTRIES; i++) {
00177     if (idt->entries[i]!=0) {
00178       idt->current=i;
00179       return idt->entries[i];
00180     }
00181   } /* for */
00182   idt->current=GWEN_IDTABLE64_MAXENTRIES;
00183   return 0;
00184 }
00185 
00186 
00187 
00188 uint64_t GWEN_IdTable64_GetFirstId2(const GWEN_IDTABLE64 *idt,
00189                                           uint64_t *tabIdx){
00190   unsigned int i;
00191 
00192   assert(idt);
00193   for (i=0; i<GWEN_IDTABLE64_MAXENTRIES; i++) {
00194     if (idt->entries[i]!=0) {
00195       *tabIdx=i;
00196       return idt->entries[i];
00197     }
00198   } /* for */
00199   return 0;
00200 }
00201 
00202 
00203 
00204 uint64_t GWEN_IdTable64_GetNextId2(const GWEN_IDTABLE64 *idt,
00205                                          uint64_t *tabIdx){
00206   unsigned int i;
00207 
00208   assert(idt);
00209 
00210   for (i=(*tabIdx)+1; i<GWEN_IDTABLE64_MAXENTRIES; i++) {
00211     if (idt->entries[i]!=0) {
00212       *tabIdx=i;
00213       return idt->entries[i];
00214     }
00215   } /* for */
00216   return 0;
00217 }
00218 
00219 
00220 
00221 
00222 
00223 
00224 GWEN_IDLIST64 *GWEN_IdList64_new(){
00225   GWEN_IDLIST64 *idl;
00226 
00227   GWEN_NEW_OBJECT(GWEN_IDLIST64, idl);
00228   idl->refCount=1;
00229   idl->idTables=GWEN_IdTable64_List_new();
00230   return idl;
00231 }
00232 
00233 
00234 
00235 void GWEN_IdList64_Attach(GWEN_IDLIST64 *idl) {
00236   assert(idl);
00237   assert(idl->refCount);
00238   idl->refCount++;
00239 }
00240 
00241 
00242 
00243 void GWEN_IdList64_free(GWEN_IDLIST64 *idl){
00244   if (idl) {
00245     assert(idl->refCount);
00246     if (--(idl->refCount)==0) {
00247       GWEN_IdTable64_List_free(idl->idTables);
00248       GWEN_FREE_OBJECT(idl);
00249     }
00250   }
00251 }
00252 
00253 
00254 
00255 int GWEN_IdList64_AddId(GWEN_IDLIST64 *idl, uint64_t id){
00256   GWEN_IDTABLE64 *idt;
00257 
00258   assert(idl);
00259 
00260   idl->current=0;
00261   idt=GWEN_IdTable64_List_First(idl->idTables);
00262   /* find free table */
00263   while(idt) {
00264     if (!GWEN_IdTable64_IsFull(idt))
00265       break;
00266     idt=GWEN_IdTable64_List_Next(idt);
00267   } /* while */
00268 
00269   if (!idt) {
00270     idt=GWEN_IdTable64_new();
00271     GWEN_IdTable64_List_Add(idt, idl->idTables);;
00272   }
00273 
00274   GWEN_IdTable64_AddId(idt, id);
00275   idl->entryCount++;
00276   return 0;
00277 }
00278 
00279 
00280 
00281 int GWEN_IdList64_DelId(GWEN_IDLIST64 *idl, uint64_t id){
00282   GWEN_IDTABLE64 *idt;
00283 
00284   assert(idl);
00285 
00286   idl->current=0;
00287   idt=GWEN_IdTable64_List_First(idl->idTables);
00288   /* find table */
00289   while(idt) {
00290     if (!GWEN_IdTable64_DelId(idt, id)) {
00291       /* found a table which had this id */
00292       GWEN_IdList64_Clean(idl);
00293       idl->entryCount--;
00294       return 0;
00295     }
00296     idt=GWEN_IdTable64_List_Next(idt);
00297   } /* while */
00298   return -1;
00299 }
00300 
00301 
00302 
00303 int GWEN_IdList64_HasId(const GWEN_IDLIST64 *idl, uint64_t id){
00304   GWEN_IDTABLE64 *idt;
00305 
00306   assert(idl);
00307 
00308   idt=GWEN_IdTable64_List_First(idl->idTables);
00309   /* find free table */
00310   while(idt) {
00311     if (GWEN_IdTable64_HasId(idt, id))
00312       return 1;
00313     idt=GWEN_IdTable64_List_Next(idt);
00314   } /* while */
00315   return 0;
00316 }
00317 
00318 
00319 
00320 void GWEN_IdList64_Clean(GWEN_IDLIST64 *idl) {
00321   GWEN_IDTABLE64 *idt;
00322 
00323   assert(idl);
00324   idl->current=0;
00325   idt=GWEN_IdTable64_List_First(idl->idTables);
00326   /* free empty tables */
00327   while(idt) {
00328     GWEN_IDTABLE64 *next;
00329 
00330     next=GWEN_IdTable64_List_Next(idt);
00331     if (GWEN_IdTable64_IsEmpty(idt)) {
00332       /*GWEN_IdTable64_List_Del(idt);*/
00333       GWEN_IdTable64_free(idt);
00334     }
00335     idt=next;
00336   } /* while */
00337 }
00338 
00339 
00340 
00341 uint64_t GWEN_IdList64_GetFirstId(GWEN_IDLIST64 *idl){
00342   GWEN_IDTABLE64 *idt;
00343 
00344   assert(idl);
00345 
00346   idt=GWEN_IdTable64_List_First(idl->idTables);
00347   /* find table which contains the first id */
00348   while(idt) {
00349     GWEN_IDTABLE64 *next;
00350     uint64_t id;
00351 
00352     next=GWEN_IdTable64_List_Next(idt);
00353     id=GWEN_IdTable64_GetFirstId(idt);
00354     if (id) {
00355       idl->current=idt;
00356       return id;
00357     }
00358     idt=next;
00359   } /* while */
00360 
00361   return 0;
00362 }
00363 
00364 
00365 
00366 uint64_t GWEN_IdList64_GetNextId(GWEN_IDLIST64 *idl){
00367   GWEN_IDTABLE64 *idt;
00368   uint64_t id;
00369 
00370   assert(idl);
00371 
00372   idt=idl->current;
00373   if (idt) {
00374     id=GWEN_IdTable64_GetNextId(idt);
00375     if (id) {
00376       idl->current=idt;
00377       return id;
00378     }
00379   }
00380   else {
00381     idl->current=0;
00382     return 0;
00383   }
00384 
00385   idt=GWEN_IdTable64_List_Next(idt);
00386   while (idt) {
00387     id=GWEN_IdTable64_GetFirstId(idt);
00388     if (id) {
00389       idl->current=idt;
00390       return id;
00391     }
00392     idt=GWEN_IdTable64_List_Next(idt);
00393   } /* while */
00394 
00395   idl->current=0;
00396   return 0;
00397 }
00398 
00399 
00400 
00401 int GWEN_IdList64_Sort(GWEN_IDLIST64 *idl){
00402   GWEN_IDLIST64_ITERATOR *it;
00403   GWEN_IDTABLE64 *idt;
00404   unsigned int cnt;
00405   uint64_t *ptr;
00406   unsigned int i;
00407 
00408   assert(idl);
00409 
00410   /* count ids */
00411   idt=GWEN_IdTable64_List_First(idl->idTables);
00412   cnt=0;
00413   while(idt) {
00414     GWEN_IDTABLE64 *next;
00415 
00416     next=GWEN_IdTable64_List_Next(idt);
00417     cnt+=GWEN_IdTable64_GetCount(idt);
00418     idt=next;
00419   } /* while */
00420 
00421   if (!cnt)
00422     return 0;
00423 
00424   /* move ids to a temporary list */
00425   ptr=(uint64_t*)malloc(sizeof(uint64_t)*cnt);
00426   assert(ptr);
00427 
00428   it=GWEN_IdList64_Iterator_new(idl);
00429   for (i=0; i<cnt; i++) {
00430     uint64_t id;
00431 
00432     if (i==0)
00433       id=GWEN_IdList64_Iterator_GetFirstId(it);
00434     else
00435       id=GWEN_IdList64_Iterator_GetNextId(it);
00436     assert(id);
00437     ptr[i]=id;
00438   } /* for */
00439   GWEN_IdList64_Iterator_free(it);
00440 
00441   /* remove all tables (we will add sorted tables later) */
00442   GWEN_IdTable64_List_Clear(idl->idTables);
00443   idl->current=0;
00444 
00445   /* sort temporary list */
00446   while(1) {
00447     int rpl;
00448 
00449     rpl=0;
00450     for (i=0; i<(cnt-1); i++) {
00451       if (ptr[i]>ptr[i+1]) {
00452         uint64_t id;
00453 
00454         id=ptr[i];
00455         ptr[i]=ptr[i+1];
00456         ptr[i+1]=id;
00457         rpl=1;
00458       }
00459     } /* for */
00460     if (!rpl)
00461       break;
00462   } /* while */
00463 
00464   /* move back sorted list of ids from temporary list */
00465   for (i=0; i<cnt; i++) {
00466     GWEN_IdList64_AddId(idl, ptr[i]);
00467   }
00468   free(ptr);
00469 
00470   return 0;
00471 }
00472 
00473 
00474 
00475 void GWEN_IdList64_Clear(GWEN_IDLIST64 *idl){
00476   assert(idl);
00477   GWEN_IdTable64_List_Clear(idl->idTables);
00478   idl->entryCount=0;
00479   idl->current=0;
00480 }
00481 
00482 
00483 
00484 GWEN_IDLIST64 *GWEN_IdList64_dup(const GWEN_IDLIST64 *idl){
00485   GWEN_IDLIST64 *nidl;
00486   GWEN_IDTABLE64 *idt;
00487 
00488   assert(idl);
00489   nidl=GWEN_IdList64_new();
00490 
00491   idt=GWEN_IdTable64_List_First(idl->idTables);
00492   while(idt) {
00493     if (idt->freeEntries!=GWEN_IDTABLE64_MAXENTRIES){
00494       int i;
00495 
00496       for (i=0; i<GWEN_IDTABLE64_MAXENTRIES; i++) {
00497         if (idt->entries[i]!=0)
00498           GWEN_IdList64_AddId(nidl, idt->entries[i]);
00499       }
00500     }
00501     idt=GWEN_IdTable64_List_Next(idt);
00502   }
00503 
00504   return nidl;
00505 }
00506 
00507 
00508 
00509 uint64_t GWEN_IdList64_GetFirstId2(const GWEN_IDLIST64 *idl,
00510                                          uint64_t *pos){
00511   GWEN_IDTABLE64 *idt;
00512   int tabNum=0;
00513 
00514   assert(idl);
00515 
00516   idt=GWEN_IdTable64_List_First(idl->idTables);
00517   /* find free table */
00518   while(idt) {
00519     GWEN_IDTABLE64 *next;
00520     uint64_t id;
00521     uint64_t tabIdx;
00522 
00523     next=GWEN_IdTable64_List_Next(idt);
00524     id=GWEN_IdTable64_GetFirstId2(idt, &tabIdx);
00525     if (id) {
00526       *pos=(tabNum*GWEN_IDTABLE64_MAXENTRIES)+tabIdx;
00527       return id;
00528     }
00529     tabNum++;
00530     idt=next;
00531   } /* while */
00532 
00533   return 0;
00534 }
00535 
00536 
00537 
00538 uint64_t GWEN_IdList64_GetNextId2(const GWEN_IDLIST64 *idl,
00539                                   uint64_t *pos){
00540   GWEN_IDTABLE64 *idt;
00541   int i;
00542   int tabNum;
00543   uint64_t tabIdx;
00544 
00545   assert(idl);
00546   tabNum=(*pos)/GWEN_IDTABLE64_MAXENTRIES;
00547   tabIdx=(*pos)%GWEN_IDTABLE64_MAXENTRIES;
00548 
00549   /* seek table */
00550   i=tabNum;
00551   idt=GWEN_IdTable64_List_First(idl->idTables);
00552   while(i--) idt=GWEN_IdTable64_List_Next(idt);
00553   assert(idt);
00554 
00555   while(idt) {
00556     GWEN_IDTABLE64 *next;
00557     uint64_t id;
00558 
00559     next=GWEN_IdTable64_List_Next(idt);
00560     id=GWEN_IdTable64_GetNextId2(idt, &tabIdx);
00561     if (id) {
00562       *pos=(tabNum*GWEN_IDTABLE64_MAXENTRIES)+tabIdx;
00563       return id;
00564     }
00565     tabNum++;
00566     idt=next;
00567   } /* while */
00568 
00569   return 0;
00570 }
00571 
00572 
00573 
00574 GWEN_IDLIST64_ITERATOR *GWEN_IdList64_Iterator_new(GWEN_IDLIST64 *idl) {
00575   GWEN_IDLIST64_ITERATOR *it;
00576 
00577   assert(idl);
00578   GWEN_NEW_OBJECT(GWEN_IDLIST64_ITERATOR, it);
00579 
00580   GWEN_IdList64_Attach(idl);
00581   it->list=idl;
00582 
00583   return it;
00584 }
00585 
00586 
00587 
00588 void GWEN_IdList64_Iterator_free(GWEN_IDLIST64_ITERATOR *it) {
00589   if (it) {
00590     if (it->currentTable)
00591       GWEN_IdTable64_free(it->currentTable);
00592     GWEN_IdList64_free(it->list);
00593     GWEN_FREE_OBJECT(it);
00594   }
00595 }
00596 
00597 
00598 
00599 uint64_t GWEN_IdList64_Iterator_GetFirstId(GWEN_IDLIST64_ITERATOR *it) {
00600   GWEN_IDTABLE64 *idt;
00601 
00602   assert(it);
00603 
00604   idt=GWEN_IdTable64_List_First(it->list->idTables);
00605   /* find table which contains the first id */
00606   while(idt) {
00607     GWEN_IDTABLE64 *next;
00608     unsigned int i;
00609 
00610     next=GWEN_IdTable64_List_Next(idt);
00611 
00612     for (i=0; i<GWEN_IDTABLE64_MAXENTRIES; i++) {
00613       if (idt->entries[i]!=0) {
00614         /* attach to new table */
00615         GWEN_IdTable64_Attach(idt);
00616         /* detach from previous table */
00617         GWEN_IdTable64_free(it->currentTable);
00618         /* store current table and index */
00619         it->currentTable=idt;
00620         it->currentIndex=i;
00621         /* return id */
00622         return idt->entries[i];
00623       }
00624     } /* for */
00625 
00626     idt=next;
00627   } /* while */
00628 
00629   GWEN_IdTable64_free(it->currentTable);
00630   it->currentTable=NULL;
00631   it->currentIndex=0;
00632 
00633   return 0;
00634 }
00635 
00636 
00637 
00638 uint64_t GWEN_IdList64_Iterator_GetNextId(GWEN_IDLIST64_ITERATOR *it) {
00639   GWEN_IDTABLE64 *idt;
00640   uint32_t startIdx;
00641 
00642   assert(it);
00643 
00644   idt=it->currentTable;
00645   startIdx=it->currentIndex+1;
00646 
00647   /* find table which contains the next id */
00648   while(idt) {
00649     GWEN_IDTABLE64 *next;
00650     unsigned int i;
00651 
00652     next=GWEN_IdTable64_List_Next(idt);
00653 
00654     for (i=startIdx; i<GWEN_IDTABLE64_MAXENTRIES; i++) {
00655       if (idt->entries[i]!=0) {
00656         /* attach to new table */
00657         GWEN_IdTable64_Attach(idt);
00658         /* detach from previous table */
00659         GWEN_IdTable64_free(it->currentTable);
00660         /* store current table and index */
00661         it->currentTable=idt;
00662         it->currentIndex=i;
00663         /* return id */
00664         return idt->entries[i];
00665       }
00666     } /* for */
00667 
00668     /* reset start index to start at 0 with next table */
00669     startIdx=0;
00670     idt=next;
00671   } /* while */
00672 
00673   GWEN_IdTable64_free(it->currentTable);
00674   it->currentTable=NULL;
00675   it->currentIndex=0;
00676 
00677   return 0;
00678 }
00679 
00680 
00681 
00682 
00683 
00684 
00685 
00686 
00687 
00688 
00689 
00690 
00691 
00692 

Generated on Fri Apr 11 01:53:46 2008 for gwenhywfar by  doxygen 1.5.5