1545

Committed 31 May 2024 06:53AM UTC coverage: 89.234% (-0.08%) from 89.312%

Build # 1545

Build Type

Pull #475

github

Committed by

web-flow

Commit Message

Merge 53e54d53c into 78018fdc1

Pull Request Pull Request #475: Refactor int hash and hash in container

Run Details

7 of 7 new or added lines in 4 files covered. (100.0%)

4 existing lines in 4 files now uncovered.

2644 of 2963 relevant lines covered (89.23%)

2587.51 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

89.83

/linked_hashmap/impl.mbt

// Copyright 2024 International Digital Economy Academy
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

// Default initial capacity
let default_init_capacity = 8

/// Create a hash map.
pub fn LinkedHashMap::new[K, V]() -> LinkedHashMap[K, V] {
  {
    size: 0,
    capacity: default_init_capacity,
    growAt: calc_grow_threshold(default_init_capacity),
    entries: FixedArray::make(default_init_capacity, None),
    head: None,
    tail: None,
  }
}

/// Create a hash map from array.
pub fn LinkedHashMap::from_array[K : Hash + Eq, V](
  arr : Array[(K, V)]
) -> LinkedHashMap[K, V] {
  let m = new()
  arr.iter(fn(e) { m.set(e.0, e.1) })
  m
}

/// Set a key-value pair into the hash map.
/// @alert unsafe "Panic if the hash map is full."
pub fn set[K : Hash + Eq, V](
  self : LinkedHashMap[K, V],
  key : K,
  value : V
) -> Unit {
  if self.capacity == 0 || self.size >= self.growAt {
    self.grow()
  }
  let hash = key.hash()
  let insert_entry = { psl: 0, hash, key, value, prev: None, next: None }
  loop 0, self.index(hash), insert_entry {
    i, idx, entry => {
      if i == self.capacity {
        panic()
      }
      match self.entries[idx] {
        None => {
          self.entries[idx] = Some(entry)
          self.size += 1
          self.add_entry_to_tail(insert_entry)
          break
        }
        Some(curr_entry) => {
          if curr_entry.hash == entry.hash && curr_entry.key == entry.key {
            curr_entry.value = entry.value
            break
          }
          if entry.psl > curr_entry.psl {
            self.entries[idx] = Some(entry)
            curr_entry.psl += 1
            continue i + 1, self.next_index(idx), curr_entry
          } else {
            entry.psl += 1
            continue i + 1, self.next_index(idx), entry
          }
        }
      }
    }
  }
}

pub fn op_set[K : Hash + Eq, V](
  self : LinkedHashMap[K, V],
  key : K,
  value : V
) -> Unit {
  self.set(key, value)
}

/// Get the value associated with a key.
pub fn get[K : Hash + Eq, V](self : LinkedHashMap[K, V], key : K) -> Option[V] {
  let hash = key.hash()
  for i = 0, idx = self.index(hash)
      i < self.capacity
      i = i + 1, idx = self.next_index(idx) {
    match self.entries[idx] {
      Some(entry) => {
        if entry.hash == hash && entry.key == key {
          break Some(entry.value)
        }
        if i > entry.psl {
          break None
        }
      }
      None => break None
    }
  } else {
    None
  }
}

pub fn op_get[K : Hash + Eq, V](
  self : LinkedHashMap[K, V],
  key : K
) -> Option[V] {
  self.get(key)
}

/// Get the value associated with a key, 
/// returns the provided default value if the key does not exist.
pub fn get_or_default[K : Hash + Eq, V](
  self : LinkedHashMap[K, V],
  key : K,
  default : V
) -> V {
  match self.get(key) {
    Some(v) => v
    None => default
  }
}

/// Check if the hash map contains a key.
pub fn contains[K : Hash + Eq, V](self : LinkedHashMap[K, V], key : K) -> Bool {
  match self.get(key) {
    Some(_) => true
    None => false
  }
}

