Linux GNU 11.4.0 Code Coverage Report

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 84.7% 116 / 0 / 137
Functions: -% 0 / 1 / 1
Branches: 67.6% 69 / 0 / 102
OMCompiler/Compiler/Util/UnorderedMap.mo
Line Branch Exec Source
1 /*
2 * This file is part of OpenModelica.
3 *
4 * Copyright (c) 1998-2026, Open Source Modelica Consortium (OSMC),
5 * c/o Linköpings universitet, Department of Computer and Information Science,
6 * SE-58183 Linköping, Sweden.
7 *
8 * All rights reserved.
9 *
10 * THIS PROGRAM IS PROVIDED UNDER THE TERMS OF AGPL VERSION 3 LICENSE OR
11 * THIS OSMC PUBLIC LICENSE (OSMC-PL) VERSION 1.8.
12 * ANY USE, REPRODUCTION OR DISTRIBUTION OF THIS PROGRAM CONSTITUTES
13 * RECIPIENT'S ACCEPTANCE OF THE OSMC PUBLIC LICENSE OR THE GNU AGPL
14 * VERSION 3, ACCORDING TO RECIPIENTS CHOICE.
15 *
16 * The OpenModelica software and the OSMC (Open Source Modelica Consortium)
17 * Public License (OSMC-PL) are obtained from OSMC, either from the above
18 * address, from the URLs:
19 * http://www.openmodelica.org or
20 * https://github.com/OpenModelica/ or
21 * http://www.ida.liu.se/projects/OpenModelica,
22 * and in the OpenModelica distribution.
23 *
24 * GNU AGPL version 3 is obtained from:
25 * https://www.gnu.org/licenses/licenses.html#GPL
26 *
27 * This program is distributed WITHOUT ANY WARRANTY; without
28 * even the implied warranty of MERCHANTABILITY or FITNESS
29 * FOR A PARTICULAR PURPOSE, EXCEPT AS EXPRESSLY SET FORTH
30 * IN THE BY RECIPIENT SELECTED SUBSIDIARY LICENSE CONDITIONS OF OSMC-PL.
31 *
32 * See the full OSMC Public License conditions for more details.
33 *
34 */
35
36 encapsulated uniontype UnorderedMap<K, V>
37 "An implementation of a generic unordered map, a.k.a. hash map.
38
39 This implementation uses separate chaining and automatically rehashes the map
40 when the load factor becomes too large to keep the performance up."
41
42 import Vector;
43
44 protected
45 import Error;
46 import List;
47 import MetaModelica.Dangerous.*;
48 import Util;
49 import IOStream;
50 import UnorderedSet;
51
52 public
53 partial function Hash
54 input K key;
55 output Integer hash;
56 end Hash;
57
58 partial function KeyEq
59 input K key1;
60 input K key2;
61 output Boolean equal;
62 end KeyEq;
63
64 partial function KeyStringFn
65 input K key;
66 output String str;
67 end KeyStringFn;
68
69 partial function ValueStringFn
70 input V value;
71 output String str;
72 end ValueStringFn;
73
74 record UNORDERED_MAP
75 Vector<list<Integer>> buckets;
76 Vector<K> keys;
77 Vector<Integer> hashes "hashFn of each key";
78 Vector<V> values;
79 Hash hashFn;
80 KeyEq eqFn;
81 end UNORDERED_MAP;
82
83 function new<V>
84 "Creates a new map given a hash function, key equality function, and
85 optional desired bucket count. An appropriate bucket count is
86 Util.nextPrime(number of elements that will be added), but starting with a
87 low bucket count is also fine if the number of elements is unknown since
88 the map rehashes as needed."
89 input Hash hash;
90 input KeyEq keyEq;
91 input Integer bucketCount = 1;
92 output UnorderedMap<K, V> map;
93 algorithm
94 683348 map := UNORDERED_MAP(
95 Vector.newFill(bucketCount, {}),
96 Vector.new<K>(),
97 Vector.new<Integer>(),
98 Vector.new<V>(),
99 hash,
100 keyEq
101 );
102 end new;
103
104 function fromLists<V>
105 "Creates a new map from a list of keys and a corresponding list of values.
106 Fails if the two lists do not have the same size."
107 input list<K> keys;
108 input list<V> values;
109 input Hash hash;
110 input KeyEq keyEq;
111 output UnorderedMap<K, V> map;
112 protected
113 Integer key_count, bucket_count;
114 V v;
115 list<V> rest_v = values;
116 algorithm
117 1371 key_count := listLength(keys);
118 1371 bucket_count := Util.nextPrime(key_count);
119
120 1371 map := UNORDERED_MAP(
121 Vector.newFill(bucket_count, {}),
122 Vector.new<K>(key_count),
123 Vector.new<Integer>(key_count),
124 Vector.new<V>(key_count),
125 hash,
126 keyEq
127 );
128
129
2/2
✓ Branch 0 taken 1822 times.
✓ Branch 1 taken 1371 times.
 3193 for k in keys loop
