MagickCore  7.1.1-43
Convert, Edit, Or Compose Bitmap Images
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 */
61 {
62  size_t
63  capacity,
64  elements;
65 
67  *head,
68  *tail,
69  *next;
70 
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 */
103 MagickExport MagickBooleanType AppendValueToLinkedList(
104  LinkedListInfo *list_info,const void *value)
105 {
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 */
157 MagickExport void ClearLinkedList(LinkedListInfo *list_info,
158  void *(*relinquish_value)(void *))
159 {
161  *element;
162 
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 */
211 MagickExport LinkedListInfo *DestroyLinkedList(LinkedListInfo *list_info,
212  void *(*relinquish_value)(void *))
213 {
215  *entry;
216 
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 */
260 MagickPrivate 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 */
290 MagickExport 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 */
327 MagickExport 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 */
370 MagickExport 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 */
404 MagickExport void *GetValueFromLinkedList(LinkedListInfo *list_info,
405  const size_t index)
406 {
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 */
469 MagickExport MagickBooleanType InsertValueInLinkedList(
470  LinkedListInfo *list_info,const size_t index,const void *value)
471 {
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  {
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 */
570 MagickExport MagickBooleanType InsertValueInSortedLinkedList(
571  LinkedListInfo *list_info,int (*compare)(const void *,const void *),
572  void **replace,const void *value)
573 {
575  *element;
576 
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 */
655 MagickExport 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 */
688 MagickExport MagickBooleanType LinkedListToArray(LinkedListInfo *list_info,
689  void **array)
690 {
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 */
735 MagickExport LinkedListInfo *NewLinkedList(const size_t capacity)
736 {
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 */
778 MagickExport void *RemoveElementByValueFromLinkedList(LinkedListInfo *list_info,
779  const void *value)
780 {
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  {
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 */
850 MagickExport void *RemoveElementFromLinkedList(LinkedListInfo *list_info,
851  const size_t index)
852 {
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  {
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 */
921 MagickExport 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  {
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 */
981 MagickExport 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 */
1015 MagickPrivate 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 }
SemaphoreInfo
Definition: semaphore.c:60
_LinkedListInfo
Definition: linked-list.c:60
_ElementInfo
Definition: draw.c:132