/* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % % % % % H H AAA SSSSS H H M M AAA PPPP % % H H A A SS H H MM MM A A P P % % HHHHH AAAAA SSS HHHHH M M M AAAAA PPPP % % H H A A SS H H M M A A P % % H H A A SSSSS H H M M A A P % % % % % % MagickCore Hash-map and Linked-list Methods % % % % Software Design % % Cristy % % December 2002 % % % % % % Copyright 1999-2014 ImageMagick Studio LLC, a non-profit organization % % dedicated to making software imaging solutions freely available. % % % % You may not use this file except in compliance with the License. You may % % obtain a copy of the License at % % % % http://www.imagemagick.org/script/license.php % % % % Unless required by applicable law or agreed to in writing, software % % distributed under the License is distributed on an "AS IS" BASIS, % % WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. % % See the License for the specific language governing permissions and % % limitations under the License. % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % This module implements the standard handy hash and linked-list methods for % storing and retrieving large numbers of data elements. It is loosely based % on the Java implementation of these algorithms. % */ /* Include declarations. */ #include "MagickCore/studio.h" #include "MagickCore/exception.h" #include "MagickCore/exception-private.h" #include "MagickCore/hashmap.h" #include "MagickCore/memory_.h" #include "MagickCore/semaphore.h" #include "MagickCore/signature-private.h" #include "MagickCore/string_.h" /* Typedef declarations. */ typedef struct _ElementInfo { void *value; struct _ElementInfo *next; } ElementInfo; typedef struct _EntryInfo { size_t hash; void *key, *value; } EntryInfo; struct _LinkedListInfo { size_t capacity, elements; ElementInfo *head, *tail, *next; SemaphoreInfo *semaphore; size_t signature; }; struct _HashmapInfo { size_t (*hash)(const void *); MagickBooleanType (*compare)(const void *,const void *); void *(*relinquish_key)(void *), *(*relinquish_value)(void *); size_t capacity, entries, next; MagickBooleanType head_of_list; LinkedListInfo **map; SemaphoreInfo *semaphore; size_t signature; }; /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % % % % % A p p e n d V a l u e T o L i n k e d L i s t % % % % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % AppendValueToLinkedList() appends a value to the end of the linked-list. % % The format of the AppendValueToLinkedList method is: % % MagickBooleanType AppendValueToLinkedList(LinkedListInfo *list_info, % const void *value) % % A description of each parameter follows: % % o list_info: the linked-list info. % % o value: the value. % */ MagickExport MagickBooleanType AppendValueToLinkedList( LinkedListInfo *list_info,const void *value) { register ElementInfo *next; assert(list_info != (LinkedListInfo *) NULL); assert(list_info->signature == MagickSignature); if (list_info->elements == list_info->capacity) return(MagickFalse); next=(ElementInfo *) AcquireMagickMemory(sizeof(*next)); if (next == (ElementInfo *) NULL) return(MagickFalse); next->value=(void *) value; next->next=(ElementInfo *) NULL; LockSemaphoreInfo(list_info->semaphore); if (list_info->next == (ElementInfo *) NULL) list_info->next=next; if (list_info->elements == 0) list_info->head=next; else list_info->tail->next=next; list_info->tail=next; list_info->elements++; UnlockSemaphoreInfo(list_info->semaphore); return(MagickTrue); } /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % % % % % C l e a r L i n k e d L i s t % % % % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % ClearLinkedList() clears all the elements from the linked-list. % % The format of the ClearLinkedList method is: % % void ClearLinkedList(LinkedListInfo *list_info, % void *(*relinquish_value)(void *)) % % A description of each parameter follows: % % o list_info: the linked-list info. % % o relinquish_value: the value deallocation method; typically % RelinquishMagickMemory(). % */ MagickExport void ClearLinkedList(LinkedListInfo *list_info, void *(*relinquish_value)(void *)) { ElementInfo *element; register ElementInfo *next; assert(list_info != (LinkedListInfo *) NULL); assert(list_info->signature == MagickSignature); LockSemaphoreInfo(list_info->semaphore); next=list_info->head; while (next != (ElementInfo *) NULL) { if (relinquish_value != (void *(*)(void *)) NULL) next->value=relinquish_value(next->value); element=next; next=next->next; element=(ElementInfo *) RelinquishMagickMemory(element); } list_info->head=(ElementInfo *) NULL; list_info->tail=(ElementInfo *) NULL; list_info->next=(ElementInfo *) NULL; list_info->elements=0; UnlockSemaphoreInfo(list_info->semaphore); } /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % % % % % C o m p a r e H a s h m a p S t r i n g % % % % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % CompareHashmapString() finds an entry in a hash-map based on the contents % of a string. % % The format of the CompareHashmapString method is: % % MagickBooleanType CompareHashmapString(const void *target, % const void *source) % % A description of each parameter follows: % % o target: the target string. % % o source: the source string. % */ MagickExport MagickBooleanType CompareHashmapString(const void *target, const void *source) { const char *p, *q; p=(const char *) target; q=(const char *) source; return(IsMagickTrue(LocaleCompare(p,q))); } /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % % % % % C o m p a r e H a s h m a p S t r i n g I n f o % % % % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % CompareHashmapStringInfo() finds an entry in a hash-map based on the % contents of a string. % % The format of the CompareHashmapStringInfo method is: % % MagickBooleanType CompareHashmapStringInfo(const void *target, % const void *source) % % A description of each parameter follows: % % o target: the target string. % % o source: the source string. % */ MagickExport MagickBooleanType CompareHashmapStringInfo(const void *target, const void *source) { return(IsMagickTrue(LocaleCompare((const char *)target, (const char *)source))); } /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % % % % % D e s t r o y H a s h m a p % % % % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % DestroyHashmap() frees the hash-map and all associated resources. % % The format of the DestroyHashmap method is: % % HashmapInfo *DestroyHashmap(HashmapInfo *hashmap_info) % % A description of each parameter follows: % % o hashmap_info: the hashmap info. % */ MagickExport HashmapInfo *DestroyHashmap(HashmapInfo *hashmap_info) { LinkedListInfo *list_info; register EntryInfo *entry; register ssize_t i; assert(hashmap_info != (HashmapInfo *) NULL); assert(hashmap_info->signature == MagickSignature); LockSemaphoreInfo(hashmap_info->semaphore); for (i=0; i < (ssize_t) hashmap_info->capacity; i++) { list_info=hashmap_info->map[i]; if (list_info != (LinkedListInfo *) NULL) { list_info->next=list_info->head; entry=(EntryInfo *) GetNextValueInLinkedList(list_info); while (entry != (EntryInfo *) NULL) { if (hashmap_info->relinquish_key != (void *(*)(void *)) NULL) entry->key=hashmap_info->relinquish_key(entry->key); if (hashmap_info->relinquish_value != (void *(*)(void *)) NULL) entry->value=hashmap_info->relinquish_value(entry->value); entry=(EntryInfo *) GetNextValueInLinkedList(list_info); } } if (list_info != (LinkedListInfo *) NULL) list_info=DestroyLinkedList(list_info,RelinquishMagickMemory); } hashmap_info->map=(LinkedListInfo **) RelinquishMagickMemory( hashmap_info->map); hashmap_info->signature=(~MagickSignature); UnlockSemaphoreInfo(hashmap_info->semaphore); RelinquishSemaphoreInfo(&hashmap_info->semaphore); hashmap_info=(HashmapInfo *) RelinquishMagickMemory(hashmap_info); return(hashmap_info); } /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % % % % % D e s t r o y L i n k e d L i s t % % % % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % DestroyLinkedList() frees the linked-list and all associated resources. % % The format of the DestroyLinkedList method is: % % LinkedListInfo *DestroyLinkedList(LinkedListInfo *list_info, % void *(*relinquish_value)(void *)) % % A description of each parameter follows: % % o list_info: the linked-list info. % % o relinquish_value: the value deallocation method; typically % RelinquishMagickMemory(). % */ MagickExport LinkedListInfo *DestroyLinkedList(LinkedListInfo *list_info, void *(*relinquish_value)(void *)) { ElementInfo *entry; register ElementInfo *next; assert(list_info != (LinkedListInfo *) NULL); assert(list_info->signature == MagickSignature); LockSemaphoreInfo(list_info->semaphore); for (next=list_info->head; next != (ElementInfo *) NULL; ) { if (relinquish_value != (void *(*)(void *)) NULL) next->value=relinquish_value(next->value); entry=next; next=next->next; entry=(ElementInfo *) RelinquishMagickMemory(entry); } list_info->signature=(~MagickSignature); UnlockSemaphoreInfo(list_info->semaphore); RelinquishSemaphoreInfo(&list_info->semaphore); list_info=(LinkedListInfo *) RelinquishMagickMemory(list_info); return(list_info); } /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % % % % % G e t L a s t V a l u e I n L i n k e d L i s t % % % % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % GetLastValueInLinkedList() gets the last value in the linked-list. % % The format of the GetLastValueInLinkedList method is: % % void *GetLastValueInLinkedList(LinkedListInfo *list_info) % % A description of each parameter follows: % % o list_info: the linked_list info. % */ MagickExport void *GetLastValueInLinkedList(LinkedListInfo *list_info) { void *value; assert(list_info != (LinkedListInfo *) NULL); assert(list_info->signature == MagickSignature); if (list_info->elements == 0) return((void *) NULL); LockSemaphoreInfo(list_info->semaphore); value=list_info->tail->value; UnlockSemaphoreInfo(list_info->semaphore); return(value); } /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % % % % % G e t N e x t K e y I n H a s h m a p % % % % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % GetNextKeyInHashmap() gets the next key in the hash-map. % % The format of the GetNextKeyInHashmap method is: % % void *GetNextKeyInHashmap(HashmapInfo *hashmap_info) % % A description of each parameter follows: % % o hashmap_info: the hashmap info. % */ MagickExport void *GetNextKeyInHashmap(HashmapInfo *hashmap_info) { LinkedListInfo *list_info; register EntryInfo *entry; void *key; assert(hashmap_info != (HashmapInfo *) NULL); assert(hashmap_info->signature == MagickSignature); LockSemaphoreInfo(hashmap_info->semaphore); while (hashmap_info->next < hashmap_info->capacity) { list_info=hashmap_info->map[hashmap_info->next]; if (list_info != (LinkedListInfo *) NULL) { if (IfMagickFalse(hashmap_info->head_of_list)) { list_info->next=list_info->head; hashmap_info->head_of_list=MagickTrue; } entry=(EntryInfo *) GetNextValueInLinkedList(list_info); if (entry != (EntryInfo *) NULL) { key=entry->key; UnlockSemaphoreInfo(hashmap_info->semaphore); return(key); } hashmap_info->head_of_list=MagickFalse; } hashmap_info->next++; } UnlockSemaphoreInfo(hashmap_info->semaphore); return((void *) NULL); } /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % % % % % G e t N e x t V a l u e I n H a s h m a p % % % % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % GetNextValueInHashmap() gets the next value in the hash-map. % % The format of the GetNextValueInHashmap method is: % % void *GetNextValueInHashmap(HashmapInfo *hashmap_info) % % A description of each parameter follows: % % o hashmap_info: the hashmap info. % */ MagickExport void *GetNextValueInHashmap(HashmapInfo *hashmap_info) { LinkedListInfo *list_info; register EntryInfo *entry; void *value; assert(hashmap_info != (HashmapInfo *) NULL); assert(hashmap_info->signature == MagickSignature); LockSemaphoreInfo(hashmap_info->semaphore); while (hashmap_info->next < hashmap_info->capacity) { list_info=hashmap_info->map[hashmap_info->next]; if (list_info != (LinkedListInfo *) NULL) { if (IfMagickFalse(hashmap_info->head_of_list)) { list_info->next=list_info->head; hashmap_info->head_of_list=MagickTrue; } entry=(EntryInfo *) GetNextValueInLinkedList(list_info); if (entry != (EntryInfo *) NULL) { value=entry->value; UnlockSemaphoreInfo(hashmap_info->semaphore); return(value); } hashmap_info->head_of_list=MagickFalse; } hashmap_info->next++; } UnlockSemaphoreInfo(hashmap_info->semaphore); return((void *) NULL); } /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % % % % % G e t N e x t V a l u e I n L i n k e d L i s t % % % % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % GetNextValueInLinkedList() gets the next value in the linked-list. % % The format of the GetNextValueInLinkedList method is: % % void *GetNextValueInLinkedList(LinkedListInfo *list_info) % % A description of each parameter follows: % % o list_info: the linked-list info. % */ MagickExport void *GetNextValueInLinkedList(LinkedListInfo *list_info) { void *value; assert(list_info != (LinkedListInfo *) NULL); assert(list_info->signature == MagickSignature); LockSemaphoreInfo(list_info->semaphore); if (list_info->next == (ElementInfo *) NULL) { UnlockSemaphoreInfo(list_info->semaphore); return((void *) NULL); } value=list_info->next->value; list_info->next=list_info->next->next; UnlockSemaphoreInfo(list_info->semaphore); return(value); } /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % % % % % 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 % % % % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % GetNumberOfEntriesInHashmap() returns the number of entries in the hash-map. % % The format of the GetNumberOfEntriesInHashmap method is: % % size_t GetNumberOfEntriesInHashmap(const HashmapInfo *hashmap_info) % % A description of each parameter follows: % % o hashmap_info: the hashmap info. % */ MagickExport size_t GetNumberOfEntriesInHashmap( const HashmapInfo *hashmap_info) { assert(hashmap_info != (HashmapInfo *) NULL); assert(hashmap_info->signature == MagickSignature); return(hashmap_info->entries); } /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % % % % % 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 % % % % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % GetNumberOfElementsInLinkedList() returns the number of entries in the % linked-list. % % The format of the GetNumberOfElementsInLinkedList method is: % % size_t GetNumberOfElementsInLinkedList( % const LinkedListInfo *list_info) % % A description of each parameter follows: % % o list_info: the linked-list info. % */ MagickExport size_t GetNumberOfElementsInLinkedList( const LinkedListInfo *list_info) { assert(list_info != (LinkedListInfo *) NULL); assert(list_info->signature == MagickSignature); return(list_info->elements); } /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % % % % % G e t V a l u e F r o m H a s h m a p % % % % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % GetValueFromHashmap() gets an entry from the hash-map by its key. % % The format of the GetValueFromHashmap method is: % % void *GetValueFromHashmap(HashmapInfo *hashmap_info,const void *key) % % A description of each parameter follows: % % o hashmap_info: the hashmap info. % % o key: the key. % */ MagickExport void *GetValueFromHashmap(HashmapInfo *hashmap_info, const void *key) { LinkedListInfo *list_info; register EntryInfo *entry; size_t hash; void *value; assert(hashmap_info != (HashmapInfo *) NULL); assert(hashmap_info->signature == MagickSignature); if (key == (const void *) NULL) return((void *) NULL); LockSemaphoreInfo(hashmap_info->semaphore); hash=hashmap_info->hash(key); list_info=hashmap_info->map[hash % hashmap_info->capacity]; if (list_info != (LinkedListInfo *) NULL) { list_info->next=list_info->head; entry=(EntryInfo *) GetNextValueInLinkedList(list_info); while (entry != (EntryInfo *) NULL) { if (entry->hash == hash) { MagickBooleanType compare; compare=MagickTrue; if (hashmap_info->compare != (MagickBooleanType (*)(const void *,const void *)) NULL) compare=hashmap_info->compare(key,entry->key); if (IfMagickTrue(compare)) { value=entry->value; UnlockSemaphoreInfo(hashmap_info->semaphore); return(value); } } entry=(EntryInfo *) GetNextValueInLinkedList(list_info); } } UnlockSemaphoreInfo(hashmap_info->semaphore); return((void *) NULL); } /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % % % % % G e t V a l u e F r o m L i n k e d L i s t % % % % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % GetValueFromLinkedList() gets a value from the linked-list at the specified % location. % % The format of the GetValueFromLinkedList method is: % % void *GetValueFromLinkedList(LinkedListInfo *list_info, % const size_t index) % % A description of each parameter follows: % % o list_info: the linked_list info. % % o index: the list index. % */ MagickExport void *GetValueFromLinkedList(LinkedListInfo *list_info, const size_t index) { register ElementInfo *next; register ssize_t i; void *value; assert(list_info != (LinkedListInfo *) NULL); assert(list_info->signature == MagickSignature); if (index >= list_info->elements) return((void *) NULL); LockSemaphoreInfo(list_info->semaphore); if (index == 0) { value=list_info->head->value; UnlockSemaphoreInfo(list_info->semaphore); return(value); } if (index == (list_info->elements-1)) { value=list_info->tail->value; UnlockSemaphoreInfo(list_info->semaphore); return(value); } next=list_info->head; for (i=0; i < (ssize_t) index; i++) next=next->next; value=next->value; UnlockSemaphoreInfo(list_info->semaphore); return(value); } /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % % % % % H a s h P o i n t e r T y p e % % % % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % HashPointerType() finds an entry in a hash-map based on the address of a % pointer. % % The format of the HashPointerType method is: % % size_t HashPointerType(const void *pointer) % % A description of each parameter follows: % % o pointer: compute the hash entry location from this pointer address. % */ MagickExport size_t HashPointerType(const void *pointer) { size_t hash; hash=(size_t) pointer; hash+=(~(hash << 9)); hash^=(hash >> 14); hash+=(hash << 4); hash^=(hash >> 10); return(hash); } /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % % % % % H a s h S t r i n g T y p e % % % % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % HashStringType() finds an entry in a hash-map based on the contents of a % string. % % The format of the HashStringType method is: % % size_t HashStringType(const void *string) % % A description of each parameter follows: % % o string: compute the hash entry location from this string. % */ MagickExport size_t HashStringType(const void *string) { const unsigned char *digest; register ssize_t i; SignatureInfo *signature_info; size_t hash; StringInfo *signature; signature_info=AcquireSignatureInfo(); signature=StringToStringInfo((const char *) string); UpdateSignature(signature_info,signature); FinalizeSignature(signature_info); digest=GetStringInfoDatum(GetSignatureDigest(signature_info)); hash=0; for (i=0; i < 8; i++) hash^=digest[i]; signature=DestroyStringInfo(signature); signature_info=DestroySignatureInfo(signature_info); return(hash); } /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % % % % % H a s h S t r i n g I n f o T y p e % % % % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % Specify the HashStringInfoType() method in NewHashmap() to find an entry % in a hash-map based on the contents of a string. % % The format of the HashStringInfoType method is: % % size_t HashStringInfoType(const void *string_info) % % A description of each parameter follows: % % o string_info: compute the hash entry location from this string. % */ MagickExport size_t HashStringInfoType(const void *string_info) { const unsigned char *digest; register ssize_t i; SignatureInfo *signature_info; size_t hash; signature_info=AcquireSignatureInfo(); UpdateSignature(signature_info,(const StringInfo *) string_info); FinalizeSignature(signature_info); digest=GetStringInfoDatum(GetSignatureDigest(signature_info)); hash=0; for (i=0; i < 8; i++) hash^=digest[i]; signature_info=DestroySignatureInfo(signature_info); return(hash); } /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % % % % % I n s e r t V a l u e I n L i n k e d L i s t % % % % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % InsertValueInLinkedList() inserts an element in the linked-list at the % specified location. % % The format of the InsertValueInLinkedList method is: % % MagickBooleanType InsertValueInLinkedList(ListInfo *list_info, % const size_t index,const void *value) % % A description of each parameter follows: % % o list_info: the hashmap info. % % o index: the index. % % o value: the value. % */ MagickExport MagickBooleanType InsertValueInLinkedList( LinkedListInfo *list_info,const size_t index,const void *value) { register ElementInfo *next; register ssize_t i; assert(list_info != (LinkedListInfo *) NULL); assert(list_info->signature == MagickSignature); if (value == (const void *) NULL) return(MagickFalse); if ((index > list_info->elements) || (list_info->elements == list_info->capacity)) return(MagickFalse); next=(ElementInfo *) AcquireMagickMemory(sizeof(*next)); if (next == (ElementInfo *) NULL) return(MagickFalse); next->value=(void *) value; next->next=(ElementInfo *) NULL; LockSemaphoreInfo(list_info->semaphore); if (list_info->elements == 0) { if (list_info->next == (ElementInfo *) NULL) list_info->next=next; list_info->head=next; list_info->tail=next; } else { if (index == 0) { if (list_info->next == list_info->head) list_info->next=next; next->next=list_info->head; list_info->head=next; } else if (index == list_info->elements) { if (list_info->next == (ElementInfo *) NULL) list_info->next=next; list_info->tail->next=next; list_info->tail=next; } else { ElementInfo *element; element=list_info->head; next->next=element->next; for (i=1; i < (ssize_t) index; i++) { element=element->next; next->next=element->next; } next=next->next; element->next=next; if (list_info->next == next->next) list_info->next=next; } } list_info->elements++; UnlockSemaphoreInfo(list_info->semaphore); return(MagickTrue); } /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % % % % % 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 % % % % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % InsertValueInSortedLinkedList() inserts a value in the sorted linked-list. % % The format of the InsertValueInSortedLinkedList method is: % % MagickBooleanType InsertValueInSortedLinkedList(ListInfo *list_info, % int (*compare)(const void *,const void *),void **replace, % const void *value) % % A description of each parameter follows: % % o list_info: the hashmap info. % % o index: the index. % % o compare: the compare method. % % o replace: return previous element here. % % o value: the value. % */ MagickExport MagickBooleanType InsertValueInSortedLinkedList( LinkedListInfo *list_info,int (*compare)(const void *,const void *), void **replace,const void *value) { ElementInfo *element; register ElementInfo *next; register ssize_t i; assert(list_info != (LinkedListInfo *) NULL); assert(list_info->signature == MagickSignature); if ((compare == (int (*)(const void *,const void *)) NULL) || (value == (const void *) NULL)) return(MagickFalse); if (list_info->elements == list_info->capacity) return(MagickFalse); next=(ElementInfo *) AcquireMagickMemory(sizeof(*next)); if (next == (ElementInfo *) NULL) return(MagickFalse); next->value=(void *) value; element=(ElementInfo *) NULL; LockSemaphoreInfo(list_info->semaphore); next->next=list_info->head; while (next->next != (ElementInfo *) NULL) { i=(ssize_t) compare(value,next->next->value); if ((i < 0) || ((replace != (void **) NULL) && (i == 0))) { if (i == 0) { *replace=next->next->value; next->next=next->next->next; if (element != (ElementInfo *) NULL) element->next=(ElementInfo *) RelinquishMagickMemory( element->next); list_info->elements--; } if (element != (ElementInfo *) NULL) element->next=next; else list_info->head=next; break; } element=next->next; next->next=next->next->next; } if (next->next == (ElementInfo *) NULL) { if (element != (ElementInfo *) NULL) element->next=next; else list_info->head=next; list_info->tail=next; } list_info->elements++; UnlockSemaphoreInfo(list_info->semaphore); return(MagickTrue); } /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % % % % % I s H a s h m a p E m p t y % % % % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % IsHashmapEmpty() returns MagickTrue if the hash-map is empty. % % The format of the IsHashmapEmpty method is: % % MagickBooleanType IsHashmapEmpty(const HashmapInfo *hashmap_info) % % A description of each parameter follows: % % o hashmap_info: the hashmap info. % */ MagickExport MagickBooleanType IsHashmapEmpty(const HashmapInfo *hashmap_info) { assert(hashmap_info != (HashmapInfo *) NULL); assert(hashmap_info->signature == MagickSignature); return(IsMagickTrue(hashmap_info->entries == 0)); } /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % % % % % I s L i n k e d L i s t E m p t y % % % % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % IsLinkedListEmpty() returns MagickTrue if the linked-list is empty. % % The format of the IsLinkedListEmpty method is: % % MagickBooleanType IsLinkedListEmpty(LinkedListInfo *list_info) % % A description of each parameter follows: % % o list_info: the linked-list info. % */ MagickExport MagickBooleanType IsLinkedListEmpty( const LinkedListInfo *list_info) { assert(list_info != (LinkedListInfo *) NULL); assert(list_info->signature == MagickSignature); return(IsMagickTrue(list_info->elements == 0)); } /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % % % % % L i n k e d L i s t T o A r r a y % % % % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % LinkedListToArray() converts the linked-list to an array. % % The format of the LinkedListToArray method is: % % MagickBooleanType LinkedListToArray(LinkedListInfo *list_info, % void **array) % % A description of each parameter follows: % % o list_info: the linked-list info. % % o array: the array. % */ MagickExport MagickBooleanType LinkedListToArray(LinkedListInfo *list_info, void **array) { register ElementInfo *next; register ssize_t i; assert(list_info != (LinkedListInfo *) NULL); assert(list_info->signature == MagickSignature); if (array == (void **) NULL) return(MagickFalse); LockSemaphoreInfo(list_info->semaphore); next=list_info->head; for (i=0; next != (ElementInfo *) NULL; i++) { array[i]=next->value; next=next->next; } UnlockSemaphoreInfo(list_info->semaphore); return(MagickTrue); } /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % % % % % N e w H a s h m a p % % % % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % NewHashmap() returns a pointer to a HashmapInfo structure initialized % to default values. The capacity is an initial estimate. The hashmap will % increase capacity dynamically as the demand requires. % % The format of the NewHashmap method is: % % HashmapInfo *NewHashmap(const size_t capacity, % size_t (*hash)(const void *), % MagickBooleanType (*compare)(const void *,const void *), % void *(*relinquish_key)(void *),void *(*relinquish_value)(void *)) % % A description of each parameter follows: % % o capacity: the initial number entries in the hash-map: typically % SmallHashmapSize, MediumHashmapSize, or LargeHashmapSize. The % hashmap will dynamically increase its capacity on demand. % % o hash: the hash method, typically HashPointerType(), HashStringType(), % or HashStringInfoType(). % % o compare: the compare method, typically NULL, CompareHashmapString(), % or CompareHashmapStringInfo(). % % o relinquish_key: the key deallocation method, typically % RelinquishMagickMemory(), called whenever a key is removed from the % hash-map. % % o relinquish_value: the value deallocation method; typically % RelinquishMagickMemory(), called whenever a value object is removed from % the hash-map. % */ MagickExport HashmapInfo *NewHashmap(const size_t capacity, size_t (*hash)(const void *), MagickBooleanType (*compare)(const void *,const void *), void *(*relinquish_key)(void *),void *(*relinquish_value)(void *)) { HashmapInfo *hashmap_info; hashmap_info=(HashmapInfo *) AcquireMagickMemory(sizeof(*hashmap_info)); if (hashmap_info == (HashmapInfo *) NULL) ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed"); (void) ResetMagickMemory(hashmap_info,0,sizeof(*hashmap_info)); hashmap_info->hash=HashPointerType; if (hash != (size_t (*)(const void *)) NULL) hashmap_info->hash=hash; hashmap_info->compare=(MagickBooleanType (*)(const void *,const void *)) NULL; if (compare != (MagickBooleanType (*)(const void *,const void *)) NULL) hashmap_info->compare=compare; hashmap_info->relinquish_key=relinquish_key; hashmap_info->relinquish_value=relinquish_value; hashmap_info->entries=0; hashmap_info->capacity=capacity; hashmap_info->map=(LinkedListInfo **) NULL; if (~capacity >= 1UL) hashmap_info->map=(LinkedListInfo **) AcquireQuantumMemory((size_t) capacity+1UL,sizeof(*hashmap_info->map)); if (hashmap_info->map == (LinkedListInfo **) NULL) ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed"); (void) ResetMagickMemory(hashmap_info->map,0,(size_t) capacity* sizeof(*hashmap_info->map)); hashmap_info->semaphore=AcquireSemaphoreInfo(); hashmap_info->signature=MagickSignature; return(hashmap_info); } /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % % % % % N e w L i n k e d L i s t I n f o % % % % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % NewLinkedList() returns a pointer to a LinkedListInfo structure % initialized to default values. % % The format of the NewLinkedList method is: % % LinkedListInfo *NewLinkedList(const size_t capacity) % % A description of each parameter follows: % % o capacity: the maximum number of elements in the list. % */ MagickExport LinkedListInfo *NewLinkedList(const size_t capacity) { LinkedListInfo *list_info; list_info=(LinkedListInfo *) AcquireMagickMemory(sizeof(*list_info)); if (list_info == (LinkedListInfo *) NULL) ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed"); (void) ResetMagickMemory(list_info,0,sizeof(*list_info)); list_info->capacity=capacity == 0 ? (size_t) (~0) : capacity; list_info->elements=0; list_info->head=(ElementInfo *) NULL; list_info->tail=(ElementInfo *) NULL; list_info->next=(ElementInfo *) NULL; list_info->semaphore=AcquireSemaphoreInfo(); list_info->signature=MagickSignature; return(list_info); } /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % % % % % P u t E n t r y I n H a s h m a p % % % % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % PutEntryInHashmap() puts an entry in the hash-map. If the key already % exists in the map it is first removed. % % The format of the PutEntryInHashmap method is: % % MagickBooleanType PutEntryInHashmap(HashmapInfo *hashmap_info, % const void *key,const void *value) % % A description of each parameter follows: % % o hashmap_info: the hashmap info. % % o key: the key. % % o value: the value. % */ static MagickBooleanType IncreaseHashmapCapacity(HashmapInfo *hashmap_info) { #define MaxCapacities 20 const size_t capacities[MaxCapacities] = { 17, 31, 61, 131, 257, 509, 1021, 2053, 4099, 8191, 16381, 32771, 65537, 131071, 262147, 524287, 1048573, 2097143, 4194301, 8388617 }; ElementInfo *element; EntryInfo *entry; LinkedListInfo *list_info, *map_info, **map; register ElementInfo *next; register ssize_t i; size_t capacity; /* Increase to the next prime capacity. */ for (i=0; i < MaxCapacities; i++) if (hashmap_info->capacity < capacities[i]) break; if (i >= (MaxCapacities-1)) return(MagickFalse); capacity=capacities[i+1]; map=(LinkedListInfo **) AcquireQuantumMemory((size_t) capacity+1UL, sizeof(*map)); if (map == (LinkedListInfo **) NULL) return(MagickFalse); (void) ResetMagickMemory(map,0,(size_t) capacity*sizeof(*map)); /* Copy entries to new hashmap with increased capacity. */ for (i=0; i < (ssize_t) hashmap_info->capacity; i++) { list_info=hashmap_info->map[i]; if (list_info == (LinkedListInfo *) NULL) continue; LockSemaphoreInfo(list_info->semaphore); for (next=list_info->head; next != (ElementInfo *) NULL; ) { element=next; next=next->next; entry=(EntryInfo *) element->value; map_info=map[entry->hash % capacity]; if (map_info == (LinkedListInfo *) NULL) { map_info=NewLinkedList(0); map[entry->hash % capacity]=map_info; } map_info->next=element; element->next=map_info->head; map_info->head=element; map_info->elements++; } list_info->signature=(~MagickSignature); UnlockSemaphoreInfo(list_info->semaphore); RelinquishSemaphoreInfo(&list_info->semaphore); list_info=(LinkedListInfo *) RelinquishMagickMemory(list_info); } hashmap_info->map=(LinkedListInfo **) RelinquishMagickMemory( hashmap_info->map); hashmap_info->map=map; hashmap_info->capacity=capacity; return(MagickTrue); } MagickExport MagickBooleanType PutEntryInHashmap(HashmapInfo *hashmap_info, const void *key,const void *value) { EntryInfo *entry, *next; LinkedListInfo *list_info; register size_t i; assert(hashmap_info != (HashmapInfo *) NULL); assert(hashmap_info->signature == MagickSignature); if ((key == (void *) NULL) || (value == (void *) NULL)) return(MagickFalse); next=(EntryInfo *) AcquireMagickMemory(sizeof(*next)); if (next == (EntryInfo *) NULL) return(MagickFalse); LockSemaphoreInfo(hashmap_info->semaphore); next->hash=hashmap_info->hash(key); next->key=(void *) key; next->value=(void *) value; list_info=hashmap_info->map[next->hash % hashmap_info->capacity]; if (list_info == (LinkedListInfo *) NULL) { list_info=NewLinkedList(0); hashmap_info->map[next->hash % hashmap_info->capacity]=list_info; } else { list_info->next=list_info->head; entry=(EntryInfo *) GetNextValueInLinkedList(list_info); for (i=0; entry != (EntryInfo *) NULL; i++) { if (entry->hash == next->hash) { MagickBooleanType compare; compare=MagickTrue; if (hashmap_info->compare != (MagickBooleanType (*)(const void *,const void *)) NULL) compare=hashmap_info->compare(key,entry->key); if( IfMagickTrue(compare) ) { (void) RemoveElementFromLinkedList(list_info,i); if (hashmap_info->relinquish_key != (void *(*)(void *)) NULL) entry->key=hashmap_info->relinquish_key(entry->key); if (hashmap_info->relinquish_value != (void *(*)(void *)) NULL) entry->value=hashmap_info->relinquish_value(entry->value); entry=(EntryInfo *) RelinquishMagickMemory(entry); break; } } entry=(EntryInfo *) GetNextValueInLinkedList(list_info); } } if (IfMagickFalse(InsertValueInLinkedList(list_info,0,next))) { next=(EntryInfo *) RelinquishMagickMemory(next); UnlockSemaphoreInfo(hashmap_info->semaphore); return(MagickFalse); } if (list_info->elements >= (hashmap_info->capacity-1)) if (IfMagickFalse(IncreaseHashmapCapacity(hashmap_info))) { UnlockSemaphoreInfo(hashmap_info->semaphore); return(MagickFalse); } hashmap_info->entries++; UnlockSemaphoreInfo(hashmap_info->semaphore); return(MagickTrue); } /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % % % % % 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 % % % % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % RemoveElementByValueFromLinkedList() removes an element from the linked-list % by value. % % The format of the RemoveElementByValueFromLinkedList method is: % % void *RemoveElementByValueFromLinkedList(LinkedListInfo *list_info, % const void *value) % % A description of each parameter follows: % % o list_info: the list info. % % o value: the value. % */ MagickExport void *RemoveElementByValueFromLinkedList(LinkedListInfo *list_info, const void *value) { ElementInfo *next; assert(list_info != (LinkedListInfo *) NULL); assert(list_info->signature == MagickSignature); if ((list_info->elements == 0) || (value == (const void *) NULL)) return((void *) NULL); LockSemaphoreInfo(list_info->semaphore); if (value == list_info->head->value) { if (list_info->next == list_info->head) list_info->next=list_info->head->next; next=list_info->head; list_info->head=list_info->head->next; next=(ElementInfo *) RelinquishMagickMemory(next); } else { ElementInfo *element; next=list_info->head; while ((next->next != (ElementInfo *) NULL) && (next->next->value != value)) next=next->next; if (next->next == (ElementInfo *) NULL) { UnlockSemaphoreInfo(list_info->semaphore); return((void *) NULL); } element=next->next; next->next=element->next; if (element == list_info->tail) list_info->tail=next; if (list_info->next == element) list_info->next=element->next; element=(ElementInfo *) RelinquishMagickMemory(element); } list_info->elements--; UnlockSemaphoreInfo(list_info->semaphore); return((void *) value); } /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % % % % % 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 % % % % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % RemoveElementFromLinkedList() removes an element from the linked-list at the % specified location. % % The format of the RemoveElementFromLinkedList method is: % % void *RemoveElementFromLinkedList(LinkedListInfo *list_info, % const size_t index) % % A description of each parameter follows: % % o list_info: the linked-list info. % % o index: the index. % */ MagickExport void *RemoveElementFromLinkedList(LinkedListInfo *list_info, const size_t index) { ElementInfo *next; register ssize_t i; void *value; assert(list_info != (LinkedListInfo *) NULL); assert(list_info->signature == MagickSignature); if (index >= list_info->elements) return((void *) NULL); LockSemaphoreInfo(list_info->semaphore); if (index == 0) { if (list_info->next == list_info->head) list_info->next=list_info->head->next; value=list_info->head->value; next=list_info->head; list_info->head=list_info->head->next; next=(ElementInfo *) RelinquishMagickMemory(next); } else { ElementInfo *element; next=list_info->head; for (i=1; i < (ssize_t) index; i++) next=next->next; element=next->next; next->next=element->next; if (element == list_info->tail) list_info->tail=next; if (list_info->next == element) list_info->next=element->next; value=element->value; element=(ElementInfo *) RelinquishMagickMemory(element); } list_info->elements--; UnlockSemaphoreInfo(list_info->semaphore); return(value); } /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % % % % % R e m o v e E n t r y F r o m H a s h m a p % % % % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % RemoveEntryFromHashmap() removes an entry from the hash-map by its key. % % The format of the RemoveEntryFromHashmap method is: % % void *RemoveEntryFromHashmap(HashmapInfo *hashmap_info,void *key) % % A description of each parameter follows: % % o hashmap_info: the hashmap info. % % o key: the key. % */ MagickExport void *RemoveEntryFromHashmap(HashmapInfo *hashmap_info, const void *key) { EntryInfo *entry; LinkedListInfo *list_info; register size_t i; size_t hash; void *value; assert(hashmap_info != (HashmapInfo *) NULL); assert(hashmap_info->signature == MagickSignature); if (key == (const void *) NULL) return((void *) NULL); LockSemaphoreInfo(hashmap_info->semaphore); hash=hashmap_info->hash(key); list_info=hashmap_info->map[hash % hashmap_info->capacity]; if (list_info != (LinkedListInfo *) NULL) { list_info->next=list_info->head; entry=(EntryInfo *) GetNextValueInLinkedList(list_info); for (i=0; entry != (EntryInfo *) NULL; i++) { if (entry->hash == hash) { MagickBooleanType compare; compare=MagickTrue; if (hashmap_info->compare != (MagickBooleanType (*)(const void *,const void *)) NULL) compare=hashmap_info->compare(key,entry->key); if( IfMagickTrue(compare) ) { entry=(EntryInfo *) RemoveElementFromLinkedList(list_info,i); if (entry == (EntryInfo *) NULL) { UnlockSemaphoreInfo(hashmap_info->semaphore); return((void *) NULL); } if (hashmap_info->relinquish_key != (void *(*)(void *)) NULL) entry->key=hashmap_info->relinquish_key(entry->key); value=entry->value; entry=(EntryInfo *) RelinquishMagickMemory(entry); hashmap_info->entries--; UnlockSemaphoreInfo(hashmap_info->semaphore); return(value); } } entry=(EntryInfo *) GetNextValueInLinkedList(list_info); } } UnlockSemaphoreInfo(hashmap_info->semaphore); return((void *) NULL); } /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % % % % % 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 % % % % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % RemoveLastElementFromLinkedList() removes the last element from the % linked-list. % % The format of the RemoveLastElementFromLinkedList method is: % % void *RemoveLastElementFromLinkedList(LinkedListInfo *list_info) % % A description of each parameter follows: % % o list_info: the linked-list info. % */ MagickExport void *RemoveLastElementFromLinkedList(LinkedListInfo *list_info) { void *value; assert(list_info != (LinkedListInfo *) NULL); assert(list_info->signature == MagickSignature); if (list_info->elements == 0) return((void *) NULL); LockSemaphoreInfo(list_info->semaphore); if (list_info->next == list_info->tail) list_info->next=(ElementInfo *) NULL; if (list_info->elements == 1UL) { value=list_info->head->value; list_info->head=(ElementInfo *) NULL; list_info->tail=(ElementInfo *) RelinquishMagickMemory(list_info->tail); } else { ElementInfo *next; value=list_info->tail->value; next=list_info->head; while (next->next != list_info->tail) next=next->next; list_info->tail=(ElementInfo *) RelinquishMagickMemory(list_info->tail); list_info->tail=next; next->next=(ElementInfo *) NULL; } list_info->elements--; UnlockSemaphoreInfo(list_info->semaphore); return(value); } /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % % % % % R e s e t H a s h m a p I t e r a t o r % % % % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % ResetHashmapIterator() resets the hash-map iterator. Use it in conjunction % with GetNextKeyInHashmap() to iterate over all the keys in the hash-map. % % The format of the ResetHashmapIterator method is: % % ResetHashmapIterator(HashmapInfo *hashmap_info) % % A description of each parameter follows: % % o hashmap_info: the hashmap info. % */ MagickExport void ResetHashmapIterator(HashmapInfo *hashmap_info) { assert(hashmap_info != (HashmapInfo *) NULL); assert(hashmap_info->signature == MagickSignature); LockSemaphoreInfo(hashmap_info->semaphore); hashmap_info->next=0; hashmap_info->head_of_list=MagickFalse; UnlockSemaphoreInfo(hashmap_info->semaphore); } /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % % % % % R e s e t L i n k e d L i s t I t e r a t o r % % % % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % ResetLinkedListIterator() resets the lined-list iterator. Use it in % conjunction with GetNextValueInLinkedList() to iterate over all the values % in the linked-list. % % The format of the ResetLinkedListIterator method is: % % ResetLinkedListIterator(LinkedListInfo *list_info) % % A description of each parameter follows: % % o list_info: the linked-list info. % */ MagickExport void ResetLinkedListIterator(LinkedListInfo *list_info) { assert(list_info != (LinkedListInfo *) NULL); assert(list_info->signature == MagickSignature); LockSemaphoreInfo(list_info->semaphore); list_info->next=list_info->head; UnlockSemaphoreInfo(list_info->semaphore); }