130
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1822 times.
 1822 v :: rest_v := rest_v;
131 1822 add(k, v, map);
132 end for;
133 end fromLists;
134
135 function copy
136 "Returns a copy of the map."
137 input UnorderedMap<K, V> map;
138 output UnorderedMap<K, V> outMap;
139 algorithm
140 665 outMap := UNORDERED_MAP(
141 Vector.copy(map.buckets),
142 Vector.copy(map.keys),
143 Vector.copy(map.hashes),
144 Vector.copy(map.values),
145 map.hashFn,
146 map.eqFn
147 );
148 end copy;
149
150 function deepCopy
151 "Returns a deep copy of the map using the given copy function for values."
152 input UnorderedMap<K, V> map;
153 input CopyFn fn;
154 output UnorderedMap<K, V> outMap;
155
156 partial function CopyFn
157 input output V value;
158 end CopyFn;
159 algorithm
160 ✗ outMap := UNORDERED_MAP(
161 Vector.copy(map.buckets),
162 Vector.copy(map.keys),
163 Vector.copy(map.hashes),
164 Vector.deepCopy(map.values, fn),
165 map.hashFn,
166 map.eqFn
167 );
168 end deepCopy;
169
170 function add
171 "Adds a key and associated value to the map, or updates the value if the key
172 already exists in the map. Might trigger a rehash."
173 input K key;
174 input V value;
175 input UnorderedMap<K, V> map;
176 protected
177 Integer index, hash;
178 algorithm
179 2593050 (index, hash) := find(key, map);
180
181
2/2
✓ Branch 0 taken 245495 times.
✓ Branch 1 taken 2347555 times.
 2593050 if index > 0 then
182 245495 Vector.update(map.values, index, value);
183 else
184 2347555 addEntry(key, value, hash, map);
185 end if;
186 end add;
187
188 function addNew
189 "Adds a key and associated value to the map without checking if it already
190 exists. Faster than add since it doesn't need to check if the key exists,
191 but will lead to duplicate keys if it actually does exist in the map
192 already. Might trigger a rehash."
193 input K key;
194 input V value;
195 input UnorderedMap<K, V> map;
196 protected
197 Hash hashfn = map.hashFn;
198 algorithm
199
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 364305 times.
 364305 addEntry(key, value, hashfn(key), map);
200 end addNew;
201
202 function addUnique
203 "Adds a key and associated value to the map, but fails if the key already
204 exists. Might trigger a rehash."
205 input K key;
206 input V value;
207 input UnorderedMap<K, V> map;
208 protected
209 Integer index, hash;
210 algorithm
211 8302 (index, hash) := find(key, map);
212
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 8302 times.
 8302 false := index > 0;
213 8302 addEntry(key, value, hash, map);
214 end addUnique;
215
216 function tryAdd
217 "Adds a key and associated value to the map if the key doesn't already
218 exist, otherwise does nothing. Returns the value associated with the key if
219 the key already existed, otherwise the new value. Might trigger a rehash."
220 input K key;
221 input V value;
222 input UnorderedMap<K, V> map;
223 output V outValue;
224 protected
225 Integer index, hash;
226 algorithm
227 58115 (index, hash) := find(key, map);
228
229
2/2
✓ Branch 0 taken 9446 times.
✓ Branch 1 taken 48669 times.
 58115 if index > 0 then
