OMCompiler/Compiler/Util/BaseHashTable.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 BaseHashTable | ||
| 37 | " | ||
| 38 | file: BaseHashTable.mo | ||
| 39 | package: BaseHashTable | ||
| 40 | author: Peter Aronsson (MathCore) | ||
| 41 | description: BaseHashTable is a generic implementation of hashtables. | ||
| 42 | See HashTable*.mo to see how to use it. | ||
| 43 | |||
| 44 | |||
| 45 | This file is an extension to OpenModelica. | ||
| 46 | |||
| 47 | Based on HashTable.mo but | ||
| 48 | Key = DAE.ComponentRef | ||
| 49 | Value = DAE.Exp" | ||
| 50 | |||
| 51 | |||
| 52 | // Below is the instance specific code. For each hashtable the user must define: | ||
| 53 | // Key - The key used to uniquely define elements in a hashtable | ||
| 54 | // Value - The data to associate with each key | ||
| 55 | // hashFunc - A function that maps a key to a positive integer. | ||
| 56 | // keyEqual - A comparison function between two keys, returns true if equal. | ||
| 57 | |||
| 58 | protected | ||
| 59 | import Array; | ||
| 60 | import List; | ||
| 61 | |||
| 62 | // Generic hashtable code below | ||
| 63 | |||
| 64 | // adrpo: use a prime here (pick your poison): | ||
| 65 | // 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 | ||
| 66 | // 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 | ||
| 67 | // 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 | ||
| 68 | // 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 | ||
| 69 | // 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 | ||
| 70 | // 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 | ||
| 71 | // 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 | ||
| 72 | // 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 | ||
| 73 | // 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 | ||
| 74 | // 971 977 983 991 997 1013 2053 3023 4013 4999 5051 5087 24971 | ||
| 75 | // | ||
| 76 | // You can also use Util.nextPrime if you know exactly how large the hash table | ||
| 77 | // should be. | ||
| 78 | |||
| 79 | public constant Integer lowBucketSize = 257; | ||
| 80 | public constant Integer avgBucketSize = 2053; | ||
| 81 | public constant Integer bigBucketSize = 4013; | ||
| 82 | public constant Integer biggerBucketSize = 25343; | ||
| 83 | public constant Integer hugeBucketSize = 536870879 "2^29 - 33 is prime :)"; | ||
| 84 | public constant Integer defaultBucketSize = avgBucketSize; | ||
| 85 | |||
| 86 | public | ||
| 87 | replaceable type Key subtypeof Any; | ||
| 88 | replaceable type Value subtypeof Any; | ||
| 89 | |||
| 90 | type HashEntry = tuple<Key, Value>; | ||
| 91 | type HashNode = list<tuple<Key, Integer>>; | ||
| 92 | type HashTable = tuple<HashVector, ValueArray, Integer, FuncsTuple>; | ||
| 93 | type HashVector = array<HashNode>; | ||
| 94 | type ValueArray = tuple<Integer, Integer, array<Option<HashEntry>>>; | ||
| 95 | type FuncsTuple = tuple<FuncHash, FuncEq, FuncKeyString, FuncValString>; | ||
| 96 | |||
| 97 | partial function FuncHash input Key key; output Integer hash; end FuncHash; | ||
| 98 | partial function FuncEq input Key key1; input Key key2; output Boolean b; end FuncEq; | ||
| 99 | partial function FuncKeyString input Key key; output String str; end FuncKeyString; | ||
| 100 | partial function FuncValString input Value val; output String str; end FuncValString; | ||
| 101 | |||
| 102 | public function bucketToValuesSize | ||
| 103 | "calculate the values array size based on the bucket size" | ||
| 104 | input Integer szBucket; | ||
| 105 | output Integer szArr; | ||
| 106 | algorithm | ||
| 107 | 407311 | szArr := realInt(realMul(intReal(szBucket), 0.6)); // intDiv(szBucket, 10); | |
| 108 | end bucketToValuesSize; | ||
| 109 | |||
| 110 | public function emptyHashTableWork | ||
| 111 | input Integer szBucket; | ||
| 112 | input FuncsTuple fntpl; | ||
| 113 | output HashTable hashTable; | ||
| 114 | protected | ||
| 115 | array<list<tuple<Key,Integer>>> arr; | ||
| 116 | array<Option<tuple<Key,Value>>> emptyarr; | ||
| 117 | protected | ||
| 118 | Integer szArr, szBucketFixed = intMax(szBucket, 1); | ||
| 119 | algorithm | ||
| 120 | 407311 | arr := arrayCreate(szBucketFixed, {}); | |
| 121 | 407311 | szArr := bucketToValuesSize(szBucketFixed); | |
| 122 | 407311 | emptyarr := arrayCreate(szArr, NONE()); | |
| 123 | 407311 | hashTable := (arr,(0,szArr,emptyarr),szBucketFixed,fntpl); | |
| 124 | end emptyHashTableWork; | ||
| 125 | |||
| 126 | public function add | ||
| 127 | "Add a Key-Value tuple to hashtable. | ||
| 128 | If the Key-Value tuple already exists, the function updates the Value." | ||
| 129 | input HashEntry entry; | ||
| 130 | input HashTable hashTable; | ||
| 131 | output HashTable outHashTable; | ||
| 132 | protected | ||
| 133 | HashVector hashvec; | ||
| 134 | ValueArray varr; | ||
| 135 | Integer bsize, hash_idx, arr_idx, new_pos; | ||
| 136 | FuncsTuple fntpl; | ||
| 137 | FuncHash hashFunc; | ||
| 138 | FuncEq keyEqual; | ||
| 139 | Key key, key2; | ||
| 140 | HashNode indices; | ||
| 141 | algorithm | ||
| 142 | 3222370 | (key, _) := entry; | |
| 143 | 3222370 | (hashvec, varr, bsize, fntpl as (hashFunc, keyEqual, _, _)) := hashTable; | |
| 144 | |||
| 145 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 3222370 times.
|
3222370 | hash_idx := intMod(hashFunc(key), bsize) + 1; |
| 146 | 3222370 | indices := hashvec[hash_idx]; | |
| 147 | |||
| 148 |
2/2✓ Branch 0 taken 1560518 times.
✓ Branch 1 taken 2381529 times.
|
3942047 | for i in indices loop |
| 149 | 1560518 | (key2, _) := i; | |
| 150 | |||
| 151 |
3/4✗ Branch 0 not taken.
✓ Branch 1 taken 1560518 times.
✓ Branch 4 taken 840841 times.
✓ Branch 5 taken 719677 times.
|
1560518 | if keyEqual(key, key2) then |
| 152 | 840841 | (_, arr_idx) := i; | |
| 153 | 840841 | valueArraySet(varr, arr_idx, entry); | |
| 154 | outHashTable := hashTable; | ||
| 155 | 840841 | return; | |
| 156 | end if; | ||
| 157 | end for; | ||
| 158 | |||
| 159 | 2381529 | (varr, new_pos) := valueArrayAdd(varr, entry); | |
| 160 | 4763058 | arrayUpdate(hashvec, hash_idx, ((key, new_pos)) :: indices); | |
| 161 | 2381529 | outHashTable := (hashvec, varr, bsize, fntpl); | |
| 162 | end add; | ||
| 163 | |||
| 164 | public function dumpHashTableStatistics " | ||
| 165 | author: PA. | ||
| 166 | dump statistics on how many entries per hash value. Useful to see how hash function behaves" | ||
| 167 | input HashTable hashTable; | ||
| 168 | algorithm | ||
| 169 | () := match hashTable | ||
| 170 | local HashVector hvec; | ||
| 171 | case (hvec,_,_,_) algorithm | ||
| 172 | ✗ | print("index list lengths:\n"); | |
| 173 | ✗ | print(stringDelimitList(list(intString(listLength(l)) for l in hvec),",")); | |
| 174 | ✗ | print("\n"); | |
| 175 | ✗ | print("non-zero: " + String(sum(1 for l guard not listEmpty(l) in hvec)) + "/" + String(arrayLength(hvec)) +"\n"); | |
| 176 | ✗ | print("max element: " + String(max(listLength(l) for l in hvec)) + "\n"); | |
| 177 | ✗ | print("total entries: " + String(sum(listLength(l) for l in hvec)) + "\n"); | |
| 178 | then (); | ||
| 179 | end match; | ||
| 180 | end dumpHashTableStatistics; | ||
| 181 | |||
| 182 | public function addNoUpdCheck | ||
| 183 | "Add a Key-Value tuple to hashtable, without checking if it already exists. | ||
| 184 | This function is thus more efficient than add if you already know that the | ||
| 185 | Key-Value tuple doesn't already exist in the hashtable." | ||
| 186 | input HashEntry entry; | ||
| 187 | input HashTable hashTable; | ||
| 188 | output HashTable outHashTable; | ||
| 189 | algorithm | ||
| 190 | outHashTable := match (entry, hashTable) | ||
| 191 | local | ||
| 192 | Integer indx, newpos, bsize; | ||
| 193 | ValueArray varr; | ||
| 194 | HashNode indexes; | ||
| 195 | HashVector hashvec; | ||
| 196 | tuple<Key,Value> v; | ||
| 197 | Key key; | ||
| 198 | FuncsTuple fntpl; | ||
| 199 | FuncHash hashFunc; | ||
| 200 | |||
| 201 | // Adding when not existing previously | ||
| 202 | case ((v as (key, _)), | ||
| 203 | (hashvec, varr, bsize, fntpl as (hashFunc, _, _, _))) | ||
| 204 | algorithm | ||
| 205 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 19 times.
|
19 | indx := intMod(hashFunc(key), bsize)+1; |
| 206 | 19 | (varr,newpos) := valueArrayAdd(varr, v); | |
| 207 | 19 | indexes := hashvec[indx]; | |
| 208 | 38 | hashvec := arrayUpdate(hashvec, indx, ((key, newpos) :: indexes)); | |
| 209 | 19 | then | |
| 210 | ((hashvec, varr, bsize, fntpl)); | ||
| 211 | |||
| 212 | end match; | ||
| 213 | end addNoUpdCheck; | ||
| 214 | |||
| 215 | public function addUnique | ||
| 216 | "Add a Key-Value tuple to hashtable. If the Key is already used it fails." | ||
| 217 | input HashEntry entry; | ||
| 218 | input HashTable hashTable; | ||
| 219 | output HashTable outHashTable; | ||
| 220 | protected | ||
| 221 | Integer indx, newpos, bsize; | ||
| 222 | ValueArray varr; | ||
| 223 | HashNode indexes; | ||
| 224 | HashVector hashvec; | ||
| 225 | Key key; | ||
| 226 | FuncsTuple fntpl; | ||
| 227 | FuncHash hashFunc; | ||
| 228 | algorithm | ||
| 229 | // Adding when not existing previously | ||
| 230 | 18 | (key, _) := entry; | |
| 231 | 18 | (hashvec, varr, bsize, fntpl as (hashFunc, _, _, _)) := hashTable; | |
| 232 |
2/2✓ Branch 0 taken 18 times.
✓ Branch 1 taken 18 times.
|
36 | failure(get(key, hashTable)); |
| 233 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 18 times.
|
18 | indx := intMod(hashFunc(key), bsize)+1; |
| 234 | 18 | (varr, newpos) := valueArrayAdd(varr, entry); | |
| 235 | 18 | indexes := hashvec[indx]; | |
| 236 | 36 | hashvec := arrayUpdate(hashvec, indx, ((key, newpos) :: indexes)); | |
| 237 | 18 | outHashTable := (hashvec, varr, bsize, fntpl); | |
| 238 | end addUnique; | ||
| 239 | |||
| 240 | public function update | ||
| 241 | "Updates an already existing value in the hashtable. Fails if the entry does | ||
| 242 | not exist." | ||
| 243 | input HashEntry entry; | ||
| 244 | input HashTable hashTable; | ||
| 245 | protected | ||
| 246 | ValueArray varr; | ||
| 247 | Integer index; | ||
| 248 | Key key; | ||
| 249 | algorithm | ||
| 250 | 18 | (key, _) := entry; | |
| 251 | 18 | (_, varr, _, _) := hashTable; | |
| 252 | 18 | index := hasKeyIndex(key, hashTable); | |
| 253 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 18 times.
|
18 | true := valueArrayKeyIndexExists(varr, index); |
| 254 | 18 | valueArraySet(varr, index, entry); | |
| 255 | end update; | ||
| 256 | |||
| 257 | public function delete | ||
| 258 | "Deletes the Value associatied with Key from the HashTable. | ||
| 259 | Note: This function does not delete from the index table, only from the | ||
| 260 | ValueArray. This means that a lot of deletions will not make the HashTable | ||
| 261 | more compact, it will still contain a lot of incices information." | ||
| 262 | input Key key; | ||
| 263 | input HashTable hashTable; | ||
| 264 | protected | ||
| 265 | Integer indx; | ||
| 266 | ValueArray varr; | ||
| 267 | algorithm | ||
| 268 | ✗ | indx := hasKeyIndex(key, hashTable); | |
| 269 | ✗ | (_, varr, _, _) := hashTable; | |
| 270 | ✗ | if not valueArrayKeyIndexExists(varr, indx) then | |
| 271 | ✗ | print("BaseHashTable.delete failed\n"); | |
| 272 | ✗ | fail(); | |
| 273 | end if; | ||
| 274 | ✗ | valueArrayClear(varr, indx); | |
| 275 | end delete; | ||
| 276 | |||
| 277 | public function hasKey "checks if the given key is in the hashTable" | ||
| 278 | input Key key; | ||
| 279 | input HashTable hashTable; | ||
| 280 | output Boolean b; | ||
| 281 | protected | ||
| 282 | ValueArray varr; | ||
| 283 | algorithm | ||
| 284 | 4268256 | (_, varr, _, _) := hashTable; | |
| 285 | 4268256 | b := valueArrayKeyIndexExists(varr, hasKeyIndex(key, hashTable)); | |
| 286 | end hasKey; | ||
| 287 | |||
| 288 | public function anyKeyInHashTable "Returns true if any of the keys are present in the hashtable. Stops and returns true upon first occurence" | ||
| 289 | input list<Key> keys; | ||
| 290 | input HashTable ht; | ||
| 291 | output Boolean res; | ||
| 292 | algorithm | ||
| 293 | ✗ | for key in keys loop | |
| 294 | ✗ | if hasKey(key, ht) then | |
| 295 | res := true; | ||
| 296 | ✗ | return; | |
| 297 | end if; | ||
| 298 | end for; | ||
| 299 | res := false; | ||
| 300 | end anyKeyInHashTable; | ||
| 301 | |||
| 302 | public function get | ||
| 303 | "Returns a Value given a Key and a HashTable." | ||
| 304 | input Key key; | ||
| 305 | input HashTable hashTable; | ||
| 306 | output Value value; | ||
| 307 | protected | ||
| 308 | Integer i; | ||
| 309 | ValueArray varr; | ||
| 310 | algorithm | ||
| 311 | 7831776 | i := hasKeyIndex(key, hashTable); | |
| 312 |
2/2✓ Branch 0 taken 2000389 times.
✓ Branch 1 taken 5831387 times.
|
7831776 | false := i == -1; |
| 313 | 5831387 | (_, varr, _, _) := hashTable; | |
| 314 | 5831387 | (_, value) := getValueArray(varr, i); | |
| 315 | end get; | ||
| 316 | |||
| 317 | public function getOrDefault | ||
| 318 | "Returns a Value given a Key and a HashTable if it exists, | ||
| 319 | otherwise returns the default value." | ||
| 320 | input Key key; | ||
| 321 | input HashTable hashTable; | ||
| 322 | input Value default; | ||
| 323 | output Value value; | ||
| 324 | algorithm | ||
| 325 | ✗ | value := if hasKey(key, hashTable) then get(key, hashTable) else default; | |
| 326 | end getOrDefault; | ||
| 327 | |||
| 328 | protected function hasKeyIndex | ||
| 329 | "help function to get and hasKey" | ||
| 330 | input Key key; | ||
| 331 | input HashTable hashTable; | ||
| 332 | output Integer indx; | ||
| 333 | protected | ||
| 334 | Integer hashindx, bsize; | ||
| 335 | HashNode indexes; | ||
| 336 | HashVector hashvec; | ||
| 337 | FuncEq keyEqual; | ||
| 338 | FuncHash hashFunc; | ||
| 339 | algorithm | ||
| 340 | 12100050 | (hashvec, _, bsize, (hashFunc, keyEqual, _, _)) := hashTable; | |
| 341 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 12100050 times.
|
12100050 | hashindx := intMod(hashFunc(key), bsize) + 1; |
| 342 | 12100050 | indexes := hashvec[hashindx]; | |
| 343 | 12100050 | indx := hasKeyIndex2(key, indexes, keyEqual); | |
| 344 | end hasKeyIndex; | ||
| 345 | |||
| 346 | protected function hasKeyIndex2 | ||
| 347 | "Helper function to get" | ||
| 348 | input Key key; | ||
| 349 | input HashNode keyIndices; | ||
| 350 | input FuncEq keyEqual; | ||
| 351 | output Integer index "Returns -1 on failure"; | ||
| 352 | protected | ||
| 353 | Key key2; | ||
| 354 | algorithm | ||
| 355 |
2/2✓ Branch 0 taken 13942230 times.
✓ Branch 1 taken 3159782 times.
|
17102012 | for keyIndex in keyIndices loop |
| 356 | 13942230 | (key2, index) := keyIndex; | |
| 357 |
3/4✗ Branch 0 not taken.
✓ Branch 1 taken 13942230 times.
✓ Branch 4 taken 8940268 times.
✓ Branch 5 taken 5001962 times.
|
13942230 | if keyEqual(key, key2) then |
| 358 | 8940268 | return; | |
| 359 | end if; | ||
| 360 | end for; | ||
| 361 | index := -1 "Mark the failure so we can do hasKey without matchcontinue"; | ||
| 362 | end hasKeyIndex2; | ||
| 363 | |||
| 364 | public function dumpHashTable | ||
| 365 | input HashTable t; | ||
| 366 | protected | ||
| 367 | FuncKeyString printKey; | ||
| 368 | FuncValString printValue; | ||
| 369 | Key k; | ||
| 370 | Value v; | ||
| 371 | algorithm | ||
| 372 | 10 | (_, _, _, (_, _, printKey, printValue)) := t; | |
| 373 | 10 | print("HashTable:\n"); | |
| 374 | |||
| 375 |
2/2✓ Branch 1 taken 49 times.
✓ Branch 2 taken 10 times.
|
59 | for entry in hashTableList(t) loop |
| 376 | 49 | (k, v) := entry; | |
| 377 | 49 | print("{"); | |
| 378 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 49 times.
|
49 | print(printKey(k)); |
| 379 | 49 | print(",{"); | |
| 380 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 49 times.
|
49 | print(printValue(v)); |
| 381 | 49 | print("}}\n"); | |
| 382 | end for; | ||
| 383 | end dumpHashTable; | ||
| 384 | |||
| 385 | |||
| 386 | public function debugDump | ||
| 387 | input HashTable ht; | ||
| 388 | protected | ||
| 389 | FuncKeyString printKey; | ||
| 390 | FuncValString printValue; | ||
| 391 | Key k; | ||
| 392 | |||
| 393 | Integer n, size, i, j, szBucket; | ||
| 394 | array<Option<HashEntry>> arr; | ||
| 395 | HashEntry he; | ||
| 396 | array<HashNode> hashVector; | ||
| 397 | algorithm | ||
| 398 | ✗ | (hashVector, (n, size, arr), szBucket, (_, _, printKey, printValue)) := ht; | |
| 399 | ✗ | print("Debug HashTable:\n"); | |
| 400 | ✗ | print("szBucket: " + intString(szBucket) + "\n"); | |
| 401 | |||
| 402 | ✗ | print("Debug ValueArray:\n"); | |
| 403 | ✗ | print("number of entires: " + intString(n) + "\n"); | |
| 404 | ✗ | print("size: " + intString(size) + "\n"); | |
| 405 | i := 0; | ||
| 406 | ✗ | for entry in arr loop | |
| 407 | ✗ | i := i+1; | |
| 408 | ✗ | if isSome(entry) then | |
| 409 | ✗ | SOME(he) := entry; | |
| 410 | ✗ | print(intString(i) + ": " + dumpTuple(he, printKey, printValue) + "\n"); | |
| 411 | end if; | ||
| 412 | end for; | ||
| 413 | |||
| 414 | ✗ | print("Debug HashVector:\n"); | |
| 415 | i := 0; | ||
| 416 | ✗ | for node in hashVector loop | |
| 417 | ✗ | i := i+1; | |
| 418 | ✗ | if not listEmpty(node) then | |
| 419 | ✗ | print(intString(i) + ":"); | |
| 420 | ✗ | for n in node loop | |
| 421 | ✗ | (k, j) := n; | |
| 422 | ✗ | print(" {" + printKey(k) + ", " + intString(j) + "}"); | |
| 423 | end for; | ||
| 424 | ✗ | print("\n"); | |
| 425 | end if; | ||
| 426 | end for; | ||
| 427 | end debugDump; | ||
| 428 | |||
| 429 | protected function dumpTuple | ||
| 430 | input HashEntry tpl; | ||
| 431 | input FuncKeyString printKey; | ||
| 432 | input FuncValString printValue; | ||
| 433 | output String str; | ||
| 434 | protected | ||
| 435 | Key k; | ||
| 436 | Value v; | ||
| 437 | String sk, sv; | ||
| 438 | algorithm | ||
| 439 | ✗ | (k, v) := tpl; | |
| 440 | ✗ | sk := printKey(k); | |
| 441 | ✗ | sv := printValue(v); | |
| 442 | ✗ | str := stringAppendList({"{", sk, ",{", sv, "}}"}); | |
| 443 | end dumpTuple; | ||
| 444 | |||
| 445 | public function hashTableValueList | ||
| 446 | "Returns the Value entries as a list of Values." | ||
| 447 | input HashTable hashTable; | ||
| 448 | output list<Value> valLst; | ||
| 449 | algorithm | ||
| 450 | 2436 | valLst := List.unzipSecond(hashTableList(hashTable)); | |
| 451 | end hashTableValueList; | ||
| 452 | |||
| 453 | public function hashTableKeyList | ||
| 454 | "Returns the Key entries as a list of Keys." | ||
| 455 | input HashTable hashTable; | ||
| 456 | output list<Key> valLst; | ||
| 457 | algorithm | ||
| 458 | 1909 | valLst := List.unzip(hashTableList(hashTable)); | |
| 459 | end hashTableKeyList; | ||
| 460 | |||
| 461 | public function hashTableList | ||
| 462 | "Returns the entries in the hashTable as a list of HashEntries." | ||
| 463 | input HashTable hashTable; | ||
| 464 | output list<HashEntry> outEntries; | ||
| 465 | protected | ||
| 466 | ValueArray varr; | ||
| 467 | algorithm | ||
| 468 | 4528 | (_, varr, _, _) := hashTable; | |
| 469 | 4528 | outEntries := valueArrayList(varr); | |
| 470 | end hashTableList; | ||
| 471 | |||
| 472 | public function hashTableListReversed | ||
| 473 | "Returns the entries in the hashTable as a list of HashEntries, in reverse | ||
| 474 | order." | ||
| 475 | input HashTable hashTable; | ||
| 476 | output list<HashEntry> entries; | ||
| 477 | protected | ||
| 478 | ValueArray varr; | ||
| 479 | algorithm | ||
| 480 | ✗ | (_, varr, _, _) := hashTable; | |
| 481 | ✗ | entries := valueArrayListReversed(varr); | |
| 482 | end hashTableListReversed; | ||
| 483 | |||
| 484 | public function valueArrayList | ||
| 485 | "Transforms a ValueArray to a HashEntry list." | ||
| 486 | input ValueArray valueArray; | ||
| 487 | output list<HashEntry> outEntries; | ||
| 488 | protected | ||
| 489 | array<Option<HashEntry>> arr; | ||
| 490 | algorithm | ||
| 491 | 4528 | (_, _, arr) := valueArray; | |
| 492 | 4528 | outEntries := Array.fold(arr, List.consOption, {}); | |
| 493 | 4528 | outEntries := listReverse(outEntries); | |
| 494 | end valueArrayList; | ||
| 495 | |||
| 496 | public function valueArrayListReversed | ||
| 497 | "Transforms a ValueArray to a HashEntry list, in reverse order compared to | ||
| 498 | valueArrayList." | ||
| 499 | input ValueArray valueArray; | ||
| 500 | output list<HashEntry> entries; | ||
| 501 | protected | ||
| 502 | array<Option<HashEntry>> arr; | ||
| 503 | algorithm | ||
| 504 | ✗ | (_, _, arr) := valueArray; | |
| 505 | ✗ | entries := Array.fold(arr, List.consOption, {}); | |
| 506 | end valueArrayListReversed; | ||
| 507 | |||
| 508 | public function hashTableCurrentSize | ||
| 509 | "Returns the number of elements inserted into the table" | ||
| 510 | input HashTable hashTable; | ||
| 511 | output Integer sz; | ||
| 512 | protected | ||
| 513 | ValueArray va; | ||
| 514 | algorithm | ||
| 515 | 170378 | (_, va, _, _) := hashTable; | |
| 516 | 170378 | sz := valueArrayLength(va); | |
| 517 | end hashTableCurrentSize; | ||
| 518 | |||
| 519 | public function valueArrayLength | ||
| 520 | "Returns the number of elements in the ValueArray" | ||
| 521 | input ValueArray valueArray; | ||
| 522 | output Integer sz; | ||
| 523 | algorithm | ||
| 524 | 170378 | (sz, _, _) := valueArray; | |
| 525 | end valueArrayLength; | ||
| 526 | |||
| 527 | protected | ||
| 528 | |||
| 529 | function valueArrayAdd | ||
| 530 | "Adds an entry last to the ValueArray, increasing array size if no space left | ||
| 531 | by factor 1.4" | ||
| 532 | input ValueArray valueArray; | ||
| 533 | input HashEntry entry; | ||
| 534 | output ValueArray outValueArray; | ||
| 535 | output Integer newpos; | ||
| 536 | protected | ||
| 537 | Integer n,size,expandsize,expandsize_1; | ||
| 538 | array<Option<HashEntry>> arr; | ||
| 539 | Real rsize,rexpandsize; | ||
| 540 | algorithm | ||
| 541 | 2381566 | (n,size,arr) := valueArray; | |
| 542 |
2/2✓ Branch 0 taken 20715 times.
✓ Branch 1 taken 2360851 times.
|
2381566 | if n >= size then |
| 543 | 20715 | rsize := intReal(size); | |
| 544 | 20715 | rexpandsize := rsize * 0.4; | |
| 545 | 20715 | expandsize := realInt(rexpandsize); | |
| 546 | expandsize_1 := intMax(expandsize, 1); | ||
| 547 | 20715 | size := expandsize_1 + size; | |
| 548 | 20715 | arr := Array.expand(expandsize_1, arr, NONE()); | |
| 549 | end if; | ||
| 550 | 2381566 | arr := arrayUpdate(arr, n + 1, SOME(entry)); | |
| 551 | 2381566 | outValueArray := (n+1,size,arr); | |
| 552 | newpos := n + 1; | ||
| 553 | end valueArrayAdd; | ||
| 554 | |||
| 555 | function valueArraySet | ||
| 556 | "Set the n:th variable in the ValueArray to value." | ||
| 557 | input ValueArray valueArray; | ||
| 558 | input Integer pos; | ||
| 559 | input HashEntry entry; | ||
| 560 | output ValueArray outValueArray; | ||
| 561 | algorithm | ||
| 562 | outValueArray := match valueArray | ||
| 563 | local | ||
| 564 | array<Option<HashEntry>> arr; | ||
| 565 | Integer n, size; | ||
| 566 | |||
| 567 | case (n, size, arr) | ||
| 568 | algorithm | ||
| 569 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 840859 times.
|
840859 | true := pos <= size; |
| 570 | 840859 | arr := arrayUpdate(arr, pos, SOME(entry)); | |
| 571 | 840859 | then | |
| 572 | ((n, size, arr)); | ||
| 573 | end match; | ||
| 574 | end valueArraySet; | ||
| 575 | |||
| 576 | function valueArrayClear | ||
| 577 | "Clears the n:th variable in the ValueArray (set to NONE())." | ||
| 578 | input ValueArray valueArray; | ||
| 579 | input Integer pos; | ||
| 580 | protected | ||
| 581 | array<Option<HashEntry>> arr; | ||
| 582 | Integer size; | ||
| 583 | algorithm | ||
| 584 | ✗ | (_, size, arr) := valueArray; | |
| 585 | ✗ | true := pos <= size; // TODO: Needed? arrayUpdate checks bounds and we should more reasonably check n? | |
| 586 | ✗ | arrayUpdate(arr, pos,NONE()); | |
| 587 | end valueArrayClear; | ||
| 588 | |||
| 589 | protected | ||
| 590 | function getValueArray | ||
| 591 | "Retrieve the n:th Value from ValueArray, index from 1..n." | ||
| 592 | input ValueArray valueArray; | ||
| 593 | input Integer pos; | ||
| 594 | output Key key; | ||
| 595 | output Value value; | ||
| 596 | protected | ||
| 597 | array<Option<HashEntry>> arr; | ||
| 598 | Integer n; | ||
| 599 | algorithm | ||
| 600 | 5831387 | (n, _, arr) := valueArray; | |
| 601 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 5831387 times.
|
5831387 | true := pos <= n; // In case the user sends in higher values and we did not clear the array properly? |
| 602 |
3/6✗ Branch 1 not taken.
✓ Branch 2 taken 5831387 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 5831387 times.
✓ Branch 6 taken 5831387 times.
✗ Branch 7 not taken.
|
5831387 | SOME((key,value)) := arrayGet(arr, pos); |
| 603 | end getValueArray; | ||
| 604 | |||
| 605 | function valueArrayKeyIndexExists | ||
| 606 | "Checks if the given index exists in the value array" | ||
| 607 | input ValueArray valueArray; | ||
| 608 | input Integer pos; | ||
| 609 | output Boolean b; | ||
| 610 | algorithm | ||
| 611 | b := match (valueArray, pos) | ||
| 612 | local | ||
| 613 | Integer n; | ||
| 614 | array<Option<HashEntry>> arr; | ||
| 615 | |||
| 616 | case (_, -1) then false; | ||
| 617 | case ((n, _, arr), _) | ||
| 618 |
4/6✓ Branch 0 taken 3108877 times.
✓ Branch 1 taken 4 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 3108877 times.
✓ Branch 5 taken 3108877 times.
✗ Branch 6 not taken.
|
3108881 | then if pos <= n then isSome(arr[pos]) else false; |
| 619 | |||
| 620 | end match; | ||
| 621 | end valueArrayKeyIndexExists; | ||
| 622 | |||
| 623 | public function copy | ||
| 624 | "Makes a copy of a hashtable." | ||
| 625 | input HashTable inHashTable; | ||
| 626 | output HashTable outCopy; | ||
| 627 | protected | ||
| 628 | HashVector hv; | ||
| 629 | Integer bs, vs, ve; | ||
| 630 | FuncsTuple ft; | ||
| 631 | array<Option<HashEntry>> vae; | ||
| 632 | algorithm | ||
| 633 | 10 | (hv, (vs, ve, vae), bs, ft) := inHashTable; | |
| 634 | 10 | hv := arrayCopy(hv); | |
| 635 | 10 | vae := arrayCopy(vae); | |
| 636 | 10 | outCopy := (hv, (vs, ve, vae), bs, ft); | |
| 637 | end copy; | ||
| 638 | |||
| 639 | public function clear | ||
| 640 | "Clears the hashtable." | ||
| 641 | input output HashTable ht; | ||
| 642 | protected | ||
| 643 | HashVector hv; | ||
| 644 | Integer bs, vs, ve, hash_idx; | ||
| 645 | FuncsTuple ft; | ||
| 646 | FuncHash hashFunc; | ||
| 647 | Key key; | ||
| 648 | array<Option<HashEntry>> vae; | ||
| 649 | algorithm | ||
| 650 | 27250 | (hv, (vs, ve, vae), bs, ft as (hashFunc,_,_,_)) := ht; | |
| 651 |
2/2✓ Branch 0 taken 14057 times.
✓ Branch 1 taken 13193 times.
|
156911 | for i in 1:vs loop |
| 652 | () := match arrayGet(vae, i) | ||
| 653 | case SOME((key,_)) | ||
| 654 | algorithm | ||
| 655 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 129661 times.
|
259322 | hash_idx := intMod(hashFunc(key), bs) + 1; |
| 656 | 129661 | arrayUpdate(hv, hash_idx, {}); | |
| 657 | 129661 | arrayUpdate(vae, i, NONE()); | |
| 658 | then (); | ||
| 659 | else (); | ||
| 660 | end match; | ||
| 661 | end for; | ||
| 662 | 27250 | ht := (hv, (0, ve, vae), bs, ft); | |
| 663 | end clear; | ||
| 664 | |||
| 665 | public function clearAssumeNoDelete | ||
| 666 | "Clears a HashTable that has not been properly stored, but was known to never delete an element (making the values sequential SOME() for as long as there are elements). NOTE: Does not handle arrays that were expanded?" | ||
| 667 | input HashTable ht; | ||
| 668 | protected | ||
| 669 | HashVector hv; | ||
| 670 | Integer bs, vs, ve, hash_idx; | ||
| 671 | FuncsTuple ft; | ||
| 672 | FuncHash hashFunc; | ||
| 673 | Key key; | ||
| 674 | array<Option<HashEntry>> vae; | ||
| 675 | constant Boolean workaroundForBug=true "TODO: Make it impossible to update a value by not updating n (fully mutable HT instead of this hybrid)"; | ||
| 676 | constant Boolean debug=false; | ||
| 677 | algorithm | ||
| 678 | 364590 | (hv, (vs, ve, vae), bs, ft as (hashFunc,_,_,_)) := ht; | |
| 679 |
1/2✓ Branch 0 taken 364590 times.
✗ Branch 1 not taken.
|
449174880 | for i in 1:ve loop |
| 680 | () := match arrayGet(vae, i) | ||
| 681 | case SOME((key,_)) | ||
| 682 | algorithm | ||
| 683 | if not workaroundForBug then | ||
| 684 | hash_idx := intMod(hashFunc(key), bs) + 1; | ||
| 685 | arrayUpdate(hv, hash_idx, {}); | ||
| 686 | end if; | ||
| 687 | 594948 | arrayUpdate(vae, i, NONE()); | |
| 688 | then (); | ||
| 689 | else | ||
| 690 | algorithm | ||
| 691 | if not workaroundForBug then return; end if; | ||
| 692 | then (); | ||
| 693 | end match; | ||
| 694 | end for; | ||
| 695 | if debug then | ||
| 696 | for i in vae loop | ||
| 697 | if isSome(i) then | ||
| 698 | print("vae not empty\n"); | ||
| 699 | break; | ||
| 700 | end if; | ||
| 701 | end for; | ||
| 702 | end if; | ||
| 703 | if workaroundForBug then | ||
| 704 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 364590 times.
|
748867860 | for i in 1:arrayLength(hv) loop |
| 705 |
2/2✓ Branch 1 taken 594945 times.
✓ Branch 2 taken 747908325 times.
|
748503270 | if not listEmpty(arrayGet(hv,i)) then |
| 706 | if debug then print("hv not empty\n"); end if; | ||
| 707 | 594945 | arrayUpdate(hv,i,{}); | |
| 708 | end if; | ||
| 709 | end for; | ||
| 710 | end if; | ||
| 711 | end clearAssumeNoDelete; | ||
| 712 | |||
| 713 | annotation(__OpenModelica_Interface="util"); | ||
| 714 | end BaseHashTable; | ||
| 715 |