** 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
| 868 | ** not a valid integer in Lua.) |
| 869 | */ |
| 870 | static lua_Unsigned hash_search (Table *t, lua_Unsigned j) { |
| 871 | lua_Unsigned i; |
| 872 | if (j == 0) j++; /* the caller ensures 'j + 1' is present */ |
| 873 | do { |
| 874 | i = j; /* 'i' is a present index */ |
| 875 | if (j <= l_castS2U(LUA_MAXINTEGER) / 2) |
| 876 | j *= 2; |
| 877 | else { |
| 878 | j = LUA_MAXINTEGER; |
| 879 | if (isempty(luaH_getint(t, j))) /* t[j] not present? */ |
| 880 | break; /* 'j' now is an absent index */ |
| 881 | else /* weird case */ |
| 882 | return j; /* well, max integer is a boundary... */ |
| 883 | } |
| 884 | } while (!isempty(luaH_getint(t, j))); /* repeat until an absent t[j] */ |
| 885 | /* i < j && t[i] present && t[j] absent */ |
| 886 | while (j - i > 1u) { /* do a binary search between them */ |
| 887 | lua_Unsigned m = (i + j) / 2; |
| 888 | if (isempty(luaH_getint(t, m))) j = m; |
| 889 | else i = m; |
| 890 | } |
| 891 | return i; |
| 892 | } |
| 893 | |
| 894 | |
| 895 | static unsigned int binsearch (const TValue *array, unsigned int i, |
no test coverage detected