230 9446 outValue := Vector.getNoBounds(map.values, index);
231 else
232 outValue := value;
233 48669 addEntry(key, value, hash, map);
234 end if;
235 end tryAdd;
236
237 function tryUpdate
238 "Updates the value associated with a key if the key exists in the map,
239 otherwise does nothing. Returns whether the value was updated or not,
240 i.e. if the key exists in the map or not."
241 input K key;
242 input V value;
243 input UnorderedMap<K, V> map;
244 output Boolean updated;
245 protected
246 Integer index, hash;
247 algorithm
248 11 (index, hash) := find(key, map);
249 11 updated := index > 0;
250
251
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 11 times.
 11 if updated then
252 11 Vector.update(map.values, index, value);
253 end if;
254 end tryUpdate;
255
256 function addUpdate
257 "Adds a key and associated value to the map, where the value is generated by
258 calling the given function. If the key already exists the function is given
259 the old value. The generated value is returned by this function.
260
261 This function can be used to e.g. append to an existing value or create a
262 new value if none exists. This is faster than trying to fetch the value,
263 updating it and then readding it, since the key only needs to be hashed
264 once."
265 input K key;
266 input UpdateFn fn;
267 input UnorderedMap<K, V> map;
268 output V value;
269
270 partial function UpdateFn
271 input Option<V> oldValue;
272 output V value;
273 end UpdateFn;
274 protected
275 Integer index, hash;
276 algorithm
277 225243 (index, hash) := find(key, map);
278
279
2/2
✓ Branch 0 taken 10112 times.
✓ Branch 1 taken 215131 times.
 225243 if index > 0 then
280
2/2
✓ Branch 0 taken 8340 times.
✓ Branch 1 taken 1772 times.
 20224 value := fn(SOME(Vector.getNoBounds(map.values, index)));
281 10112 Vector.updateNoBounds(map.values, index, value);
282 else
283
2/2
✓ Branch 0 taken 209398 times.
✓ Branch 1 taken 5733 times.
 215131 value := fn(NONE());
284 215131 addEntry(key, value, hash, map);
285 end if;
286 end addUpdate;
287
288 function addMerge
289 "Adds a key and associated value to the map. If the key already exists the
290 merge function is called with the new and the old value and its result is
291 stored. Unlike addUpdate this takes a plain function rather than a closure,
292 which matters on paths that add millions of entries."
293 input K key;
294 input V value;
295 input MergeFn fn;
296 input UnorderedMap<K, V> map;
297
298 partial function MergeFn
299 input V newValue;
300 input V oldValue;
301 output V value;
302 end MergeFn;
303 protected
304 Integer index, hash;
305 algorithm
306 ✗ (index, hash) := find(key, map);
307
308 ✗ if index > 0 then
309 ✗ Vector.updateNoBounds(map.values, index, fn(value, Vector.getNoBounds(map.values, index)));
310 else
311 ✗ addEntry(key, value, hash, map);
312 end if;
313 end addMerge;
314
315 function tryAddUpdate
316 "Adds a key and associated value to the map, where the value is generated by
317 calling the given function. If the key already exists the function is given
318 the old value. The generated value is returned by this function. If the key
319 does not exist nothing happens.
320
321 This function can be used to e.g. append to an existing key, value pair.
322 This is faster than trying to fetch the value,
323 updating it and then readding it, since the key only needs to be hashed
324 once."
325 input K key;
326 input UpdateFn fn;
327 input UnorderedMap<K, V> map;
328 output Boolean updated;
329
330 partial function UpdateFn
331 input Option<V> oldValue;
332 output V value;
333 end UpdateFn;
334 protected
335 Integer index, hash;
336 V value;
337 algorithm
338 38 (index, hash) := find(key, map);
339 38 updated := index > 0;
340
341
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 38 times.
 38 if updated then
342
1/2
✓ Branch 0 taken 38 times.
✗ Branch 1 not taken.
 76 value := fn(SOME(Vector.getNoBounds(map.values, index)));
343 38 Vector.updateNoBounds(map.values, index, value);
344 end if;
345 end tryAddUpdate;
346
347 function remove
348 "Removes a key from the map. Returns true if the key existed in the map and
349 was removed, or false if the key did not exist in the map. This function is
350 O(N) since it will remove the key/value from the key/value arrays.
351
352 Will not trigger a rehash, so rehash must be called manually if shrinking
353 the map is desirable (probably not a good idea unless the load factor is
354 very low, i.e. less than 0.25 or so)."
355 input K key;
356 input UnorderedMap<K, V> map;
357 output Boolean removed;
358 protected
359 Integer hash, index;
360 list<Integer> bucket;
361
362 function update_indices
363 input list<Integer> bucket;
364 input Integer removedIndex;
365 output list<Integer> outBucket;
366 algorithm
367
6/6
✓ Branch 0 taken 6697 times.
✓ Branch 1 taken 17889 times.
✓ Branch 2 taken 6697 times.
✓ Branch 3 taken 17889 times.
✓ Branch 4 taken 4252 times.
✓ Branch 5 taken 2445 times.
 24586 outBucket := list(if i > removedIndex then i-1 else i for i in bucket);
