annotate modules/sets.tp @ 81:a905e13db753

Increase the number of buckets checked in a hash set as it grows to keep space overhead reasonable
author Mike Pavone <pavone@retrodev.com>
date Wed, 18 Jul 2012 08:59:08 -0700
parents cbc92ee13f35
children a2d2d8e09291
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
80
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
1 #{
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
2 hash <- {
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
3 empty <- #{
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
4 empty? <- { true }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
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
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
8 #{
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
9 buckets <- #[empty empty empty empty]
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
10 contains? <- :object {
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
11 hv <- object hash
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
12
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
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
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
16 i <- 0
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
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
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
20 trunc <- hv % (buckets length)
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
21 if: trunc < 0 { trunc <- 0 - trunc }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
22 bucketval <- (buckets get: trunc)
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
23 if: (bucketval empty?) {
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
24 notdone <- false
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
25 } else: {
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
26 if: (bucketval eq: hv) {
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
27 ret <- true
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
28 notdone <- false
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
29 }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
30 }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
31 i <- i + 1
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
32 }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
33 ret
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
34 }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
35 add <- :object {
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
36 addHash: (object hash)
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
37 }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
38 addHash <- :hv {
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
39 makeBucket <- :hv {
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
40 #{
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
41 empty? <- { false }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
42 v <- hv
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
43 eq <- :other { v = other }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
44 }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
45 }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
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
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
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
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
51 trunc <- hv % (buckets length)
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
52 if: trunc < 0 { trunc <- 0 - trunc }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
53 bucketval <- (buckets get: trunc)
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
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
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
56 buckets set: trunc (makeBucket: hv)
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
57 notdone <- false
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
58 } else: {
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
59 if: (bucketval eq: hv) {
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
60 notdone <- false
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
61 }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
62 }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
63 i <- i + 1
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
64 }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
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
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
73 newbucks <- #[]
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
74 while: { (newbucks length) < newsize } do: {
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
75 newbucks append: empty
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
76 }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
77 oldbucks <- buckets
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
78 buckets <- newbucks
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
79 foreach: oldbucks :idx el {
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
80 if: (not: (el empty?)) {
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
81 addHash: (el v)
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
82 }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
83 }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
84 addHash: hv
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
85 }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
86 self
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
87 }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
88 }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
89 }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
90 }