Linux GNU 11.4.0 Code Coverage Report

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 69.2% 63 / 0 / 91
Functions: -% 0 / 1 / 1
Branches: 46.6% 27 / 0 / 58
OMCompiler/Compiler/Util/BaseHashSet.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 package BaseHashSet
37 "
38 file: BaseHashSet.mo
39 package: BaseHashSet
40 author: Peter Aronsson (MathCore), Jens Frenkel (TU Dresden)
41 description: BaseHashSet is a generic implementation of hashsets.
42 See HashSet*.mo to see how to use it.
43
44
45 This file is an extension to OpenModelica.
46
47 Based on HashSet.mo but
48 Key = DAE.ComponentRef
49 "
50
51
52 // Below is the instance specific code. For each hashset the user must define:
53 // Key - The key used to uniquely define elements in a hashset
54 // hashFunc - A function that maps a key to a positive integer.
55 // keyEqual - A comparison function between two keys, returns true if equal.
56
57 protected import Array;
58
59 // Generic hashset code below
60
61 // adrpo: use a prime here (pick your poison):
62 // 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67
63 // 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157
64 // 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257
65 // 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367
66 // 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467
67 // 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599
68 // 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709
69 // 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829
70 // 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967
71 // 971 977 983 991 997 1013 2053 3023 4013 4999 5051 5087 24971
72 //
73 // You can also use Util.nextPrime if you know exactly how large the hash set
74 // should be.
75
76 public constant Integer lowBucketSize = 257;
77 public constant Integer avgBucketSize = 2053;
78 public constant Integer bigBucketSize = 4013;
79 public constant Integer biggerBucketSize = 25343;
80 public constant Integer hugeBucketSize = 536870879 "2^29 - 33 is prime :)";
81 public constant Integer defaultBucketSize = avgBucketSize;
82
83 public
84 replaceable type Key subtypeof Any;
85 type HashSet = tuple<HashVector, ValueArray, Integer, Integer, FuncsTuple>;
86 type HashVector = array<list<tuple<Key,Integer>>>;
87 type ValueArray = tuple<Integer,Integer,array<Option<Key>>>;
88 type FuncsTuple = tuple<FuncHash,FuncEq,FuncKeyString>;
89 partial function FuncHash input Key key; output Integer hash; end FuncHash;
90 partial function FuncEq input Key key1; input Key key2; output Boolean b; end FuncEq;
91 partial function FuncKeyString input Key key; output String str; end FuncKeyString;
92
93 public function bucketToValuesSize
94 "calculate the values array size based on the bucket size"
95 input Integer szBucket;
96 output Integer szArr;
97 algorithm
98 38114 szArr := realInt(realMul(intReal(szBucket), 0.6)); // intDiv(szBucket, 10);
99 end bucketToValuesSize;
100
101
102
103 public function emptyHashSetWork
104 input Integer szBucket;
105 input FuncsTuple fntpl;
106 output HashSet hashSet;
107 protected
108 array<list<tuple<Key,Integer>>> arr;
109 array<Option<Key>> emptyarr;
110 protected
111 Integer szArr;
112 algorithm
113 38114 arr := arrayCreate(szBucket, {});
114 38114 szArr := bucketToValuesSize(szBucket);
115 38114 emptyarr := arrayCreate(szArr, NONE());
116 38114 hashSet := (arr,(0,szArr,emptyarr),szBucket,0,fntpl);
117 end emptyHashSetWork;
118
119 public function add
120 "
121 Add a Key to hashset.
122 If the Key already exists, nothing happen.
123 "
124 input Key entry;
125 input HashSet hashSet;
126 output HashSet outHashSet;
127 algorithm
128 outHashSet := match (entry,hashSet)
129 local
130 Integer hval,indx,newpos,n,bsize;
131 tuple<Integer,Integer,array<Option<Key>>> varr;
132 list<tuple<Key,Integer>> indexes;
133 array<list<tuple<Key,Integer>>> hashvec;
134 Key key;
135 Option<Key> fkey;
136 FuncsTuple fntpl;
137 FuncHash hashFunc;
138 FuncKeyString keystrFunc;
139 String s;
140
141 // Adding when not existing previously
142 case (key,((hashvec,varr,bsize,n,fntpl as (hashFunc,_,_))))
143 algorithm
144 842959 (fkey,indx) := get1(key, hashSet);
145
3/4
✗ Branch 0 not taken.
✓ Branch 1 taken 842959 times.
✓ Branch 2 taken 789495 times.
✓ Branch 3 taken 53464 times.
 842959 if isSome(fkey) then
