gwenhywfar  4.7.0beta
pointerlist.c
Go to the documentation of this file.
1 /***************************************************************************
2  begin : Wed Sep 12 2012
3  copyright : (C) 2012 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 "pointerlist_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_POINTERLIST_TABLE *GWEN_PointerListTable_new(void){
45  GWEN_POINTERLIST_TABLE *idt;
46 
47  GWEN_NEW_OBJECT(GWEN_POINTERLIST_TABLE, idt);
48  idt->refCount=1;
49 
50  idt->freeEntries=GWEN_POINTERLIST_TABLE_MAXENTRIES;
51  return idt;
52 }
53 
54 
55 
56 void GWEN_PointerListTable_free(GWEN_POINTERLIST_TABLE *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 static inline int GWEN_PointerListTable_AddPtr(GWEN_POINTERLIST_TABLE *idt, void *ptr){
68  unsigned int i;
69 
70  for (i=0; i<GWEN_POINTERLIST_TABLE_MAXENTRIES; i++) {
71  if (idt->entries[i]==0) {
72  idt->entries[i]=ptr;
73  idt->freeEntries--;
74  return 0;
75  }
76  } /* for */
77  return -1;
78 }
79 
80 
81 
82 static inline int GWEN_PointerListTable_AppendPtr(GWEN_POINTERLIST_TABLE *idt, void *ptr){
83  if (idt->freeEntries) {
84  unsigned int i;
85 
86  i=GWEN_POINTERLIST_TABLE_MAXENTRIES-idt->freeEntries;
87  idt->entries[i]=ptr;
88  idt->freeEntries--;
89  return 0;
90  }
91  else
92  return -1;
93 }
94 
95 
96 
97 static inline int GWEN_PointerListTable_HasPtr(const GWEN_POINTERLIST_TABLE *idt, void *ptr){
98  unsigned int i;
99 
100  for (i=0; i<GWEN_POINTERLIST_TABLE_MAXENTRIES; i++) {
101  if (idt->entries[i]==ptr) {
102  return 1;
103  }
104  } /* for */
105  return 0;
106 }
107 
108 
109 
110 static inline int GWEN_PointerListTable_DelPtr(GWEN_POINTERLIST_TABLE *idt, void *ptr){
111  unsigned int i;
112 
113  for (i=0; i<GWEN_POINTERLIST_TABLE_MAXENTRIES; i++) {
114  if (idt->entries[i]==ptr) {
115  idt->entries[i]=0;
116  idt->freeEntries++;
117  return 0;
118  }
119  } /* for */
120  return -1;
121 }
122 
123 
124 
125 static inline int GWEN_PointerListTable_IsEmpty(const GWEN_POINTERLIST_TABLE *idt){
126  return GWEN_POINTERLIST_TABLE_MAXENTRIES==idt->freeEntries;
127 }
128 
129 
130 
131 static inline int GWEN_PointerListTable_IsFull(const GWEN_POINTERLIST_TABLE *idt){
132  return idt->freeEntries==0;
133 }
134 
135 
136 
137 static inline unsigned int GWEN_PointerListTable_GetCount(const GWEN_POINTERLIST_TABLE *idt){
138  return GWEN_POINTERLIST_TABLE_MAXENTRIES-idt->freeEntries;
139 }
140 
141 
142 
143 static inline void *GWEN_PointerListTable_GetFirstPtr(const GWEN_POINTERLIST_TABLE *idt, uint64_t *tabIdx){
144  unsigned int i;
145 
146  for (i=0; i<GWEN_POINTERLIST_TABLE_MAXENTRIES; i++) {
147  if (idt->entries[i]!=0) {
148  *tabIdx=i;
149  return idt->entries[i];
150  }
151  } /* for */
152  return NULL;
153 }
154 
155 
156 
157 static inline void *GWEN_PointerListTable_GetNextPtr(const GWEN_POINTERLIST_TABLE *idt, uint64_t *tabIdx){
158  unsigned int i;
159 
160  for (i=(*tabIdx)+1; i<GWEN_POINTERLIST_TABLE_MAXENTRIES; i++) {
161  if (idt->entries[i]!=0) {
162  *tabIdx=i;
163  return idt->entries[i];
164  }
165  } /* for */
166  return NULL;
167 }
168 
169 
170 
171 
172 
173 
175  GWEN_POINTERLIST *idl;
176 
178  idl->refCount=1;
179  idl->tableStep=GWEN_POINTERLIST_DEFAULT_STEP;
180  return idl;
181 }
182 
183 
184 
186  assert(idl);
187  assert(idl->refCount);
188  idl->refCount++;
189 }
190 
191 
192 
194  if (idl) {
195  assert(idl->refCount);
196  if (idl->refCount==1) {
198  idl->refCount=0;
199  GWEN_FREE_OBJECT(idl);
200  }
201  else
202  idl->refCount--;
203  }
204 }
205 
206 
207 
208 void GWEN_PointerList_AddTable(GWEN_POINTERLIST *idl, GWEN_POINTERLIST_TABLE *idt) {
209  GWEN_POINTERLIST_TABLE **tablePtr;
210  int idx;
211 
212  assert(idl);
213 
214  tablePtr=idl->pIdTablePointers;
215  for (idx=0, tablePtr=idl->pIdTablePointers; idx<idl->idTableCount; idx++, tablePtr++) {
216  if (*tablePtr==NULL)
217  break;
218  } /* while */
219 
220  if (idx>=idl->idTableCount) {
221  uint32_t newCount;
222  GWEN_POINTERLIST_TABLE **newPtr;
223 
224  /* resize */
225  newCount=idl->idTableCount+idl->tableStep;
226  newPtr=(GWEN_POINTERLIST_TABLE **)realloc(idl->pIdTablePointers, sizeof(GWEN_POINTERLIST_TABLE*)*newCount);
227  assert(newPtr);
228  /* init new pointers */
229  memset((void*)(newPtr+idl->idTableCount),
230  0,
231  sizeof(GWEN_POINTERLIST_TABLE*)*(newCount-idl->idTableCount));
232  idl->pIdTablePointers=newPtr;
233  idl->pIdTablePointers[idl->idTableCount]=idt;
234  idl->lastTableIdx=idl->idTableCount;
235  idl->idTableCount=newCount;
236  }
237  else {
238  idl->pIdTablePointers[idx]=idt;
239  idl->lastTableIdx=idx;
240  }
241 }
242 
243 
244 
246  GWEN_POINTERLIST_TABLE *idt=NULL;
247  GWEN_POINTERLIST_TABLE **tablePtr;
248  int idx;
249 
250  assert(idl);
251 
252  if (idl->pIdTablePointers==NULL) {
253  /* create an initial pointer table which can take up to tableStep pointers */
254  idl->pIdTablePointers=(GWEN_POINTERLIST_TABLE **) malloc(sizeof(GWEN_POINTERLIST_TABLE*)*(idl->tableStep));
255  assert(idl->pIdTablePointers);
256  memset(idl->pIdTablePointers, 0, sizeof(GWEN_POINTERLIST*)*(idl->tableStep));
257  idl->idTableCount=idl->tableStep;
258  }
259 
260  for (idx=0, tablePtr=idl->pIdTablePointers; idx<idl->idTableCount; idx++, tablePtr++) {
261  idt=*tablePtr;
262  if (idt && !GWEN_PointerListTable_IsFull(idt))
263  break;
264  } /* while */
265 
266  if (idx>=idl->idTableCount) {
268  GWEN_PointerList_AddTable(idl, idt);
269  }
270 
272  idl->entryCount++;
273  return 0;
274 }
275 
276 
277 
279  if (idl->pIdTablePointers) {
280  GWEN_POINTERLIST_TABLE *idt=NULL;
281  GWEN_POINTERLIST_TABLE **tablePtr;
282  int idx;
283 
284  for (idx=0, tablePtr=idl->pIdTablePointers; idx<idl->idTableCount; idx++, tablePtr++) {
285  idt=*tablePtr;
286  if (idt && !GWEN_PointerListTable_DelPtr(idt, ptr)) {
287  /* found a table which had this id */
289  idl->entryCount--;
290  return 0;
291  }
292  }
293  }
294 
295  return -1;
296 }
297 
298 
299 
300 int GWEN_PointerList_HasPtr(const GWEN_POINTERLIST *idl, void *ptr){
301  if (idl->pIdTablePointers) {
302  GWEN_POINTERLIST_TABLE *idt=NULL;
303  GWEN_POINTERLIST_TABLE **tablePtr;
304  int idx;
305 
306  for (idx=0, tablePtr=idl->pIdTablePointers; idx<idl->idTableCount; idx++, tablePtr++) {
307  idt=*tablePtr;
308  if (idt && GWEN_PointerListTable_HasPtr(idt, ptr))
309  return 1;
310  }
311  }
312 
313  return 0;
314 }
315 
316 
317 
319  GWEN_POINTERLIST_TABLE *idt=NULL;
320  GWEN_POINTERLIST_TABLE **tablePtr;
321  int idx;
322 
323  for (idx=0, tablePtr=idl->pIdTablePointers; idx<idl->idTableCount; idx++, tablePtr++) {
324  idt=*tablePtr;
325  if (idt && GWEN_PointerListTable_IsEmpty(idt)) {
327  *tablePtr=NULL;
328  }
329  }
330 }
331 
332 
333 
335  if (idl->pIdTablePointers) {
336  GWEN_POINTERLIST_TABLE *idt=NULL;
337  GWEN_POINTERLIST_TABLE **tablePtr;
338  int idx;
339 
340  for (idx=0, tablePtr=idl->pIdTablePointers; idx<idl->idTableCount; idx++, tablePtr++) {
341  idt=*tablePtr;
342  if (idt) {
344  *tablePtr=NULL;
345  }
346  }
347  free(idl->pIdTablePointers);
348  idl->pIdTablePointers=NULL;
349  }
350  idl->entryCount=0;
351  idl->nextIdx=0;
352 }
353 
354 
355 
357  GWEN_POINTERLIST *nidl;
358  int idx;
359 
360  nidl=GWEN_PointerList_new();
361  nidl->tableStep=idl->tableStep;
362 
363  nidl->idTableCount=idl->idTableCount;
364  nidl->entryCount=idl->entryCount;
365  if (idl->pIdTablePointers) {
366  for (idx=0; idx<idl->idTableCount; idx++) {
367  GWEN_POINTERLIST_TABLE *idt;
368 
369  idt=idl->pIdTablePointers[idx];
370  if (idt && !GWEN_PointerListTable_IsEmpty(idt)) {
371  GWEN_POINTERLIST_TABLE *nidt;
372 
374  memmove(nidt->entries, idt->entries, GWEN_POINTERLIST_TABLE_MAXENTRIES*sizeof(void*));
375  nidt->freeEntries=idt->freeEntries;
376  GWEN_PointerList_AddTable(nidl, nidt);
377  }
378  }
379  }
380 
381  return nidl;
382 }
383 
384 
385 
387  assert(idl);
388  assert(idl->refCount);
389 
390  return idl->entryCount;
391 }
392 
393 
394 
395 void *GWEN_PointerList_GetFirstPtr(const GWEN_POINTERLIST *idl, uint64_t *pos){
396  GWEN_POINTERLIST_TABLE *idt=NULL;
397  GWEN_POINTERLIST_TABLE **tablePtr;
398  int idx;
399  int idIndex=0;
400 
401  *pos=0;
402  for (idx=0, tablePtr=idl->pIdTablePointers; idx<idl->idTableCount; idx++, tablePtr++) {
403  idt=*tablePtr;
404  if (idt && !GWEN_PointerListTable_IsEmpty(idt)) {
405  int i;
406  void *ptr;
407 
408  for (i=0; i<GWEN_POINTERLIST_TABLE_MAXENTRIES; i++) {
409  if (idt->entries[i]!=0) {
410  ptr=idt->entries[i];
411  *pos=idIndex+i+1;
412  return ptr;
413  }
414  }
415  }
416  idIndex+=GWEN_POINTERLIST_TABLE_MAXENTRIES;
417  }
418 
419  return NULL;
420 }
421 
422 
423 
424 void *GWEN_PointerList_GetNextPtr(const GWEN_POINTERLIST *idl, uint64_t *pos){
425  if (*pos) {
426  GWEN_POINTERLIST_TABLE *idt;
427  uint64_t tableNum=*pos / GWEN_POINTERLIST_TABLE_MAXENTRIES;
428  uint64_t tableIdx=*pos % GWEN_POINTERLIST_TABLE_MAXENTRIES;
429  GWEN_POINTERLIST_TABLE **tablePtr;
430  int idIndex=0;
431  int idx;
432 
433  if (tableNum>idl->idTableCount) {
434  DBG_ERROR(GWEN_LOGDOMAIN, "Table number out of range");
435  *pos=0;
436  return 0;
437  }
438 
439  idIndex=(tableNum*GWEN_POINTERLIST_TABLE_MAXENTRIES);
440  for (idx=tableNum, tablePtr=idl->pIdTablePointers+tableNum; idx<idl->idTableCount; idx++, tablePtr++) {
441  idt=*tablePtr;
442  if (idt && !GWEN_PointerListTable_IsEmpty(idt)) {
443  int i;
444  void *ptr;
445 
446  if (idx==tableNum) {
447  for (i=tableIdx; i<GWEN_POINTERLIST_TABLE_MAXENTRIES; i++) {
448  if (idt->entries[i]!=0) {
449  ptr=idt->entries[i];
450  *pos=idIndex+i+1;
451  return ptr;
452  }
453  }
454  }
455  else {
456  for (i=0; i<GWEN_POINTERLIST_TABLE_MAXENTRIES; i++) {
457  if (idt->entries[i]!=0) {
458  ptr=idt->entries[i];
459  *pos=idIndex+i+1;
460  return ptr;
461  }
462  }
463  }
464  }
465  idIndex+=GWEN_POINTERLIST_TABLE_MAXENTRIES;
466  }
467  *pos=0;
468  }
469 
470  return NULL;
471 }
472 
473 
474 
475 
478 
479  assert(idl);
481 
483  it->list=idl;
484 
485  return it;
486 }
487 
488 
489 
491  if (it) {
492  GWEN_PointerList_free(it->list);
493  GWEN_FREE_OBJECT(it);
494  }
495 }
496 
497 
498 
500  return GWEN_PointerList_GetFirstPtr(it->list, &(it->nextIndex));
501 }
502 
503 
504 
506  return GWEN_PointerList_GetNextPtr(it->list, &(it->nextIndex));
507 }
508 
509 
510 
512  GWEN_POINTERLIST_TABLE *idt=NULL;
513 
514  assert(idl);
515 
516  if (idl->pIdTablePointers==NULL) {
517  /* create an initial pointer table which can take up to tableStep pointers */
518  idl->pIdTablePointers=(GWEN_POINTERLIST_TABLE **) malloc(sizeof(GWEN_POINTERLIST_TABLE*)*(idl->tableStep));
519  assert(idl->pIdTablePointers);
520  memset(idl->pIdTablePointers, 0, sizeof(GWEN_POINTERLIST_TABLE*)*(idl->tableStep));
521  idl->idTableCount=idl->tableStep;
522  }
523 
524  idt=idl->pIdTablePointers[idl->lastTableIdx];
525  if (idt==NULL || GWEN_PointerListTable_IsFull(idt)) {
527  GWEN_PointerList_AddTable(idl, idt);
528  }
529 
531  idl->entryCount++;
532  return 0;
533 }
534 
535 
536 
537 void *GWEN_PointerList_GetPtrAt(const GWEN_POINTERLIST *idl, uint64_t idx) {
538  GWEN_POINTERLIST_TABLE *idt;
539  uint64_t tableNum=idx / GWEN_POINTERLIST_TABLE_MAXENTRIES;
540  uint64_t tableIdx=idx % GWEN_POINTERLIST_TABLE_MAXENTRIES;
541 
542  assert(idl);
543  if (tableNum>idl->idTableCount) {
544  DBG_INFO(GWEN_LOGDOMAIN, "Table index out of range");
545  return 0;
546  }
547 
548  idt=idl->pIdTablePointers[tableNum];
549  if (idt==NULL) {
550  DBG_INFO(GWEN_LOGDOMAIN, "Table index points to an empty table");
551  return 0;
552  }
553 
554  return idt->entries[tableIdx];
555 }
556 
557 
558 
559 
560 
561 
562 
563 
564 
565 
566