MagickCore  6.9.13-12
Convert, Edit, Or Compose Bitmap Images
hashmap.c
1 /*
2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3 % %
4 % %
5 % %
6 % H H AAA SSSSS H H M M AAA PPPP %
7 % H H A A SS H H MM MM A A P P %
8 % HHHHH AAAAA SSS HHHHH M M M AAAAA PPPP %
9 % H H A A SS H H M M A A P %
10 % H H A A SSSSS H H M M A A P %
11 % %
12 % %
13 % MagickCore Hash-map and 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 "magick/studio.h"
46 #include "magick/exception.h"
47 #include "magick/exception-private.h"
48 #include "magick/hashmap.h"
49 #include "magick/hashmap-private.h"
50 #include "magick/locale_.h"
51 #include "magick/memory_.h"
52 #include "magick/semaphore.h"
53 #include "magick/signature-private.h"
54 #include "magick/string_.h"
55 ␌
56 /*
57  Typedef declarations.
58 */
59 typedef struct _EntryInfo
60 {
61  size_t
62  hash;
63 
64  void
65  *key,
66  *value;
67 } EntryInfo;
68 
70 {
71  size_t
72  capacity,
73  elements;
74 
76  *head,
77  *tail,
78  *next;
79 
81  *semaphore;
82 
83  size_t
84  signature;
85 };
86 
88 {
89  size_t
90  (*hash)(const void *);
91 
92  MagickBooleanType
93  (*compare)(const void *,const void *);
94 
95  void
96  *(*relinquish_key)(void *),
97  *(*relinquish_value)(void *);
98 
99  size_t
100  capacity,
101  entries,
102  next;
103 
104  MagickBooleanType
105  head_of_list;
106 
108  **map;
109 
111  *semaphore;
112 
113  size_t
114  signature;
115 };
116 ␌
117 /*
118 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
119 % %
120 % %
121 % %
122 % A p p e n d V a l u e T o L i n k e d L i s t %
123 % %
124 % %
125 % %
126 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
127 %
128 % AppendValueToLinkedList() appends a value to the end of the linked-list.
129 %
130 % The format of the AppendValueToLinkedList method is:
131 %
132 % MagickBooleanType AppendValueToLinkedList(LinkedListInfo *list_info,
133 % const void *value)
134 %
135 % A description of each parameter follows:
136 %
137 % o list_info: the linked-list info.
138 %
139 % o value: the value.
140 %
141 */
142 MagickExport MagickBooleanType AppendValueToLinkedList(
143  LinkedListInfo *list_info,const void *value)
144 {
146  *next;
147 
148  assert(list_info != (LinkedListInfo *) NULL);
149  assert(list_info->signature == MagickCoreSignature);
150  if (list_info->elements == list_info->capacity)
151  return(MagickFalse);
152  next=(ElementInfo *) AcquireMagickMemory(sizeof(*next));
153  if (next == (ElementInfo *) NULL)
154  return(MagickFalse);
155  next->value=(void *) value;
156  next->next=(ElementInfo *) NULL;
157  LockSemaphoreInfo(list_info->semaphore);
158  if (list_info->next == (ElementInfo *) NULL)
159  list_info->next=next;
160  if (list_info->elements == 0)
161  list_info->head=next;
162  else
163  list_info->tail->next=next;
164  list_info->tail=next;
165  list_info->elements++;
166  UnlockSemaphoreInfo(list_info->semaphore);
167  return(MagickTrue);
168 }
169 ␌
170 /*
171 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
172 % %
173 % %
174 % %
175 % C l e a r L i n k e d L i s t %
176 % %
177 % %
178 % %
179 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
180 %
181 % ClearLinkedList() clears all the elements from the linked-list.
182 %
183 % The format of the ClearLinkedList method is:
184 %
185 % void ClearLinkedList(LinkedListInfo *list_info,
186 % void *(*relinquish_value)(void *))
187 %
188 % A description of each parameter follows:
189 %
190 % o list_info: the linked-list info.
191 %
192 % o relinquish_value: the value deallocation method; typically
193 % RelinquishMagickMemory().
194 %
195 */
196 MagickExport void ClearLinkedList(LinkedListInfo *list_info,
197  void *(*relinquish_value)(void *))
198 {
200  *element;
201 
203  *next;
204 
205  assert(list_info != (LinkedListInfo *) NULL);
206  assert(list_info->signature == MagickCoreSignature);
207  LockSemaphoreInfo(list_info->semaphore);
208  next=list_info->head;
209  while (next != (ElementInfo *) NULL)
210  {
211  if (relinquish_value != (void *(*)(void *)) NULL)
212  next->value=relinquish_value(next->value);
213  element=next;
214  next=next->next;
215  element=(ElementInfo *) RelinquishMagickMemory(element);
216  }
217  list_info->head=(ElementInfo *) NULL;
218  list_info->tail=(ElementInfo *) NULL;
219  list_info->next=(ElementInfo *) NULL;
220  list_info->elements=0;
221  UnlockSemaphoreInfo(list_info->semaphore);
222 }
223 ␌
224 /*
225 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
226 % %
227 % %
228 % %
229 % C o m p a r e H a s h m a p S t r i n g %
230 % %
231 % %
232 % %
233 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
234 %
235 % CompareHashmapString() finds an entry in a hash-map based on the contents
236 % of a string.
237 %
238 % The format of the CompareHashmapString method is:
239 %
240 % MagickBooleanType CompareHashmapString(const void *target,
241 % const void *source)
242 %
243 % A description of each parameter follows:
244 %
245 % o target: the target string.
246 %
247 % o source: the source string.
248 %
249 */
250 MagickExport MagickBooleanType CompareHashmapString(const void *target,
251  const void *source)
252 {
253  const char
254  *p,
255  *q;
256 
257  p=(const char *) target;
258  q=(const char *) source;
259  return(LocaleCompare(p,q) == 0 ? MagickTrue : MagickFalse);
260 }
261 ␌
262 /*
263 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
264 % %
265 % %
266 % %
267 % C o m p a r e H a s h m a p S t r i n g I n f o %
268 % %
269 % %
270 % %
271 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
272 %
273 % CompareHashmapStringInfo() finds an entry in a hash-map based on the
274 % contents of a string.
275 %
276 % The format of the CompareHashmapStringInfo method is:
277 %
278 % MagickBooleanType CompareHashmapStringInfo(const void *target,
279 % const void *source)
280 %
281 % A description of each parameter follows:
282 %
283 % o target: the target string.
284 %
285 % o source: the source string.
286 %
287 */
288 MagickExport MagickBooleanType CompareHashmapStringInfo(const void *target,
289  const void *source)
290 {
291  const StringInfo
292  *p,
293  *q;
294 
295  p=(const StringInfo *) target;
296  q=(const StringInfo *) source;
297  return(CompareStringInfo(p,q) == 0 ? MagickTrue : MagickFalse);
298 }
299 ␌
300 /*
301 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
302 % %
303 % %
304 % %
305 % D e s t r o y H a s h m a p %
306 % %
307 % %
308 % %
309 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
310 %
311 % DestroyHashmap() frees the hash-map and all associated resources.
312 %
313 % The format of the DestroyHashmap method is:
314 %
315 % HashmapInfo *DestroyHashmap(HashmapInfo *hashmap_info)
316 %
317 % A description of each parameter follows:
318 %
319 % o hashmap_info: the hashmap info.
320 %
321 */
322 MagickExport HashmapInfo *DestroyHashmap(HashmapInfo *hashmap_info)
323 {
325  *list_info;
326 
327  EntryInfo
328  *entry;
329 
330  ssize_t
331  i;
332 
333  assert(hashmap_info != (HashmapInfo *) NULL);
334  assert(hashmap_info->signature == MagickCoreSignature);
335  LockSemaphoreInfo(hashmap_info->semaphore);
336  for (i=0; i < (ssize_t) hashmap_info->capacity; i++)
337  {
338  list_info=hashmap_info->map[i];
339  if (list_info != (LinkedListInfo *) NULL)
340  {
341  list_info->next=list_info->head;
342  entry=(EntryInfo *) GetNextValueInLinkedList(list_info);
343  while (entry != (EntryInfo *) NULL)
344  {
345  if (hashmap_info->relinquish_key != (void *(*)(void *)) NULL)
346  entry->key=hashmap_info->relinquish_key(entry->key);
347  if (hashmap_info->relinquish_value != (void *(*)(void *)) NULL)
348  entry->value=hashmap_info->relinquish_value(entry->value);
349  entry=(EntryInfo *) GetNextValueInLinkedList(list_info);
350  }
351  }
352  if (list_info != (LinkedListInfo *) NULL)
353  list_info=DestroyLinkedList(list_info,RelinquishMagickMemory);
354  }
355  hashmap_info->map=(LinkedListInfo **) RelinquishMagickMemory(
356  hashmap_info->map);
357  hashmap_info->signature=(~MagickCoreSignature);
358  UnlockSemaphoreInfo(hashmap_info->semaphore);
359  DestroySemaphoreInfo(&hashmap_info->semaphore);
360  hashmap_info=(HashmapInfo *) RelinquishMagickMemory(hashmap_info);
361  return(hashmap_info);
362 }
363 ␌
364 /*
365 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
366 % %
367 % %
368 % %
369 % D e s t r o y L i n k e d L i s t %
370 % %
371 % %
372 % %
373 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
374 %
375 % DestroyLinkedList() frees the linked-list and all associated resources.
376 %
377 % The format of the DestroyLinkedList method is:
378 %
379 % LinkedListInfo *DestroyLinkedList(LinkedListInfo *list_info,
380 % void *(*relinquish_value)(void *))
381 %
382 % A description of each parameter follows:
383 %
384 % o list_info: the linked-list info.
385 %
386 % o relinquish_value: the value deallocation method; typically
387 % RelinquishMagickMemory().
388 %
389 */
390 MagickExport LinkedListInfo *DestroyLinkedList(LinkedListInfo *list_info,
391  void *(*relinquish_value)(void *))
392 {
394  *entry;
395 
397  *next;
398 
399  assert(list_info != (LinkedListInfo *) NULL);
400  assert(list_info->signature == MagickCoreSignature);
401  LockSemaphoreInfo(list_info->semaphore);
402  for (next=list_info->head; next != (ElementInfo *) NULL; )
403  {
404  if (relinquish_value != (void *(*)(void *)) NULL)
405  next->value=relinquish_value(next->value);
406  entry=next;
407  next=next->next;
408  entry=(ElementInfo *) RelinquishMagickMemory(entry);
409  }
410  list_info->signature=(~MagickCoreSignature);
411  UnlockSemaphoreInfo(list_info->semaphore);
412  DestroySemaphoreInfo(&list_info->semaphore);
413  list_info=(LinkedListInfo *) RelinquishMagickMemory(list_info);
414  return(list_info);
415 }
416 ␌
417 /*
418 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
419 % %
420 % %
421 % %
422 % 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 %
423 % %
424 % %
425 % %
426 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
427 %
428 % GetHeadElementInLinkedList() gets the head element in the linked-list.
429 %
430 % The format of the GetHeadElementInLinkedList method is:
431 %
432 % ElementInfo *GetHeadElementInLinkedList(LinkedListInfo *list_info)
433 %
434 % A description of each parameter follows:
435 %
436 % o list_info: the linked_list info.
437 %
438 */
439 MagickPrivate ElementInfo *GetHeadElementInLinkedList(
440  LinkedListInfo *list_info)
441 {
442  assert(list_info != (LinkedListInfo *) NULL);
443  assert(list_info->signature == MagickCoreSignature);
444  return(list_info->head);
445 }
446 ␌
447 /*
448 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
449 % %
450 % %
451 % %
452 % G e t L a s t V a l u e I n L i n k e d L i s t %
453 % %
454 % %
455 % %
456 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
457 %
458 % GetLastValueInLinkedList() gets the last value in the linked-list.
459 %
460 % The format of the GetLastValueInLinkedList method is:
461 %
462 % void *GetLastValueInLinkedList(LinkedListInfo *list_info)
463 %
464 % A description of each parameter follows:
465 %
466 % o list_info: the linked_list info.
467 %
468 */
469 MagickExport void *GetLastValueInLinkedList(LinkedListInfo *list_info)
470 {
471  void
472  *value;
473 
474  assert(list_info != (LinkedListInfo *) NULL);
475  assert(list_info->signature == MagickCoreSignature);
476  if (list_info->elements == 0)
477  return((void *) NULL);
478  LockSemaphoreInfo(list_info->semaphore);
479  value=list_info->tail->value;
480  UnlockSemaphoreInfo(list_info->semaphore);
481  return(value);
482 }
483 ␌
484 /*
485 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
486 % %
487 % %
488 % %
489 % G e t N e x t K e y I n H a s h m a p %
490 % %
491 % %
492 % %
493 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
494 %
495 % GetNextKeyInHashmap() gets the next key in the hash-map.
496 %
497 % The format of the GetNextKeyInHashmap method is:
498 %
499 % void *GetNextKeyInHashmap(HashmapInfo *hashmap_info)
500 %
501 % A description of each parameter follows:
502 %
503 % o hashmap_info: the hashmap info.
504 %
505 */
506 MagickExport void *GetNextKeyInHashmap(HashmapInfo *hashmap_info)
507 {
509  *list_info;
510 
511  EntryInfo
512  *entry;
513 
514  void
515  *key;
516 
517  assert(hashmap_info != (HashmapInfo *) NULL);
518  assert(hashmap_info->signature == MagickCoreSignature);
519  LockSemaphoreInfo(hashmap_info->semaphore);
520  while (hashmap_info->next < hashmap_info->capacity)
521  {
522  list_info=hashmap_info->map[hashmap_info->next];
523  if (list_info != (LinkedListInfo *) NULL)
524  {
525  if (hashmap_info->head_of_list == MagickFalse)
526  {
527  list_info->next=list_info->head;
528  hashmap_info->head_of_list=MagickTrue;
529  }
530  entry=(EntryInfo *) GetNextValueInLinkedList(list_info);
531  if (entry != (EntryInfo *) NULL)
532  {
533  key=entry->key;
534  UnlockSemaphoreInfo(hashmap_info->semaphore);
535  return(key);
536  }
537  hashmap_info->head_of_list=MagickFalse;
538  }
539  hashmap_info->next++;
540  }
541  UnlockSemaphoreInfo(hashmap_info->semaphore);
542  return((void *) NULL);
543 }
544 ␌
545 /*
546 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
547 % %
548 % %
549 % %
550 % G e t N e x t V a l u e I n H a s h m a p %
551 % %
552 % %
553 % %
554 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
555 %
556 % GetNextValueInHashmap() gets the next value in the hash-map.
557 %
558 % The format of the GetNextValueInHashmap method is:
559 %
560 % void *GetNextValueInHashmap(HashmapInfo *hashmap_info)
561 %
562 % A description of each parameter follows:
563 %
564 % o hashmap_info: the hashmap info.
565 %
566 */
567 MagickExport void *GetNextValueInHashmap(HashmapInfo *hashmap_info)
568 {
570  *list_info;
571 
572  EntryInfo
573  *entry;
574 
575  void
576  *value;
577 
578  assert(hashmap_info != (HashmapInfo *) NULL);
579  assert(hashmap_info->signature == MagickCoreSignature);
580  LockSemaphoreInfo(hashmap_info->semaphore);
581  while (hashmap_info->next < hashmap_info->capacity)
582  {
583  list_info=hashmap_info->map[hashmap_info->next];
584  if (list_info != (LinkedListInfo *) NULL)
585  {
586  if (hashmap_info->head_of_list == MagickFalse)
587  {
588  list_info->next=list_info->head;
589  hashmap_info->head_of_list=MagickTrue;
590  }
591  entry=(EntryInfo *) GetNextValueInLinkedList(list_info);
592  if (entry != (EntryInfo *) NULL)
593  {
594  value=entry->value;
595  UnlockSemaphoreInfo(hashmap_info->semaphore);
596  return(value);
597  }
598  hashmap_info->head_of_list=MagickFalse;
599  }
600  hashmap_info->next++;
601  }
602  UnlockSemaphoreInfo(hashmap_info->semaphore);
603  return((void *) NULL);
604 }
605 ␌
606 /*
607 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
608 % %
609 % %
610 % %
611 % G e t N e x t V a l u e I n L i n k e d L i s t %
612 % %
613 % %
614 % %
615 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
616 %
617 % GetNextValueInLinkedList() gets the next value in the linked-list.
618 %
619 % The format of the GetNextValueInLinkedList method is:
620 %
621 % void *GetNextValueInLinkedList(LinkedListInfo *list_info)
622 %
623 % A description of each parameter follows:
624 %
625 % o list_info: the linked-list info.
626 %
627 */
628 MagickExport void *GetNextValueInLinkedList(LinkedListInfo *list_info)
629 {
630  void
631  *value;
632 
633  assert(list_info != (LinkedListInfo *) NULL);
634  assert(list_info->signature == MagickCoreSignature);
635  LockSemaphoreInfo(list_info->semaphore);
636  if (list_info->next == (ElementInfo *) NULL)
637  {
638  UnlockSemaphoreInfo(list_info->semaphore);
639  return((void *) NULL);
640  }
641  value=list_info->next->value;
642  list_info->next=list_info->next->next;
643  UnlockSemaphoreInfo(list_info->semaphore);
644  return(value);
645 }
646 ␌
647 /*
648 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
649 % %
650 % %
651 % %
652 % G e t N u m b e r O f E n t r i e s I n H a s h m a p %
653 % %
654 % %
655 % %
656 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
657 %
658 % GetNumberOfEntriesInHashmap() returns the number of entries in the hash-map.
659 %
660 % The format of the GetNumberOfEntriesInHashmap method is:
661 %
662 % size_t GetNumberOfEntriesInHashmap(const HashmapInfo *hashmap_info)
663 %
664 % A description of each parameter follows:
665 %
666 % o hashmap_info: the hashmap info.
667 %
668 */
669 MagickExport size_t GetNumberOfEntriesInHashmap(
670  const HashmapInfo *hashmap_info)
671 {
672  assert(hashmap_info != (HashmapInfo *) NULL);
673  assert(hashmap_info->signature == MagickCoreSignature);
674  return(hashmap_info->entries);
675 }
676 ␌
677 /*
678 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
679 % %
680 % %
681 % %
682 % 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 %
683 % %
684 % %
685 % %
686 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
687 %
688 % GetNumberOfElementsInLinkedList() returns the number of entries in the
689 % linked-list.
690 %
691 % The format of the GetNumberOfElementsInLinkedList method is:
692 %
693 % size_t GetNumberOfElementsInLinkedList(
694 % const LinkedListInfo *list_info)
695 %
696 % A description of each parameter follows:
697 %
698 % o list_info: the linked-list info.
699 %
700 */
701 MagickExport size_t GetNumberOfElementsInLinkedList(
702  const LinkedListInfo *list_info)
703 {
704  assert(list_info != (LinkedListInfo *) NULL);
705  assert(list_info->signature == MagickCoreSignature);
706  return(list_info->elements);
707 }
708 ␌
709 /*
710 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
711 % %
712 % %
713 % %
714 % G e t V a l u e F r o m H a s h m a p %
715 % %
716 % %
717 % %
718 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
719 %
720 % GetValueFromHashmap() gets an entry from the hash-map by its key.
721 %
722 % The format of the GetValueFromHashmap method is:
723 %
724 % void *GetValueFromHashmap(HashmapInfo *hashmap_info,const void *key)
725 %
726 % A description of each parameter follows:
727 %
728 % o hashmap_info: the hashmap info.
729 %
730 % o key: the key.
731 %
732 */
733 MagickExport void *GetValueFromHashmap(HashmapInfo *hashmap_info,
734  const void *key)
735 {
737  *list_info;
738 
739  EntryInfo
740  *entry;
741 
742  size_t
743  hash;
744 
745  void
746  *value;
747 
748  assert(hashmap_info != (HashmapInfo *) NULL);
749  assert(hashmap_info->signature == MagickCoreSignature);
750  if (key == (const void *) NULL)
751  return((void *) NULL);
752  LockSemaphoreInfo(hashmap_info->semaphore);
753  hash=hashmap_info->hash(key);
754  list_info=hashmap_info->map[hash % hashmap_info->capacity];
755  if (list_info != (LinkedListInfo *) NULL)
756  {
757  list_info->next=list_info->head;
758  entry=(EntryInfo *) GetNextValueInLinkedList(list_info);
759  while (entry != (EntryInfo *) NULL)
760  {
761  if (entry->hash == hash)
762  {
763  MagickBooleanType
764  compare;
765 
766  compare=MagickTrue;
767  if (hashmap_info->compare !=
768  (MagickBooleanType (*)(const void *,const void *)) NULL)
769  compare=hashmap_info->compare(key,entry->key);
770  if (compare != MagickFalse)
771  {
772  value=entry->value;
773  UnlockSemaphoreInfo(hashmap_info->semaphore);
774  return(value);
775  }
776  }
777  entry=(EntryInfo *) GetNextValueInLinkedList(list_info);
778  }
779  }
780  UnlockSemaphoreInfo(hashmap_info->semaphore);
781  return((void *) NULL);
782 }
783 ␌
784 /*
785 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
786 % %
787 % %
788 % %
789 % G e t V a l u e F r o m L i n k e d L i s t %
790 % %
791 % %
792 % %
793 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
794 %
795 % GetValueFromLinkedList() gets a value from the linked-list at the specified
796 % location.
797 %
798 % The format of the GetValueFromLinkedList method is:
799 %
800 % void *GetValueFromLinkedList(LinkedListInfo *list_info,
801 % const size_t index)
802 %
803 % A description of each parameter follows:
804 %
805 % o list_info: the linked_list info.
806 %
807 % o index: the list index.
808 %
809 */
810 MagickExport void *GetValueFromLinkedList(LinkedListInfo *list_info,
811  const size_t index)
812 {
814  *next;
815 
816  ssize_t
817  i;
818 
819  void
820  *value;
821 
822  assert(list_info != (LinkedListInfo *) NULL);
823  assert(list_info->signature == MagickCoreSignature);
824  if (index >= list_info->elements)
825  return((void *) NULL);
826  LockSemaphoreInfo(list_info->semaphore);
827  if (index == 0)
828  {
829  value=list_info->head->value;
830  UnlockSemaphoreInfo(list_info->semaphore);
831  return(value);
832  }
833  if (index == (list_info->elements-1))
834  {
835  value=list_info->tail->value;
836  UnlockSemaphoreInfo(list_info->semaphore);
837  return(value);
838  }
839  next=list_info->head;
840  for (i=0; i < (ssize_t) index; i++)
841  next=next->next;
842  value=next->value;
843  UnlockSemaphoreInfo(list_info->semaphore);
844  return(value);
845 }
846 ␌
847 /*
848 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
849 % %
850 % %
851 % %
852 % H a s h P o i n t e r T y p e %
853 % %
854 % %
855 % %
856 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
857 %
858 % HashPointerType() finds an entry in a hash-map based on the address of a
859 % pointer.
860 %
861 % The format of the HashPointerType method is:
862 %
863 % size_t HashPointerType(const void *pointer)
864 %
865 % A description of each parameter follows:
866 %
867 % o pointer: compute the hash entry location from this pointer address.
868 %
869 */
870 MagickExport size_t HashPointerType(const void *pointer)
871 {
872  size_t
873  hash;
874 
875  hash=(size_t) pointer;
876  hash+=(~(hash << 9));
877  hash^=(hash >> 14);
878  hash+=(hash << 4);
879  hash^=(hash >> 10);
880  return(hash);
881 }
882 ␌
883 /*
884 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
885 % %
886 % %
887 % %
888 % H a s h S t r i n g T y p e %
889 % %
890 % %
891 % %
892 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
893 %
894 % HashStringType() finds an entry in a hash-map based on the contents of a
895 % string.
896 %
897 % The format of the HashStringType method is:
898 %
899 % size_t HashStringType(const void *string)
900 %
901 % A description of each parameter follows:
902 %
903 % o string: compute the hash entry location from this string.
904 %
905 */
906 MagickExport size_t HashStringType(const void *string)
907 {
908  const unsigned char
909  *digest;
910 
911  ssize_t
912  i;
913 
915  *signature_info;
916 
917  size_t
918  hash;
919 
920  StringInfo
921  *signature;
922 
923  signature_info=AcquireSignatureInfo();
924  signature=StringToStringInfo((const char *) string);
925  UpdateSignature(signature_info,signature);
926  FinalizeSignature(signature_info);
927  digest=GetStringInfoDatum(GetSignatureDigest(signature_info));
928  hash=0;
929  for (i=0; i < 8; i++)
930  hash^=digest[i];
931  signature=DestroyStringInfo(signature);
932  signature_info=DestroySignatureInfo(signature_info);
933  return(hash);
934 }
935 ␌
936 /*
937 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
938 % %
939 % %
940 % %
941 % H a s h S t r i n g I n f o T y p e %
942 % %
943 % %
944 % %
945 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
946 %
947 % Specify the HashStringInfoType() method in NewHashmap() to find an entry
948 % in a hash-map based on the contents of a string.
949 %
950 % The format of the HashStringInfoType method is:
951 %
952 % size_t HashStringInfoType(const void *string_info)
953 %
954 % A description of each parameter follows:
955 %
956 % o string_info: compute the hash entry location from this string.
957 %
958 */
959 MagickExport size_t HashStringInfoType(const void *string_info)
960 {
961  const unsigned char
962  *digest;
963 
964  ssize_t
965  i;
966 
968  *signature_info;
969 
970  size_t
971  hash;
972 
973  signature_info=AcquireSignatureInfo();
974  UpdateSignature(signature_info,(const StringInfo *) string_info);
975  FinalizeSignature(signature_info);
976  digest=GetStringInfoDatum(GetSignatureDigest(signature_info));
977  hash=0;
978  for (i=0; i < 8; i++)
979  hash^=digest[i];
980  signature_info=DestroySignatureInfo(signature_info);
981  return(hash);
982 }
983 ␌
984 /*
985 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
986 % %
987 % %
988 % %
989 % I n s e r t V a l u e I n L i n k e d L i s t %
990 % %
991 % %
992 % %
993 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
994 %
995 % InsertValueInLinkedList() inserts an element in the linked-list at the
996 % specified location.
997 %
998 % The format of the InsertValueInLinkedList method is:
999 %
1000 % MagickBooleanType InsertValueInLinkedList(ListInfo *list_info,
1001 % const size_t index,const void *value)
1002 %
1003 % A description of each parameter follows:
1004 %
1005 % o list_info: the hashmap info.
1006 %
1007 % o index: the index.
1008 %
1009 % o value: the value.
1010 %
1011 */
1012 MagickExport MagickBooleanType InsertValueInLinkedList(
1013  LinkedListInfo *list_info,const size_t index,const void *value)
1014 {
1015  ElementInfo
1016  *next;
1017 
1018  ssize_t
1019  i;
1020 
1021  assert(list_info != (LinkedListInfo *) NULL);
1022  assert(list_info->signature == MagickCoreSignature);
1023  if (value == (const void *) NULL)
1024  return(MagickFalse);
1025  if ((index > list_info->elements) ||
1026  (list_info->elements == list_info->capacity))
1027  return(MagickFalse);
1028  next=(ElementInfo *) AcquireMagickMemory(sizeof(*next));
1029  if (next == (ElementInfo *) NULL)
1030  return(MagickFalse);
1031  next->value=(void *) value;
1032  next->next=(ElementInfo *) NULL;
1033  LockSemaphoreInfo(list_info->semaphore);
1034  if (list_info->elements == 0)
1035  {
1036  if (list_info->next == (ElementInfo *) NULL)
1037  list_info->next=next;
1038  list_info->head=next;
1039  list_info->tail=next;
1040  }
1041  else
1042  {
1043  if (index == 0)
1044  {
1045  if (list_info->next == list_info->head)
1046  list_info->next=next;
1047  next->next=list_info->head;
1048  list_info->head=next;
1049  }
1050  else
1051  if (index == list_info->elements)
1052  {
1053  if (list_info->next == (ElementInfo *) NULL)
1054  list_info->next=next;
1055  list_info->tail->next=next;
1056  list_info->tail=next;
1057  }
1058  else
1059  {
1060  ElementInfo
1061  *element;
1062 
1063  element=list_info->head;
1064  next->next=element->next;
1065  for (i=1; i < (ssize_t) index; i++)
1066  {
1067  element=element->next;
1068  next->next=element->next;
1069  }
1070  next=next->next;
1071  element->next=next;
1072  if (list_info->next == next->next)
1073  list_info->next=next;
1074  }
1075  }
1076  list_info->elements++;
1077  UnlockSemaphoreInfo(list_info->semaphore);
1078  return(MagickTrue);
1079 }
1080 ␌
1081 /*
1082 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1083 % %
1084 % %
1085 % %
1086 % 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 %
1087 % %
1088 % %
1089 % %
1090 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1091 %
1092 % InsertValueInSortedLinkedList() inserts a value in the sorted linked-list.
1093 %
1094 % The format of the InsertValueInSortedLinkedList method is:
1095 %
1096 % MagickBooleanType InsertValueInSortedLinkedList(ListInfo *list_info,
1097 % int (*compare)(const void *,const void *),void **replace,
1098 % const void *value)
1099 %
1100 % A description of each parameter follows:
1101 %
1102 % o list_info: the hashmap info.
1103 %
1104 % o index: the index.
1105 %
1106 % o compare: the compare method.
1107 %
1108 % o replace: return previous element here.
1109 %
1110 % o value: the value.
1111 %
1112 */
1113 MagickExport MagickBooleanType InsertValueInSortedLinkedList(
1114  LinkedListInfo *list_info,int (*compare)(const void *,const void *),
1115  void **replace,const void *value)
1116 {
1117  ElementInfo
1118  *element;
1119 
1120  ElementInfo
1121  *next;
1122 
1123  ssize_t
1124  i;
1125 
1126  assert(list_info != (LinkedListInfo *) NULL);
1127  assert(list_info->signature == MagickCoreSignature);
1128  if ((compare == (int (*)(const void *,const void *)) NULL) ||
1129  (value == (const void *) NULL))
1130  return(MagickFalse);
1131  if (list_info->elements == list_info->capacity)
1132  return(MagickFalse);
1133  next=(ElementInfo *) AcquireMagickMemory(sizeof(*next));
1134  if (next == (ElementInfo *) NULL)
1135  return(MagickFalse);
1136  next->value=(void *) value;
1137  element=(ElementInfo *) NULL;
1138  LockSemaphoreInfo(list_info->semaphore);
1139  next->next=list_info->head;
1140  while (next->next != (ElementInfo *) NULL)
1141  {
1142  i=(ssize_t) compare(value,next->next->value);
1143  if ((i < 0) || ((replace != (void **) NULL) && (i == 0)))
1144  {
1145  if (i == 0)
1146  {
1147  *replace=next->next->value;
1148  next->next=next->next->next;
1149  if (element != (ElementInfo *) NULL)
1150  element->next=(ElementInfo *) RelinquishMagickMemory(
1151  element->next);
1152  list_info->elements--;
1153  }
1154  if (element != (ElementInfo *) NULL)
1155  element->next=next;
1156  else
1157  list_info->head=next;
1158  break;
1159  }
1160  element=next->next;
1161  next->next=next->next->next;
1162  }
1163  if (next->next == (ElementInfo *) NULL)
1164  {
1165  if (element != (ElementInfo *) NULL)
1166  element->next=next;
1167  else
1168  list_info->head=next;
1169  list_info->tail=next;
1170  }
1171  list_info->elements++;
1172  UnlockSemaphoreInfo(list_info->semaphore);
1173  return(MagickTrue);
1174 }
1175 ␌
1176 /*
1177 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1178 % %
1179 % %
1180 % %
1181 % I s H a s h m a p E m p t y %
1182 % %
1183 % %
1184 % %
1185 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1186 %
1187 % IsHashmapEmpty() returns MagickTrue if the hash-map is empty.
1188 %
1189 % The format of the IsHashmapEmpty method is:
1190 %
1191 % MagickBooleanType IsHashmapEmpty(const HashmapInfo *hashmap_info)
1192 %
1193 % A description of each parameter follows:
1194 %
1195 % o hashmap_info: the hashmap info.
1196 %
1197 */
1198 MagickExport MagickBooleanType IsHashmapEmpty(const HashmapInfo *hashmap_info)
1199 {
1200  assert(hashmap_info != (HashmapInfo *) NULL);
1201  assert(hashmap_info->signature == MagickCoreSignature);
1202  return(hashmap_info->entries == 0 ? MagickTrue : MagickFalse);
1203 }
1204 ␌
1205 /*
1206 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1207 % %
1208 % %
1209 % %
1210 % I s L i n k e d L i s t E m p t y %
1211 % %
1212 % %
1213 % %
1214 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1215 %
1216 % IsLinkedListEmpty() returns MagickTrue if the linked-list is empty.
1217 %
1218 % The format of the IsLinkedListEmpty method is:
1219 %
1220 % MagickBooleanType IsLinkedListEmpty(LinkedListInfo *list_info)
1221 %
1222 % A description of each parameter follows:
1223 %
1224 % o list_info: the linked-list info.
1225 %
1226 */
1227 MagickExport MagickBooleanType IsLinkedListEmpty(
1228  const LinkedListInfo *list_info)
1229 {
1230  assert(list_info != (LinkedListInfo *) NULL);
1231  assert(list_info->signature == MagickCoreSignature);
1232  return(list_info->elements == 0 ? MagickTrue : MagickFalse);
1233 }
1234 ␌
1235 /*
1236 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1237 % %
1238 % %
1239 % %
1240 % L i n k e d L i s t T o A r r a y %
1241 % %
1242 % %
1243 % %
1244 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1245 %
1246 % LinkedListToArray() converts the linked-list to an array.
1247 %
1248 % The format of the LinkedListToArray method is:
1249 %
1250 % MagickBooleanType LinkedListToArray(LinkedListInfo *list_info,
1251 % void **array)
1252 %
1253 % A description of each parameter follows:
1254 %
1255 % o list_info: the linked-list info.
1256 %
1257 % o array: the array.
1258 %
1259 */
1260 MagickExport MagickBooleanType LinkedListToArray(LinkedListInfo *list_info,
1261  void **array)
1262 {
1263  ElementInfo
1264  *next;
1265 
1266  ssize_t
1267  i;
1268 
1269  assert(list_info != (LinkedListInfo *) NULL);
1270  assert(list_info->signature == MagickCoreSignature);
1271  if (array == (void **) NULL)
1272  return(MagickFalse);
1273  LockSemaphoreInfo(list_info->semaphore);
1274  next=list_info->head;
1275  for (i=0; next != (ElementInfo *) NULL; i++)
1276  {
1277  array[i]=next->value;
1278  next=next->next;
1279  }
1280  UnlockSemaphoreInfo(list_info->semaphore);
1281  return(MagickTrue);
1282 }
1283 ␌
1284 /*
1285 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1286 % %
1287 % %
1288 % %
1289 % N e w H a s h m a p %
1290 % %
1291 % %
1292 % %
1293 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1294 %
1295 % NewHashmap() returns a pointer to a HashmapInfo structure initialized
1296 % to default values. The capacity is an initial estimate. The hashmap will
1297 % increase capacity dynamically as the demand requires.
1298 %
1299 % Prefer a hashmap over a linked-list if you do not require duplicate keys and
1300 % the capacity is large.
1301 %
1302 % The format of the NewHashmap method is:
1303 %
1304 % HashmapInfo *NewHashmap(const size_t capacity,
1305 % size_t (*hash)(const void *),
1306 % MagickBooleanType (*compare)(const void *,const void *),
1307 % void *(*relinquish_key)(void *),void *(*relinquish_value)(void *))
1308 %
1309 % A description of each parameter follows:
1310 %
1311 % o capacity: the initial number entries in the hash-map: typically
1312 % SmallHashmapSize, MediumHashmapSize, or LargeHashmapSize. The
1313 % hashmap will dynamically increase its capacity on demand.
1314 %
1315 % o hash: the hash method, typically HashPointerType(), HashStringType(),
1316 % or HashStringInfoType().
1317 %
1318 % o compare: the compare method, typically NULL, CompareHashmapString(),
1319 % or CompareHashmapStringInfo().
1320 %
1321 % o relinquish_key: the key deallocation method, typically
1322 % RelinquishMagickMemory(), called whenever a key is removed from the
1323 % hash-map.
1324 %
1325 % o relinquish_value: the value deallocation method; typically
1326 % RelinquishMagickMemory(), called whenever a value object is removed from
1327 % the hash-map.
1328 %
1329 */
1330 MagickExport HashmapInfo *NewHashmap(const size_t capacity,
1331  size_t (*hash)(const void *),
1332  MagickBooleanType (*compare)(const void *,const void *),
1333  void *(*relinquish_key)(void *),void *(*relinquish_value)(void *))
1334 {
1335  HashmapInfo
1336  *hashmap_info;
1337 
1338  hashmap_info=(HashmapInfo *) AcquireMagickMemory(sizeof(*hashmap_info));
1339  if (hashmap_info == (HashmapInfo *) NULL)
1340  ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
1341  (void) memset(hashmap_info,0,sizeof(*hashmap_info));
1342  hashmap_info->hash=HashPointerType;
1343  if (hash != (size_t (*)(const void *)) NULL)
1344  hashmap_info->hash=hash;
1345  hashmap_info->compare=(MagickBooleanType (*)(const void *,const void *)) NULL;
1346  if (compare != (MagickBooleanType (*)(const void *,const void *)) NULL)
1347  hashmap_info->compare=compare;
1348  hashmap_info->relinquish_key=relinquish_key;
1349  hashmap_info->relinquish_value=relinquish_value;
1350  hashmap_info->entries=0;
1351  hashmap_info->capacity=capacity;
1352  hashmap_info->map=(LinkedListInfo **) NULL;
1353  if (~capacity >= 1UL)
1354  hashmap_info->map=(LinkedListInfo **) AcquireQuantumMemory((size_t)
1355  capacity+1UL,sizeof(*hashmap_info->map));
1356  if (hashmap_info->map == (LinkedListInfo **) NULL)
1357  ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
1358  (void) memset(hashmap_info->map,0,(size_t) capacity*
1359  sizeof(*hashmap_info->map));
1360  hashmap_info->semaphore=AllocateSemaphoreInfo();
1361  hashmap_info->signature=MagickCoreSignature;
1362  return(hashmap_info);
1363 }
1364 ␌
1365 /*
1366 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1367 % %
1368 % %
1369 % %
1370 % N e w L i n k e d L i s t I n f o %
1371 % %
1372 % %
1373 % %
1374 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1375 %
1376 % NewLinkedList() returns a pointer to a LinkedListInfo structure
1377 % initialized to default values.
1378 %
1379 % The format of the NewLinkedList method is:
1380 %
1381 % LinkedListInfo *NewLinkedList(const size_t capacity)
1382 %
1383 % A description of each parameter follows:
1384 %
1385 % o capacity: the maximum number of elements in the list.
1386 %
1387 */
1388 MagickExport LinkedListInfo *NewLinkedList(const size_t capacity)
1389 {
1391  *list_info;
1392 
1393  list_info=(LinkedListInfo *) AcquireMagickMemory(sizeof(*list_info));
1394  if (list_info == (LinkedListInfo *) NULL)
1395  ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
1396  (void) memset(list_info,0,sizeof(*list_info));
1397  list_info->capacity=capacity == 0 ? (size_t) (~0) : capacity;
1398  list_info->elements=0;
1399  list_info->head=(ElementInfo *) NULL;
1400  list_info->tail=(ElementInfo *) NULL;
1401  list_info->next=(ElementInfo *) NULL;
1402  list_info->semaphore=AllocateSemaphoreInfo();
1403  list_info->signature=MagickCoreSignature;
1404  return(list_info);
1405 }
1406 ␌
1407 /*
1408 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1409 % %
1410 % %
1411 % %
1412 % P u t E n t r y I n H a s h m a p %
1413 % %
1414 % %
1415 % %
1416 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1417 %
1418 % PutEntryInHashmap() puts an entry in the hash-map. If the key already
1419 % exists in the map it is first removed.
1420 %
1421 % The format of the PutEntryInHashmap method is:
1422 %
1423 % MagickBooleanType PutEntryInHashmap(HashmapInfo *hashmap_info,
1424 % const void *key,const void *value)
1425 %
1426 % A description of each parameter follows:
1427 %
1428 % o hashmap_info: the hashmap info.
1429 %
1430 % o key: the key.
1431 %
1432 % o value: the value.
1433 %
1434 */
1435 
1436 static MagickBooleanType IncreaseHashmapCapacity(HashmapInfo *hashmap_info)
1437 {
1438 #define MaxCapacities 20
1439 
1440  const size_t
1441  capacities[MaxCapacities] =
1442  {
1443  17, 31, 61, 131, 257, 509, 1021, 2053, 4099, 8191, 16381, 32771,
1444  65537, 131071, 262147, 524287, 1048573, 2097143, 4194301, 8388617
1445  };
1446 
1447  ElementInfo
1448  *element;
1449 
1450  EntryInfo
1451  *entry;
1452 
1454  *map_info,
1455  **map;
1456 
1457  ElementInfo
1458  *next;
1459 
1460  ssize_t
1461  i;
1462 
1463  size_t
1464  capacity;
1465 
1466  /*
1467  Increase to the next prime capacity.
1468  */
1469  for (i=0; i < MaxCapacities; i++)
1470  if (hashmap_info->capacity < capacities[i])
1471  break;
1472  if (i >= (MaxCapacities-1))
1473  return(MagickFalse);
1474  capacity=capacities[i+1];
1475  map=(LinkedListInfo **) AcquireQuantumMemory((size_t) capacity+1UL,
1476  sizeof(*map));
1477  if (map == (LinkedListInfo **) NULL)
1478  return(MagickFalse);
1479  (void) memset(map,0,(size_t) capacity*sizeof(*map));
1480  /*
1481  Copy entries to new hashmap with increased capacity.
1482  */
1483  for (i=0; i < (ssize_t) hashmap_info->capacity; i++)
1484  {
1486  *list_info;
1487 
1488  list_info=hashmap_info->map[i];
1489  if (list_info == (LinkedListInfo *) NULL)
1490  continue;
1491  LockSemaphoreInfo(list_info->semaphore);
1492  for (next=list_info->head; next != (ElementInfo *) NULL; )
1493  {
1494  element=next;
1495  next=next->next;
1496  entry=(EntryInfo *) element->value;
1497  map_info=map[entry->hash % capacity];
1498  if (map_info == (LinkedListInfo *) NULL)
1499  {
1500  map_info=NewLinkedList(0);
1501  map[entry->hash % capacity]=map_info;
1502  }
1503  map_info->next=element;
1504  element->next=map_info->head;
1505  map_info->head=element;
1506  map_info->elements++;
1507  }
1508  list_info->signature=(~MagickCoreSignature);
1509  UnlockSemaphoreInfo(list_info->semaphore);
1510  DestroySemaphoreInfo(&list_info->semaphore);
1511  list_info=(LinkedListInfo *) RelinquishMagickMemory(list_info);
1512  }
1513  hashmap_info->map=(LinkedListInfo **) RelinquishMagickMemory(
1514  hashmap_info->map);
1515  hashmap_info->map=map;
1516  hashmap_info->capacity=capacity;
1517  return(MagickTrue);
1518 }
1519 
1520 MagickExport MagickBooleanType PutEntryInHashmap(HashmapInfo *hashmap_info,
1521  const void *key,const void *value)
1522 {
1523  EntryInfo
1524  *entry,
1525  *next;
1526 
1528  *list_info;
1529 
1530  size_t
1531  i;
1532 
1533  assert(hashmap_info != (HashmapInfo *) NULL);
1534  assert(hashmap_info->signature == MagickCoreSignature);
1535  if ((key == (void *) NULL) || (value == (void *) NULL))
1536  return(MagickFalse);
1537  next=(EntryInfo *) AcquireMagickMemory(sizeof(*next));
1538  if (next == (EntryInfo *) NULL)
1539  return(MagickFalse);
1540  LockSemaphoreInfo(hashmap_info->semaphore);
1541  next->hash=hashmap_info->hash(key);
1542  next->key=(void *) key;
1543  next->value=(void *) value;
1544  list_info=hashmap_info->map[next->hash % hashmap_info->capacity];
1545  if (list_info == (LinkedListInfo *) NULL)
1546  {
1547  list_info=NewLinkedList(0);
1548  hashmap_info->map[next->hash % hashmap_info->capacity]=list_info;
1549  }
1550  else
1551  {
1552  list_info->next=list_info->head;
1553  entry=(EntryInfo *) GetNextValueInLinkedList(list_info);
1554  for (i=0; entry != (EntryInfo *) NULL; i++)
1555  {
1556  if (entry->hash == next->hash)
1557  {
1558  MagickBooleanType
1559  compare;
1560 
1561  compare=MagickTrue;
1562  if (hashmap_info->compare !=
1563  (MagickBooleanType (*)(const void *,const void *)) NULL)
1564  compare=hashmap_info->compare(key,entry->key);
1565  if (compare != MagickFalse)
1566  {
1567  (void) RemoveElementFromLinkedList(list_info,i);
1568  if (hashmap_info->relinquish_key != (void *(*)(void *)) NULL)
1569  entry->key=hashmap_info->relinquish_key(entry->key);
1570  if (hashmap_info->relinquish_value != (void *(*)(void *)) NULL)
1571  entry->value=hashmap_info->relinquish_value(entry->value);
1572  entry=(EntryInfo *) RelinquishMagickMemory(entry);
1573  break;
1574  }
1575  }
1576  entry=(EntryInfo *) GetNextValueInLinkedList(list_info);
1577  }
1578  }
1579  if (InsertValueInLinkedList(list_info,0,next) == MagickFalse)
1580  {
1581  next=(EntryInfo *) RelinquishMagickMemory(next);
1582  UnlockSemaphoreInfo(hashmap_info->semaphore);
1583  return(MagickFalse);
1584  }
1585  if (list_info->elements >= (hashmap_info->capacity-1))
1586  if (IncreaseHashmapCapacity(hashmap_info) == MagickFalse)
1587  {
1588  UnlockSemaphoreInfo(hashmap_info->semaphore);
1589  return(MagickFalse);
1590  }
1591  hashmap_info->entries++;
1592  UnlockSemaphoreInfo(hashmap_info->semaphore);
1593  return(MagickTrue);
1594 }
1595 ␌
1596 /*
1597 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1598 % %
1599 % %
1600 % %
1601 % 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 %
1602 % %
1603 % %
1604 % %
1605 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1606 %
1607 % RemoveElementByValueFromLinkedList() removes an element from the linked-list
1608 % by value.
1609 %
1610 % The format of the RemoveElementByValueFromLinkedList method is:
1611 %
1612 % void *RemoveElementByValueFromLinkedList(LinkedListInfo *list_info,
1613 % const void *value)
1614 %
1615 % A description of each parameter follows:
1616 %
1617 % o list_info: the list info.
1618 %
1619 % o value: the value.
1620 %
1621 */
1622 MagickExport void *RemoveElementByValueFromLinkedList(LinkedListInfo *list_info,
1623  const void *value)
1624 {
1625  ElementInfo
1626  *next;
1627 
1628  assert(list_info != (LinkedListInfo *) NULL);
1629  assert(list_info->signature == MagickCoreSignature);
1630  if ((list_info->elements == 0) || (value == (const void *) NULL))
1631  return((void *) NULL);
1632  LockSemaphoreInfo(list_info->semaphore);
1633  if (value == list_info->head->value)
1634  {
1635  if (list_info->next == list_info->head)
1636  list_info->next=list_info->head->next;
1637  next=list_info->head;
1638  list_info->head=list_info->head->next;
1639  next=(ElementInfo *) RelinquishMagickMemory(next);
1640  }
1641  else
1642  {
1643  ElementInfo
1644  *element;
1645 
1646  next=list_info->head;
1647  while ((next->next != (ElementInfo *) NULL) &&
1648  (next->next->value != value))
1649  next=next->next;
1650  if (next->next == (ElementInfo *) NULL)
1651  {
1652  UnlockSemaphoreInfo(list_info->semaphore);
1653  return((void *) NULL);
1654  }
1655  element=next->next;
1656  next->next=element->next;
1657  if (element == list_info->tail)
1658  list_info->tail=next;
1659  if (list_info->next == element)
1660  list_info->next=element->next;
1661  element=(ElementInfo *) RelinquishMagickMemory(element);
1662  }
1663  list_info->elements--;
1664  UnlockSemaphoreInfo(list_info->semaphore);
1665  return((void *) value);
1666 }
1667 ␌
1668 /*
1669 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1670 % %
1671 % %
1672 % %
1673 % 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 %
1674 % %
1675 % %
1676 % %
1677 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1678 %
1679 % RemoveElementFromLinkedList() removes an element from the linked-list at the
1680 % specified location.
1681 %
1682 % The format of the RemoveElementFromLinkedList method is:
1683 %
1684 % void *RemoveElementFromLinkedList(LinkedListInfo *list_info,
1685 % const size_t index)
1686 %
1687 % A description of each parameter follows:
1688 %
1689 % o list_info: the linked-list info.
1690 %
1691 % o index: the index.
1692 %
1693 */
1694 MagickExport void *RemoveElementFromLinkedList(LinkedListInfo *list_info,
1695  const size_t index)
1696 {
1697  ElementInfo
1698  *next;
1699 
1700  ssize_t
1701  i;
1702 
1703  void
1704  *value;
1705 
1706  assert(list_info != (LinkedListInfo *) NULL);
1707  assert(list_info->signature == MagickCoreSignature);
1708  if (index >= list_info->elements)
1709  return((void *) NULL);
1710  LockSemaphoreInfo(list_info->semaphore);
1711  if (index == 0)
1712  {
1713  if (list_info->next == list_info->head)
1714  list_info->next=list_info->head->next;
1715  value=list_info->head->value;
1716  next=list_info->head;
1717  list_info->head=list_info->head->next;
1718  next=(ElementInfo *) RelinquishMagickMemory(next);
1719  }
1720  else
1721  {
1722  ElementInfo
1723  *element;
1724 
1725  next=list_info->head;
1726  for (i=1; i < (ssize_t) index; i++)
1727  next=next->next;
1728  element=next->next;
1729  next->next=element->next;
1730  if (element == list_info->tail)
1731  list_info->tail=next;
1732  if (list_info->next == element)
1733  list_info->next=element->next;
1734  value=element->value;
1735  element=(ElementInfo *) RelinquishMagickMemory(element);
1736  }
1737  list_info->elements--;
1738  UnlockSemaphoreInfo(list_info->semaphore);
1739  return(value);
1740 }
1741 ␌
1742 /*
1743 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1744 % %
1745 % %
1746 % %
1747 % R e m o v e E n t r y F r o m H a s h m a p %
1748 % %
1749 % %
1750 % %
1751 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1752 %
1753 % RemoveEntryFromHashmap() removes an entry from the hash-map by its key.
1754 %
1755 % The format of the RemoveEntryFromHashmap method is:
1756 %
1757 % void *RemoveEntryFromHashmap(HashmapInfo *hashmap_info,void *key)
1758 %
1759 % A description of each parameter follows:
1760 %
1761 % o hashmap_info: the hashmap info.
1762 %
1763 % o key: the key.
1764 %
1765 */
1766 MagickExport void *RemoveEntryFromHashmap(HashmapInfo *hashmap_info,
1767  const void *key)
1768 {
1769  EntryInfo
1770  *entry;
1771 
1773  *list_info;
1774 
1775  size_t
1776  i;
1777 
1778  size_t
1779  hash;
1780 
1781  void
1782  *value;
1783 
1784  assert(hashmap_info != (HashmapInfo *) NULL);
1785  assert(hashmap_info->signature == MagickCoreSignature);
1786  if (key == (const void *) NULL)
1787  return((void *) NULL);
1788  LockSemaphoreInfo(hashmap_info->semaphore);
1789  hash=hashmap_info->hash(key);
1790  list_info=hashmap_info->map[hash % hashmap_info->capacity];
1791  if (list_info != (LinkedListInfo *) NULL)
1792  {
1793  list_info->next=list_info->head;
1794  entry=(EntryInfo *) GetNextValueInLinkedList(list_info);
1795  for (i=0; entry != (EntryInfo *) NULL; i++)
1796  {
1797  if (entry->hash == hash)
1798  {
1799  MagickBooleanType
1800  compare;
1801 
1802  compare=MagickTrue;
1803  if (hashmap_info->compare !=
1804  (MagickBooleanType (*)(const void *,const void *)) NULL)
1805  compare=hashmap_info->compare(key,entry->key);
1806  if (compare != MagickFalse)
1807  {
1808  entry=(EntryInfo *) RemoveElementFromLinkedList(list_info,i);
1809  if (entry == (EntryInfo *) NULL)
1810  {
1811  UnlockSemaphoreInfo(hashmap_info->semaphore);
1812  return((void *) NULL);
1813  }
1814  if (hashmap_info->relinquish_key != (void *(*)(void *)) NULL)
1815  entry->key=hashmap_info->relinquish_key(entry->key);
1816  value=entry->value;
1817  entry=(EntryInfo *) RelinquishMagickMemory(entry);
1818  hashmap_info->entries--;
1819  UnlockSemaphoreInfo(hashmap_info->semaphore);
1820  return(value);
1821  }
1822  }
1823  entry=(EntryInfo *) GetNextValueInLinkedList(list_info);
1824  }
1825  }
1826  UnlockSemaphoreInfo(hashmap_info->semaphore);
1827  return((void *) NULL);
1828 }
1829 ␌
1830 /*
1831 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1832 % %
1833 % %
1834 % %
1835 % 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 %
1836 % %
1837 % %
1838 % %
1839 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1840 %
1841 % RemoveLastElementFromLinkedList() removes the last element from the
1842 % linked-list.
1843 %
1844 % The format of the RemoveLastElementFromLinkedList method is:
1845 %
1846 % void *RemoveLastElementFromLinkedList(LinkedListInfo *list_info)
1847 %
1848 % A description of each parameter follows:
1849 %
1850 % o list_info: the linked-list info.
1851 %
1852 */
1853 MagickExport void *RemoveLastElementFromLinkedList(LinkedListInfo *list_info)
1854 {
1855  void
1856  *value;
1857 
1858  assert(list_info != (LinkedListInfo *) NULL);
1859  assert(list_info->signature == MagickCoreSignature);
1860  if (list_info->elements == 0)
1861  return((void *) NULL);
1862  LockSemaphoreInfo(list_info->semaphore);
1863  if (list_info->next == list_info->tail)
1864  list_info->next=(ElementInfo *) NULL;
1865  if (list_info->elements == 1UL)
1866  {
1867  value=list_info->head->value;
1868  list_info->head=(ElementInfo *) NULL;
1869  list_info->tail=(ElementInfo *) RelinquishMagickMemory(list_info->tail);
1870  }
1871  else
1872  {
1873  ElementInfo
1874  *next;
1875 
1876  value=list_info->tail->value;
1877  next=list_info->head;
1878  while (next->next != list_info->tail)
1879  next=next->next;
1880  list_info->tail=(ElementInfo *) RelinquishMagickMemory(list_info->tail);
1881  list_info->tail=next;
1882  next->next=(ElementInfo *) NULL;
1883  }
1884  list_info->elements--;
1885  UnlockSemaphoreInfo(list_info->semaphore);
1886  return(value);
1887 }
1888 ␌
1889 /*
1890 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1891 % %
1892 % %
1893 % %
1894 % R e s e t H a s h m a p I t e r a t o r %
1895 % %
1896 % %
1897 % %
1898 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1899 %
1900 % ResetHashmapIterator() resets the hash-map iterator. Use it in conjunction
1901 % with GetNextKeyInHashmap() to iterate over all the keys in the hash-map.
1902 %
1903 % The format of the ResetHashmapIterator method is:
1904 %
1905 % ResetHashmapIterator(HashmapInfo *hashmap_info)
1906 %
1907 % A description of each parameter follows:
1908 %
1909 % o hashmap_info: the hashmap info.
1910 %
1911 */
1912 MagickExport void ResetHashmapIterator(HashmapInfo *hashmap_info)
1913 {
1914  assert(hashmap_info != (HashmapInfo *) NULL);
1915  assert(hashmap_info->signature == MagickCoreSignature);
1916  LockSemaphoreInfo(hashmap_info->semaphore);
1917  hashmap_info->next=0;
1918  hashmap_info->head_of_list=MagickFalse;
1919  UnlockSemaphoreInfo(hashmap_info->semaphore);
1920 }
1921 ␌
1922 /*
1923 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1924 % %
1925 % %
1926 % %
1927 % R e s e t L i n k e d L i s t I t e r a t o r %
1928 % %
1929 % %
1930 % %
1931 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1932 %
1933 % ResetLinkedListIterator() resets the lined-list iterator. Use it in
1934 % conjunction with GetNextValueInLinkedList() to iterate over all the values
1935 % in the linked-list.
1936 %
1937 % The format of the ResetLinkedListIterator method is:
1938 %
1939 % ResetLinkedListIterator(LinkedListInfo *list_info)
1940 %
1941 % A description of each parameter follows:
1942 %
1943 % o list_info: the linked-list info.
1944 %
1945 */
1946 MagickExport void ResetLinkedListIterator(LinkedListInfo *list_info)
1947 {
1948  assert(list_info != (LinkedListInfo *) NULL);
1949  assert(list_info->signature == MagickCoreSignature);
1950  LockSemaphoreInfo(list_info->semaphore);
1951  list_info->next=list_info->head;
1952  UnlockSemaphoreInfo(list_info->semaphore);
1953 }
1954 ␌
1955 /*
1956 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1957 % %
1958 % %
1959 % %
1960 % 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 %
1961 % %
1962 % %
1963 % %
1964 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1965 %
1966 % SetHeadElementInLinkedList() sets the head element of the linked-list.
1967 %
1968 % The format of the SetHeadElementInLinkedList method is:
1969 %
1970 % SetHeadElementInLinkedList(LinkedListInfo *list_info,
1971 % ElementInfo *element)
1972 %
1973 % A description of each parameter follows:
1974 %
1975 % o list_info: the linked-list info.
1976 %
1977 % o element: the element to set as the head.
1978 %
1979 */
1980 MagickPrivate void SetHeadElementInLinkedList(LinkedListInfo *list_info,
1981  ElementInfo *element)
1982 {
1983  ElementInfo
1984  *prev;
1985 
1986  assert(list_info != (LinkedListInfo *) NULL);
1987  assert(list_info->signature == MagickCoreSignature);
1988  assert(element != (ElementInfo *) NULL);
1989  if (element == list_info->head)
1990  return;
1991  prev=list_info->head;
1992  while (prev != (ElementInfo *) NULL)
1993  {
1994  if (prev->next == element)
1995  {
1996  prev->next=element->next;
1997  element->next=list_info->head;
1998  if (list_info->head == list_info->next)
1999  list_info->next=element;
2000  list_info->head=element;
2001  break;
2002  }
2003  prev=prev->next;
2004  }
2005 }