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