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