From abed7e293f2e8a83e8036df7f2a3e1d9859e5fb2 Mon Sep 17 00:00:00 2001 From: dirk Date: Sun, 31 Jan 2016 17:10:21 +0100 Subject: [PATCH] Renamed hashmap.c to linked-list.c and removed the hashmap code. --- MagickCore/MagickCore.h | 2 +- MagickCore/Makefile.am | 4 +- MagickCore/accelerate.c | 2 +- MagickCore/cipher.c | 2 +- MagickCore/coder.c | 2 +- MagickCore/configure.c | 2 +- MagickCore/configure.h | 2 +- MagickCore/delegate.c | 2 +- MagickCore/distort.c | 2 +- MagickCore/exception.c | 2 +- MagickCore/hashmap.c | 1928 ----------------------- MagickCore/histogram.c | 2 +- MagickCore/linked-list.c | 967 ++++++++++++ MagickCore/{hashmap.h => linked-list.h} | 36 +- MagickCore/locale.c | 2 +- MagickCore/locale_.h | 2 +- MagickCore/log.c | 2 +- MagickCore/magic.c | 2 +- MagickCore/mime.c | 2 +- MagickCore/module.c | 2 +- MagickCore/morphology.c | 2 +- MagickCore/prepress.c | 2 +- MagickCore/profile.c | 2 +- MagickCore/resource.c | 2 +- MagickCore/type.c | 2 +- MagickCore/version.c | 2 +- coders/miff.c | 2 +- coders/mpc.c | 2 +- 28 files changed, 998 insertions(+), 1985 deletions(-) delete mode 100644 MagickCore/hashmap.c create mode 100644 MagickCore/linked-list.c rename MagickCore/{hashmap.h => linked-list.h} (60%) diff --git a/MagickCore/MagickCore.h b/MagickCore/MagickCore.h index b10d5ca2a..8f822e798 100644 --- a/MagickCore/MagickCore.h +++ b/MagickCore/MagickCore.h @@ -110,12 +110,12 @@ extern "C" { #include "MagickCore/fx.h" #include "MagickCore/gem.h" #include "MagickCore/geometry.h" -#include "MagickCore/hashmap.h" #include "MagickCore/histogram.h" #include "MagickCore/identify.h" #include "MagickCore/image.h" #include "MagickCore/image-view.h" #include "MagickCore/layer.h" +#include "MagickCore/linked-list.h" #include "MagickCore/list.h" #include "MagickCore/locale_.h" #include "MagickCore/log.h" diff --git a/MagickCore/Makefile.am b/MagickCore/Makefile.am index c1edbcf70..a1e3d6190 100644 --- a/MagickCore/Makefile.am +++ b/MagickCore/Makefile.am @@ -149,8 +149,6 @@ MAGICKCORE_BASE_SRCS = \ MagickCore/gem-private.h \ MagickCore/geometry.c \ MagickCore/geometry.h \ - MagickCore/hashmap.c \ - MagickCore/hashmap.h \ MagickCore/histogram.c \ MagickCore/histogram.h \ MagickCore/identify.c \ @@ -162,6 +160,8 @@ MAGICKCORE_BASE_SRCS = \ MagickCore/image-view.h \ MagickCore/layer.c \ MagickCore/layer.h \ + MagickCore/linked-list.c \ + MagickCore/linked-list.h \ MagickCore/list.c \ MagickCore/list.h \ MagickCore/locale.c \ diff --git a/MagickCore/accelerate.c b/MagickCore/accelerate.c index c9d551040..eddd7fece 100644 --- a/MagickCore/accelerate.c +++ b/MagickCore/accelerate.c @@ -52,9 +52,9 @@ Include declarations. #include "MagickCore/exception.h" #include "MagickCore/exception-private.h" #include "MagickCore/gem.h" -#include "MagickCore/hashmap.h" #include "MagickCore/image.h" #include "MagickCore/image-private.h" +#include "MagickCore/linked-list.h" #include "MagickCore/list.h" #include "MagickCore/memory_.h" #include "MagickCore/monitor-private.h" diff --git a/MagickCore/cipher.c b/MagickCore/cipher.c index 8000c4330..7da9909ab 100644 --- a/MagickCore/cipher.c +++ b/MagickCore/cipher.c @@ -43,9 +43,9 @@ #include "MagickCore/cipher.h" #include "MagickCore/exception.h" #include "MagickCore/exception-private.h" -#include "MagickCore/hashmap.h" #include "MagickCore/image.h" #include "MagickCore/image-private.h" +#include "MagickCore/linked-list.h" #include "MagickCore/list.h" #include "MagickCore/memory_.h" #include "MagickCore/monitor.h" diff --git a/MagickCore/coder.c b/MagickCore/coder.c index 2652515ab..1231ba073 100644 --- a/MagickCore/coder.c +++ b/MagickCore/coder.c @@ -48,7 +48,7 @@ #include "MagickCore/draw.h" #include "MagickCore/exception.h" #include "MagickCore/exception-private.h" -#include "MagickCore/hashmap.h" +#include "MagickCore/linked-list.h" #include "MagickCore/log.h" #include "MagickCore/memory_.h" #include "MagickCore/option.h" diff --git a/MagickCore/configure.c b/MagickCore/configure.c index 2a9dbcd8c..768bc3945 100644 --- a/MagickCore/configure.c +++ b/MagickCore/configure.c @@ -46,7 +46,7 @@ #include "MagickCore/configure-private.h" #include "MagickCore/exception.h" #include "MagickCore/exception-private.h" -#include "MagickCore/hashmap.h" +#include "MagickCore/linked-list.h" #include "MagickCore/log.h" #include "MagickCore/memory_.h" #include "MagickCore/semaphore.h" diff --git a/MagickCore/configure.h b/MagickCore/configure.h index f38237486..48ee4f956 100644 --- a/MagickCore/configure.h +++ b/MagickCore/configure.h @@ -18,7 +18,7 @@ #ifndef _MAGICKCORE_CONFIGURE_H #define _MAGICKCORE_CONFIGURE_H -#include "MagickCore/hashmap.h" +#include "MagickCore/linked-list.h" #if defined(__cplusplus) || defined(c_plusplus) extern "C" { diff --git a/MagickCore/delegate.c b/MagickCore/delegate.c index 12fe07823..261111df2 100644 --- a/MagickCore/delegate.c +++ b/MagickCore/delegate.c @@ -55,8 +55,8 @@ #include "MagickCore/delegate-private.h" #include "MagickCore/exception.h" #include "MagickCore/exception-private.h" -#include "MagickCore/hashmap.h" #include "MagickCore/image-private.h" +#include "MagickCore/linked-list.h" #include "MagickCore/list.h" #include "MagickCore/memory_.h" #include "MagickCore/nt-base-private.h" diff --git a/MagickCore/distort.c b/MagickCore/distort.c index af78f6c40..fef2f3287 100644 --- a/MagickCore/distort.c +++ b/MagickCore/distort.c @@ -51,8 +51,8 @@ #include "MagickCore/exception.h" #include "MagickCore/exception-private.h" #include "MagickCore/gem.h" -#include "MagickCore/hashmap.h" #include "MagickCore/image.h" +#include "MagickCore/linked-list.h" #include "MagickCore/list.h" #include "MagickCore/matrix.h" #include "MagickCore/matrix-private.h" diff --git a/MagickCore/exception.c b/MagickCore/exception.c index fef76bdb6..b52236bc4 100644 --- a/MagickCore/exception.c +++ b/MagickCore/exception.c @@ -44,7 +44,7 @@ #include "MagickCore/client.h" #include "MagickCore/exception.h" #include "MagickCore/exception-private.h" -#include "MagickCore/hashmap.h" +#include "MagickCore/linked-list.h" #include "MagickCore/locale_.h" #include "MagickCore/log.h" #include "MagickCore/magick.h" diff --git a/MagickCore/hashmap.c b/MagickCore/hashmap.c deleted file mode 100644 index 6eb605820..000000000 --- a/MagickCore/hashmap.c +++ /dev/null @@ -1,1928 +0,0 @@ -/* -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% % -% % -% % -% 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-2016 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/locale_.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 == MagickCoreSignature); - 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 == MagickCoreSignature); - 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(LocaleCompare(p,q) == 0 ? MagickTrue : MagickFalse); -} - -/* -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% % -% % -% % -% 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) -{ - const StringInfo - *p, - *q; - - p=(const StringInfo *) target; - q=(const StringInfo *) source; - return(CompareStringInfo(p,q) == 0 ? MagickTrue : MagickFalse); -} - -/* -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% % -% % -% % -% 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 == MagickCoreSignature); - 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=(~MagickCoreSignature); - 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 == MagickCoreSignature); - 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=(~MagickCoreSignature); - 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 == MagickCoreSignature); - 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 == MagickCoreSignature); - 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 (hashmap_info->head_of_list == MagickFalse) - { - 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 == MagickCoreSignature); - 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 (hashmap_info->head_of_list == MagickFalse) - { - 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 == MagickCoreSignature); - 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 == MagickCoreSignature); - 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 == MagickCoreSignature); - 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 == MagickCoreSignature); - 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 (compare != MagickFalse) - { - 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 == MagickCoreSignature); - 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 == MagickCoreSignature); - 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 == MagickCoreSignature); - 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 == MagickCoreSignature); - return(hashmap_info->entries == 0 ? MagickTrue : MagickFalse); -} - -/* -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% % -% % -% % -% 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 == MagickCoreSignature); - return(list_info->elements == 0 ? MagickTrue : MagickFalse); -} - -/* -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% % -% % -% % -% 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 == MagickCoreSignature); - 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=MagickCoreSignature; - 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=MagickCoreSignature; - 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 - *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++) - { - LinkedListInfo - *list_info; - - 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=(~MagickCoreSignature); - 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 == MagickCoreSignature); - 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( compare != MagickFalse ) - { - (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 (InsertValueInLinkedList(list_info,0,next) == MagickFalse) - { - next=(EntryInfo *) RelinquishMagickMemory(next); - UnlockSemaphoreInfo(hashmap_info->semaphore); - return(MagickFalse); - } - if (list_info->elements >= (hashmap_info->capacity-1)) - if (IncreaseHashmapCapacity(hashmap_info) == MagickFalse) - { - 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 == MagickCoreSignature); - 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 == MagickCoreSignature); - 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 == MagickCoreSignature); - 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 (compare != MagickFalse) - { - 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 == MagickCoreSignature); - 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 == MagickCoreSignature); - 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 == MagickCoreSignature); - LockSemaphoreInfo(list_info->semaphore); - list_info->next=list_info->head; - UnlockSemaphoreInfo(list_info->semaphore); -} diff --git a/MagickCore/histogram.c b/MagickCore/histogram.c index 5a822915c..32294aeaa 100644 --- a/MagickCore/histogram.c +++ b/MagickCore/histogram.c @@ -46,9 +46,9 @@ #include "MagickCore/enhance.h" #include "MagickCore/exception.h" #include "MagickCore/exception-private.h" -#include "MagickCore/hashmap.h" #include "MagickCore/histogram.h" #include "MagickCore/image.h" +#include "MagickCore/linked-list.h" #include "MagickCore/list.h" #include "MagickCore/memory_.h" #include "MagickCore/monitor-private.h" diff --git a/MagickCore/linked-list.c b/MagickCore/linked-list.c new file mode 100644 index 000000000..95a49a3d6 --- /dev/null +++ b/MagickCore/linked-list.c @@ -0,0 +1,967 @@ +/* +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% % +% % +% % +% L IIIII N N K K EEEEE DDDD L IIIII SSSSS TTTTT % +% L I NN N K K E D D L I SS T % +% L I N N N KKK EEE D D = L I SSS T % +% L I N NN K K E D D L I SS T % +% LLLLL IIIII N N K K EEEEE DDDD LLLLL IIIII SSSSS T % +% % +% % +% MagickCore Linked-list Methods % +% % +% Software Design % +% Cristy % +% December 2002 % +% % +% % +% Copyright 1999-2016 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/linked-list.h" +#include "MagickCore/locale_.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; + +struct _LinkedListInfo +{ + size_t + capacity, + elements; + + ElementInfo + *head, + *tail, + *next; + + 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 == MagickCoreSignature); + 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 == MagickCoreSignature); + 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); +} + +/* +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% % +% % +% % +% 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 == MagickCoreSignature); + 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=(~MagickCoreSignature); + 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 == MagickCoreSignature); + 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 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 == MagickCoreSignature); + 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 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 == MagickCoreSignature); + return(list_info->elements); +} + +/* +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% % +% % +% % +% 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 == MagickCoreSignature); + 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); +} + +/* +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% % +% % +% % +% 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 == MagickCoreSignature); + 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 == MagickCoreSignature); + 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 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 == MagickCoreSignature); + return(list_info->elements == 0 ? MagickTrue : MagickFalse); +} + +/* +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% % +% % +% % +% 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 == MagickCoreSignature); + 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 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=MagickCoreSignature; + return(list_info); +} + +/* +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% % +% % +% % +% 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 == MagickCoreSignature); + 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 == MagickCoreSignature); + 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 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 == MagickCoreSignature); + 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 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 == MagickCoreSignature); + LockSemaphoreInfo(list_info->semaphore); + list_info->next=list_info->head; + UnlockSemaphoreInfo(list_info->semaphore); +} diff --git a/MagickCore/hashmap.h b/MagickCore/linked-list.h similarity index 60% rename from MagickCore/hashmap.h rename to MagickCore/linked-list.h index 29ddf1f3d..dbb54d375 100644 --- a/MagickCore/hashmap.h +++ b/MagickCore/linked-list.h @@ -13,67 +13,41 @@ See the License for the specific language governing permissions and limitations under the License. - MagickCore hash methods. + MagickCore linked list methods. */ -#ifndef _MAGICKCORE_HASHMAP_H -#define _MAGICKCORE_HASHMAP_H +#ifndef _MAGICKCORE_LINKED_LIST_H +#define _MAGICKCORE_LINKED_LIST_H #if defined(__cplusplus) || defined(c_plusplus) extern "C" { #endif -#define SmallHashmapSize 17 -#define MediumHashmapSize 509 -#define LargeHashmapSize 8191 -#define HugeHashmapSize 131071 - -typedef struct _HashmapInfo - HashmapInfo; - typedef struct _LinkedListInfo LinkedListInfo; -extern MagickExport HashmapInfo - *DestroyHashmap(HashmapInfo *), - *NewHashmap(const size_t,size_t (*)(const void *),MagickBooleanType (*) - (const void *,const void *),void *(*)(void *),void *(*)(void *)); - extern MagickExport LinkedListInfo *DestroyLinkedList(LinkedListInfo *,void *(*)(void *)), *NewLinkedList(const size_t); extern MagickExport MagickBooleanType AppendValueToLinkedList(LinkedListInfo *,const void *), - CompareHashmapString(const void *,const void *), - CompareHashmapStringInfo(const void *,const void *), InsertValueInLinkedList(LinkedListInfo *,const size_t,const void *), InsertValueInSortedLinkedList(LinkedListInfo *, int (*)(const void *,const void *),void **,const void *), - IsHashmapEmpty(const HashmapInfo *), IsLinkedListEmpty(const LinkedListInfo *), - LinkedListToArray(LinkedListInfo *,void **), - PutEntryInHashmap(HashmapInfo *,const void *,const void *); + LinkedListToArray(LinkedListInfo *,void **); extern MagickExport size_t - GetNumberOfElementsInLinkedList(const LinkedListInfo *), - GetNumberOfEntriesInHashmap(const HashmapInfo *), - HashPointerType(const void *), - HashStringType(const void *), - HashStringInfoType(const void *); + GetNumberOfElementsInLinkedList(const LinkedListInfo *); extern MagickExport void ClearLinkedList(LinkedListInfo *,void *(*)(void *)), *GetLastValueInLinkedList(LinkedListInfo *), - *GetNextKeyInHashmap(HashmapInfo *), - *GetNextValueInHashmap(HashmapInfo *), *GetNextValueInLinkedList(LinkedListInfo *), - *GetValueFromHashmap(HashmapInfo *,const void *), *GetValueFromLinkedList(LinkedListInfo *,const size_t), *RemoveElementByValueFromLinkedList(LinkedListInfo *,const void *), *RemoveElementFromLinkedList(LinkedListInfo *,const size_t), - *RemoveEntryFromHashmap(HashmapInfo *,const void *), *RemoveLastElementFromLinkedList(LinkedListInfo *), - ResetHashmapIterator(HashmapInfo *), ResetLinkedListIterator(LinkedListInfo *); #if defined(__cplusplus) || defined(c_plusplus) diff --git a/MagickCore/locale.c b/MagickCore/locale.c index 154290a02..ccd083295 100644 --- a/MagickCore/locale.c +++ b/MagickCore/locale.c @@ -45,8 +45,8 @@ #include "MagickCore/configure.h" #include "MagickCore/exception.h" #include "MagickCore/exception-private.h" -#include "MagickCore/hashmap.h" #include "MagickCore/image-private.h" +#include "MagickCore/linked-list.h" #include "MagickCore/locale_.h" #include "MagickCore/locale-private.h" #include "MagickCore/log.h" diff --git a/MagickCore/locale_.h b/MagickCore/locale_.h index 564a90c3f..e31d81d11 100644 --- a/MagickCore/locale_.h +++ b/MagickCore/locale_.h @@ -18,7 +18,7 @@ #ifndef _MAGICKCORE_LOCALE_H #define _MAGICKCORE_LOCALE_H -#include "MagickCore/hashmap.h" +#include "MagickCore/linked-list.h" #if defined(__cplusplus) || defined(c_plusplus) extern "C" { diff --git a/MagickCore/log.c b/MagickCore/log.c index fec604b8f..139362ddc 100644 --- a/MagickCore/log.c +++ b/MagickCore/log.c @@ -46,7 +46,7 @@ #include "MagickCore/configure-private.h" #include "MagickCore/exception.h" #include "MagickCore/exception-private.h" -#include "MagickCore/hashmap.h" +#include "MagickCore/linked-list.h" #include "MagickCore/log.h" #include "MagickCore/log-private.h" #include "MagickCore/memory_.h" diff --git a/MagickCore/magic.c b/MagickCore/magic.c index ddc92de03..34715cff1 100644 --- a/MagickCore/magic.c +++ b/MagickCore/magic.c @@ -46,7 +46,7 @@ #include "MagickCore/configure-private.h" #include "MagickCore/exception.h" #include "MagickCore/exception-private.h" -#include "MagickCore/hashmap.h" +#include "MagickCore/linked-list.h" #include "MagickCore/magic.h" #include "MagickCore/magic-private.h" #include "MagickCore/memory_.h" diff --git a/MagickCore/mime.c b/MagickCore/mime.c index 8b96d383c..68dacff1f 100644 --- a/MagickCore/mime.c +++ b/MagickCore/mime.c @@ -44,7 +44,7 @@ #include "MagickCore/configure-private.h" #include "MagickCore/exception.h" #include "MagickCore/exception-private.h" -#include "MagickCore/hashmap.h" +#include "MagickCore/linked-list.h" #include "MagickCore/memory_.h" #include "MagickCore/mime.h" #include "MagickCore/mime-private.h" diff --git a/MagickCore/module.c b/MagickCore/module.c index b253bd10c..419f3f37f 100644 --- a/MagickCore/module.c +++ b/MagickCore/module.c @@ -48,7 +48,7 @@ #include "MagickCore/exception.h" #include "MagickCore/exception-private.h" #include "MagickCore/log.h" -#include "MagickCore/hashmap.h" +#include "MagickCore/linked-list.h" #include "MagickCore/magic.h" #include "MagickCore/magick.h" #include "MagickCore/memory_.h" diff --git a/MagickCore/morphology.c b/MagickCore/morphology.c index cedad4e49..649c1bc8f 100644 --- a/MagickCore/morphology.c +++ b/MagickCore/morphology.c @@ -59,9 +59,9 @@ #include "MagickCore/exception-private.h" #include "MagickCore/gem.h" #include "MagickCore/gem-private.h" -#include "MagickCore/hashmap.h" #include "MagickCore/image.h" #include "MagickCore/image-private.h" +#include "MagickCore/linked-list.h" #include "MagickCore/list.h" #include "MagickCore/magick.h" #include "MagickCore/memory_.h" diff --git a/MagickCore/prepress.c b/MagickCore/prepress.c index f44a93d40..878061748 100644 --- a/MagickCore/prepress.c +++ b/MagickCore/prepress.c @@ -43,8 +43,8 @@ #include "MagickCore/cache-view.h" #include "MagickCore/exception.h" #include "MagickCore/exception-private.h" -#include "MagickCore/hashmap.h" #include "MagickCore/image.h" +#include "MagickCore/linked-list.h" #include "MagickCore/list.h" #include "MagickCore/memory_.h" #include "MagickCore/pixel-accessor.h" diff --git a/MagickCore/profile.c b/MagickCore/profile.c index 4fca905fa..3b5048b97 100644 --- a/MagickCore/profile.c +++ b/MagickCore/profile.c @@ -47,8 +47,8 @@ #include "MagickCore/configure.h" #include "MagickCore/exception.h" #include "MagickCore/exception-private.h" -#include "MagickCore/hashmap.h" #include "MagickCore/image.h" +#include "MagickCore/linked-list.h" #include "MagickCore/memory_.h" #include "MagickCore/monitor.h" #include "MagickCore/monitor-private.h" diff --git a/MagickCore/resource.c b/MagickCore/resource.c index 538052ec7..ce2c2f653 100644 --- a/MagickCore/resource.c +++ b/MagickCore/resource.c @@ -44,7 +44,7 @@ #include "MagickCore/configure.h" #include "MagickCore/exception.h" #include "MagickCore/exception-private.h" -#include "MagickCore/hashmap.h" +#include "MagickCore/linked-list.h" #include "MagickCore/log.h" #include "MagickCore/image.h" #include "MagickCore/image-private.h" diff --git a/MagickCore/type.c b/MagickCore/type.c index 958995740..f851b9824 100644 --- a/MagickCore/type.c +++ b/MagickCore/type.c @@ -46,8 +46,8 @@ #include "MagickCore/draw.h" #include "MagickCore/exception.h" #include "MagickCore/exception-private.h" -#include "MagickCore/hashmap.h" #include "MagickCore/image-private.h" +#include "MagickCore/linked-list.h" #include "MagickCore/log.h" #include "MagickCore/memory_.h" #include "MagickCore/nt-feature.h" diff --git a/MagickCore/version.c b/MagickCore/version.c index b1e92bd31..cfa66b398 100644 --- a/MagickCore/version.c +++ b/MagickCore/version.c @@ -40,7 +40,7 @@ #include "MagickCore/configure.h" #include "MagickCore/exception.h" #include "MagickCore/exception-private.h" -#include "MagickCore/hashmap.h" +#include "MagickCore/linked-list.h" #include "MagickCore/locale_.h" #include "MagickCore/option.h" #include "MagickCore/string_.h" diff --git a/coders/miff.c b/coders/miff.c index c25789f95..97038dada 100644 --- a/coders/miff.c +++ b/coders/miff.c @@ -53,10 +53,10 @@ #include "MagickCore/constitute.h" #include "MagickCore/exception.h" #include "MagickCore/exception-private.h" -#include "MagickCore/hashmap.h" #include "MagickCore/geometry.h" #include "MagickCore/image.h" #include "MagickCore/image-private.h" +#include "MagickCore/linked-list.h" #include "MagickCore/list.h" #include "MagickCore/magick.h" #include "MagickCore/memory_.h" diff --git a/coders/mpc.c b/coders/mpc.c index daaf95d2b..8264a6823 100644 --- a/coders/mpc.c +++ b/coders/mpc.c @@ -53,9 +53,9 @@ #include "MagickCore/exception.h" #include "MagickCore/exception-private.h" #include "MagickCore/geometry.h" -#include "MagickCore/hashmap.h" #include "MagickCore/image.h" #include "MagickCore/image-private.h" +#include "MagickCore/linked-list.h" #include "MagickCore/list.h" #include "MagickCore/magick.h" #include "MagickCore/memory_.h" -- 2.40.0