** Try to find a boundary in the hash part of table 't'. From the ** caller, we know that 'j' is zero or present and that 'j + 1' is ** present. We want to find a larger key that is absent from the ** table, so that we can do a binary search between the two keys to ** find a boundary. We keep doubling 'j' until we get an absent index. ** If the doubling would overflow, we try LUA_MAXINTEGER. If it
| 842 | ** not a valid integer in Lua.) |
| 843 | */ |
| 844 | static lua_Unsigned hash_search (Table *t, lua_Unsigned j) { |
| 845 | lua_Unsigned i; |
| 846 | if (j == 0) j++; /* the caller ensures 'j + 1' is present */ |
| 847 | do { |
| 848 | i = j; /* 'i' is a present index */ |
| 849 | if (j <= l_castS2U(LUA_MAXINTEGER) / 2) |
| 850 | j *= 2; |
| 851 | else { |
| 852 | j = LUA_MAXINTEGER; |
| 853 | if (isempty(luaH_getint(t, j))) /* t[j] not present? */ |
| 854 | break; /* 'j' now is an absent index */ |
| 855 | else /* weird case */ |
| 856 | return j; /* well, max integer is a boundary... */ |
| 857 | } |
| 858 | } while (!isempty(luaH_getint(t, j))); /* repeat until an absent t[j] */ |
| 859 | /* i < j && t[i] present && t[j] absent */ |
| 860 | while (j - i > 1u) { /* do a binary search between them */ |
| 861 | lua_Unsigned m = (i + j) / 2; |
| 862 | if (isempty(luaH_getint(t, m))) j = m; |
| 863 | else i = m; |
| 864 | } |
| 865 | return i; |
| 866 | } |
| 867 | |
| 868 | |
| 869 | static unsigned int binsearch (const TValue *array, unsigned int i, |
no test coverage detected