granicus.if.org Git - imagemagick/blob - MagickCore/hashmap.c

   1 /*
   2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   3 %                                                                             %
   4 %                                                                             %
   5 %                                                                             %
   6 %                H   H   AAA   SSSSS  H   H  M   M   AAA   PPPP               %
   7 %                H   H  A   A  SS     H   H  MM MM  A   A  P   P              %
   8 %                HHHHH  AAAAA   SSS   HHHHH  M M M  AAAAA  PPPP               %
   9 %                H   H  A   A     SS  H   H  M   M  A   A  P                  %
  10 %                H   H  A   A  SSSSS  H   H  M   M  A   A  P                  %
  11 %                                                                             %
  12 %                                                                             %
  13 %                  MagickCore Hash-map and Linked-list Methods                %
  14 %                                                                             %
  15 %                              Software Design                                %
  16 %                                   Cristy                                    %
  17 %                               December 2002                                 %
  18 %                                                                             %
  19 %                                                                             %
  20 %  Copyright 1999-2014 ImageMagick Studio LLC, a non-profit organization      %
  21 %  dedicated to making software imaging solutions freely available.           %
  22 %                                                                             %
  23 %  You may not use this file except in compliance with the License.  You may  %
  24 %  obtain a copy of the License at                                            %
  25 %                                                                             %
  26 %    http://www.imagemagick.org/script/license.php                            %
  27 %                                                                             %
  28 %  Unless required by applicable law or agreed to in writing, software        %
  29 %  distributed under the License is distributed on an "AS IS" BASIS,          %
  30 %  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.   %
  31 %  See the License for the specific language governing permissions and        %
  32 %  limitations under the License.                                             %
  33 %                                                                             %
  34 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  35 %
  36 %  This module implements the standard handy hash and linked-list methods for
  37 %  storing and retrieving large numbers of data elements.  It is loosely based
  38 %  on the Java implementation of these algorithms.
  39 %
  40 */
  41 \f
  42 /*
  43   Include declarations.
  44 */
  45 #include "MagickCore/studio.h"
  46 #include "MagickCore/exception.h"
  47 #include "MagickCore/exception-private.h"
  48 #include "MagickCore/hashmap.h"
  49 #include "MagickCore/memory_.h"
  50 #include "MagickCore/semaphore.h"
  51 #include "MagickCore/signature-private.h"
  52 #include "MagickCore/string_.h"
  53 \f
  54 /*
  55   Typedef declarations.
  56 */
  57 typedef struct _ElementInfo
  58 {
  59   void
  60     *value;
  61
  62   struct _ElementInfo
  63     *next;
  64 } ElementInfo;
  65
  66 typedef struct _EntryInfo
  67 {
  68   size_t
  69     hash;
  70
  71   void
  72     *key,
  73     *value;
  74 } EntryInfo;
  75
  76 struct _LinkedListInfo
  77 {
  78   size_t
  79     capacity,
  80     elements;
  81
  82   ElementInfo
  83     *head,
  84     *tail,
  85     *next;
  86
  87   SemaphoreInfo
  88     *semaphore;
  89
  90   size_t
  91     signature;
  92 };
  93
  94 struct _HashmapInfo
  95 {
  96   size_t
  97     (*hash)(const void *);
  98
  99   MagickBooleanType
 100     (*compare)(const void *,const void *);
 101
 102   void
 103     *(*relinquish_key)(void *),
 104     *(*relinquish_value)(void *);
 105
 106   size_t
 107     capacity,
 108     entries,
 109     next;
 110
 111   MagickBooleanType
 112     head_of_list;
 113
 114   LinkedListInfo
 115     **map;
 116
 117   SemaphoreInfo
 118     *semaphore;
 119
 120   size_t
 121     signature;
 122 };
 123 \f
 124 /*
 125 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 126 %                                                                             %
 127 %                                                                             %
 128 %                                                                             %
 129 %   A p p e n d V a l u e T o L i n k e d L i s t                             %
 130 %                                                                             %
 131 %                                                                             %
 132 %                                                                             %
 133 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 134 %
 135 %  AppendValueToLinkedList() appends a value to the end of the linked-list.
 136 %
 137 %  The format of the AppendValueToLinkedList method is:
 138 %
 139 %      MagickBooleanType AppendValueToLinkedList(LinkedListInfo *list_info,
 140 %        const void *value)
 141 %
 142 %  A description of each parameter follows:
 143 %
 144 %    o list_info: the linked-list info.
 145 %
 146 %    o value: the value.
 147 %
 148 */
 149 MagickExport MagickBooleanType AppendValueToLinkedList(
 150   LinkedListInfo *list_info,const void *value)
 151 {
 152   register ElementInfo
 153     *next;
 154
 155   assert(list_info != (LinkedListInfo *) NULL);
 156   assert(list_info->signature == MagickSignature);
 157   if (list_info->elements == list_info->capacity)
 158     return(MagickFalse);
 159   next=(ElementInfo *) AcquireMagickMemory(sizeof(*next));
 160   if (next == (ElementInfo *) NULL)
 161     return(MagickFalse);
 162   next->value=(void *) value;
 163   next->next=(ElementInfo *) NULL;
 164   LockSemaphoreInfo(list_info->semaphore);
 165   if (list_info->next == (ElementInfo *) NULL)
 166     list_info->next=next;
 167   if (list_info->elements == 0)
 168     list_info->head=next;
 169   else
 170     list_info->tail->next=next;
 171   list_info->tail=next;
 172   list_info->elements++;
 173   UnlockSemaphoreInfo(list_info->semaphore);
 174   return(MagickTrue);
 175 }
 176 \f
 177 /*
 178 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 179 %                                                                             %
 180 %                                                                             %
 181 %                                                                             %
 182 %   C l e a r L i n k e d L i s t                                             %
 183 %                                                                             %
 184 %                                                                             %
 185 %                                                                             %
 186 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 187 %
 188 %  ClearLinkedList() clears all the elements from the linked-list.
 189 %
 190 %  The format of the ClearLinkedList method is:
 191 %
 192 %      void ClearLinkedList(LinkedListInfo *list_info,
 193 %        void *(*relinquish_value)(void *))
 194 %
 195 %  A description of each parameter follows:
 196 %
 197 %    o list_info: the linked-list info.
 198 %
 199 %    o relinquish_value: the value deallocation method; typically
 200 %      RelinquishMagickMemory().
 201 %
 202 */
 203 MagickExport void ClearLinkedList(LinkedListInfo *list_info,
 204   void *(*relinquish_value)(void *))
 205 {
 206   ElementInfo
 207     *element;
 208
 209   register ElementInfo
 210     *next;
 211
 212   assert(list_info != (LinkedListInfo *) NULL);
 213   assert(list_info->signature == MagickSignature);
 214   LockSemaphoreInfo(list_info->semaphore);
 215   next=list_info->head;
 216   while (next != (ElementInfo *) NULL)
 217   {
 218     if (relinquish_value != (void *(*)(void *)) NULL)
 219       next->value=relinquish_value(next->value);
 220     element=next;
 221     next=next->next;
 222     element=(ElementInfo *) RelinquishMagickMemory(element);
 223   }
 224   list_info->head=(ElementInfo *) NULL;
 225   list_info->tail=(ElementInfo *) NULL;
 226   list_info->next=(ElementInfo *) NULL;
 227   list_info->elements=0;
 228   UnlockSemaphoreInfo(list_info->semaphore);
 229 }
 230 \f
 231 /*
 232 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 233 %                                                                             %
 234 %                                                                             %
 235 %                                                                             %
 236 %   C o m p a r e H a s h m a p S t r i n g                                   %
 237 %                                                                             %
 238 %                                                                             %
 239 %                                                                             %
 240 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 241 %
 242 %  CompareHashmapString() finds an entry in a hash-map based on the contents
 243 %  of a string.
 244 %
 245 %  The format of the CompareHashmapString method is:
 246 %
 247 %      MagickBooleanType CompareHashmapString(const void *target,
 248 %        const void *source)
 249 %
 250 %  A description of each parameter follows:
 251 %
 252 %    o target: the target string.
 253 %
 254 %    o source: the source string.
 255 %
 256 */
 257 MagickExport MagickBooleanType CompareHashmapString(const void *target,
 258   const void *source)
 259 {
 260   const char
 261     *p,
 262     *q;
 263
 264   p=(const char *) target;
 265   q=(const char *) source;
 266   return(IsMagickTrue(LocaleCompare(p,q)));
 267 }
 268 \f
 269 /*
 270 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 271 %                                                                             %
 272 %                                                                             %
 273 %                                                                             %
 274 %   C o m p a r e H a s h m a p S t r i n g I n f o                           %
 275 %                                                                             %
 276 %                                                                             %
 277 %                                                                             %
 278 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 279 %
 280 %  CompareHashmapStringInfo() finds an entry in a hash-map based on the
 281 %  contents of a string.
 282 %
 283 %  The format of the CompareHashmapStringInfo method is:
 284 %
 285 %      MagickBooleanType CompareHashmapStringInfo(const void *target,
 286 %        const void *source)
 287 %
 288 %  A description of each parameter follows:
 289 %
 290 %    o target: the target string.
 291 %
 292 %    o source: the source string.
 293 %
 294 */
 295 MagickExport MagickBooleanType CompareHashmapStringInfo(const void *target,
 296   const void *source)
 297 {
 298   return(IsMagickTrue(LocaleCompare((const char *)target,
 299            (const char *)source)));
 300 }
 301 \f
 302 /*
 303 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 304 %                                                                             %
 305 %                                                                             %
 306 %                                                                             %
 307 %   D e s t r o y H a s h m a p                                               %
 308 %                                                                             %
 309 %                                                                             %
 310 %                                                                             %
 311 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 312 %
 313 %  DestroyHashmap() frees the hash-map and all associated resources.
 314 %
 315 %  The format of the DestroyHashmap method is:
 316 %
 317 %      HashmapInfo *DestroyHashmap(HashmapInfo *hashmap_info)
 318 %
 319 %  A description of each parameter follows:
 320 %
 321 %    o hashmap_info: the hashmap info.
 322 %
 323 */
 324 MagickExport HashmapInfo *DestroyHashmap(HashmapInfo *hashmap_info)
 325 {
 326   LinkedListInfo
 327     *list_info;
 328
 329   register EntryInfo
 330     *entry;
 331
 332   register ssize_t
 333     i;
 334
 335   assert(hashmap_info != (HashmapInfo *) NULL);
 336   assert(hashmap_info->signature == MagickSignature);
 337   LockSemaphoreInfo(hashmap_info->semaphore);
 338   for (i=0; i < (ssize_t) hashmap_info->capacity; i++)
 339   {
 340     list_info=hashmap_info->map[i];
 341     if (list_info != (LinkedListInfo *) NULL)
 342       {
 343         list_info->next=list_info->head;
 344         entry=(EntryInfo *) GetNextValueInLinkedList(list_info);
 345         while (entry != (EntryInfo *) NULL)
 346         {
 347           if (hashmap_info->relinquish_key != (void *(*)(void *)) NULL)
 348             entry->key=hashmap_info->relinquish_key(entry->key);
 349           if (hashmap_info->relinquish_value != (void *(*)(void *)) NULL)
 350             entry->value=hashmap_info->relinquish_value(entry->value);
 351           entry=(EntryInfo *) GetNextValueInLinkedList(list_info);
 352         }
 353       }
 354     if (list_info != (LinkedListInfo *) NULL)
 355       list_info=DestroyLinkedList(list_info,RelinquishMagickMemory);
 356   }
 357   hashmap_info->map=(LinkedListInfo **) RelinquishMagickMemory(
 358     hashmap_info->map);
 359   hashmap_info->signature=(~MagickSignature);
 360   UnlockSemaphoreInfo(hashmap_info->semaphore);
 361   RelinquishSemaphoreInfo(&hashmap_info->semaphore);
 362   hashmap_info=(HashmapInfo *) RelinquishMagickMemory(hashmap_info);
 363   return(hashmap_info);
 364 }
 365 \f
 366 /*
 367 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 368 %                                                                             %
 369 %                                                                             %
 370 %                                                                             %
 371 %   D e s t r o y L i n k e d L i s t                                         %
 372 %                                                                             %
 373 %                                                                             %
 374 %                                                                             %
 375 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 376 %
 377 %  DestroyLinkedList() frees the linked-list and all associated resources.
 378 %
 379 %  The format of the DestroyLinkedList method is:
 380 %
 381 %      LinkedListInfo *DestroyLinkedList(LinkedListInfo *list_info,
 382 %        void *(*relinquish_value)(void *))
 383 %
 384 %  A description of each parameter follows:
 385 %
 386 %    o list_info: the linked-list info.
 387 %
 388 %    o relinquish_value: the value deallocation method;  typically
 389 %      RelinquishMagickMemory().
 390 %
 391 */
 392 MagickExport LinkedListInfo *DestroyLinkedList(LinkedListInfo *list_info,
 393   void *(*relinquish_value)(void *))
 394 {
 395   ElementInfo
 396     *entry;
 397
 398   register ElementInfo
 399     *next;
 400
 401   assert(list_info != (LinkedListInfo *) NULL);
 402   assert(list_info->signature == MagickSignature);
 403   LockSemaphoreInfo(list_info->semaphore);
 404   for (next=list_info->head; next != (ElementInfo *) NULL; )
 405   {
 406     if (relinquish_value != (void *(*)(void *)) NULL)
 407       next->value=relinquish_value(next->value);
 408     entry=next;
 409     next=next->next;
 410     entry=(ElementInfo *) RelinquishMagickMemory(entry);
 411   }
 412   list_info->signature=(~MagickSignature);
 413   UnlockSemaphoreInfo(list_info->semaphore);
 414   RelinquishSemaphoreInfo(&list_info->semaphore);
 415   list_info=(LinkedListInfo *) RelinquishMagickMemory(list_info);
 416   return(list_info);
 417 }
 418 \f
 419 /*
 420 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 421 %                                                                             %
 422 %                                                                             %
 423 %                                                                             %
 424 %   G e t L a s t V a l u e I n L i n k e d L i s t                           %
 425 %                                                                             %
 426 %                                                                             %
 427 %                                                                             %
 428 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 429 %
 430 %  GetLastValueInLinkedList() gets the last value in the linked-list.
 431 %
 432 %  The format of the GetLastValueInLinkedList method is:
 433 %
 434 %      void *GetLastValueInLinkedList(LinkedListInfo *list_info)
 435 %
 436 %  A description of each parameter follows:
 437 %
 438 %    o list_info: the linked_list info.
 439 %
 440 */
 441 MagickExport void *GetLastValueInLinkedList(LinkedListInfo *list_info)
 442 {
 443   void
 444     *value;
 445
 446   assert(list_info != (LinkedListInfo *) NULL);
 447   assert(list_info->signature == MagickSignature);
 448   if (list_info->elements == 0)
 449     return((void *) NULL);
 450   LockSemaphoreInfo(list_info->semaphore);
 451   value=list_info->tail->value;
 452   UnlockSemaphoreInfo(list_info->semaphore);
 453   return(value);
 454 }
 455 \f
 456 /*
 457 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 458 %                                                                             %
 459 %                                                                             %
 460 %                                                                             %
 461 %   G e t N e x t K e y I n H a s h m a p                                     %
 462 %                                                                             %
 463 %                                                                             %
 464 %                                                                             %
 465 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 466 %
 467 %  GetNextKeyInHashmap() gets the next key in the hash-map.
 468 %
 469 %  The format of the GetNextKeyInHashmap method is:
 470 %
 471 %      void *GetNextKeyInHashmap(HashmapInfo *hashmap_info)
 472 %
 473 %  A description of each parameter follows:
 474 %
 475 %    o hashmap_info: the hashmap info.
 476 %
 477 */
 478 MagickExport void *GetNextKeyInHashmap(HashmapInfo *hashmap_info)
 479 {
 480   LinkedListInfo
 481     *list_info;
 482
 483   register EntryInfo
 484     *entry;
 485
 486   void
 487     *key;
 488
 489   assert(hashmap_info != (HashmapInfo *) NULL);
 490   assert(hashmap_info->signature == MagickSignature);
 491   LockSemaphoreInfo(hashmap_info->semaphore);
 492   while (hashmap_info->next < hashmap_info->capacity)
 493   {
 494     list_info=hashmap_info->map[hashmap_info->next];
 495     if (list_info != (LinkedListInfo *) NULL)
 496       {
 497         if (IfMagickFalse(hashmap_info->head_of_list))
 498           {
 499             list_info->next=list_info->head;
 500             hashmap_info->head_of_list=MagickTrue;
 501           }
 502         entry=(EntryInfo *) GetNextValueInLinkedList(list_info);
 503         if (entry != (EntryInfo *) NULL)
 504           {
 505             key=entry->key;
 506             UnlockSemaphoreInfo(hashmap_info->semaphore);
 507             return(key);
 508           }
 509         hashmap_info->head_of_list=MagickFalse;
 510       }
 511     hashmap_info->next++;
 512   }
 513   UnlockSemaphoreInfo(hashmap_info->semaphore);
 514   return((void *) NULL);
 515 }
 516 \f
 517 /*
 518 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 519 %                                                                             %
 520 %                                                                             %
 521 %                                                                             %
 522 %   G e t N e x t V a l u e I n H a s h m a p                                 %
 523 %                                                                             %
 524 %                                                                             %
 525 %                                                                             %
 526 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 527 %
 528 %  GetNextValueInHashmap() gets the next value in the hash-map.
 529 %
 530 %  The format of the GetNextValueInHashmap method is:
 531 %
 532 %      void *GetNextValueInHashmap(HashmapInfo *hashmap_info)
 533 %
 534 %  A description of each parameter follows:
 535 %
 536 %    o hashmap_info: the hashmap info.
 537 %
 538 */
 539 MagickExport void *GetNextValueInHashmap(HashmapInfo *hashmap_info)
 540 {
 541   LinkedListInfo
 542     *list_info;
 543
 544   register EntryInfo
 545     *entry;
 546
 547   void
 548     *value;
 549
 550   assert(hashmap_info != (HashmapInfo *) NULL);
 551   assert(hashmap_info->signature == MagickSignature);
 552   LockSemaphoreInfo(hashmap_info->semaphore);
 553   while (hashmap_info->next < hashmap_info->capacity)
 554   {
 555     list_info=hashmap_info->map[hashmap_info->next];
 556     if (list_info != (LinkedListInfo *) NULL)
 557       {
 558         if (IfMagickFalse(hashmap_info->head_of_list))
 559           {
 560             list_info->next=list_info->head;
 561             hashmap_info->head_of_list=MagickTrue;
 562           }
 563         entry=(EntryInfo *) GetNextValueInLinkedList(list_info);
 564         if (entry != (EntryInfo *) NULL)
 565           {
 566             value=entry->value;
 567             UnlockSemaphoreInfo(hashmap_info->semaphore);
 568             return(value);
 569           }
 570         hashmap_info->head_of_list=MagickFalse;
 571       }
 572     hashmap_info->next++;
 573   }
 574   UnlockSemaphoreInfo(hashmap_info->semaphore);
 575   return((void *) NULL);
 576 }
 577 \f
 578 /*
 579 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 580 %                                                                             %
 581 %                                                                             %
 582 %                                                                             %
 583 %   G e t N e x t V a l u e I n L i n k e d L i s t                           %
 584 %                                                                             %
 585 %                                                                             %
 586 %                                                                             %
 587 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 588 %
 589 %  GetNextValueInLinkedList() gets the next value in the linked-list.
 590 %
 591 %  The format of the GetNextValueInLinkedList method is:
 592 %
 593 %      void *GetNextValueInLinkedList(LinkedListInfo *list_info)
 594 %
 595 %  A description of each parameter follows:
 596 %
 597 %    o list_info: the linked-list info.
 598 %
 599 */
 600 MagickExport void *GetNextValueInLinkedList(LinkedListInfo *list_info)
 601 {
 602   void
 603     *value;
 604
 605   assert(list_info != (LinkedListInfo *) NULL);
 606   assert(list_info->signature == MagickSignature);
 607   LockSemaphoreInfo(list_info->semaphore);
 608   if (list_info->next == (ElementInfo *) NULL)
 609     {
 610       UnlockSemaphoreInfo(list_info->semaphore);
 611       return((void *) NULL);
 612     }
 613   value=list_info->next->value;
 614   list_info->next=list_info->next->next;
 615   UnlockSemaphoreInfo(list_info->semaphore);
 616   return(value);
 617 }
 618 \f
 619 /*
 620 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 621 %                                                                             %
 622 %                                                                             %
 623 %                                                                             %
 624 %   G e t N u m b e r O f E n t r i e s I n H a s h m a p                     %
 625 %                                                                             %
 626 %                                                                             %
 627 %                                                                             %
 628 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 629 %
 630 %  GetNumberOfEntriesInHashmap() returns the number of entries in the hash-map.
 631 %
 632 %  The format of the GetNumberOfEntriesInHashmap method is:
 633 %
 634 %      size_t GetNumberOfEntriesInHashmap(const HashmapInfo *hashmap_info)
 635 %
 636 %  A description of each parameter follows:
 637 %
 638 %    o hashmap_info: the hashmap info.
 639 %
 640 */
 641 MagickExport size_t GetNumberOfEntriesInHashmap(
 642   const HashmapInfo *hashmap_info)
 643 {
 644   assert(hashmap_info != (HashmapInfo *) NULL);
 645   assert(hashmap_info->signature == MagickSignature);
 646   return(hashmap_info->entries);
 647 }
 648 \f
 649 /*
 650 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 651 %                                                                             %
 652 %                                                                             %
 653 %                                                                             %
 654 %   G e t N u m b e r O f E l e m e n t s I n L i n k e d L i s t             %
 655 %                                                                             %
 656 %                                                                             %
 657 %                                                                             %
 658 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 659 %
 660 %  GetNumberOfElementsInLinkedList() returns the number of entries in the
 661 %  linked-list.
 662 %
 663 %  The format of the GetNumberOfElementsInLinkedList method is:
 664 %
 665 %      size_t GetNumberOfElementsInLinkedList(
 666 %        const LinkedListInfo *list_info)
 667 %
 668 %  A description of each parameter follows:
 669 %
 670 %    o list_info: the linked-list info.
 671 %
 672 */
 673 MagickExport size_t GetNumberOfElementsInLinkedList(
 674   const LinkedListInfo *list_info)
 675 {
 676   assert(list_info != (LinkedListInfo *) NULL);
 677   assert(list_info->signature == MagickSignature);
 678   return(list_info->elements);
 679 }
 680 \f
 681 /*
 682 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 683 %                                                                             %
 684 %                                                                             %
 685 %                                                                             %
 686 %   G e t V a l u e F r o m H a s h m a p                                     %
 687 %                                                                             %
 688 %                                                                             %
 689 %                                                                             %
 690 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 691 %
 692 %  GetValueFromHashmap() gets an entry from the hash-map by its key.
 693 %
 694 %  The format of the GetValueFromHashmap method is:
 695 %
 696 %      void *GetValueFromHashmap(HashmapInfo *hashmap_info,const void *key)
 697 %
 698 %  A description of each parameter follows:
 699 %
 700 %    o hashmap_info: the hashmap info.
 701 %
 702 %    o key: the key.
 703 %
 704 */
 705 MagickExport void *GetValueFromHashmap(HashmapInfo *hashmap_info,
 706   const void *key)
 707 {
 708   LinkedListInfo
 709     *list_info;
 710
 711   register EntryInfo
 712     *entry;
 713
 714   size_t
 715     hash;
 716
 717   void
 718     *value;
 719
 720   assert(hashmap_info != (HashmapInfo *) NULL);
 721   assert(hashmap_info->signature == MagickSignature);
 722   if (key == (const void *) NULL)
 723     return((void *) NULL);
 724   LockSemaphoreInfo(hashmap_info->semaphore);
 725   hash=hashmap_info->hash(key);
 726   list_info=hashmap_info->map[hash % hashmap_info->capacity];
 727   if (list_info != (LinkedListInfo *) NULL)
 728     {
 729       list_info->next=list_info->head;
 730       entry=(EntryInfo *) GetNextValueInLinkedList(list_info);
 731       while (entry != (EntryInfo *) NULL)
 732       {
 733         if (entry->hash == hash)
 734           {
 735             MagickBooleanType
 736               compare;
 737
 738             compare=MagickTrue;
 739             if (hashmap_info->compare !=
 740                 (MagickBooleanType (*)(const void *,const void *)) NULL)
 741               compare=hashmap_info->compare(key,entry->key);
 742             if (IfMagickTrue(compare))
 743               {
 744                 value=entry->value;
 745                 UnlockSemaphoreInfo(hashmap_info->semaphore);
 746                 return(value);
 747               }
 748           }
 749         entry=(EntryInfo *) GetNextValueInLinkedList(list_info);
 750       }
 751     }
 752   UnlockSemaphoreInfo(hashmap_info->semaphore);
 753   return((void *) NULL);
 754 }
 755 \f
 756 /*
 757 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 758 %                                                                             %
 759 %                                                                             %
 760 %                                                                             %
 761 %   G e t V a l u e F r o m L i n k e d L i s t                               %
 762 %                                                                             %
 763 %                                                                             %
 764 %                                                                             %
 765 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 766 %
 767 %  GetValueFromLinkedList() gets a value from the linked-list at the specified
 768 %  location.
 769 %
 770 %  The format of the GetValueFromLinkedList method is:
 771 %
 772 %      void *GetValueFromLinkedList(LinkedListInfo *list_info,
 773 %        const size_t index)
 774 %
 775 %  A description of each parameter follows:
 776 %
 777 %    o list_info: the linked_list info.
 778 %
 779 %    o index: the list index.
 780 %
 781 */
 782 MagickExport void *GetValueFromLinkedList(LinkedListInfo *list_info,
 783   const size_t index)
 784 {
 785   register ElementInfo
 786     *next;
 787
 788   register ssize_t
 789     i;
 790
 791   void
 792     *value;
 793
 794   assert(list_info != (LinkedListInfo *) NULL);
 795   assert(list_info->signature == MagickSignature);
 796   if (index >= list_info->elements)
 797     return((void *) NULL);
 798   LockSemaphoreInfo(list_info->semaphore);
 799   if (index == 0)
 800     {
 801       value=list_info->head->value;
 802       UnlockSemaphoreInfo(list_info->semaphore);
 803       return(value);
 804     }
 805   if (index == (list_info->elements-1))
 806     {
 807       value=list_info->tail->value;
 808       UnlockSemaphoreInfo(list_info->semaphore);
 809       return(value);
 810     }
 811   next=list_info->head;
 812   for (i=0; i < (ssize_t) index; i++)
 813     next=next->next;
 814   value=next->value;
 815   UnlockSemaphoreInfo(list_info->semaphore);
 816   return(value);
 817 }
 818 \f
 819 /*
 820 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 821 %                                                                             %
 822 %                                                                             %
 823 %                                                                             %
 824 %   H a s h P o i n t e r T y p e                                             %
 825 %                                                                             %
 826 %                                                                             %
 827 %                                                                             %
 828 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 829 %
 830 %  HashPointerType() finds an entry in a hash-map based on the address of a
 831 %  pointer.
 832 %
 833 %  The format of the HashPointerType method is:
 834 %
 835 %      size_t HashPointerType(const void *pointer)
 836 %
 837 %  A description of each parameter follows:
 838 %
 839 %    o pointer: compute the hash entry location from this pointer address.
 840 %
 841 */
 842 MagickExport size_t HashPointerType(const void *pointer)
 843 {
 844   size_t
 845     hash;
 846
 847   hash=(size_t) pointer;
 848   hash+=(~(hash << 9));
 849   hash^=(hash >> 14);
 850   hash+=(hash << 4);
 851   hash^=(hash >> 10);
 852   return(hash);
 853 }
 854 \f
 855 /*
 856 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 857 %                                                                             %
 858 %                                                                             %
 859 %                                                                             %
 860 %   H a s h S t r i n g T y p e                                               %
 861 %                                                                             %
 862 %                                                                             %
 863 %                                                                             %
 864 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 865 %
 866 %  HashStringType() finds an entry in a hash-map based on the contents of a
 867 %  string.
 868 %
 869 %  The format of the HashStringType method is:
 870 %
 871 %      size_t HashStringType(const void *string)
 872 %
 873 %  A description of each parameter follows:
 874 %
 875 %    o string: compute the hash entry location from this string.
 876 %
 877 */
 878 MagickExport size_t HashStringType(const void *string)
 879 {
 880   const unsigned char
 881     *digest;
 882
 883   register ssize_t
 884     i;
 885
 886   SignatureInfo
 887     *signature_info;
 888
 889   size_t
 890     hash;
 891
 892   StringInfo
 893     *signature;
 894
 895   signature_info=AcquireSignatureInfo();
 896   signature=StringToStringInfo((const char *) string);
 897   UpdateSignature(signature_info,signature);
 898   FinalizeSignature(signature_info);
 899   digest=GetStringInfoDatum(GetSignatureDigest(signature_info));
 900   hash=0;
 901   for (i=0; i < 8; i++)
 902     hash^=digest[i];
 903   signature=DestroyStringInfo(signature);
 904   signature_info=DestroySignatureInfo(signature_info);
 905   return(hash);
 906 }
 907 \f
 908 /*
 909 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 910 %                                                                             %
 911 %                                                                             %
 912 %                                                                             %
 913 %   H a s h S t r i n g I n f o T y p e                                       %
 914 %                                                                             %
 915 %                                                                             %
 916 %                                                                             %
 917 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 918 %
 919 %  Specify the HashStringInfoType() method in NewHashmap() to find an entry
 920 %  in a hash-map based on the contents of a string.
 921 %
 922 %  The format of the HashStringInfoType method is:
 923 %
 924 %      size_t HashStringInfoType(const void *string_info)
 925 %
 926 %  A description of each parameter follows:
 927 %
 928 %    o string_info: compute the hash entry location from this string.
 929 %
 930 */
 931 MagickExport size_t HashStringInfoType(const void *string_info)
 932 {
 933   const unsigned char
 934     *digest;
 935
 936   register ssize_t
 937     i;
 938
 939   SignatureInfo
 940     *signature_info;
 941
 942   size_t
 943     hash;
 944
 945   signature_info=AcquireSignatureInfo();
 946   UpdateSignature(signature_info,(const StringInfo *) string_info);
 947   FinalizeSignature(signature_info);
 948   digest=GetStringInfoDatum(GetSignatureDigest(signature_info));
 949   hash=0;
 950   for (i=0; i < 8; i++)
 951     hash^=digest[i];
 952   signature_info=DestroySignatureInfo(signature_info);
 953   return(hash);
 954 }
 955 \f
 956 /*
 957 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 958 %                                                                             %
 959 %                                                                             %
 960 %                                                                             %
 961 %   I n s e r t V a l u e I n L i n k e d L i s t                             %
 962 %                                                                             %
 963 %                                                                             %
 964 %                                                                             %
 965 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 966 %
 967 %  InsertValueInLinkedList() inserts an element in the linked-list at the
 968 %  specified location.
 969 %
 970 %  The format of the InsertValueInLinkedList method is:
 971 %
 972 %      MagickBooleanType InsertValueInLinkedList(ListInfo *list_info,
 973 %        const size_t index,const void *value)
 974 %
 975 %  A description of each parameter follows:
 976 %
 977 %    o list_info: the hashmap info.
 978 %
 979 %    o index: the index.
 980 %
 981 %    o value: the value.
 982 %
 983 */
 984 MagickExport MagickBooleanType InsertValueInLinkedList(
 985   LinkedListInfo *list_info,const size_t index,const void *value)
 986 {
 987   register ElementInfo
 988     *next;
 989
 990   register ssize_t
 991     i;
 992
 993   assert(list_info != (LinkedListInfo *) NULL);
 994   assert(list_info->signature == MagickSignature);
 995   if (value == (const void *) NULL)
 996     return(MagickFalse);
 997   if ((index > list_info->elements) ||
 998       (list_info->elements == list_info->capacity))
 999     return(MagickFalse);
1000   next=(ElementInfo *) AcquireMagickMemory(sizeof(*next));
1001   if (next == (ElementInfo *) NULL)
1002     return(MagickFalse);
1003   next->value=(void *) value;
1004   next->next=(ElementInfo *) NULL;
1005   LockSemaphoreInfo(list_info->semaphore);
1006   if (list_info->elements == 0)
1007     {
1008       if (list_info->next == (ElementInfo *) NULL)
1009         list_info->next=next;
1010       list_info->head=next;
1011       list_info->tail=next;
1012     }
1013   else
1014     {
1015       if (index == 0)
1016         {
1017           if (list_info->next == list_info->head)
1018             list_info->next=next;
1019           next->next=list_info->head;
1020           list_info->head=next;
1021         }
1022       else
1023         if (index == list_info->elements)
1024           {
1025             if (list_info->next == (ElementInfo *) NULL)
1026               list_info->next=next;
1027             list_info->tail->next=next;
1028             list_info->tail=next;
1029           }
1030         else
1031           {
1032             ElementInfo
1033               *element;
1034
1035             element=list_info->head;
1036             next->next=element->next;
1037             for (i=1; i < (ssize_t) index; i++)
1038             {
1039               element=element->next;
1040               next->next=element->next;
1041             }
1042             next=next->next;
1043             element->next=next;
1044             if (list_info->next == next->next)
1045               list_info->next=next;
1046           }
1047     }
1048   list_info->elements++;
1049   UnlockSemaphoreInfo(list_info->semaphore);
1050   return(MagickTrue);
1051 }
1052 \f
1053 /*
1054 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1055 %                                                                             %
1056 %                                                                             %
1057 %                                                                             %
1058 %   I n s e r t V a l u e I n S o r t e d L i n k e d L i s t                 %
1059 %                                                                             %
1060 %                                                                             %
1061 %                                                                             %
1062 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1063 %
1064 %  InsertValueInSortedLinkedList() inserts a value in the sorted linked-list.
1065 %
1066 %  The format of the InsertValueInSortedLinkedList method is:
1067 %
1068 %      MagickBooleanType InsertValueInSortedLinkedList(ListInfo *list_info,
1069 %        int (*compare)(const void *,const void *),void **replace,
1070 %        const void *value)
1071 %
1072 %  A description of each parameter follows:
1073 %
1074 %    o list_info: the hashmap info.
1075 %
1076 %    o index: the index.
1077 %
1078 %    o compare: the compare method.
1079 %
1080 %    o replace: return previous element here.
1081 %
1082 %    o value: the value.
1083 %
1084 */
1085 MagickExport MagickBooleanType InsertValueInSortedLinkedList(
1086   LinkedListInfo *list_info,int (*compare)(const void *,const void *),
1087   void **replace,const void *value)
1088 {
1089   ElementInfo
1090     *element;
1091
1092   register ElementInfo
1093     *next;
1094
1095   register ssize_t
1096     i;
1097
1098   assert(list_info != (LinkedListInfo *) NULL);
1099   assert(list_info->signature == MagickSignature);
1100   if ((compare == (int (*)(const void *,const void *)) NULL) ||
1101       (value == (const void *) NULL))
1102     return(MagickFalse);
1103   if (list_info->elements == list_info->capacity)
1104     return(MagickFalse);
1105   next=(ElementInfo *) AcquireMagickMemory(sizeof(*next));
1106   if (next == (ElementInfo *) NULL)
1107     return(MagickFalse);
1108   next->value=(void *) value;
1109   element=(ElementInfo *) NULL;
1110   LockSemaphoreInfo(list_info->semaphore);
1111   next->next=list_info->head;
1112   while (next->next != (ElementInfo *) NULL)
1113   {
1114     i=(ssize_t) compare(value,next->next->value);
1115     if ((i < 0) || ((replace != (void **) NULL) && (i == 0)))
1116       {
1117         if (i == 0)
1118           {
1119             *replace=next->next->value;
1120             next->next=next->next->next;
1121             if (element != (ElementInfo *) NULL)
1122               element->next=(ElementInfo *) RelinquishMagickMemory(
1123                 element->next);
1124             list_info->elements--;
1125           }
1126         if (element != (ElementInfo *) NULL)
1127           element->next=next;
1128         else
1129           list_info->head=next;
1130         break;
1131       }
1132     element=next->next;
1133     next->next=next->next->next;
1134   }
1135   if (next->next == (ElementInfo *) NULL)
1136     {
1137       if (element != (ElementInfo *) NULL)
1138         element->next=next;
1139       else
1140         list_info->head=next;
1141       list_info->tail=next;
1142     }
1143   list_info->elements++;
1144   UnlockSemaphoreInfo(list_info->semaphore);
1145   return(MagickTrue);
1146 }
1147 \f
1148 /*
1149 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1150 %                                                                             %
1151 %                                                                             %
1152 %                                                                             %
1153 %   I s H a s h m a p E m p t y                                               %
1154 %                                                                             %
1155 %                                                                             %
1156 %                                                                             %
1157 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1158 %
1159 %  IsHashmapEmpty() returns MagickTrue if the hash-map is empty.
1160 %
1161 %  The format of the IsHashmapEmpty method is:
1162 %
1163 %      MagickBooleanType IsHashmapEmpty(const HashmapInfo *hashmap_info)
1164 %
1165 %  A description of each parameter follows:
1166 %
1167 %    o hashmap_info: the hashmap info.
1168 %
1169 */
1170 MagickExport MagickBooleanType IsHashmapEmpty(const HashmapInfo *hashmap_info)
1171 {
1172   assert(hashmap_info != (HashmapInfo *) NULL);
1173   assert(hashmap_info->signature == MagickSignature);
1174   return(IsMagickTrue(hashmap_info->entries == 0));
1175 }
1176 \f
1177 /*
1178 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1179 %                                                                             %
1180 %                                                                             %
1181 %                                                                             %
1182 %   I s L i n k e d L i s t E m p t y                                         %
1183 %                                                                             %
1184 %                                                                             %
1185 %                                                                             %
1186 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1187 %
1188 %  IsLinkedListEmpty() returns MagickTrue if the linked-list is empty.
1189 %
1190 %  The format of the IsLinkedListEmpty method is:
1191 %
1192 %      MagickBooleanType IsLinkedListEmpty(LinkedListInfo *list_info)
1193 %
1194 %  A description of each parameter follows:
1195 %
1196 %    o list_info: the linked-list info.
1197 %
1198 */
1199 MagickExport MagickBooleanType IsLinkedListEmpty(
1200   const LinkedListInfo *list_info)
1201 {
1202   assert(list_info != (LinkedListInfo *) NULL);
1203   assert(list_info->signature == MagickSignature);
1204   return(IsMagickTrue(list_info->elements == 0));
1205 }
1206 \f
1207 /*
1208 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1209 %                                                                             %
1210 %                                                                             %
1211 %                                                                             %
1212 %   L i n k e d L i s t T o A r r a y                                         %
1213 %                                                                             %
1214 %                                                                             %
1215 %                                                                             %
1216 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1217 %
1218 %  LinkedListToArray() converts the linked-list to an array.
1219 %
1220 %  The format of the LinkedListToArray method is:
1221 %
1222 %      MagickBooleanType LinkedListToArray(LinkedListInfo *list_info,
1223 %        void **array)
1224 %
1225 %  A description of each parameter follows:
1226 %
1227 %    o list_info: the linked-list info.
1228 %
1229 %    o array: the array.
1230 %
1231 */
1232 MagickExport MagickBooleanType LinkedListToArray(LinkedListInfo *list_info,
1233   void **array)
1234 {
1235   register ElementInfo
1236     *next;
1237
1238   register ssize_t
1239     i;
1240
1241   assert(list_info != (LinkedListInfo *) NULL);
1242   assert(list_info->signature == MagickSignature);
1243   if (array == (void **) NULL)
1244     return(MagickFalse);
1245   LockSemaphoreInfo(list_info->semaphore);
1246   next=list_info->head;
1247   for (i=0; next != (ElementInfo *) NULL; i++)
1248   {
1249     array[i]=next->value;
1250     next=next->next;
1251   }
1252   UnlockSemaphoreInfo(list_info->semaphore);
1253   return(MagickTrue);
1254 }
1255 \f
1256 /*
1257 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1258 %                                                                             %
1259 %                                                                             %
1260 %                                                                             %
1261 %   N e w H a s h m a p                                                       %
1262 %                                                                             %
1263 %                                                                             %
1264 %                                                                             %
1265 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1266 %
1267 %  NewHashmap() returns a pointer to a HashmapInfo structure initialized
1268 %  to default values.  The capacity is an initial estimate.  The hashmap will
1269 %  increase capacity dynamically as the demand requires.
1270 %
1271 %  The format of the NewHashmap method is:
1272 %
1273 %      HashmapInfo *NewHashmap(const size_t capacity,
1274 %        size_t (*hash)(const void *),
1275 %        MagickBooleanType (*compare)(const void *,const void *),
1276 %        void *(*relinquish_key)(void *),void *(*relinquish_value)(void *))
1277 %
1278 %  A description of each parameter follows:
1279 %
1280 %    o capacity: the initial number entries in the hash-map: typically
1281 %      SmallHashmapSize, MediumHashmapSize, or LargeHashmapSize.  The
1282 %      hashmap will dynamically increase its capacity on demand.
1283 %
1284 %    o hash: the hash method, typically HashPointerType(), HashStringType(),
1285 %      or HashStringInfoType().
1286 %
1287 %    o compare: the compare method, typically NULL, CompareHashmapString(),
1288 %      or CompareHashmapStringInfo().
1289 %
1290 %    o relinquish_key: the key deallocation method, typically
1291 %      RelinquishMagickMemory(), called whenever a key is removed from the
1292 %      hash-map.
1293 %
1294 %    o relinquish_value: the value deallocation method;  typically
1295 %      RelinquishMagickMemory(), called whenever a value object is removed from
1296 %      the hash-map.
1297 %
1298 */
1299 MagickExport HashmapInfo *NewHashmap(const size_t capacity,
1300   size_t (*hash)(const void *),
1301   MagickBooleanType (*compare)(const void *,const void *),
1302   void *(*relinquish_key)(void *),void *(*relinquish_value)(void *))
1303 {
1304   HashmapInfo
1305     *hashmap_info;
1306
1307   hashmap_info=(HashmapInfo *) AcquireMagickMemory(sizeof(*hashmap_info));
1308   if (hashmap_info == (HashmapInfo *) NULL)
1309     ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
1310   (void) ResetMagickMemory(hashmap_info,0,sizeof(*hashmap_info));
1311   hashmap_info->hash=HashPointerType;
1312   if (hash != (size_t (*)(const void *)) NULL)
1313     hashmap_info->hash=hash;
1314   hashmap_info->compare=(MagickBooleanType (*)(const void *,const void *)) NULL;
1315   if (compare != (MagickBooleanType (*)(const void *,const void *)) NULL)
1316     hashmap_info->compare=compare;
1317   hashmap_info->relinquish_key=relinquish_key;
1318   hashmap_info->relinquish_value=relinquish_value;
1319   hashmap_info->entries=0;
1320   hashmap_info->capacity=capacity;
1321   hashmap_info->map=(LinkedListInfo **) NULL;
1322   if (~capacity >= 1UL)
1323     hashmap_info->map=(LinkedListInfo **) AcquireQuantumMemory((size_t)
1324       capacity+1UL,sizeof(*hashmap_info->map));
1325   if (hashmap_info->map == (LinkedListInfo **) NULL)
1326     ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
1327   (void) ResetMagickMemory(hashmap_info->map,0,(size_t) capacity*
1328     sizeof(*hashmap_info->map));
1329   hashmap_info->semaphore=AcquireSemaphoreInfo();
1330   hashmap_info->signature=MagickSignature;
1331   return(hashmap_info);
1332 }
1333 \f
1334 /*
1335 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1336 %                                                                             %
1337 %                                                                             %
1338 %                                                                             %
1339 %   N e w L i n k e d L i s t I n f o                                         %
1340 %                                                                             %
1341 %                                                                             %
1342 %                                                                             %
1343 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1344 %
1345 %  NewLinkedList() returns a pointer to a LinkedListInfo structure
1346 %  initialized to default values.
1347 %
1348 %  The format of the NewLinkedList method is:
1349 %
1350 %      LinkedListInfo *NewLinkedList(const size_t capacity)
1351 %
1352 %  A description of each parameter follows:
1353 %
1354 %    o capacity: the maximum number of elements in the list.
1355 %
1356 */
1357 MagickExport LinkedListInfo *NewLinkedList(const size_t capacity)
1358 {
1359   LinkedListInfo
1360     *list_info;
1361
1362   list_info=(LinkedListInfo *) AcquireMagickMemory(sizeof(*list_info));
1363   if (list_info == (LinkedListInfo *) NULL)
1364     ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
1365   (void) ResetMagickMemory(list_info,0,sizeof(*list_info));
1366   list_info->capacity=capacity == 0 ? (size_t) (~0) : capacity;
1367   list_info->elements=0;
1368   list_info->head=(ElementInfo *) NULL;
1369   list_info->tail=(ElementInfo *) NULL;
1370   list_info->next=(ElementInfo *) NULL;
1371   list_info->semaphore=AcquireSemaphoreInfo();
1372   list_info->signature=MagickSignature;
1373   return(list_info);
1374 }
1375 \f
1376 /*
1377 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1378 %                                                                             %
1379 %                                                                             %
1380 %                                                                             %
1381 %   P u t E n t r y I n H a s h m a p                                         %
1382 %                                                                             %
1383 %                                                                             %
1384 %                                                                             %
1385 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1386 %
1387 %  PutEntryInHashmap() puts an entry in the hash-map.  If the key already
1388 %  exists in the map it is first removed.
1389 %
1390 %  The format of the PutEntryInHashmap method is:
1391 %
1392 %      MagickBooleanType PutEntryInHashmap(HashmapInfo *hashmap_info,
1393 %        const void *key,const void *value)
1394 %
1395 %  A description of each parameter follows:
1396 %
1397 %    o hashmap_info: the hashmap info.
1398 %
1399 %    o key: the key.
1400 %
1401 %    o value: the value.
1402 %
1403 */
1404
1405 static MagickBooleanType IncreaseHashmapCapacity(HashmapInfo *hashmap_info)
1406 {
1407 #define MaxCapacities  20
1408
1409   const size_t
1410     capacities[MaxCapacities] =
1411     {
1412       17, 31, 61, 131, 257, 509, 1021, 2053, 4099, 8191, 16381, 32771,
1413       65537, 131071, 262147, 524287, 1048573, 2097143, 4194301, 8388617
1414     };
1415
1416   ElementInfo
1417     *element;
1418
1419   EntryInfo
1420     *entry;
1421
1422   LinkedListInfo
1423     *list_info,
1424     *map_info,
1425     **map;
1426
1427   register ElementInfo
1428     *next;
1429
1430   register ssize_t
1431     i;
1432
1433   size_t
1434     capacity;
1435
1436   /*
1437     Increase to the next prime capacity.
1438   */
1439   for (i=0; i < MaxCapacities; i++)
1440     if (hashmap_info->capacity < capacities[i])
1441       break;
1442   if (i >= (MaxCapacities-1))
1443     return(MagickFalse);
1444   capacity=capacities[i+1];
1445   map=(LinkedListInfo **) AcquireQuantumMemory((size_t) capacity+1UL,
1446     sizeof(*map));
1447   if (map == (LinkedListInfo **) NULL)
1448     return(MagickFalse);
1449   (void) ResetMagickMemory(map,0,(size_t) capacity*sizeof(*map));
1450   /*
1451     Copy entries to new hashmap with increased capacity.
1452   */
1453   for (i=0; i < (ssize_t) hashmap_info->capacity; i++)
1454   {
1455     list_info=hashmap_info->map[i];
1456     if (list_info == (LinkedListInfo *) NULL)
1457       continue;
1458     LockSemaphoreInfo(list_info->semaphore);
1459     for (next=list_info->head; next != (ElementInfo *) NULL; )
1460     {
1461       element=next;
1462       next=next->next;
1463       entry=(EntryInfo *) element->value;
1464       map_info=map[entry->hash % capacity];
1465       if (map_info == (LinkedListInfo *) NULL)
1466         {
1467           map_info=NewLinkedList(0);
1468           map[entry->hash % capacity]=map_info;
1469         }
1470       map_info->next=element;
1471       element->next=map_info->head;
1472       map_info->head=element;
1473       map_info->elements++;
1474     }
1475     list_info->signature=(~MagickSignature);
1476     UnlockSemaphoreInfo(list_info->semaphore);
1477     RelinquishSemaphoreInfo(&list_info->semaphore);
1478     list_info=(LinkedListInfo *) RelinquishMagickMemory(list_info);
1479   }
1480   hashmap_info->map=(LinkedListInfo **) RelinquishMagickMemory(
1481     hashmap_info->map);
1482   hashmap_info->map=map;
1483   hashmap_info->capacity=capacity;
1484   return(MagickTrue);
1485 }
1486
1487 MagickExport MagickBooleanType PutEntryInHashmap(HashmapInfo *hashmap_info,
1488   const void *key,const void *value)
1489 {
1490   EntryInfo
1491     *entry,
1492     *next;
1493
1494   LinkedListInfo
1495     *list_info;
1496
1497   register size_t
1498     i;
1499
1500   assert(hashmap_info != (HashmapInfo *) NULL);
1501   assert(hashmap_info->signature == MagickSignature);
1502   if ((key == (void *) NULL) || (value == (void *) NULL))
1503     return(MagickFalse);
1504   next=(EntryInfo *) AcquireMagickMemory(sizeof(*next));
1505   if (next == (EntryInfo *) NULL)
1506     return(MagickFalse);
1507   LockSemaphoreInfo(hashmap_info->semaphore);
1508   next->hash=hashmap_info->hash(key);
1509   next->key=(void *) key;
1510   next->value=(void *) value;
1511   list_info=hashmap_info->map[next->hash % hashmap_info->capacity];
1512   if (list_info == (LinkedListInfo *) NULL)
1513     {
1514       list_info=NewLinkedList(0);
1515       hashmap_info->map[next->hash % hashmap_info->capacity]=list_info;
1516     }
1517   else
1518     {
1519       list_info->next=list_info->head;
1520       entry=(EntryInfo *) GetNextValueInLinkedList(list_info);
1521       for (i=0; entry != (EntryInfo *) NULL; i++)
1522       {
1523         if (entry->hash == next->hash)
1524           {
1525             MagickBooleanType
1526               compare;
1527
1528             compare=MagickTrue;
1529             if (hashmap_info->compare !=
1530                 (MagickBooleanType (*)(const void *,const void *)) NULL)
1531               compare=hashmap_info->compare(key,entry->key);
1532             if( IfMagickTrue(compare) )
1533               {
1534                 (void) RemoveElementFromLinkedList(list_info,i);
1535                 if (hashmap_info->relinquish_key != (void *(*)(void *)) NULL)
1536                   entry->key=hashmap_info->relinquish_key(entry->key);
1537                 if (hashmap_info->relinquish_value != (void *(*)(void *)) NULL)
1538                   entry->value=hashmap_info->relinquish_value(entry->value);
1539                 entry=(EntryInfo *) RelinquishMagickMemory(entry);
1540                 break;
1541               }
1542           }
1543         entry=(EntryInfo *) GetNextValueInLinkedList(list_info);
1544       }
1545     }
1546   if (IfMagickFalse(InsertValueInLinkedList(list_info,0,next)))
1547     {
1548       next=(EntryInfo *) RelinquishMagickMemory(next);
1549       UnlockSemaphoreInfo(hashmap_info->semaphore);
1550       return(MagickFalse);
1551     }
1552   if (list_info->elements >= (hashmap_info->capacity-1))
1553     if (IfMagickFalse(IncreaseHashmapCapacity(hashmap_info)))
1554       {
1555         UnlockSemaphoreInfo(hashmap_info->semaphore);
1556         return(MagickFalse);
1557       }
1558   hashmap_info->entries++;
1559   UnlockSemaphoreInfo(hashmap_info->semaphore);
1560   return(MagickTrue);
1561 }
1562 \f
1563 /*
1564 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1565 %                                                                             %
1566 %                                                                             %
1567 %                                                                             %
1568 %   R e m o v e E l e m e n t B y V a l u e F r o m L i n k e d L i s t       %
1569 %                                                                             %
1570 %                                                                             %
1571 %                                                                             %
1572 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1573 %
1574 %  RemoveElementByValueFromLinkedList() removes an element from the linked-list
1575 %  by value.
1576 %
1577 %  The format of the RemoveElementByValueFromLinkedList method is:
1578 %
1579 %      void *RemoveElementByValueFromLinkedList(LinkedListInfo *list_info,
1580 %        const void *value)
1581 %
1582 %  A description of each parameter follows:
1583 %
1584 %    o list_info: the list info.
1585 %
1586 %    o value: the value.
1587 %
1588 */
1589 MagickExport void *RemoveElementByValueFromLinkedList(LinkedListInfo *list_info,
1590   const void *value)
1591 {
1592   ElementInfo
1593     *next;
1594
1595   assert(list_info != (LinkedListInfo *) NULL);
1596   assert(list_info->signature == MagickSignature);
1597   if ((list_info->elements == 0) || (value == (const void *) NULL))
1598     return((void *) NULL);
1599   LockSemaphoreInfo(list_info->semaphore);
1600   if (value == list_info->head->value)
1601     {
1602       if (list_info->next == list_info->head)
1603         list_info->next=list_info->head->next;
1604       next=list_info->head;
1605       list_info->head=list_info->head->next;
1606       next=(ElementInfo *) RelinquishMagickMemory(next);
1607     }
1608   else
1609     {
1610       ElementInfo
1611         *element;
1612
1613       next=list_info->head;
1614       while ((next->next != (ElementInfo *) NULL) &&
1615              (next->next->value != value))
1616         next=next->next;
1617       if (next->next == (ElementInfo *) NULL)
1618         {
1619           UnlockSemaphoreInfo(list_info->semaphore);
1620           return((void *) NULL);
1621         }
1622       element=next->next;
1623       next->next=element->next;
1624       if (element == list_info->tail)
1625         list_info->tail=next;
1626       if (list_info->next == element)
1627         list_info->next=element->next;
1628       element=(ElementInfo *) RelinquishMagickMemory(element);
1629     }
1630   list_info->elements--;
1631   UnlockSemaphoreInfo(list_info->semaphore);
1632   return((void *) value);
1633 }
1634 \f
1635 /*
1636 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1637 %                                                                             %
1638 %                                                                             %
1639 %                                                                             %
1640 %   R e m o v e E l e m e n t F r o m L i n k e d L i s t                     %
1641 %                                                                             %
1642 %                                                                             %
1643 %                                                                             %
1644 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1645 %
1646 %  RemoveElementFromLinkedList() removes an element from the linked-list at the
1647 %  specified location.
1648 %
1649 %  The format of the RemoveElementFromLinkedList method is:
1650 %
1651 %      void *RemoveElementFromLinkedList(LinkedListInfo *list_info,
1652 %        const size_t index)
1653 %
1654 %  A description of each parameter follows:
1655 %
1656 %    o list_info: the linked-list info.
1657 %
1658 %    o index: the index.
1659 %
1660 */
1661 MagickExport void *RemoveElementFromLinkedList(LinkedListInfo *list_info,
1662   const size_t index)
1663 {
1664   ElementInfo
1665     *next;
1666
1667   register ssize_t
1668     i;
1669
1670   void
1671     *value;
1672
1673   assert(list_info != (LinkedListInfo *) NULL);
1674   assert(list_info->signature == MagickSignature);
1675   if (index >= list_info->elements)
1676     return((void *) NULL);
1677   LockSemaphoreInfo(list_info->semaphore);
1678   if (index == 0)
1679     {
1680       if (list_info->next == list_info->head)
1681         list_info->next=list_info->head->next;
1682       value=list_info->head->value;
1683       next=list_info->head;
1684       list_info->head=list_info->head->next;
1685       next=(ElementInfo *) RelinquishMagickMemory(next);
1686     }
1687   else
1688     {
1689       ElementInfo
1690         *element;
1691
1692       next=list_info->head;
1693       for (i=1; i < (ssize_t) index; i++)
1694         next=next->next;
1695       element=next->next;
1696       next->next=element->next;
1697       if (element == list_info->tail)
1698         list_info->tail=next;
1699       if (list_info->next == element)
1700         list_info->next=element->next;
1701       value=element->value;
1702       element=(ElementInfo *) RelinquishMagickMemory(element);
1703     }
1704   list_info->elements--;
1705   UnlockSemaphoreInfo(list_info->semaphore);
1706   return(value);
1707 }
1708 \f
1709 /*
1710 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1711 %                                                                             %
1712 %                                                                             %
1713 %                                                                             %
1714 %   R e m o v e E n t r y F r o m H a s h m a p                               %
1715 %                                                                             %
1716 %                                                                             %
1717 %                                                                             %
1718 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1719 %
1720 %  RemoveEntryFromHashmap() removes an entry from the hash-map by its key.
1721 %
1722 %  The format of the RemoveEntryFromHashmap method is:
1723 %
1724 %      void *RemoveEntryFromHashmap(HashmapInfo *hashmap_info,void *key)
1725 %
1726 %  A description of each parameter follows:
1727 %
1728 %    o hashmap_info: the hashmap info.
1729 %
1730 %    o key: the key.
1731 %
1732 */
1733 MagickExport void *RemoveEntryFromHashmap(HashmapInfo *hashmap_info,
1734   const void *key)
1735 {
1736   EntryInfo
1737     *entry;
1738
1739   LinkedListInfo
1740     *list_info;
1741
1742   register size_t
1743     i;
1744
1745   size_t
1746     hash;
1747
1748   void
1749     *value;
1750
1751   assert(hashmap_info != (HashmapInfo *) NULL);
1752   assert(hashmap_info->signature == MagickSignature);
1753   if (key == (const void *) NULL)
1754     return((void *) NULL);
1755   LockSemaphoreInfo(hashmap_info->semaphore);
1756   hash=hashmap_info->hash(key);
1757   list_info=hashmap_info->map[hash % hashmap_info->capacity];
1758   if (list_info != (LinkedListInfo *) NULL)
1759     {
1760       list_info->next=list_info->head;
1761       entry=(EntryInfo *) GetNextValueInLinkedList(list_info);
1762       for (i=0; entry != (EntryInfo *) NULL; i++)
1763       {
1764         if (entry->hash == hash)
1765           {
1766             MagickBooleanType
1767               compare;
1768
1769             compare=MagickTrue;
1770             if (hashmap_info->compare !=
1771                 (MagickBooleanType (*)(const void *,const void *)) NULL)
1772               compare=hashmap_info->compare(key,entry->key);
1773             if( IfMagickTrue(compare) )
1774               {
1775                 entry=(EntryInfo *) RemoveElementFromLinkedList(list_info,i);
1776                 if (entry == (EntryInfo *) NULL)
1777                   {
1778                     UnlockSemaphoreInfo(hashmap_info->semaphore);
1779                     return((void *) NULL);
1780                   }
1781                 if (hashmap_info->relinquish_key != (void *(*)(void *)) NULL)
1782                   entry->key=hashmap_info->relinquish_key(entry->key);
1783                 value=entry->value;
1784                 entry=(EntryInfo *) RelinquishMagickMemory(entry);
1785                 hashmap_info->entries--;
1786                 UnlockSemaphoreInfo(hashmap_info->semaphore);
1787                 return(value);
1788               }
1789           }
1790         entry=(EntryInfo *) GetNextValueInLinkedList(list_info);
1791       }
1792     }
1793   UnlockSemaphoreInfo(hashmap_info->semaphore);
1794   return((void *) NULL);
1795 }
1796 \f
1797 /*
1798 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1799 %                                                                             %
1800 %                                                                             %
1801 %                                                                             %
1802 %   R e m o v e L a s t E l e m e n t F r o m L i n k e d L i s t             %
1803 %                                                                             %
1804 %                                                                             %
1805 %                                                                             %
1806 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1807 %
1808 %  RemoveLastElementFromLinkedList() removes the last element from the
1809 %  linked-list.
1810 %
1811 %  The format of the RemoveLastElementFromLinkedList method is:
1812 %
1813 %      void *RemoveLastElementFromLinkedList(LinkedListInfo *list_info)
1814 %
1815 %  A description of each parameter follows:
1816 %
1817 %    o list_info: the linked-list info.
1818 %
1819 */
1820 MagickExport void *RemoveLastElementFromLinkedList(LinkedListInfo *list_info)
1821 {
1822   void
1823     *value;
1824
1825   assert(list_info != (LinkedListInfo *) NULL);
1826   assert(list_info->signature == MagickSignature);
1827   if (list_info->elements == 0)
1828     return((void *) NULL);
1829   LockSemaphoreInfo(list_info->semaphore);
1830   if (list_info->next == list_info->tail)
1831     list_info->next=(ElementInfo *) NULL;
1832   if (list_info->elements == 1UL)
1833     {
1834       value=list_info->head->value;
1835       list_info->head=(ElementInfo *) NULL;
1836       list_info->tail=(ElementInfo *) RelinquishMagickMemory(list_info->tail);
1837     }
1838   else
1839     {
1840       ElementInfo
1841         *next;
1842
1843       value=list_info->tail->value;
1844       next=list_info->head;
1845       while (next->next != list_info->tail)
1846         next=next->next;
1847       list_info->tail=(ElementInfo *) RelinquishMagickMemory(list_info->tail);
1848       list_info->tail=next;
1849       next->next=(ElementInfo *) NULL;
1850     }
1851   list_info->elements--;
1852   UnlockSemaphoreInfo(list_info->semaphore);
1853   return(value);
1854 }
1855 \f
1856 /*
1857 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1858 %                                                                             %
1859 %                                                                             %
1860 %                                                                             %
1861 %   R e s e t H a s h m a p I t e r a t o r                                   %
1862 %                                                                             %
1863 %                                                                             %
1864 %                                                                             %
1865 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1866 %
1867 %  ResetHashmapIterator() resets the hash-map iterator.  Use it in conjunction
1868 %  with GetNextKeyInHashmap() to iterate over all the keys in the hash-map.
1869 %
1870 %  The format of the ResetHashmapIterator method is:
1871 %
1872 %      ResetHashmapIterator(HashmapInfo *hashmap_info)
1873 %
1874 %  A description of each parameter follows:
1875 %
1876 %    o hashmap_info: the hashmap info.
1877 %
1878 */
1879 MagickExport void ResetHashmapIterator(HashmapInfo *hashmap_info)
1880 {
1881   assert(hashmap_info != (HashmapInfo *) NULL);
1882   assert(hashmap_info->signature == MagickSignature);
1883   LockSemaphoreInfo(hashmap_info->semaphore);
1884   hashmap_info->next=0;
1885   hashmap_info->head_of_list=MagickFalse;
1886   UnlockSemaphoreInfo(hashmap_info->semaphore);
1887 }
1888 \f
1889 /*
1890 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1891 %                                                                             %
1892 %                                                                             %
1893 %                                                                             %
1894 %   R e s e t L i n k e d L i s t I t e r a t o r                             %
1895 %                                                                             %
1896 %                                                                             %
1897 %                                                                             %
1898 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1899 %
1900 %  ResetLinkedListIterator() resets the lined-list iterator.  Use it in
1901 %  conjunction with GetNextValueInLinkedList() to iterate over all the values
1902 %  in the linked-list.
1903 %
1904 %  The format of the ResetLinkedListIterator method is:
1905 %
1906 %      ResetLinkedListIterator(LinkedListInfo *list_info)
1907 %
1908 %  A description of each parameter follows:
1909 %
1910 %    o list_info: the linked-list info.
1911 %
1912 */
1913 MagickExport void ResetLinkedListIterator(LinkedListInfo *list_info)
1914 {
1915   assert(list_info != (LinkedListInfo *) NULL);
1916   assert(list_info->signature == MagickSignature);
1917   LockSemaphoreInfo(list_info->semaphore);
1918   list_info->next=list_info->head;
1919   UnlockSemaphoreInfo(list_info->semaphore);
1920 }