gwenhywfar  4.8.0beta
idlist.c
Go to the documentation of this file.
1 /***************************************************************************
2  $RCSfile$
3  -------------------
4  cvs : $Id$
5  begin : Mon Mar 01 2004
6  copyright : (C) 2004 by Martin Preuss
7  email : martin@libchipcard.de
8 
9  ***************************************************************************
10  * *
11  * This library is free software; you can redistribute it and/or *
12  * modify it under the terms of the GNU Lesser General Public *
13  * License as published by the Free Software Foundation; either *
14  * version 2.1 of the License, or (at your option) any later version. *
15  * *
16  * This library is distributed in the hope that it will be useful, *
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of *
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
19  * Lesser General Public License for more details. *
20  * *
21  * You should have received a copy of the GNU Lesser General Public *
22  * License along with this library; if not, write to the Free Software *
23  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, *
24  * MA 02111-1307 USA *
25  * *
26  ***************************************************************************/
27 
28 
29 
30 #ifdef HAVE_CONFIG_H
31 # include <config.h>
32 #endif
33 
34 
35 #include "idlist_p.h"
36 #include <gwenhywfar/debug.h>
37 
38 
39 #include <stdlib.h>
40 #include <assert.h>
41 #include <string.h>
42 
43 
44 GWEN_LIST_FUNCTIONS(GWEN_IDTABLE, GWEN_IdTable)
45 /* No trailing semicolon here because this is a macro call */
46 
47 
48 
49 GWEN_IDTABLE *GWEN_IdTable_new(void){
50  GWEN_IDTABLE *idt;
51 
52  GWEN_NEW_OBJECT(GWEN_IDTABLE, idt);
53  GWEN_LIST_INIT(GWEN_IDTABLE, idt);
54 
55  idt->freeEntries=GWEN_IDTABLE_MAXENTRIES;
56  return idt;
57 }
58 
59 
60 
61 void GWEN_IdTable_free(GWEN_IDTABLE *idt){
62  if (idt) {
63  GWEN_LIST_FINI(GWEN_IDTABLE, idt);
64  GWEN_FREE_OBJECT(idt);
65  }
66 }
67 
68 
69 
70 int GWEN_IdTable_AddId(GWEN_IDTABLE *idt, uint32_t id){
71  unsigned int i;
72 
73  assert(idt);
74  assert(id);
75 
76  for (i=0; i<GWEN_IDTABLE_MAXENTRIES; i++) {
77  if (idt->entries[i]==0) {
78  idt->entries[i]=id;
79  idt->freeEntries--;
80  return 0;
81  }
82  } /* for */
83  return -1;
84 }
85 
86 
87 
88 int GWEN_IdTable_HasId(const GWEN_IDTABLE *idt, uint32_t id){
89  unsigned int i;
90 
91  assert(idt);
92  assert(id);
93 
94  for (i=0; i<GWEN_IDTABLE_MAXENTRIES; i++) {
95  if (idt->entries[i]==id) {
96  return 1;
97  }
98  } /* for */
99  return 0;
100 }
101 
102 
103 
104 int GWEN_IdTable_DelId(GWEN_IDTABLE *idt, uint32_t id){
105  unsigned int i;
106 
107  assert(idt);
108  assert(id);
109 
110  for (i=0; i<GWEN_IDTABLE_MAXENTRIES; i++) {
111  if (idt->entries[i]==id) {
112  idt->entries[i]=0;
113  idt->freeEntries++;
114  return 0;
115  }
116  } /* for */
117  return -1;
118 }
119 
120 
121 
122 int GWEN_IdTable_IsEmpty(const GWEN_IDTABLE *idt){
123  assert(idt);
124  return GWEN_IDTABLE_MAXENTRIES==idt->freeEntries;
125 }
126 
127 
128 
129 int GWEN_IdTable_IsFull(const GWEN_IDTABLE *idt){
130  assert(idt);
131  return idt->freeEntries==0;
132 }
133 
134 
135 
136 unsigned int GWEN_IdTable_GetCount(const GWEN_IDTABLE *idt){
137  assert(idt);
138  return GWEN_IDTABLE_MAXENTRIES-idt->freeEntries;
139 }
140 
141 
142 
143 uint32_t GWEN_IdTable_GetFirstId(GWEN_IDTABLE *idt){
144  unsigned int i;
145 
146  assert(idt);
147  idt->current=0;
148  for (i=0; i<GWEN_IDTABLE_MAXENTRIES; i++) {
149  if (idt->entries[i]!=0) {
150  idt->current=i;
151  return idt->entries[i];
152  }
153  } /* for */
154  return 0;
155 }
156 
157 
158 
159 uint32_t GWEN_IdTable_GetNextId(GWEN_IDTABLE *idt){
160  unsigned int i;
161 
162  assert(idt);
163 
164  for (i=idt->current+1; i<GWEN_IDTABLE_MAXENTRIES; i++) {
165  if (idt->entries[i]!=0) {
166  idt->current=i;
167  return idt->entries[i];
168  }
169  } /* for */
170  idt->current=GWEN_IDTABLE_MAXENTRIES;
171  return 0;
172 }
173 
174 
175 
176 uint32_t GWEN_IdTable_GetFirstId2(const GWEN_IDTABLE *idt,
177  uint32_t *tabIdx){
178  unsigned int i;
179 
180  assert(idt);
181  for (i=0; i<GWEN_IDTABLE_MAXENTRIES; i++) {
182  if (idt->entries[i]!=0) {
183  *tabIdx=i;
184  return idt->entries[i];
185  }
186  } /* for */
187  return 0;
188 }
189 
190 
191 
192 uint32_t GWEN_IdTable_GetNextId2(const GWEN_IDTABLE *idt,
193  uint32_t *tabIdx){
194  unsigned int i;
195 
196  assert(idt);
197 
198  for (i=(*tabIdx)+1; i<GWEN_IDTABLE_MAXENTRIES; i++) {
199  if (idt->entries[i]!=0) {
200  *tabIdx=i;
201  return idt->entries[i];
202  }
203  } /* for */
204  return 0;
205 }
206 
207 
208 
209 
210 
211 
213  GWEN_IDLIST *idl;
214 
216  idl->idTables=GWEN_IdTable_List_new();
217  return idl;
218 }
219 
220 
221 
223  if (idl) {
224  GWEN_IdTable_List_free(idl->idTables);
225  GWEN_FREE_OBJECT(idl);
226  }
227 }
228 
229 
230 
231 int GWEN_IdList_AddId(GWEN_IDLIST *idl, uint32_t id){
232  GWEN_IDTABLE *idt;
233 
234  assert(idl);
235 
236  idl->current=0;
237  idt=GWEN_IdTable_List_First(idl->idTables);
238  /* find free table */
239  while(idt) {
240  if (!GWEN_IdTable_IsFull(idt))
241  break;
242  idt=GWEN_IdTable_List_Next(idt);
243  } /* while */
244 
245  if (!idt) {
246  idt=GWEN_IdTable_new();
247  GWEN_IdTable_List_Add(idt, idl->idTables);;
248  }
249 
250  GWEN_IdTable_AddId(idt, id);
251  idl->entryCount++;
252  return 0;
253 }
254 
255 
256 
257 int GWEN_IdList_DelId(GWEN_IDLIST *idl, uint32_t id){
258  GWEN_IDTABLE *idt;
259 
260  assert(idl);
261 
262  idl->current=0;
263  idt=GWEN_IdTable_List_First(idl->idTables);
264  /* find table */
265  while(idt) {
266  if (!GWEN_IdTable_DelId(idt, id)) {
267  /* found a table which had this id */
268  GWEN_IdList_Clean(idl);
269  idl->entryCount--;
270  return 0;
271  }
272  idt=GWEN_IdTable_List_Next(idt);
273  } /* while */
274  return -1;
275 }
276 
277 
278 
279 int GWEN_IdList_HasId(const GWEN_IDLIST *idl, uint32_t id){
280  GWEN_IDTABLE *idt;
281 
282  assert(idl);
283 
284  idt=GWEN_IdTable_List_First(idl->idTables);
285  /* find free table */
286  while(idt) {
287  if (GWEN_IdTable_HasId(idt, id))
288  return 1;
289  idt=GWEN_IdTable_List_Next(idt);
290  } /* while */
291  return 0;
292 }
293 
294 
295 
297  GWEN_IDTABLE *idt;
298 
299  assert(idl);
300  idl->current=0;
301  idt=GWEN_IdTable_List_First(idl->idTables);
302  /* find free table */
303  while(idt) {
304  GWEN_IDTABLE *next;
305 
306  next=GWEN_IdTable_List_Next(idt);
307  if (GWEN_IdTable_IsEmpty(idt)) {
308  GWEN_IdTable_List_Del(idt);
309  GWEN_IdTable_free(idt);
310  }
311  idt=next;
312  } /* while */
313 }
314 
315 
316 
318  GWEN_IDTABLE *idt;
319 
320  assert(idl);
321 
322  idt=GWEN_IdTable_List_First(idl->idTables);
323  /* find free table */
324  while(idt) {
325  GWEN_IDTABLE *next;
326  uint32_t id;
327 
328  next=GWEN_IdTable_List_Next(idt);
329  id=GWEN_IdTable_GetFirstId(idt);
330  if (id) {
331  idl->current=idt;
332  return id;
333  }
334  idt=next;
335  } /* while */
336 
337  return 0;
338 }
339 
340 
341 
343  GWEN_IDTABLE *idt;
344  uint32_t id;
345 
346  assert(idl);
347 
348  idt=idl->current;
349  if (idt) {
350  id=GWEN_IdTable_GetNextId(idt);
351  if (id) {
352  idl->current=idt;
353  return id;
354  }
355  }
356  else {
357  idl->current=0;
358  return 0;
359  }
360 
361  idt=GWEN_IdTable_List_Next(idt);
362  while (idt) {
363  id=GWEN_IdTable_GetFirstId(idt);
364  if (id) {
365  idl->current=idt;
366  return id;
367  }
368  idt=GWEN_IdTable_List_Next(idt);
369  } /* while */
370 
371  idl->current=0;
372  return 0;
373 }
374 
375 
376 
378  GWEN_IDTABLE *idt;
379  unsigned int cnt;
380  uint32_t *ptr;
381  unsigned int i;
382 
383  assert(idl);
384 
385  /* count ids */
386  idt=GWEN_IdTable_List_First(idl->idTables);
387  cnt=0;
388  while(idt) {
389  GWEN_IDTABLE *next;
390 
391  next=GWEN_IdTable_List_Next(idt);
392  cnt+=GWEN_IdTable_GetCount(idt);
393  idt=next;
394  } /* while */
395 
396  if (!cnt)
397  return 0;
398 
399  /* move ids to a temporary list */
400  ptr=(uint32_t*)malloc(sizeof(uint32_t)*cnt);
401  assert(ptr);
402 
403  for (i=0; i<cnt; i++) {
404  uint32_t id;
405 
406  if (i==0)
407  id=GWEN_IdList_GetFirstId(idl);
408  else
409  id=GWEN_IdList_GetNextId(idl);
410  assert(id);
411  ptr[i]=id;
412  } /* for */
413 
414  GWEN_IdTable_List_Clear(idl->idTables);
415  idl->current=0;
416 
417  /* sort temporary list */
418  while(1) {
419  int rpl;
420 
421  rpl=0;
422  for (i=0; i<(cnt-1); i++) {
423  if (ptr[i]>ptr[i+1]) {
424  uint32_t id;
425 
426  id=ptr[i];
427  ptr[i]=ptr[i+1];
428  ptr[i+1]=id;
429  rpl=1;
430  }
431  } /* for */
432  if (!rpl)
433  break;
434  } /* while */
435 
436  /* move back from temporary list */
437  for (i=0; i<cnt; i++) {
438  GWEN_IdList_AddId(idl, ptr[i]);
439  }
440  free(ptr);
441 
442  return 0;
443 }
444 
445 
446 
448  assert(idl);
449  GWEN_IdTable_List_Clear(idl->idTables);
450  idl->entryCount=0;
451  idl->current=0;
452 }
453 
454 
455 
457  GWEN_IDLIST *nidl;
458  GWEN_IDTABLE *idt;
459 
460  assert(idl);
461  nidl=GWEN_IdList_new();
462 
463  idt=GWEN_IdTable_List_First(idl->idTables);
464  while(idt) {
465  if (idt->freeEntries!=GWEN_IDTABLE_MAXENTRIES){
466  int i;
467 
468  for (i=0; i<GWEN_IDTABLE_MAXENTRIES; i++) {
469  if (idt->entries[i]!=0)
470  GWEN_IdList_AddId(nidl, idt->entries[i]);
471  }
472  }
473  idt=GWEN_IdTable_List_Next(idt);
474  }
475 
476  return nidl;
477 }
478 
479 
480 
482  uint32_t *pos){
483  GWEN_IDTABLE *idt;
484  int tabNum=0;
485 
486  assert(idl);
487 
488  idt=GWEN_IdTable_List_First(idl->idTables);
489  /* find free table */
490  while(idt) {
491  GWEN_IDTABLE *next;
492  uint32_t id;
493  uint32_t tabIdx;
494 
495  next=GWEN_IdTable_List_Next(idt);
496  id=GWEN_IdTable_GetFirstId2(idt, &tabIdx);
497  if (id) {
498  *pos=(tabNum*GWEN_IDTABLE_MAXENTRIES)+tabIdx;
499  return id;
500  }
501  tabNum++;
502  idt=next;
503  } /* while */
504 
505  return 0;
506 }
507 
508 
509 
511  uint32_t *pos){
512  GWEN_IDTABLE *idt;
513  int i;
514  int tabNum;
515  uint32_t tabIdx;
516 
517  assert(idl);
518  tabNum=(*pos)/GWEN_IDTABLE_MAXENTRIES;
519  tabIdx=(*pos)%GWEN_IDTABLE_MAXENTRIES;
520 
521  /* seek table */
522  i=tabNum;
523  idt=GWEN_IdTable_List_First(idl->idTables);
524  while(i--) idt=GWEN_IdTable_List_Next(idt);
525  assert(idt);
526 
527  while(idt) {
528  GWEN_IDTABLE *next;
529  uint32_t id;
530 
531  next=GWEN_IdTable_List_Next(idt);
532  id=GWEN_IdTable_GetNextId2(idt, &tabIdx);
533  if (id) {
534  *pos=(tabNum*GWEN_IDTABLE_MAXENTRIES)+tabIdx;
535  return id;
536  }
537  tabNum++;
538  idt=next;
539  } /* while */
540 
541  return 0;
542 }
543 
544 
545 
546 
547 
548 
549 
550 
551 
552 
553