-
Notifications
You must be signed in to change notification settings - Fork 71
/
memo.go
98 lines (86 loc) · 1.92 KB
/
memo.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
package memo
// Func is the type of the function to memoize.
type Func func(key string, done <-chan struct{}) (interface{}, error)
// A result is the result of calling a Func.
type result struct {
value interface{}
err error
}
type entry struct {
res result
ready chan struct{} // closed when res is ready
}
// A request is a message requesting that the Func be applied to key.
type request struct {
key string
response chan<- result // the client wants a single result
done <-chan struct{}
}
type Memo struct {
requests chan request
}
// New returns a memoization of f.
// Clients must subsequently call Close.
func New(f Func) *Memo {
memo := &Memo{
requests: make(chan request),
}
go memo.server(f)
return memo
}
var canceledKeys chan string
func (memo *Memo) Get(key string, done <-chan struct{}) (interface{}, error) {
response := make(chan result)
memo.requests <- request{key, response, done}
res := <-response
select {
case <-done:
canceledKeys <- key
default:
}
return res.value, res.err
}
func (memo *Memo) Close() {
close(memo.requests)
}
func (memo *Memo) server(f Func) {
cache := make(map[string]*entry)
for {
LOOP:
for {
select {
case key := <-canceledKeys:
delete(cache, key)
default:
break LOOP
}
}
select {
case req, ok := <-memo.requests:
if !ok {
return
}
e := cache[req.key]
if e == nil {
// This is the first request for this key.
e = &entry{ready: make(chan struct{})}
cache[req.key] = e
go e.call(f, req.key, req.done) // call f(key)
}
go e.deliver(req.response)
default:
}
}
}
func (e *entry) call(f Func, key string, done <-chan struct{}) {
// Evaluate the function.
e.res.value, e.res.err = f(key, done)
// Broadcast the ready condition.
close(e.ready)
}
func (e *entry) deliver(response chan<- result) {
// Wait for the ready condition.
<-e.ready
// Send the result to the client.
response <- e.res
}