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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
|
(** THIS FILE WAS AUTOMATICALLY GENERATED BY AENEAS *)
(** [hashmap]: function definitions *)
Require Import Primitives.
Import Primitives.
Require Import Coq.ZArith.ZArith.
Require Import List.
Import ListNotations.
Local Open Scope Primitives_scope.
Require Import Hashmap_Types.
Include Hashmap_Types.
Module Hashmap_Funs.
(** [hashmap::hash_key]:
Source: 'tests/src/hashmap.rs', lines 27:0-27:32 *)
Definition hash_key (k : usize) : result usize :=
Ok k.
(** [hashmap::{hashmap::HashMap<T>}::allocate_slots]: loop 0:
Source: 'tests/src/hashmap.rs', lines 50:4-56:5 *)
Fixpoint hashMap_allocate_slots_loop
(T : Type) (n : nat) (slots : alloc_vec_Vec (List_t T)) (n1 : usize) :
result (alloc_vec_Vec (List_t T))
:=
match n with
| O => Fail_ OutOfFuel
| S n2 =>
if n1 s> 0%usize
then (
slots1 <- alloc_vec_Vec_push (List_t T) slots List_Nil;
n3 <- usize_sub n1 1%usize;
hashMap_allocate_slots_loop T n2 slots1 n3)
else Ok slots
end
.
(** [hashmap::{hashmap::HashMap<T>}::allocate_slots]:
Source: 'tests/src/hashmap.rs', lines 50:4-50:76 *)
Definition hashMap_allocate_slots
(T : Type) (n : nat) (slots : alloc_vec_Vec (List_t T)) (n1 : usize) :
result (alloc_vec_Vec (List_t T))
:=
hashMap_allocate_slots_loop T n slots n1
.
(** [hashmap::{hashmap::HashMap<T>}::new_with_capacity]:
Source: 'tests/src/hashmap.rs', lines 59:4-63:13 *)
Definition hashMap_new_with_capacity
(T : Type) (n : nat) (capacity : usize) (max_load_dividend : usize)
(max_load_divisor : usize) :
result (HashMap_t T)
:=
slots <- hashMap_allocate_slots T n (alloc_vec_Vec_new (List_t T)) capacity;
i <- usize_mul capacity max_load_dividend;
i1 <- usize_div i max_load_divisor;
Ok
{|
hashMap_num_entries := 0%usize;
hashMap_max_load_factor := (max_load_dividend, max_load_divisor);
hashMap_max_load := i1;
hashMap_slots := slots
|}
.
(** [hashmap::{hashmap::HashMap<T>}::new]:
Source: 'tests/src/hashmap.rs', lines 75:4-75:24 *)
Definition hashMap_new (T : Type) (n : nat) : result (HashMap_t T) :=
hashMap_new_with_capacity T n 32%usize 4%usize 5%usize
.
(** [hashmap::{hashmap::HashMap<T>}::clear]:
Source: 'tests/src/hashmap.rs', lines 80:4-80:27 *)
Definition hashMap_clear
(T : Type) (n : nat) (self : HashMap_t T) : result (HashMap_t T) :=
admit
.
(** [hashmap::{hashmap::HashMap<T>}::len]:
Source: 'tests/src/hashmap.rs', lines 90:4-90:30 *)
Definition hashMap_len (T : Type) (self : HashMap_t T) : result usize :=
Ok self.(hashMap_num_entries)
.
(** [hashmap::{hashmap::HashMap<T>}::insert_in_list]:
Source: 'tests/src/hashmap.rs', lines 97:4-97:71 *)
Definition hashMap_insert_in_list
(T : Type) (n : nat) (key : usize) (value : T) (ls : List_t T) :
result (bool * (List_t T))
:=
admit
.
(** [hashmap::{hashmap::HashMap<T>}::insert_no_resize]:
Source: 'tests/src/hashmap.rs', lines 117:4-117:54 *)
Definition hashMap_insert_no_resize
(T : Type) (n : nat) (self : HashMap_t T) (key : usize) (value : T) :
result (HashMap_t T)
:=
hash <- hash_key key;
let i := alloc_vec_Vec_len (List_t T) self.(hashMap_slots) in
hash_mod <- usize_rem hash i;
p <-
alloc_vec_Vec_index_mut (List_t T) usize
(core_slice_index_SliceIndexUsizeSliceTInst (List_t T))
self.(hashMap_slots) hash_mod;
let (l, index_mut_back) := p in
p1 <- hashMap_insert_in_list T n key value l;
let (inserted, l1) := p1 in
if inserted
then (
i1 <- usize_add self.(hashMap_num_entries) 1%usize;
v <- index_mut_back l1;
Ok
{|
hashMap_num_entries := i1;
hashMap_max_load_factor := self.(hashMap_max_load_factor);
hashMap_max_load := self.(hashMap_max_load);
hashMap_slots := v
|})
else (
v <- index_mut_back l1;
Ok
{|
hashMap_num_entries := self.(hashMap_num_entries);
hashMap_max_load_factor := self.(hashMap_max_load_factor);
hashMap_max_load := self.(hashMap_max_load);
hashMap_slots := v
|})
.
(** [hashmap::{hashmap::HashMap<T>}::move_elements_from_list]:
Source: 'tests/src/hashmap.rs', lines 183:4-183:72 *)
Definition hashMap_move_elements_from_list
(T : Type) (n : nat) (ntable : HashMap_t T) (ls : List_t T) :
result (HashMap_t T)
:=
admit
.
(** [hashmap::{hashmap::HashMap<T>}::move_elements]:
Source: 'tests/src/hashmap.rs', lines 171:4-171:95 *)
Definition hashMap_move_elements
(T : Type) (n : nat) (ntable : HashMap_t T)
(slots : alloc_vec_Vec (List_t T)) (i : usize) :
result ((HashMap_t T) * (alloc_vec_Vec (List_t T)))
:=
admit
.
(** [hashmap::{hashmap::HashMap<T>}::try_resize]:
Source: 'tests/src/hashmap.rs', lines 140:4-140:28 *)
Definition hashMap_try_resize
(T : Type) (n : nat) (self : HashMap_t T) : result (HashMap_t T) :=
max_usize <- scalar_cast U32 Usize core_u32_max;
let capacity := alloc_vec_Vec_len (List_t T) self.(hashMap_slots) in
n1 <- usize_div max_usize 2%usize;
let (i, i1) := self.(hashMap_max_load_factor) in
i2 <- usize_div n1 i;
if capacity s<= i2
then (
i3 <- usize_mul capacity 2%usize;
ntable <- hashMap_new_with_capacity T n i3 i i1;
p <- hashMap_move_elements T n ntable self.(hashMap_slots) 0%usize;
let (ntable1, _) := p in
Ok
{|
hashMap_num_entries := self.(hashMap_num_entries);
hashMap_max_load_factor := (i, i1);
hashMap_max_load := ntable1.(hashMap_max_load);
hashMap_slots := ntable1.(hashMap_slots)
|})
else
Ok
{|
hashMap_num_entries := self.(hashMap_num_entries);
hashMap_max_load_factor := (i, i1);
hashMap_max_load := self.(hashMap_max_load);
hashMap_slots := self.(hashMap_slots)
|}
.
(** [hashmap::{hashmap::HashMap<T>}::insert]:
Source: 'tests/src/hashmap.rs', lines 129:4-129:48 *)
Definition hashMap_insert
(T : Type) (n : nat) (self : HashMap_t T) (key : usize) (value : T) :
result (HashMap_t T)
:=
self1 <- hashMap_insert_no_resize T n self key value;
i <- hashMap_len T self1;
if i s> self1.(hashMap_max_load)
then hashMap_try_resize T n self1
else Ok self1
.
(** [hashmap::{hashmap::HashMap<T>}::contains_key_in_list]:
Source: 'tests/src/hashmap.rs', lines 206:4-206:68 *)
Definition hashMap_contains_key_in_list
(T : Type) (n : nat) (key : usize) (ls : List_t T) : result bool :=
admit
.
(** [hashmap::{hashmap::HashMap<T>}::contains_key]:
Source: 'tests/src/hashmap.rs', lines 199:4-199:49 *)
Definition hashMap_contains_key
(T : Type) (n : nat) (self : HashMap_t T) (key : usize) : result bool :=
hash <- hash_key key;
let i := alloc_vec_Vec_len (List_t T) self.(hashMap_slots) in
hash_mod <- usize_rem hash i;
l <-
alloc_vec_Vec_index (List_t T) usize
(core_slice_index_SliceIndexUsizeSliceTInst (List_t T))
self.(hashMap_slots) hash_mod;
hashMap_contains_key_in_list T n key l
.
(** [hashmap::{hashmap::HashMap<T>}::get_in_list]:
Source: 'tests/src/hashmap.rs', lines 224:4-224:70 *)
Definition hashMap_get_in_list
(T : Type) (n : nat) (key : usize) (ls : List_t T) : result T :=
admit
.
(** [hashmap::{hashmap::HashMap<T>}::get]:
Source: 'tests/src/hashmap.rs', lines 239:4-239:55 *)
Definition hashMap_get
(T : Type) (n : nat) (self : HashMap_t T) (key : usize) : result T :=
hash <- hash_key key;
let i := alloc_vec_Vec_len (List_t T) self.(hashMap_slots) in
hash_mod <- usize_rem hash i;
l <-
alloc_vec_Vec_index (List_t T) usize
(core_slice_index_SliceIndexUsizeSliceTInst (List_t T))
self.(hashMap_slots) hash_mod;
hashMap_get_in_list T n key l
.
(** [hashmap::{hashmap::HashMap<T>}::get_mut_in_list]:
Source: 'tests/src/hashmap.rs', lines 245:4-245:86 *)
Definition hashMap_get_mut_in_list
(T : Type) (n : nat) (ls : List_t T) (key : usize) :
result (T * (T -> result (List_t T)))
:=
admit
.
(** [hashmap::{hashmap::HashMap<T>}::get_mut]:
Source: 'tests/src/hashmap.rs', lines 257:4-257:67 *)
Definition hashMap_get_mut
(T : Type) (n : nat) (self : HashMap_t T) (key : usize) :
result (T * (T -> result (HashMap_t T)))
:=
hash <- hash_key key;
let i := alloc_vec_Vec_len (List_t T) self.(hashMap_slots) in
hash_mod <- usize_rem hash i;
p <-
alloc_vec_Vec_index_mut (List_t T) usize
(core_slice_index_SliceIndexUsizeSliceTInst (List_t T))
self.(hashMap_slots) hash_mod;
let (l, index_mut_back) := p in
p1 <- hashMap_get_mut_in_list T n l key;
let (t, get_mut_in_list_back) := p1 in
let back :=
fun (ret : T) =>
l1 <- get_mut_in_list_back ret;
v <- index_mut_back l1;
Ok
{|
hashMap_num_entries := self.(hashMap_num_entries);
hashMap_max_load_factor := self.(hashMap_max_load_factor);
hashMap_max_load := self.(hashMap_max_load);
hashMap_slots := v
|} in
Ok (t, back)
.
(** [hashmap::{hashmap::HashMap<T>}::remove_from_list]:
Source: 'tests/src/hashmap.rs', lines 265:4-265:69 *)
Definition hashMap_remove_from_list
(T : Type) (n : nat) (key : usize) (ls : List_t T) :
result ((option T) * (List_t T))
:=
admit
.
(** [hashmap::{hashmap::HashMap<T>}::remove]:
Source: 'tests/src/hashmap.rs', lines 294:4-294:52 *)
Definition hashMap_remove
(T : Type) (n : nat) (self : HashMap_t T) (key : usize) :
result ((option T) * (HashMap_t T))
:=
hash <- hash_key key;
let i := alloc_vec_Vec_len (List_t T) self.(hashMap_slots) in
hash_mod <- usize_rem hash i;
p <-
alloc_vec_Vec_index_mut (List_t T) usize
(core_slice_index_SliceIndexUsizeSliceTInst (List_t T))
self.(hashMap_slots) hash_mod;
let (l, index_mut_back) := p in
p1 <- hashMap_remove_from_list T n key l;
let (x, l1) := p1 in
match x with
| None =>
v <- index_mut_back l1;
Ok (None,
{|
hashMap_num_entries := self.(hashMap_num_entries);
hashMap_max_load_factor := self.(hashMap_max_load_factor);
hashMap_max_load := self.(hashMap_max_load);
hashMap_slots := v
|})
| Some x1 =>
i1 <- usize_sub self.(hashMap_num_entries) 1%usize;
v <- index_mut_back l1;
Ok (Some x1,
{|
hashMap_num_entries := i1;
hashMap_max_load_factor := self.(hashMap_max_load_factor);
hashMap_max_load := self.(hashMap_max_load);
hashMap_slots := v
|})
end
.
(** [hashmap::test1]:
Source: 'tests/src/hashmap.rs', lines 315:0-315:10 *)
Definition test1 (n : nat) : result unit :=
hm <- hashMap_new u64 n;
hm1 <- hashMap_insert u64 n hm 0%usize 42%u64;
hm2 <- hashMap_insert u64 n hm1 128%usize 18%u64;
hm3 <- hashMap_insert u64 n hm2 1024%usize 138%u64;
hm4 <- hashMap_insert u64 n hm3 1056%usize 256%u64;
i <- hashMap_get u64 n hm4 128%usize;
if negb (i s= 18%u64)
then Fail_ Failure
else (
p <- hashMap_get_mut u64 n hm4 1024%usize;
let (_, get_mut_back) := p in
hm5 <- get_mut_back 56%u64;
i1 <- hashMap_get u64 n hm5 1024%usize;
if negb (i1 s= 56%u64)
then Fail_ Failure
else (
p1 <- hashMap_remove u64 n hm5 1024%usize;
let (x, hm6) := p1 in
match x with
| None => Fail_ Failure
| Some x1 =>
if negb (x1 s= 56%u64)
then Fail_ Failure
else (
i2 <- hashMap_get u64 n hm6 0%usize;
if negb (i2 s= 42%u64)
then Fail_ Failure
else (
i3 <- hashMap_get u64 n hm6 128%usize;
if negb (i3 s= 18%u64)
then Fail_ Failure
else (
i4 <- hashMap_get u64 n hm6 1056%usize;
if negb (i4 s= 256%u64) then Fail_ Failure else Ok tt)))
end))
.
End Hashmap_Funs.
|
