]> granicus.if.org Git - imagemagick/blob - MagickCore/hashmap.c
(no commit message)
[imagemagick] / 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 }