368 end update_indices;
369 algorithm
370 2077 (index, hash) := find(key, map);
371 2077 removed := index > 0;
372
373 // Key didn't exist in the map, do nothing.
374
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2077 times.
 2077 if not removed then
375 ✗ return;
376 end if;
377
378 // Remove the index from the bucket.
379
1/2
✓ Branch 1 taken 2077 times.
✗ Branch 2 not taken.
 2077 hash := intMod(hash, Vector.size(map.buckets)) + 1;
380 2077 bucket := Vector.get(map.buckets, hash);
381 2077 bucket := List.deleteMemberOnTrue(index, bucket, intEq);
382 2077 Vector.updateNoBounds(map.buckets, hash, bucket);
383
384 // Remove the key/value from the arrays.
385 2077 Vector.remove(map.keys, index);
386 2077 Vector.remove(map.hashes, index);
387 2077 Vector.remove(map.values, index);
388
389 // Update the indices in the buckets.
390 2077 Vector.apply(map.buckets, function update_indices(removedIndex = index));
391 end remove;
392
393 function clear
394 input UnorderedMap<K, V> map;
395 algorithm
396 2548 Vector.clear(map.buckets);
397 2548 Vector.push(map.buckets, {});
398 2548 Vector.clear(map.keys);
399 2548 Vector.clear(map.hashes);
400 2548 Vector.clear(map.values);
401 end clear;
402
403 function get
404 "Returns SOME(value) if the given key has an associated value in the map,
405 otherwise NONE()."
406 input K key;
407 input UnorderedMap<K, V> map;
408 output Option<V> value;
409 protected
410 Integer index = find(key, map);
411 algorithm
412
2/2
✓ Branch 0 taken 1162260 times.
✓ Branch 1 taken 1406799 times.
 2569059 value := if index > 0 then SOME(Vector.getNoBounds(map.values, index)) else NONE();
413 end get;
414
415 function getSafe
416 "Returns value if the given key has an associated value in the map,
417 otherwise fails."
418 input K key;
419 input UnorderedMap<K, V> map;
420 input SourceInfo info;
421 output V value;
422 protected
423 Integer index = find(key, map);
424 algorithm
425
1/2
✓ Branch 0 taken 112641 times.
✗ Branch 1 not taken.
 112641 if index > 0 then
426 112641 value := Vector.getNoBounds(map.values, index);
427 else
428 ✗ Error.addInternalError(getInstanceName() + " failed because the key did not exist.", info);
429 ✗ fail();
430 end if;
431 end getSafe;
432
433 function getOrFail
434 "Returns the value associated with the given key, or fails if no such value exists."
435 input K key;
436 input UnorderedMap<K, V> map;
437 output V value = Vector.get(map.values, find(key, map));
438 end getOrFail;
439
440 function getOrDefault
441 input K key;
442 input UnorderedMap<K, V> map;
443 input V default;
444 output V value;
445 protected
446 Integer index = find(key, map);
447 algorithm
448
2/2
✓ Branch 0 taken 352651 times.
✓ Branch 1 taken 1183818 times.
 1536469 value := if index > 0 then Vector.getNoBounds(map.values, index) else default;
449 end getOrDefault;
450
451 function getList
452 "Returns all values associated with the given keys, omits values for missing keys."
453 input list<K> keys;
454 input UnorderedMap<K, V> map;
455 output list<V> values = {};
456 protected
457 Integer index;
458 algorithm
459 ✗ for key in keys loop
460 ✗ index := find(key, map);
461 ✗ if index > 0 then
462 ✗ values := Vector.getNoBounds(map.values, index) :: values;
463 end if;
464 end for;
465 ✗ values := listReverseInPlace(values);
466 end getList;
467
468 function getKey
469 "Returns SOME(key) if the key exists in the map, otherwise NONE()."
470 input K key;
471 input UnorderedMap<K, V> map;
472 output Option<K> outKey;
473 protected
474 Integer index = find(key, map);
475 algorithm
476
2/2
✓ Branch 0 taken 57 times.
✓ Branch 1 taken 100 times.
 157 outKey := if index > 0 then SOME(Vector.getNoBounds(map.keys, index)) else NONE();
