|
Hi, there seems to be a bug in the function 'countint' in 'ltable.c' of version 'lua-5.2.0-alpha'. It counts a key one off its correct position so that in border cases it is counted in the wrong bucket. If a table is only populated by increasing integer keys starting from 1, the hashtable should never be used. But the erroneous counting would use it e.g. for a key '2^m+1', which does not fit in the allocated array. This slows down performance, because a rehash has to be done twice (for '2^m+1' and for '2^m+2'). In addition if key = MAXASIZE = 2^MAXBITS is used, the non existent bucket 'nums[MAXBITS+1]' is used with unpredictable results. My suggestion: static int countint (const TValue *key, int *nums) { int k = arrayindex(key); if (0 < k && k <= MAXASIZE) { /* is `key' an appropriate array index? */ /* nums[luaO_ceillog2(k)]++; */ /* count as such */ nums[luaO_ceillog2(k-1)]++ /* count as such [CORRECTING BUG] */ return 1; } else return 0; } Regards, Michael Rose
|