Mercurial > repos > tabletprog
annotate modules/sets.tp @ 251:2557ce4e671f
Fix a couple of compiler bugs. topenv was getting initialized in multiple places. This resulted in multiple copies of modules getting created which caused problems for macro expansion. Additionally, arguments were not being marked as declared during code generation so assigning to an argument that was not closed over generated invalid C code.
| author | Michael Pavone <pavone@retrodev.com> |
|---|---|
| date | Fri, 11 Apr 2014 22:29:32 -0700 |
| parents | a2d2d8e09291 |
| children |
| rev | line source |
|---|---|
| 80 | 1 #{ |
| 2 hash <- { | |
| 3 empty <- #{ | |
| 4 empty? <- { true } | |
| 5 } | |
|
81
a905e13db753
Increase the number of buckets checked in a hash set as it grows to keep space overhead reasonable
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
6 size <- 0 |
|
a905e13db753
Increase the number of buckets checked in a hash set as it grows to keep space overhead reasonable
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
7 hashdiffs <- #[0] |
| 80 | 8 #{ |
| 9 buckets <- #[empty empty empty empty] | |
|
125
6f8d868e8da0
Add size to set implementation
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
10 size <- 0 |
| 80 | 11 contains? <- :object { |
| 12 hv <- object hash | |
| 13 | |
| 14 notdone <- true | |
|
81
a905e13db753
Increase the number of buckets checked in a hash set as it grows to keep space overhead reasonable
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
15 |
|
a905e13db753
Increase the number of buckets checked in a hash set as it grows to keep space overhead reasonable
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
16 basehash <- hv |
| 80 | 17 i <- 0 |
| 18 ret <- false | |
|
81
a905e13db753
Increase the number of buckets checked in a hash set as it grows to keep space overhead reasonable
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
19 while: { if: notdone { i < (hashdiffs length) } } do: { |
|
a905e13db753
Increase the number of buckets checked in a hash set as it grows to keep space overhead reasonable
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
20 hv <- basehash + (hashdiffs get: i) |
| 80 | 21 trunc <- hv % (buckets length) |
| 22 if: trunc < 0 { trunc <- 0 - trunc } | |
| 23 bucketval <- (buckets get: trunc) | |
| 24 if: (bucketval empty?) { | |
| 25 notdone <- false | |
| 26 } else: { | |
| 27 if: (bucketval eq: hv) { | |
| 28 ret <- true | |
| 29 notdone <- false | |
| 30 } | |
| 31 } | |
| 32 i <- i + 1 | |
| 33 } | |
| 34 ret | |
| 35 } | |
| 36 add <- :object { | |
| 37 addHash: (object hash) | |
| 38 } | |
| 39 addHash <- :hv { | |
| 40 makeBucket <- :hv { | |
| 41 #{ | |
| 42 empty? <- { false } | |
| 43 v <- hv | |
| 44 eq <- :other { v = other } | |
| 45 } | |
| 46 } | |
| 47 notdone <- true | |
|
81
a905e13db753
Increase the number of buckets checked in a hash set as it grows to keep space overhead reasonable
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
48 basehash <- hv |
| 80 | 49 i <- 0 |
|
81
a905e13db753
Increase the number of buckets checked in a hash set as it grows to keep space overhead reasonable
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
50 while: { if: notdone { i < (hashdiffs length) } } do: { |
|
a905e13db753
Increase the number of buckets checked in a hash set as it grows to keep space overhead reasonable
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
51 hv <- basehash + (hashdiffs get: i) |
| 80 | 52 trunc <- hv % (buckets length) |
| 53 if: trunc < 0 { trunc <- 0 - trunc } | |
| 54 bucketval <- (buckets get: trunc) | |
| 55 if: (bucketval empty?) { | |
|
81
a905e13db753
Increase the number of buckets checked in a hash set as it grows to keep space overhead reasonable
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
56 size <- size + 1 |
| 80 | 57 buckets set: trunc (makeBucket: hv) |
| 58 notdone <- false | |
| 59 } else: { | |
| 60 if: (bucketval eq: hv) { | |
| 61 notdone <- false | |
| 62 } | |
| 63 } | |
| 64 i <- i + 1 | |
| 65 } | |
| 66 if: notdone { | |
|
81
a905e13db753
Increase the number of buckets checked in a hash set as it grows to keep space overhead reasonable
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
67 newsize <- (buckets length) * 3 + 1 |
|
a905e13db753
Increase the number of buckets checked in a hash set as it grows to keep space overhead reasonable
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
68 lastdiff <- hashdiffs get: ((hashdiffs length) - 1) |
|
a905e13db753
Increase the number of buckets checked in a hash set as it grows to keep space overhead reasonable
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
69 if: lastdiff <= 0 { |
|
a905e13db753
Increase the number of buckets checked in a hash set as it grows to keep space overhead reasonable
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
70 hashdiffs append: ((0 - lastdiff) + 1) |
|
a905e13db753
Increase the number of buckets checked in a hash set as it grows to keep space overhead reasonable
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
71 } else: { |
|
a905e13db753
Increase the number of buckets checked in a hash set as it grows to keep space overhead reasonable
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
72 hashdiffs append: (0 - lastdiff) |
|
a905e13db753
Increase the number of buckets checked in a hash set as it grows to keep space overhead reasonable
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
73 } |
| 80 | 74 newbucks <- #[] |
|
125
6f8d868e8da0
Add size to set implementation
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
75 newbucks resize: newsize |
| 80 | 76 while: { (newbucks length) < newsize } do: { |
| 77 newbucks append: empty | |
| 78 } | |
| 79 oldbucks <- buckets | |
| 80 buckets <- newbucks | |
|
125
6f8d868e8da0
Add size to set implementation
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
81 size <- 0 |
| 80 | 82 foreach: oldbucks :idx el { |
| 83 if: (not: (el empty?)) { | |
| 84 addHash: (el v) | |
| 85 } | |
| 86 } | |
| 87 addHash: hv | |
| 88 } | |
| 89 self | |
| 90 } | |
| 91 } | |
| 92 } | |
| 93 } |