146 //print("adding when present, indx =" );print(intString(indx));print("\n");
147 53464 varr := valueArraySetnth(varr, indx, key);
148 else
149
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 789495 times.
 789495 indx := intMod(hashFunc(key), bsize);
150 789495 newpos := valueArrayLength(varr);
151 789495 varr := valueArrayAdd(varr, key);
152 789495 indexes := hashvec[indx + 1];
153 1578990 hashvec := arrayUpdate(hashvec, indx + 1, ((key,newpos) :: indexes));
154 789495 n := valueArrayLength(varr);
155 end if;
156 842959 then ((hashvec,varr,bsize,n,fntpl));
157
158 case (key,((_,_,bsize,_,(hashFunc,_,keystrFunc))))
159 algorithm
160 ✗ print("- BaseHashSet.add failed: ");
161 ✗ print("bsize: ");
162 ✗ print(intString(bsize));
163 ✗ print(" key: ");
164 ✗ s := keystrFunc(key);
165 ✗ print(s + " Hash: ");
166 ✗ hval := intMod(hashFunc(key),bsize);
167 ✗ print(intString(hval));
168 ✗ print("\n");
169 ✗ then
170 fail();
171 end match;
172 end add;
173
174 public function addNoUpdCheck
175 "Add a Key to hashset, without checking if it already exists.
176 This function is thus more efficient than add if you already know that the
177 Key doesn't already exist in the hashset."
178 input Key entry;
179 input HashSet hashSet;
180 output HashSet outHashSet;
181 algorithm
182 outHashSet := match (entry,hashSet)
183 local
184 Integer indx,newpos,n_1,bsize;
185 tuple<Integer,Integer,array<Option<Key>>> varr_1,varr;
186 list<tuple<Key,Integer>> indexes;
187 array<list<tuple<Key,Integer>>> hashvec_1,hashvec;
188 Key key;
189 FuncsTuple fntpl;
190 FuncHash hashFunc;
191
192 // Adding when not existing previously
193 case (key,(hashvec,varr,bsize,_,fntpl as (hashFunc,_,_)))
194 algorithm
195 ✗ indx := intMod(hashFunc(key), bsize);
196 ✗ newpos := valueArrayLength(varr);
197 ✗ varr_1 := valueArrayAdd(varr, key);
198 ✗ indexes := hashvec[indx + 1];
199 ✗ hashvec_1 := arrayUpdate(hashvec, indx + 1, ((key,newpos) :: indexes));
200 ✗ n_1 := valueArrayLength(varr_1);
201 ✗ then ((hashvec_1,varr_1,bsize,n_1,fntpl));
202 end match;
203 end addNoUpdCheck;
204
205 public function addUnique
206 "Add a Key to hashset. If the Key is already used it fails."
207 input Key key;
208 input HashSet hashSet;
209 output HashSet outHashSet;
210 algorithm
211 outHashSet := match hashSet
212 local
213 Integer indx,newpos,n_1,bsize;
214 tuple<Integer,Integer,array<Option<Key>>> varr_1,varr;
215 list<tuple<Key,Integer>> indexes;
216 array<list<tuple<Key,Integer>>> hashvec_1,hashvec;
217 FuncsTuple fntpl;
218 FuncHash hashFunc;
219
220 // Adding when not existing previously
221 case (hashvec, varr, bsize, _, fntpl as (hashFunc, _, _)) guard not has(key, hashSet)
222 algorithm
223
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1285 times.
 1285 indx := intMod(hashFunc(key), bsize);
224 1285 newpos := valueArrayLength(varr);
225 1285 varr_1 := valueArrayAdd(varr, key);
226 1285 indexes := hashvec[indx + 1];
227 2570 hashvec_1 := arrayUpdate(hashvec, indx + 1, ((key, newpos) :: indexes));
228 1285 n_1 := valueArrayLength(varr_1);
229 1285 then
230 ((hashvec_1, varr_1, bsize, n_1, fntpl));
231
232 end match;
233 end addUnique;
234
235 public function delete
236 "
237 delete the Key from the HashSet.
238 Note: This function does not delete from the index table, only from the tuple<Integer,Integer,array<Option<Key>>>.
239 This means that a lot of deletions will not make the HashSet more compact, it will still contain
240 a lot of incices information.
241 "
242 input Key key;
243 input HashSet hashSet;
244 output HashSet outHashSet;
245 protected
246 Integer indx,n,bsize;
247 tuple<Integer,Integer,array<Option<Key>>> varr_1,varr;
248 array<list<tuple<Key,Integer>>> hashvec;
249 FuncsTuple fntpl;
250 algorithm
251 4346 (hashvec,varr,bsize,n,fntpl) := hashSet;
252
2/4
✗ Branch 1 not taken.
✓ Branch 2 taken 4346 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 4346 times.
 4346 (SOME(_),indx) := get1(key, hashSet);
