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