aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--cmd/santa-example/main.go38
-rw-r--r--external_test.go5
-rw-r--r--go.mod7
-rw-r--r--go.sum11
-rw-r--r--stmutil/containers.go132
5 files changed, 102 insertions, 91 deletions
diff --git a/cmd/santa-example/main.go b/cmd/santa-example/main.go
index dcc8067..76c0fbc 100644
--- a/cmd/santa-example/main.go
+++ b/cmd/santa-example/main.go
@@ -3,28 +3,28 @@
//
// The problem is given as:
//
-// Santa repeatedly sleeps until wakened by either all of his nine reindeer,
-// back from their holidays, or by a group of three of his ten elves. If
-// awakened by the reindeer, he harnesses each of them to his sleigh,
-// delivers toys with them and finally unharnesses them (allowing them to
-// go off on holiday). If awakened by a group of elves, he shows each of the
-// group into his study, consults with them on toy R&D and finally shows
-// them each out (allowing them to go back to work). Santa should give
-// priority to the reindeer in the case that there is both a group of elves
-// and a group of reindeer waiting.
+// Santa repeatedly sleeps until wakened by either all of his nine reindeer,
+// back from their holidays, or by a group of three of his ten elves. If
+// awakened by the reindeer, he harnesses each of them to his sleigh,
+// delivers toys with them and finally unharnesses them (allowing them to
+// go off on holiday). If awakened by a group of elves, he shows each of the
+// group into his study, consults with them on toy R&D and finally shows
+// them each out (allowing them to go back to work). Santa should give
+// priority to the reindeer in the case that there is both a group of elves
+// and a group of reindeer waiting.
//
// Here we follow the solution given in the paper, described as such:
//
-// Santa makes one "Group" for the elves and one for the reindeer. Each elf
-// (or reindeer) tries to join its Group. If it succeeds, it gets two
-// "Gates" in return. The first Gate allows Santa to control when the elf
-// can enter the study, and also lets Santa know when they are all inside.
-// Similarly, the second Gate controls the elves leaving the study. Santa,
-// for his part, waits for either of his two Groups to be ready, and then
-// uses that Group's Gates to marshal his helpers (elves or reindeer)
-// through their task. Thus the helpers spend their lives in an infinite
-// loop: try to join a group, move through the gates under Santa's control,
-// and then delay for a random interval before trying to join a group again.
+// Santa makes one "Group" for the elves and one for the reindeer. Each elf
+// (or reindeer) tries to join its Group. If it succeeds, it gets two
+// "Gates" in return. The first Gate allows Santa to control when the elf
+// can enter the study, and also lets Santa know when they are all inside.
+// Similarly, the second Gate controls the elves leaving the study. Santa,
+// for his part, waits for either of his two Groups to be ready, and then
+// uses that Group's Gates to marshal his helpers (elves or reindeer)
+// through their task. Thus the helpers spend their lives in an infinite
+// loop: try to join a group, move through the gates under Santa's control,
+// and then delay for a random interval before trying to join a group again.
//
// See the paper for more details regarding the solution's implementation.
package main
diff --git a/external_test.go b/external_test.go
index abdf544..1291cce 100644
--- a/external_test.go
+++ b/external_test.go
@@ -99,7 +99,7 @@ func BenchmarkInvertedThunderingHerd(b *testing.B) {
for i := 0; i < b.N; i++ {
done := stm.NewBuiltinEqVar(false)
tokens := stm.NewBuiltinEqVar(0)
- pending := stm.NewVar(stmutil.NewSet())
+ pending := stm.NewVar(stmutil.NewSet[*stm.Var[bool]]())
for range iter.N(1000) {
ready := stm.NewVar(false)
stm.Atomically(stm.VoidOperation(func(tx *stm.Tx) {
@@ -132,8 +132,7 @@ func BenchmarkInvertedThunderingHerd(b *testing.B) {
for stm.Atomically(func(tx *stm.Tx) bool {
tx.Assert(tokens.Get(tx) > 0)
tokens.Set(tx, tokens.Get(tx)-1)
- pending.Get(tx).Range(func(i any) bool {
- ready := i.(*stm.Var[bool])
+ pending.Get(tx).Range(func(ready *stm.Var[bool]) bool {
if !ready.Get(tx) {
ready.Set(tx, true)
return false
diff --git a/go.mod b/go.mod
index 9c36758..de2ab4a 100644
--- a/go.mod
+++ b/go.mod
@@ -7,15 +7,14 @@ require (
github.com/anacrolix/envpprof v1.0.0
github.com/anacrolix/missinggo v1.1.0
github.com/anacrolix/missinggo/v2 v2.2.0
- github.com/benbjohnson/immutable v0.2.0
+ github.com/benbjohnson/immutable v0.4.1-0.20221220213129-8932b999621d
github.com/stretchr/testify v1.3.0
)
require (
github.com/bradfitz/iter v0.0.0-20190303215204-33e6a9893b0c // indirect
github.com/davecgh/go-spew v1.1.1 // indirect
- github.com/huandu/xstrings v1.2.0 // indirect
+ github.com/huandu/xstrings v1.3.2 // indirect
github.com/pmezard/go-difflib v1.0.0 // indirect
+ golang.org/x/exp v0.0.0-20221026004748-78e5e7837ae6 // indirect
)
-
-exclude github.com/benbjohnson/immutable v0.4.0
diff --git a/go.sum b/go.sum
index f0522d7..5542336 100644
--- a/go.sum
+++ b/go.sum
@@ -21,8 +21,8 @@ github.com/anacrolix/missinggo/v2 v2.2.0/go.mod h1:o0jgJoYOyaoYQ4E2ZMISVa9c88BbU
github.com/anacrolix/tagflag v0.0.0-20180109131632-2146c8d41bf0/go.mod h1:1m2U/K6ZT+JZG0+bdMK6qauP49QT4wE5pmhJXOKKCHw=
github.com/anacrolix/tagflag v1.0.0/go.mod h1:1m2U/K6ZT+JZG0+bdMK6qauP49QT4wE5pmhJXOKKCHw=
github.com/apache/thrift v0.12.0/go.mod h1:cp2SuWMxlEZw2r+iP2GNCdIi4C1qmUzdZFSVb+bacwQ=
-github.com/benbjohnson/immutable v0.2.0 h1:t0rW3lNFwfQ85IDO1mhMbumxdVSti4nnVaal4r45Oio=
-github.com/benbjohnson/immutable v0.2.0/go.mod h1:uc6OHo6PN2++n98KHLxW8ef4W42ylHiQSENghE1ezxI=
+github.com/benbjohnson/immutable v0.4.1-0.20221220213129-8932b999621d h1:2qVb9bsAMtmAfnxXltm+6eBzrrS7SZ52c3SedsulaMI=
+github.com/benbjohnson/immutable v0.4.1-0.20221220213129-8932b999621d/go.mod h1:iAr8OjJGLnLmVUr9MZ/rz4PWUy6Ouc2JLYuMArmvAJM=
github.com/beorn7/perks v0.0.0-20180321164747-3a771d992973/go.mod h1:Dwedo/Wpr24TaqPxmxbtue+5NUziq4I4S80YR8gNf3Q=
github.com/bradfitz/iter v0.0.0-20140124041915-454541ec3da2/go.mod h1:PyRFw1Lt2wKX4ZVSQ2mk+PeDa1rxyObEDlApuIsUKuo=
github.com/bradfitz/iter v0.0.0-20190303215204-33e6a9893b0c h1:FUUopH4brHNO2kJoNN3pV+OBEYmgraLT/KHZrMM69r0=
@@ -55,7 +55,7 @@ github.com/golang/snappy v0.0.1/go.mod h1:/XxbfmMg8lxefKM7IXC3fBNl/7bRcc72aCRzEW
github.com/google/btree v0.0.0-20180124185431-e89373fe6b4a/go.mod h1:lNA+9X1NB3Zf8V7Ke586lFgjr2dZNuvo3lPJSGZ5JPQ=
github.com/google/btree v1.0.0/go.mod h1:lNA+9X1NB3Zf8V7Ke586lFgjr2dZNuvo3lPJSGZ5JPQ=
github.com/google/go-cmp v0.2.0/go.mod h1:oXzfMopK8JAjlY9xF4vHSVASa0yLyX7SntLO5aqRK0M=
-github.com/google/go-cmp v0.5.6 h1:BKbKCqvP6I+rmFHt06ZmyQtvB8xAkWdhFyr0ZUNZcxQ=
+github.com/google/go-cmp v0.5.8 h1:e6P7q2lk1O+qJJb4BtCQXlK8vWEO8V1ZeuEdJNOqZyg=
github.com/gopherjs/gopherjs v0.0.0-20181017120253-0766667cb4d1/go.mod h1:wJfORRmW1u3UXTncJ5qlYoELFm8eSnnEO6hX4iZ3EWY=
github.com/gopherjs/gopherjs v0.0.0-20181103185306-d547d1d9531e/go.mod h1:wJfORRmW1u3UXTncJ5qlYoELFm8eSnnEO6hX4iZ3EWY=
github.com/gopherjs/gopherjs v0.0.0-20190309154008-847fc94819f9/go.mod h1:wJfORRmW1u3UXTncJ5qlYoELFm8eSnnEO6hX4iZ3EWY=
@@ -65,8 +65,9 @@ github.com/hashicorp/golang-lru v0.5.0/go.mod h1:/m3WP610KZHVQ1SGc6re/UDhFvYD7pJ
github.com/hexops/gotextdiff v1.0.3 h1:gitA9+qJrrTCsiCl7+kh75nPqQt1cx4ZkudSTLoUqJM=
github.com/hpcloud/tail v1.0.0/go.mod h1:ab1qPbhIpdTxEkNHXyeSf5vhxWSCs/tWer42PpOxQnU=
github.com/huandu/xstrings v1.0.0/go.mod h1:4qWG/gcEcfX4z/mBDHJ++3ReCw9ibxbsNJbcucJdbSo=
-github.com/huandu/xstrings v1.2.0 h1:yPeWdRnmynF7p+lLYz0H2tthW9lqhMJrQV/U7yy4wX0=
github.com/huandu/xstrings v1.2.0/go.mod h1:DvyZB1rfVYsBIigL8HwpZgxHwXozlTgGqn63UyNX5k4=
+github.com/huandu/xstrings v1.3.2 h1:L18LIDzqlW6xN2rEkpdV8+oL/IXWJ1APd+vsdYy4Wdw=
+github.com/huandu/xstrings v1.3.2/go.mod h1:y5/lhBue+AyNmUVz9RLU9xbLR0o4KIIExikq4ovT0aE=
github.com/jtolds/gls v4.2.1+incompatible/go.mod h1:QJZ7F/aHp+rZTRtaJ1ow/lLfFfVYBRgL+9YlvaHOwJU=
github.com/jtolds/gls v4.20.0+incompatible/go.mod h1:QJZ7F/aHp+rZTRtaJ1ow/lLfFfVYBRgL+9YlvaHOwJU=
github.com/julienschmidt/httprouter v1.2.0/go.mod h1:SYymIcj16QtmaHHD7aYtjjsJG7VTCxuUUipMqKk8s4w=
@@ -115,6 +116,8 @@ go.opencensus.io v0.20.2/go.mod h1:6WKK9ahsWS3RSO+PY9ZHZUfv2irvY6gN279GOPZjmmk=
golang.org/x/crypto v0.0.0-20180904163835-0709b304e793/go.mod h1:6SG95UA2DQfeDnfUPMdvaQW0Q7yPrPDi9nlGo2tz2b4=
golang.org/x/crypto v0.0.0-20190308221718-c2843e01d9a2/go.mod h1:djNgcEr1/C05ACkg1iLfiJU5Ep61QUkGW8qpdssI0+w=
golang.org/x/exp v0.0.0-20190121172915-509febef88a4/go.mod h1:CJ0aWSM057203Lf6IL+f9T1iT9GByDxfZKAQTCR3kQA=
+golang.org/x/exp v0.0.0-20221026004748-78e5e7837ae6 h1:mC6uOkPi9SUk8A59jZvw7//rlyc+MlELtQUCyOUSKZQ=
+golang.org/x/exp v0.0.0-20221026004748-78e5e7837ae6/go.mod h1:cyybsKvd6eL0RnXn6p/Grxp8F5bW7iYuBgsNCOHpMYE=
golang.org/x/lint v0.0.0-20181026193005-c67002cb31c3/go.mod h1:UVdnD1Gm6xHRNCYTkRU2/jEulfH38KcIWyp/GAMgvoE=
golang.org/x/lint v0.0.0-20190227174305-5b3e6a55c961/go.mod h1:wehouNa3lNwaWXcvxsM5YxQ5yQlVC4a0KAMCusXpPoU=
golang.org/x/lint v0.0.0-20190301231843-5614ed5bae6f/go.mod h1:UVdnD1Gm6xHRNCYTkRU2/jEulfH38KcIWyp/GAMgvoE=
diff --git a/stmutil/containers.go b/stmutil/containers.go
index c7a4a49..0cc592d 100644
--- a/stmutil/containers.go
+++ b/stmutil/containers.go
@@ -3,142 +3,154 @@ package stmutil
import (
"unsafe"
- "github.com/benbjohnson/immutable"
-
"github.com/anacrolix/missinggo/v2/iter"
+ "github.com/benbjohnson/immutable"
)
-type Settish interface {
- Add(any) Settish
- Delete(any) Settish
- Contains(any) bool
- Range(func(any) bool)
+// This is the type constraint for keys passed through from github.com/benbjohnson/immutable.
+type KeyConstraint interface {
+ comparable
+}
+
+type Settish[K KeyConstraint] interface {
+ Add(K) Settish[K]
+ Delete(K) Settish[K]
+ Contains(K) bool
+ Range(func(K) bool)
iter.Iterable
Len() int
}
-type mapToSet struct {
- m Mappish
+type mapToSet[K KeyConstraint] struct {
+ m Mappish[K, struct{}]
}
-type interhash struct{}
+type interhash[K KeyConstraint] struct{}
-func (interhash) Hash(x any) uint32 {
+func (interhash[K]) Hash(x K) uint32 {
return uint32(nilinterhash(unsafe.Pointer(&x), 0))
}
-func (interhash) Equal(i, j any) bool {
+func (interhash[K]) Equal(i, j K) bool {
return i == j
}
-func NewSet() Settish {
- return mapToSet{NewMap()}
+func NewSet[K KeyConstraint]() Settish[K] {
+ return mapToSet[K]{NewMap[K, struct{}]()}
}
-func NewSortedSet(lesser lessFunc) Settish {
- return mapToSet{NewSortedMap(lesser)}
+func NewSortedSet[K KeyConstraint](lesser lessFunc[K]) Settish[K] {
+ return mapToSet[K]{NewSortedMap[K, struct{}](lesser)}
}
-func (s mapToSet) Add(x any) Settish {
- s.m = s.m.Set(x, nil)
+func (s mapToSet[K]) Add(x K) Settish[K] {
+ s.m = s.m.Set(x, struct{}{})
return s
}
-func (s mapToSet) Delete(x any) Settish {
+func (s mapToSet[K]) Delete(x K) Settish[K] {
s.m = s.m.Delete(x)
return s
}
-func (s mapToSet) Len() int {
+func (s mapToSet[K]) Len() int {
return s.m.Len()
}
-func (s mapToSet) Contains(x any) bool {
+func (s mapToSet[K]) Contains(x K) bool {
_, ok := s.m.Get(x)
return ok
}
-func (s mapToSet) Range(f func(any) bool) {
- s.m.Range(func(k, _ any) bool {
+func (s mapToSet[K]) Range(f func(K) bool) {
+ s.m.Range(func(k K, _ struct{}) bool {
return f(k)
})
}
-func (s mapToSet) Iter(cb iter.Callback) {
- s.Range(cb)
+func (s mapToSet[K]) Iter(cb iter.Callback) {
+ s.Range(func(k K) bool {
+ return cb(k)
+ })
}
-type Map struct {
- *immutable.Map
+type Map[K KeyConstraint, V any] struct {
+ *immutable.Map[K, V]
}
-func NewMap() Mappish {
- return Map{immutable.NewMap(interhash{})}
+func NewMap[K KeyConstraint, V any]() Mappish[K, V] {
+ return Map[K, V]{immutable.NewMap[K, V](interhash[K]{})}
}
-var _ Mappish = Map{}
-
-func (m Map) Delete(x any) Mappish {
+func (m Map[K, V]) Delete(x K) Mappish[K, V] {
m.Map = m.Map.Delete(x)
return m
}
-func (m Map) Set(key, value any) Mappish {
+func (m Map[K, V]) Set(key K, value V) Mappish[K, V] {
m.Map = m.Map.Set(key, value)
return m
}
-func (sm Map) Range(f func(key, value any) bool) {
+func (sm Map[K, V]) Range(f func(K, V) bool) {
iter := sm.Map.Iterator()
- for !iter.Done() {
- if !f(iter.Next()) {
+ for {
+ k, v, ok := iter.Next()
+ if !ok {
+ break
+ }
+ if !f(k, v) {
return
}
}
}
-func (sm Map) Iter(cb iter.Callback) {
- sm.Range(func(key, _ any) bool {
+func (sm Map[K, V]) Iter(cb iter.Callback) {
+ sm.Range(func(key K, _ V) bool {
return cb(key)
})
}
-type SortedMap struct {
- *immutable.SortedMap
+type SortedMap[K KeyConstraint, V any] struct {
+ *immutable.SortedMap[K, V]
}
-func (sm SortedMap) Set(key, value any) Mappish {
+func (sm SortedMap[K, V]) Set(key K, value V) Mappish[K, V] {
sm.SortedMap = sm.SortedMap.Set(key, value)
return sm
}
-func (sm SortedMap) Delete(key any) Mappish {
+func (sm SortedMap[K, V]) Delete(key K) Mappish[K, V] {
sm.SortedMap = sm.SortedMap.Delete(key)
return sm
}
-func (sm SortedMap) Range(f func(key, value any) bool) {
+func (sm SortedMap[K, V]) Range(f func(key K, value V) bool) {
iter := sm.SortedMap.Iterator()
- for !iter.Done() {
- if !f(iter.Next()) {
+ for {
+ k, v, ok := iter.Next()
+ if !ok {
+ break
+ }
+ if !f(k, v) {
return
}
}
}
-func (sm SortedMap) Iter(cb iter.Callback) {
- sm.Range(func(key, _ any) bool {
+func (sm SortedMap[K, V]) Iter(cb iter.Callback) {
+ sm.Range(func(key K, _ V) bool {
return cb(key)
})
}
-type lessFunc func(l, r any) bool
+type lessFunc[T KeyConstraint] func(l, r T) bool
-type comparer struct {
- less lessFunc
+type comparer[K KeyConstraint] struct {
+ less lessFunc[K]
}
-func (me comparer) Compare(i, j any) int {
+func (me comparer[K]) Compare(i, j K) int {
if me.less(i, j) {
return -1
} else if me.less(j, i) {
@@ -148,17 +160,17 @@ func (me comparer) Compare(i, j any) int {
}
}
-func NewSortedMap(less lessFunc) Mappish {
- return SortedMap{
- SortedMap: immutable.NewSortedMap(comparer{less}),
+func NewSortedMap[K KeyConstraint, V any](less lessFunc[K]) Mappish[K, V] {
+ return SortedMap[K, V]{
+ SortedMap: immutable.NewSortedMap[K, V](comparer[K]{less}),
}
}
-type Mappish interface {
- Set(key, value any) Mappish
- Delete(key any) Mappish
- Get(key any) (any, bool)
- Range(func(_, _ any) bool)
+type Mappish[K, V any] interface {
+ Set(K, V) Mappish[K, V]
+ Delete(key K) Mappish[K, V]
+ Get(key K) (V, bool)
+ Range(func(K, V) bool)
Len() int
iter.Iterable
}
@@ -178,5 +190,3 @@ func interfaceHash(x any) uint32 {
type Lenner interface {
Len() int
}
-
-type List = *immutable.List
generated by cgit v1.2.3 (git 2.49.0) at 2025-07-06 14:03:59 +0000