1 /*********************************************************************
2 Functions for linked lists.
3 This is part of GNU Astronomy Utilities (Gnuastro) package.
4
5 Original author:
6 Mohammad Akhlaghi <mohammad@akhlaghi.org>
7 Contributing author(s):
8 Copyright (C) 2015-2021, Free Software Foundation, Inc.
9
10 Gnuastro is free software: you can redistribute it and/or modify it
11 under the terms of the GNU General Public License as published by the
12 Free Software Foundation, either version 3 of the License, or (at your
13 option) any later version.
14
15 Gnuastro is distributed in the hope that it will be useful, but
16 WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18 General Public License for more details.
19
20 You should have received a copy of the GNU General Public License
21 along with Gnuastro. If not, see <http://www.gnu.org/licenses/>.
22 **********************************************************************/
23 #include <config.h>
24
25 #include <stdio.h>
26 #include <errno.h>
27 #include <error.h>
28 #include <stdlib.h>
29 #include <assert.h>
30 #include <inttypes.h>
31
32 #include <gnuastro/list.h>
33 #include <gnuastro/blank.h>
34 #include <gnuastro/pointer.h>
35
36 #include <gnuastro-internal/checkset.h>
37
38
39
40
41
42
43
44
45
46 /****************************************************************
47 ***************** String ********************
48 ****************************************************************/
49 void
gal_list_str_add(gal_list_str_t ** list,char * value,int allocate)50 gal_list_str_add(gal_list_str_t **list, char *value,
51 int allocate)
52 {
53 gal_list_str_t *newnode;
54
55 /* If the value is a NULL pointer, don't add to the list. */
56 if(value==NULL) return;
57
58 errno=0;
59 newnode=malloc(sizeof *newnode);
60 if(newnode==NULL)
61 error(EXIT_FAILURE, errno, "%s: allocating new node", __func__);
62
63 if(allocate)
64 gal_checkset_allocate_copy(value, &newnode->v);
65 else
66 newnode->v=value;
67
68 newnode->next=*list;
69 *list=newnode;
70 }
71
72
73
74
75
76 char *
gal_list_str_pop(gal_list_str_t ** list)77 gal_list_str_pop(gal_list_str_t **list)
78 {
79 char *out=NULL;
80 gal_list_str_t *tmp;
81 if(*list)
82 {
83 tmp=*list;
84 out=tmp->v;
85 *list=tmp->next;
86 free(tmp);
87 }
88 return out;
89 }
90
91
92
93
94
95 size_t
gal_list_str_number(gal_list_str_t * list)96 gal_list_str_number(gal_list_str_t *list)
97 {
98 size_t num=0;
99 gal_list_str_t *tmp;
100 for(tmp=list;tmp!=NULL;tmp=tmp->next) ++num;
101 return num;
102 }
103
104
105
106
107
108 gal_list_str_t *
gal_list_str_last(gal_list_str_t * list)109 gal_list_str_last(gal_list_str_t *list)
110 {
111 if(list)
112 {
113 while(list->next!=NULL) list=list->next;
114 return list;
115 }
116 else return NULL;
117 }
118
119
120
121
122
123 void
gal_list_str_print(gal_list_str_t * list)124 gal_list_str_print(gal_list_str_t *list)
125 {
126 gal_list_str_t *tmp;
127 for(tmp=list; tmp!=NULL; tmp=tmp->next)
128 printf("%s\n", tmp->v);
129 }
130
131
132
133
134
135 void
gal_list_str_reverse(gal_list_str_t ** list)136 gal_list_str_reverse(gal_list_str_t **list)
137 {
138 char *thisstring;
139 gal_list_str_t *correctorder=NULL;
140
141 /* Only do the reversal if there is more than one element. */
142 if( *list && (*list)->next )
143 {
144 while(*list!=NULL)
145 {
146 thisstring=gal_list_str_pop(list);
147 gal_list_str_add(&correctorder, thisstring, 0);
148 }
149 *list=correctorder;
150 }
151 }
152
153
154
155
156
157 void
gal_list_str_free(gal_list_str_t * list,int freevalue)158 gal_list_str_free(gal_list_str_t *list, int freevalue)
159 {
160 gal_list_str_t *tmp;
161 while(list!=NULL)
162 {
163 tmp=list->next;
164 if(freevalue)
165 free(list->v);
166 free(list);
167 list=tmp;
168 }
169 }
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190 /****************************************************************
191 ***************** int ********************
192 ****************************************************************/
193 void
gal_list_i32_add(gal_list_i32_t ** list,int32_t value)194 gal_list_i32_add(gal_list_i32_t **list, int32_t value)
195 {
196 gal_list_i32_t *newnode;
197
198 errno=0;
199 newnode=malloc(sizeof *newnode);
200 if(newnode==NULL)
201 error(EXIT_FAILURE, errno, "%s: allocating new node", __func__);
202
203 newnode->v=value;
204 newnode->next=*list;
205 *list=newnode;
206 }
207
208
209
210
211
212 int32_t
gal_list_i32_pop(gal_list_i32_t ** list)213 gal_list_i32_pop(gal_list_i32_t **list)
214 {
215 gal_list_i32_t *tmp;
216 int out=GAL_BLANK_INT32;
217
218 if(*list)
219 {
220 tmp=*list;
221 out=tmp->v;
222 *list=tmp->next;
223 free(tmp);
224 }
225 return out;
226 }
227
228
229
230
231
232 size_t
gal_list_i32_number(gal_list_i32_t * list)233 gal_list_i32_number(gal_list_i32_t *list)
234 {
235 size_t num=0;
236 gal_list_i32_t *tmp;
237 for(tmp=list;tmp!=NULL;tmp=tmp->next)
238 ++num;
239 return num;
240 }
241
242
243
244
245
246 gal_list_i32_t *
gal_list_i32_last(gal_list_i32_t * list)247 gal_list_i32_last(gal_list_i32_t *list)
248 {
249 if(list)
250 {
251 while(list->next!=NULL) list=list->next;
252 return list;
253 }
254 else return NULL;
255 }
256
257
258
259
260
261 void
gal_list_i32_print(gal_list_i32_t * list)262 gal_list_i32_print(gal_list_i32_t *list)
263 {
264 gal_list_i32_t *tmp;
265 for(tmp=list; tmp!=NULL; tmp=tmp->next)
266 printf("%"PRId32"\n", tmp->v);
267 }
268
269
270
271
272
273 void
gal_list_i32_reverse(gal_list_i32_t ** list)274 gal_list_i32_reverse(gal_list_i32_t **list)
275 {
276 int thisnum;
277 gal_list_i32_t *correctorder=NULL;
278
279 if( *list && (*list)->next )
280 {
281 while(*list!=NULL)
282 {
283 thisnum=gal_list_i32_pop(list);
284 gal_list_i32_add(&correctorder, thisnum);
285 }
286 *list=correctorder;
287 }
288 }
289
290
291
292
293
294 int32_t *
gal_list_i32_to_array(gal_list_i32_t * list,int reverse,size_t * num)295 gal_list_i32_to_array(gal_list_i32_t *list, int reverse, size_t *num)
296 {
297 size_t i;
298 int32_t *out=NULL;
299 gal_list_i32_t *tmp;
300
301 *num=gal_list_i32_number(list);
302
303 if(*num)
304 {
305 out=gal_pointer_allocate(GAL_TYPE_SIZE_T, *num, 0, __func__, "out");
306
307 i = reverse ? *num-1: 0;
308 if(reverse)
309 for(tmp=list;tmp!=NULL;tmp=tmp->next)
310 out[i--]=tmp->v;
311 else
312 for(tmp=list;tmp!=NULL;tmp=tmp->next)
313 out[i++]=tmp->v;
314 }
315
316 return out;
317 }
318
319
320
321
322
323 void
gal_list_i32_free(gal_list_i32_t * list)324 gal_list_i32_free(gal_list_i32_t *list)
325 {
326 gal_list_i32_t *tmp, *ttmp;
327 tmp=list;
328 while(tmp!=NULL)
329 {
330 ttmp=tmp->next;
331 free(tmp);
332 tmp=ttmp;
333 }
334 }
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355 /****************************************************************
356 ***************** size_t ********************
357 ****************************************************************/
358 void
gal_list_sizet_add(gal_list_sizet_t ** list,size_t value)359 gal_list_sizet_add(gal_list_sizet_t **list, size_t value)
360 {
361 gal_list_sizet_t *newnode;
362
363 errno=0;
364 newnode=malloc(sizeof *newnode);
365 if(newnode==NULL)
366 error(EXIT_FAILURE, errno, "%s: allocating new node", __func__);
367
368 newnode->v=value;
369 newnode->next=*list;
370 *list=newnode;
371 }
372
373
374
375
376
377 size_t
gal_list_sizet_pop(gal_list_sizet_t ** list)378 gal_list_sizet_pop(gal_list_sizet_t **list)
379 {
380 gal_list_sizet_t *tmp;
381 size_t out=GAL_BLANK_SIZE_T;
382
383 if(list)
384 {
385 tmp=*list;
386 out=tmp->v;
387 *list=tmp->next;
388 free(tmp);
389 }
390 return out;
391 }
392
393
394
395
396
397 size_t
gal_list_sizet_number(gal_list_sizet_t * list)398 gal_list_sizet_number(gal_list_sizet_t *list)
399 {
400 size_t num=0;
401 gal_list_sizet_t *tmp;
402 for(tmp=list;tmp!=NULL;tmp=tmp->next)
403 ++num;
404 return num;
405 }
406
407
408
409
410
411 gal_list_sizet_t *
gal_list_sizet_last(gal_list_sizet_t * list)412 gal_list_sizet_last(gal_list_sizet_t *list)
413 {
414 if(list)
415 {
416 while(list->next!=NULL) list=list->next;
417 return list;
418 }
419 else return NULL;
420 }
421
422
423
424
425
426 void
gal_list_sizet_print(gal_list_sizet_t * list)427 gal_list_sizet_print(gal_list_sizet_t *list)
428 {
429 gal_list_sizet_t *tmp;
430 for(tmp=list;tmp!=NULL;tmp=tmp->next)
431 printf("%zu\n", tmp->v);
432 return;
433 }
434
435
436
437
438
439 void
gal_list_sizet_reverse(gal_list_sizet_t ** list)440 gal_list_sizet_reverse(gal_list_sizet_t **list)
441 {
442 size_t thisnum;
443 gal_list_sizet_t *correctorder=NULL;
444
445 if( *list && (*list)->next )
446 {
447 while(*list!=NULL)
448 {
449 thisnum=gal_list_sizet_pop(list);
450 gal_list_sizet_add(&correctorder, thisnum);
451 }
452 *list=correctorder;
453 }
454 }
455
456
457
458
459
460 size_t *
gal_list_sizet_to_array(gal_list_sizet_t * list,int reverse,size_t * num)461 gal_list_sizet_to_array(gal_list_sizet_t *list, int reverse, size_t *num)
462 {
463 size_t i, *out=NULL;
464 gal_list_sizet_t *tmp;
465
466 *num=gal_list_sizet_number(list);
467
468 if(*num)
469 {
470 out=gal_pointer_allocate(GAL_TYPE_SIZE_T, *num, 0, __func__, "out");
471
472 i = reverse ? *num-1: 0;
473 if(reverse)
474 for(tmp=list;tmp!=NULL;tmp=tmp->next)
475 out[i--]=tmp->v;
476 else
477 for(tmp=list;tmp!=NULL;tmp=tmp->next)
478 out[i++]=tmp->v;
479 }
480
481 return out;
482 }
483
484
485
486
487
488 void
gal_list_sizet_free(gal_list_sizet_t * list)489 gal_list_sizet_free(gal_list_sizet_t *list)
490 {
491 gal_list_sizet_t *tmp, *ttmp;
492 tmp=list;
493 while(tmp!=NULL)
494 {
495 ttmp=tmp->next;
496 free(tmp);
497 tmp=ttmp;
498 }
499 }
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520 /****************************************************************
521 ***************** Float ********************
522 ****************************************************************/
523 void
gal_list_f32_add(gal_list_f32_t ** list,float value)524 gal_list_f32_add(gal_list_f32_t **list, float value)
525 {
526 struct gal_list_f32_t *newnode;
527
528 errno=0;
529 newnode=malloc(sizeof *newnode);
530 if(newnode==NULL)
531 error(EXIT_FAILURE, errno, "%s: allocating new node", __func__);
532
533 newnode->v=value;
534 newnode->next=*list;
535 *list=newnode;
536 }
537
538
539
540
541
542 float
gal_list_f32_pop(gal_list_f32_t ** list)543 gal_list_f32_pop(gal_list_f32_t **list)
544 {
545 float out=NAN;
546 gal_list_f32_t *tmp;
547
548 if(*list)
549 {
550 tmp=*list;
551 out=tmp->v;
552 *list=tmp->next;
553 free(tmp);
554 }
555 return out;
556 }
557
558
559
560
561
562 size_t
gal_list_f32_number(gal_list_f32_t * list)563 gal_list_f32_number(gal_list_f32_t *list)
564 {
565 size_t num=0;
566 gal_list_f32_t *tmp;
567 for(tmp=list;tmp!=NULL;tmp=tmp->next)
568 ++num;
569 return num;
570 }
571
572
573
574
575
576 gal_list_f32_t *
gal_list_f32_last(gal_list_f32_t * list)577 gal_list_f32_last(gal_list_f32_t *list)
578 {
579 if(list)
580 {
581 while(list->next!=NULL) list=list->next;
582 return list;
583 }
584 else return NULL;
585 }
586
587
588
589
590
591 void
gal_list_f32_reverse(gal_list_f32_t ** list)592 gal_list_f32_reverse(gal_list_f32_t **list)
593 {
594 float thisnum;
595 gal_list_f32_t *correctorder=NULL;
596
597 if( *list && (*list)->next )
598 {
599 while(*list!=NULL)
600 {
601 thisnum=gal_list_f32_pop(list);
602 gal_list_f32_add(&correctorder, thisnum);
603 }
604 *list=correctorder;
605 }
606 }
607
608
609
610
611
612 void
gal_list_f32_print(gal_list_f32_t * list)613 gal_list_f32_print(gal_list_f32_t *list)
614 {
615 gal_list_f32_t *tmp;
616 for(tmp=list;tmp!=NULL;tmp=tmp->next)
617 printf("%f\n", tmp->v);
618 return;
619 }
620
621
622
623
624
625 float *
gal_list_f32_to_array(gal_list_f32_t * list,int reverse,size_t * num)626 gal_list_f32_to_array(gal_list_f32_t *list, int reverse, size_t *num)
627 {
628 size_t i;
629 float *out=NULL;
630 gal_list_f32_t *tmp;
631
632 /* Find the number of elements: */
633 *num=gal_list_f32_number(list);
634
635 /* If there is actually anything in the list, then allocate the array and
636 fill it in. */
637 if(*num)
638 {
639 /* Allocate the space: */
640 out=gal_pointer_allocate(GAL_TYPE_FLOAT32, *num, 0, __func__, "out");
641
642 /* Fill in the array. */
643 i = reverse ? *num-1: 0;
644 if(reverse)
645 for(tmp=list;tmp!=NULL;tmp=tmp->next)
646 out[i--]=tmp->v;
647 else
648 for(tmp=list;tmp!=NULL;tmp=tmp->next)
649 out[i++]=tmp->v;
650 }
651
652 /* Return the created array. */
653 return out;
654 }
655
656
657
658
659
660 void
gal_list_f32_free(gal_list_f32_t * list)661 gal_list_f32_free(gal_list_f32_t *list)
662 {
663 gal_list_f32_t *tmp, *ttmp;
664 tmp=list;
665 while(tmp!=NULL)
666 {
667 ttmp=tmp->next;
668 free(tmp);
669 tmp=ttmp;
670 }
671 }
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692 /****************************************************************
693 ***************** Double ********************
694 ****************************************************************/
695 void
gal_list_f64_add(gal_list_f64_t ** list,double value)696 gal_list_f64_add(gal_list_f64_t **list, double value)
697 {
698 gal_list_f64_t *newnode;
699
700 errno=0;
701 newnode=malloc(sizeof *newnode);
702 if(newnode==NULL)
703 error(EXIT_FAILURE, errno, "%s: allocating new node", __func__);
704
705 newnode->v=value;
706 newnode->next=*list;
707 *list=newnode;
708 }
709
710
711
712
713
714 double
gal_list_f64_pop(gal_list_f64_t ** list)715 gal_list_f64_pop(gal_list_f64_t **list)
716 {
717 double out=NAN;
718 gal_list_f64_t *tmp;
719
720 if(*list)
721 {
722 tmp=*list;
723 out=tmp->v;
724 *list=tmp->next;
725 free(tmp);
726 }
727 return out;
728 }
729
730
731
732
733
734 size_t
gal_list_f64_number(gal_list_f64_t * list)735 gal_list_f64_number(gal_list_f64_t *list)
736 {
737 size_t num=0;
738 gal_list_f64_t *tmp;
739 for(tmp=list;tmp!=NULL;tmp=tmp->next)
740 ++num;
741 return num;
742 }
743
744
745
746
747
748 gal_list_f64_t *
gal_list_f64_last(gal_list_f64_t * list)749 gal_list_f64_last(gal_list_f64_t *list)
750 {
751 if(list)
752 {
753 while(list->next!=NULL) list=list->next;
754 return list;
755 }
756 else return NULL;
757 }
758
759
760
761
762
763 void
gal_list_f64_print(gal_list_f64_t * list)764 gal_list_f64_print(gal_list_f64_t *list)
765 {
766 gal_list_f64_t *tmp;
767 for(tmp=list;tmp!=NULL;tmp=tmp->next)
768 printf("%f\n", tmp->v);
769 return;
770 }
771
772
773
774
775
776 void
gal_list_f64_reverse(gal_list_f64_t ** list)777 gal_list_f64_reverse(gal_list_f64_t **list)
778 {
779 double thisvalue;
780 gal_list_f64_t *correctorder=NULL;
781
782 /* Only do the reversal if there is more than one element. */
783 if( *list && (*list)->next )
784 {
785 while(*list!=NULL)
786 {
787 thisvalue=gal_list_f64_pop(list);
788 gal_list_f64_add(&correctorder, thisvalue);
789 }
790 *list=correctorder;
791 }
792 }
793
794
795
796
797 double *
gal_list_f64_to_array(gal_list_f64_t * list,int reverse,size_t * num)798 gal_list_f64_to_array(gal_list_f64_t *list, int reverse, size_t *num)
799 {
800 size_t i;
801 double *out=NULL;
802 gal_list_f64_t *tmp;
803
804 /* Find the number of elements: */
805 *num=gal_list_f64_number(list);
806
807 /* If there is actually anything in the list, then allocate the array and
808 fill it in. */
809 if(*num)
810 {
811 /* Allocate the space: */
812 out=gal_pointer_allocate(GAL_TYPE_FLOAT64, *num, 0, __func__, "out");
813
814 /* Fill in the array. */
815 i = reverse ? *num-1: 0;
816 if(reverse)
817 for(tmp=list;tmp!=NULL;tmp=tmp->next)
818 out[i--]=tmp->v;
819 else
820 for(tmp=list;tmp!=NULL;tmp=tmp->next)
821 out[i++]=tmp->v;
822 }
823
824 /* Return the created array. */
825 return out;
826 }
827
828
829
830
831
832 void
gal_list_f64_free(gal_list_f64_t * list)833 gal_list_f64_free(gal_list_f64_t *list)
834 {
835 gal_list_f64_t *tmp, *ttmp;
836 tmp=list;
837 while(tmp!=NULL)
838 {
839 ttmp=tmp->next;
840 free(tmp);
841 tmp=ttmp;
842 }
843 }
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863 /****************************************************************
864 ***************** void * ********************
865 ****************************************************************/
866 void
gal_list_void_add(gal_list_void_t ** list,void * value)867 gal_list_void_add(gal_list_void_t **list, void *value)
868 {
869 gal_list_void_t *newnode;
870
871 errno=0;
872 newnode=malloc(sizeof *newnode);
873 if(newnode==NULL)
874 error(EXIT_FAILURE, errno, "%s: allocating new node", __func__);
875
876 newnode->v=value;
877 newnode->next=*list;
878 *list=newnode;
879 }
880
881
882
883
884
885 void *
gal_list_void_pop(gal_list_void_t ** list)886 gal_list_void_pop(gal_list_void_t **list)
887 {
888 void *out=NULL;
889 gal_list_void_t *tmp;
890
891 if(*list)
892 {
893 tmp=*list;
894 out=tmp->v;
895 *list=tmp->next;
896 free(tmp);
897 }
898 return out;
899 }
900
901
902
903
904
905 size_t
gal_list_void_number(gal_list_void_t * list)906 gal_list_void_number(gal_list_void_t *list)
907 {
908 size_t num=0;
909 gal_list_void_t *tmp;
910 for(tmp=list;tmp!=NULL;tmp=tmp->next)
911 ++num;
912 return num;
913 }
914
915
916
917
918
919 gal_list_void_t *
gal_list_void_last(gal_list_void_t * list)920 gal_list_void_last(gal_list_void_t *list)
921 {
922 if(list)
923 {
924 while(list->next!=NULL) list=list->next;
925 return list;
926 }
927 else return NULL;
928 }
929
930
931
932
933
934 void
gal_list_void_reverse(gal_list_void_t ** list)935 gal_list_void_reverse(gal_list_void_t **list)
936 {
937 void *thisptr;
938 gal_list_void_t *correctorder=NULL;
939
940 if( *list && (*list)->next )
941 {
942 while(*list!=NULL)
943 {
944 thisptr=gal_list_void_pop(list);
945 gal_list_void_add(&correctorder, thisptr);
946 }
947 *list=correctorder;
948 }
949 }
950
951
952
953
954
955 void
gal_list_void_free(gal_list_void_t * list,int freevalue)956 gal_list_void_free(gal_list_void_t *list, int freevalue)
957 {
958 gal_list_void_t *tmp=list, *ttmp;
959 while(tmp!=NULL)
960 {
961 if(freevalue) free(tmp->v);
962 ttmp=tmp->next;
963 free(tmp);
964 tmp=ttmp;
965 }
966 }
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987 /****************************************************************
988 **************** Ordered size_t ********************
989 ****************************************************************/
990 /* We want to put the nodes in order based on the 'tosort' value of
991 each node. The top element should always have the smallest radius. */
992 void
gal_list_osizet_add(gal_list_osizet_t ** list,size_t value,float tosort)993 gal_list_osizet_add(gal_list_osizet_t **list,
994 size_t value, float tosort)
995 {
996 gal_list_osizet_t *newnode, *tmp=*list, *prev=NULL;
997
998 errno=0;
999 newnode=malloc(sizeof *newnode);
1000 if(newnode==NULL)
1001 error(EXIT_FAILURE, errno, "%s: allocating new node", __func__);
1002
1003 newnode->v=value;
1004 newnode->s=tosort;
1005
1006 /* *list points to the smallest value in the queue!*/
1007 while(tmp!=NULL)
1008 {
1009 if(tosort<tmp->s) break;
1010 /* No need for else, it will only come here if the condition
1011 above is not satisfied. */
1012 prev=tmp;
1013 tmp=tmp->next;
1014 }
1015
1016 if(tmp==NULL) /* This is the largest value so far. */
1017 { /* '*list' only changes if it is NULL. */
1018 newnode->next=NULL;
1019 if(prev) prev->next=newnode; /* 'prev' is not NULL! */
1020 else *list=newnode; /* Only for initial node. */
1021 }
1022 else
1023 {
1024 if(prev) prev->next=newnode;
1025 else *list=newnode; /* 'tosort' is smaller than all. */
1026 newnode->next=tmp;
1027 }
1028 }
1029
1030
1031
1032
1033
1034 /* Note that the popped element is the smallest! */
1035 size_t
gal_list_osizet_pop(gal_list_osizet_t ** list,float * sortvalue)1036 gal_list_osizet_pop(gal_list_osizet_t **list, float *sortvalue)
1037 {
1038 size_t value;
1039 gal_list_osizet_t *tmp=*list;
1040
1041 if(*list)
1042 {
1043 value=tmp->v;
1044 *sortvalue=tmp->s;
1045 *list=tmp->next;
1046 free(tmp);
1047 }
1048 else
1049 {
1050 value=GAL_BLANK_SIZE_T;
1051 *sortvalue=NAN;
1052 }
1053
1054 return value;
1055 }
1056
1057
1058
1059
1060
1061 /* Add the elements of an gal_list_osll to a gal_list_sll. */
1062 void
gal_list_osizet_to_sizet_free(gal_list_osizet_t * in,gal_list_sizet_t ** out)1063 gal_list_osizet_to_sizet_free(gal_list_osizet_t *in,
1064 gal_list_sizet_t **out)
1065 {
1066 gal_list_osizet_t *tmp;
1067 while(in!=NULL)
1068 {
1069 tmp=in->next;
1070 gal_list_sizet_add(out, in->v);
1071 free(in);
1072 in=tmp;
1073 }
1074 }
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095 /****************************************************************
1096 ****************** Two way, Ordered SLL ********************
1097 ***************** size_t ********************
1098 ****************************************************************/
1099 /* Doubly-linked ordered size_t list can be visualized like this:
1100
1101 largest pointer
1102 |
1103 NULL <-- (v0,s0) <--> (v1,s1) <--> ... (vn,sn) --> NULL
1104 |
1105 smallest pointer
1106
1107 Where s(n)>s(n+1) for all n.
1108 */
1109 /* Very similar to Ordered SLL, but now it is two way. */
1110 void
gal_list_dosizet_add(gal_list_dosizet_t ** largest,gal_list_dosizet_t ** smallest,size_t value,float tosort)1111 gal_list_dosizet_add(gal_list_dosizet_t **largest,
1112 gal_list_dosizet_t **smallest, size_t value, float tosort)
1113 {
1114 gal_list_dosizet_t *newnode, *tmp=*largest;
1115
1116 errno=0;
1117 newnode=malloc(sizeof *newnode);
1118 if(newnode==NULL)
1119 error(EXIT_FAILURE, errno, "%s: allocating new node", __func__);
1120
1121 newnode->v=value;
1122 newnode->s=tosort;
1123 newnode->prev=NULL;
1124
1125 while(tmp!=NULL)
1126 {
1127 if(tosort >= tmp->s) break;
1128 /* No need for else, it will only come here if the condition
1129 above is not satisfied. */
1130 newnode->prev=tmp;
1131 tmp=tmp->next;
1132 }
1133
1134 if(tmp==NULL) /* This is the smallest value so far. */
1135 { /* '*largest' only changes if it is NULL. */
1136 newnode->next=NULL;
1137 *smallest=newnode;
1138 if(newnode->prev) /* 'prev' is not NULL! */
1139 newnode->prev->next=newnode;
1140 else /* 'prev is NULL, Only first. */
1141 *largest=newnode;
1142 }
1143 else
1144 {
1145 if(newnode->prev)
1146 {
1147 newnode->prev->next->prev=newnode;
1148 newnode->prev->next=newnode;
1149 }
1150 else
1151 {
1152 (*largest)->prev=newnode;
1153 *largest=newnode; /* 'tosort' is larger than all. */
1154 }
1155 newnode->next=tmp;
1156 }
1157 }
1158
1159
1160
1161
1162
1163 /* Note that start has to be initialized. */
1164 size_t
gal_list_dosizet_pop_smallest(gal_list_dosizet_t ** largest,gal_list_dosizet_t ** smallest,float * tosort)1165 gal_list_dosizet_pop_smallest(gal_list_dosizet_t **largest,
1166 gal_list_dosizet_t **smallest, float *tosort)
1167 {
1168 size_t value;
1169 gal_list_dosizet_t *tmp=*smallest;
1170
1171 if(*smallest)
1172 {
1173 value=tmp->v;
1174 *tosort=tmp->s;
1175
1176 *smallest=tmp->prev;
1177 free(tmp);
1178 if(*smallest)
1179 (*smallest)->next=NULL;
1180 else
1181 *largest=NULL;
1182 }
1183 else
1184 {
1185 /* If 'smallest' is NULL, 'largest' should also be NULL. */
1186 if(*largest)
1187 error(EXIT_FAILURE, 0, "%s: 'largest' and 'smallest' pointers must "
1188 "both be non-NULL or both be NULL. However, in this call, "
1189 "'smallest' was NULL while 'largest' isn't NULL", __func__);
1190 value=GAL_BLANK_SIZE_T;
1191 *tosort=NAN;
1192 }
1193
1194 /*printf("Popped v: %zu, s: %f\n", *value, *tosort);*/
1195
1196 return value;
1197 }
1198
1199
1200
1201
1202
1203 void
gal_list_dosizet_print(gal_list_dosizet_t * largest,gal_list_dosizet_t * smallest)1204 gal_list_dosizet_print(gal_list_dosizet_t *largest,
1205 gal_list_dosizet_t *smallest)
1206 {
1207 size_t counter=1; /* We are not counting array elements :-D ! */
1208 while(largest!=NULL)
1209 {
1210 printf("\t%-5zu (%zu, %.4f) \n", counter++,
1211 largest->v, largest->s);
1212 largest=largest->next;
1213 printf("\t\t\t\t(%zu, %.4f)\n", smallest->v, smallest->s);
1214 smallest=smallest->prev;
1215 }
1216 printf("\n");
1217 }
1218
1219
1220
1221
1222
1223 void
gal_list_dosizet_to_sizet(gal_list_dosizet_t * in,gal_list_sizet_t ** out)1224 gal_list_dosizet_to_sizet(gal_list_dosizet_t *in, gal_list_sizet_t **out)
1225 {
1226 gal_list_dosizet_t *tmp;
1227 while(in!=NULL)
1228 {
1229 tmp=in->next;
1230 gal_list_sizet_add(out, in->v);
1231 free(in);
1232 in=tmp;
1233 }
1234 }
1235
1236
1237
1238
1239
1240 void
gal_list_dosizet_free(gal_list_dosizet_t * largest)1241 gal_list_dosizet_free(gal_list_dosizet_t *largest)
1242 {
1243 gal_list_dosizet_t *tmp;
1244 while(largest!=NULL)
1245 {
1246 tmp=largest->next;
1247 free(largest);
1248 largest=tmp;
1249 }
1250 }
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271 /*********************************************************************/
1272 /************* Data structure as a linked list ******************/
1273 /*********************************************************************/
1274 /* Add a new data structure to the top of an existing linked list of data
1275 structures. Note that if the new node is its self a list, all its nodes
1276 will be added to the list. */
1277 void
gal_list_data_add(gal_data_t ** list,gal_data_t * newnode)1278 gal_list_data_add(gal_data_t **list, gal_data_t *newnode)
1279 {
1280 gal_data_t *tmp=newnode, *toadd;
1281
1282 /* Check if newnode is itself a list or not. */
1283 if(newnode->next)
1284 {
1285 /* Go onto the last node in newnode's existing list. */
1286 while(tmp->next) tmp=tmp->next;
1287
1288 /* Set the last node as the node to add to the list. */
1289 toadd=tmp;
1290 }
1291 else
1292 /* Its not a list, so just set it to 'toadd'. */
1293 toadd=newnode;
1294
1295
1296 /* Set the next element of toadd and update what list points to.*/
1297 toadd->next=*list;
1298 *list=newnode;
1299 }
1300
1301
1302
1303
1304
1305 void
gal_list_data_add_alloc(gal_data_t ** list,void * array,uint8_t type,size_t ndim,size_t * dsize,struct wcsprm * wcs,int clear,size_t minmapsize,int quietmmap,char * name,char * unit,char * comment)1306 gal_list_data_add_alloc(gal_data_t **list, void *array, uint8_t type,
1307 size_t ndim, size_t *dsize, struct wcsprm *wcs,
1308 int clear, size_t minmapsize, int quietmmap,
1309 char *name, char *unit, char *comment)
1310 {
1311 gal_data_t *newnode;
1312
1313 /* Put all the input information into a new data structure node. */
1314 newnode=gal_data_alloc(array, type, ndim, dsize, wcs, clear,
1315 minmapsize, quietmmap, name, unit, comment);
1316
1317 /* Add the new node to the list. */
1318 gal_list_data_add(list, newnode);
1319 }
1320
1321
1322
1323
1324
1325 gal_data_t *
gal_list_data_pop(gal_data_t ** list)1326 gal_list_data_pop(gal_data_t **list)
1327 {
1328 gal_data_t *out=NULL;
1329
1330 /* If list is not empty. */
1331 if(*list)
1332 {
1333 /* Keep the top pointer. */
1334 out=*list;
1335
1336 /* Move the list pointer to the next node. */
1337 *list=out->next;
1338
1339 /* Set the next poitner of the out pointer to NULL so it isn't
1340 interpretted as a list any more. */
1341 out->next=NULL;
1342 }
1343 return out;
1344 }
1345
1346
1347
1348
1349
1350 void
gal_list_data_reverse(gal_data_t ** list)1351 gal_list_data_reverse(gal_data_t **list)
1352 {
1353 gal_data_t *popped, *in=*list, *reversed=NULL;
1354
1355 /* Only do the job if the list is not NULL and has more than one node. */
1356 if( in && in->next )
1357 {
1358 while(in!=NULL)
1359 {
1360 popped=gal_list_data_pop(&in);
1361 gal_list_data_add(&reversed, popped);
1362 }
1363 *list=reversed;
1364 }
1365 }
1366
1367
1368
1369
1370
1371 gal_data_t **
gal_list_data_to_array_ptr(gal_data_t * list,size_t * num)1372 gal_list_data_to_array_ptr(gal_data_t *list, size_t *num)
1373 {
1374 size_t i, n;
1375 gal_data_t *tmp, **out;
1376
1377 /* Count how many columns are necessary. */
1378 n=*num=gal_list_data_number(list);
1379
1380 /* Allocate space for the array. */
1381 errno=0;
1382 out=malloc(n * sizeof *out);
1383 if(out==NULL)
1384 error(EXIT_FAILURE, 0, "%s: couldn't allocate %zu bytes", __func__,
1385 n * sizeof *out);
1386
1387 /* Fill up the array with the pointers and return. */
1388 i=0;
1389 for(tmp=list;tmp!=NULL;tmp=tmp->next) out[i++]=tmp;
1390 return out;
1391 }
1392
1393
1394
1395
1396
1397 size_t
gal_list_data_number(gal_data_t * list)1398 gal_list_data_number(gal_data_t *list)
1399 {
1400 size_t num=0;
1401 while(list!=NULL)
1402 {
1403 ++num;
1404 list=list->next;
1405 }
1406 return num;
1407 }
1408
1409
1410
1411
1412
1413 gal_data_t *
gal_list_data_last(gal_data_t * list)1414 gal_list_data_last(gal_data_t *list)
1415 {
1416 if(list)
1417 {
1418 while(list->next!=NULL) list=list->next;
1419 return list;
1420 }
1421 else return NULL;
1422 }
1423
1424
1425
1426
1427 void
gal_list_data_free(gal_data_t * list)1428 gal_list_data_free(gal_data_t *list)
1429 {
1430 struct gal_data_t *tmp;
1431 while(list!=NULL)
1432 {
1433 tmp=list->next;
1434 gal_data_free(list);
1435 list=tmp;
1436 }
1437 }
1438