Common — library colibrilib.tagtbl — module Tagtbl
64
module Tagtbl : TagtblIntf

Implemented

66
use int.Int
67
use mach.int.Int63
68
use map.Map
69
use map.Const
70
use seq.Seq
71
use mach.array.Array63
72
73
clone export S {… begin (* cloned colibrilib.tagtbl.S *) type
key
val function
tag
key : int63 axiom
tag_correct
end
}
with axiom tag_correct

The keys of defined are stored at their tag in arr

  Valid (21ms) (colibri2)
76
type
t
'a = {
77
arr
: array 'a;
78
ghost mutable
contents
: map key 'a;
79
ghost
defined
: key -> bool;
80
ghost
length
: int;
81
}
82
invariant { length = arr.Array63.length - 1 }
83
invariant { forall k. defined k -> 0 <= tag k <= length }
84
invariant { forall k. defined k -> Map.get contents k = Seq.get arr.elts (tag k) }
85
by {
86
arr = (make 0 (any 'a): array 'a);
87
contents = (const (any 'a): map key 'a);
88
defined = (fun _ -> false);
89
length = -1;
90
}
91
92
function (
[]
) (h: t 'a) (k: key) : 'a = Map.get h.contents k
93
94
predicate
mem
(k: key) (h: t 'a) = h.defined k
95
Valid (25ms) (colibri2)
96
let
create
(s: int63) (def: 'a) (ghost defined: key -> bool) : t 'a
97
requires { forall k. defined k -> 0 <= tag k <= s }
98
requires { -1 <= s < max_int63 }
99
ensures { result.contents = const def }
100
ensures { result.defined = defined }
101
ensures { result.length = s }
102
=
103
{ arr = make (s + 1) def; contents = const def; defined = defined; length = to_int s }
104
Valid (22ms) (colibri2)
105
let function
max_tags
(h: t 'a) : int63
106
ensures { result = h.length }
107
=
108
Array63.length h.arr - 1
109
Valid (191ms) (cvc5)
110
let
set
(h: t 'a) (k: key) (v: 'a) : unit
111
requires { mem k h }
112
writes { h.arr.elts, h.contents }
113
ensures { h.contents = Map.set (old h.contents) k v }
114
=
115
h.arr[tag k] <- v;
116
h.contents <- Map.set h.contents k v
117
Valid (24ms) (colibri2)
118
let
find
(h: t 'a) (k: key) : 'a
119
requires { mem k h }
120
ensures { result = h[k] }
121
=
122
h.arr[tag k]
123
124
end