gwenhywfar  4.7.0beta
list.c
Go to the documentation of this file.
1 /***************************************************************************
2  begin : Sat Nov 15 2003
3  copyright : (C) 2003 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 #ifdef HAVE_CONFIG_H
27 # include <config.h>
28 #endif
29 
30 #define DISABLE_DEBUGLOG
31 
32 
33 #include "list_p.h"
34 #include <gwenhywfar/misc.h>
35 #include <gwenhywfar/debug.h>
36 
37 
39 
40 
41 
42 GWEN_LIST_ENTRY *GWEN_ListEntry_new(void){
43  GWEN_LIST_ENTRY *le;
44 
45  GWEN_NEW_OBJECT(GWEN_LIST_ENTRY, le);
46  le->usage=1;
47  return le;
48 }
49 
50 
51 
52 void GWEN_ListEntry_free(GWEN_LIST_ENTRY *le){
53  if (le) {
54  if (le->usage) {
55  le->usage--;
56  if (le->usage==0) {
57  /* unlink */
58  le->previous=0;
59  le->next=0;
60  DBG_VERBOUS(GWEN_LOGDOMAIN, "Freeing entry");
61  GWEN_RefPtr_free(le->dataPtr);
62  /* really free */
63  GWEN_FREE_OBJECT(le);
64  }
65  }
66  }
67 }
68 
69 
70 
71 GWEN__LISTPTR *GWEN__ListPtr_new(void){
72  GWEN__LISTPTR *lp;
73 
74  GWEN_NEW_OBJECT(GWEN__LISTPTR, lp);
75  lp->refCount=1;
76  return lp;
77 }
78 
79 
80 
81 void GWEN__ListPtr_free(GWEN__LISTPTR *lp){
82  if (lp) {
83  assert(lp->refCount);
84  if (--(lp->refCount)==0) {
86  GWEN_FREE_OBJECT(lp);
87  }
88  }
89 }
90 
91 
92 
93 void GWEN__ListPtr_Attach(GWEN__LISTPTR *lp){
94  assert(lp);
95  assert(lp->refCount);
96  lp->refCount++;
97 }
98 
99 
100 
101 void GWEN__ListPtr_Clear(GWEN__LISTPTR *lp){
102  GWEN_LIST_ENTRY *le;
103 
104  assert(lp);
105  le=lp->first;
106  while(le) {
107  GWEN_LIST_ENTRY *nle;
108 
109  nle=le->next;
111  le=nle;
112  } /* while */
113  lp->first=0;
114  lp->last=0;
115  lp->size=0;
116 }
117 
118 
119 
120 GWEN__LISTPTR *GWEN__ListPtr_dup(GWEN__LISTPTR *lp){
121  GWEN__LISTPTR *nlp;
122  GWEN_LIST_ENTRY *le;
123 
124  nlp=GWEN__ListPtr_new();
125  assert(lp);
126  le=lp->first;
127  while(le) {
128  GWEN_LIST_ENTRY *nle;
129 
130  nle=GWEN_ListEntry_new();
131  if (le->dataPtr)
132  nle->dataPtr=GWEN_RefPtr_dup(le->dataPtr);
133  /* push back */
134  nle->previous=nlp->last;
135  if (nlp->last)
136  nlp->last->next=nle;
137  nlp->last=nle;
138  if (!(nlp->first))
139  nlp->first=nle;
140  nlp->size++;
141  nle->linkCount=le->linkCount;
142 
143  le=le->next;
144  } /* while */
145 
146  return nlp;
147 }
148 
149 
150 
151 
152 
153 
154 
155 
157  GWEN_LIST *l;
158 
161  l->listPtr=GWEN__ListPtr_new();
162  return l;
163 }
164 
165 
166 
168  if (l) {
170  GWEN__ListPtr_free(l->listPtr);
171  GWEN_RefPtrInfo_free(l->refPtrInfo);
172  GWEN_FREE_OBJECT(l);
173  }
174 }
175 
176 
177 
179  GWEN_LIST *nl;
180 
181  assert(l);
182  assert(l->listPtr);
185  nl->listPtr=l->listPtr;
186  GWEN__ListPtr_Attach(nl->listPtr);
187  return nl;
188 }
189 
190 
191 
193  assert(l);
194  return l->refPtrInfo;
195 }
196 
197 
198 
200  assert(l);
201  if (rpi)
203  GWEN_RefPtrInfo_free(l->refPtrInfo);
204  l->refPtrInfo=rpi;
205 }
206 
207 
208 
210  GWEN_LIST_ENTRY *le;
211  GWEN__LISTPTR *lp;
212 
213  if (l->listPtr->refCount>1) {
214  GWEN__LISTPTR *nlp;
215 
216  /* only copy the list if someone else is using it */
217  nlp=GWEN__ListPtr_dup(l->listPtr);
218  GWEN__ListPtr_free(l->listPtr);
219  l->listPtr=nlp;
220  }
221  lp=l->listPtr;
222 
223  le=GWEN_ListEntry_new();
224  le->dataPtr=rp;
225  le->previous=lp->last;
226  if (lp->last)
227  lp->last->next=le;
228  lp->last=le;
229  if (!(lp->first))
230  lp->first=le;
231  lp->size++;
232  le->linkCount=1;
233 }
234 
235 
236 
237 void GWEN_List_PushBack(GWEN_LIST *l, void *p){
238  GWEN_List_PushBackRefPtr(l, GWEN_RefPtr_new(p, l->refPtrInfo));
239 }
240 
241 
242 
244  GWEN_LIST_ENTRY *le;
245  GWEN__LISTPTR *lp;
246 
247  if (l->listPtr->refCount>1) {
248  GWEN__LISTPTR *nlp;
249 
250  /* only copy the list if someone else is using it */
251  nlp=GWEN__ListPtr_dup(l->listPtr);
252  GWEN__ListPtr_free(l->listPtr);
253  l->listPtr=nlp;
254  }
255  lp=l->listPtr;
256 
257  le=GWEN_ListEntry_new();
258  le->dataPtr=rp;
259  le->next=lp->first;
260  if (lp->first)
261  lp->first->previous=le;
262  lp->first=le;
263  if (!(lp->last))
264  lp->last=le;
265  lp->size++;
266  le->linkCount=1;
267 }
268 
269 
270 
271 void GWEN_List_PushFront(GWEN_LIST *l, void *p){
272  GWEN_List_PushFrontRefPtr(l, GWEN_RefPtr_new(p, l->refPtrInfo));
273 }
274 
275 
276 
278  assert(l);
279  assert(l->listPtr);
280  if (l->listPtr->first)
281  return GWEN_RefPtr_GetData(l->listPtr->first->dataPtr);
282  return 0;
283 }
284 
285 
286 
288  assert(l);
289  assert(l->listPtr);
290  if (l->listPtr->first)
291  return l->listPtr->first->dataPtr;
292  return 0;
293 }
294 
295 
296 
297 void *GWEN_List_GetBack(const GWEN_LIST *l){
298  assert(l);
299  assert(l->listPtr);
300  if (l->listPtr->last)
301  return GWEN_RefPtr_GetData(l->listPtr->last->dataPtr);
302  return 0;
303 }
304 
305 
306 
308  assert(l);
309  assert(l->listPtr);
310  if (l->listPtr->last)
311  return l->listPtr->last->dataPtr;
312  return 0;
313 }
314 
315 
316 
317 unsigned int GWEN_List_GetSize(const GWEN_LIST *l){
318  assert(l);
319  assert(l->listPtr);
320  return l->listPtr->size;
321 }
322 
324  return GWEN_List_GetSize(l) == 0;
325 }
326 
327 
329  GWEN_LIST_ENTRY *le;
330  GWEN__LISTPTR *lp;
331 
332  assert(l);
333  assert(l->listPtr);
334  if (l->listPtr->last==0)
335  return;
336  if (l->listPtr->refCount>1) {
337  GWEN__LISTPTR *nlp;
338 
339  /* only copy the list if someone else is using it */
340  nlp=GWEN__ListPtr_dup(l->listPtr);
341  GWEN__ListPtr_free(l->listPtr);
342  l->listPtr=nlp;
343  }
344  lp=l->listPtr;
345 
346  le=lp->last;
347  if (le) {
348  le->linkCount=0;
349  lp->last=le->previous;
350  if (le->previous) {
351  le->previous->next=0;
352  }
353  else {
354  lp->last=0;
355  lp->first=0;
356  }
358  lp->size--;
359  }
360 }
361 
362 
363 
365  GWEN_LIST_ENTRY *le;
366  GWEN__LISTPTR *lp;
367 
368  assert(l);
369  assert(l->listPtr);
370  if (l->listPtr->first==0)
371  return;
372  if (l->listPtr->refCount>1) {
373  GWEN__LISTPTR *nlp;
374 
375  /* only copy the list if someone else is using it */
376  nlp=GWEN__ListPtr_dup(l->listPtr);
377  GWEN__ListPtr_free(l->listPtr);
378  l->listPtr=nlp;
379  }
380  lp=l->listPtr;
381 
382  le=lp->first;
383  if (le) {
384  le->linkCount=0;
385  lp->first=le->next;
386  if (le->next) {
387  le->next->previous=0;
388  }
389  else {
390  lp->first=0;
391  lp->last=0;
392  }
394  lp->size--;
395  }
396 }
397 
398 
399 
401  /* GWEN__LISTPTR *lp; */
402 
403  assert(l);
404  if (l->listPtr->refCount>1) {
405  GWEN__LISTPTR *nlp;
406 
407  /* only copy the list if someone else is using it */
408  nlp=GWEN__ListPtr_dup(l->listPtr);
409  GWEN__ListPtr_free(l->listPtr);
410  l->listPtr=nlp;
411  }
412  else
413  GWEN__ListPtr_Clear(l->listPtr);
414 }
415 
416 
417 
419  GWEN_LIST_FOREACH_CB fn, void *user_data){
420  GWEN_LIST_ITERATOR *it;
421  void *el;
422  assert(l);
423 
424  it=GWEN_List_First(l);
425  if (!it)
426  return 0;
427  el=GWEN_ListIterator_Data(it);
428  while(el) {
429  el=fn(el, user_data);
430  if (el) {
432  return el;
433  }
434  el=GWEN_ListIterator_Next(it);
435  }
437  return 0;
438 }
439 
440 
441 
443  if (l->listPtr->refCount>1) {
444  GWEN__LISTPTR *nlp;
445 
446  /* only copy the list if someone else is using it */
447  nlp=GWEN__ListPtr_dup(l->listPtr);
448  GWEN__ListPtr_free(l->listPtr);
449  l->listPtr=nlp;
450  }
451 }
452 
453 
454 
456  GWEN_LIST_ENTRY *current;
457  GWEN__LISTPTR *lp;
458 
459  assert(l);
460  assert(l->listPtr);
461  if (l->listPtr->refCount>1) {
462  GWEN_LIST_ENTRY *tle;
463  GWEN__LISTPTR *nlp;
464  int i;
465 
466  /* find the position of the iterator within current list */
467  tle=it->current;
468  assert(tle);
469  i=0;
470  while(tle->previous) {
471  i++;
472  tle=tle->previous;
473  }
474 
475  /* copy the list */
476  nlp=GWEN__ListPtr_dup(l->listPtr);
477  GWEN__ListPtr_free(l->listPtr);
478  l->listPtr=nlp;
479 
480  /* seek and set the iterator position */
481  tle=l->listPtr->first;
482  assert(tle);
483  while(tle && i--) {
484  tle=tle->next;
485  }
486  assert(tle);
487  it->current=tle;
488  }
489  lp=l->listPtr;
490 
491  assert(it);
492  if (it->current) {
493  current=it->current;
494  if (it->current->linkCount==1) {
495  /* unlink from list */
496  if (lp->first==current)
497  lp->first=current->next;
498  if (lp->last==current)
499  lp->last=current->previous;
500 
501  /* unlink from next */
502  if (current->next) {
503  it->current=current->next;
504  current->next->usage++;
505  current->next->previous=current->previous;
506  }
507  else
508  it->current=0;
509  /* unlink from previous */
510  if (current->previous)
511  current->previous->next=current->next;
512  /* free */
513  current->usage--;
514  GWEN_ListEntry_free(current);
515  lp->size--;
516  }
517  else {
518  /* move iterator forwards even if the current entry has not
519  * been deleted. Thus making the return condition clear to the
520  * caller.
521  */
522  if (current->next) {
523  it->current=current->next;
524  current->next->usage++;
525  }
526  else
527  it->current=0;
528  current->usage--;
529  it->current->linkCount--;
530  }
531  }
532 }
533 
534 
535 
537  GWEN_LIST_ITERATOR *li;
538 
539  li=GWEN_List_First(l);
540  if (li) {
541  void *d;
542 
544  while(d) {
545  if (d==p) {
546  return li;
547  }
549  }
551  }
552  return 0;
553 }
554 
555 
556 
557 const void *GWEN_List_Contains(GWEN_LIST *l, const void *p) {
558  GWEN_LIST_ITERATOR *li;
559 
560  li = GWEN_List_FindIter(l, p);
561  if (li) {
563  return p;
564  }
565  return 0;
566 }
567 
568 
569 
570 void GWEN_List_Remove(GWEN_LIST *l, const void *p) {
571  GWEN_LIST_ITERATOR *li;
572 
573  li = GWEN_List_FindIter(l, p);
574  if (li) {
575  GWEN_List_Erase(l, li);
577  }
578 }
579 
580 
581 
583  GWEN_LIST_ITERATOR *li;
584 
585  assert(l);
586  assert(l->listPtr);
587  if (l->listPtr->first==0)
588  return 0;
589  li=GWEN_ListIterator_new(l);
590  li->current=l->listPtr->first;
591  if (li->current) {
592  li->current->usage++;
593  }
594  return li;
595 }
596 
597 
598 
600  GWEN_LIST_ITERATOR *li;
601 
602  assert(l);
603  assert(l->listPtr);
604  if (l->listPtr->last==0)
605  return 0;
606  li=GWEN_ListIterator_new(l);
607  li->current=l->listPtr->last;
608  if (li->current)
609  li->current->usage++;
610  return li;
611 }
612 
613 
614 
615 void GWEN_List_Dump(const GWEN_LIST *l, FILE *f, unsigned int indent){
616  GWEN_LIST_ENTRY *le;
617  unsigned int i;
618 
619  fprintf(f, "List contains %d entries\n", l->listPtr->size);
620  le=l->listPtr->first;
621  while(le) {
622  for (i=0; i<indent; i++) fprintf(f, " ");
623  fprintf(f, "List entry %p\n", (void*)le);
624  for (i=0; i<indent; i++) fprintf(f, " ");
625  fprintf(f, " Usage : %d\n", le->usage);
626  for (i=0; i<indent; i++) fprintf(f, " ");
627  fprintf(f, " Previous: %p\n", (void*)le->previous);
628  for (i=0; i<indent; i++) fprintf(f, " ");
629  fprintf(f, " Next : %p\n", (void*)le->next);
630  for (i=0; i<indent; i++) fprintf(f, " ");
631  fprintf(f, " Data : %p\n", (void*)GWEN_RefPtr_GetData(le->dataPtr));
632  le=le->next;
633  } /* while */
634 }
635 
636 
637 
638 
640  GWEN_LIST_ITERATOR *li;
641 
643  li->list=l;
644  return li;
645 }
646 
647 
648 
650  if (li) {
651  if (li->current)
652  GWEN_ListEntry_free(li->current);
653  GWEN_FREE_OBJECT(li);
654  }
655 }
656 
657 
658 
660  GWEN_REFPTR *rp;
661 
662  assert(li);
664  if (!rp)
665  return 0;
666  return GWEN_RefPtr_GetData(rp);
667 }
668 
669 
670 
672  GWEN_LIST_ENTRY *le;
673 
674  assert(li);
675 
676  le=li->current;
677  if (le)
678  le=le->previous;
679  if (li->current)
680  GWEN_ListEntry_free(li->current);
681  li->current=le;
682  if (le) {
683  le->usage++;
684  return le->dataPtr;
685  }
686  return 0;
687 }
688 
689 
690 
692  GWEN_REFPTR *rp;
693 
694  assert(li);
696  if (!rp)
697  return 0;
698  return GWEN_RefPtr_GetData(rp);
699 }
700 
701 
702 
704  GWEN_LIST_ENTRY *le;
705 
706  assert(li);
707 
708  le=li->current;
709  if (le)
710  le=le->next;
711  if (li->current)
712  GWEN_ListEntry_free(li->current);
713  li->current=le;
714  if (le) {
715  le->usage++;
716  return le->dataPtr;
717  }
718  return 0;
719 }
720 
721 
722 
724  assert(li);
725 
726  if (li->current)
727  return GWEN_RefPtr_GetData(li->current->dataPtr);
728  return 0;
729 }
730 
731 
732 
734  assert(li);
735 
736  if (li->current)
737  return li->current->dataPtr;
738  return 0;
739 }
740 
741 
742 
744  assert(li);
745 
746  if (li->current)
747  li->current->linkCount++;
748 }
749 
750 
751 
753  assert(li);
754 
755  assert(li->current);
756  return li->current->linkCount;
757 }
758 
759 
760 
761 
762 
763 
764 
765 
766 /* __________________________________________________________________________
767  * AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
768  * ConstList
769  * YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY
770  */
771 
772 
773 
775  return GWEN_List_new();
776 }
777 
778 
779 
781  GWEN_List_free(l);
782 }
783 
784 
785 
786 void GWEN_ConstList_PushBack(GWEN_CONSTLIST *l, const void *p){
787  GWEN_List_PushBack(l, (void*)p);
788 }
789 
790 
791 
792 void GWEN_ConstList_PushFront(GWEN_CONSTLIST *l, const void *p){
793  GWEN_List_PushFront(l, (void*)p);
794 }
795 
796 
797 
799  return GWEN_List_GetFront(l);
800 }
801 
802 
803 
805  return GWEN_List_GetBack(l);
806 }
807 
808 
809 
810 unsigned int GWEN_ConstList_GetSize(const GWEN_CONSTLIST *l){
811  return GWEN_List_GetSize(l);
812 }
813 
815  return GWEN_ConstList_GetSize(l) == 0;
816 }
817 
818 
819 
822 }
823 
824 
825 
828 }
829 
830 
831 
833  GWEN_List_Erase(l, it);
834 }
835 
836 
837 
839  GWEN_List_Clear(l);
840 }
841 
842 
845  void *user_data){
846  GWEN_LIST_ITERATOR *it;
847  const void *el;
848  assert(l);
849 
850  it = GWEN_List_First(l);
851  if (!it)
852  return 0;
853  el = GWEN_ListIterator_Data(it);
854  while(el) {
855  el = fn(el, user_data);
856  if (el) {
858  return el;
859  }
860  el = GWEN_ListIterator_Next(it);
861  }
863  return 0;
864 }
865 
866 
867 
870 
871  li=GWEN_ConstList_First(l);
872  if (li) {
873  const void *d;
874 
876  while(d) {
877  if (d==p) {
878  return li;
879  }
881  }
883  }
884  return 0;
885 }
886 
887 const void *GWEN_ConstList_Contains(const GWEN_CONSTLIST *l, const void *p) {
889 
890  li = GWEN_ConstList_FindIter(l, p);
891  if (li) {
893  return p;
894  }
895  return 0;
896 }
897 
898 void GWEN_ConstList_Remove(GWEN_CONSTLIST *l, const void *p) {
900 
901  li = GWEN_ConstList_FindIter(l, p);
902  if (li) {
903  GWEN_ConstList_Erase(l, li);
904  }
905 }
906 
908  return GWEN_List_First(l);
909 }
910 
911 
912 
914  return GWEN_List_Last(l);
915 }
916 
917 
918 
920  return GWEN_ListIterator_new(l);
921 }
922 
923 
924 
927 }
928 
929 
930 
932  return GWEN_ListIterator_Previous(li);
933 }
934 
935 
936 
938  return GWEN_ListIterator_Next(li);
939 }
940 
941 
942 
944  return GWEN_ListIterator_Data(li);
945 }
946 
947 
948 
949 
950 
951