MagickCore  7.0.7
Convert, Edit, Or Compose Bitmap Images
linked-list.c
Go to the documentation of this file.
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-2018 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://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"
48 #include "MagickCore/linked-list.h"
49 #include "MagickCore/locale_.h"
50 #include "MagickCore/memory_.h"
52 #include "MagickCore/semaphore.h"
54 #include "MagickCore/string_.h"
55 
56 /*
57  Typedef declarations.
58 */
59 typedef struct _ElementInfo
60 {
61  void
63 
64  struct _ElementInfo
65  *next;
66 } ElementInfo;
67 
69 {
70  size_t
71  capacity,
72  elements;
73 
75  *head,
76  *tail,
77  *next;
78 
81 
82  size_t
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 */
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 */
166  void *(*relinquish_value)(void *))
167 {
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 */
220  void *(*relinquish_value)(void *))
221 {
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 */
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 */
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 */
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 */
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 */
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  {
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 */
549  LinkedListInfo *list_info,int (*compare)(const void *,const void *),
550  void **replace,const void *value)
551 {
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)
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 */
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 */
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 */
714 {
716  *list_info;
717 
718  list_info=(LinkedListInfo *) AcquireCriticalMemory(sizeof(*list_info));
719  (void) ResetMagickMemory(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 */
757  const void *value)
758 {
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  {
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 */
829  const size_t index)
830 {
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  {
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 */
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  {
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 */
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 }
MagickExport void * GetValueFromLinkedList(LinkedListInfo *list_info, const size_t index)
Definition: linked-list.c:382
MagickExport void * RemoveElementFromLinkedList(LinkedListInfo *list_info, const size_t index)
Definition: linked-list.c:828
MagickExport void UnlockSemaphoreInfo(SemaphoreInfo *semaphore_info)
Definition: semaphore.c:450
MagickExport void ResetLinkedListIterator(LinkedListInfo *list_info)
Definition: linked-list.c:959
MagickExport LinkedListInfo * DestroyLinkedList(LinkedListInfo *list_info, void *(*relinquish_value)(void *))
Definition: linked-list.c:219
MagickExport MagickBooleanType InsertValueInSortedLinkedList(LinkedListInfo *list_info, int(*compare)(const void *, const void *), void **replace, const void *value)
Definition: linked-list.c:548
MagickExport SemaphoreInfo * AcquireSemaphoreInfo(void)
Definition: semaphore.c:192
MagickExport MagickBooleanType InsertValueInLinkedList(LinkedListInfo *list_info, const size_t index, const void *value)
Definition: linked-list.c:447
MagickExport MagickBooleanType IsLinkedListEmpty(const LinkedListInfo *list_info)
Definition: linked-list.c:633
MagickExport MagickBooleanType AppendValueToLinkedList(LinkedListInfo *list_info, const void *value)
Definition: linked-list.c:111
MagickExport void * RemoveElementByValueFromLinkedList(LinkedListInfo *list_info, const void *value)
Definition: linked-list.c:756
ElementInfo * tail
Definition: linked-list.c:75
MagickExport void * GetNextValueInLinkedList(LinkedListInfo *list_info)
Definition: linked-list.c:305
#define MagickCoreSignature
MagickExport void LockSemaphoreInfo(SemaphoreInfo *semaphore_info)
Definition: semaphore.c:293
void * value
Definition: linked-list.c:62
SemaphoreInfo * semaphore
Definition: linked-list.c:80
MagickBooleanType
Definition: magick-type.h:156
MagickExport void * RemoveLastElementFromLinkedList(LinkedListInfo *list_info)
Definition: linked-list.c:899
MagickExport void * ResetMagickMemory(void *memory, int byte, const size_t size)
Definition: memory.c:1164
struct _ElementInfo * next
Definition: linked-list.c:64
MagickExport MagickBooleanType static void * AcquireCriticalMemory(const size_t size)
MagickExport void * GetLastValueInLinkedList(LinkedListInfo *list_info)
Definition: linked-list.c:268
MagickExport MagickBooleanType LinkedListToArray(LinkedListInfo *list_info, void **array)
Definition: linked-list.c:666
MagickExport LinkedListInfo * NewLinkedList(const size_t capacity)
Definition: linked-list.c:713
size_t signature
Definition: linked-list.c:83
ElementInfo * next
Definition: linked-list.c:75
MagickExport void ClearLinkedList(LinkedListInfo *list_info, void *(*relinquish_value)(void *))
Definition: linked-list.c:165
MagickExport void * AcquireMagickMemory(const size_t size)
Definition: memory.c:458
MagickExport size_t GetNumberOfElementsInLinkedList(const LinkedListInfo *list_info)
Definition: linked-list.c:348
ElementInfo * head
Definition: linked-list.c:75
struct _ElementInfo ElementInfo
MagickExport void * RelinquishMagickMemory(void *memory)
Definition: memory.c:1038
#define MagickExport
MagickExport void RelinquishSemaphoreInfo(SemaphoreInfo **semaphore_info)
Definition: semaphore.c:351