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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
|
# This file is a part of Julia. License is MIT: https://julialang.org/license
# weak key dictionaries
"""
WeakKeyDict([itr])
`WeakKeyDict()` constructs a hash table where the keys are weak
references to objects, and thus may be garbage collected even when
referenced in a hash table.
See [`Dict`](@ref) for further help. Note, unlike [`Dict`](@ref),
`WeakKeyDict` does not convert keys on insertion.
"""
mutable struct WeakKeyDict{K,V} <: AbstractDict{K,V}
ht::Dict{WeakRef,V}
lock::Threads.RecursiveSpinLock
finalizer::Function
# Constructors mirror Dict's
function WeakKeyDict{K,V}() where V where K
t = new(Dict{Any,V}(), Threads.RecursiveSpinLock(), identity)
t.finalizer = function (k)
# when a weak key is finalized, remove from dictionary if it is still there
if islocked(t)
finalizer(t.finalizer, k)
return nothing
end
delete!(t, k)
end
return t
end
end
function WeakKeyDict{K,V}(kv) where V where K
h = WeakKeyDict{K,V}()
for (k,v) in kv
h[k] = v
end
return h
end
WeakKeyDict{K,V}(p::Pair) where V where K = setindex!(WeakKeyDict{K,V}(), p.second, p.first)
function WeakKeyDict{K,V}(ps::Pair...) where V where K
h = WeakKeyDict{K,V}()
sizehint!(h, length(ps))
for p in ps
h[p.first] = p.second
end
return h
end
WeakKeyDict() = WeakKeyDict{Any,Any}()
WeakKeyDict(kv::Tuple{}) = WeakKeyDict()
copy(d::WeakKeyDict) = WeakKeyDict(d)
WeakKeyDict(ps::Pair{K,V}...) where {K,V} = WeakKeyDict{K,V}(ps)
WeakKeyDict(ps::Pair{K}...) where {K} = WeakKeyDict{K,Any}(ps)
WeakKeyDict(ps::(Pair{K,V} where K)...) where {V} = WeakKeyDict{Any,V}(ps)
WeakKeyDict(ps::Pair...) = WeakKeyDict{Any,Any}(ps)
function WeakKeyDict(kv)
try
Base.dict_with_eltype((K, V) -> WeakKeyDict{K, V}, kv, eltype(kv))
catch e
if !isiterable(typeof(kv)) || !all(x->isa(x,Union{Tuple,Pair}),kv)
throw(ArgumentError("WeakKeyDict(kv): kv needs to be an iterator of tuples or pairs"))
else
rethrow(e)
end
end
end
empty(d::WeakKeyDict, ::Type{K}, ::Type{V}) where {K, V} = WeakKeyDict{K, V}()
islocked(wkh::WeakKeyDict) = islocked(wkh.lock)
lock(f, wkh::WeakKeyDict) = lock(f, wkh.lock)
trylock(f, wkh::WeakKeyDict) = trylock(f, wkh.lock)
function setindex!(wkh::WeakKeyDict{K}, v, key) where K
!isa(key, K) && throw(ArgumentError("$key is not a valid key for type $K"))
finalizer(wkh.finalizer, key)
lock(wkh) do
wkh.ht[WeakRef(key)] = v
end
return wkh
end
function getkey(wkh::WeakKeyDict{K}, kk, default) where K
return lock(wkh) do
k = getkey(wkh.ht, kk, secret_table_token)
k === secret_table_token && return default
return k.value::K
end
end
get(wkh::WeakKeyDict{K}, key, default) where {K} = lock(() -> get(wkh.ht, key, default), wkh)
get(default::Callable, wkh::WeakKeyDict{K}, key) where {K} = lock(() -> get(default, wkh.ht, key), wkh)
function get!(wkh::WeakKeyDict{K}, key, default) where {K}
!isa(key, K) && throw(ArgumentError("$key is not a valid key for type $K"))
lock(() -> get!(wkh.ht, WeakRef(key), default), wkh)
end
function get!(default::Callable, wkh::WeakKeyDict{K}, key) where {K}
!isa(key, K) && throw(ArgumentError("$key is not a valid key for type $K"))
lock(() -> get!(default, wkh.ht, WeakRef(key)), wkh)
end
pop!(wkh::WeakKeyDict{K}, key) where {K} = lock(() -> pop!(wkh.ht, key), wkh)
pop!(wkh::WeakKeyDict{K}, key, default) where {K} = lock(() -> pop!(wkh.ht, key, default), wkh)
delete!(wkh::WeakKeyDict, key) = lock(() -> delete!(wkh.ht, key), wkh)
empty!(wkh::WeakKeyDict) = (lock(() -> empty!(wkh.ht), wkh); wkh)
haskey(wkh::WeakKeyDict{K}, key) where {K} = lock(() -> haskey(wkh.ht, key), wkh)
getindex(wkh::WeakKeyDict{K}, key) where {K} = lock(() -> getindex(wkh.ht, key), wkh)
isempty(wkh::WeakKeyDict) = isempty(wkh.ht)
length(t::WeakKeyDict) = length(t.ht)
function iterate(t::WeakKeyDict{K,V}) where V where K
gc_token = Ref{Bool}(false) # no keys will be deleted via finalizers until this token is gc'd
finalizer(gc_token) do r
if r[]
r[] = false
unlock(t.lock)
end
end
s = lock(t.lock)
iterate(t, (gc_token,))
end
function iterate(t::WeakKeyDict{K,V}, state) where V where K
gc_token = first(state)
y = iterate(t.ht, tail(state)...)
y === nothing && return nothing
wkv, i = y
kv = Pair{K,V}(wkv[1].value::K, wkv[2])
return (kv, (gc_token, i))
end
filter!(f, d::WeakKeyDict) = filter_in_one_pass!(f, d)
|