477 end getKey;
478
479 function updateKey
480 "Updates an existing key by replacing it with a new value.
481 This can be used to update properties of the key that does not affect its
482 hash or equivalence relation. Will fail if the key doesn't exist in the map."
483 input K key;
484 input UnorderedMap<K, V> map;
485 algorithm
486 27 Vector.update(map.keys, find(key, map), key);
487 end updateKey;
488
489 function contains
490 "Returns whether the given key exists in the map or not."
491 input K key;
492 input UnorderedMap<K, V> map;
493 output Boolean res = find(key, map) > 0;
494 end contains;
495
496 function first
497 "Returns the 'first' element in the map, or fails if the map is empty."
498 input UnorderedMap<K, V> map;
499 output V value = Vector.get(map.values, 1);
500 end first;
501
502 function firstKey
503 "Returns the 'first' key in the map, or fails if the map is empty."
504 input UnorderedMap<K, V> map;
505 output K key = Vector.get(map.keys, 1);
506 end firstKey;
507
508 function keyAt
509 input UnorderedMap<K, V> map;
510 input Integer index;
511 output K key = Vector.get(map.keys, index);
512 end keyAt;
513
514 function valueAt
515 input UnorderedMap<K, V> map;
516 input Integer index;
517 output V value = Vector.get(map.values, index);
518 end valueAt;
519
520 function toList
521 "Returns a list with the (key, value) pairs."
522 input UnorderedMap<K, V> map;
523 output list<tuple<K, V>> lst = List.zip(keyList(map), valueList(map));
524 end toList;
525
526 function keyList
527 "Returns the keys as a list."
528 input UnorderedMap<K, V> map;
529 output list<K> keys = Vector.toList(map.keys);
530 end keyList;
531
532 function valueList
533 "Returns the values as a list."
534 input UnorderedMap<K, V> map;
535 output list<V> values = Vector.toList(map.values);
536 end valueList;
537
538 function toArray
539 "Returns an array with the (key, value) pairs."
540 input UnorderedMap<K, V> map;
541 output array<tuple<K, V>> entries;
542 protected
543 Vector<K> keys = map.keys;
544 Vector<V> values = map.values;
545 tuple<K, V> t = t;
546 Integer sz = Vector.size(keys);
547 algorithm
548 1590 entries := arrayCreateNoInit(sz, t);
549
550
2/2
✓ Branch 0 taken 1204 times.
✓ Branch 1 taken 386 times.
 119780 for i in 1:sz loop
551 118190 arrayUpdateNoBoundsChecking(entries, i,
552 (Vector.getNoBounds(keys, i), Vector.getNoBounds(values, i)));
553 end for;
554 end toArray;
555
556 function keyArray
557 "Returns the keys as an array."
558 input UnorderedMap<K, V> map;
559 output array<K> keys = Vector.toArray(map.keys);
560 end keyArray;
561
562 function valueArray
563 "Returns the values as an array."
564 input UnorderedMap<K, V> map;
565 output array<V> values = Vector.toArray(map.values);
566 end valueArray;
567
568 function toVector
569 "Returns a Vector with the (key, value) pairs."
570 input UnorderedMap<K, V> map;
571 output Vector<tuple<K, V>> entries;
572 protected
573 Vector<K> keys = map.keys;
574 Vector<V> values = map.values;
575 Integer sz = Vector.size(keys);
576 type EntryT = tuple<K, V>;
577 algorithm
578 ✗ entries := Vector.new<EntryT>(sz);
579
580 ✗ for i in 1:sz loop
581 ✗ Vector.updateNoBounds(entries, i,
582 (Vector.getNoBounds(keys, i), Vector.getNoBounds(values, i)));
583 end for;
584 end toVector;
585
586 function keyVector
587 "Returns the keys as a Vector."
588 input UnorderedMap<K, V> map;
589 output Vector<K> keys = Vector.copy(map.keys);
590 end keyVector;
591
592 function valueVector
593 "Returns the values as a Vector."
594 input UnorderedMap<K, V> map;
595 output Vector<V> values = Vector.copy(map.values);
596 end valueVector;
597
598 function keySet
599 "Returns the keys as an UnorderedSet"
600 input UnorderedMap<K, V> map;
601 output UnorderedSet<K> set;
602 protected
603 Integer bucket_count = Vector.size(map.buckets);
604 array<list<K>> buckets;
605 algorithm
606 19 buckets := arrayCreate(bucket_count, {});
607
1/2
✓ Branch 0 taken 19 times.
✗ Branch 1 not taken.
 4902 for h in 1:bucket_count loop
