2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
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 %
13 % MagickCore Hash-map and Linked-list Methods %
20 % Copyright 1999-2014 ImageMagick Studio LLC, a non-profit organization %
21 % dedicated to making software imaging solutions freely available. %
23 % You may not use this file except in compliance with the License. You may %
24 % obtain a copy of the License at %
26 % http://www.imagemagick.org/script/license.php %
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. %
34 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
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.
45 #include "MagickCore/studio.h"
46 #include "MagickCore/exception.h"
47 #include "MagickCore/exception-private.h"
48 #include "MagickCore/hashmap.h"
49 #include "MagickCore/memory_.h"
50 #include "MagickCore/semaphore.h"
51 #include "MagickCore/signature-private.h"
52 #include "MagickCore/string_.h"
57 typedef struct _ElementInfo
66 typedef struct _EntryInfo
76 struct _LinkedListInfo
97 (*hash)(const void *);
100 (*compare)(const void *,const void *);
103 *(*relinquish_key)(void *),
104 *(*relinquish_value)(void *);
125 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
129 % A p p e n d V a l u e T o L i n k e d L i s t %
133 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
135 % AppendValueToLinkedList() appends a value to the end of the linked-list.
137 % The format of the AppendValueToLinkedList method is:
139 % MagickBooleanType AppendValueToLinkedList(LinkedListInfo *list_info,
142 % A description of each parameter follows:
144 % o list_info: the linked-list info.
146 % o value: the value.
149 MagickExport MagickBooleanType AppendValueToLinkedList(
150 LinkedListInfo *list_info,const void *value)
155 assert(list_info != (LinkedListInfo *) NULL);
156 assert(list_info->signature == MagickSignature);
157 if (list_info->elements == list_info->capacity)
159 next=(ElementInfo *) AcquireMagickMemory(sizeof(*next));
160 if (next == (ElementInfo *) NULL)
162 next->value=(void *) value;
163 next->next=(ElementInfo *) NULL;
164 LockSemaphoreInfo(list_info->semaphore);
165 if (list_info->next == (ElementInfo *) NULL)
166 list_info->next=next;
167 if (list_info->elements == 0)
168 list_info->head=next;
170 list_info->tail->next=next;
171 list_info->tail=next;
172 list_info->elements++;
173 UnlockSemaphoreInfo(list_info->semaphore);
178 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
182 % C l e a r L i n k e d L i s t %
186 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
188 % ClearLinkedList() clears all the elements from the linked-list.
190 % The format of the ClearLinkedList method is:
192 % void ClearLinkedList(LinkedListInfo *list_info,
193 % void *(*relinquish_value)(void *))
195 % A description of each parameter follows:
197 % o list_info: the linked-list info.
199 % o relinquish_value: the value deallocation method; typically
200 % RelinquishMagickMemory().
203 MagickExport void ClearLinkedList(LinkedListInfo *list_info,
204 void *(*relinquish_value)(void *))
212 assert(list_info != (LinkedListInfo *) NULL);
213 assert(list_info->signature == MagickSignature);
214 LockSemaphoreInfo(list_info->semaphore);
215 next=list_info->head;
216 while (next != (ElementInfo *) NULL)
218 if (relinquish_value != (void *(*)(void *)) NULL)
219 next->value=relinquish_value(next->value);
222 element=(ElementInfo *) RelinquishMagickMemory(element);
224 list_info->head=(ElementInfo *) NULL;
225 list_info->tail=(ElementInfo *) NULL;
226 list_info->next=(ElementInfo *) NULL;
227 list_info->elements=0;
228 UnlockSemaphoreInfo(list_info->semaphore);
232 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
236 % C o m p a r e H a s h m a p S t r i n g %
240 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
242 % CompareHashmapString() finds an entry in a hash-map based on the contents
245 % The format of the CompareHashmapString method is:
247 % MagickBooleanType CompareHashmapString(const void *target,
248 % const void *source)
250 % A description of each parameter follows:
252 % o target: the target string.
254 % o source: the source string.
257 MagickExport MagickBooleanType CompareHashmapString(const void *target,
264 p=(const char *) target;
265 q=(const char *) source;
266 return(IsMagickTrue(LocaleCompare(p,q)));
270 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
274 % C o m p a r e H a s h m a p S t r i n g I n f o %
278 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
280 % CompareHashmapStringInfo() finds an entry in a hash-map based on the
281 % contents of a string.
283 % The format of the CompareHashmapStringInfo method is:
285 % MagickBooleanType CompareHashmapStringInfo(const void *target,
286 % const void *source)
288 % A description of each parameter follows:
290 % o target: the target string.
292 % o source: the source string.
295 MagickExport MagickBooleanType CompareHashmapStringInfo(const void *target,
298 return(IsMagickTrue(LocaleCompare((const char *)target,
299 (const char *)source)));
303 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
307 % D e s t r o y H a s h m a p %
311 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
313 % DestroyHashmap() frees the hash-map and all associated resources.
315 % The format of the DestroyHashmap method is:
317 % HashmapInfo *DestroyHashmap(HashmapInfo *hashmap_info)
319 % A description of each parameter follows:
321 % o hashmap_info: the hashmap info.
324 MagickExport HashmapInfo *DestroyHashmap(HashmapInfo *hashmap_info)
335 assert(hashmap_info != (HashmapInfo *) NULL);
336 assert(hashmap_info->signature == MagickSignature);
337 LockSemaphoreInfo(hashmap_info->semaphore);
338 for (i=0; i < (ssize_t) hashmap_info->capacity; i++)
340 list_info=hashmap_info->map[i];
341 if (list_info != (LinkedListInfo *) NULL)
343 list_info->next=list_info->head;
344 entry=(EntryInfo *) GetNextValueInLinkedList(list_info);
345 while (entry != (EntryInfo *) NULL)
347 if (hashmap_info->relinquish_key != (void *(*)(void *)) NULL)
348 entry->key=hashmap_info->relinquish_key(entry->key);
349 if (hashmap_info->relinquish_value != (void *(*)(void *)) NULL)
350 entry->value=hashmap_info->relinquish_value(entry->value);
351 entry=(EntryInfo *) GetNextValueInLinkedList(list_info);
354 if (list_info != (LinkedListInfo *) NULL)
355 list_info=DestroyLinkedList(list_info,RelinquishMagickMemory);
357 hashmap_info->map=(LinkedListInfo **) RelinquishMagickMemory(
359 hashmap_info->signature=(~MagickSignature);
360 UnlockSemaphoreInfo(hashmap_info->semaphore);
361 RelinquishSemaphoreInfo(&hashmap_info->semaphore);
362 hashmap_info=(HashmapInfo *) RelinquishMagickMemory(hashmap_info);
363 return(hashmap_info);
367 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
371 % D e s t r o y L i n k e d L i s t %
375 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
377 % DestroyLinkedList() frees the linked-list and all associated resources.
379 % The format of the DestroyLinkedList method is:
381 % LinkedListInfo *DestroyLinkedList(LinkedListInfo *list_info,
382 % void *(*relinquish_value)(void *))
384 % A description of each parameter follows:
386 % o list_info: the linked-list info.
388 % o relinquish_value: the value deallocation method; typically
389 % RelinquishMagickMemory().
392 MagickExport LinkedListInfo *DestroyLinkedList(LinkedListInfo *list_info,
393 void *(*relinquish_value)(void *))
401 assert(list_info != (LinkedListInfo *) NULL);
402 assert(list_info->signature == MagickSignature);
403 LockSemaphoreInfo(list_info->semaphore);
404 for (next=list_info->head; next != (ElementInfo *) NULL; )
406 if (relinquish_value != (void *(*)(void *)) NULL)
407 next->value=relinquish_value(next->value);
410 entry=(ElementInfo *) RelinquishMagickMemory(entry);
412 list_info->signature=(~MagickSignature);
413 UnlockSemaphoreInfo(list_info->semaphore);
414 RelinquishSemaphoreInfo(&list_info->semaphore);
415 list_info=(LinkedListInfo *) RelinquishMagickMemory(list_info);
420 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
424 % G e t L a s t V a l u e I n L i n k e d L i s t %
428 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
430 % GetLastValueInLinkedList() gets the last value in the linked-list.
432 % The format of the GetLastValueInLinkedList method is:
434 % void *GetLastValueInLinkedList(LinkedListInfo *list_info)
436 % A description of each parameter follows:
438 % o list_info: the linked_list info.
441 MagickExport void *GetLastValueInLinkedList(LinkedListInfo *list_info)
446 assert(list_info != (LinkedListInfo *) NULL);
447 assert(list_info->signature == MagickSignature);
448 if (list_info->elements == 0)
449 return((void *) NULL);
450 LockSemaphoreInfo(list_info->semaphore);
451 value=list_info->tail->value;
452 UnlockSemaphoreInfo(list_info->semaphore);
457 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
461 % G e t N e x t K e y I n H a s h m a p %
465 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
467 % GetNextKeyInHashmap() gets the next key in the hash-map.
469 % The format of the GetNextKeyInHashmap method is:
471 % void *GetNextKeyInHashmap(HashmapInfo *hashmap_info)
473 % A description of each parameter follows:
475 % o hashmap_info: the hashmap info.
478 MagickExport void *GetNextKeyInHashmap(HashmapInfo *hashmap_info)
489 assert(hashmap_info != (HashmapInfo *) NULL);
490 assert(hashmap_info->signature == MagickSignature);
491 LockSemaphoreInfo(hashmap_info->semaphore);
492 while (hashmap_info->next < hashmap_info->capacity)
494 list_info=hashmap_info->map[hashmap_info->next];
495 if (list_info != (LinkedListInfo *) NULL)
497 if (IfMagickFalse(hashmap_info->head_of_list))
499 list_info->next=list_info->head;
500 hashmap_info->head_of_list=MagickTrue;
502 entry=(EntryInfo *) GetNextValueInLinkedList(list_info);
503 if (entry != (EntryInfo *) NULL)
506 UnlockSemaphoreInfo(hashmap_info->semaphore);
509 hashmap_info->head_of_list=MagickFalse;
511 hashmap_info->next++;
513 UnlockSemaphoreInfo(hashmap_info->semaphore);
514 return((void *) NULL);
518 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
522 % G e t N e x t V a l u e I n H a s h m a p %
526 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
528 % GetNextValueInHashmap() gets the next value in the hash-map.
530 % The format of the GetNextValueInHashmap method is:
532 % void *GetNextValueInHashmap(HashmapInfo *hashmap_info)
534 % A description of each parameter follows:
536 % o hashmap_info: the hashmap info.
539 MagickExport void *GetNextValueInHashmap(HashmapInfo *hashmap_info)
550 assert(hashmap_info != (HashmapInfo *) NULL);
551 assert(hashmap_info->signature == MagickSignature);
552 LockSemaphoreInfo(hashmap_info->semaphore);
553 while (hashmap_info->next < hashmap_info->capacity)
555 list_info=hashmap_info->map[hashmap_info->next];
556 if (list_info != (LinkedListInfo *) NULL)
558 if (IfMagickFalse(hashmap_info->head_of_list))
560 list_info->next=list_info->head;
561 hashmap_info->head_of_list=MagickTrue;
563 entry=(EntryInfo *) GetNextValueInLinkedList(list_info);
564 if (entry != (EntryInfo *) NULL)
567 UnlockSemaphoreInfo(hashmap_info->semaphore);
570 hashmap_info->head_of_list=MagickFalse;
572 hashmap_info->next++;
574 UnlockSemaphoreInfo(hashmap_info->semaphore);
575 return((void *) NULL);
579 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
583 % G e t N e x t V a l u e I n L i n k e d L i s t %
587 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
589 % GetNextValueInLinkedList() gets the next value in the linked-list.
591 % The format of the GetNextValueInLinkedList method is:
593 % void *GetNextValueInLinkedList(LinkedListInfo *list_info)
595 % A description of each parameter follows:
597 % o list_info: the linked-list info.
600 MagickExport void *GetNextValueInLinkedList(LinkedListInfo *list_info)
605 assert(list_info != (LinkedListInfo *) NULL);
606 assert(list_info->signature == MagickSignature);
607 LockSemaphoreInfo(list_info->semaphore);
608 if (list_info->next == (ElementInfo *) NULL)
610 UnlockSemaphoreInfo(list_info->semaphore);
611 return((void *) NULL);
613 value=list_info->next->value;
614 list_info->next=list_info->next->next;
615 UnlockSemaphoreInfo(list_info->semaphore);
620 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
624 % 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 %
628 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
630 % GetNumberOfEntriesInHashmap() returns the number of entries in the hash-map.
632 % The format of the GetNumberOfEntriesInHashmap method is:
634 % size_t GetNumberOfEntriesInHashmap(const HashmapInfo *hashmap_info)
636 % A description of each parameter follows:
638 % o hashmap_info: the hashmap info.
641 MagickExport size_t GetNumberOfEntriesInHashmap(
642 const HashmapInfo *hashmap_info)
644 assert(hashmap_info != (HashmapInfo *) NULL);
645 assert(hashmap_info->signature == MagickSignature);
646 return(hashmap_info->entries);
650 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
654 % 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 %
658 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
660 % GetNumberOfElementsInLinkedList() returns the number of entries in the
663 % The format of the GetNumberOfElementsInLinkedList method is:
665 % size_t GetNumberOfElementsInLinkedList(
666 % const LinkedListInfo *list_info)
668 % A description of each parameter follows:
670 % o list_info: the linked-list info.
673 MagickExport size_t GetNumberOfElementsInLinkedList(
674 const LinkedListInfo *list_info)
676 assert(list_info != (LinkedListInfo *) NULL);
677 assert(list_info->signature == MagickSignature);
678 return(list_info->elements);
682 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
686 % G e t V a l u e F r o m H a s h m a p %
690 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
692 % GetValueFromHashmap() gets an entry from the hash-map by its key.
694 % The format of the GetValueFromHashmap method is:
696 % void *GetValueFromHashmap(HashmapInfo *hashmap_info,const void *key)
698 % A description of each parameter follows:
700 % o hashmap_info: the hashmap info.
705 MagickExport void *GetValueFromHashmap(HashmapInfo *hashmap_info,
720 assert(hashmap_info != (HashmapInfo *) NULL);
721 assert(hashmap_info->signature == MagickSignature);
722 if (key == (const void *) NULL)
723 return((void *) NULL);
724 LockSemaphoreInfo(hashmap_info->semaphore);
725 hash=hashmap_info->hash(key);
726 list_info=hashmap_info->map[hash % hashmap_info->capacity];
727 if (list_info != (LinkedListInfo *) NULL)
729 list_info->next=list_info->head;
730 entry=(EntryInfo *) GetNextValueInLinkedList(list_info);
731 while (entry != (EntryInfo *) NULL)
733 if (entry->hash == hash)
739 if (hashmap_info->compare !=
740 (MagickBooleanType (*)(const void *,const void *)) NULL)
741 compare=hashmap_info->compare(key,entry->key);
742 if (IfMagickTrue(compare))
745 UnlockSemaphoreInfo(hashmap_info->semaphore);
749 entry=(EntryInfo *) GetNextValueInLinkedList(list_info);
752 UnlockSemaphoreInfo(hashmap_info->semaphore);
753 return((void *) NULL);
757 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
761 % G e t V a l u e F r o m L i n k e d L i s t %
765 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
767 % GetValueFromLinkedList() gets a value from the linked-list at the specified
770 % The format of the GetValueFromLinkedList method is:
772 % void *GetValueFromLinkedList(LinkedListInfo *list_info,
773 % const size_t index)
775 % A description of each parameter follows:
777 % o list_info: the linked_list info.
779 % o index: the list index.
782 MagickExport void *GetValueFromLinkedList(LinkedListInfo *list_info,
794 assert(list_info != (LinkedListInfo *) NULL);
795 assert(list_info->signature == MagickSignature);
796 if (index >= list_info->elements)
797 return((void *) NULL);
798 LockSemaphoreInfo(list_info->semaphore);
801 value=list_info->head->value;
802 UnlockSemaphoreInfo(list_info->semaphore);
805 if (index == (list_info->elements-1))
807 value=list_info->tail->value;
808 UnlockSemaphoreInfo(list_info->semaphore);
811 next=list_info->head;
812 for (i=0; i < (ssize_t) index; i++)
815 UnlockSemaphoreInfo(list_info->semaphore);
820 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
824 % H a s h P o i n t e r T y p e %
828 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
830 % HashPointerType() finds an entry in a hash-map based on the address of a
833 % The format of the HashPointerType method is:
835 % size_t HashPointerType(const void *pointer)
837 % A description of each parameter follows:
839 % o pointer: compute the hash entry location from this pointer address.
842 MagickExport size_t HashPointerType(const void *pointer)
847 hash=(size_t) pointer;
848 hash+=(~(hash << 9));
856 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
860 % H a s h S t r i n g T y p e %
864 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
866 % HashStringType() finds an entry in a hash-map based on the contents of a
869 % The format of the HashStringType method is:
871 % size_t HashStringType(const void *string)
873 % A description of each parameter follows:
875 % o string: compute the hash entry location from this string.
878 MagickExport size_t HashStringType(const void *string)
895 signature_info=AcquireSignatureInfo();
896 signature=StringToStringInfo((const char *) string);
897 UpdateSignature(signature_info,signature);
898 FinalizeSignature(signature_info);
899 digest=GetStringInfoDatum(GetSignatureDigest(signature_info));
901 for (i=0; i < 8; i++)
903 signature=DestroyStringInfo(signature);
904 signature_info=DestroySignatureInfo(signature_info);
909 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
913 % H a s h S t r i n g I n f o T y p e %
917 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
919 % Specify the HashStringInfoType() method in NewHashmap() to find an entry
920 % in a hash-map based on the contents of a string.
922 % The format of the HashStringInfoType method is:
924 % size_t HashStringInfoType(const void *string_info)
926 % A description of each parameter follows:
928 % o string_info: compute the hash entry location from this string.
931 MagickExport size_t HashStringInfoType(const void *string_info)
945 signature_info=AcquireSignatureInfo();
946 UpdateSignature(signature_info,(const StringInfo *) string_info);
947 FinalizeSignature(signature_info);
948 digest=GetStringInfoDatum(GetSignatureDigest(signature_info));
950 for (i=0; i < 8; i++)
952 signature_info=DestroySignatureInfo(signature_info);
957 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
961 % I n s e r t V a l u e I n L i n k e d L i s t %
965 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
967 % InsertValueInLinkedList() inserts an element in the linked-list at the
968 % specified location.
970 % The format of the InsertValueInLinkedList method is:
972 % MagickBooleanType InsertValueInLinkedList(ListInfo *list_info,
973 % const size_t index,const void *value)
975 % A description of each parameter follows:
977 % o list_info: the hashmap info.
979 % o index: the index.
981 % o value: the value.
984 MagickExport MagickBooleanType InsertValueInLinkedList(
985 LinkedListInfo *list_info,const size_t index,const void *value)
993 assert(list_info != (LinkedListInfo *) NULL);
994 assert(list_info->signature == MagickSignature);
995 if (value == (const void *) NULL)
997 if ((index > list_info->elements) ||
998 (list_info->elements == list_info->capacity))
1000 next=(ElementInfo *) AcquireMagickMemory(sizeof(*next));
1001 if (next == (ElementInfo *) NULL)
1002 return(MagickFalse);
1003 next->value=(void *) value;
1004 next->next=(ElementInfo *) NULL;
1005 LockSemaphoreInfo(list_info->semaphore);
1006 if (list_info->elements == 0)
1008 if (list_info->next == (ElementInfo *) NULL)
1009 list_info->next=next;
1010 list_info->head=next;
1011 list_info->tail=next;
1017 if (list_info->next == list_info->head)
1018 list_info->next=next;
1019 next->next=list_info->head;
1020 list_info->head=next;
1023 if (index == list_info->elements)
1025 if (list_info->next == (ElementInfo *) NULL)
1026 list_info->next=next;
1027 list_info->tail->next=next;
1028 list_info->tail=next;
1035 element=list_info->head;
1036 next->next=element->next;
1037 for (i=1; i < (ssize_t) index; i++)
1039 element=element->next;
1040 next->next=element->next;
1044 if (list_info->next == next->next)
1045 list_info->next=next;
1048 list_info->elements++;
1049 UnlockSemaphoreInfo(list_info->semaphore);
1054 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1058 % 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 %
1062 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1064 % InsertValueInSortedLinkedList() inserts a value in the sorted linked-list.
1066 % The format of the InsertValueInSortedLinkedList method is:
1068 % MagickBooleanType InsertValueInSortedLinkedList(ListInfo *list_info,
1069 % int (*compare)(const void *,const void *),void **replace,
1070 % const void *value)
1072 % A description of each parameter follows:
1074 % o list_info: the hashmap info.
1076 % o index: the index.
1078 % o compare: the compare method.
1080 % o replace: return previous element here.
1082 % o value: the value.
1085 MagickExport MagickBooleanType InsertValueInSortedLinkedList(
1086 LinkedListInfo *list_info,int (*compare)(const void *,const void *),
1087 void **replace,const void *value)
1092 register ElementInfo
1098 assert(list_info != (LinkedListInfo *) NULL);
1099 assert(list_info->signature == MagickSignature);
1100 if ((compare == (int (*)(const void *,const void *)) NULL) ||
1101 (value == (const void *) NULL))
1102 return(MagickFalse);
1103 if (list_info->elements == list_info->capacity)
1104 return(MagickFalse);
1105 next=(ElementInfo *) AcquireMagickMemory(sizeof(*next));
1106 if (next == (ElementInfo *) NULL)
1107 return(MagickFalse);
1108 next->value=(void *) value;
1109 element=(ElementInfo *) NULL;
1110 LockSemaphoreInfo(list_info->semaphore);
1111 next->next=list_info->head;
1112 while (next->next != (ElementInfo *) NULL)
1114 i=(ssize_t) compare(value,next->next->value);
1115 if ((i < 0) || ((replace != (void **) NULL) && (i == 0)))
1119 *replace=next->next->value;
1120 next->next=next->next->next;
1121 if (element != (ElementInfo *) NULL)
1122 element->next=(ElementInfo *) RelinquishMagickMemory(
1124 list_info->elements--;
1126 if (element != (ElementInfo *) NULL)
1129 list_info->head=next;
1133 next->next=next->next->next;
1135 if (next->next == (ElementInfo *) NULL)
1137 if (element != (ElementInfo *) NULL)
1140 list_info->head=next;
1141 list_info->tail=next;
1143 list_info->elements++;
1144 UnlockSemaphoreInfo(list_info->semaphore);
1149 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1153 % I s H a s h m a p E m p t y %
1157 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1159 % IsHashmapEmpty() returns MagickTrue if the hash-map is empty.
1161 % The format of the IsHashmapEmpty method is:
1163 % MagickBooleanType IsHashmapEmpty(const HashmapInfo *hashmap_info)
1165 % A description of each parameter follows:
1167 % o hashmap_info: the hashmap info.
1170 MagickExport MagickBooleanType IsHashmapEmpty(const HashmapInfo *hashmap_info)
1172 assert(hashmap_info != (HashmapInfo *) NULL);
1173 assert(hashmap_info->signature == MagickSignature);
1174 return(IsMagickTrue(hashmap_info->entries == 0));
1178 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1182 % I s L i n k e d L i s t E m p t y %
1186 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1188 % IsLinkedListEmpty() returns MagickTrue if the linked-list is empty.
1190 % The format of the IsLinkedListEmpty method is:
1192 % MagickBooleanType IsLinkedListEmpty(LinkedListInfo *list_info)
1194 % A description of each parameter follows:
1196 % o list_info: the linked-list info.
1199 MagickExport MagickBooleanType IsLinkedListEmpty(
1200 const LinkedListInfo *list_info)
1202 assert(list_info != (LinkedListInfo *) NULL);
1203 assert(list_info->signature == MagickSignature);
1204 return(IsMagickTrue(list_info->elements == 0));
1208 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1212 % L i n k e d L i s t T o A r r a y %
1216 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1218 % LinkedListToArray() converts the linked-list to an array.
1220 % The format of the LinkedListToArray method is:
1222 % MagickBooleanType LinkedListToArray(LinkedListInfo *list_info,
1225 % A description of each parameter follows:
1227 % o list_info: the linked-list info.
1229 % o array: the array.
1232 MagickExport MagickBooleanType LinkedListToArray(LinkedListInfo *list_info,
1235 register ElementInfo
1241 assert(list_info != (LinkedListInfo *) NULL);
1242 assert(list_info->signature == MagickSignature);
1243 if (array == (void **) NULL)
1244 return(MagickFalse);
1245 LockSemaphoreInfo(list_info->semaphore);
1246 next=list_info->head;
1247 for (i=0; next != (ElementInfo *) NULL; i++)
1249 array[i]=next->value;
1252 UnlockSemaphoreInfo(list_info->semaphore);
1257 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1261 % N e w H a s h m a p %
1265 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1267 % NewHashmap() returns a pointer to a HashmapInfo structure initialized
1268 % to default values. The capacity is an initial estimate. The hashmap will
1269 % increase capacity dynamically as the demand requires.
1271 % The format of the NewHashmap method is:
1273 % HashmapInfo *NewHashmap(const size_t capacity,
1274 % size_t (*hash)(const void *),
1275 % MagickBooleanType (*compare)(const void *,const void *),
1276 % void *(*relinquish_key)(void *),void *(*relinquish_value)(void *))
1278 % A description of each parameter follows:
1280 % o capacity: the initial number entries in the hash-map: typically
1281 % SmallHashmapSize, MediumHashmapSize, or LargeHashmapSize. The
1282 % hashmap will dynamically increase its capacity on demand.
1284 % o hash: the hash method, typically HashPointerType(), HashStringType(),
1285 % or HashStringInfoType().
1287 % o compare: the compare method, typically NULL, CompareHashmapString(),
1288 % or CompareHashmapStringInfo().
1290 % o relinquish_key: the key deallocation method, typically
1291 % RelinquishMagickMemory(), called whenever a key is removed from the
1294 % o relinquish_value: the value deallocation method; typically
1295 % RelinquishMagickMemory(), called whenever a value object is removed from
1299 MagickExport HashmapInfo *NewHashmap(const size_t capacity,
1300 size_t (*hash)(const void *),
1301 MagickBooleanType (*compare)(const void *,const void *),
1302 void *(*relinquish_key)(void *),void *(*relinquish_value)(void *))
1307 hashmap_info=(HashmapInfo *) AcquireMagickMemory(sizeof(*hashmap_info));
1308 if (hashmap_info == (HashmapInfo *) NULL)
1309 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
1310 (void) ResetMagickMemory(hashmap_info,0,sizeof(*hashmap_info));
1311 hashmap_info->hash=HashPointerType;
1312 if (hash != (size_t (*)(const void *)) NULL)
1313 hashmap_info->hash=hash;
1314 hashmap_info->compare=(MagickBooleanType (*)(const void *,const void *)) NULL;
1315 if (compare != (MagickBooleanType (*)(const void *,const void *)) NULL)
1316 hashmap_info->compare=compare;
1317 hashmap_info->relinquish_key=relinquish_key;
1318 hashmap_info->relinquish_value=relinquish_value;
1319 hashmap_info->entries=0;
1320 hashmap_info->capacity=capacity;
1321 hashmap_info->map=(LinkedListInfo **) NULL;
1322 if (~capacity >= 1UL)
1323 hashmap_info->map=(LinkedListInfo **) AcquireQuantumMemory((size_t)
1324 capacity+1UL,sizeof(*hashmap_info->map));
1325 if (hashmap_info->map == (LinkedListInfo **) NULL)
1326 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
1327 (void) ResetMagickMemory(hashmap_info->map,0,(size_t) capacity*
1328 sizeof(*hashmap_info->map));
1329 hashmap_info->semaphore=AcquireSemaphoreInfo();
1330 hashmap_info->signature=MagickSignature;
1331 return(hashmap_info);
1335 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1339 % N e w L i n k e d L i s t I n f o %
1343 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1345 % NewLinkedList() returns a pointer to a LinkedListInfo structure
1346 % initialized to default values.
1348 % The format of the NewLinkedList method is:
1350 % LinkedListInfo *NewLinkedList(const size_t capacity)
1352 % A description of each parameter follows:
1354 % o capacity: the maximum number of elements in the list.
1357 MagickExport LinkedListInfo *NewLinkedList(const size_t capacity)
1362 list_info=(LinkedListInfo *) AcquireMagickMemory(sizeof(*list_info));
1363 if (list_info == (LinkedListInfo *) NULL)
1364 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
1365 (void) ResetMagickMemory(list_info,0,sizeof(*list_info));
1366 list_info->capacity=capacity == 0 ? (size_t) (~0) : capacity;
1367 list_info->elements=0;
1368 list_info->head=(ElementInfo *) NULL;
1369 list_info->tail=(ElementInfo *) NULL;
1370 list_info->next=(ElementInfo *) NULL;
1371 list_info->semaphore=AcquireSemaphoreInfo();
1372 list_info->signature=MagickSignature;
1377 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1381 % P u t E n t r y I n H a s h m a p %
1385 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1387 % PutEntryInHashmap() puts an entry in the hash-map. If the key already
1388 % exists in the map it is first removed.
1390 % The format of the PutEntryInHashmap method is:
1392 % MagickBooleanType PutEntryInHashmap(HashmapInfo *hashmap_info,
1393 % const void *key,const void *value)
1395 % A description of each parameter follows:
1397 % o hashmap_info: the hashmap info.
1401 % o value: the value.
1405 static MagickBooleanType IncreaseHashmapCapacity(HashmapInfo *hashmap_info)
1407 #define MaxCapacities 20
1410 capacities[MaxCapacities] =
1412 17, 31, 61, 131, 257, 509, 1021, 2053, 4099, 8191, 16381, 32771,
1413 65537, 131071, 262147, 524287, 1048573, 2097143, 4194301, 8388617
1427 register ElementInfo
1437 Increase to the next prime capacity.
1439 for (i=0; i < MaxCapacities; i++)
1440 if (hashmap_info->capacity < capacities[i])
1442 if (i >= (MaxCapacities-1))
1443 return(MagickFalse);
1444 capacity=capacities[i+1];
1445 map=(LinkedListInfo **) AcquireQuantumMemory((size_t) capacity+1UL,
1447 if (map == (LinkedListInfo **) NULL)
1448 return(MagickFalse);
1449 (void) ResetMagickMemory(map,0,(size_t) capacity*sizeof(*map));
1451 Copy entries to new hashmap with increased capacity.
1453 for (i=0; i < (ssize_t) hashmap_info->capacity; i++)
1455 list_info=hashmap_info->map[i];
1456 if (list_info == (LinkedListInfo *) NULL)
1458 LockSemaphoreInfo(list_info->semaphore);
1459 for (next=list_info->head; next != (ElementInfo *) NULL; )
1463 entry=(EntryInfo *) element->value;
1464 map_info=map[entry->hash % capacity];
1465 if (map_info == (LinkedListInfo *) NULL)
1467 map_info=NewLinkedList(0);
1468 map[entry->hash % capacity]=map_info;
1470 map_info->next=element;
1471 element->next=map_info->head;
1472 map_info->head=element;
1473 map_info->elements++;
1475 list_info->signature=(~MagickSignature);
1476 UnlockSemaphoreInfo(list_info->semaphore);
1477 RelinquishSemaphoreInfo(&list_info->semaphore);
1478 list_info=(LinkedListInfo *) RelinquishMagickMemory(list_info);
1480 hashmap_info->map=(LinkedListInfo **) RelinquishMagickMemory(
1482 hashmap_info->map=map;
1483 hashmap_info->capacity=capacity;
1487 MagickExport MagickBooleanType PutEntryInHashmap(HashmapInfo *hashmap_info,
1488 const void *key,const void *value)
1500 assert(hashmap_info != (HashmapInfo *) NULL);
1501 assert(hashmap_info->signature == MagickSignature);
1502 if ((key == (void *) NULL) || (value == (void *) NULL))
1503 return(MagickFalse);
1504 next=(EntryInfo *) AcquireMagickMemory(sizeof(*next));
1505 if (next == (EntryInfo *) NULL)
1506 return(MagickFalse);
1507 LockSemaphoreInfo(hashmap_info->semaphore);
1508 next->hash=hashmap_info->hash(key);
1509 next->key=(void *) key;
1510 next->value=(void *) value;
1511 list_info=hashmap_info->map[next->hash % hashmap_info->capacity];
1512 if (list_info == (LinkedListInfo *) NULL)
1514 list_info=NewLinkedList(0);
1515 hashmap_info->map[next->hash % hashmap_info->capacity]=list_info;
1519 list_info->next=list_info->head;
1520 entry=(EntryInfo *) GetNextValueInLinkedList(list_info);
1521 for (i=0; entry != (EntryInfo *) NULL; i++)
1523 if (entry->hash == next->hash)
1529 if (hashmap_info->compare !=
1530 (MagickBooleanType (*)(const void *,const void *)) NULL)
1531 compare=hashmap_info->compare(key,entry->key);
1532 if( IfMagickTrue(compare) )
1534 (void) RemoveElementFromLinkedList(list_info,i);
1535 if (hashmap_info->relinquish_key != (void *(*)(void *)) NULL)
1536 entry->key=hashmap_info->relinquish_key(entry->key);
1537 if (hashmap_info->relinquish_value != (void *(*)(void *)) NULL)
1538 entry->value=hashmap_info->relinquish_value(entry->value);
1539 entry=(EntryInfo *) RelinquishMagickMemory(entry);
1543 entry=(EntryInfo *) GetNextValueInLinkedList(list_info);
1546 if (IfMagickFalse(InsertValueInLinkedList(list_info,0,next)))
1548 next=(EntryInfo *) RelinquishMagickMemory(next);
1549 UnlockSemaphoreInfo(hashmap_info->semaphore);
1550 return(MagickFalse);
1552 if (list_info->elements >= (hashmap_info->capacity-1))
1553 if (IfMagickFalse(IncreaseHashmapCapacity(hashmap_info)))
1555 UnlockSemaphoreInfo(hashmap_info->semaphore);
1556 return(MagickFalse);
1558 hashmap_info->entries++;
1559 UnlockSemaphoreInfo(hashmap_info->semaphore);
1564 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1568 % 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 %
1572 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1574 % RemoveElementByValueFromLinkedList() removes an element from the linked-list
1577 % The format of the RemoveElementByValueFromLinkedList method is:
1579 % void *RemoveElementByValueFromLinkedList(LinkedListInfo *list_info,
1580 % const void *value)
1582 % A description of each parameter follows:
1584 % o list_info: the list info.
1586 % o value: the value.
1589 MagickExport void *RemoveElementByValueFromLinkedList(LinkedListInfo *list_info,
1595 assert(list_info != (LinkedListInfo *) NULL);
1596 assert(list_info->signature == MagickSignature);
1597 if ((list_info->elements == 0) || (value == (const void *) NULL))
1598 return((void *) NULL);
1599 LockSemaphoreInfo(list_info->semaphore);
1600 if (value == list_info->head->value)
1602 if (list_info->next == list_info->head)
1603 list_info->next=list_info->head->next;
1604 next=list_info->head;
1605 list_info->head=list_info->head->next;
1606 next=(ElementInfo *) RelinquishMagickMemory(next);
1613 next=list_info->head;
1614 while ((next->next != (ElementInfo *) NULL) &&
1615 (next->next->value != value))
1617 if (next->next == (ElementInfo *) NULL)
1619 UnlockSemaphoreInfo(list_info->semaphore);
1620 return((void *) NULL);
1623 next->next=element->next;
1624 if (element == list_info->tail)
1625 list_info->tail=next;
1626 if (list_info->next == element)
1627 list_info->next=element->next;
1628 element=(ElementInfo *) RelinquishMagickMemory(element);
1630 list_info->elements--;
1631 UnlockSemaphoreInfo(list_info->semaphore);
1632 return((void *) value);
1636 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1640 % 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 %
1644 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1646 % RemoveElementFromLinkedList() removes an element from the linked-list at the
1647 % specified location.
1649 % The format of the RemoveElementFromLinkedList method is:
1651 % void *RemoveElementFromLinkedList(LinkedListInfo *list_info,
1652 % const size_t index)
1654 % A description of each parameter follows:
1656 % o list_info: the linked-list info.
1658 % o index: the index.
1661 MagickExport void *RemoveElementFromLinkedList(LinkedListInfo *list_info,
1673 assert(list_info != (LinkedListInfo *) NULL);
1674 assert(list_info->signature == MagickSignature);
1675 if (index >= list_info->elements)
1676 return((void *) NULL);
1677 LockSemaphoreInfo(list_info->semaphore);
1680 if (list_info->next == list_info->head)
1681 list_info->next=list_info->head->next;
1682 value=list_info->head->value;
1683 next=list_info->head;
1684 list_info->head=list_info->head->next;
1685 next=(ElementInfo *) RelinquishMagickMemory(next);
1692 next=list_info->head;
1693 for (i=1; i < (ssize_t) index; i++)
1696 next->next=element->next;
1697 if (element == list_info->tail)
1698 list_info->tail=next;
1699 if (list_info->next == element)
1700 list_info->next=element->next;
1701 value=element->value;
1702 element=(ElementInfo *) RelinquishMagickMemory(element);
1704 list_info->elements--;
1705 UnlockSemaphoreInfo(list_info->semaphore);
1710 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1714 % R e m o v e E n t r y F r o m H a s h m a p %
1718 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1720 % RemoveEntryFromHashmap() removes an entry from the hash-map by its key.
1722 % The format of the RemoveEntryFromHashmap method is:
1724 % void *RemoveEntryFromHashmap(HashmapInfo *hashmap_info,void *key)
1726 % A description of each parameter follows:
1728 % o hashmap_info: the hashmap info.
1733 MagickExport void *RemoveEntryFromHashmap(HashmapInfo *hashmap_info,
1751 assert(hashmap_info != (HashmapInfo *) NULL);
1752 assert(hashmap_info->signature == MagickSignature);
1753 if (key == (const void *) NULL)
1754 return((void *) NULL);
1755 LockSemaphoreInfo(hashmap_info->semaphore);
1756 hash=hashmap_info->hash(key);
1757 list_info=hashmap_info->map[hash % hashmap_info->capacity];
1758 if (list_info != (LinkedListInfo *) NULL)
1760 list_info->next=list_info->head;
1761 entry=(EntryInfo *) GetNextValueInLinkedList(list_info);
1762 for (i=0; entry != (EntryInfo *) NULL; i++)
1764 if (entry->hash == hash)
1770 if (hashmap_info->compare !=
1771 (MagickBooleanType (*)(const void *,const void *)) NULL)
1772 compare=hashmap_info->compare(key,entry->key);
1773 if( IfMagickTrue(compare) )
1775 entry=(EntryInfo *) RemoveElementFromLinkedList(list_info,i);
1776 if (entry == (EntryInfo *) NULL)
1778 UnlockSemaphoreInfo(hashmap_info->semaphore);
1779 return((void *) NULL);
1781 if (hashmap_info->relinquish_key != (void *(*)(void *)) NULL)
1782 entry->key=hashmap_info->relinquish_key(entry->key);
1784 entry=(EntryInfo *) RelinquishMagickMemory(entry);
1785 hashmap_info->entries--;
1786 UnlockSemaphoreInfo(hashmap_info->semaphore);
1790 entry=(EntryInfo *) GetNextValueInLinkedList(list_info);
1793 UnlockSemaphoreInfo(hashmap_info->semaphore);
1794 return((void *) NULL);
1798 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1802 % 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 %
1806 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1808 % RemoveLastElementFromLinkedList() removes the last element from the
1811 % The format of the RemoveLastElementFromLinkedList method is:
1813 % void *RemoveLastElementFromLinkedList(LinkedListInfo *list_info)
1815 % A description of each parameter follows:
1817 % o list_info: the linked-list info.
1820 MagickExport void *RemoveLastElementFromLinkedList(LinkedListInfo *list_info)
1825 assert(list_info != (LinkedListInfo *) NULL);
1826 assert(list_info->signature == MagickSignature);
1827 if (list_info->elements == 0)
1828 return((void *) NULL);
1829 LockSemaphoreInfo(list_info->semaphore);
1830 if (list_info->next == list_info->tail)
1831 list_info->next=(ElementInfo *) NULL;
1832 if (list_info->elements == 1UL)
1834 value=list_info->head->value;
1835 list_info->head=(ElementInfo *) NULL;
1836 list_info->tail=(ElementInfo *) RelinquishMagickMemory(list_info->tail);
1843 value=list_info->tail->value;
1844 next=list_info->head;
1845 while (next->next != list_info->tail)
1847 list_info->tail=(ElementInfo *) RelinquishMagickMemory(list_info->tail);
1848 list_info->tail=next;
1849 next->next=(ElementInfo *) NULL;
1851 list_info->elements--;
1852 UnlockSemaphoreInfo(list_info->semaphore);
1857 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1861 % R e s e t H a s h m a p I t e r a t o r %
1865 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1867 % ResetHashmapIterator() resets the hash-map iterator. Use it in conjunction
1868 % with GetNextKeyInHashmap() to iterate over all the keys in the hash-map.
1870 % The format of the ResetHashmapIterator method is:
1872 % ResetHashmapIterator(HashmapInfo *hashmap_info)
1874 % A description of each parameter follows:
1876 % o hashmap_info: the hashmap info.
1879 MagickExport void ResetHashmapIterator(HashmapInfo *hashmap_info)
1881 assert(hashmap_info != (HashmapInfo *) NULL);
1882 assert(hashmap_info->signature == MagickSignature);
1883 LockSemaphoreInfo(hashmap_info->semaphore);
1884 hashmap_info->next=0;
1885 hashmap_info->head_of_list=MagickFalse;
1886 UnlockSemaphoreInfo(hashmap_info->semaphore);
1890 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1894 % R e s e t L i n k e d L i s t I t e r a t o r %
1898 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1900 % ResetLinkedListIterator() resets the lined-list iterator. Use it in
1901 % conjunction with GetNextValueInLinkedList() to iterate over all the values
1902 % in the linked-list.
1904 % The format of the ResetLinkedListIterator method is:
1906 % ResetLinkedListIterator(LinkedListInfo *list_info)
1908 % A description of each parameter follows:
1910 % o list_info: the linked-list info.
1913 MagickExport void ResetLinkedListIterator(LinkedListInfo *list_info)
1915 assert(list_info != (LinkedListInfo *) NULL);
1916 assert(list_info->signature == MagickSignature);
1917 LockSemaphoreInfo(list_info->semaphore);
1918 list_info->next=list_info->head;
1919 UnlockSemaphoreInfo(list_info->semaphore);