granicus.if.org Git - imagemagick/blob - MagickCore/linked-list.c

   1 /*\r
   2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
   3 %                                                                             %\r
   4 %                                                                             %\r
   5 %                                                                             %\r
   6 %   L      IIIII  N   N  K   K  EEEEE  DDDD      L      IIIII  SSSSS  TTTTT   %\r
   7 %   L        I    NN  N  K  K   E      D   D     L        I    SS       T     %\r
   8 %   L        I    N N N  KKK    EEE    D   D  =  L        I     SSS     T     %\r
   9 %   L        I    N  NN  K  K   E      D   D     L        I       SS    T     %\r
  10 %   LLLLL  IIIII  N   N  K   K  EEEEE  DDDD      LLLLL  IIIII  SSSSS    T     %\r
  11 %                                                                             %\r
  12 %                                                                             %\r
  13 %                  MagickCore Linked-list Methods                             %\r
  14 %                                                                             %\r
  15 %                              Software Design                                %\r
  16 %                                   Cristy                                    %\r
  17 %                               December 2002                                 %\r
  18 %                                                                             %\r
  19 %                                                                             %\r
  20 %  Copyright 1999-2017 ImageMagick Studio LLC, a non-profit organization      %\r
  21 %  dedicated to making software imaging solutions freely available.           %\r
  22 %                                                                             %\r
  23 %  You may not use this file except in compliance with the License.  You may  %\r
  24 %  obtain a copy of the License at                                            %\r
  25 %                                                                             %\r
  26 %    https://www.imagemagick.org/script/license.php                           %\r
  27 %                                                                             %\r
  28 %  Unless required by applicable law or agreed to in writing, software        %\r
  29 %  distributed under the License is distributed on an "AS IS" BASIS,          %\r
  30 %  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.   %\r
  31 %  See the License for the specific language governing permissions and        %\r
  32 %  limitations under the License.                                             %\r
  33 %                                                                             %\r
  34 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
  35 %\r
  36 %  This module implements the standard handy hash and linked-list methods for\r
  37 %  storing and retrieving large numbers of data elements.  It is loosely based\r
  38 %  on the Java implementation of these algorithms.\r
  39 %\r
  40 */\r
  41 \f\r
  42 /*\r
  43   Include declarations.\r
  44 */\r
  45 #include "MagickCore/studio.h"\r
  46 #include "MagickCore/exception.h"\r
  47 #include "MagickCore/exception-private.h"\r
  48 #include "MagickCore/linked-list.h"\r
  49 #include "MagickCore/locale_.h"\r
  50 #include "MagickCore/memory_.h"\r
  51 #include "MagickCore/semaphore.h"\r
  52 #include "MagickCore/signature-private.h"\r
  53 #include "MagickCore/string_.h"\r
  54 \f\r
  55 /*\r
  56   Typedef declarations.\r
  57 */\r
  58 typedef struct _ElementInfo\r
  59 {\r
  60   void\r
  61     *value;\r
  62 \r
  63   struct _ElementInfo\r
  64     *next;\r
  65 } ElementInfo;\r
  66 \r
  67 struct _LinkedListInfo\r
  68 {\r
  69   size_t\r
  70     capacity,\r
  71     elements;\r
  72 \r
  73   ElementInfo\r
  74     *head,\r
  75     *tail,\r
  76     *next;\r
  77 \r
  78   SemaphoreInfo\r
  79     *semaphore;\r
  80 \r
  81   size_t\r
  82     signature;\r
  83 };\r
  84 \f\r
  85 /*\r
  86 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
  87 %                                                                             %\r
  88 %                                                                             %\r
  89 %                                                                             %\r
  90 %   A p p e n d V a l u e T o L i n k e d L i s t                             %\r
  91 %                                                                             %\r
  92 %                                                                             %\r
  93 %                                                                             %\r
  94 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
  95 %\r
  96 %  AppendValueToLinkedList() appends a value to the end of the linked-list.\r
  97 %\r
  98 %  The format of the AppendValueToLinkedList method is:\r
  99 %\r
 100 %      MagickBooleanType AppendValueToLinkedList(LinkedListInfo *list_info,\r
 101 %        const void *value)\r
 102 %\r
 103 %  A description of each parameter follows:\r
 104 %\r
 105 %    o list_info: the linked-list info.\r
 106 %\r
 107 %    o value: the value.\r
 108 %\r
 109 */\r
 110 MagickExport MagickBooleanType AppendValueToLinkedList(\r
 111   LinkedListInfo *list_info,const void *value)\r
 112 {\r
 113   register ElementInfo\r
 114     *next;\r
 115 \r
 116   assert(list_info != (LinkedListInfo *) NULL);\r
 117   assert(list_info->signature == MagickCoreSignature);\r
 118   if (list_info->elements == list_info->capacity)\r
 119     return(MagickFalse);\r
 120   next=(ElementInfo *) AcquireMagickMemory(sizeof(*next));\r
 121   if (next == (ElementInfo *) NULL)\r
 122     return(MagickFalse);\r
 123   next->value=(void *) value;\r
 124   next->next=(ElementInfo *) NULL;\r
 125   LockSemaphoreInfo(list_info->semaphore);\r
 126   if (list_info->next == (ElementInfo *) NULL)\r
 127     list_info->next=next;\r
 128   if (list_info->elements == 0)\r
 129     list_info->head=next;\r
 130   else\r
 131     list_info->tail->next=next;\r
 132   list_info->tail=next;\r
 133   list_info->elements++;\r
 134   UnlockSemaphoreInfo(list_info->semaphore);\r
 135   return(MagickTrue);\r
 136 }\r
 137 \f\r
 138 /*\r
 139 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
 140 %                                                                             %\r
 141 %                                                                             %\r
 142 %                                                                             %\r
 143 %   C l e a r L i n k e d L i s t                                             %\r
 144 %                                                                             %\r
 145 %                                                                             %\r
 146 %                                                                             %\r
 147 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
 148 %\r
 149 %  ClearLinkedList() clears all the elements from the linked-list.\r
 150 %\r
 151 %  The format of the ClearLinkedList method is:\r
 152 %\r
 153 %      void ClearLinkedList(LinkedListInfo *list_info,\r
 154 %        void *(*relinquish_value)(void *))\r
 155 %\r
 156 %  A description of each parameter follows:\r
 157 %\r
 158 %    o list_info: the linked-list info.\r
 159 %\r
 160 %    o relinquish_value: the value deallocation method; typically\r
 161 %      RelinquishMagickMemory().\r
 162 %\r
 163 */\r
 164 MagickExport void ClearLinkedList(LinkedListInfo *list_info,\r
 165   void *(*relinquish_value)(void *))\r
 166 {\r
 167   ElementInfo\r
 168     *element;\r
 169 \r
 170   register ElementInfo\r
 171     *next;\r
 172 \r
 173   assert(list_info != (LinkedListInfo *) NULL);\r
 174   assert(list_info->signature == MagickCoreSignature);\r
 175   LockSemaphoreInfo(list_info->semaphore);\r
 176   next=list_info->head;\r
 177   while (next != (ElementInfo *) NULL)\r
 178   {\r
 179     if (relinquish_value != (void *(*)(void *)) NULL)\r
 180       next->value=relinquish_value(next->value);\r
 181     element=next;\r
 182     next=next->next;\r
 183     element=(ElementInfo *) RelinquishMagickMemory(element);\r
 184   }\r
 185   list_info->head=(ElementInfo *) NULL;\r
 186   list_info->tail=(ElementInfo *) NULL;\r
 187   list_info->next=(ElementInfo *) NULL;\r
 188   list_info->elements=0;\r
 189   UnlockSemaphoreInfo(list_info->semaphore);\r
 190 }\r
 191 \r
 192 /*\r
 193 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
 194 %                                                                             %\r
 195 %                                                                             %\r
 196 %                                                                             %\r
 197 %   D e s t r o y L i n k e d L i s t                                         %\r
 198 %                                                                             %\r
 199 %                                                                             %\r
 200 %                                                                             %\r
 201 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
 202 %\r
 203 %  DestroyLinkedList() frees the linked-list and all associated resources.\r
 204 %\r
 205 %  The format of the DestroyLinkedList method is:\r
 206 %\r
 207 %      LinkedListInfo *DestroyLinkedList(LinkedListInfo *list_info,\r
 208 %        void *(*relinquish_value)(void *))\r
 209 %\r
 210 %  A description of each parameter follows:\r
 211 %\r
 212 %    o list_info: the linked-list info.\r
 213 %\r
 214 %    o relinquish_value: the value deallocation method;  typically\r
 215 %      RelinquishMagickMemory().\r
 216 %\r
 217 */\r
 218 MagickExport LinkedListInfo *DestroyLinkedList(LinkedListInfo *list_info,\r
 219   void *(*relinquish_value)(void *))\r
 220 {\r
 221   ElementInfo\r
 222     *entry;\r
 223 \r
 224   register ElementInfo\r
 225     *next;\r
 226 \r
 227   assert(list_info != (LinkedListInfo *) NULL);\r
 228   assert(list_info->signature == MagickCoreSignature);\r
 229   LockSemaphoreInfo(list_info->semaphore);\r
 230   for (next=list_info->head; next != (ElementInfo *) NULL; )\r
 231   {\r
 232     if (relinquish_value != (void *(*)(void *)) NULL)\r
 233       next->value=relinquish_value(next->value);\r
 234     entry=next;\r
 235     next=next->next;\r
 236     entry=(ElementInfo *) RelinquishMagickMemory(entry);\r
 237   }\r
 238   list_info->signature=(~MagickCoreSignature);\r
 239   UnlockSemaphoreInfo(list_info->semaphore);\r
 240   RelinquishSemaphoreInfo(&list_info->semaphore);\r
 241   list_info=(LinkedListInfo *) RelinquishMagickMemory(list_info);\r
 242   return(list_info);\r
 243 }\r
 244 \f\r
 245 /*\r
 246 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
 247 %                                                                             %\r
 248 %                                                                             %\r
 249 %                                                                             %\r
 250 %   G e t L a s t V a l u e I n L i n k e d L i s t                           %\r
 251 %                                                                             %\r
 252 %                                                                             %\r
 253 %                                                                             %\r
 254 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
 255 %\r
 256 %  GetLastValueInLinkedList() gets the last value in the linked-list.\r
 257 %\r
 258 %  The format of the GetLastValueInLinkedList method is:\r
 259 %\r
 260 %      void *GetLastValueInLinkedList(LinkedListInfo *list_info)\r
 261 %\r
 262 %  A description of each parameter follows:\r
 263 %\r
 264 %    o list_info: the linked_list info.\r
 265 %\r
 266 */\r
 267 MagickExport void *GetLastValueInLinkedList(LinkedListInfo *list_info)\r
 268 {\r
 269   void\r
 270     *value;\r
 271 \r
 272   assert(list_info != (LinkedListInfo *) NULL);\r
 273   assert(list_info->signature == MagickCoreSignature);\r
 274   if (list_info->elements == 0)\r
 275     return((void *) NULL);\r
 276   LockSemaphoreInfo(list_info->semaphore);\r
 277   value=list_info->tail->value;\r
 278   UnlockSemaphoreInfo(list_info->semaphore);\r
 279   return(value);\r
 280 }\r
 281 \r
 282 /*\r
 283 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
 284 %                                                                             %\r
 285 %                                                                             %\r
 286 %                                                                             %\r
 287 %   G e t N e x t V a l u e I n L i n k e d L i s t                           %\r
 288 %                                                                             %\r
 289 %                                                                             %\r
 290 %                                                                             %\r
 291 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
 292 %\r
 293 %  GetNextValueInLinkedList() gets the next value in the linked-list.\r
 294 %\r
 295 %  The format of the GetNextValueInLinkedList method is:\r
 296 %\r
 297 %      void *GetNextValueInLinkedList(LinkedListInfo *list_info)\r
 298 %\r
 299 %  A description of each parameter follows:\r
 300 %\r
 301 %    o list_info: the linked-list info.\r
 302 %\r
 303 */\r
 304 MagickExport void *GetNextValueInLinkedList(LinkedListInfo *list_info)\r
 305 {\r
 306   void\r
 307     *value;\r
 308 \r
 309   assert(list_info != (LinkedListInfo *) NULL);\r
 310   assert(list_info->signature == MagickCoreSignature);\r
 311   LockSemaphoreInfo(list_info->semaphore);\r
 312   if (list_info->next == (ElementInfo *) NULL)\r
 313     {\r
 314       UnlockSemaphoreInfo(list_info->semaphore);\r
 315       return((void *) NULL);\r
 316     }\r
 317   value=list_info->next->value;\r
 318   list_info->next=list_info->next->next;\r
 319   UnlockSemaphoreInfo(list_info->semaphore);\r
 320   return(value);\r
 321 }\r
 322 \f\r
 323 /*\r
 324 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
 325 %                                                                             %\r
 326 %                                                                             %\r
 327 %                                                                             %\r
 328 %   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             %\r
 329 %                                                                             %\r
 330 %                                                                             %\r
 331 %                                                                             %\r
 332 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
 333 %\r
 334 %  GetNumberOfElementsInLinkedList() returns the number of entries in the\r
 335 %  linked-list.\r
 336 %\r
 337 %  The format of the GetNumberOfElementsInLinkedList method is:\r
 338 %\r
 339 %      size_t GetNumberOfElementsInLinkedList(\r
 340 %        const LinkedListInfo *list_info)\r
 341 %\r
 342 %  A description of each parameter follows:\r
 343 %\r
 344 %    o list_info: the linked-list info.\r
 345 %\r
 346 */\r
 347 MagickExport size_t GetNumberOfElementsInLinkedList(\r
 348   const LinkedListInfo *list_info)\r
 349 {\r
 350   assert(list_info != (LinkedListInfo *) NULL);\r
 351   assert(list_info->signature == MagickCoreSignature);\r
 352   return(list_info->elements);\r
 353 }\r
 354 \r
 355 /*\r
 356 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
 357 %                                                                             %\r
 358 %                                                                             %\r
 359 %                                                                             %\r
 360 %   G e t V a l u e F r o m L i n k e d L i s t                               %\r
 361 %                                                                             %\r
 362 %                                                                             %\r
 363 %                                                                             %\r
 364 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
 365 %\r
 366 %  GetValueFromLinkedList() gets a value from the linked-list at the specified\r
 367 %  location.\r
 368 %\r
 369 %  The format of the GetValueFromLinkedList method is:\r
 370 %\r
 371 %      void *GetValueFromLinkedList(LinkedListInfo *list_info,\r
 372 %        const size_t index)\r
 373 %\r
 374 %  A description of each parameter follows:\r
 375 %\r
 376 %    o list_info: the linked_list info.\r
 377 %\r
 378 %    o index: the list index.\r
 379 %\r
 380 */\r
 381 MagickExport void *GetValueFromLinkedList(LinkedListInfo *list_info,\r
 382   const size_t index)\r
 383 {\r
 384   register ElementInfo\r
 385     *next;\r
 386 \r
 387   register ssize_t\r
 388     i;\r
 389 \r
 390   void\r
 391     *value;\r
 392 \r
 393   assert(list_info != (LinkedListInfo *) NULL);\r
 394   assert(list_info->signature == MagickCoreSignature);\r
 395   if (index >= list_info->elements)\r
 396     return((void *) NULL);\r
 397   LockSemaphoreInfo(list_info->semaphore);\r
 398   if (index == 0)\r
 399     {\r
 400       value=list_info->head->value;\r
 401       UnlockSemaphoreInfo(list_info->semaphore);\r
 402       return(value);\r
 403     }\r
 404   if (index == (list_info->elements-1))\r
 405     {\r
 406       value=list_info->tail->value;\r
 407       UnlockSemaphoreInfo(list_info->semaphore);\r
 408       return(value);\r
 409     }\r
 410   next=list_info->head;\r
 411   for (i=0; i < (ssize_t) index; i++)\r
 412     next=next->next;\r
 413   value=next->value;\r
 414   UnlockSemaphoreInfo(list_info->semaphore);\r
 415   return(value);\r
 416 }\r
 417 \r
 418 /*\r
 419 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
 420 %                                                                             %\r
 421 %                                                                             %\r
 422 %                                                                             %\r
 423 %   I n s e r t V a l u e I n L i n k e d L i s t                             %\r
 424 %                                                                             %\r
 425 %                                                                             %\r
 426 %                                                                             %\r
 427 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
 428 %\r
 429 %  InsertValueInLinkedList() inserts an element in the linked-list at the\r
 430 %  specified location.\r
 431 %\r
 432 %  The format of the InsertValueInLinkedList method is:\r
 433 %\r
 434 %      MagickBooleanType InsertValueInLinkedList(ListInfo *list_info,\r
 435 %        const size_t index,const void *value)\r
 436 %\r
 437 %  A description of each parameter follows:\r
 438 %\r
 439 %    o list_info: the hashmap info.\r
 440 %\r
 441 %    o index: the index.\r
 442 %\r
 443 %    o value: the value.\r
 444 %\r
 445 */\r
 446 MagickExport MagickBooleanType InsertValueInLinkedList(\r
 447   LinkedListInfo *list_info,const size_t index,const void *value)\r
 448 {\r
 449   register ElementInfo\r
 450     *next;\r
 451 \r
 452   register ssize_t\r
 453     i;\r
 454 \r
 455   assert(list_info != (LinkedListInfo *) NULL);\r
 456   assert(list_info->signature == MagickCoreSignature);\r
 457   if (value == (const void *) NULL)\r
 458     return(MagickFalse);\r
 459   if ((index > list_info->elements) ||\r
 460       (list_info->elements == list_info->capacity))\r
 461     return(MagickFalse);\r
 462   next=(ElementInfo *) AcquireMagickMemory(sizeof(*next));\r
 463   if (next == (ElementInfo *) NULL)\r
 464     return(MagickFalse);\r
 465   next->value=(void *) value;\r
 466   next->next=(ElementInfo *) NULL;\r
 467   LockSemaphoreInfo(list_info->semaphore);\r
 468   if (list_info->elements == 0)\r
 469     {\r
 470       if (list_info->next == (ElementInfo *) NULL)\r
 471         list_info->next=next;\r
 472       list_info->head=next;\r
 473       list_info->tail=next;\r
 474     }\r
 475   else\r
 476     {\r
 477       if (index == 0)\r
 478         {\r
 479           if (list_info->next == list_info->head)\r
 480             list_info->next=next;\r
 481           next->next=list_info->head;\r
 482           list_info->head=next;\r
 483         }\r
 484       else\r
 485         if (index == list_info->elements)\r
 486           {\r
 487             if (list_info->next == (ElementInfo *) NULL)\r
 488               list_info->next=next;\r
 489             list_info->tail->next=next;\r
 490             list_info->tail=next;\r
 491           }\r
 492         else\r
 493           {\r
 494             ElementInfo\r
 495               *element;\r
 496 \r
 497             element=list_info->head;\r
 498             next->next=element->next;\r
 499             for (i=1; i < (ssize_t) index; i++)\r
 500             {\r
 501               element=element->next;\r
 502               next->next=element->next;\r
 503             }\r
 504             next=next->next;\r
 505             element->next=next;\r
 506             if (list_info->next == next->next)\r
 507               list_info->next=next;\r
 508           }\r
 509     }\r
 510   list_info->elements++;\r
 511   UnlockSemaphoreInfo(list_info->semaphore);\r
 512   return(MagickTrue);\r
 513 }\r
 514 \f\r
 515 /*\r
 516 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
 517 %                                                                             %\r
 518 %                                                                             %\r
 519 %                                                                             %\r
 520 %   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                 %\r
 521 %                                                                             %\r
 522 %                                                                             %\r
 523 %                                                                             %\r
 524 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
 525 %\r
 526 %  InsertValueInSortedLinkedList() inserts a value in the sorted linked-list.\r
 527 %\r
 528 %  The format of the InsertValueInSortedLinkedList method is:\r
 529 %\r
 530 %      MagickBooleanType InsertValueInSortedLinkedList(ListInfo *list_info,\r
 531 %        int (*compare)(const void *,const void *),void **replace,\r
 532 %        const void *value)\r
 533 %\r
 534 %  A description of each parameter follows:\r
 535 %\r
 536 %    o list_info: the hashmap info.\r
 537 %\r
 538 %    o index: the index.\r
 539 %\r
 540 %    o compare: the compare method.\r
 541 %\r
 542 %    o replace: return previous element here.\r
 543 %\r
 544 %    o value: the value.\r
 545 %\r
 546 */\r
 547 MagickExport MagickBooleanType InsertValueInSortedLinkedList(\r
 548   LinkedListInfo *list_info,int (*compare)(const void *,const void *),\r
 549   void **replace,const void *value)\r
 550 {\r
 551   ElementInfo\r
 552     *element;\r
 553 \r
 554   register ElementInfo\r
 555     *next;\r
 556 \r
 557   register ssize_t\r
 558     i;\r
 559 \r
 560   assert(list_info != (LinkedListInfo *) NULL);\r
 561   assert(list_info->signature == MagickCoreSignature);\r
 562   if ((compare == (int (*)(const void *,const void *)) NULL) ||\r
 563       (value == (const void *) NULL))\r
 564     return(MagickFalse);\r
 565   if (list_info->elements == list_info->capacity)\r
 566     return(MagickFalse);\r
 567   next=(ElementInfo *) AcquireMagickMemory(sizeof(*next));\r
 568   if (next == (ElementInfo *) NULL)\r
 569     return(MagickFalse);\r
 570   next->value=(void *) value;\r
 571   element=(ElementInfo *) NULL;\r
 572   LockSemaphoreInfo(list_info->semaphore);\r
 573   next->next=list_info->head;\r
 574   while (next->next != (ElementInfo *) NULL)\r
 575   {\r
 576     i=(ssize_t) compare(value,next->next->value);\r
 577     if ((i < 0) || ((replace != (void **) NULL) && (i == 0)))\r
 578       {\r
 579         if (i == 0)\r
 580           {\r
 581             *replace=next->next->value;\r
 582             next->next=next->next->next;\r
 583             if (element != (ElementInfo *) NULL)\r
 584               element->next=(ElementInfo *) RelinquishMagickMemory(\r
 585                 element->next);\r
 586             list_info->elements--;\r
 587           }\r
 588         if (element != (ElementInfo *) NULL)\r
 589           element->next=next;\r
 590         else\r
 591           list_info->head=next;\r
 592         break;\r
 593       }\r
 594     element=next->next;\r
 595     next->next=next->next->next;\r
 596   }\r
 597   if (next->next == (ElementInfo *) NULL)\r
 598     {\r
 599       if (element != (ElementInfo *) NULL)\r
 600         element->next=next;\r
 601       else\r
 602         list_info->head=next;\r
 603       list_info->tail=next;\r
 604     }\r
 605   list_info->elements++;\r
 606   UnlockSemaphoreInfo(list_info->semaphore);\r
 607   return(MagickTrue);\r
 608 }\r
 609 \r
 610 /*\r
 611 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
 612 %                                                                             %\r
 613 %                                                                             %\r
 614 %                                                                             %\r
 615 %   I s L i n k e d L i s t E m p t y                                         %\r
 616 %                                                                             %\r
 617 %                                                                             %\r
 618 %                                                                             %\r
 619 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
 620 %\r
 621 %  IsLinkedListEmpty() returns MagickTrue if the linked-list is empty.\r
 622 %\r
 623 %  The format of the IsLinkedListEmpty method is:\r
 624 %\r
 625 %      MagickBooleanType IsLinkedListEmpty(LinkedListInfo *list_info)\r
 626 %\r
 627 %  A description of each parameter follows:\r
 628 %\r
 629 %    o list_info: the linked-list info.\r
 630 %\r
 631 */\r
 632 MagickExport MagickBooleanType IsLinkedListEmpty(\r
 633   const LinkedListInfo *list_info)\r
 634 {\r
 635   assert(list_info != (LinkedListInfo *) NULL);\r
 636   assert(list_info->signature == MagickCoreSignature);\r
 637   return(list_info->elements == 0 ? MagickTrue : MagickFalse);\r
 638 }\r
 639 \f\r
 640 /*\r
 641 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
 642 %                                                                             %\r
 643 %                                                                             %\r
 644 %                                                                             %\r
 645 %   L i n k e d L i s t T o A r r a y                                         %\r
 646 %                                                                             %\r
 647 %                                                                             %\r
 648 %                                                                             %\r
 649 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
 650 %\r
 651 %  LinkedListToArray() converts the linked-list to an array.\r
 652 %\r
 653 %  The format of the LinkedListToArray method is:\r
 654 %\r
 655 %      MagickBooleanType LinkedListToArray(LinkedListInfo *list_info,\r
 656 %        void **array)\r
 657 %\r
 658 %  A description of each parameter follows:\r
 659 %\r
 660 %    o list_info: the linked-list info.\r
 661 %\r
 662 %    o array: the array.\r
 663 %\r
 664 */\r
 665 MagickExport MagickBooleanType LinkedListToArray(LinkedListInfo *list_info,\r
 666   void **array)\r
 667 {\r
 668   register ElementInfo\r
 669     *next;\r
 670 \r
 671   register ssize_t\r
 672     i;\r
 673 \r
 674   assert(list_info != (LinkedListInfo *) NULL);\r
 675   assert(list_info->signature == MagickCoreSignature);\r
 676   if (array == (void **) NULL)\r
 677     return(MagickFalse);\r
 678   LockSemaphoreInfo(list_info->semaphore);\r
 679   next=list_info->head;\r
 680   for (i=0; next != (ElementInfo *) NULL; i++)\r
 681   {\r
 682     array[i]=next->value;\r
 683     next=next->next;\r
 684   }\r
 685   UnlockSemaphoreInfo(list_info->semaphore);\r
 686   return(MagickTrue);\r
 687 }\r
 688 \f\r
 689 /*\r
 690 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
 691 %                                                                             %\r
 692 %                                                                             %\r
 693 %                                                                             %\r
 694 %   N e w L i n k e d L i s t I n f o                                         %\r
 695 %                                                                             %\r
 696 %                                                                             %\r
 697 %                                                                             %\r
 698 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
 699 %\r
 700 %  NewLinkedList() returns a pointer to a LinkedListInfo structure\r
 701 %  initialized to default values.\r
 702 %\r
 703 %  The format of the NewLinkedList method is:\r
 704 %\r
 705 %      LinkedListInfo *NewLinkedList(const size_t capacity)\r
 706 %\r
 707 %  A description of each parameter follows:\r
 708 %\r
 709 %    o capacity: the maximum number of elements in the list.\r
 710 %\r
 711 */\r
 712 MagickExport LinkedListInfo *NewLinkedList(const size_t capacity)\r
 713 {\r
 714   LinkedListInfo\r
 715     *list_info;\r
 716 \r
 717   list_info=(LinkedListInfo *) AcquireMagickMemory(sizeof(*list_info));\r
 718   if (list_info == (LinkedListInfo *) NULL)\r
 719     ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");\r
 720   (void) ResetMagickMemory(list_info,0,sizeof(*list_info));\r
 721   list_info->capacity=capacity == 0 ? (size_t) (~0) : capacity;\r
 722   list_info->elements=0;\r
 723   list_info->head=(ElementInfo *) NULL;\r
 724   list_info->tail=(ElementInfo *) NULL;\r
 725   list_info->next=(ElementInfo *) NULL;\r
 726   list_info->semaphore=AcquireSemaphoreInfo();\r
 727   list_info->signature=MagickCoreSignature;\r
 728   return(list_info);\r
 729 }\r
 730 \f\r
 731 /*\r
 732 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
 733 %                                                                             %\r
 734 %                                                                             %\r
 735 %                                                                             %\r
 736 %   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       %\r
 737 %                                                                             %\r
 738 %                                                                             %\r
 739 %                                                                             %\r
 740 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
 741 %\r
 742 %  RemoveElementByValueFromLinkedList() removes an element from the linked-list\r
 743 %  by value.\r
 744 %\r
 745 %  The format of the RemoveElementByValueFromLinkedList method is:\r
 746 %\r
 747 %      void *RemoveElementByValueFromLinkedList(LinkedListInfo *list_info,\r
 748 %        const void *value)\r
 749 %\r
 750 %  A description of each parameter follows:\r
 751 %\r
 752 %    o list_info: the list info.\r
 753 %\r
 754 %    o value: the value.\r
 755 %\r
 756 */\r
 757 MagickExport void *RemoveElementByValueFromLinkedList(LinkedListInfo *list_info,\r
 758   const void *value)\r
 759 {\r
 760   ElementInfo\r
 761     *next;\r
 762 \r
 763   assert(list_info != (LinkedListInfo *) NULL);\r
 764   assert(list_info->signature == MagickCoreSignature);\r
 765   if ((list_info->elements == 0) || (value == (const void *) NULL))\r
 766     return((void *) NULL);\r
 767   LockSemaphoreInfo(list_info->semaphore);\r
 768   if (value == list_info->head->value)\r
 769     {\r
 770       if (list_info->next == list_info->head)\r
 771         list_info->next=list_info->head->next;\r
 772       next=list_info->head;\r
 773       list_info->head=list_info->head->next;\r
 774       next=(ElementInfo *) RelinquishMagickMemory(next);\r
 775     }\r
 776   else\r
 777     {\r
 778       ElementInfo\r
 779         *element;\r
 780 \r
 781       next=list_info->head;\r
 782       while ((next->next != (ElementInfo *) NULL) &&\r
 783              (next->next->value != value))\r
 784         next=next->next;\r
 785       if (next->next == (ElementInfo *) NULL)\r
 786         {\r
 787           UnlockSemaphoreInfo(list_info->semaphore);\r
 788           return((void *) NULL);\r
 789         }\r
 790       element=next->next;\r
 791       next->next=element->next;\r
 792       if (element == list_info->tail)\r
 793         list_info->tail=next;\r
 794       if (list_info->next == element)\r
 795         list_info->next=element->next;\r
 796       element=(ElementInfo *) RelinquishMagickMemory(element);\r
 797     }\r
 798   list_info->elements--;\r
 799   UnlockSemaphoreInfo(list_info->semaphore);\r
 800   return((void *) value);\r
 801 }\r
 802 \f\r
 803 /*\r
 804 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
 805 %                                                                             %\r
 806 %                                                                             %\r
 807 %                                                                             %\r
 808 %   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                     %\r
 809 %                                                                             %\r
 810 %                                                                             %\r
 811 %                                                                             %\r
 812 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
 813 %\r
 814 %  RemoveElementFromLinkedList() removes an element from the linked-list at the\r
 815 %  specified location.\r
 816 %\r
 817 %  The format of the RemoveElementFromLinkedList method is:\r
 818 %\r
 819 %      void *RemoveElementFromLinkedList(LinkedListInfo *list_info,\r
 820 %        const size_t index)\r
 821 %\r
 822 %  A description of each parameter follows:\r
 823 %\r
 824 %    o list_info: the linked-list info.\r
 825 %\r
 826 %    o index: the index.\r
 827 %\r
 828 */\r
 829 MagickExport void *RemoveElementFromLinkedList(LinkedListInfo *list_info,\r
 830   const size_t index)\r
 831 {\r
 832   ElementInfo\r
 833     *next;\r
 834 \r
 835   register ssize_t\r
 836     i;\r
 837 \r
 838   void\r
 839     *value;\r
 840 \r
 841   assert(list_info != (LinkedListInfo *) NULL);\r
 842   assert(list_info->signature == MagickCoreSignature);\r
 843   if (index >= list_info->elements)\r
 844     return((void *) NULL);\r
 845   LockSemaphoreInfo(list_info->semaphore);\r
 846   if (index == 0)\r
 847     {\r
 848       if (list_info->next == list_info->head)\r
 849         list_info->next=list_info->head->next;\r
 850       value=list_info->head->value;\r
 851       next=list_info->head;\r
 852       list_info->head=list_info->head->next;\r
 853       next=(ElementInfo *) RelinquishMagickMemory(next);\r
 854     }\r
 855   else\r
 856     {\r
 857       ElementInfo\r
 858         *element;\r
 859 \r
 860       next=list_info->head;\r
 861       for (i=1; i < (ssize_t) index; i++)\r
 862         next=next->next;\r
 863       element=next->next;\r
 864       next->next=element->next;\r
 865       if (element == list_info->tail)\r
 866         list_info->tail=next;\r
 867       if (list_info->next == element)\r
 868         list_info->next=element->next;\r
 869       value=element->value;\r
 870       element=(ElementInfo *) RelinquishMagickMemory(element);\r
 871     }\r
 872   list_info->elements--;\r
 873   UnlockSemaphoreInfo(list_info->semaphore);\r
 874   return(value);\r
 875 }\r
 876 \r
 877 /*\r
 878 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
 879 %                                                                             %\r
 880 %                                                                             %\r
 881 %                                                                             %\r
 882 %   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             %\r
 883 %                                                                             %\r
 884 %                                                                             %\r
 885 %                                                                             %\r
 886 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
 887 %\r
 888 %  RemoveLastElementFromLinkedList() removes the last element from the\r
 889 %  linked-list.\r
 890 %\r
 891 %  The format of the RemoveLastElementFromLinkedList method is:\r
 892 %\r
 893 %      void *RemoveLastElementFromLinkedList(LinkedListInfo *list_info)\r
 894 %\r
 895 %  A description of each parameter follows:\r
 896 %\r
 897 %    o list_info: the linked-list info.\r
 898 %\r
 899 */\r
 900 MagickExport void *RemoveLastElementFromLinkedList(LinkedListInfo *list_info)\r
 901 {\r
 902   void\r
 903     *value;\r
 904 \r
 905   assert(list_info != (LinkedListInfo *) NULL);\r
 906   assert(list_info->signature == MagickCoreSignature);\r
 907   if (list_info->elements == 0)\r
 908     return((void *) NULL);\r
 909   LockSemaphoreInfo(list_info->semaphore);\r
 910   if (list_info->next == list_info->tail)\r
 911     list_info->next=(ElementInfo *) NULL;\r
 912   if (list_info->elements == 1UL)\r
 913     {\r
 914       value=list_info->head->value;\r
 915       list_info->head=(ElementInfo *) NULL;\r
 916       list_info->tail=(ElementInfo *) RelinquishMagickMemory(list_info->tail);\r
 917     }\r
 918   else\r
 919     {\r
 920       ElementInfo\r
 921         *next;\r
 922 \r
 923       value=list_info->tail->value;\r
 924       next=list_info->head;\r
 925       while (next->next != list_info->tail)\r
 926         next=next->next;\r
 927       list_info->tail=(ElementInfo *) RelinquishMagickMemory(list_info->tail);\r
 928       list_info->tail=next;\r
 929       next->next=(ElementInfo *) NULL;\r
 930     }\r
 931   list_info->elements--;\r
 932   UnlockSemaphoreInfo(list_info->semaphore);\r
 933   return(value);\r
 934 }\r
 935 \f\r
 936 /*\r
 937 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
 938 %                                                                             %\r
 939 %                                                                             %\r
 940 %                                                                             %\r
 941 %   R e s e t L i n k e d L i s t I t e r a t o r                             %\r
 942 %                                                                             %\r
 943 %                                                                             %\r
 944 %                                                                             %\r
 945 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
 946 %\r
 947 %  ResetLinkedListIterator() resets the lined-list iterator.  Use it in\r
 948 %  conjunction with GetNextValueInLinkedList() to iterate over all the values\r
 949 %  in the linked-list.\r
 950 %\r
 951 %  The format of the ResetLinkedListIterator method is:\r
 952 %\r
 953 %      ResetLinkedListIterator(LinkedListInfo *list_info)\r
 954 %\r
 955 %  A description of each parameter follows:\r
 956 %\r
 957 %    o list_info: the linked-list info.\r
 958 %\r
 959 */\r
 960 MagickExport void ResetLinkedListIterator(LinkedListInfo *list_info)\r
 961 {\r
 962   assert(list_info != (LinkedListInfo *) NULL);\r
 963   assert(list_info->signature == MagickCoreSignature);\r
 964   LockSemaphoreInfo(list_info->semaphore);\r
 965   list_info->next=list_info->head;\r
 966   UnlockSemaphoreInfo(list_info->semaphore);\r
 967 }\r