608
4/4
✓ Branch 1 taken 24 times.
✓ Branch 2 taken 4883 times.
✓ Branch 3 taken 24 times.
✓ Branch 4 taken 4883 times.
 4907 arrayUpdateNoBoundsChecking(buckets, h,
609 list(Vector.getNoBounds(map.keys, i) for i in Vector.get(map.buckets, h)));
610 end for;
611
612 19 set := UnorderedSet.UNORDERED_SET(
613 Mutable.create(buckets),
614 Mutable.create(Vector.size(map.keys)),
615 map.hashFn,
616 map.eqFn);
617 end keySet;
618
619 function fold<FT>
620 "Folds over the values in the map."
621 input UnorderedMap<K, V> map;
622 input FoldFn fn;
623 input output FT arg;
624
625 partial function FoldFn
626 input V value;
627 input output FT arg;
628 end FoldFn;
629 algorithm
630 ✗ arg := Vector.fold(map.values, fn, arg);
631 end fold;
632
633 function map<OT>
634 "Applies a function to each value in the given map and returns a copy of the
635 map with the new values."
636 input UnorderedMap<K, V> map;
637 input MapFn fn;
638 output UnorderedMap<K, OT> outMap;
639
640 partial function MapFn
641 input V value;
642 output OT outValue;
643 end MapFn;
644 protected
645 Vector<OT> new_values;
646 algorithm
647 ✗ new_values := Vector.map(map.values, fn);
648 ✗ outMap := UNORDERED_MAP(
649 Vector.copy(map.buckets),
650 Vector.copy(map.keys),
651 Vector.copy(map.hashes),
652 new_values,
653 map.hashFn,
654 map.eqFn
655 );
656 end map;
657
658 function apply
659 "Replaces each value in the given map with the result of the given function
660 when applied to each value."
661 input UnorderedMap<K, V> map;
662 input ApplyFn fn;
663
664 partial function ApplyFn
665 input output V value;
666 end ApplyFn;
667 algorithm
668 54609 Vector.apply(map.values, fn);
669 end apply;
670
671 function merge
672 input UnorderedMap<K, V> map1;
673 input UnorderedMap<K, V> map2;
674 input SourceInfo info;
675 output UnorderedMap<K, V> result;
676 protected
677 UnorderedMap<K, V> tmp;
678 K k;
679 V v;
680 algorithm
681
2/2
✓ Branch 2 taken 182 times.
✓ Branch 3 taken 229 times.
 411 if Vector.size(map1.keys) > Vector.size(map2.keys) then
682 182 result := copy(map1);
683 tmp := map2;
684 else
685 229 result := copy(map2);
686 tmp := map1;
687 end if;
688
2/2
✓ Branch 1 taken 310 times.
✓ Branch 2 taken 101 times.
 1131 for i in 1:Vector.size(tmp.keys) loop
689 720 k := Vector.getNoBounds(tmp.keys, i);
690 720 v := Vector.getNoBounds(tmp.values, i);
691 try
692 720 addUnique(k, v, result);
693 else
694 ✗ Error.addInternalError(getInstanceName() + " failed because both maps contain the same key.", info);
695 end try;
696 end for;
697 end merge;
698
699 function subMap
700 input UnorderedMap<K, V> map;
701 input list<K> lst;
702 output UnorderedMap<K, V> sub_map;
703 protected
704 Integer len;
705 algorithm
706 980 len := listLength(lst);
707 980 sub_map := UNORDERED_MAP(
708 Vector.newFill(Util.nextPrime(len), {}),
709 Vector.new<K>(len),
710 Vector.new<Integer>(len),
711 Vector.new<V>(len),
712 map.hashFn,
713 map.eqFn
714 );
715
2/2
✓ Branch 0 taken 10590 times.
✓ Branch 1 taken 980 times.
 11570 for k in lst loop
