Download Reference Manual
The Developer's Library for D
About Wiki Forums Source Search Contact

root/trunk/tango/util/container/HashMap.d

Revision 5421, 40.4 kB (checked in by kris, 2 years ago)

added support for retaining the key hash-value (via a -version=HashCache? in the interim)

  • Property svn:eol-style set to native
Line 
1 /*******************************************************************************
2
3         copyright:      Copyright (c) 2008 Kris Bell. All rights reserved
4
5         license:        BSD style: $(LICENSE)
6
7         version:        Apr 2008: Initial release
8
9         authors:        Kris
10
11         Since:          0.99.7
12
13         Based upon Doug Lea's Java collection package
14
15 *******************************************************************************/
16
17 module tango.util.container.HashMap;
18
19 private import tango.util.container.Slink;
20
21 public  import tango.util.container.Container;
22
23 private import tango.util.container.model.IContainer;
24
25 private import tango.core.Exception : NoSuchElementException;
26
27 /*******************************************************************************
28
29         Hash table implementation of a Map
30
31         ---
32         Iterator iterator ()
33         int opApply (int delegate(ref V value) dg)
34         int opApply (int delegate(ref K key, ref V value) dg)
35
36         bool get (K key, ref V element)
37         bool keyOf (V value, ref K key)
38         bool contains (V element)
39         bool containsPair (K key, V element)
40
41         bool removeKey (K key)
42         bool take (ref V element)
43         bool take (K key, ref V element)
44         size_t remove (V element, bool all)
45         size_t remove (IContainer!(V) e, bool all)
46         size_t replace (V oldElement, V newElement, bool all)
47         bool replacePair (K key, V oldElement, V newElement)
48
49         bool add (K key, V element)
50         bool opIndexAssign (V element, K key)
51         V    opIndex (K key)
52         V*   opIn_r (K key)
53
54         size_t size ()
55         bool isEmpty ()
56         V[] toArray (V[] dst)
57         HashMap dup ()
58         HashMap clear ()
59         HashMap reset ()
60         size_t buckets ()
61         float threshold ()
62         void buckets (size_t cap)
63         void threshold (float desired)
64         ---
65
66 *******************************************************************************/
67
68 class HashMap (K, V, alias Hash = Container.hash,
69                      alias Reap = Container.reap,
70                      alias Heap = Container.DefaultCollect)
71                      : IContainer!(V)
72 {
73         // bucket types
74         version (HashCache)
75                  private alias Slink!(V, K, false, true) Type;
76             else
77                 private alias Slink!(V, K) Type;
78
79         private alias Type         *Ref;
80
81         // allocator type
82         private alias Heap!(Type)  Alloc;
83
84         // each table entry is a linked list, or null
85         private Ref                table[];
86        
87         // number of elements contained
88         private size_t             count;
89
90         // the threshold load factor
91         private float              loadFactor;
92
93         // configured heap manager
94         private Alloc              heap;
95        
96         // mutation tag updates on each change
97         private size_t             mutation;
98
99         /***********************************************************************
100
101                 Construct a HashMap instance
102
103         ***********************************************************************/
104
105         this (float f = Container.defaultLoadFactor)
106         {
107                 loadFactor = f;
108         }
109
110         /***********************************************************************
111
112                 Clean up when deleted
113
114         ***********************************************************************/
115
116         ~this ()
117         {
118                 reset;
119         }
120
121         /***********************************************************************
122
123                 Return a generic iterator for contained elements
124                 
125         ***********************************************************************/
126
127         final Iterator iterator ()
128         {
129                 Iterator i = void;
130                 i.mutation = mutation;
131                 i.table = table;
132                 i.owner = this;
133                 i.cell = null;
134                 i.row = 0;
135                 return i;
136         }
137
138         /***********************************************************************
139
140
141         ***********************************************************************/
142
143         final int opApply (int delegate(ref K key, ref V value) dg)
144         {
145                 return iterator.opApply (dg);
146         }
147
148         /***********************************************************************
149
150
151         ***********************************************************************/
152
153         final int opApply (int delegate(ref V value) dg)
154         {
155                 return iterator.opApply ((ref K k, ref V v) {return dg(v);});
156         }
157
158         /***********************************************************************
159
160                 Return the number of elements contained
161                 
162         ***********************************************************************/
163
164         final size_t size ()
165         {
166                 return count;
167         }
168        
169         /***********************************************************************
170
171                 Add a new element to the set. Does not add if there is an
172                 equivalent already present. Returns true where an element
173                 is added, false where it already exists (and was possibly
174                 updated).
175                 
176                 Time complexity: O(1) average; O(n) worst.
177                 
178         ***********************************************************************/
179
180         final bool add (K key, V element)
181         {
182                 if (table is null)
183                     resize (Container.defaultInitialBuckets);
184
185                 auto hd = &table [Hash (key, table.length)];
186                 auto node = *hd;
187                
188                 if (node is null)
189                    {
190                    *hd = heap.allocate.set (key, element, null);
191                    increment;
192                    }
193                 else
194                    {
195                    auto p = node.findKey (key);
196                    if (p)
197                       {
198                       if (element != p.value)
199                          {
200                          p.value = element;
201                          mutate;
202                          }
203                       return false;
204                       }
205                    else
206                       {
207                       *hd = heap.allocate.set (key, element, node);
208                       increment;
209
210                       // we only check load factor on add to nonempty bin
211                       checkLoad;
212                       }
213                    }
214                 return true;
215         }
216
217         /***********************************************************************
218
219                 Add a new element to the set. Does not add if there is an
220                 equivalent already present. Returns true where an element
221                 is added, false where it already exists (and was possibly
222                 updated). This variation invokes the given retain function
223                 when the key does not already exist. You would typically
224                 use that to duplicate a char[], or whatever is required.
225                 
226                 Time complexity: O(1) average; O(n) worst.
227                 
228         ***********************************************************************/
229
230         final bool add (K key, V element, K function(K) retain)
231         {
232                 if (table is null)
233                     resize (Container.defaultInitialBuckets);
234
235                 auto hd = &table [Hash (key, table.length)];
236                 auto node = *hd;
237                
238                 if (node is null)
239                    {
240                    *hd = heap.allocate.set (retain(key), element, null);
241                    increment;
242                    }
243                 else
244                    {
245                    auto p = node.findKey (key);
246                    if (p)
247                       {
248                       if (element != p.value)
249                          {
250                          p.value = element;
251                          mutate;
252                          }
253                       return false;
254                       }
255                    else
256                       {
257                       *hd = heap.allocate.set (retain(key), element, node);
258                       increment;
259
260                       // we only check load factor on add to nonempty bin
261                       checkLoad;
262                       }
263                    }
264                 return true;
265         }
266
267         /***********************************************************************
268
269                 Return the element associated with key
270
271                 param: a key
272                 param: a value reference (where returned value will reside)
273                 Returns: whether the key is contained or not
274         
275         ************************************************************************/
276
277         final bool get (K key, ref V element)
278         {
279                 if (count)
280                    {
281                    auto p = table [Hash (key, table.length)];
282                    if (p && (p = p.findKey(key)) !is null)
283                       {
284                       element = p.value;
285                       return true;
286                       }
287                    }
288                 return false;
289         }
290
291         /***********************************************************************
292
293                 Return the element associated with key
294
295                 param: a key
296                 Returns: a pointer to the located value, or null if not found
297         
298         ************************************************************************/
299
300         final V* opIn_r (K key)
301         {
302                 if (count)
303                    {
304                    auto p = table [Hash (key, table.length)];
305                    if (p && (p = p.findKey(key)) !is null)
306                        return &p.value;
307                    }
308                 return null;
309         }
310
311         /***********************************************************************
312
313                 Does this set contain the given element?
314         
315                 Time complexity: O(1) average; O(n) worst
316                 
317         ***********************************************************************/
318
319         final bool contains (V element)
320         {
321                 return instances (element) > 0;
322         }
323
324         /***********************************************************************
325
326                 Time complexity: O(n).
327         
328         ************************************************************************/
329        
330         final bool keyOf (V value, ref K key)
331         {
332                 if (count)
333                     foreach (list; table)
334                             if (list)
335                                {
336                                auto p = list.find (value);
337                                if (p)
338                                   {
339                                   key = p.key;
340                                   return true;
341                                   }
342                                }
343                 return false;
344         }
345
346         /***********************************************************************
347
348                 Time complexity: O(1) average; O(n) worst.
349                 
350         ***********************************************************************/
351        
352         final bool containsKey (K key)
353         {
354                 if (count)
355                    {
356                    auto p = table[Hash (key, table.length)];
357                    if (p && p.findKey(key))
358                        return true;
359                    }
360                 return false;
361         }
362
363         /***********************************************************************
364
365                 Time complexity: O(1) average; O(n) worst.
366         
367         ***********************************************************************/
368        
369         final bool containsPair (K key, V element)
370         {
371                 if (count)
372                    {                   
373                    auto p = table[Hash (key, table.length)];
374                    if (p && p.findPair (key, element))
375                        return true;
376                    }
377                 return false;
378         }
379
380         /***********************************************************************
381
382                 Make an independent copy of the container. Does not clone
383                 elements
384                 
385                 Time complexity: O(n)
386                 
387         ***********************************************************************/
388
389         final HashMap dup ()
390         {
391                 auto clone = new HashMap!(K, V, Hash, Reap, Heap) (loadFactor);
392
393                 if (count)
394                    {
395                    clone.buckets (buckets);
396
397                    foreach (key, value; iterator)
398                             clone.add (key, value);
399                    }
400                 return clone;
401         }
402
403         /***********************************************************************
404
405                 Time complexity: O(1) average; O(n) worst.
406         
407         ***********************************************************************/
408        
409         final bool removeKey (K key)
410         {
411                 V value;
412
413                 return take (key, value);
414         }
415
416         /***********************************************************************
417
418                 Time complexity: O(1) average; O(n) worst.
419         
420         ***********************************************************************/
421        
422         final bool replaceKey (K key, K replace)
423         {
424                 if (count)
425                    {
426                    auto h = Hash (key, table.length);
427                    auto hd = table[h];
428                    auto trail = hd;
429                    auto p = hd;
430
431                    while (p)
432                          {
433                          auto n = p.next;
434                          if (key == p.key)
435                             {
436                             if (p is hd)
437                                 table[h] = n;
438                             else
439                                trail.detachNext;
440                            
441                             // inject into new location
442                             h = Hash (replace, table.length);
443                             table[h] = p.set (replace, p.value, table[h]);
444                             return true;
445                             }
446                          else
447                             {
448                             trail = p;
449                             p = n;
450                             }
451                          }
452                    }
453                 return false;
454         }
455
456         /***********************************************************************
457
458                 Time complexity: O(1) average; O(n) worst.
459         
460         ***********************************************************************/
461        
462         final bool replacePair (K key, V oldElement, V newElement)
463         {
464                 if (count)
465                    {
466                    auto p = table [Hash (key, table.length)];
467                    if (p)
468                       {
469                       auto c = p.findPair (key, oldElement);
470                       if (c)
471                          {
472                          c.value = newElement;
473                          mutate;
474                          return true;
475                          }
476                       }
477                    }
478                 return false;
479         }
480
481         /***********************************************************************
482
483                 Remove and expose the first element. Returns false when no
484                 more elements are contained
485         
486                 Time complexity: O(n)
487
488         ***********************************************************************/
489
490         final bool take (ref V element)
491         {
492                 if (count)
493                     foreach (ref list; table)
494                              if (list)
495                                 {
496                                 auto p = list;
497                                 element = p.value;
498                                 list = p.next;
499                                 decrement (p);
500                                 return true;
501                                 }
502                 return false;
503         }
504
505         /***********************************************************************
506
507                 Remove and expose the element associated with key
508
509                 param: a key
510                 param: a value reference (where returned value will reside)
511                 Returns: whether the key is contained or not
512         
513                 Time complexity: O(1) average, O(n) worst
514
515         ***********************************************************************/
516        
517         final bool take (K key, ref V value)
518         {
519                 if (count)
520                    {
521                    auto p = &table [Hash (key, table.length)];
522                    auto n = *p;
523
524                    while ((n = *p) !is null)
525                            if (key == n.key)
526                               {
527                               *p = n.next;
528                               value = n.value;
529                               decrement (n);
530                               return true;
531                               }
532                            else
533                               p = &n.next;
534                    }
535                 return false;
536         }
537
538         /***********************************************************************
539
540                 Operator shortcut for assignment
541
542         ***********************************************************************/
543
544         final bool opIndexAssign (V element, K key)
545         {
546                 return add (key, element);
547         }
548
549         /***********************************************************************
550
551                 Operator retreival function
552
553                 Throws NoSuchElementException where key is missing
554
555         ***********************************************************************/
556
557         final V opIndex (K key)
558         {
559                 auto p = opIn_r (key);
560                 if (p)
561                     return *p;
562                 throw new NoSuchElementException ("missing or invalid key");
563         }
564
565         /***********************************************************************
566
567                 Remove a set of values
568
569         ************************************************************************/
570
571         final size_t remove (IContainer!(V) e, bool all = false)
572         {
573                 auto i = count;
574                 foreach (value; e)
575                          remove (value, all);
576                 return i - count;
577         }
578
579         /***********************************************************************
580
581                 Removes element instances, and returns the number of elements
582                 removed
583                 
584                 Time complexity: O(1) average; O(n) worst
585         
586         ************************************************************************/
587
588         final size_t remove (V element, bool all = false)
589         {
590                 auto i = count;
591                
592                 if (i)
593                     foreach (ref node; table)
594                             {                         
595                             auto p = node;
596                             auto trail = node;
597
598                             while (p)
599                                   {     
600                                   auto n = p.next;
601                                   if (element == p.value)
602                                      {
603                                      decrement (p);
604                                      if (p is node)
605                                         {
606                                         node = n;
607                                         trail = n;
608                                         }
609                                      else
610                                         trail.next = n;
611
612                                      if (! all)
613                                            return i - count;
614                                      else
615                                         p = n;
616                                      }
617                                   else
618                                      {
619                                      trail = p;
620                                      p = n;
621                                      }
622                                   }
623                             }
624
625                 return i - count;
626         }
627
628         /***********************************************************************
629
630                 Replace instances of oldElement with newElement, and returns
631                 the number of replacements
632
633                 Time complexity: O(n).
634                 
635         ************************************************************************/
636
637         final size_t replace (V oldElement, V newElement, bool all = false)
638         {
639                 size_t i;
640                
641                 if (count && oldElement != newElement)
642                     foreach (node; table)
643                              while (node && (node = node.find(oldElement)) !is null)
644                                    {
645                                    ++i;
646                                    mutate;
647                                    node.value = newElement;
648                                    if (! all)
649                                          return i;
650                                    }
651                 return i;
652         }
653        
654         /***********************************************************************
655
656                 Clears the HashMap contents. Various attributes are
657                 retained, such as the internal table itself. Invoke
658                 reset() to drop everything.
659
660                 Time complexity: O(n)
661                 
662         ***********************************************************************/
663
664         final HashMap clear ()
665         {
666                 return clear (false);
667         }
668
669         /***********************************************************************
670
671                 Reset the HashMap contents. This releases more memory
672                 than clear() does
673
674                 Time complexity: O(n)
675                 
676         ***********************************************************************/
677
678         final HashMap reset ()
679         {
680                 clear (true);
681                 heap.collect (table);
682                 table = null;
683                 return this;
684         }
685
686         /***********************************************************************
687
688                 Return the number of buckets
689
690                 Time complexity: O(1)
691
692         ***********************************************************************/
693
694         final size_t buckets ()
695         {
696                 return table ? table.length : 0;
697         }
698
699         /***********************************************************************
700
701                 Set the desired number of buckets in the hash table. Any
702                 value greater than or equal to one is OK.
703
704                 If different than current buckets, causes a version change
705                 
706                 Time complexity: O(n)
707
708         ***********************************************************************/
709
710         final HashMap buckets (size_t cap)
711         {
712                 if (cap < Container.defaultInitialBuckets)
713                     cap = Container.defaultInitialBuckets;
714
715                 if (cap !is buckets)
716                     resize (cap);
717                 return this;
718         }
719
720         /***********************************************************************
721
722                 Set the number of buckets for the given threshold
723                 and resize as required
724                 
725                 Time complexity: O(n)
726
727         ***********************************************************************/
728
729         final HashMap buckets (size_t cap, float threshold)
730         {
731                 loadFactor = threshold;
732                 return buckets (cast(size_t)(cap / threshold) + 1);
733         }
734
735         /***********************************************************************
736
737                 Configure the assigned allocator with the size of each
738                 allocation block (number of nodes allocated at one time)
739                 and the number of nodes to pre-populate the cache with.
740                 
741                 Time complexity: O(n)
742
743         ***********************************************************************/
744
745         final HashMap cache (size_t chunk, size_t count=0)
746         {
747                 heap.config (chunk, count);
748                 return this;
749         }
750
751         /***********************************************************************
752
753                 Return the current load factor threshold
754
755                 The Hash table occasionally checka against the load factor
756                 resizes itself if it has gone past it.
757
758                 Time complexity: O(1)
759
760         ***********************************************************************/
761
762         final float threshold ()
763         {
764                 return loadFactor;
765         }
766
767         /***********************************************************************
768
769                 Set the resize threshold, and resize as required
770                 Set the current desired load factor. Any value greater
771                 than 0 is OK. The current load is checked against it,
772                 possibly causing a resize.
773                 
774                 Time complexity: O(n)
775                 
776         ***********************************************************************/
777
778         final void threshold (float desired)
779         {
780                 assert (desired > 0.0);
781                 loadFactor = desired;
782                 if (table)
783                     checkLoad;
784         }
785
786         /***********************************************************************
787
788                 Copy and return the contained set of values in an array,
789                 using the optional dst as a recipient (which is resized
790                 as necessary).
791
792                 Returns a slice of dst representing the container values.
793                 
794                 Time complexity: O(n)
795                 
796         ***********************************************************************/
797
798         final V[] toArray (V[] dst = null)
799         {
800                 if (dst.length < count)
801                     dst.length = count;
802
803                 size_t i = 0;
804                 foreach (k, v; this)
805                          dst[i++] = v;
806                 return dst [0 .. count];                       
807         }
808
809         /***********************************************************************
810
811                 Is this container empty?
812                 
813                 Time complexity: O(1)
814                 
815         ***********************************************************************/
816
817         final bool isEmpty ()
818         {
819                 return count is 0;
820         }
821
822         /***********************************************************************
823
824                 Sanity check
825
826         ***********************************************************************/
827                        
828         final HashMap check ()
829         {
830                 assert(!(table is null && count !is 0));
831                 assert((table is null || table.length > 0));
832                 assert(loadFactor > 0.0f);
833
834                 if (table)
835                    {
836                    size_t c = 0;
837                    for (size_t i=0; i < table.length; ++i)
838                         for (auto p = table[i]; p; p = p.next)
839                             {
840                             ++c;
841                             assert(contains(p.value));
842                             assert(containsKey(p.key));
843                             assert(instances(p.value) >= 1);
844                             assert(containsPair(p.key, p.value));
845                             assert(Hash (p.key, table.length) is i);
846                             }
847                    assert(c is count);
848                    }
849                 return this;
850         }
851
852         /***********************************************************************
853
854                 Count the element instances in the set (there can only be
855                 0 or 1 instances in a Set).
856                 
857                 Time complexity: O(n)
858                 
859         ***********************************************************************/
860
861         private size_t instances (V element)
862         {
863                 size_t c = 0;
864                 foreach (node; table)
865                          if (node)
866                              c += node.count (element);
867                 return c;
868         }
869
870         /***********************************************************************
871
872                  Check to see if we are past load factor threshold. If so,
873                  resize so that we are at half of the desired threshold.
874                 
875         ***********************************************************************/
876
877         private HashMap checkLoad ()
878         {
879                 float fc = count;
880                 float ft = table.length;
881                 if (fc / ft > loadFactor)
882                     resize (2 * cast(size_t)(fc / loadFactor) + 1);
883                 return this;
884         }
885
886         /***********************************************************************
887
888                 resize table to new capacity, rehashing all elements
889                 
890         ***********************************************************************/
891
892         private void resize (size_t newCap)
893         {
894                 // Stdout.formatln ("resize {}", newCap);
895                 auto newtab = heap.allocate (newCap);
896                 mutate;
897
898                 foreach (bucket; table)
899                          while (bucket)
900                                {
901                                auto n = bucket.next;
902                                version (HashCache)
903                                         auto h = n.cache;
904                                   else
905                                      auto h = Hash (bucket.key, newCap);
906                                bucket.next = newtab[h];
907                                newtab[h] = bucket;
908                                bucket = n;
909                                }
910
911                 // release the prior table and assign new one
912                 heap.collect (table);
913                 table = newtab;
914         }
915
916         /***********************************************************************
917
918                 Remove the indicated node. We need to traverse buckets
919                 for this, since we're singly-linked only. Better to save
920                 the per-node memory than to gain a little on each remove
921
922                 Used by iterators only
923                 
924         ***********************************************************************/
925
926         private bool removeNode (Ref node, Ref* list)
927         {
928                 auto p = list;
929                 auto n = *p;
930
931                 while ((n = *p) !is null)
932                         if (n is node)
933                            {
934                            *p = n.next;
935                            decrement (n);
936                            return true;
937                            }
938                         else
939                            p = &n.next;
940                 return false;
941         }
942
943         /***********************************************************************
944
945                 Clears the HashMap contents. Various attributes are
946                 retained, such as the internal table itself. Invoke
947                 reset() to drop everything.
948
949                 Time complexity: O(n)
950                 
951         ***********************************************************************/
952
953         private final HashMap clear (bool all)
954         {
955                 mutate;
956
957                 // collect each node if we can't collect all at once
958                 if (heap.collect(all) is false)
959                     foreach (v; table)
960                              while (v)
961                                    {
962                                    auto n = v.next;
963                                    decrement (v);
964                                    v = n;
965                                    }
966
967                 // retain table, but remove bucket chains
968                 foreach (ref v; table)
969                          v = null;
970
971                 count = 0;
972                 return this;
973         }
974
975         /***********************************************************************
976
977                 new element was added
978                 
979         ***********************************************************************/
980
981         private void increment ()
982         {
983                 ++mutation;
984                 ++count;
985         }
986        
987         /***********************************************************************
988
989                 element was removed
990                 
991         ***********************************************************************/
992
993         private void decrement (Ref p)
994         {
995                 Reap (p.key, p.value);
996                 heap.collect (p);
997                 ++mutation;
998                 --count;
999         }
1000        
1001         /***********************************************************************
1002
1003                 set was changed
1004                 
1005         ***********************************************************************/
1006
1007         private void mutate ()
1008         {
1009                 ++mutation;
1010         }
1011
1012         /***********************************************************************
1013
1014                 Iterator with no filtering
1015
1016         ***********************************************************************/
1017
1018         private struct Iterator
1019         {
1020                 size_t  row;
1021                 Ref     cell,
1022                         prior;
1023                 Ref[]   table;
1024                 HashMap owner;
1025                 size_t  mutation;
1026
1027                 /***************************************************************
1028
1029                         Did the container change underneath us?
1030
1031                 ***************************************************************/
1032
1033                 bool valid ()
1034                 {
1035                         return owner.mutation is mutation;
1036                 }               
1037
1038                 /***************************************************************
1039
1040                         Accesses the next value, and returns false when
1041                         there are no further values to traverse
1042
1043                 ***************************************************************/
1044
1045                 bool next (ref K k, ref V v)
1046                 {
1047                         auto n = next (k);
1048                         return (n) ? v = *n, true : false;
1049                 }
1050                
1051                 /***************************************************************
1052
1053                         Return a pointer to the next value, or null when
1054                         there are no further values to traverse
1055
1056                 ***************************************************************/
1057
1058                 V* next (ref K k)
1059                 {
1060                         while (cell is null)
1061                                if (row < table.length)
1062                                    cell = table [row++];
1063                                else
1064                                   return null;
1065  
1066                         prior = cell;
1067                         k = cell.key;
1068                         cell = cell.next;
1069                         return &prior.value;
1070
1071                 }
1072
1073                 /***************************************************************
1074
1075                         Foreach support
1076
1077                 ***************************************************************/
1078
1079                 int opApply (int delegate(ref K key, ref V value) dg)
1080                 {
1081                         int result;
1082
1083                         auto c = cell;
1084                         loop: while (true)
1085                               {
1086                               while (c is null)
1087                                      if (row < table.length)
1088                                          c = table [row++];
1089                                      else
1090                                         break loop;
1091  
1092                               prior = c;
1093                               c = c.next;
1094                               if ((result = dg(prior.key, prior.value)) != 0)
1095                                    break loop;
1096                               }
1097
1098                         cell = c;
1099                         return result;
1100                 }                               
1101
1102                 /***************************************************************
1103
1104                         Remove value at the current iterator location
1105
1106                 ***************************************************************/
1107
1108                 bool remove ()
1109                 {
1110                         if (prior)
1111                             if (owner.removeNode (prior, &table[row-1]))
1112                                {
1113                                // ignore this change
1114                                ++mutation;
1115                                return true;
1116                                }
1117
1118                         prior = null;
1119                         return false;
1120                 }
1121         }
1122 }
1123
1124
1125 /*******************************************************************************
1126
1127 *******************************************************************************/
1128
1129 debug (HashMap)
1130 {
1131         import tango.io.Stdout;
1132         import tango.core.Memory;
1133         import tango.time.StopWatch;
1134
1135         void main()
1136         {
1137                 // usage examples ...
1138                 auto map = new HashMap!(char[], int);
1139                 map.add ("foo", 1);
1140                 map.add ("bar", 2);
1141                 map.add ("wumpus", 3);
1142
1143                 // implicit generic iteration
1144                 foreach (key, value; map)
1145                          Stdout.formatln ("{}:{}", key, value);
1146
1147                 // explicit generic iteration
1148                 foreach (key, value; map.iterator)
1149                          Stdout.formatln ("{}:{}", key, value);
1150
1151                 // generic iteration with optional remove
1152                 auto s = map.iterator;
1153                 foreach (key, value; s)
1154                         {} // s.remove;
1155
1156                 // incremental iteration, with optional remove
1157                 char[] k;
1158                 int    v;
1159                 auto iterator = map.iterator;
1160                 while (iterator.next(k, v))
1161                       {} //iterator.remove;
1162                
1163                 // incremental iteration, with optional failfast
1164                 auto it = map.iterator;
1165                 while (it.valid && it.next(k, v))
1166                       {}
1167
1168                 // remove specific element
1169                 map.removeKey ("wumpus");
1170
1171                 // remove first element ...
1172                 while (map.take(v))
1173                        Stdout.formatln ("taking {}, {} left", v, map.size);
1174                  
1175                 // setup for benchmark, with a set of integers. We
1176                 // use a chunk allocator, and presize the bucket[]
1177                 auto test = new HashMap!(int, int);//, Container.hash, Container.reap, Container.ChunkGC);
1178                 test.buckets(1_500_000);//.cache(8000, 1000000);
1179                 const count = 1_000_000;
1180                 StopWatch w;
1181
1182                 GC.collect;
1183                 test.check;
1184
1185                 // benchmark adding
1186                 w.start;
1187                 for (int i=count; i--;)
1188                      test.add(i, i);
1189                 Stdout.formatln ("{} adds: {}/s", test.size, test.size/w.stop);
1190
1191                 // benchmark reading
1192                 w.start;
1193                 for (int i=count; i--;)
1194                      test.get(i, v);
1195                 Stdout.formatln ("{} lookups: {}/s", test.size, test.size/w.stop);
1196
1197                 // benchmark adding without allocation overhead
1198                 test.clear;
1199                 w.start;
1200                 for (int i=count; i--;)
1201                      test.add(i, i);
1202                 Stdout.formatln ("{} adds (after clear): {}/s", test.size, test.size/w.stop);
1203
1204                 // benchmark duplication
1205                 w.start;
1206                 auto dup = test.dup;
1207                 Stdout.formatln ("{} element dup: {}/s", dup.size, dup.size/w.stop);
1208
1209                 // benchmark iteration
1210                 w.start;
1211                 foreach (key, value; test) {}
1212                 Stdout.formatln ("{} element iteration: {}/s", test.size, test.size/w.stop);
1213
1214                 GC.collect;
1215                 test.check;
1216 /+
1217                 auto aa = new HashMap!(long, int, Container.hash, Container.reap, Container.Chunk);
1218                 aa.buckets(7_500_000).cache(100000, 5_000_000);
1219                 w.start;
1220                 for (int i=5_000_000; i--;)
1221                      aa.add (i, 0);
1222                 Stdout.formatln ("{} test iteration: {}/s", aa.size, aa.size/w.stop);
1223 +/
1224         }
1225 }
Note: See TracBrowser for help on using the browser.