summaryrefslogtreecommitdiff
path: root/tests
diff options
context:
space:
mode:
Diffstat (limited to 'tests')
-rw-r--r--tests/lean/hashmap_on_disk/HashmapMain/Funs.lean891
1 files changed, 440 insertions, 451 deletions
diff --git a/tests/lean/hashmap_on_disk/HashmapMain/Funs.lean b/tests/lean/hashmap_on_disk/HashmapMain/Funs.lean
index 79d711e9..5e78d9cf 100644
--- a/tests/lean/hashmap_on_disk/HashmapMain/Funs.lean
+++ b/tests/lean/hashmap_on_disk/HashmapMain/Funs.lean
@@ -182,261 +182,365 @@ def hashmap_hash_map_insert_no_resize_fwd_back
hashmap_hash_map_max_load := self.hashmap_hash_map_max_load,
hashmap_hash_map_slots := v
}
- else
- do
- let l0 <- hashmap_hash_map_insert_in_list_back T key value l
- let v <-
- vec_index_mut_back (hashmap_list_t T) self.hashmap_hash_map_slots
- hash_mod l0
- result.ret
- {
- hashmap_hash_map_num_entries := self.hashmap_hash_map_num_entries,
- hashmap_hash_map_max_load_factor := self.hashmap_hash_map_max_load_factor,
- hashmap_hash_map_max_load := self.hashmap_hash_map_max_load,
- hashmap_hash_map_slots := v
- }
-
- /- [core::num::u32::{9}::MAX] -/
- def core_num_u32_max_body : result UInt32 :=
- result.ret (UInt32.ofNatCore 4294967295 (by intlit))
- def core_num_u32_max_c : UInt32 :=
- eval_global core_num_u32_max_body (by simp)
-
- /- [hashmap_main::hashmap::HashMap::{0}::move_elements_from_list] -/
- def hashmap_hash_map_move_elements_from_list_loop_fwd_back
- (T : Type) (ntable : hashmap_hash_map_t T) (ls : hashmap_list_t T) :
- (result (hashmap_hash_map_t T))
- :=
- match ls with
- | hashmap_list_t.HashmapListCons k v tl =>
+ else
do
- let ntable0 <- hashmap_hash_map_insert_no_resize_fwd_back T ntable k v
- hashmap_hash_map_move_elements_from_list_loop_fwd_back T ntable0 tl
- | hashmap_list_t.HashmapListNil => result.ret ntable
-
- termination_by hashmap_hash_map_move_elements_from_list_loop_fwd_back ntable
- ls => hashmap_hash_map_move_elements_from_list_loop_terminates
- T ntable ls
- decreasing_by
- hashmap_hash_map_move_elements_from_list_loop_decreases ntable ls
-
- /- [hashmap_main::hashmap::HashMap::{0}::move_elements_from_list] -/
- def hashmap_hash_map_move_elements_from_list_fwd_back
- (T : Type) (ntable : hashmap_hash_map_t T) (ls : hashmap_list_t T) :
- result (hashmap_hash_map_t T)
- :=
- hashmap_hash_map_move_elements_from_list_loop_fwd_back T ntable ls
+ let l0 <- hashmap_hash_map_insert_in_list_back T key value l
+ let v <-
+ vec_index_mut_back (hashmap_list_t T) self.hashmap_hash_map_slots
+ hash_mod l0
+ result.ret
+ {
+ hashmap_hash_map_num_entries := self.hashmap_hash_map_num_entries,
+ hashmap_hash_map_max_load_factor := self.hashmap_hash_map_max_load_factor,
+ hashmap_hash_map_max_load := self.hashmap_hash_map_max_load,
+ hashmap_hash_map_slots := v
+ }
+
+/- [core::num::u32::{9}::MAX] -/
+def core_num_u32_max_body : result UInt32 :=
+ result.ret (UInt32.ofNatCore 4294967295 (by intlit))
+def core_num_u32_max_c : UInt32 := eval_global core_num_u32_max_body (by simp)
+
+/- [hashmap_main::hashmap::HashMap::{0}::move_elements_from_list] -/
+def hashmap_hash_map_move_elements_from_list_loop_fwd_back
+ (T : Type) (ntable : hashmap_hash_map_t T) (ls : hashmap_list_t T) :
+ (result (hashmap_hash_map_t T))
+ :=
+ match ls with
+ | hashmap_list_t.HashmapListCons k v tl =>
+ do
+ let ntable0 <- hashmap_hash_map_insert_no_resize_fwd_back T ntable k v
+ hashmap_hash_map_move_elements_from_list_loop_fwd_back T ntable0 tl
+ | hashmap_list_t.HashmapListNil => result.ret ntable
- /- [hashmap_main::hashmap::HashMap::{0}::move_elements] -/
- def hashmap_hash_map_move_elements_loop_fwd_back
- (T : Type) (ntable : hashmap_hash_map_t T) (slots : vec (hashmap_list_t T))
- (i : USize) :
- (result ((hashmap_hash_map_t T) × (vec (hashmap_list_t T))))
- :=
- let i0 := vec_len (hashmap_list_t T) slots
- if i < i0
+termination_by hashmap_hash_map_move_elements_from_list_loop_fwd_back ntable ls
+ => hashmap_hash_map_move_elements_from_list_loop_terminates T
+ ntable ls
+decreasing_by hashmap_hash_map_move_elements_from_list_loop_decreases ntable ls
+
+/- [hashmap_main::hashmap::HashMap::{0}::move_elements_from_list] -/
+def hashmap_hash_map_move_elements_from_list_fwd_back
+ (T : Type) (ntable : hashmap_hash_map_t T) (ls : hashmap_list_t T) :
+ result (hashmap_hash_map_t T)
+ :=
+ hashmap_hash_map_move_elements_from_list_loop_fwd_back T ntable ls
+
+/- [hashmap_main::hashmap::HashMap::{0}::move_elements] -/
+def hashmap_hash_map_move_elements_loop_fwd_back
+ (T : Type) (ntable : hashmap_hash_map_t T) (slots : vec (hashmap_list_t T))
+ (i : USize) :
+ (result ((hashmap_hash_map_t T) × (vec (hashmap_list_t T))))
+ :=
+ let i0 := vec_len (hashmap_list_t T) slots
+ if i < i0
+ then
+ do
+ let l <- vec_index_mut_fwd (hashmap_list_t T) slots i
+ let ls :=
+ mem_replace_fwd (hashmap_list_t T) l hashmap_list_t.HashmapListNil
+ let ntable0 <-
+ hashmap_hash_map_move_elements_from_list_fwd_back T ntable ls
+ let i1 <- USize.checked_add i (USize.ofNatCore 1 (by intlit))
+ let l0 :=
+ mem_replace_back (hashmap_list_t T) l hashmap_list_t.HashmapListNil
+ let slots0 <- vec_index_mut_back (hashmap_list_t T) slots i l0
+ hashmap_hash_map_move_elements_loop_fwd_back T ntable0 slots0 i1
+ else result.ret (ntable, slots)
+termination_by hashmap_hash_map_move_elements_loop_fwd_back ntable slots i =>
+ hashmap_hash_map_move_elements_loop_terminates T ntable slots i
+decreasing_by hashmap_hash_map_move_elements_loop_decreases ntable slots i
+
+/- [hashmap_main::hashmap::HashMap::{0}::move_elements] -/
+def hashmap_hash_map_move_elements_fwd_back
+ (T : Type) (ntable : hashmap_hash_map_t T) (slots : vec (hashmap_list_t T))
+ (i : USize) :
+ result ((hashmap_hash_map_t T) × (vec (hashmap_list_t T)))
+ :=
+ hashmap_hash_map_move_elements_loop_fwd_back T ntable slots i
+
+/- [hashmap_main::hashmap::HashMap::{0}::try_resize] -/
+def hashmap_hash_map_try_resize_fwd_back
+ (T : Type) (self : hashmap_hash_map_t T) : result (hashmap_hash_map_t T) :=
+ do
+ let max_usize <- scalar_cast USize core_num_u32_max_c
+ let capacity := vec_len (hashmap_list_t T) self.hashmap_hash_map_slots
+ let n1 <- USize.checked_div max_usize (USize.ofNatCore 2 (by intlit))
+ let (i, i0) := self.hashmap_hash_map_max_load_factor
+ let i1 <- USize.checked_div n1 i
+ if capacity <= i1
then
do
- let l <- vec_index_mut_fwd (hashmap_list_t T) slots i
- let ls :=
- mem_replace_fwd (hashmap_list_t T) l hashmap_list_t.HashmapListNil
- let ntable0 <-
- hashmap_hash_map_move_elements_from_list_fwd_back T ntable ls
- let i1 <- USize.checked_add i (USize.ofNatCore 1 (by intlit))
- let l0 :=
- mem_replace_back (hashmap_list_t T) l hashmap_list_t.HashmapListNil
- let slots0 <- vec_index_mut_back (hashmap_list_t T) slots i l0
- hashmap_hash_map_move_elements_loop_fwd_back T ntable0 slots0 i1
- else result.ret (ntable, slots)
- termination_by hashmap_hash_map_move_elements_loop_fwd_back ntable slots i =>
- hashmap_hash_map_move_elements_loop_terminates T ntable slots i
- decreasing_by hashmap_hash_map_move_elements_loop_decreases ntable slots i
+ let i2 <- USize.checked_mul capacity (USize.ofNatCore 2 (by intlit))
+ let ntable <- hashmap_hash_map_new_with_capacity_fwd T i2 i i0
+ let (ntable0, _) <-
+ hashmap_hash_map_move_elements_fwd_back T ntable
+ self.hashmap_hash_map_slots (USize.ofNatCore 0 (by intlit))
+ result.ret
+ {
+ hashmap_hash_map_num_entries := self.hashmap_hash_map_num_entries,
+ hashmap_hash_map_max_load_factor := (i, i0),
+ hashmap_hash_map_max_load := ntable0.hashmap_hash_map_max_load,
+ hashmap_hash_map_slots := ntable0.hashmap_hash_map_slots
+ }
+ else
+ result.ret
+ {
+ hashmap_hash_map_num_entries := self.hashmap_hash_map_num_entries,
+ hashmap_hash_map_max_load_factor := (i, i0),
+ hashmap_hash_map_max_load := self.hashmap_hash_map_max_load,
+ hashmap_hash_map_slots := self.hashmap_hash_map_slots
+ }
+
+/- [hashmap_main::hashmap::HashMap::{0}::insert] -/
+def hashmap_hash_map_insert_fwd_back
+ (T : Type) (self : hashmap_hash_map_t T) (key : USize) (value : T) :
+ result (hashmap_hash_map_t T)
+ :=
+ do
+ let self0 <- hashmap_hash_map_insert_no_resize_fwd_back T self key value
+ let i <- hashmap_hash_map_len_fwd T self0
+ if i > self0.hashmap_hash_map_max_load
+ then hashmap_hash_map_try_resize_fwd_back T self0
+ else result.ret self0
+
+/- [hashmap_main::hashmap::HashMap::{0}::contains_key_in_list] -/
+def hashmap_hash_map_contains_key_in_list_loop_fwd
+ (T : Type) (key : USize) (ls : hashmap_list_t T) : (result Bool) :=
+ match ls with
+ | hashmap_list_t.HashmapListCons ckey t tl =>
+ if ckey = key
+ then result.ret true
+ else hashmap_hash_map_contains_key_in_list_loop_fwd T key tl
+ | hashmap_list_t.HashmapListNil => result.ret false
- /- [hashmap_main::hashmap::HashMap::{0}::move_elements] -/
- def hashmap_hash_map_move_elements_fwd_back
- (T : Type) (ntable : hashmap_hash_map_t T) (slots : vec (hashmap_list_t T))
- (i : USize) :
- result ((hashmap_hash_map_t T) × (vec (hashmap_list_t T)))
- :=
- hashmap_hash_map_move_elements_loop_fwd_back T ntable slots i
+termination_by hashmap_hash_map_contains_key_in_list_loop_fwd key ls =>
+ hashmap_hash_map_contains_key_in_list_loop_terminates T key ls
+decreasing_by hashmap_hash_map_contains_key_in_list_loop_decreases key ls
+
+/- [hashmap_main::hashmap::HashMap::{0}::contains_key_in_list] -/
+def hashmap_hash_map_contains_key_in_list_fwd
+ (T : Type) (key : USize) (ls : hashmap_list_t T) : result Bool :=
+ hashmap_hash_map_contains_key_in_list_loop_fwd T key ls
+
+/- [hashmap_main::hashmap::HashMap::{0}::contains_key] -/
+def hashmap_hash_map_contains_key_fwd
+ (T : Type) (self : hashmap_hash_map_t T) (key : USize) : result Bool :=
+ do
+ let hash <- hashmap_hash_key_fwd key
+ let i := vec_len (hashmap_list_t T) self.hashmap_hash_map_slots
+ let hash_mod <- USize.checked_rem hash i
+ let l <-
+ vec_index_fwd (hashmap_list_t T) self.hashmap_hash_map_slots hash_mod
+ hashmap_hash_map_contains_key_in_list_fwd T key l
+
+/- [hashmap_main::hashmap::HashMap::{0}::get_in_list] -/
+def hashmap_hash_map_get_in_list_loop_fwd
+ (T : Type) (key : USize) (ls : hashmap_list_t T) : (result T) :=
+ match ls with
+ | hashmap_list_t.HashmapListCons ckey cvalue tl =>
+ if ckey = key
+ then result.ret cvalue
+ else hashmap_hash_map_get_in_list_loop_fwd T key tl
+ | hashmap_list_t.HashmapListNil => result.fail error.panic
- /- [hashmap_main::hashmap::HashMap::{0}::try_resize] -/
- def hashmap_hash_map_try_resize_fwd_back
- (T : Type) (self : hashmap_hash_map_t T) : result (hashmap_hash_map_t T) :=
- do
- let max_usize <- scalar_cast USize core_num_u32_max_c
- let capacity := vec_len (hashmap_list_t T) self.hashmap_hash_map_slots
- let n1 <- USize.checked_div max_usize (USize.ofNatCore 2 (by intlit))
- let (i, i0) := self.hashmap_hash_map_max_load_factor
- let i1 <- USize.checked_div n1 i
- if capacity <= i1
- then
- do
- let i2 <- USize.checked_mul capacity (USize.ofNatCore 2 (by intlit))
- let ntable <- hashmap_hash_map_new_with_capacity_fwd T i2 i i0
- let (ntable0, _) <-
- hashmap_hash_map_move_elements_fwd_back T ntable
- self.hashmap_hash_map_slots (USize.ofNatCore 0 (by intlit))
- result.ret
- {
- hashmap_hash_map_num_entries := self.hashmap_hash_map_num_entries,
- hashmap_hash_map_max_load_factor := (i, i0),
- hashmap_hash_map_max_load := ntable0.hashmap_hash_map_max_load,
- hashmap_hash_map_slots := ntable0.hashmap_hash_map_slots
- }
- else
- result.ret
- {
- hashmap_hash_map_num_entries := self.hashmap_hash_map_num_entries,
- hashmap_hash_map_max_load_factor := (i, i0),
- hashmap_hash_map_max_load := self.hashmap_hash_map_max_load,
- hashmap_hash_map_slots := self.hashmap_hash_map_slots
- }
-
- /- [hashmap_main::hashmap::HashMap::{0}::insert] -/
- def hashmap_hash_map_insert_fwd_back
- (T : Type) (self : hashmap_hash_map_t T) (key : USize) (value : T) :
- result (hashmap_hash_map_t T)
- :=
- do
- let self0 <-
- hashmap_hash_map_insert_no_resize_fwd_back T self key value
- let i <- hashmap_hash_map_len_fwd T self0
- if i > self0.hashmap_hash_map_max_load
- then hashmap_hash_map_try_resize_fwd_back T self0
- else result.ret self0
-
- /- [hashmap_main::hashmap::HashMap::{0}::contains_key_in_list] -/
- def hashmap_hash_map_contains_key_in_list_loop_fwd
- (T : Type) (key : USize) (ls : hashmap_list_t T) : (result Bool) :=
- match ls with
- | hashmap_list_t.HashmapListCons ckey t tl =>
- if ckey = key
- then result.ret true
- else hashmap_hash_map_contains_key_in_list_loop_fwd T key tl
- | hashmap_list_t.HashmapListNil => result.ret false
-
- termination_by hashmap_hash_map_contains_key_in_list_loop_fwd key ls =>
- hashmap_hash_map_contains_key_in_list_loop_terminates T key ls
- decreasing_by hashmap_hash_map_contains_key_in_list_loop_decreases key ls
-
- /- [hashmap_main::hashmap::HashMap::{0}::contains_key_in_list] -/
- def hashmap_hash_map_contains_key_in_list_fwd
- (T : Type) (key : USize) (ls : hashmap_list_t T) : result Bool :=
- hashmap_hash_map_contains_key_in_list_loop_fwd T key ls
-
- /- [hashmap_main::hashmap::HashMap::{0}::contains_key] -/
- def hashmap_hash_map_contains_key_fwd
- (T : Type) (self : hashmap_hash_map_t T) (key : USize) : result Bool :=
- do
- let hash <- hashmap_hash_key_fwd key
- let i := vec_len (hashmap_list_t T) self.hashmap_hash_map_slots
- let hash_mod <- USize.checked_rem hash i
- let l <-
- vec_index_fwd (hashmap_list_t T) self.hashmap_hash_map_slots hash_mod
- hashmap_hash_map_contains_key_in_list_fwd T key l
-
- /- [hashmap_main::hashmap::HashMap::{0}::get_in_list] -/
- def hashmap_hash_map_get_in_list_loop_fwd
- (T : Type) (key : USize) (ls : hashmap_list_t T) : (result T) :=
- match ls with
- | hashmap_list_t.HashmapListCons ckey cvalue tl =>
- if ckey = key
- then result.ret cvalue
- else hashmap_hash_map_get_in_list_loop_fwd T key tl
- | hashmap_list_t.HashmapListNil => result.fail error.panic
-
- termination_by hashmap_hash_map_get_in_list_loop_fwd key ls =>
- hashmap_hash_map_get_in_list_loop_terminates
- T key ls
- decreasing_by hashmap_hash_map_get_in_list_loop_decreases key ls
-
- /- [hashmap_main::hashmap::HashMap::{0}::get_in_list] -/
- def hashmap_hash_map_get_in_list_fwd
- (T : Type) (key : USize) (ls : hashmap_list_t T) : result T :=
- hashmap_hash_map_get_in_list_loop_fwd T key ls
-
- /- [hashmap_main::hashmap::HashMap::{0}::get] -/
- def hashmap_hash_map_get_fwd
- (T : Type) (self : hashmap_hash_map_t T) (key : USize) : result T :=
+termination_by hashmap_hash_map_get_in_list_loop_fwd key ls =>
+ hashmap_hash_map_get_in_list_loop_terminates
+ T key ls
+decreasing_by hashmap_hash_map_get_in_list_loop_decreases key ls
+
+/- [hashmap_main::hashmap::HashMap::{0}::get_in_list] -/
+def hashmap_hash_map_get_in_list_fwd
+ (T : Type) (key : USize) (ls : hashmap_list_t T) : result T :=
+ hashmap_hash_map_get_in_list_loop_fwd T key ls
+
+/- [hashmap_main::hashmap::HashMap::{0}::get] -/
+def hashmap_hash_map_get_fwd
+ (T : Type) (self : hashmap_hash_map_t T) (key : USize) : result T :=
+ do
+ let hash <- hashmap_hash_key_fwd key
+ let i := vec_len (hashmap_list_t T) self.hashmap_hash_map_slots
+ let hash_mod <- USize.checked_rem hash i
+ let l <-
+ vec_index_fwd (hashmap_list_t T) self.hashmap_hash_map_slots hash_mod
+ hashmap_hash_map_get_in_list_fwd T key l
+
+/- [hashmap_main::hashmap::HashMap::{0}::get_mut_in_list] -/
+def hashmap_hash_map_get_mut_in_list_loop_fwd
+ (T : Type) (ls : hashmap_list_t T) (key : USize) : (result T) :=
+ match ls with
+ | hashmap_list_t.HashmapListCons ckey cvalue tl =>
+ if ckey = key
+ then result.ret cvalue
+ else hashmap_hash_map_get_mut_in_list_loop_fwd T tl key
+ | hashmap_list_t.HashmapListNil => result.fail error.panic
+
+termination_by hashmap_hash_map_get_mut_in_list_loop_fwd ls key =>
+ hashmap_hash_map_get_mut_in_list_loop_terminates
+ T ls key
+decreasing_by hashmap_hash_map_get_mut_in_list_loop_decreases ls key
+
+/- [hashmap_main::hashmap::HashMap::{0}::get_mut_in_list] -/
+def hashmap_hash_map_get_mut_in_list_fwd
+ (T : Type) (ls : hashmap_list_t T) (key : USize) : result T :=
+ hashmap_hash_map_get_mut_in_list_loop_fwd T ls key
+
+/- [hashmap_main::hashmap::HashMap::{0}::get_mut_in_list] -/
+def hashmap_hash_map_get_mut_in_list_loop_back
+ (T : Type) (ls : hashmap_list_t T) (key : USize) (ret0 : T) :
+ (result (hashmap_list_t T))
+ :=
+ match ls with
+ | hashmap_list_t.HashmapListCons ckey cvalue tl =>
+ if ckey = key
+ then result.ret (hashmap_list_t.HashmapListCons ckey ret0 tl)
+ else
do
- let hash <- hashmap_hash_key_fwd key
- let i := vec_len (hashmap_list_t T) self.hashmap_hash_map_slots
- let hash_mod <- USize.checked_rem hash i
- let l <-
- vec_index_fwd (hashmap_list_t T) self.hashmap_hash_map_slots hash_mod
- hashmap_hash_map_get_in_list_fwd T key l
-
- /- [hashmap_main::hashmap::HashMap::{0}::get_mut_in_list] -/
- def hashmap_hash_map_get_mut_in_list_loop_fwd
- (T : Type) (ls : hashmap_list_t T) (key : USize) : (result T) :=
- match ls with
- | hashmap_list_t.HashmapListCons ckey cvalue tl =>
- if ckey = key
- then result.ret cvalue
- else hashmap_hash_map_get_mut_in_list_loop_fwd T tl key
+ let l <- hashmap_hash_map_get_mut_in_list_loop_back T tl key ret0
+ result.ret (hashmap_list_t.HashmapListCons ckey cvalue l)
+ | hashmap_list_t.HashmapListNil => result.fail error.panic
+
+termination_by hashmap_hash_map_get_mut_in_list_loop_back ls key ret0 =>
+ hashmap_hash_map_get_mut_in_list_loop_terminates T ls key
+decreasing_by hashmap_hash_map_get_mut_in_list_loop_decreases ls key
+
+/- [hashmap_main::hashmap::HashMap::{0}::get_mut_in_list] -/
+def hashmap_hash_map_get_mut_in_list_back
+ (T : Type) (ls : hashmap_list_t T) (key : USize) (ret0 : T) :
+ result (hashmap_list_t T)
+ :=
+ hashmap_hash_map_get_mut_in_list_loop_back T ls key ret0
+
+/- [hashmap_main::hashmap::HashMap::{0}::get_mut] -/
+def hashmap_hash_map_get_mut_fwd
+ (T : Type) (self : hashmap_hash_map_t T) (key : USize) : result T :=
+ do
+ let hash <- hashmap_hash_key_fwd key
+ let i := vec_len (hashmap_list_t T) self.hashmap_hash_map_slots
+ let hash_mod <- USize.checked_rem hash i
+ let l <-
+ vec_index_mut_fwd (hashmap_list_t T) self.hashmap_hash_map_slots hash_mod
+ hashmap_hash_map_get_mut_in_list_fwd T l key
+
+/- [hashmap_main::hashmap::HashMap::{0}::get_mut] -/
+def hashmap_hash_map_get_mut_back
+ (T : Type) (self : hashmap_hash_map_t T) (key : USize) (ret0 : T) :
+ result (hashmap_hash_map_t T)
+ :=
+ do
+ let hash <- hashmap_hash_key_fwd key
+ let i := vec_len (hashmap_list_t T) self.hashmap_hash_map_slots
+ let hash_mod <- USize.checked_rem hash i
+ let l <-
+ vec_index_mut_fwd (hashmap_list_t T) self.hashmap_hash_map_slots hash_mod
+ let l0 <- hashmap_hash_map_get_mut_in_list_back T l key ret0
+ let v <-
+ vec_index_mut_back (hashmap_list_t T) self.hashmap_hash_map_slots
+ hash_mod l0
+ result.ret
+ {
+ hashmap_hash_map_num_entries := self.hashmap_hash_map_num_entries,
+ hashmap_hash_map_max_load_factor := self.hashmap_hash_map_max_load_factor,
+ hashmap_hash_map_max_load := self.hashmap_hash_map_max_load,
+ hashmap_hash_map_slots := v
+ }
+
+/- [hashmap_main::hashmap::HashMap::{0}::remove_from_list] -/
+def hashmap_hash_map_remove_from_list_loop_fwd
+ (T : Type) (key : USize) (ls : hashmap_list_t T) : (result (Option T)) :=
+ match ls with
+ | hashmap_list_t.HashmapListCons ckey t tl =>
+ if ckey = key
+ then
+ let mv_ls :=
+ mem_replace_fwd (hashmap_list_t T) (hashmap_list_t.HashmapListCons ckey
+ t tl) hashmap_list_t.HashmapListNil
+ match mv_ls with
+ | hashmap_list_t.HashmapListCons i cvalue tl0 =>
+ result.ret (Option.some cvalue)
| hashmap_list_t.HashmapListNil => result.fail error.panic
- termination_by hashmap_hash_map_get_mut_in_list_loop_fwd ls key =>
- hashmap_hash_map_get_mut_in_list_loop_terminates T ls key
- decreasing_by hashmap_hash_map_get_mut_in_list_loop_decreases ls key
-
- /- [hashmap_main::hashmap::HashMap::{0}::get_mut_in_list] -/
- def hashmap_hash_map_get_mut_in_list_fwd
- (T : Type) (ls : hashmap_list_t T) (key : USize) : result T :=
- hashmap_hash_map_get_mut_in_list_loop_fwd T ls key
-
- /- [hashmap_main::hashmap::HashMap::{0}::get_mut_in_list] -/
- def hashmap_hash_map_get_mut_in_list_loop_back
- (T : Type) (ls : hashmap_list_t T) (key : USize) (ret0 : T) :
- (result (hashmap_list_t T))
- :=
- match ls with
- | hashmap_list_t.HashmapListCons ckey cvalue tl =>
- if ckey = key
- then result.ret (hashmap_list_t.HashmapListCons ckey ret0 tl)
- else
- do
- let l <- hashmap_hash_map_get_mut_in_list_loop_back T tl key ret0
- result.ret (hashmap_list_t.HashmapListCons ckey cvalue l)
+ else hashmap_hash_map_remove_from_list_loop_fwd T key tl
+ | hashmap_list_t.HashmapListNil => result.ret Option.none
+
+termination_by hashmap_hash_map_remove_from_list_loop_fwd key ls =>
+ hashmap_hash_map_remove_from_list_loop_terminates
+ T key ls
+decreasing_by hashmap_hash_map_remove_from_list_loop_decreases key ls
+
+/- [hashmap_main::hashmap::HashMap::{0}::remove_from_list] -/
+def hashmap_hash_map_remove_from_list_fwd
+ (T : Type) (key : USize) (ls : hashmap_list_t T) : result (Option T) :=
+ hashmap_hash_map_remove_from_list_loop_fwd T key ls
+
+/- [hashmap_main::hashmap::HashMap::{0}::remove_from_list] -/
+def hashmap_hash_map_remove_from_list_loop_back
+ (T : Type) (key : USize) (ls : hashmap_list_t T) :
+ (result (hashmap_list_t T))
+ :=
+ match ls with
+ | hashmap_list_t.HashmapListCons ckey t tl =>
+ if ckey = key
+ then
+ let mv_ls :=
+ mem_replace_fwd (hashmap_list_t T) (hashmap_list_t.HashmapListCons ckey
+ t tl) hashmap_list_t.HashmapListNil
+ match mv_ls with
+ | hashmap_list_t.HashmapListCons i cvalue tl0 => result.ret tl0
| hashmap_list_t.HashmapListNil => result.fail error.panic
- termination_by hashmap_hash_map_get_mut_in_list_loop_back ls key ret0 =>
- hashmap_hash_map_get_mut_in_list_loop_terminates T ls key
- decreasing_by hashmap_hash_map_get_mut_in_list_loop_decreases ls key
-
- /- [hashmap_main::hashmap::HashMap::{0}::get_mut_in_list] -/
- def hashmap_hash_map_get_mut_in_list_back
- (T : Type) (ls : hashmap_list_t T) (key : USize) (ret0 : T) :
- result (hashmap_list_t T)
- :=
- hashmap_hash_map_get_mut_in_list_loop_back T ls key ret0
-
- /- [hashmap_main::hashmap::HashMap::{0}::get_mut] -/
- def hashmap_hash_map_get_mut_fwd
- (T : Type) (self : hashmap_hash_map_t T) (key : USize) : result T :=
+ else
+ do
+ let l <- hashmap_hash_map_remove_from_list_loop_back T key tl
+ result.ret (hashmap_list_t.HashmapListCons ckey t l)
+ | hashmap_list_t.HashmapListNil => result.ret hashmap_list_t.HashmapListNil
+
+termination_by hashmap_hash_map_remove_from_list_loop_back key ls =>
+ hashmap_hash_map_remove_from_list_loop_terminates
+ T key ls
+decreasing_by hashmap_hash_map_remove_from_list_loop_decreases key ls
+
+/- [hashmap_main::hashmap::HashMap::{0}::remove_from_list] -/
+def hashmap_hash_map_remove_from_list_back
+ (T : Type) (key : USize) (ls : hashmap_list_t T) :
+ result (hashmap_list_t T)
+ :=
+ hashmap_hash_map_remove_from_list_loop_back T key ls
+
+/- [hashmap_main::hashmap::HashMap::{0}::remove] -/
+def hashmap_hash_map_remove_fwd
+ (T : Type) (self : hashmap_hash_map_t T) (key : USize) : result (Option T) :=
+ do
+ let hash <- hashmap_hash_key_fwd key
+ let i := vec_len (hashmap_list_t T) self.hashmap_hash_map_slots
+ let hash_mod <- USize.checked_rem hash i
+ let l <-
+ vec_index_mut_fwd (hashmap_list_t T) self.hashmap_hash_map_slots hash_mod
+ let x <- hashmap_hash_map_remove_from_list_fwd T key l
+ match x with
+ | Option.none => result.ret Option.none
+ | Option.some x0 =>
do
- let hash <- hashmap_hash_key_fwd key
- let i := vec_len (hashmap_list_t T) self.hashmap_hash_map_slots
- let hash_mod <- USize.checked_rem hash i
- let l <-
- vec_index_mut_fwd (hashmap_list_t T) self.hashmap_hash_map_slots
- hash_mod
- hashmap_hash_map_get_mut_in_list_fwd T l key
+ let _ <- USize.checked_sub self.hashmap_hash_map_num_entries
+ (USize.ofNatCore 1 (by intlit))
+ result.ret (Option.some x0)
- /- [hashmap_main::hashmap::HashMap::{0}::get_mut] -/
- def hashmap_hash_map_get_mut_back
- (T : Type) (self : hashmap_hash_map_t T) (key : USize) (ret0 : T) :
- result (hashmap_hash_map_t T)
- :=
+
+/- [hashmap_main::hashmap::HashMap::{0}::remove] -/
+def hashmap_hash_map_remove_back
+ (T : Type) (self : hashmap_hash_map_t T) (key : USize) :
+ result (hashmap_hash_map_t T)
+ :=
+ do
+ let hash <- hashmap_hash_key_fwd key
+ let i := vec_len (hashmap_list_t T) self.hashmap_hash_map_slots
+ let hash_mod <- USize.checked_rem hash i
+ let l <-
+ vec_index_mut_fwd (hashmap_list_t T) self.hashmap_hash_map_slots hash_mod
+ let x <- hashmap_hash_map_remove_from_list_fwd T key l
+ match x with
+ | Option.none =>
do
- let hash <- hashmap_hash_key_fwd key
- let i := vec_len (hashmap_list_t T) self.hashmap_hash_map_slots
- let hash_mod <- USize.checked_rem hash i
- let l <-
- vec_index_mut_fwd (hashmap_list_t T) self.hashmap_hash_map_slots
- hash_mod
- let l0 <- hashmap_hash_map_get_mut_in_list_back T l key ret0
+ let l0 <- hashmap_hash_map_remove_from_list_back T key l
let v <-
vec_index_mut_back (hashmap_list_t T) self.hashmap_hash_map_slots
hash_mod l0
@@ -447,221 +551,106 @@ def hashmap_hash_map_insert_no_resize_fwd_back
hashmap_hash_map_max_load := self.hashmap_hash_map_max_load,
hashmap_hash_map_slots := v
}
-
- /- [hashmap_main::hashmap::HashMap::{0}::remove_from_list] -/
- def hashmap_hash_map_remove_from_list_loop_fwd
- (T : Type) (key : USize) (ls : hashmap_list_t T) : (result (Option T)) :=
- match ls with
- | hashmap_list_t.HashmapListCons ckey t tl =>
- if ckey = key
- then
- let mv_ls :=
- mem_replace_fwd (hashmap_list_t T) (hashmap_list_t.HashmapListCons
- ckey t tl) hashmap_list_t.HashmapListNil
- match mv_ls with
- | hashmap_list_t.HashmapListCons i cvalue tl0 =>
- result.ret (Option.some cvalue)
- | hashmap_list_t.HashmapListNil => result.fail error.panic
-
- else hashmap_hash_map_remove_from_list_loop_fwd T key tl
- | hashmap_list_t.HashmapListNil => result.ret Option.none
-
- termination_by hashmap_hash_map_remove_from_list_loop_fwd key ls =>
- hashmap_hash_map_remove_from_list_loop_terminates T key ls
- decreasing_by hashmap_hash_map_remove_from_list_loop_decreases key ls
-
- /- [hashmap_main::hashmap::HashMap::{0}::remove_from_list] -/
- def hashmap_hash_map_remove_from_list_fwd
- (T : Type) (key : USize) (ls : hashmap_list_t T) : result (Option T) :=
- hashmap_hash_map_remove_from_list_loop_fwd T key ls
-
- /- [hashmap_main::hashmap::HashMap::{0}::remove_from_list] -/
- def hashmap_hash_map_remove_from_list_loop_back
- (T : Type) (key : USize) (ls : hashmap_list_t T) :
- (result (hashmap_list_t T))
- :=
- match ls with
- | hashmap_list_t.HashmapListCons ckey t tl =>
- if ckey = key
- then
- let mv_ls :=
- mem_replace_fwd (hashmap_list_t T) (hashmap_list_t.HashmapListCons
- ckey t tl) hashmap_list_t.HashmapListNil
- match mv_ls with
- | hashmap_list_t.HashmapListCons i cvalue tl0 => result.ret tl0
- | hashmap_list_t.HashmapListNil => result.fail error.panic
-
- else
- do
- let l <- hashmap_hash_map_remove_from_list_loop_back T key tl
- result.ret (hashmap_list_t.HashmapListCons ckey t l)
- | hashmap_list_t.HashmapListNil =>
- result.ret hashmap_list_t.HashmapListNil
-
- termination_by hashmap_hash_map_remove_from_list_loop_back key ls =>
- hashmap_hash_map_remove_from_list_loop_terminates T key ls
- decreasing_by hashmap_hash_map_remove_from_list_loop_decreases key ls
-
- /- [hashmap_main::hashmap::HashMap::{0}::remove_from_list] -/
- def hashmap_hash_map_remove_from_list_back
- (T : Type) (key : USize) (ls : hashmap_list_t T) :
- result (hashmap_list_t T)
- :=
- hashmap_hash_map_remove_from_list_loop_back T key ls
-
- /- [hashmap_main::hashmap::HashMap::{0}::remove] -/
- def hashmap_hash_map_remove_fwd
- (T : Type) (self : hashmap_hash_map_t T) (key : USize) :
- result (Option T)
- :=
+ | Option.some x0 =>
do
- let hash <- hashmap_hash_key_fwd key
- let i := vec_len (hashmap_list_t T) self.hashmap_hash_map_slots
- let hash_mod <- USize.checked_rem hash i
- let l <-
- vec_index_mut_fwd (hashmap_list_t T) self.hashmap_hash_map_slots
- hash_mod
- let x <- hashmap_hash_map_remove_from_list_fwd T key l
- match x with
- | Option.none => result.ret Option.none
- | Option.some x0 =>
- do
- let _ <- USize.checked_sub self.hashmap_hash_map_num_entries
- (USize.ofNatCore 1 (by intlit))
- result.ret (Option.some x0)
-
+ let i0 <- USize.checked_sub self.hashmap_hash_map_num_entries
+ (USize.ofNatCore 1 (by intlit))
+ let l0 <- hashmap_hash_map_remove_from_list_back T key l
+ let v <-
+ vec_index_mut_back (hashmap_list_t T) self.hashmap_hash_map_slots
+ hash_mod l0
+ result.ret
+ {
+ hashmap_hash_map_num_entries := i0,
+ hashmap_hash_map_max_load_factor := self.hashmap_hash_map_max_load_factor,
+ hashmap_hash_map_max_load := self.hashmap_hash_map_max_load,
+ hashmap_hash_map_slots := v
+ }
- /- [hashmap_main::hashmap::HashMap::{0}::remove] -/
- def hashmap_hash_map_remove_back
- (T : Type) (self : hashmap_hash_map_t T) (key : USize) :
- result (hashmap_hash_map_t T)
- :=
+
+/- [hashmap_main::hashmap::test1] -/
+def hashmap_test1_fwd : result Unit :=
+ do
+ let hm <- hashmap_hash_map_new_fwd UInt64
+ let hm0 <-
+ hashmap_hash_map_insert_fwd_back UInt64 hm
+ (USize.ofNatCore 0 (by intlit)) (UInt64.ofNatCore 42 (by intlit))
+ let hm1 <-
+ hashmap_hash_map_insert_fwd_back UInt64 hm0
+ (USize.ofNatCore 128 (by intlit)) (UInt64.ofNatCore 18 (by intlit))
+ let hm2 <-
+ hashmap_hash_map_insert_fwd_back UInt64 hm1
+ (USize.ofNatCore 1024 (by intlit)) (UInt64.ofNatCore 138 (by intlit))
+ let hm3 <-
+ hashmap_hash_map_insert_fwd_back UInt64 hm2
+ (USize.ofNatCore 1056 (by intlit)) (UInt64.ofNatCore 256 (by intlit))
+ let i <-
+ hashmap_hash_map_get_fwd UInt64 hm3 (USize.ofNatCore 128 (by intlit))
+ if not (i = (UInt64.ofNatCore 18 (by intlit)))
+ then result.fail error.panic
+ else
do
- let hash <- hashmap_hash_key_fwd key
- let i := vec_len (hashmap_list_t T) self.hashmap_hash_map_slots
- let hash_mod <- USize.checked_rem hash i
- let l <-
- vec_index_mut_fwd (hashmap_list_t T) self.hashmap_hash_map_slots
- hash_mod
- let x <- hashmap_hash_map_remove_from_list_fwd T key l
- match x with
- | Option.none =>
+ let hm4 <-
+ hashmap_hash_map_get_mut_back UInt64 hm3
+ (USize.ofNatCore 1024 (by intlit))
+ (UInt64.ofNatCore 56 (by intlit))
+ let i0 <-
+ hashmap_hash_map_get_fwd UInt64 hm4
+ (USize.ofNatCore 1024 (by intlit))
+ if not (i0 = (UInt64.ofNatCore 56 (by intlit)))
+ then result.fail error.panic
+ else
do
- let l0 <- hashmap_hash_map_remove_from_list_back T key l
- let v <-
- vec_index_mut_back (hashmap_list_t T) self.hashmap_hash_map_slots
- hash_mod l0
- result.ret
- {
- hashmap_hash_map_num_entries := self.hashmap_hash_map_num_entries,
- hashmap_hash_map_max_load_factor := self.hashmap_hash_map_max_load_factor,
- hashmap_hash_map_max_load := self.hashmap_hash_map_max_load,
- hashmap_hash_map_slots := v
- }
- | Option.some x0 =>
- do
- let i0 <- USize.checked_sub self.hashmap_hash_map_num_entries
- (USize.ofNatCore 1 (by intlit))
- let l0 <- hashmap_hash_map_remove_from_list_back T key l
- let v <-
- vec_index_mut_back (hashmap_list_t T)
- self.hashmap_hash_map_slots hash_mod l0
- result.ret
- {
- hashmap_hash_map_num_entries := i0,
- hashmap_hash_map_max_load_factor := self.hashmap_hash_map_max_load_factor,
- hashmap_hash_map_max_load := self.hashmap_hash_map_max_load,
- hashmap_hash_map_slots := v
- }
-
- /- [hashmap_main::hashmap::test1] -/
- def hashmap_test1_fwd : result Unit :=
- do
- let hm <- hashmap_hash_map_new_fwd UInt64
- let hm0 <-
- hashmap_hash_map_insert_fwd_back UInt64 hm
- (USize.ofNatCore 0 (by intlit)) (UInt64.ofNatCore 42 (by intlit))
- let hm1 <-
- hashmap_hash_map_insert_fwd_back UInt64 hm0
- (USize.ofNatCore 128 (by intlit))
- (UInt64.ofNatCore 18 (by intlit))
- let hm2 <-
- hashmap_hash_map_insert_fwd_back UInt64 hm1
- (USize.ofNatCore 1024 (by intlit))
- (UInt64.ofNatCore 138 (by intlit))
- let hm3 <-
- hashmap_hash_map_insert_fwd_back UInt64 hm2
- (USize.ofNatCore 1056 (by intlit))
- (UInt64.ofNatCore 256 (by intlit))
- let i <-
- hashmap_hash_map_get_fwd UInt64 hm3
- (USize.ofNatCore 128 (by intlit))
- if not (i = (UInt64.ofNatCore 18 (by intlit)))
- then result.fail error.panic
- else
- do
- let hm4 <-
- hashmap_hash_map_get_mut_back UInt64 hm3
- (USize.ofNatCore 1024 (by intlit))
- (UInt64.ofNatCore 56 (by intlit))
- let i0 <-
- hashmap_hash_map_get_fwd UInt64 hm4
- (USize.ofNatCore 1024 (by intlit))
- if not (i0 = (UInt64.ofNatCore 56 (by intlit)))
+ let x <-
+ hashmap_hash_map_remove_fwd UInt64 hm4
+ (USize.ofNatCore 1024 (by intlit))
+ match x with
+ | Option.none => result.fail error.panic
+ | Option.some x0 =>
+ if not (x0 = (UInt64.ofNatCore 56 (by intlit)))
then result.fail error.panic
else
do
- let x <-
- hashmap_hash_map_remove_fwd UInt64 hm4
+ let hm5 <-
+ hashmap_hash_map_remove_back UInt64 hm4
(USize.ofNatCore 1024 (by intlit))
- match x with
- | Option.none => result.fail error.panic
- | Option.some x0 =>
- if not (x0 = (UInt64.ofNatCore 56 (by intlit)))
- then result.fail error.panic
- else
- do
- let hm5 <-
- hashmap_hash_map_remove_back UInt64 hm4
- (USize.ofNatCore 1024 (by intlit))
- let i1 <-
- hashmap_hash_map_get_fwd UInt64 hm5
- (USize.ofNatCore 0 (by intlit))
- if not (i1 = (UInt64.ofNatCore 42 (by intlit)))
- then result.fail error.panic
- else
- do
- let i2 <-
- hashmap_hash_map_get_fwd UInt64 hm5
- (USize.ofNatCore 128 (by intlit))
- if not (i2 = (UInt64.ofNatCore 18 (by intlit)))
- then result.fail error.panic
- else
- do
- let i3 <-
- hashmap_hash_map_get_fwd UInt64 hm5
- (USize.ofNatCore 1056 (by intlit))
- if not (i3 =
- (UInt64.ofNatCore 256 (by intlit)))
- then result.fail error.panic
- else result.ret ()
-
-
- /- Unit test for [hashmap_main::hashmap::test1] -/
- #assert (hashmap_test1_fwd = ret ())
-
- /- [hashmap_main::insert_on_disk] -/
- def insert_on_disk_fwd
- (key : USize) (value : UInt64) (st : state) : result (state × Unit) :=
- do
- let (st0, hm) <- hashmap_utils_deserialize_fwd st
- let hm0 <- hashmap_hash_map_insert_fwd_back UInt64 hm key value
- let (st1, _) <- hashmap_utils_serialize_fwd hm0 st0
- result.ret (st1, ())
-
- /- [hashmap_main::main] -/
- def main_fwd : result Unit := result.ret ()
-
- /- Unit test for [hashmap_main::main] -/
- #assert (main_fwd = ret ())
-
+ let i1 <-
+ hashmap_hash_map_get_fwd UInt64 hm5
+ (USize.ofNatCore 0 (by intlit))
+ if not (i1 = (UInt64.ofNatCore 42 (by intlit)))
+ then result.fail error.panic
+ else
+ do
+ let i2 <-
+ hashmap_hash_map_get_fwd UInt64 hm5
+ (USize.ofNatCore 128 (by intlit))
+ if not (i2 = (UInt64.ofNatCore 18 (by intlit)))
+ then result.fail error.panic
+ else
+ do
+ let i3 <-
+ hashmap_hash_map_get_fwd UInt64 hm5
+ (USize.ofNatCore 1056 (by intlit))
+ if not (i3 = (UInt64.ofNatCore 256 (by intlit)))
+ then result.fail error.panic
+ else result.ret ()
+
+
+/- Unit test for [hashmap_main::hashmap::test1] -/
+#assert (hashmap_test1_fwd = ret ())
+
+/- [hashmap_main::insert_on_disk] -/
+def insert_on_disk_fwd
+ (key : USize) (value : UInt64) (st : state) : result (state × Unit) :=
+ do
+ let (st0, hm) <- hashmap_utils_deserialize_fwd st
+ let hm0 <- hashmap_hash_map_insert_fwd_back UInt64 hm key value
+ let (st1, _) <- hashmap_utils_serialize_fwd hm0 st0
+ result.ret (st1, ())
+
+/- [hashmap_main::main] -/
+def main_fwd : result Unit := result.ret ()
+
+/- Unit test for [hashmap_main::main] -/
+#assert (main_fwd = ret ())
+