716 10590 add(k, getSafe(k, map, sourceInfo()), sub_map);
717 end for;
718 end subMap;
719
720 function all
721 "Returns true if the given function returns true for all values in the map,
722 otherwise false."
723 input UnorderedMap<K, V> map;
724 input PredFn fn;
725 output Boolean res;
726
727 partial function PredFn
728 input V value;
729 output Boolean res;
730 end PredFn;
731 algorithm
732 96 res := Vector.all(map.values, fn);
733 end all;
734
735 function any
736 "Returns true if the given function returns true for any value in the map,
737 otherwise false."
738 input UnorderedMap<K, V> map;
739 input PredFn fn;
740 output Boolean res;
741
742 partial function PredFn
743 input V value;
744 output Boolean res;
745 end PredFn;
746 algorithm
747 ✗ res := Vector.any(map.values, fn);
748 end any;
749
750 function none
751 "Returns true if the given function returns true for none of the values in
752 the map, otherwise false."
753 input UnorderedMap<K, V> map;
754 input PredFn fn;
755 output Boolean res;
756
757 partial function PredFn
758 input V value;
759 output Boolean res;
760 end PredFn;
761 algorithm
762 203047 res := Vector.none(map.values, fn);
763 end none;
764
765 function size
766 "Returns the number of elements the map contains."
767 input UnorderedMap<K, V> map;
768 output Integer s = Vector.size(map.keys);
769 end size;
770
771 function isEmpty
772 "Returns whether the map is empty or not."
773 input UnorderedMap<K, V> map;
774 output Boolean empty = Vector.isEmpty(map.keys);
775 end isEmpty;
776
777 function bucketCount
778 "Returns the number of buckets in the map."
779 input UnorderedMap<K, V> map;
780 output Integer count = Vector.size(map.buckets);
781 end bucketCount;
782
783 function loadFactor
784 "Returns the load factor, defined as the number of entries divided by the
785 number of buckets."
786 input UnorderedMap<K, V> map;
787 output Real load = intReal(Vector.size(map.keys)) / Vector.size(map.buckets);
788 end loadFactor;
789
790 function rehash
791 "Changes the number of buckets to an appropriate number based on the number
792 of elements in the map and redistributes the keys by their stored hashes."
793 input UnorderedMap<K, V> map;
794 protected
795 Vector<Integer> hashes = map.hashes;
796 Vector<list<Integer>> buckets = map.buckets;
797 Integer bucket_count, bucket_id;
798 algorithm
799 // Clear the buckets.
800 199355 Vector.clear(buckets);
801
802 // Change the number of buckets for a load factor of about 0.5.
803 199355 bucket_count := Util.nextPrime(Vector.size(hashes) * 2);
804 199355 Vector.resize(buckets, bucket_count, {});
805
806 // Refill the buckets.
807
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 199355 times.
 1561829 for i in 1:Vector.size(hashes) loop
808
1/2
✓ Branch 1 taken 1362474 times.
✗ Branch 2 not taken.
 1362474 bucket_id := intMod(Vector.getNoBounds(hashes, i), bucket_count) + 1;
809 2724948 Vector.updateNoBounds(buckets, bucket_id, i :: Vector.getNoBounds(buckets, bucket_id));
810 end for;
811 end rehash;
812
813 function toString
814 "Returns a string representation of the map."
815 input UnorderedMap<K, V> map;
816 input KeyStringFn keyStringFn;
817 input ValueStringFn valueStringFn;
818 input String delimiter = "\n";
819 input String concatinator = ", ";
820 output String str;
821 protected
822 list<String> strl = {};
823 Vector<K> keys = map.keys;
824 Vector<V> values = map.values;
825 algorithm
826
1/2
✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
 74 for i in Vector.size(keys):-1:1 loop
827
2/4
✗ Branch 0 not taken.
✓ Branch 1 taken 56 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 56 times.
 56 strl := "(" + keyStringFn(Vector.get(keys, i)) + concatinator +