/// Remove a key-value pair from hash map.
pub fn remove[K : Hash + Eq, V](self : LinkedHashMap[K, V], key : K) -> Unit {
  let hash = key.hash()
  for i = 0, idx = self.index(hash)
      i < self.capacity
      i = i + 1, idx = self.next_index(idx) {
    match self.entries[idx] {
      Some(entry) => {
        if entry.hash == hash && entry.key == key {
          self.entries[idx] = None
          self.shift_back(idx)
          self.size -= 1
          self.remove_entry(entry)
          break
        }
        if i > entry.psl {
          return
        }
      }
      None => ()
    }
  }
}

fn add_entry_to_tail[K : Eq, V](
  self : LinkedHashMap[K, V],
  entry : Entry[K, V]
) -> Unit {
  match self.tail {
    None => {
      self.head = Some(entry)
      self.tail = Some(entry)
    }
    Some(tail) => {
      tail.next = Some(entry)
      entry.prev = Some(tail)
      self.tail = Some(entry)
    }
  }
}

fn remove_entry[K : Eq, V](
  self : LinkedHashMap[K, V],
  entry : Entry[K, V]
) -> Unit {
  if self.is_empty() {
    self.head = None
    self.tail = None
  } else {
    match self.head {
      Some(head) => if head == entry { self.head = entry.next }
      None => ()
    }
    match self.tail {
      Some(tail) => if tail == entry { self.tail = entry.prev }
      None => ()
    }
    match entry.prev {
      Some(prev) => prev.next = entry.next
      None => ()
    }
    match entry.next {
      Some(next) => next.prev = entry.prev
      None => ()
    }
  }
  entry.prev = None
  entry.next = None
}

fn shift_back[K : Hash, V](
  self : LinkedHashMap[K, V],
  start_index : Int
) -> Unit {
  for i = 0, prev = start_index, curr = self.next_index(start_index)
      i < self.entries.length()
      i = i + 1, prev = curr, curr = self.next_index(curr) {
    match self.entries[curr] {
      Some(entry) => {
        if entry.psl == 0 {
          break
        }
        entry.psl -= 1
        self.entries[prev] = Some(entry)
        self.entries[curr] = None
      }
      None => break
    }
  }
}

fn grow[K : Hash + Eq, V](self : LinkedHashMap[K, V]) -> Unit {
  // handle zero capacity
  if self.capacity == 0 {
    self.capacity = default_init_capacity
    self.growAt = calc_grow_threshold(self.capacity)
    self.size = 0
    self.entries = FixedArray::make(self.capacity, None)
    return
  }
  let old_head = self.head
  self.entries = FixedArray::make(self.capacity * 2, None)
  self.capacity = self.capacity * 2
  self.growAt = calc_grow_threshold(self.capacity)
  self.size = 0
  self.head = None
  loop old_head {
    Some({ key, value, next, .. }) => {
      self.set(key, value)
      continue next
    }
    None => break
  }
}

fn index[K : Hash, V](self : LinkedHashMap[K, V], hash : Int) -> Int {
  hash.abs().land(self.capacity - 1)
}

fn next_index[K : Hash, V](self : LinkedHashMap[K, V], index : Int) -> Int {
  (index + 1).land(self.capacity - 1)
}

fn calc_grow_threshold(capacity : Int) -> Int {
  capacity * 13 / 16
}

