LEFT | RIGHT |
1 // Copyright 2009 The Go Authors. All rights reserved. | 1 // Copyright 2009 The Go Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style | 2 // Use of this source code is governed by a BSD-style |
3 // license that can be found in the LICENSE file. | 3 // license that can be found in the LICENSE file. |
4 | 4 |
5 #include "runtime.h" | 5 #include "runtime.h" |
6 #include "arch_GOARCH.h" | 6 #include "arch_GOARCH.h" |
7 #include "malloc.h" | 7 #include "malloc.h" |
8 #include "hashmap.h" | 8 #include "hashmap.h" |
9 #include "type.h" | 9 #include "type.h" |
10 #include "race.h" | 10 #include "race.h" |
(...skipping 204 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
215 | 215 |
216 flags = CanFreeBucket; | 216 flags = CanFreeBucket; |
217 | 217 |
218 // figure out how big we have to make everything | 218 // figure out how big we have to make everything |
219 keysize = t->key->size; | 219 keysize = t->key->size; |
220 if(keysize > MAXKEYSIZE) { | 220 if(keysize > MAXKEYSIZE) { |
221 flags |= IndirectKey | CanFreeKey; | 221 flags |= IndirectKey | CanFreeKey; |
222 keysize = sizeof(byte*); | 222 keysize = sizeof(byte*); |
223 } | 223 } |
224 valuesize = t->elem->size; | 224 valuesize = t->elem->size; |
225 » if(valuesize >= MAXVALUESIZE) { | 225 » if(valuesize > MAXVALUESIZE) { |
226 flags |= IndirectValue; | 226 flags |= IndirectValue; |
227 valuesize = sizeof(byte*); | 227 valuesize = sizeof(byte*); |
228 } | 228 } |
229 bucketsize = offsetof(Bucket, data[0]) + (keysize + valuesize) * BUCKETS
IZE; | 229 bucketsize = offsetof(Bucket, data[0]) + (keysize + valuesize) * BUCKETS
IZE; |
230 | 230 |
231 // invariants we depend on. We should probably check these at compile t
ime | 231 // invariants we depend on. We should probably check these at compile t
ime |
232 // somewhere, but for now we'll do it here. | 232 // somewhere, but for now we'll do it here. |
233 if(t->key->align > BUCKETSIZE) | 233 if(t->key->align > BUCKETSIZE) |
234 runtime·throw("key align too big"); | 234 runtime·throw("key align too big"); |
235 if(t->elem->align > BUCKETSIZE) | 235 if(t->elem->align > BUCKETSIZE) |
(...skipping 12 matching lines...) Expand all Loading... |
248 runtime·throw("need padding in bucket (value)"); | 248 runtime·throw("need padding in bucket (value)"); |
249 | 249 |
250 // find size parameter which will hold the requested # of elements | 250 // find size parameter which will hold the requested # of elements |
251 B = 0; | 251 B = 0; |
252 while(hint > BUCKETSIZE && hint > LOAD * ((uintptr)1 << B)) | 252 while(hint > BUCKETSIZE && hint > LOAD * ((uintptr)1 << B)) |
253 B++; | 253 B++; |
254 | 254 |
255 // allocate initial hash table | 255 // allocate initial hash table |
256 // If hint is large zeroing this memory could take a while. | 256 // If hint is large zeroing this memory could take a while. |
257 if(checkgc) mstats.next_gc = mstats.heap_alloc; | 257 if(checkgc) mstats.next_gc = mstats.heap_alloc; |
258 » buckets = runtime·mallocgc(bucketsize << B, 0, 1, 0); | 258 » if(B == 0) { |
259 » for(i = 0; i < (uintptr)1 << B; i++) { | 259 » » // done lazily later. |
260 » » b = (Bucket*)(buckets + i * bucketsize); | 260 » » buckets = nil; |
261 » » clearbucket(b); | 261 » } else { |
| 262 » » buckets = runtime·mallocgc(bucketsize << B, 0, 1, 0); |
| 263 » » for(i = 0; i < (uintptr)1 << B; i++) { |
| 264 » » » b = (Bucket*)(buckets + i * bucketsize); |
| 265 » » » clearbucket(b); |
| 266 » » } |
262 } | 267 } |
263 | 268 |
264 // initialize Hmap | 269 // initialize Hmap |
265 // Note: we save all these stores to the end so gciter doesn't see | 270 // Note: we save all these stores to the end so gciter doesn't see |
266 // a partially initialized map. | 271 // a partially initialized map. |
267 h->count = 0; | 272 h->count = 0; |
268 h->B = B; | 273 h->B = B; |
269 h->flags = flags; | 274 h->flags = flags; |
270 h->keysize = keysize; | 275 h->keysize = keysize; |
271 h->valuesize = valuesize; | 276 h->valuesize = valuesize; |
(...skipping 196 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
468 check(t, h); | 473 check(t, h); |
469 } | 474 } |
470 | 475 |
471 // returns ptr to value associated with key *keyp, or nil if none. | 476 // returns ptr to value associated with key *keyp, or nil if none. |
472 // if it returns non-nil, updates *keyp to point to the currently stored key. | 477 // if it returns non-nil, updates *keyp to point to the currently stored key. |
473 static byte* | 478 static byte* |
474 hash_lookup(MapType *t, Hmap *h, byte **keyp) | 479 hash_lookup(MapType *t, Hmap *h, byte **keyp) |
475 { | 480 { |
476 void *key; | 481 void *key; |
477 uintptr hash; | 482 uintptr hash; |
478 » uintptr bucket; | 483 » uintptr bucket, oldbucket; |
479 Bucket *b; | 484 Bucket *b; |
480 uint8 top; | 485 uint8 top; |
481 uintptr i; | 486 uintptr i; |
482 bool eq; | 487 bool eq; |
483 byte *k, *k2, *v; | 488 byte *k, *k2, *v; |
484 | 489 |
485 key = *keyp; | 490 key = *keyp; |
486 if(docheck) | 491 if(docheck) |
487 check(t, h); | 492 check(t, h); |
| 493 if(h->count == 0) |
| 494 return nil; |
488 hash = h->hash0; | 495 hash = h->hash0; |
489 t->key->alg->hash(&hash, t->key->size, key); | 496 t->key->alg->hash(&hash, t->key->size, key); |
490 bucket = hash & (((uintptr)1 << h->B) - 1); | 497 bucket = hash & (((uintptr)1 << h->B) - 1); |
491 » if(h->oldbuckets != nil) | 498 » if(h->oldbuckets != nil) { |
492 » » grow_work(t, h, bucket); | 499 » » oldbucket = bucket & (((uintptr)1 << (h->B - 1)) - 1); |
493 » b = (Bucket*)(h->buckets + bucket * h->bucketsize); | 500 » » b = (Bucket*)(h->oldbuckets + oldbucket * h->bucketsize); |
| 501 » » if(evacuated(b)) { |
| 502 » » » b = (Bucket*)(h->buckets + bucket * h->bucketsize); |
| 503 » » } |
| 504 » } else { |
| 505 » » b = (Bucket*)(h->buckets + bucket * h->bucketsize); |
| 506 » } |
494 top = hash >> (sizeof(uintptr)*8 - 8); | 507 top = hash >> (sizeof(uintptr)*8 - 8); |
495 if(top == 0) | 508 if(top == 0) |
496 top = 1; | 509 top = 1; |
497 do { | 510 do { |
498 for(i = 0, k = b->data, v = k + h->keysize * BUCKETSIZE; i < BUC
KETSIZE; i++, k += h->keysize, v += h->valuesize) { | 511 for(i = 0, k = b->data, v = k + h->keysize * BUCKETSIZE; i < BUC
KETSIZE; i++, k += h->keysize, v += h->valuesize) { |
499 if(b->tophash[i] == top) { | 512 if(b->tophash[i] == top) { |
500 k2 = IK(h, k); | 513 k2 = IK(h, k); |
501 t->key->alg->equal(&eq, t->key->size, key, k2); | 514 t->key->alg->equal(&eq, t->key->size, key, k2); |
502 if(eq) { | 515 if(eq) { |
503 *keyp = k2; | 516 *keyp = k2; |
(...skipping 61 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
565 uint8 *inserti; | 578 uint8 *inserti; |
566 byte *insertk, *insertv; | 579 byte *insertk, *insertv; |
567 uint8 top; | 580 uint8 top; |
568 byte *k, *v; | 581 byte *k, *v; |
569 byte *kmem, *vmem; | 582 byte *kmem, *vmem; |
570 | 583 |
571 if(docheck) | 584 if(docheck) |
572 check(t, h); | 585 check(t, h); |
573 hash = h->hash0; | 586 hash = h->hash0; |
574 t->key->alg->hash(&hash, t->key->size, key); | 587 t->key->alg->hash(&hash, t->key->size, key); |
| 588 if(h->buckets == nil) { |
| 589 h->buckets = runtime·mallocgc(h->bucketsize, 0, 1, 0); |
| 590 b = (Bucket*)(h->buckets); |
| 591 clearbucket(b); |
| 592 } |
| 593 |
575 again: | 594 again: |
576 bucket = hash & (((uintptr)1 << h->B) - 1); | 595 bucket = hash & (((uintptr)1 << h->B) - 1); |
577 if(h->oldbuckets != nil) | 596 if(h->oldbuckets != nil) |
578 grow_work(t, h, bucket); | 597 grow_work(t, h, bucket); |
579 b = (Bucket*)(h->buckets + bucket * h->bucketsize); | 598 b = (Bucket*)(h->buckets + bucket * h->bucketsize); |
580 top = hash >> (sizeof(uintptr)*8 - 8); | 599 top = hash >> (sizeof(uintptr)*8 - 8); |
581 if(top == 0) | 600 if(top == 0) |
582 top = 1; | 601 top = 1; |
583 inserti = 0; | 602 inserti = 0; |
584 insertk = nil; | 603 insertk = nil; |
(...skipping 67 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
652 uintptr hash; | 671 uintptr hash; |
653 uintptr bucket; | 672 uintptr bucket; |
654 Bucket *b; | 673 Bucket *b; |
655 uint8 top; | 674 uint8 top; |
656 uintptr i; | 675 uintptr i; |
657 byte *k, *v; | 676 byte *k, *v; |
658 bool eq; | 677 bool eq; |
659 ········ | 678 ········ |
660 if(docheck) | 679 if(docheck) |
661 check(t, h); | 680 check(t, h); |
| 681 if(h->count == 0) |
| 682 return; |
662 hash = h->hash0; | 683 hash = h->hash0; |
663 t->key->alg->hash(&hash, t->key->size, key); | 684 t->key->alg->hash(&hash, t->key->size, key); |
664 bucket = hash & (((uintptr)1 << h->B) - 1); | 685 bucket = hash & (((uintptr)1 << h->B) - 1); |
665 if(h->oldbuckets != nil) | 686 if(h->oldbuckets != nil) |
666 grow_work(t, h, bucket); | 687 grow_work(t, h, bucket); |
667 b = (Bucket*)(h->buckets + bucket * h->bucketsize); | 688 b = (Bucket*)(h->buckets + bucket * h->bucketsize); |
668 top = hash >> (sizeof(uintptr)*8 - 8); | 689 top = hash >> (sizeof(uintptr)*8 - 8); |
669 if(top == 0) | 690 if(top == 0) |
670 top = 1; | 691 top = 1; |
671 do { | 692 do { |
(...skipping 47 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
719 bool wrapped; | 740 bool wrapped; |
720 | 741 |
721 // state of table at time iterator is initialized | 742 // state of table at time iterator is initialized |
722 uint8 B; | 743 uint8 B; |
723 byte *buckets; | 744 byte *buckets; |
724 | 745 |
725 // iter state | 746 // iter state |
726 uintptr bucket; | 747 uintptr bucket; |
727 struct Bucket *bptr; | 748 struct Bucket *bptr; |
728 uintptr i; | 749 uintptr i; |
| 750 intptr check_bucket; |
729 }; | 751 }; |
730 | 752 |
731 // iterator state: | 753 // iterator state: |
732 // bucket: the current bucket ID | 754 // bucket: the current bucket ID |
733 // b: the current Bucket in the chain | 755 // b: the current Bucket in the chain |
734 // i: the next offset to check in the current bucket | 756 // i: the next offset to check in the current bucket |
735 static void | 757 static void |
736 hash_iter_init(MapType *t, Hmap *h, struct hash_iter *it) | 758 hash_iter_init(MapType *t, Hmap *h, struct hash_iter *it) |
737 { | 759 { |
| 760 if(sizeof(struct hash_iter) / sizeof(uintptr) != 11) { |
| 761 runtime·throw("hash_iter size incorrect"); // see ../../cmd/gc/r
ange.c |
| 762 } |
738 it->t = t; | 763 it->t = t; |
739 it->h = h; | 764 it->h = h; |
740 | 765 |
741 // grab snapshot of bucket state | 766 // grab snapshot of bucket state |
742 it->B = h->B; | 767 it->B = h->B; |
743 it->buckets = h->buckets; | 768 it->buckets = h->buckets; |
744 | 769 |
745 // iterator state | 770 // iterator state |
746 it->bucket = it->endbucket = runtime·fastrand1() & (((uintptr)1 << h->B)
- 1); | 771 it->bucket = it->endbucket = runtime·fastrand1() & (((uintptr)1 << h->B)
- 1); |
747 it->wrapped = false; | 772 it->wrapped = false; |
748 it->bptr = nil; | 773 it->bptr = nil; |
749 | 774 |
750 » // Remember we have an iterator at this level. | 775 » // Remember we have an iterator. |
751 » h->flags |= Iterator; | 776 » h->flags |= Iterator | OldIterator; // careful: see issue 5120. |
| 777 |
| 778 » if(h->buckets == nil) { |
| 779 » » // Empty map. Force next hash_next to exit without |
| 780 » » // evalulating h->bucket. |
| 781 » » it->wrapped = true; |
| 782 » } |
752 } | 783 } |
753 | 784 |
754 // initializes it->key and it->value to the next key/value pair | 785 // initializes it->key and it->value to the next key/value pair |
755 // in the iteration, or nil if we've reached the end. | 786 // in the iteration, or nil if we've reached the end. |
756 static void | 787 static void |
757 hash_next(struct hash_iter *it) | 788 hash_next(struct hash_iter *it) |
758 { | 789 { |
759 Hmap *h; | 790 Hmap *h; |
760 MapType *t; | 791 MapType *t; |
761 » uintptr bucket; | 792 » uintptr bucket, oldbucket; |
| 793 » uintptr hash; |
762 Bucket *b; | 794 Bucket *b; |
763 uintptr i; | 795 uintptr i; |
| 796 intptr check_bucket; |
764 bool eq; | 797 bool eq; |
765 byte *k, *v; | 798 byte *k, *v; |
766 byte *rk, *rv; | 799 byte *rk, *rv; |
767 | 800 |
768 h = it->h; | 801 h = it->h; |
769 t = it->t; | 802 t = it->t; |
770 bucket = it->bucket; | 803 bucket = it->bucket; |
771 b = it->bptr; | 804 b = it->bptr; |
772 i = it->i; | 805 i = it->i; |
| 806 check_bucket = it->check_bucket; |
773 | 807 |
774 next: | 808 next: |
775 if(b == nil) { | 809 if(b == nil) { |
776 if(bucket == it->endbucket && it->wrapped) { | 810 if(bucket == it->endbucket && it->wrapped) { |
777 // end of iteration | 811 // end of iteration |
778 it->key = nil; | 812 it->key = nil; |
779 it->value = nil; | 813 it->value = nil; |
780 return; | 814 return; |
781 } | 815 } |
782 if(h->oldbuckets != nil && it->B == h->B) { | 816 if(h->oldbuckets != nil && it->B == h->B) { |
783 // Iterator was started in the middle of a grow, and the
grow isn't done yet. | 817 // Iterator was started in the middle of a grow, and the
grow isn't done yet. |
784 » » » // Make sure the bucket we're about to read is valid. | 818 » » » // If the bucket we're looking at hasn't been filled in
yet (i.e. the old |
785 » » » grow_work(t, h, bucket); | 819 » » » // bucket hasn't been evacuated) then we need to iterate
through the old |
786 » » } | 820 » » » // bucket and only return the ones that will be migrated
to this bucket. |
787 » » b = (Bucket*)(it->buckets + bucket * h->bucketsize); | 821 » » » oldbucket = bucket & (((uintptr)1 << (it->B - 1)) - 1); |
| 822 » » » b = (Bucket*)(h->oldbuckets + oldbucket * h->bucketsize)
; |
| 823 » » » if(!evacuated(b)) { |
| 824 » » » » check_bucket = bucket; |
| 825 » » » } else { |
| 826 » » » » b = (Bucket*)(it->buckets + bucket * h->bucketsi
ze); |
| 827 » » » » check_bucket = -1; |
| 828 » » » } |
| 829 » » } else { |
| 830 » » » b = (Bucket*)(it->buckets + bucket * h->bucketsize); |
| 831 » » » check_bucket = -1; |
| 832 » » } |
788 bucket++; | 833 bucket++; |
789 if(bucket == ((uintptr)1 << it->B)) { | 834 if(bucket == ((uintptr)1 << it->B)) { |
790 bucket = 0; | 835 bucket = 0; |
791 it->wrapped = true; | 836 it->wrapped = true; |
792 } | 837 } |
793 i = 0; | 838 i = 0; |
794 } | 839 } |
795 k = b->data + h->keysize * i; | 840 k = b->data + h->keysize * i; |
796 v = b->data + h->keysize * BUCKETSIZE + h->valuesize * i; | 841 v = b->data + h->keysize * BUCKETSIZE + h->valuesize * i; |
797 for(; i < BUCKETSIZE; i++, k += h->keysize, v += h->valuesize) { | 842 for(; i < BUCKETSIZE; i++, k += h->keysize, v += h->valuesize) { |
798 if(b->tophash[i] != 0) { | 843 if(b->tophash[i] != 0) { |
| 844 if(check_bucket >= 0) { |
| 845 // Special case: iterator was started during a g
row and the |
| 846 // grow is not done yet. We're working on a buc
ket whose |
| 847 // oldbucket has not been evacuated yet. So we
iterate |
| 848 // through the oldbucket, skipping any keys that
will go |
| 849 // to the other new bucket (each oldbucket expan
ds to two |
| 850 // buckets during a grow). |
| 851 t->key->alg->equal(&eq, t->key->size, IK(h, k),
IK(h, k)); |
| 852 if(!eq) { |
| 853 // Hash is meaningless if k != k (NaNs).
Return all |
| 854 // NaNs during the first of the two new
buckets. |
| 855 if(bucket >= ((uintptr)1 << (it->B - 1))
) { |
| 856 continue; |
| 857 } |
| 858 } else { |
| 859 // If the item in the oldbucket is not d
estined for |
| 860 // the current new bucket in the iterati
on, skip it. |
| 861 hash = h->hash0; |
| 862 t->key->alg->hash(&hash, t->key->size, I
K(h, k)); |
| 863 if((hash & (((uintptr)1 << it->B) - 1))
!= check_bucket) { |
| 864 continue; |
| 865 } |
| 866 } |
| 867 } |
799 if(!evacuated(b)) { | 868 if(!evacuated(b)) { |
800 // this is the golden data, we can return it. | 869 // this is the golden data, we can return it. |
801 it->key = IK(h, k); | 870 it->key = IK(h, k); |
802 it->value = IV(h, v); | 871 it->value = IV(h, v); |
803 } else { | 872 } else { |
804 // The hash table has grown since the iterator w
as started. | 873 // The hash table has grown since the iterator w
as started. |
805 // The golden data for this key is now somewhere
else. | 874 // The golden data for this key is now somewhere
else. |
806 t->key->alg->equal(&eq, t->key->size, IK(h, k),
IK(h, k)); | 875 t->key->alg->equal(&eq, t->key->size, IK(h, k),
IK(h, k)); |
807 if(eq) { | 876 if(eq) { |
808 // Check the current hash table for the
data. | 877 // Check the current hash table for the
data. |
(...skipping 12 matching lines...) Expand all Loading... |
821 // updated, so we can just return it. T
hat's lucky for | 890 // updated, so we can just return it. T
hat's lucky for |
822 // us because when key!=key we can't loo
k it up | 891 // us because when key!=key we can't loo
k it up |
823 // successfully in the current table. | 892 // successfully in the current table. |
824 it->key = IK(h, k); | 893 it->key = IK(h, k); |
825 it->value = IV(h, v); | 894 it->value = IV(h, v); |
826 } | 895 } |
827 } | 896 } |
828 it->bucket = bucket; | 897 it->bucket = bucket; |
829 it->bptr = b; | 898 it->bptr = b; |
830 it->i = i + 1; | 899 it->i = i + 1; |
| 900 it->check_bucket = check_bucket; |
831 return; | 901 return; |
832 } | 902 } |
833 } | 903 } |
834 b = overflowptr(b); | 904 b = overflowptr(b); |
835 i = 0; | 905 i = 0; |
836 goto next; | 906 goto next; |
837 } | 907 } |
838 | 908 |
839 | 909 |
840 #define PHASE_BUCKETS 0 | 910 #define PHASE_BUCKETS 0 |
841 #define PHASE_OLD_BUCKETS 1 | 911 #define PHASE_OLD_BUCKETS 1 |
842 #define PHASE_TABLE 2 | 912 #define PHASE_TABLE 2 |
843 #define PHASE_OLD_TABLE 3 | 913 #define PHASE_OLD_TABLE 3 |
844 #define PHASE_DONE 4 | 914 #define PHASE_DONE 4 |
845 | 915 |
846 // Initialize the iterator. | 916 // Initialize the iterator. |
847 // Returns false if Hmap contains no pointers (in which case the iterator is not
initialized). | 917 // Returns false if Hmap contains no pointers (in which case the iterator is not
initialized). |
848 bool | 918 bool |
849 hash_gciter_init (Hmap *h, struct hash_gciter *it) | 919 hash_gciter_init (Hmap *h, struct hash_gciter *it) |
850 { | 920 { |
851 » // GC during map initialization | 921 » // GC during map initialization or on an empty map. |
852 if(h->buckets == nil) | 922 if(h->buckets == nil) |
853 return false; | 923 return false; |
854 | 924 |
855 it->h = h; | 925 it->h = h; |
856 it->phase = PHASE_BUCKETS; | 926 it->phase = PHASE_BUCKETS; |
857 it->bucket = 0; | 927 it->bucket = 0; |
858 it->b = nil; | 928 it->b = nil; |
859 | 929 |
860 // TODO: finish evacuating oldbuckets so that we can collect | 930 // TODO: finish evacuating oldbuckets so that we can collect |
861 // oldbuckets? We don't want to keep a partially evacuated | 931 // oldbuckets? We don't want to keep a partially evacuated |
(...skipping 579 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1441 t->elem->alg->copy(t->elem->size, av, it->value); | 1511 t->elem->alg->copy(t->elem->size, av, it->value); |
1442 | 1512 |
1443 if(debug) { | 1513 if(debug) { |
1444 runtime·prints("mapiter2: iter="); | 1514 runtime·prints("mapiter2: iter="); |
1445 runtime·printpointer(it); | 1515 runtime·printpointer(it); |
1446 runtime·prints("; map="); | 1516 runtime·prints("; map="); |
1447 runtime·printpointer(it->h); | 1517 runtime·printpointer(it->h); |
1448 runtime·prints("\n"); | 1518 runtime·prints("\n"); |
1449 } | 1519 } |
1450 } | 1520 } |
LEFT | RIGHT |