** Compute the optimal size for the array part of table 't'. 'nums' is a ** "count array" where 'nums[i]' is the number of integers in the table ** between 2^(i - 1) + 1 and 2^i. 'pna' enters with the total number of ** integer keys in the table and leaves with the number of keys that ** will go to the array part; return the optimal size. (The condition ** 'twotoi > 0' in the for loop stops the l
| 378 | ** 'twotoi > 0' in the for loop stops the loop if 'twotoi' overflows.) |
| 379 | */ |
| 380 | static unsigned int computesizes (unsigned int nums[], unsigned int *pna) { |
| 381 | int i; |
| 382 | unsigned int twotoi; /* 2^i (candidate for optimal size) */ |
| 383 | unsigned int a = 0; /* number of elements smaller than 2^i */ |
| 384 | unsigned int na = 0; /* number of elements to go to array part */ |
| 385 | unsigned int optimal = 0; /* optimal size for array part */ |
| 386 | /* loop while keys can fill more than half of total size */ |
| 387 | for (i = 0, twotoi = 1; |
| 388 | twotoi > 0 && *pna > twotoi / 2; |
| 389 | i++, twotoi *= 2) { |
| 390 | a += nums[i]; |
| 391 | if (a > twotoi/2) { /* more than half elements present? */ |
| 392 | optimal = twotoi; /* optimal size (till now) */ |
| 393 | na = a; /* all elements up to 'optimal' will go to array part */ |
| 394 | } |
| 395 | } |
| 396 | lua_assert((optimal == 0 || optimal / 2 < na) && na <= optimal); |
| 397 | *pna = na; |
| 398 | return optimal; |
| 399 | } |
| 400 | |
| 401 | |
| 402 | static int countint (lua_Integer key, unsigned int *nums) { |