253 4346 varr_1 := valueArrayClearnth(varr, indx);
254 4346 outHashSet := ((hashvec,varr_1,bsize,n,fntpl));
255 end delete;
256
257 public function has
258 "Returns true if Key is in the HashSet."
259 input Key key;
260 input HashSet hashSet;
261 output Boolean b;
262 algorithm
263 b:= match hashSet
264 local
265 Option<Key> oKey;
266 // empty set containg nothing
267 case (_,(0,_,_),_,_,_)
268 then
269 false;
270 else
271 algorithm
272 864510 (oKey,_) := get1(key,hashSet);
273
3/4
✗ Branch 0 not taken.
✓ Branch 1 taken 864510 times.
✓ Branch 2 taken 420944 times.
✓ Branch 3 taken 443566 times.
 864510 then
274 isSome(oKey);
275 end match;
276 end has;
277
278 public function hasAll "Returns true if all keys are in the HashSet."
279 input list<Key> keys;
280 input HashSet hashSet;
281 output Boolean b = true;
282 algorithm
283 ✗ for key in keys loop
284 ✗ b := has(key, hashSet);
285
286 ✗ if not b then
287 ✗ return;
288 end if;
289 end for;
290 end hasAll;
291
292 public function get
293 "Returns Key from the HashSet. Returns NONE() if not present"
294 input Key key;
295 input HashSet hashSet;
296 output Option<Key> okey;
297 algorithm
298 ✗ (okey,_):= get1(key,hashSet);
299 end get;
300
301 protected function get1 "help function to get"
302 input Key key;
303 input HashSet hashSet;
304 output Option<Key> okey;
305 output Integer indx;
306 algorithm
307 (okey,indx) := match hashSet
308 local
309 Integer hashindx,bsize;
310 list<tuple<Key,Integer>> indexes;
311 array<list<tuple<Key,Integer>>> hashvec;
312 ValueArray varr;
313 Option<Key> k;
314 FuncEq keyEqual;
315 FuncHash hashFunc;
316 Boolean b;
317
318 case (hashvec,varr,bsize,_,(hashFunc,keyEqual,_))
319 algorithm
320
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1711815 times.
 1711815 hashindx := intMod(hashFunc(key), bsize);
321 1711815 indexes := hashvec[hashindx + 1];
322 1711815 (indx,b) := get2(key, indexes, keyEqual);
323
2/2
✓ Branch 0 taken 478754 times.
✓ Branch 1 taken 1233061 times.
 1711815 k := if b then valueArrayNthT(varr, indx) else NONE();
324 then
325 (k,indx);
326
327 end match;
328 end get1;
329
330 protected function get2
331 "Helper function to get"
332 input Key key;
333 input list<tuple<Key,Integer>> keyIndices;
334 input FuncEq keyEqual;
335 output Integer index = -1;
336 output Boolean found = true;
337 protected
338 Key key2;
339 algorithm
340
2/2
✓ Branch 0 taken 990923 times.
✓ Branch 1 taken 1233061 times.
 2223984 for t in keyIndices loop
341 990923 (key2,index) := t;
342
3/4
✗ Branch 0 not taken.
✓ Branch 1 taken 990923 times.
✓ Branch 4 taken 478754 times.
✓ Branch 5 taken 512169 times.
 990923 if keyEqual(key, key2) then
343 478754 return;
344 end if;
345 end for;
346 found := false;
347 end get2;
348
349 public function printHashSet ""
350 input HashSet hashSet;
351 protected
352 FuncKeyString printKey;
353 algorithm
354 ✗ (_, _, _, _, (_, _, printKey)) := hashSet;
355 ✗ print(stringDelimitList(list(printKey(e) for e in hashSetList(hashSet)), "\n"));
356 end printHashSet;
357
358 public function dumpHashSet ""
359 input HashSet hashSet;
360 algorithm
361 ✗ print("HashSet:\n");
362 ✗ printHashSet(hashSet);
363 ✗ print("\n");
364 end dumpHashSet;
365
366 public function hashSetList "returns the entries in the hashSet as a list of Key"
367 input HashSet hashSet;
368 output list<Key> lst;
369 algorithm
370 lst := match hashSet
371 local
372 ValueArray varr;
373 case (_,varr,_,_,_)
374 24724 then
375 valueArrayList(varr);
376 end match;
377 end hashSetList;
378
379 public function valueArrayList
380 "Transforms a ValueArray to a Key list"
381 input ValueArray inValueArray;
382 output list<Key> outList = {};
383 protected
384 array<Option<Key>> arr;
385 Integer size;
386 Key e;
387 algorithm
388 24724 (size, _, arr) := inValueArray;
389
390
2/2
✓ Branch 0 taken 18591 times.
✓ Branch 1 taken 6133 times.
 141161 for i in 1:size loop
