** Compute the optimal size for the array part of table 't'. ** This size maximizes the number of elements going to the array part ** while satisfying the condition 'arrayXhash' with the use of memory if ** all those elements went to the hash part. ** 'ct->na' enters with the total number of array indices in the table ** and leaves with the number of keys that will go to the array part; ** return
| 444 | ** return the optimal size for the array part. |
| 445 | */ |
| 446 | static unsigned computesizes (Counters *ct) { |
| 447 | int i; |
| 448 | unsigned int twotoi; /* 2^i (candidate for optimal size) */ |
| 449 | unsigned int a = 0; /* number of elements smaller than 2^i */ |
| 450 | unsigned int na = 0; /* number of elements to go to array part */ |
| 451 | unsigned int optimal = 0; /* optimal size for array part */ |
| 452 | /* traverse slices while 'twotoi' does not overflow and total of array |
| 453 | indices still can satisfy 'arrayXhash' against the array size */ |
| 454 | for (i = 0, twotoi = 1; |
| 455 | twotoi > 0 && arrayXhash(twotoi, ct->na); |
| 456 | i++, twotoi *= 2) { |
| 457 | unsigned nums = ct->nums[i]; |
| 458 | a += nums; |
| 459 | if (nums > 0 && /* grows array only if it gets more elements... */ |
| 460 | arrayXhash(twotoi, a)) { /* ...while using "less memory" */ |
| 461 | optimal = twotoi; /* optimal size (till now) */ |
| 462 | na = a; /* all elements up to 'optimal' will go to array part */ |
| 463 | } |
| 464 | } |
| 465 | ct->na = na; |
| 466 | return optimal; |
| 467 | } |
| 468 | |
| 469 | |
| 470 | static void countint (lua_Integer key, Counters *ct) { |