This source file includes following definitions.
- AppendValueToLinkedList
- ClearLinkedList
- CompareHashmapString
- CompareHashmapStringInfo
- DestroyHashmap
- DestroyLinkedList
- GetLastValueInLinkedList
- GetNextKeyInHashmap
- GetNextValueInHashmap
- GetNextValueInLinkedList
- GetNumberOfEntriesInHashmap
- GetNumberOfElementsInLinkedList
- GetValueFromHashmap
- GetValueFromLinkedList
- HashPointerType
- HashStringType
- HashStringInfoType
- InsertValueInLinkedList
- InsertValueInSortedLinkedList
- IsHashmapEmpty
- IsLinkedListEmpty
- LinkedListToArray
- NewHashmap
- NewLinkedList
- IncreaseHashmapCapacity
- PutEntryInHashmap
- RemoveElementByValueFromLinkedList
- RemoveElementFromLinkedList
- RemoveEntryFromHashmap
- RemoveLastElementFromLinkedList
- ResetHashmapIterator
- ResetLinkedListIterator
#include "magick/studio.h"
#include "magick/exception.h"
#include "magick/exception-private.h"
#include "magick/hashmap.h"
#include "magick/locale_.h"
#include "magick/memory_.h"
#include "magick/semaphore.h"
#include "magick/signature-private.h"
#include "magick/string_.h"
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;
};
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);
}
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);
}
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);
}
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);
}
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);
DestroySemaphoreInfo(&hashmap_info->semaphore);
hashmap_info=(HashmapInfo *) RelinquishMagickMemory(hashmap_info);
return(hashmap_info);
}
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);
DestroySemaphoreInfo(&list_info->semaphore);
list_info=(LinkedListInfo *) RelinquishMagickMemory(list_info);
return(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);
}
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 (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);
}
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 (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);
}
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);
}
MagickExport size_t GetNumberOfEntriesInHashmap(
const HashmapInfo *hashmap_info)
{
assert(hashmap_info != (HashmapInfo *) NULL);
assert(hashmap_info->signature == MagickSignature);
return(hashmap_info->entries);
}
MagickExport size_t GetNumberOfElementsInLinkedList(
const LinkedListInfo *list_info)
{
assert(list_info != (LinkedListInfo *) NULL);
assert(list_info->signature == MagickSignature);
return(list_info->elements);
}
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 (compare != MagickFalse)
{
value=entry->value;
UnlockSemaphoreInfo(hashmap_info->semaphore);
return(value);
}
}
entry=(EntryInfo *) GetNextValueInLinkedList(list_info);
}
}
UnlockSemaphoreInfo(hashmap_info->semaphore);
return((void *) NULL);
}
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);
}
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);
}
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);
}
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);
}
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);
}
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);
}
MagickExport MagickBooleanType IsHashmapEmpty(const HashmapInfo *hashmap_info)
{
assert(hashmap_info != (HashmapInfo *) NULL);
assert(hashmap_info->signature == MagickSignature);
return(hashmap_info->entries == 0 ? MagickTrue : MagickFalse);
}
MagickExport MagickBooleanType IsLinkedListEmpty(
const LinkedListInfo *list_info)
{
assert(list_info != (LinkedListInfo *) NULL);
assert(list_info->signature == MagickSignature);
return(list_info->elements == 0 ? MagickTrue : MagickFalse);
}
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);
}
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=AllocateSemaphoreInfo();
hashmap_info->signature=MagickSignature;
return(hashmap_info);
}
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=AllocateSemaphoreInfo();
list_info->signature=MagickSignature;
return(list_info);
}
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;
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));
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=(~MagickSignature);
UnlockSemaphoreInfo(list_info->semaphore);
DestroySemaphoreInfo(&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 (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);
}
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);
}
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);
}
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 (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);
}
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);
}
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);
}
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);
}