828 valueStringFn(Vector.get(values, i)) + ")" :: strl;
829 end for;
830
831 18 str := stringDelimitList(strl, delimiter);
832 end toString;
833
834 function toJSON
835 input UnorderedMap<K, V> map;
836 input KeyStringFn keyStringFn;
837 input ValueStringFn valueStringFn;
838 output String str;
839 protected
840 IOStream.IOStream io;
841 Vector<K> keys = map.keys;
842 Vector<V> values = map.values;
843 Integer sz = Vector.size(keys);
844 algorithm
845 5 io := IOStream.create("UnorderedMap.toJSON", IOStream.IOStreamType.LIST());
846 5 io := IOStream.append(io, "{\n");
847
848
1/2
✓ Branch 0 taken 5 times.
✗ Branch 1 not taken.
 5 if sz > 0 then
849 5 io := IOStream.append(io, " \"");
850
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 5 times.
 5 io := IOStream.append(io, keyStringFn(Vector.getNoBounds(keys, 1)));
851 5 io := IOStream.append(io, "\": \"");
852
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 5 times.
 5 io := IOStream.append(io, valueStringFn(Vector.getNoBounds(values, 1)));
853 5 io := IOStream.append(io, "\"");
854
855
1/2
✓ Branch 0 taken 5 times.
✗ Branch 1 not taken.
 16 for i in 2:sz loop
856 11 io := IOStream.append(io, ",\n \"");
857
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 11 times.
 11 io := IOStream.append(io, keyStringFn(Vector.getNoBounds(keys, i)));
858 11 io := IOStream.append(io, "\": \"");
859
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 11 times.
 11 io := IOStream.append(io, valueStringFn(Vector.getNoBounds(values, i)));
860 11 io := IOStream.append(io, "\"");
861 end for;
862 end if;
863
864 5 io := IOStream.append(io, "\n}");
865 5 str := IOStream.string(io);
866 end toJSON;
867
868 protected
869 function find
870 "Returns the array index of the given key (or -1 if the key isn't in the map)
871 and the key's hash."
872 input K key;
873 input UnorderedMap<K, V> map;
874 output Integer index = -1;
875 output Integer hash;
876 protected
877 Hash hashfn = map.hashFn;
878 KeyEq eqfn = map.eqFn;
879 list<Integer> bucket;
880 algorithm
881
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 14262958 times.
 14262958 hash := hashfn(key);
882
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 14262958 times.
 14262958 if Vector.size(map.buckets) > 0 then
883 28525916 bucket := Vector.get(map.buckets, intMod(hash, Vector.size(map.buckets)) + 1);
884
2/2
✓ Branch 0 taken 7579792 times.
✓ Branch 1 taken 11434316 times.
 19014108 for i in bucket loop
885
6/6
✓ Branch 1 taken 2876171 times.
✓ Branch 2 taken 4703621 times.
✓ Branch 3 taken 44 times.
✓ Branch 4 taken 2876127 times.
✓ Branch 9 taken 47529 times.
✓ Branch 10 taken 2828642 times.
 7579792 if Vector.getNoBounds(map.hashes, i) == hash and eqfn(key, Vector.getNoBounds(map.keys, i)) then
886 index := i;
887 break;
888 end if;
889 end for;
890 end if;
891 end find;
892
893 function addEntry
894 "Adds a key and value to the map given the key's hash."
895 input K key;
896 input V value;
897 input Integer hash;
898 input UnorderedMap<K, V> map;
899 protected
900 Vector<list<Integer>> buckets = map.buckets;
901 Integer bucket_id;
902 algorithm
903 // Add the key/value to the key/value arrays.
904 2983962 Vector.push(map.keys, key);
905 2983962 Vector.push(map.hashes, hash);
906 2983962 Vector.push(map.values, value);
907
908
2/2
✓ Branch 1 taken 199355 times.
✓ Branch 2 taken 2784607 times.
 2983962 if loadFactor(map) > 1 then
909 // Rehash if the load factor is too high to keep performance up. This
910 // rehashes all the keys, including the one we added above.
911 199355 rehash(map);
912 else
913 // Otherwise add the index of the key/value to the correct bucket.
914 2784607 bucket_id := intMod(hash, Vector.size(buckets)) + 1;
915 5569214 Vector.update(buckets, bucket_id, Vector.size(map.keys) :: Vector.get(buckets, bucket_id));
916 end if;
917 end addEntry;
918
919 annotation(__OpenModelica_Interface="util");
920 end UnorderedMap;
921