1	// Copyright 2024 International Digital Economy Academy
2	//
3	// Licensed under the Apache License, Version 2.0 (the "License");
4	// you may not use this file except in compliance with the License.
5	// You may obtain a copy of the License at
6	//
7	// http://www.apache.org/licenses/LICENSE-2.0
8	//
9	// Unless required by applicable law or agreed to in writing, software
10	// distributed under the License is distributed on an "AS IS" BASIS,
11	// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12	// See the License for the specific language governing permissions and
13	// limitations under the License.
14
15	// Default initial capacity
16	let default_init_capacity = 8
17
18	/// Create a hash map.
19	pub fn LinkedHashMap::new[K, V]() -> LinkedHashMap[K, V] {
20	{	55✔
21	size: 0,
22	capacity: default_init_capacity,
23	growAt: calc_grow_threshold(default_init_capacity),
24	entries: FixedArray::make(default_init_capacity, None),
25	head: None,
26	tail: None,
27	}
28	}
29
30	/// Create a hash map from array.
31	pub fn LinkedHashMap::from_array[K : Hash + Eq, V](
32	arr : Array[(K, V)]
33	) -> LinkedHashMap[K, V] {
34	let m = new()	9✔
35	arr.iter(fn(e) { m.set(e.0, e.1) })	22✔
36	m
37	}
38
39	/// Set a key-value pair into the hash map.
40	/// @alert unsafe "Panic if the hash map is full."
41	pub fn set[K : Hash + Eq, V](
42	self : LinkedHashMap[K, V],
43	key : K,
44	value : V
45	) -> Unit {
46	if self.capacity == 0 \|\| self.size >= self.growAt {	188✔
47	self.grow()	2✔
48	}
49	let hash = key.hash()
50	let insert_entry = { psl: 0, hash, key, value, prev: None, next: None }
51	loop 0, self.index(hash), insert_entry {
52	i, idx, entry => {	247✔
53	if i == self.capacity {
54	panic()	×
55	}
56	match self.entries[idx] {
57	None => {	172✔
58	self.entries[idx] = Some(entry)
59	self.size += 1
60	self.add_entry_to_tail(insert_entry)
61	break
62	}
63	Some(curr_entry) => {	75✔
64	if curr_entry.hash == entry.hash && curr_entry.key == entry.key {
65	curr_entry.value = entry.value	16✔
66	break
67	}
68	if entry.psl > curr_entry.psl {
69	self.entries[idx] = Some(entry)	8✔
70	curr_entry.psl += 1
71	continue i + 1, self.next_index(idx), curr_entry
72	} else {
73	entry.psl += 1	51✔
74	continue i + 1, self.next_index(idx), entry
75	}
76	}
77	}
78	}
79	}
80	}
81
82	pub fn op_set[K : Hash + Eq, V](
83	self : LinkedHashMap[K, V],
84	key : K,
85	value : V
86	) -> Unit {
87	self.set(key, value)	9✔
88	}
89
90	/// Get the value associated with a key.
91	pub fn get[K : Hash + Eq, V](self : LinkedHashMap[K, V], key : K) -> Option[V] {
92	let hash = key.hash()	47✔
93	for i = 0, idx = self.index(hash)
94	i < self.capacity
95	i = i + 1, idx = self.next_index(idx) {
96	match self.entries[idx] {	57✔
97	Some(entry) => {	42✔
98	if entry.hash == hash && entry.key == key {
99	break Some(entry.value)	32✔
100	}
101	if i > entry.psl {
UNCOV 102	break None	×
103	}
104	}
105	None => break None	15✔
106	}
107	} else {
108	None	×
109	}
110	}
111
112	pub fn op_get[K : Hash + Eq, V](
113	self : LinkedHashMap[K, V],
114	key : K
115	) -> Option[V] {
116	self.get(key)	6✔
117	}
118
119	/// Get the value associated with a key,
120	/// returns the provided default value if the key does not exist.
121	pub fn get_or_default[K : Hash + Eq, V](
122	self : LinkedHashMap[K, V],
123	key : K,
124	default : V
125	) -> V {
126	match self.get(key) {	12✔
127	Some(v) => v	8✔
128	None => default	4✔
129	}
130	}
131
132	/// Check if the hash map contains a key.
133	pub fn contains[K : Hash + Eq, V](self : LinkedHashMap[K, V], key : K) -> Bool {
134	match self.get(key) {	8✔
135	Some(_) => true	4✔
136	None => false	4✔
137	}
138	}
139
140	/// Remove a key-value pair from hash map.
141	pub fn remove[K : Hash + Eq, V](self : LinkedHashMap[K, V], key : K) -> Unit {
142	let hash = key.hash()	13✔
143	for i = 0, idx = self.index(hash)
144	i < self.capacity
145	i = i + 1, idx = self.next_index(idx) {
146	match self.entries[idx] {	23✔
147	Some(entry) => {	17✔
148	if entry.hash == hash && entry.key == key {
149	self.entries[idx] = None	10✔
150	self.shift_back(idx)
151	self.size -= 1
152	self.remove_entry(entry)
153	break
154	}
155	if i > entry.psl {
156	return	3✔
157	}
158	}
159	None => ()	6✔
160	}
161	}
162	}
163
164	fn add_entry_to_tail[K : Eq, V](
165	self : LinkedHashMap[K, V],
166	entry : Entry[K, V]
167	) -> Unit {
168	match self.tail {	172✔
169	None => {	53✔
170	self.head = Some(entry)
171	self.tail = Some(entry)
172	}
173	Some(tail) => {	119✔
174	tail.next = Some(entry)
175	entry.prev = Some(tail)
176	self.tail = Some(entry)
177	}
178	}
179	}
180
181	fn remove_entry[K : Eq, V](
182	self : LinkedHashMap[K, V],
183	entry : Entry[K, V]
184	) -> Unit {
185	if self.is_empty() {	10✔
186	self.head = None	3✔
187	self.tail = None
188	} else {
189	match self.head {	7✔
190	Some(head) => if head == entry { self.head = entry.next }	2✔
191	None => ()	×
192	}
193	match self.tail {
194	Some(tail) => if tail == entry { self.tail = entry.prev }	1✔
195	None => ()	×
196	}
197	match entry.prev {
198	Some(prev) => prev.next = entry.next	5✔
199	None => ()	2✔
200	}
201	match entry.next {
202	Some(next) => next.prev = entry.prev	6✔
203	None => ()	1✔
204	}
205	}
206	entry.prev = None
207	entry.next = None
208	}
209
210	fn shift_back[K : Hash, V](
211	self : LinkedHashMap[K, V],
212	start_index : Int
213	) -> Unit {
214	for i = 0, prev = start_index, curr = self.next_index(start_index)	10✔
215	i < self.entries.length()
216	i = i + 1, prev = curr, curr = self.next_index(curr) {
217	match self.entries[curr] {	14✔
218	Some(entry) => {	6✔
219	if entry.psl == 0 {
220	break	2✔
221	}
222	entry.psl -= 1
223	self.entries[prev] = Some(entry)
224	self.entries[curr] = None
225	}
226	None => break	8✔
227	}
228	}
229	}
230
231	fn grow[K : Hash + Eq, V](self : LinkedHashMap[K, V]) -> Unit {
232	// handle zero capacity
233	if self.capacity == 0 {	2✔
234	self.capacity = default_init_capacity	×
235	self.growAt = calc_grow_threshold(self.capacity)
236	self.size = 0
237	self.entries = FixedArray::make(self.capacity, None)
238	return
239	}
240	let old_head = self.head
241	self.entries = FixedArray::make(self.capacity * 2, None)
242	self.capacity = self.capacity * 2
243	self.growAt = calc_grow_threshold(self.capacity)
244	self.size = 0
245	self.head = None
246	loop old_head {
247	Some({ key, value, next, .. }) => {	24✔
248	self.set(key, value)
249	continue next
250	}
251	None => break	2✔
252	}
253	}
254
255	fn index[K : Hash, V](self : LinkedHashMap[K, V], hash : Int) -> Int {
256	hash.abs().land(self.capacity - 1)	248✔
257	}
258
259	fn next_index[K : Hash, V](self : LinkedHashMap[K, V], index : Int) -> Int {
260	(index + 1).land(self.capacity - 1)	93✔
261	}
262
263	fn calc_grow_threshold(capacity : Int) -> Int {
264	capacity * 13 / 16	57✔
265	}

moonbitlang / core / 1545

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous