gwenhywfar  4.7.0beta
idlist64.c
Go to the documentation of this file.
1 /***************************************************************************
2  begin : Mon Mar 01 2004
3  copyright : (C) 2004 by Martin Preuss
4  email : martin@libchipcard.de
5 
6  ***************************************************************************
7  * *
8  * This library is free software; you can redistribute it and/or *
9  * modify it under the terms of the GNU Lesser General Public *
10  * License as published by the Free Software Foundation; either *
11  * version 2.1 of the License, or (at your option) any later version. *
12  * *
13  * This library is distributed in the hope that it will be useful, *
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of *
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
16  * Lesser General Public License for more details. *
17  * *
18  * You should have received a copy of the GNU Lesser General Public *
19  * License along with this library; if not, write to the Free Software *
20  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, *
21  * MA 02111-1307 USA *
22  * *
23  ***************************************************************************/
24 
25 
26 
27 #ifdef HAVE_CONFIG_H
28 # include <config.h>
29 #endif
30 
31 #define DISABLE_DEBUGLOG
32 
33 
34 #include "idlist64_p.h"
35 #include <gwenhywfar/debug.h>
36 
37 
38 #include <stdlib.h>
39 #include <assert.h>
40 #include <string.h>
41 
42 
43 
44 GWEN_IDTABLE64 *GWEN_IdTable64_new(void){
45  GWEN_IDTABLE64 *idt;
46 
47  GWEN_NEW_OBJECT(GWEN_IDTABLE64, idt);
48  idt->refCount=1;
49 
50  idt->freeEntries=GWEN_IDTABLE64_MAXENTRIES;
51  return idt;
52 }
53 
54 
55 
56 void GWEN_IdTable64_free(GWEN_IDTABLE64 *idt){
57  if (idt) {
58  assert(idt->refCount);
59  if (--(idt->refCount)==0) {
60  GWEN_FREE_OBJECT(idt);
61  }
62  }
63 }
64 
65 
66 
67 #if 0
68 void GWEN_IdTable64_Attach(GWEN_IDTABLE64 *idt){
69  assert(idt);
70  assert(idt->refCount);
71  idt->refCount++;
72 }
73 #endif
74 
75 
76 
77 static inline int GWEN_IdTable64_AddId(GWEN_IDTABLE64 *idt, uint64_t id){
78  unsigned int i;
79 
80  for (i=0; i<GWEN_IDTABLE64_MAXENTRIES; i++) {
81  if (idt->entries[i]==0) {
82  idt->entries[i]=id;
83  idt->freeEntries--;
84  return 0;
85  }
86  } /* for */
87  return -1;
88 }
89 
90 
91 
92 static inline int GWEN_IdTable64_AppendId(GWEN_IDTABLE64 *idt, uint64_t id){
93  if (idt->freeEntries) {
94  unsigned int i;
95 
96  i=GWEN_IDTABLE64_MAXENTRIES-idt->freeEntries;
97  idt->entries[i]=id;
98  idt->freeEntries--;
99  return 0;
100  }
101  else
102  return -1;
103 }
104 
105 
106 
107 static inline int GWEN_IdTable64_HasId(const GWEN_IDTABLE64 *idt, uint64_t id){
108  unsigned int i;
109 
110  for (i=0; i<GWEN_IDTABLE64_MAXENTRIES; i++) {
111  if (idt->entries[i]==id) {
112  return 1;
113  }
114  } /* for */
115  return 0;
116 }
117 
118 
119 
120 static inline int GWEN_IdTable64_DelId(GWEN_IDTABLE64 *idt, uint64_t id){
121  unsigned int i;
122 
123  for (i=0; i<GWEN_IDTABLE64_MAXENTRIES; i++) {
124  if (idt->entries[i]==id) {
125  idt->entries[i]=0;
126  idt->freeEntries++;
127  return 0;
128  }
129  } /* for */
130  return -1;
131 }
132 
133 
134 
135 static inline int GWEN_IdTable64_IsEmpty(const GWEN_IDTABLE64 *idt){
136  return GWEN_IDTABLE64_MAXENTRIES==idt->freeEntries;
137 }
138 
139 
140 
141 static inline int GWEN_IdTable64_IsFull(const GWEN_IDTABLE64 *idt){
142  return idt->freeEntries==0;
143 }
144 
145 
146 
147 static inline unsigned int GWEN_IdTable64_GetCount(const GWEN_IDTABLE64 *idt){
148  return GWEN_IDTABLE64_MAXENTRIES-idt->freeEntries;
149 }
150 
151 
152 
153 static inline uint64_t GWEN_IdTable64_GetFirstId(GWEN_IDTABLE64 *idt){
154  unsigned int i;
155 
156  assert(idt);
157  idt->current=0;
158  for (i=0; i<GWEN_IDTABLE64_MAXENTRIES; i++) {
159  if (idt->entries[i]!=0) {
160  idt->current=i;
161  return idt->entries[i];
162  }
163  } /* for */
164  return 0;
165 }
166 
167 
168 
169 static inline uint64_t GWEN_IdTable64_GetNextId(GWEN_IDTABLE64 *idt){
170  unsigned int i;
171 
172  for (i=idt->current+1; i<GWEN_IDTABLE64_MAXENTRIES; i++) {
173  if (idt->entries[i]!=0) {
174  idt->current=i;
175  return idt->entries[i];
176  }
177  } /* for */
178  idt->current=GWEN_IDTABLE64_MAXENTRIES;
179  return 0;
180 }
181 
182 
183 
184 static inline uint64_t GWEN_IdTable64_GetFirstId2(const GWEN_IDTABLE64 *idt,
185  uint64_t *tabIdx){
186  unsigned int i;
187 
188  for (i=0; i<GWEN_IDTABLE64_MAXENTRIES; i++) {
189  if (idt->entries[i]!=0) {
190  *tabIdx=i;
191  return idt->entries[i];
192  }
193  } /* for */
194  return 0;
195 }
196 
197 
198 
199 static inline uint64_t GWEN_IdTable64_GetNextId2(const GWEN_IDTABLE64 *idt,
200  uint64_t *tabIdx){
201  unsigned int i;
202 
203  for (i=(*tabIdx)+1; i<GWEN_IDTABLE64_MAXENTRIES; i++) {
204  if (idt->entries[i]!=0) {
205  *tabIdx=i;
206  return idt->entries[i];
207  }
208  } /* for */
209  return 0;
210 }
211 
212 
213 
214 
215 
216 
218  GWEN_IDLIST64 *idl;
219 
221  idl->refCount=1;
222  return idl;
223 }
224 
225 
226 
228  assert(idl);
229  assert(idl->refCount);
230  idl->refCount++;
231 }
232 
233 
234 
236  if (idl) {
237  assert(idl->refCount);
238  if (idl->refCount==1) {
239  GWEN_IdList64_Clear(idl);
240  idl->refCount=0;
241  GWEN_FREE_OBJECT(idl);
242  }
243  else
244  idl->refCount--;
245  }
246 }
247 
248 
249 
250 void GWEN_IdList64_AddTable(GWEN_IDLIST64 *idl, GWEN_IDTABLE64 *idt) {
251  GWEN_IDTABLE64 **tablePtr;
252  int idx;
253 
254  assert(idl);
255 
256  tablePtr=idl->pIdTablePointers;
257  for (idx=0, tablePtr=idl->pIdTablePointers; idx<idl->idTableCount; idx++, tablePtr++) {
258  if (*tablePtr==NULL)
259  break;
260  } /* while */
261 
262  if (idx>=idl->idTableCount) {
263  uint32_t newCount;
264  GWEN_IDTABLE64 **newPtr;
265 
266  /* resize */
267  newCount=idl->idTableCount+GWEN_IDLIST64_STEP;
268  newPtr=(GWEN_IDTABLE64 **)realloc(idl->pIdTablePointers, sizeof(GWEN_IDTABLE64*)*newCount);
269  assert(newPtr);
270  /* init new pointers */
271  memset((void*)(newPtr+idl->idTableCount),
272  0,
273  sizeof(GWEN_IDTABLE64*)*(newCount-idl->idTableCount));
274  idl->pIdTablePointers=newPtr;
275  idl->pIdTablePointers[idl->idTableCount]=idt;
276  idl->lastTableIdx=idl->idTableCount;
277  idl->idTableCount=newCount;
278  }
279  else {
280  idl->pIdTablePointers[idx]=idt;
281  idl->lastTableIdx=idx;
282  }
283 }
284 
285 
286 
287 int GWEN_IdList64_AddId(GWEN_IDLIST64 *idl, uint64_t id){
288  GWEN_IDTABLE64 *idt=NULL;
289  GWEN_IDTABLE64 **tablePtr;
290  int idx;
291 
292  assert(idl);
293 
294  if (idl->pIdTablePointers==NULL) {
295  /* create an initial pointer table which can take up to GWEN_IDLIST64_STEP pointers */
296  idl->pIdTablePointers=(GWEN_IDTABLE64 **) malloc(sizeof(GWEN_IDTABLE64*)*GWEN_IDLIST64_STEP);
297  assert(idl->pIdTablePointers);
298  memset(idl->pIdTablePointers, 0, sizeof(GWEN_IDTABLE64*)*GWEN_IDLIST64_STEP);
299  idl->idTableCount=GWEN_IDLIST64_STEP;
300  }
301 
302  for (idx=0, tablePtr=idl->pIdTablePointers; idx<idl->idTableCount; idx++, tablePtr++) {
303  idt=*tablePtr;
304  if (idt && !GWEN_IdTable64_IsFull(idt))
305  break;
306  } /* while */
307 
308  if (idx>=idl->idTableCount) {
309  idt=GWEN_IdTable64_new();
310  GWEN_IdList64_AddTable(idl, idt);
311  }
312 
313  GWEN_IdTable64_AddId(idt, id);
314  idl->entryCount++;
315  return 0;
316 }
317 
318 
319 
320 int GWEN_IdList64_DelId(GWEN_IDLIST64 *idl, uint64_t id){
321  if (idl->pIdTablePointers) {
322  GWEN_IDTABLE64 *idt=NULL;
323  GWEN_IDTABLE64 **tablePtr;
324  int idx;
325 
326  for (idx=0, tablePtr=idl->pIdTablePointers; idx<idl->idTableCount; idx++, tablePtr++) {
327  idt=*tablePtr;
328  if (idt && !GWEN_IdTable64_DelId(idt, id)) {
329  /* found a table which had this id */
330  GWEN_IdList64_Clean(idl);
331  idl->entryCount--;
332  return 0;
333  }
334  }
335  }
336 
337  return -1;
338 }
339 
340 
341 
342 int GWEN_IdList64_HasId(const GWEN_IDLIST64 *idl, uint64_t id){
343  if (idl->pIdTablePointers) {
344  GWEN_IDTABLE64 *idt=NULL;
345  GWEN_IDTABLE64 **tablePtr;
346  int idx;
347 
348  for (idx=0, tablePtr=idl->pIdTablePointers; idx<idl->idTableCount; idx++, tablePtr++) {
349  idt=*tablePtr;
350  if (idt && GWEN_IdTable64_HasId(idt, id))
351  return 1;
352  }
353  }
354 
355  return 0;
356 }
357 
358 
359 
361  GWEN_IDTABLE64 *idt=NULL;
362  GWEN_IDTABLE64 **tablePtr;
363  int idx;
364 
365  for (idx=0, tablePtr=idl->pIdTablePointers; idx<idl->idTableCount; idx++, tablePtr++) {
366  idt=*tablePtr;
367  if (idt && GWEN_IdTable64_IsEmpty(idt)) {
368  GWEN_IdTable64_free(idt);
369  *tablePtr=NULL;
370  }
371  }
372 }
373 
374 
375 
377  if (idl->pIdTablePointers) {
378  GWEN_IDTABLE64 *idt=NULL;
379  GWEN_IDTABLE64 **tablePtr;
380  int idx;
381 
382  for (idx=0, tablePtr=idl->pIdTablePointers; idx<idl->idTableCount; idx++, tablePtr++) {
383  idt=*tablePtr;
384  if (idt) {
385  GWEN_IdTable64_free(idt);
386  *tablePtr=NULL;
387  }
388  }
389  free(idl->pIdTablePointers);
390  idl->pIdTablePointers=NULL;
391  }
392  idl->entryCount=0;
393  idl->nextIdx=0;
394 }
395 
396 
397 
398 static int __compAscending(const void *pa, const void *pb) {
399  uint64_t a=*((const uint64_t*)pa);
400  uint64_t b=*((const uint64_t*)pb);
401 
402  if (a<b)
403  return -1;
404  else if (a>b)
405  return 1;
406  else
407  return 0;
408 }
409 
410 
411 
412 static int __compDescending(const void *pa, const void *pb) {
413  uint64_t a=*((const uint64_t*)pa);
414  uint64_t b=*((const uint64_t*)pb);
415 
416  if (a<b)
417  return 1;
418  else if (a>b)
419  return -1;
420  else
421  return 0;
422 }
423 
424 
425 
426 static int GWEN_IdList64__Sort(GWEN_IDLIST64 *idl, int ascending){
427  assert(idl);
428  assert(idl->refCount);
429  if (idl->pIdTablePointers && idl->entryCount) {
431  unsigned int cnt;
432  uint64_t *ptr;
433  unsigned int i;
434 
435  assert(idl);
436 
437  /* count ids */
438  cnt=idl->entryCount;
439 
440  /* move ids to a temporary list */
441  ptr=(uint64_t*)malloc(sizeof(uint64_t)*cnt);
442  assert(ptr);
443 
445  for (i=0; i<cnt; i++) {
446  uint64_t id;
447 
448  if (i==0)
450  else
452  assert(id);
453  ptr[i]=id;
454  } /* for */
456 
457  /* remove all tables (we will add sorted tables later) */
458  GWEN_IdList64_Clear(idl);
459 
460  if (ascending)
461  qsort(ptr, cnt, sizeof(uint64_t), __compAscending);
462  else
463  qsort(ptr, cnt, sizeof(uint64_t), __compDescending);
464 
465  /* move back sorted list of ids from temporary list */
466  for (i=0; i<cnt; i++) {
467  GWEN_IdList64_AddId(idl, ptr[i]);
468  }
469  free(ptr);
470  }
471  return 0;
472 }
473 
474 
475 
477  return GWEN_IdList64__Sort(idl, 1);
478 }
479 
480 
481 
483  return GWEN_IdList64__Sort(idl, 0);
484 }
485 
486 
487 
489  GWEN_IDLIST64 *nidl;
490  int idx;
491 
492  nidl=GWEN_IdList64_new();
493 
494  nidl->idTableCount=idl->idTableCount;
495  nidl->entryCount=idl->entryCount;
496  if (idl->pIdTablePointers) {
497  for (idx=0; idx<idl->idTableCount; idx++) {
498  GWEN_IDTABLE64 *idt;
499 
500  idt=idl->pIdTablePointers[idx];
501  if (idt && !GWEN_IdTable64_IsEmpty(idt)) {
502  GWEN_IDTABLE64 *nidt;
503 
504  nidt=GWEN_IdTable64_new();
505  memmove(nidt->entries, idt->entries, GWEN_IDTABLE64_MAXENTRIES*sizeof(uint64_t));
506  nidt->freeEntries=idt->freeEntries;
507  GWEN_IdList64_AddTable(nidl, nidt);
508  }
509  }
510  }
511 
512  return nidl;
513 }
514 
515 
516 
518  assert(idl);
519  assert(idl->refCount);
520 
521  return idl->entryCount;
522 }
523 
524 
525 
526 uint64_t GWEN_IdList64__GetFirstId(const GWEN_IDLIST64 *idl, uint64_t *pos){
527  GWEN_IDTABLE64 *idt=NULL;
528  GWEN_IDTABLE64 **tablePtr;
529  int idx;
530  int idIndex=0;
531 
532  *pos=0;
533  for (idx=0, tablePtr=idl->pIdTablePointers; idx<idl->idTableCount; idx++, tablePtr++) {
534  idt=*tablePtr;
535  if (idt && !GWEN_IdTable64_IsEmpty(idt)) {
536  int i;
537  uint64_t id;
538 
539  for (i=0; i<GWEN_IDTABLE64_MAXENTRIES; i++) {
540  if (idt->entries[i]!=0) {
541  id=idt->entries[i];
542  *pos=idIndex+i+1;
543  return id;
544  }
545  }
546  }
547  idIndex+=GWEN_IDTABLE64_MAXENTRIES;
548  }
549 
550  return 0;
551 }
552 
553 
554 
555 uint64_t GWEN_IdList64__GetNextId(const GWEN_IDLIST64 *idl, uint64_t *pos){
556  if (*pos) {
557  GWEN_IDTABLE64 *idt;
558  uint64_t tableNum=*pos / GWEN_IDTABLE64_MAXENTRIES;
559  uint64_t tableIdx=*pos % GWEN_IDTABLE64_MAXENTRIES;
560  GWEN_IDTABLE64 **tablePtr;
561  int idIndex=0;
562  int idx;
563 
564  if (tableNum>idl->idTableCount) {
565  DBG_ERROR(GWEN_LOGDOMAIN, "Table number out of range");
566  *pos=0;
567  return 0;
568  }
569 
570  idIndex=(tableNum*GWEN_IDTABLE64_MAXENTRIES);
571  for (idx=tableNum, tablePtr=idl->pIdTablePointers+tableNum; idx<idl->idTableCount; idx++, tablePtr++) {
572  idt=*tablePtr;
573  if (idt && !GWEN_IdTable64_IsEmpty(idt)) {
574  int i;
575  uint64_t id;
576 
577  if (idx==tableNum) {
578  for (i=tableIdx; i<GWEN_IDTABLE64_MAXENTRIES; i++) {
579  if (idt->entries[i]!=0) {
580  id=idt->entries[i];
581  *pos=idIndex+i+1;
582  return id;
583  }
584  }
585  }
586  else {
587  for (i=0; i<GWEN_IDTABLE64_MAXENTRIES; i++) {
588  if (idt->entries[i]!=0) {
589  id=idt->entries[i];
590  *pos=idIndex+i+1;
591  return id;
592  }
593  }
594  }
595  }
596  idIndex+=GWEN_IDTABLE64_MAXENTRIES;
597  }
598  *pos=0;
599  }
600 
601  return 0;
602 }
603 
604 
605 
607  return GWEN_IdList64__GetFirstId(idl, &(idl->nextIdx));
608 }
609 
610 
611 
613  return GWEN_IdList64__GetNextId(idl, &(idl->nextIdx));
614 }
615 
616 
617 
618 uint64_t GWEN_IdList64_GetFirstId2(const GWEN_IDLIST64 *idl, uint64_t *pos){
619  return GWEN_IdList64__GetFirstId(idl, pos);
620 }
621 
622 
623 
624 uint64_t GWEN_IdList64_GetNextId2(const GWEN_IDLIST64 *idl, uint64_t *pos){
625  return GWEN_IdList64__GetNextId(idl, pos);
626 }
627 
628 
629 
630 
631 
632 
635 
636  assert(idl);
638 
640  it->list=idl;
641 
642  return it;
643 }
644 
645 
646 
648  if (it) {
649  GWEN_IdList64_free(it->list);
650  GWEN_FREE_OBJECT(it);
651  }
652 }
653 
654 
655 
657  return GWEN_IdList64__GetFirstId(it->list, &(it->nextIndex));
658 }
659 
660 
661 
663  return GWEN_IdList64__GetNextId(it->list, &(it->nextIndex));
664 }
665 
666 
667 
668 int GWEN_IdList64_AppendId(GWEN_IDLIST64 *idl, uint64_t id) {
669  GWEN_IDTABLE64 *idt=NULL;
670 
671  assert(idl);
672 
673  if (idl->pIdTablePointers==NULL) {
674  /* create an initial pointer table which can take up to GWEN_IDLIST64_STEP pointers */
675  idl->pIdTablePointers=(GWEN_IDTABLE64 **) malloc(sizeof(GWEN_IDTABLE64*)*GWEN_IDLIST64_STEP);
676  assert(idl->pIdTablePointers);
677  memset(idl->pIdTablePointers, 0, sizeof(GWEN_IDTABLE64*)*GWEN_IDLIST64_STEP);
678  idl->idTableCount=GWEN_IDLIST64_STEP;
679  }
680 
681  idt=idl->pIdTablePointers[idl->lastTableIdx];
682  if (idt==NULL || GWEN_IdTable64_IsFull(idt)) {
683  idt=GWEN_IdTable64_new();
684  GWEN_IdList64_AddTable(idl, idt);
685  }
686 
687  GWEN_IdTable64_AppendId(idt, id);
688  idl->entryCount++;
689  return 0;
690 }
691 
692 
693 
694 uint64_t GWEN_IdList64_GetIdAt(const GWEN_IDLIST64 *idl, uint64_t idx) {
695  GWEN_IDTABLE64 *idt;
696  uint64_t tableNum=idx / GWEN_IDTABLE64_MAXENTRIES;
697  uint64_t tableIdx=idx % GWEN_IDTABLE64_MAXENTRIES;
698 
699  assert(idl);
700  if (tableNum>idl->idTableCount) {
701  DBG_INFO(GWEN_LOGDOMAIN, "Table index out of range");
702  return 0;
703  }
704 
705  idt=idl->pIdTablePointers[tableNum];
706  if (idt==NULL) {
707  DBG_INFO(GWEN_LOGDOMAIN, "Table index points to an empty table");
708  return 0;
709  }
710 
711  return idt->entries[tableIdx];
712 }
713 
714 
715 
716 
717 
718 
719 
720 
721 
722 
723