Mercurial > repos > tabletprog
annotate modules/sets.tp @ 89:f23ecd4e22af
Remove some cruft from cbackend
| author | Mike Pavone <pavone@retrodev.com> |
|---|---|
| date | Mon, 23 Jul 2012 07:59:34 -0700 |
| parents | a905e13db753 |
| children | a2d2d8e09291 |
| 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] | |
| 10 contains? <- :object { | |
| 11 hv <- object hash | |
| 12 | |
| 13 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
|
14 |
|
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 basehash <- hv |
| 80 | 16 i <- 0 |
| 17 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
|
18 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
|
19 hv <- basehash + (hashdiffs get: i) |
| 80 | 20 trunc <- hv % (buckets length) |
| 21 if: trunc < 0 { trunc <- 0 - trunc } | |
| 22 bucketval <- (buckets get: trunc) | |
| 23 if: (bucketval empty?) { | |
| 24 notdone <- false | |
| 25 } else: { | |
| 26 if: (bucketval eq: hv) { | |
| 27 ret <- true | |
| 28 notdone <- false | |
| 29 } | |
| 30 } | |
| 31 i <- i + 1 | |
| 32 } | |
| 33 ret | |
| 34 } | |
| 35 add <- :object { | |
| 36 addHash: (object hash) | |
| 37 } | |
| 38 addHash <- :hv { | |
| 39 makeBucket <- :hv { | |
| 40 #{ | |
| 41 empty? <- { false } | |
| 42 v <- hv | |
| 43 eq <- :other { v = other } | |
| 44 } | |
| 45 } | |
| 46 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
|
47 basehash <- hv |
| 80 | 48 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
|
49 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
|
50 hv <- basehash + (hashdiffs get: i) |
| 80 | 51 trunc <- hv % (buckets length) |
| 52 if: trunc < 0 { trunc <- 0 - trunc } | |
| 53 bucketval <- (buckets get: trunc) | |
| 54 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
|
55 size <- size + 1 |
| 80 | 56 buckets set: trunc (makeBucket: hv) |
| 57 notdone <- false | |
| 58 } else: { | |
| 59 if: (bucketval eq: hv) { | |
| 60 notdone <- false | |
| 61 } | |
| 62 } | |
| 63 i <- i + 1 | |
| 64 } | |
| 65 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
|
66 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
|
67 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
|
68 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
|
69 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
|
70 } 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
|
71 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
|
72 } |
| 80 | 73 newbucks <- #[] |
| 74 while: { (newbucks length) < newsize } do: { | |
| 75 newbucks append: empty | |
| 76 } | |
| 77 oldbucks <- buckets | |
| 78 buckets <- newbucks | |
| 79 foreach: oldbucks :idx el { | |
| 80 if: (not: (el empty?)) { | |
| 81 addHash: (el v) | |
| 82 } | |
| 83 } | |
| 84 addHash: hv | |
| 85 } | |
| 86 self | |
| 87 } | |
| 88 } | |
| 89 } | |
| 90 } |