45 #include "magick/studio.h"
46 #include "magick/exception.h"
47 #include "magick/exception-private.h"
48 #include "magick/hashmap.h"
49 #include "magick/locale_.h"
50 #include "magick/memory_.h"
51 #include "magick/semaphore.h"
52 #include "magick/signature-private.h"
53 #include "magick/string_.h"
98 (*hash)(
const void *);
101 (*compare)(
const void *,
const void *);
104 *(*relinquish_key)(
void *),
105 *(*relinquish_value)(
void *);
150 MagickExport MagickBooleanType AppendValueToLinkedList(
157 assert(list_info->signature == MagickCoreSignature);
158 if (list_info->elements == list_info->capacity)
160 next=(
ElementInfo *) AcquireMagickMemory(
sizeof(*next));
163 next->value=(
void *) value;
165 LockSemaphoreInfo(list_info->semaphore);
167 list_info->next=next;
168 if (list_info->elements == 0)
169 list_info->head=next;
171 list_info->tail->next=next;
172 list_info->tail=next;
173 list_info->elements++;
174 UnlockSemaphoreInfo(list_info->semaphore);
205 void *(*relinquish_value)(
void *))
214 assert(list_info->signature == MagickCoreSignature);
215 LockSemaphoreInfo(list_info->semaphore);
216 next=list_info->head;
219 if (relinquish_value != (
void *(*)(
void *)) NULL)
220 next->value=relinquish_value(next->value);
223 element=(
ElementInfo *) RelinquishMagickMemory(element);
228 list_info->elements=0;
229 UnlockSemaphoreInfo(list_info->semaphore);
258 MagickExport MagickBooleanType CompareHashmapString(
const void *target,
265 p=(
const char *) target;
266 q=(
const char *) source;
267 return(LocaleCompare(p,q) == 0 ? MagickTrue : MagickFalse);
296 MagickExport MagickBooleanType CompareHashmapStringInfo(
const void *target,
305 return(CompareStringInfo(p,q) == 0 ? MagickTrue : MagickFalse);
342 assert(hashmap_info->signature == MagickCoreSignature);
343 LockSemaphoreInfo(hashmap_info->semaphore);
344 for (i=0; i < (ssize_t) hashmap_info->capacity; i++)
346 list_info=hashmap_info->map[i];
349 list_info->next=list_info->head;
350 entry=(
EntryInfo *) GetNextValueInLinkedList(list_info);
353 if (hashmap_info->relinquish_key != (
void *(*)(
void *)) NULL)
354 entry->key=hashmap_info->relinquish_key(entry->key);
355 if (hashmap_info->relinquish_value != (
void *(*)(
void *)) NULL)
356 entry->value=hashmap_info->relinquish_value(entry->value);
357 entry=(
EntryInfo *) GetNextValueInLinkedList(list_info);
361 list_info=DestroyLinkedList(list_info,RelinquishMagickMemory);
365 hashmap_info->signature=(~MagickCoreSignature);
366 UnlockSemaphoreInfo(hashmap_info->semaphore);
367 DestroySemaphoreInfo(&hashmap_info->semaphore);
368 hashmap_info=(
HashmapInfo *) RelinquishMagickMemory(hashmap_info);
369 return(hashmap_info);
399 void *(*relinquish_value)(
void *))
408 assert(list_info->signature == MagickCoreSignature);
409 LockSemaphoreInfo(list_info->semaphore);
410 for (next=list_info->head; next != (
ElementInfo *) NULL; )
412 if (relinquish_value != (
void *(*)(
void *)) NULL)
413 next->value=relinquish_value(next->value);
416 entry=(
ElementInfo *) RelinquishMagickMemory(entry);
418 list_info->signature=(~MagickCoreSignature);
419 UnlockSemaphoreInfo(list_info->semaphore);
420 DestroySemaphoreInfo(&list_info->semaphore);
447 MagickExport
void *GetLastValueInLinkedList(
LinkedListInfo *list_info)
453 assert(list_info->signature == MagickCoreSignature);
454 if (list_info->elements == 0)
455 return((
void *) NULL);
456 LockSemaphoreInfo(list_info->semaphore);
457 value=list_info->tail->value;
458 UnlockSemaphoreInfo(list_info->semaphore);
484 MagickExport
void *GetNextKeyInHashmap(
HashmapInfo *hashmap_info)
496 assert(hashmap_info->signature == MagickCoreSignature);
497 LockSemaphoreInfo(hashmap_info->semaphore);
498 while (hashmap_info->next < hashmap_info->capacity)
500 list_info=hashmap_info->map[hashmap_info->next];
503 if (hashmap_info->head_of_list == MagickFalse)
505 list_info->next=list_info->head;
506 hashmap_info->head_of_list=MagickTrue;
508 entry=(
EntryInfo *) GetNextValueInLinkedList(list_info);
512 UnlockSemaphoreInfo(hashmap_info->semaphore);
515 hashmap_info->head_of_list=MagickFalse;
517 hashmap_info->next++;
519 UnlockSemaphoreInfo(hashmap_info->semaphore);
520 return((
void *) NULL);
545 MagickExport
void *GetNextValueInHashmap(
HashmapInfo *hashmap_info)
557 assert(hashmap_info->signature == MagickCoreSignature);
558 LockSemaphoreInfo(hashmap_info->semaphore);
559 while (hashmap_info->next < hashmap_info->capacity)
561 list_info=hashmap_info->map[hashmap_info->next];
564 if (hashmap_info->head_of_list == MagickFalse)
566 list_info->next=list_info->head;
567 hashmap_info->head_of_list=MagickTrue;
569 entry=(
EntryInfo *) GetNextValueInLinkedList(list_info);
573 UnlockSemaphoreInfo(hashmap_info->semaphore);
576 hashmap_info->head_of_list=MagickFalse;
578 hashmap_info->next++;
580 UnlockSemaphoreInfo(hashmap_info->semaphore);
581 return((
void *) NULL);
606 MagickExport
void *GetNextValueInLinkedList(
LinkedListInfo *list_info)
612 assert(list_info->signature == MagickCoreSignature);
613 LockSemaphoreInfo(list_info->semaphore);
616 UnlockSemaphoreInfo(list_info->semaphore);
617 return((
void *) NULL);
619 value=list_info->next->value;
620 list_info->next=list_info->next->next;
621 UnlockSemaphoreInfo(list_info->semaphore);
647 MagickExport
size_t GetNumberOfEntriesInHashmap(
651 assert(hashmap_info->signature == MagickCoreSignature);
652 return(hashmap_info->entries);
679 MagickExport
size_t GetNumberOfElementsInLinkedList(
683 assert(list_info->signature == MagickCoreSignature);
684 return(list_info->elements);
711 MagickExport
void *GetValueFromHashmap(
HashmapInfo *hashmap_info,
727 assert(hashmap_info->signature == MagickCoreSignature);
728 if (key == (
const void *) NULL)
729 return((
void *) NULL);
730 LockSemaphoreInfo(hashmap_info->semaphore);
731 hash=hashmap_info->hash(key);
732 list_info=hashmap_info->map[hash % hashmap_info->capacity];
735 list_info->next=list_info->head;
736 entry=(
EntryInfo *) GetNextValueInLinkedList(list_info);
739 if (entry->hash == hash)
745 if (hashmap_info->compare !=
746 (MagickBooleanType (*)(
const void *,
const void *)) NULL)
747 compare=hashmap_info->compare(key,entry->key);
748 if (compare != MagickFalse)
751 UnlockSemaphoreInfo(hashmap_info->semaphore);
755 entry=(
EntryInfo *) GetNextValueInLinkedList(list_info);
758 UnlockSemaphoreInfo(hashmap_info->semaphore);
759 return((
void *) NULL);
788 MagickExport
void *GetValueFromLinkedList(
LinkedListInfo *list_info,
801 assert(list_info->signature == MagickCoreSignature);
802 if (index >= list_info->elements)
803 return((
void *) NULL);
804 LockSemaphoreInfo(list_info->semaphore);
807 value=list_info->head->value;
808 UnlockSemaphoreInfo(list_info->semaphore);
811 if (index == (list_info->elements-1))
813 value=list_info->tail->value;
814 UnlockSemaphoreInfo(list_info->semaphore);
817 next=list_info->head;
818 for (i=0; i < (ssize_t) index; i++)
821 UnlockSemaphoreInfo(list_info->semaphore);
848 MagickExport
size_t HashPointerType(
const void *pointer)
853 hash=(size_t) pointer;
854 hash+=(~(hash << 9));
884 MagickExport
size_t HashStringType(
const void *
string)
901 signature_info=AcquireSignatureInfo();
902 signature=StringToStringInfo((
const char *)
string);
903 UpdateSignature(signature_info,signature);
904 FinalizeSignature(signature_info);
905 digest=GetStringInfoDatum(GetSignatureDigest(signature_info));
907 for (i=0; i < 8; i++)
909 signature=DestroyStringInfo(signature);
910 signature_info=DestroySignatureInfo(signature_info);
937 MagickExport
size_t HashStringInfoType(
const void *string_info)
951 signature_info=AcquireSignatureInfo();
952 UpdateSignature(signature_info,(
const StringInfo *) string_info);
953 FinalizeSignature(signature_info);
954 digest=GetStringInfoDatum(GetSignatureDigest(signature_info));
956 for (i=0; i < 8; i++)
958 signature_info=DestroySignatureInfo(signature_info);
990 MagickExport MagickBooleanType InsertValueInLinkedList(
1000 assert(list_info->signature == MagickCoreSignature);
1001 if (value == (
const void *) NULL)
1002 return(MagickFalse);
1003 if ((index > list_info->elements) ||
1004 (list_info->elements == list_info->capacity))
1005 return(MagickFalse);
1006 next=(
ElementInfo *) AcquireMagickMemory(
sizeof(*next));
1008 return(MagickFalse);
1009 next->value=(
void *) value;
1011 LockSemaphoreInfo(list_info->semaphore);
1012 if (list_info->elements == 0)
1015 list_info->next=next;
1016 list_info->head=next;
1017 list_info->tail=next;
1023 if (list_info->next == list_info->head)
1024 list_info->next=next;
1025 next->next=list_info->head;
1026 list_info->head=next;
1029 if (index == list_info->elements)
1032 list_info->next=next;
1033 list_info->tail->next=next;
1034 list_info->tail=next;
1041 element=list_info->head;
1042 next->next=element->next;
1043 for (i=1; i < (ssize_t) index; i++)
1045 element=element->next;
1046 next->next=element->next;
1050 if (list_info->next == next->next)
1051 list_info->next=next;
1054 list_info->elements++;
1055 UnlockSemaphoreInfo(list_info->semaphore);
1091 MagickExport MagickBooleanType InsertValueInSortedLinkedList(
1092 LinkedListInfo *list_info,
int (*compare)(
const void *,
const void *),
1093 void **replace,
const void *value)
1105 assert(list_info->signature == MagickCoreSignature);
1106 if ((compare == (
int (*)(
const void *,
const void *)) NULL) ||
1107 (value == (
const void *) NULL))
1108 return(MagickFalse);
1109 if (list_info->elements == list_info->capacity)
1110 return(MagickFalse);
1111 next=(
ElementInfo *) AcquireMagickMemory(
sizeof(*next));
1113 return(MagickFalse);
1114 next->value=(
void *) value;
1116 LockSemaphoreInfo(list_info->semaphore);
1117 next->next=list_info->head;
1120 i=(ssize_t) compare(value,next->next->value);
1121 if ((i < 0) || ((replace != (
void **) NULL) && (i == 0)))
1125 *replace=next->next->value;
1126 next->next=next->next->next;
1128 element->next=(
ElementInfo *) RelinquishMagickMemory(
1130 list_info->elements--;
1135 list_info->head=next;
1139 next->next=next->next->next;
1146 list_info->head=next;
1147 list_info->tail=next;
1149 list_info->elements++;
1150 UnlockSemaphoreInfo(list_info->semaphore);
1176 MagickExport MagickBooleanType IsHashmapEmpty(
const HashmapInfo *hashmap_info)
1179 assert(hashmap_info->signature == MagickCoreSignature);
1180 return(hashmap_info->entries == 0 ? MagickTrue : MagickFalse);
1205 MagickExport MagickBooleanType IsLinkedListEmpty(
1209 assert(list_info->signature == MagickCoreSignature);
1210 return(list_info->elements == 0 ? MagickTrue : MagickFalse);
1238 MagickExport MagickBooleanType LinkedListToArray(
LinkedListInfo *list_info,
1248 assert(list_info->signature == MagickCoreSignature);
1249 if (array == (
void **) NULL)
1250 return(MagickFalse);
1251 LockSemaphoreInfo(list_info->semaphore);
1252 next=list_info->head;
1255 array[i]=next->value;
1258 UnlockSemaphoreInfo(list_info->semaphore);
1305 MagickExport
HashmapInfo *NewHashmap(
const size_t capacity,
1306 size_t (*hash)(
const void *),
1307 MagickBooleanType (*compare)(
const void *,
const void *),
1308 void *(*relinquish_key)(
void *),
void *(*relinquish_value)(
void *))
1313 hashmap_info=(
HashmapInfo *) AcquireMagickMemory(
sizeof(*hashmap_info));
1315 ThrowFatalException(ResourceLimitFatalError,
"MemoryAllocationFailed");
1316 (void) memset(hashmap_info,0,
sizeof(*hashmap_info));
1317 hashmap_info->hash=HashPointerType;
1318 if (hash != (
size_t (*)(
const void *)) NULL)
1319 hashmap_info->hash=hash;
1320 hashmap_info->compare=(MagickBooleanType (*)(
const void *,
const void *)) NULL;
1321 if (compare != (MagickBooleanType (*)(
const void *,
const void *)) NULL)
1322 hashmap_info->compare=compare;
1323 hashmap_info->relinquish_key=relinquish_key;
1324 hashmap_info->relinquish_value=relinquish_value;
1325 hashmap_info->entries=0;
1326 hashmap_info->capacity=capacity;
1328 if (~capacity >= 1UL)
1329 hashmap_info->map=(
LinkedListInfo **) AcquireQuantumMemory((
size_t)
1330 capacity+1UL,
sizeof(*hashmap_info->map));
1332 ThrowFatalException(ResourceLimitFatalError,
"MemoryAllocationFailed");
1333 (void) memset(hashmap_info->map,0,(
size_t) capacity*
1334 sizeof(*hashmap_info->map));
1335 hashmap_info->semaphore=AllocateSemaphoreInfo();
1336 hashmap_info->signature=MagickCoreSignature;
1337 return(hashmap_info);
1363 MagickExport
LinkedListInfo *NewLinkedList(
const size_t capacity)
1368 list_info=(
LinkedListInfo *) AcquireMagickMemory(
sizeof(*list_info));
1370 ThrowFatalException(ResourceLimitFatalError,
"MemoryAllocationFailed");
1371 (void) memset(list_info,0,
sizeof(*list_info));
1372 list_info->capacity=capacity == 0 ? (size_t) (~0) : capacity;
1373 list_info->elements=0;
1377 list_info->semaphore=AllocateSemaphoreInfo();
1378 list_info->signature=MagickCoreSignature;
1411 static MagickBooleanType IncreaseHashmapCapacity(
HashmapInfo *hashmap_info)
1413 #define MaxCapacities 20
1416 capacities[MaxCapacities] =
1418 17, 31, 61, 131, 257, 509, 1021, 2053, 4099, 8191, 16381, 32771,
1419 65537, 131071, 262147, 524287, 1048573, 2097143, 4194301, 8388617
1444 for (i=0; i < MaxCapacities; i++)
1445 if (hashmap_info->capacity < capacities[i])
1447 if (i >= (MaxCapacities-1))
1448 return(MagickFalse);
1449 capacity=capacities[i+1];
1450 map=(
LinkedListInfo **) AcquireQuantumMemory((
size_t) capacity+1UL,
1453 return(MagickFalse);
1454 (void) memset(map,0,(
size_t) capacity*
sizeof(*map));
1458 for (i=0; i < (ssize_t) hashmap_info->capacity; i++)
1463 list_info=hashmap_info->map[i];
1466 LockSemaphoreInfo(list_info->semaphore);
1467 for (next=list_info->head; next != (
ElementInfo *) NULL; )
1472 map_info=map[entry->hash % capacity];
1475 map_info=NewLinkedList(0);
1476 map[entry->hash % capacity]=map_info;
1478 map_info->next=element;
1479 element->next=map_info->head;
1480 map_info->head=element;
1481 map_info->elements++;
1483 list_info->signature=(~MagickCoreSignature);
1484 UnlockSemaphoreInfo(list_info->semaphore);
1485 DestroySemaphoreInfo(&list_info->semaphore);
1490 hashmap_info->map=map;
1491 hashmap_info->capacity=capacity;
1495 MagickExport MagickBooleanType PutEntryInHashmap(
HashmapInfo *hashmap_info,
1496 const void *key,
const void *value)
1509 assert(hashmap_info->signature == MagickCoreSignature);
1510 if ((key == (
void *) NULL) || (value == (
void *) NULL))
1511 return(MagickFalse);
1512 next=(
EntryInfo *) AcquireMagickMemory(
sizeof(*next));
1514 return(MagickFalse);
1515 LockSemaphoreInfo(hashmap_info->semaphore);
1516 next->hash=hashmap_info->hash(key);
1517 next->key=(
void *) key;
1518 next->value=(
void *) value;
1519 list_info=hashmap_info->map[next->hash % hashmap_info->capacity];
1522 list_info=NewLinkedList(0);
1523 hashmap_info->map[next->hash % hashmap_info->capacity]=list_info;
1527 list_info->next=list_info->head;
1528 entry=(
EntryInfo *) GetNextValueInLinkedList(list_info);
1529 for (i=0; entry != (
EntryInfo *) NULL; i++)
1531 if (entry->hash == next->hash)
1537 if (hashmap_info->compare !=
1538 (MagickBooleanType (*)(
const void *,
const void *)) NULL)
1539 compare=hashmap_info->compare(key,entry->key);
1540 if (compare != MagickFalse)
1542 (void) RemoveElementFromLinkedList(list_info,i);
1543 if (hashmap_info->relinquish_key != (
void *(*)(
void *)) NULL)
1544 entry->key=hashmap_info->relinquish_key(entry->key);
1545 if (hashmap_info->relinquish_value != (
void *(*)(
void *)) NULL)
1546 entry->value=hashmap_info->relinquish_value(entry->value);
1547 entry=(
EntryInfo *) RelinquishMagickMemory(entry);
1551 entry=(
EntryInfo *) GetNextValueInLinkedList(list_info);
1554 if (InsertValueInLinkedList(list_info,0,next) == MagickFalse)
1556 next=(
EntryInfo *) RelinquishMagickMemory(next);
1557 UnlockSemaphoreInfo(hashmap_info->semaphore);
1558 return(MagickFalse);
1560 if (list_info->elements >= (hashmap_info->capacity-1))
1561 if (IncreaseHashmapCapacity(hashmap_info) == MagickFalse)
1563 UnlockSemaphoreInfo(hashmap_info->semaphore);
1564 return(MagickFalse);
1566 hashmap_info->entries++;
1567 UnlockSemaphoreInfo(hashmap_info->semaphore);
1597 MagickExport
void *RemoveElementByValueFromLinkedList(
LinkedListInfo *list_info,
1604 assert(list_info->signature == MagickCoreSignature);
1605 if ((list_info->elements == 0) || (value == (
const void *) NULL))
1606 return((
void *) NULL);
1607 LockSemaphoreInfo(list_info->semaphore);
1608 if (value == list_info->head->value)
1610 if (list_info->next == list_info->head)
1611 list_info->next=list_info->head->next;
1612 next=list_info->head;
1613 list_info->head=list_info->head->next;
1614 next=(
ElementInfo *) RelinquishMagickMemory(next);
1621 next=list_info->head;
1623 (next->next->value != value))
1627 UnlockSemaphoreInfo(list_info->semaphore);
1628 return((
void *) NULL);
1631 next->next=element->next;
1632 if (element == list_info->tail)
1633 list_info->tail=next;
1634 if (list_info->next == element)
1635 list_info->next=element->next;
1636 element=(
ElementInfo *) RelinquishMagickMemory(element);
1638 list_info->elements--;
1639 UnlockSemaphoreInfo(list_info->semaphore);
1640 return((
void *) value);
1669 MagickExport
void *RemoveElementFromLinkedList(
LinkedListInfo *list_info,
1682 assert(list_info->signature == MagickCoreSignature);
1683 if (index >= list_info->elements)
1684 return((
void *) NULL);
1685 LockSemaphoreInfo(list_info->semaphore);
1688 if (list_info->next == list_info->head)
1689 list_info->next=list_info->head->next;
1690 value=list_info->head->value;
1691 next=list_info->head;
1692 list_info->head=list_info->head->next;
1693 next=(
ElementInfo *) RelinquishMagickMemory(next);
1700 next=list_info->head;
1701 for (i=1; i < (ssize_t) index; i++)
1704 next->next=element->next;
1705 if (element == list_info->tail)
1706 list_info->tail=next;
1707 if (list_info->next == element)
1708 list_info->next=element->next;
1709 value=element->value;
1710 element=(
ElementInfo *) RelinquishMagickMemory(element);
1712 list_info->elements--;
1713 UnlockSemaphoreInfo(list_info->semaphore);
1741 MagickExport
void *RemoveEntryFromHashmap(
HashmapInfo *hashmap_info,
1760 assert(hashmap_info->signature == MagickCoreSignature);
1761 if (key == (
const void *) NULL)
1762 return((
void *) NULL);
1763 LockSemaphoreInfo(hashmap_info->semaphore);
1764 hash=hashmap_info->hash(key);
1765 list_info=hashmap_info->map[hash % hashmap_info->capacity];
1768 list_info->next=list_info->head;
1769 entry=(
EntryInfo *) GetNextValueInLinkedList(list_info);
1770 for (i=0; entry != (
EntryInfo *) NULL; i++)
1772 if (entry->hash == hash)
1778 if (hashmap_info->compare !=
1779 (MagickBooleanType (*)(
const void *,
const void *)) NULL)
1780 compare=hashmap_info->compare(key,entry->key);
1781 if (compare != MagickFalse)
1783 entry=(
EntryInfo *) RemoveElementFromLinkedList(list_info,i);
1786 UnlockSemaphoreInfo(hashmap_info->semaphore);
1787 return((
void *) NULL);
1789 if (hashmap_info->relinquish_key != (
void *(*)(
void *)) NULL)
1790 entry->key=hashmap_info->relinquish_key(entry->key);
1792 entry=(
EntryInfo *) RelinquishMagickMemory(entry);
1793 hashmap_info->entries--;
1794 UnlockSemaphoreInfo(hashmap_info->semaphore);
1798 entry=(
EntryInfo *) GetNextValueInLinkedList(list_info);
1801 UnlockSemaphoreInfo(hashmap_info->semaphore);
1802 return((
void *) NULL);
1828 MagickExport
void *RemoveLastElementFromLinkedList(
LinkedListInfo *list_info)
1834 assert(list_info->signature == MagickCoreSignature);
1835 if (list_info->elements == 0)
1836 return((
void *) NULL);
1837 LockSemaphoreInfo(list_info->semaphore);
1838 if (list_info->next == list_info->tail)
1840 if (list_info->elements == 1UL)
1842 value=list_info->head->value;
1844 list_info->tail=(
ElementInfo *) RelinquishMagickMemory(list_info->tail);
1851 value=list_info->tail->value;
1852 next=list_info->head;
1853 while (next->next != list_info->tail)
1855 list_info->tail=(
ElementInfo *) RelinquishMagickMemory(list_info->tail);
1856 list_info->tail=next;
1859 list_info->elements--;
1860 UnlockSemaphoreInfo(list_info->semaphore);
1887 MagickExport
void ResetHashmapIterator(
HashmapInfo *hashmap_info)
1890 assert(hashmap_info->signature == MagickCoreSignature);
1891 LockSemaphoreInfo(hashmap_info->semaphore);
1892 hashmap_info->next=0;
1893 hashmap_info->head_of_list=MagickFalse;
1894 UnlockSemaphoreInfo(hashmap_info->semaphore);
1921 MagickExport
void ResetLinkedListIterator(
LinkedListInfo *list_info)
1924 assert(list_info->signature == MagickCoreSignature);
1925 LockSemaphoreInfo(list_info->semaphore);
1926 list_info->next=list_info->head;
1927 UnlockSemaphoreInfo(list_info->semaphore);