MagickCore 7.1.1
Convert, Edit, Or Compose Bitmap Images
Loading...
Searching...
No Matches
linked-list.c
1/*
2%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3% %
4% %
5% %
6% L IIIII N N K K EEEEE DDDD L IIIII SSSSS TTTTT %
7% L I NN N K K E D D L I SS T %
8% L I N N N KKK EEE D D = L I SSS T %
9% L I N NN K K E D D L I SS T %
10% LLLLL IIIII N N K K EEEEE DDDD LLLLL IIIII SSSSS T %
11% %
12% %
13% MagickCore Linked-list Methods %
14% %
15% Software Design %
16% Cristy %
17% December 2002 %
18% %
19% %
20% Copyright @ 1999 ImageMagick Studio LLC, a non-profit organization %
21% dedicated to making software imaging solutions freely available. %
22% %
23% You may not use this file except in compliance with the License. You may %
24% obtain a copy of the License at %
25% %
26% https://imagemagick.org/script/license.php %
27% %
28% Unless required by applicable law or agreed to in writing, software %
29% distributed under the License is distributed on an "AS IS" BASIS, %
30% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. %
31% See the License for the specific language governing permissions and %
32% limitations under the License. %
33% %
34%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
35%
36% This module implements the standard handy hash and linked-list methods for
37% storing and retrieving large numbers of data elements. It is loosely based
38% on the Java implementation of these algorithms.
39%
40*/
41␌
42/*
43 Include declarations.
44*/
45#include "MagickCore/studio.h"
46#include "MagickCore/exception.h"
47#include "MagickCore/exception-private.h"
48#include "MagickCore/linked-list.h"
49#include "MagickCore/linked-list-private.h"
50#include "MagickCore/locale_.h"
51#include "MagickCore/memory_.h"
52#include "MagickCore/memory-private.h"
53#include "MagickCore/semaphore.h"
54#include "MagickCore/signature-private.h"
55#include "MagickCore/string_.h"
56␌
57/*
58 Typedef declarations.
59*/
60struct _LinkedListInfo
61{
62 size_t
63 capacity,
64 elements;
65
66 ElementInfo
67 *head,
68 *tail,
69 *next;
70
71 SemaphoreInfo
72 *semaphore;
73
74 size_t
75 signature;
76};
77␌
78/*
79%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
80% %
81% %
82% %
83% A p p e n d V a l u e T o L i n k e d L i s t %
84% %
85% %
86% %
87%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
88%
89% AppendValueToLinkedList() appends a value to the end of the linked-list.
90%
91% The format of the AppendValueToLinkedList method is:
92%
93% MagickBooleanType AppendValueToLinkedList(LinkedListInfo *list_info,
94% const void *value)
95%
96% A description of each parameter follows:
97%
98% o list_info: the linked-list info.
99%
100% o value: the value.
101%
102*/
103MagickExport MagickBooleanType AppendValueToLinkedList(
104 LinkedListInfo *list_info,const void *value)
105{
106 ElementInfo
107 *next;
108
109 assert(list_info != (LinkedListInfo *) NULL);
110 assert(list_info->signature == MagickCoreSignature);
111 if (list_info->elements == list_info->capacity)
112 return(MagickFalse);
113 next=(ElementInfo *) AcquireMagickMemory(sizeof(*next));
114 if (next == (ElementInfo *) NULL)
115 return(MagickFalse);
116 next->value=(void *) value;
117 next->next=(ElementInfo *) NULL;
118 LockSemaphoreInfo(list_info->semaphore);
119 if (list_info->next == (ElementInfo *) NULL)
120 list_info->next=next;
121 if (list_info->elements == 0)
122 list_info->head=next;
123 else
124 list_info->tail->next=next;
125 list_info->tail=next;
126 list_info->elements++;
127 UnlockSemaphoreInfo(list_info->semaphore);
128 return(MagickTrue);
129}
130␌
131/*
132%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
133% %
134% %
135% %
136% C l e a r L i n k e d L i s t %
137% %
138% %
139% %
140%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
141%
142% ClearLinkedList() clears all the elements from the linked-list.
143%
144% The format of the ClearLinkedList method is:
145%
146% void ClearLinkedList(LinkedListInfo *list_info,
147% void *(*relinquish_value)(void *))
148%
149% A description of each parameter follows:
150%
151% o list_info: the linked-list info.
152%
153% o relinquish_value: the value deallocation method; typically
154% RelinquishMagickMemory().
155%
156*/
157MagickExport void ClearLinkedList(LinkedListInfo *list_info,
158 void *(*relinquish_value)(void *))
159{
160 ElementInfo
161 *element;
162
163 ElementInfo
164 *next;
165
166 assert(list_info != (LinkedListInfo *) NULL);
167 assert(list_info->signature == MagickCoreSignature);
168 LockSemaphoreInfo(list_info->semaphore);
169 next=list_info->head;
170 while (next != (ElementInfo *) NULL)
171 {
172 if (relinquish_value != (void *(*)(void *)) NULL)
173 next->value=relinquish_value(next->value);
174 element=next;
175 next=next->next;
176 element=(ElementInfo *) RelinquishMagickMemory(element);
177 }
178 list_info->head=(ElementInfo *) NULL;
179 list_info->tail=(ElementInfo *) NULL;
180 list_info->next=(ElementInfo *) NULL;
181 list_info->elements=0;
182 UnlockSemaphoreInfo(list_info->semaphore);
183}
184
185/*
186%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
187% %
188% %
189% %
190% D e s t r o y L i n k e d L i s t %
191% %
192% %
193% %
194%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
195%
196% DestroyLinkedList() frees the linked-list and all associated resources.
197%
198% The format of the DestroyLinkedList method is:
199%
200% LinkedListInfo *DestroyLinkedList(LinkedListInfo *list_info,
201% void *(*relinquish_value)(void *))
202%
203% A description of each parameter follows:
204%
205% o list_info: the linked-list info.
206%
207% o relinquish_value: the value deallocation method; typically
208% RelinquishMagickMemory().
209%
210*/
211MagickExport LinkedListInfo *DestroyLinkedList(LinkedListInfo *list_info,
212 void *(*relinquish_value)(void *))
213{
214 ElementInfo
215 *entry;
216
217 ElementInfo
218 *next;
219
220 assert(list_info != (LinkedListInfo *) NULL);
221 assert(list_info->signature == MagickCoreSignature);
222 LockSemaphoreInfo(list_info->semaphore);
223 for (next=list_info->head; next != (ElementInfo *) NULL; )
224 {
225 if (relinquish_value != (void *(*)(void *)) NULL)
226 next->value=relinquish_value(next->value);
227 entry=next;
228 next=next->next;
229 entry=(ElementInfo *) RelinquishMagickMemory(entry);
230 }
231 list_info->signature=(~MagickCoreSignature);
232 UnlockSemaphoreInfo(list_info->semaphore);
233 RelinquishSemaphoreInfo(&list_info->semaphore);
234 list_info=(LinkedListInfo *) RelinquishMagickMemory(list_info);
235 return(list_info);
236}
237␌
238/*
239%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
240% %
241% %
242% %
243% G e t H e a d E l e m e n t I n L i n k e d L i s t %
244% %
245% %
246% %
247%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
248%
249% GetHeadElementInLinkedList() gets the head element in the linked-list.
250%
251% The format of the GetHeadElementInLinkedList method is:
252%
253% ElementInfo *GetHeadElementInLinkedList(LinkedListInfo *list_info)
254%
255% A description of each parameter follows:
256%
257% o list_info: the linked_list info.
258%
259*/
260MagickPrivate ElementInfo *GetHeadElementInLinkedList(
261 LinkedListInfo *list_info)
262{
263 assert(list_info != (LinkedListInfo *) NULL);
264 assert(list_info->signature == MagickCoreSignature);
265 return(list_info->head);
266}
267␌
268/*
269%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
270% %
271% %
272% %
273% G e t L a s t V a l u e I n L i n k e d L i s t %
274% %
275% %
276% %
277%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
278%
279% GetLastValueInLinkedList() gets the last value in the linked-list.
280%
281% The format of the GetLastValueInLinkedList method is:
282%
283% void *GetLastValueInLinkedList(LinkedListInfo *list_info)
284%
285% A description of each parameter follows:
286%
287% o list_info: the linked_list info.
288%
289*/
290MagickExport void *GetLastValueInLinkedList(LinkedListInfo *list_info)
291{
292 void
293 *value;
294
295 assert(list_info != (LinkedListInfo *) NULL);
296 assert(list_info->signature == MagickCoreSignature);
297 if (list_info->elements == 0)
298 return((void *) NULL);
299 LockSemaphoreInfo(list_info->semaphore);
300 value=list_info->tail->value;
301 UnlockSemaphoreInfo(list_info->semaphore);
302 return(value);
303}
304
305/*
306%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
307% %
308% %
309% %
310% G e t N e x t V a l u e I n L i n k e d L i s t %
311% %
312% %
313% %
314%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
315%
316% GetNextValueInLinkedList() gets the next value in the linked-list.
317%
318% The format of the GetNextValueInLinkedList method is:
319%
320% void *GetNextValueInLinkedList(LinkedListInfo *list_info)
321%
322% A description of each parameter follows:
323%
324% o list_info: the linked-list info.
325%
326*/
327MagickExport void *GetNextValueInLinkedList(LinkedListInfo *list_info)
328{
329 void
330 *value;
331
332 assert(list_info != (LinkedListInfo *) NULL);
333 assert(list_info->signature == MagickCoreSignature);
334 LockSemaphoreInfo(list_info->semaphore);
335 if (list_info->next == (ElementInfo *) NULL)
336 {
337 UnlockSemaphoreInfo(list_info->semaphore);
338 return((void *) NULL);
339 }
340 value=list_info->next->value;
341 list_info->next=list_info->next->next;
342 UnlockSemaphoreInfo(list_info->semaphore);
343 return(value);
344}
345␌
346/*
347%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
348% %
349% %
350% %
351% G e t N u m b e r O f E l e m e n t s I n L i n k e d L i s t %
352% %
353% %
354% %
355%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
356%
357% GetNumberOfElementsInLinkedList() returns the number of entries in the
358% linked-list.
359%
360% The format of the GetNumberOfElementsInLinkedList method is:
361%
362% size_t GetNumberOfElementsInLinkedList(
363% const LinkedListInfo *list_info)
364%
365% A description of each parameter follows:
366%
367% o list_info: the linked-list info.
368%
369*/
370MagickExport size_t GetNumberOfElementsInLinkedList(
371 const LinkedListInfo *list_info)
372{
373 assert(list_info != (LinkedListInfo *) NULL);
374 assert(list_info->signature == MagickCoreSignature);
375 return(list_info->elements);
376}
377
378/*
379%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
380% %
381% %
382% %
383% G e t V a l u e F r o m L i n k e d L i s t %
384% %
385% %
386% %
387%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
388%
389% GetValueFromLinkedList() gets a value from the linked-list at the specified
390% location.
391%
392% The format of the GetValueFromLinkedList method is:
393%
394% void *GetValueFromLinkedList(LinkedListInfo *list_info,
395% const size_t index)
396%
397% A description of each parameter follows:
398%
399% o list_info: the linked_list info.
400%
401% o index: the list index.
402%
403*/
404MagickExport void *GetValueFromLinkedList(LinkedListInfo *list_info,
405 const size_t index)
406{
407 ElementInfo
408 *next;
409
410 ssize_t
411 i;
412
413 void
414 *value;
415
416 assert(list_info != (LinkedListInfo *) NULL);
417 assert(list_info->signature == MagickCoreSignature);
418 if (index >= list_info->elements)
419 return((void *) NULL);
420 LockSemaphoreInfo(list_info->semaphore);
421 if (index == 0)
422 {
423 value=list_info->head->value;
424 UnlockSemaphoreInfo(list_info->semaphore);
425 return(value);
426 }
427 if (index == (list_info->elements-1))
428 {
429 value=list_info->tail->value;
430 UnlockSemaphoreInfo(list_info->semaphore);
431 return(value);
432 }
433 next=list_info->head;
434 for (i=0; i < (ssize_t) index; i++)
435 next=next->next;
436 value=next->value;
437 UnlockSemaphoreInfo(list_info->semaphore);
438 return(value);
439}
440
441/*
442%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
443% %
444% %
445% %
446% I n s e r t V a l u e I n L i n k e d L i s t %
447% %
448% %
449% %
450%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
451%
452% InsertValueInLinkedList() inserts an element in the linked-list at the
453% specified location.
454%
455% The format of the InsertValueInLinkedList method is:
456%
457% MagickBooleanType InsertValueInLinkedList(ListInfo *list_info,
458% const size_t index,const void *value)
459%
460% A description of each parameter follows:
461%
462% o list_info: the hashmap info.
463%
464% o index: the index.
465%
466% o value: the value.
467%
468*/
469MagickExport MagickBooleanType InsertValueInLinkedList(
470 LinkedListInfo *list_info,const size_t index,const void *value)
471{
472 ElementInfo
473 *next;
474
475 ssize_t
476 i;
477
478 assert(list_info != (LinkedListInfo *) NULL);
479 assert(list_info->signature == MagickCoreSignature);
480 if (value == (const void *) NULL)
481 return(MagickFalse);
482 if ((index > list_info->elements) ||
483 (list_info->elements == list_info->capacity))
484 return(MagickFalse);
485 next=(ElementInfo *) AcquireMagickMemory(sizeof(*next));
486 if (next == (ElementInfo *) NULL)
487 return(MagickFalse);
488 next->value=(void *) value;
489 next->next=(ElementInfo *) NULL;
490 LockSemaphoreInfo(list_info->semaphore);
491 if (list_info->elements == 0)
492 {
493 if (list_info->next == (ElementInfo *) NULL)
494 list_info->next=next;
495 list_info->head=next;
496 list_info->tail=next;
497 }
498 else
499 {
500 if (index == 0)
501 {
502 if (list_info->next == list_info->head)
503 list_info->next=next;
504 next->next=list_info->head;
505 list_info->head=next;
506 }
507 else
508 if (index == list_info->elements)
509 {
510 if (list_info->next == (ElementInfo *) NULL)
511 list_info->next=next;
512 list_info->tail->next=next;
513 list_info->tail=next;
514 }
515 else
516 {
517 ElementInfo
518 *element;
519
520 element=list_info->head;
521 next->next=element->next;
522 for (i=1; i < (ssize_t) index; i++)
523 {
524 element=element->next;
525 next->next=element->next;
526 }
527 next=next->next;
528 element->next=next;
529 if (list_info->next == next->next)
530 list_info->next=next;
531 }
532 }
533 list_info->elements++;
534 UnlockSemaphoreInfo(list_info->semaphore);
535 return(MagickTrue);
536}
537␌
538/*
539%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
540% %
541% %
542% %
543% I n s e r t V a l u e I n S o r t e d L i n k e d L i s t %
544% %
545% %
546% %
547%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
548%
549% InsertValueInSortedLinkedList() inserts a value in the sorted linked-list.
550%
551% The format of the InsertValueInSortedLinkedList method is:
552%
553% MagickBooleanType InsertValueInSortedLinkedList(ListInfo *list_info,
554% int (*compare)(const void *,const void *),void **replace,
555% const void *value)
556%
557% A description of each parameter follows:
558%
559% o list_info: the hashmap info.
560%
561% o index: the index.
562%
563% o compare: the compare method.
564%
565% o replace: return previous element here.
566%
567% o value: the value.
568%
569*/
570MagickExport MagickBooleanType InsertValueInSortedLinkedList(
571 LinkedListInfo *list_info,int (*compare)(const void *,const void *),
572 void **replace,const void *value)
573{
574 ElementInfo
575 *element;
576
577 ElementInfo
578 *next;
579
580 ssize_t
581 i;
582
583 assert(list_info != (LinkedListInfo *) NULL);
584 assert(list_info->signature == MagickCoreSignature);
585 if ((compare == (int (*)(const void *,const void *)) NULL) ||
586 (value == (const void *) NULL))
587 return(MagickFalse);
588 if (list_info->elements == list_info->capacity)
589 return(MagickFalse);
590 next=(ElementInfo *) AcquireMagickMemory(sizeof(*next));
591 if (next == (ElementInfo *) NULL)
592 return(MagickFalse);
593 next->value=(void *) value;
594 element=(ElementInfo *) NULL;
595 LockSemaphoreInfo(list_info->semaphore);
596 next->next=list_info->head;
597 while (next->next != (ElementInfo *) NULL)
598 {
599 i=(ssize_t) compare(value,next->next->value);
600 if ((i < 0) || ((replace != (void **) NULL) && (i == 0)))
601 {
602 if (i == 0)
603 {
604 *replace=next->next->value;
605 next->next=next->next->next;
606 if (element != (ElementInfo *) NULL)
607 element->next=(ElementInfo *) RelinquishMagickMemory(
608 element->next);
609 list_info->elements--;
610 }
611 if (element != (ElementInfo *) NULL)
612 element->next=next;
613 else
614 list_info->head=next;
615 break;
616 }
617 element=next->next;
618 next->next=next->next->next;
619 }
620 if (next->next == (ElementInfo *) NULL)
621 {
622 if (element != (ElementInfo *) NULL)
623 element->next=next;
624 else
625 list_info->head=next;
626 list_info->tail=next;
627 }
628 list_info->elements++;
629 UnlockSemaphoreInfo(list_info->semaphore);
630 return(MagickTrue);
631}
632
633/*
634%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
635% %
636% %
637% %
638% I s L i n k e d L i s t E m p t y %
639% %
640% %
641% %
642%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
643%
644% IsLinkedListEmpty() returns MagickTrue if the linked-list is empty.
645%
646% The format of the IsLinkedListEmpty method is:
647%
648% MagickBooleanType IsLinkedListEmpty(LinkedListInfo *list_info)
649%
650% A description of each parameter follows:
651%
652% o list_info: the linked-list info.
653%
654*/
655MagickExport MagickBooleanType IsLinkedListEmpty(
656 const LinkedListInfo *list_info)
657{
658 assert(list_info != (LinkedListInfo *) NULL);
659 assert(list_info->signature == MagickCoreSignature);
660 return(list_info->elements == 0 ? MagickTrue : MagickFalse);
661}
662␌
663/*
664%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
665% %
666% %
667% %
668% L i n k e d L i s t T o A r r a y %
669% %
670% %
671% %
672%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
673%
674% LinkedListToArray() converts the linked-list to an array.
675%
676% The format of the LinkedListToArray method is:
677%
678% MagickBooleanType LinkedListToArray(LinkedListInfo *list_info,
679% void **array)
680%
681% A description of each parameter follows:
682%
683% o list_info: the linked-list info.
684%
685% o array: the array.
686%
687*/
688MagickExport MagickBooleanType LinkedListToArray(LinkedListInfo *list_info,
689 void **array)
690{
691 ElementInfo
692 *next;
693
694 ssize_t
695 i;
696
697 assert(list_info != (LinkedListInfo *) NULL);
698 assert(list_info->signature == MagickCoreSignature);
699 if (array == (void **) NULL)
700 return(MagickFalse);
701 LockSemaphoreInfo(list_info->semaphore);
702 next=list_info->head;
703 for (i=0; next != (ElementInfo *) NULL; i++)
704 {
705 array[i]=next->value;
706 next=next->next;
707 }
708 UnlockSemaphoreInfo(list_info->semaphore);
709 return(MagickTrue);
710}
711␌
712/*
713%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
714% %
715% %
716% %
717% N e w L i n k e d L i s t I n f o %
718% %
719% %
720% %
721%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
722%
723% NewLinkedList() returns a pointer to a LinkedListInfo structure
724% initialized to default values.
725%
726% The format of the NewLinkedList method is:
727%
728% LinkedListInfo *NewLinkedList(const size_t capacity)
729%
730% A description of each parameter follows:
731%
732% o capacity: the maximum number of elements in the list.
733%
734*/
735MagickExport LinkedListInfo *NewLinkedList(const size_t capacity)
736{
737 LinkedListInfo
738 *list_info;
739
740 list_info=(LinkedListInfo *) AcquireCriticalMemory(sizeof(*list_info));
741 (void) memset(list_info,0,sizeof(*list_info));
742 list_info->capacity=capacity == 0 ? (size_t) (~0) : capacity;
743 list_info->elements=0;
744 list_info->head=(ElementInfo *) NULL;
745 list_info->tail=(ElementInfo *) NULL;
746 list_info->next=(ElementInfo *) NULL;
747 list_info->semaphore=AcquireSemaphoreInfo();
748 list_info->signature=MagickCoreSignature;
749 return(list_info);
750}
751␌
752/*
753%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
754% %
755% %
756% %
757% R e m o v e E l e m e n t B y V a l u e F r o m L i n k e d L i s t %
758% %
759% %
760% %
761%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
762%
763% RemoveElementByValueFromLinkedList() removes an element from the linked-list
764% by value.
765%
766% The format of the RemoveElementByValueFromLinkedList method is:
767%
768% void *RemoveElementByValueFromLinkedList(LinkedListInfo *list_info,
769% const void *value)
770%
771% A description of each parameter follows:
772%
773% o list_info: the list info.
774%
775% o value: the value.
776%
777*/
778MagickExport void *RemoveElementByValueFromLinkedList(LinkedListInfo *list_info,
779 const void *value)
780{
781 ElementInfo
782 *next;
783
784 assert(list_info != (LinkedListInfo *) NULL);
785 assert(list_info->signature == MagickCoreSignature);
786 if ((list_info->elements == 0) || (value == (const void *) NULL))
787 return((void *) NULL);
788 LockSemaphoreInfo(list_info->semaphore);
789 if (value == list_info->head->value)
790 {
791 if (list_info->next == list_info->head)
792 list_info->next=list_info->head->next;
793 next=list_info->head;
794 list_info->head=list_info->head->next;
795 next=(ElementInfo *) RelinquishMagickMemory(next);
796 }
797 else
798 {
799 ElementInfo
800 *element;
801
802 next=list_info->head;
803 while ((next->next != (ElementInfo *) NULL) &&
804 (next->next->value != value))
805 next=next->next;
806 if (next->next == (ElementInfo *) NULL)
807 {
808 UnlockSemaphoreInfo(list_info->semaphore);
809 return((void *) NULL);
810 }
811 element=next->next;
812 next->next=element->next;
813 if (element == list_info->tail)
814 list_info->tail=next;
815 if (list_info->next == element)
816 list_info->next=element->next;
817 element=(ElementInfo *) RelinquishMagickMemory(element);
818 }
819 list_info->elements--;
820 UnlockSemaphoreInfo(list_info->semaphore);
821 return((void *) value);
822}
823␌
824/*
825%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
826% %
827% %
828% %
829% R e m o v e E l e m e n t F r o m L i n k e d L i s t %
830% %
831% %
832% %
833%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
834%
835% RemoveElementFromLinkedList() removes an element from the linked-list at the
836% specified location.
837%
838% The format of the RemoveElementFromLinkedList method is:
839%
840% void *RemoveElementFromLinkedList(LinkedListInfo *list_info,
841% const size_t index)
842%
843% A description of each parameter follows:
844%
845% o list_info: the linked-list info.
846%
847% o index: the index.
848%
849*/
850MagickExport void *RemoveElementFromLinkedList(LinkedListInfo *list_info,
851 const size_t index)
852{
853 ElementInfo
854 *next;
855
856 ssize_t
857 i;
858
859 void
860 *value;
861
862 assert(list_info != (LinkedListInfo *) NULL);
863 assert(list_info->signature == MagickCoreSignature);
864 if (index >= list_info->elements)
865 return((void *) NULL);
866 LockSemaphoreInfo(list_info->semaphore);
867 if (index == 0)
868 {
869 if (list_info->next == list_info->head)
870 list_info->next=list_info->head->next;
871 value=list_info->head->value;
872 next=list_info->head;
873 list_info->head=list_info->head->next;
874 next=(ElementInfo *) RelinquishMagickMemory(next);
875 }
876 else
877 {
878 ElementInfo
879 *element;
880
881 next=list_info->head;
882 for (i=1; i < (ssize_t) index; i++)
883 next=next->next;
884 element=next->next;
885 next->next=element->next;
886 if (element == list_info->tail)
887 list_info->tail=next;
888 if (list_info->next == element)
889 list_info->next=element->next;
890 value=element->value;
891 element=(ElementInfo *) RelinquishMagickMemory(element);
892 }
893 list_info->elements--;
894 UnlockSemaphoreInfo(list_info->semaphore);
895 return(value);
896}
897
898/*
899%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
900% %
901% %
902% %
903% R e m o v e L a s t E l e m e n t F r o m L i n k e d L i s t %
904% %
905% %
906% %
907%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
908%
909% RemoveLastElementFromLinkedList() removes the last element from the
910% linked-list.
911%
912% The format of the RemoveLastElementFromLinkedList method is:
913%
914% void *RemoveLastElementFromLinkedList(LinkedListInfo *list_info)
915%
916% A description of each parameter follows:
917%
918% o list_info: the linked-list info.
919%
920*/
921MagickExport void *RemoveLastElementFromLinkedList(LinkedListInfo *list_info)
922{
923 void
924 *value;
925
926 assert(list_info != (LinkedListInfo *) NULL);
927 assert(list_info->signature == MagickCoreSignature);
928 if (list_info->elements == 0)
929 return((void *) NULL);
930 LockSemaphoreInfo(list_info->semaphore);
931 if (list_info->next == list_info->tail)
932 list_info->next=(ElementInfo *) NULL;
933 if (list_info->elements == 1UL)
934 {
935 value=list_info->head->value;
936 list_info->head=(ElementInfo *) NULL;
937 list_info->tail=(ElementInfo *) RelinquishMagickMemory(list_info->tail);
938 }
939 else
940 {
941 ElementInfo
942 *next;
943
944 value=list_info->tail->value;
945 next=list_info->head;
946 while (next->next != list_info->tail)
947 next=next->next;
948 list_info->tail=(ElementInfo *) RelinquishMagickMemory(list_info->tail);
949 list_info->tail=next;
950 next->next=(ElementInfo *) NULL;
951 }
952 list_info->elements--;
953 UnlockSemaphoreInfo(list_info->semaphore);
954 return(value);
955}
956␌
957/*
958%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
959% %
960% %
961% %
962% R e s e t L i n k e d L i s t I t e r a t o r %
963% %
964% %
965% %
966%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
967%
968% ResetLinkedListIterator() resets the lined-list iterator. Use it in
969% conjunction with GetNextValueInLinkedList() to iterate over all the values
970% in the linked-list.
971%
972% The format of the ResetLinkedListIterator method is:
973%
974% ResetLinkedListIterator(LinkedListInfo *list_info)
975%
976% A description of each parameter follows:
977%
978% o list_info: the linked-list info.
979%
980*/
981MagickExport void ResetLinkedListIterator(LinkedListInfo *list_info)
982{
983 assert(list_info != (LinkedListInfo *) NULL);
984 assert(list_info->signature == MagickCoreSignature);
985 LockSemaphoreInfo(list_info->semaphore);
986 list_info->next=list_info->head;
987 UnlockSemaphoreInfo(list_info->semaphore);
988}
989␌
990/*
991%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
992% %
993% %
994% %
995% S e t H e a d E l e m e n t I n L i n k e d L i s t %
996% %
997% %
998% %
999%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1000%
1001% SetHeadElementInLinkedList() sets the head element of the linked-list.
1002%
1003% The format of the SetHeadElementInLinkedList method is:
1004%
1005% SetHeadElementInLinkedList(LinkedListInfo *list_info,
1006% ElementInfo *element)
1007%
1008% A description of each parameter follows:
1009%
1010% o list_info: the linked-list info.
1011%
1012% o element: the element to set as the head.
1013%
1014*/
1015MagickPrivate void SetHeadElementInLinkedList(LinkedListInfo *list_info,
1016 ElementInfo *element)
1017{
1018 ElementInfo
1019 *prev;
1020
1021 assert(list_info != (LinkedListInfo *) NULL);
1022 assert(list_info->signature == MagickCoreSignature);
1023 assert(element != (ElementInfo *) NULL);
1024 if (element == list_info->head)
1025 return;
1026 prev=list_info->head;
1027 while (prev != (ElementInfo *) NULL)
1028 {
1029 if (prev->next == element)
1030 {
1031 prev->next=element->next;
1032 element->next=list_info->head;
1033 if (list_info->head == list_info->next)
1034 list_info->next=element;
1035 list_info->head=element;
1036 break;
1037 }
1038 prev=prev->next;
1039 }
1040}
_ElementInfo
Definition draw.c:133
_LinkedListInfo
Definition linked-list.c:61