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