391
3/4
✗ Branch 1 not taken.
✓ Branch 2 taken 116437 times.
✓ Branch 3 taken 116429 times.
✓ Branch 4 taken 8 times.
 116437 if isSome(arr[i]) then
392 116429 SOME(e) := arr[i];
393 outList := e :: outList;
394 end if;
395 end for;
396
397 24724 outList := listReverse(outList);
398 end valueArrayList;
399
400 public function currentSize
401 "Returns the number of elements inserted into the table"
402 input HashSet hashSet;
403 output Integer sz;
404 protected
405 ValueArray va;
406 algorithm
407 21460 (_,va,_,_,_) := hashSet;
408 21460 sz := valueArrayLength(va);
409 end currentSize;
410
411 public function valueArrayLength
412 "Returns the number of elements in the ValueArray"
413 input ValueArray valueArray;
414 output Integer sz;
415 algorithm
416 1603020 (sz,_,_) := valueArray;
417 end valueArrayLength;
418
419 public function valueArrayAdd
420 "Adds an entry last to the ValueArray, increasing array size if no space left
421 by factor 1.4"
422 input ValueArray valueArray;
423 input Key entry;
424 output ValueArray outValueArray;
425 protected
426 Integer n,size,expandsize,expandsize_1;
427 array<Option<Key>> arr;
428 Real rsize,rexpandsize;
429 algorithm
430 790780 (n,size,arr) := valueArray;
431
2/2
✓ Branch 0 taken 3748 times.
✓ Branch 1 taken 787032 times.
 790780 if n >= size then
432 3748 rsize := intReal(size);
433 3748 rexpandsize := rsize * 0.4;
434 3748 expandsize := realInt(rexpandsize);
435 expandsize_1 := intMax(expandsize, 1);
436 3748 size := expandsize_1 + size;
437 3748 arr := Array.expand(expandsize_1, arr, NONE());
438 end if;
439 790780 arr := arrayUpdate(arr, n + 1, SOME(entry));
440 790780 outValueArray := (n+1,size,arr);
441 end valueArrayAdd;
442
443 public function valueArraySetnth
444 "Set the n:th variable in the ValueArray to value."
445 input ValueArray valueArray;
446 input Integer pos;
447 input Key entry;
448 output ValueArray outValueArray;
449 protected
450 array<Option<Key>> arr_1,arr;
451 Integer n,size;
452 algorithm
453 53464 (n,size,arr) := valueArray;
454
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 53464 times.
 53464 true := (pos < size);
455 53464 arr_1 := arrayUpdate(arr, pos + 1, SOME(entry));
456 53464 outValueArray := (n,size,arr_1);
457 end valueArraySetnth;
458
459 public function valueArrayClearnth
460 "Clears the n:th variable in the ValueArray (set to NONE())."
461 input ValueArray valueArray;
462 input Integer pos;
463 output ValueArray outValueArray;
464 protected
465 array<Option<Key>> arr_1,arr;
466 Integer n,size;
467 algorithm
468 4346 (n,size,arr) := valueArray;
469
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4346 times.
 4346 true := (pos < size);
470 4346 arr_1 := arrayUpdate(arr, pos + 1,NONE());
471 4346 outValueArray := ((n,size,arr_1));
472 end valueArrayClearnth;
473
474 public function valueArrayNth
475 "Retrieve the n:th Value from ValueArray, index from 0..n-1."
476 input ValueArray valueArray;
477 input Integer pos;
478 output Key key;
479 algorithm
480 key := match valueArray
481 local
482 Key k;
483 Integer n;
484 array<Option<Key>> arr;
485 case (n,_,arr) guard pos <= n // should be pos<n
486 algorithm
487 ✗ SOME(k) := arr[pos + 1];
488 then k;
489 end match;
490 end valueArrayNth;
491
492 protected function valueArrayNthT
493 "Retrieve the n:th Value from ValueArray, index from 0..n-1."
494 input ValueArray valueArray;
495 input Integer pos;
496 output Option<Key> key;
497 algorithm
498 key := match valueArray
499 local
500 Integer n;
501 array<Option<Key>> arr;
502 case (n,_,arr) guard pos <= n // should be pos<n
503 478754 then arr[pos + 1];
504 end match;
505 end valueArrayNthT;
506
507 annotation(__OpenModelica_Interface="util");
508 end BaseHashSet;
509