** 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
| 795 | ** not a valid integer in Lua.) |
| 796 | */ |
| 797 | static lua_Unsigned hash_search (Table *t, lua_Unsigned j) { |
| 798 | lua_Unsigned i; |
| 799 | if (j == 0) j++; /* the caller ensures 'j + 1' is present */ |
| 800 | do { |
| 801 | i = j; /* 'i' is a present index */ |
| 802 | if (j <= l_castS2U(LUA_MAXINTEGER) / 2) |
| 803 | j *= 2; |
| 804 | else { |
| 805 | j = LUA_MAXINTEGER; |
| 806 | if (isempty(luaH_getint(t, j))) /* t[j] not present? */ |
| 807 | break; /* 'j' now is an absent index */ |
| 808 | else /* weird case */ |
| 809 | return j; /* well, max integer is a boundary... */ |
| 810 | } |
| 811 | } while (!isempty(luaH_getint(t, j))); /* repeat until an absent t[j] */ |
| 812 | /* i < j && t[i] present && t[j] absent */ |
| 813 | while (j - i > 1u) { /* do a binary search between them */ |
| 814 | lua_Unsigned m = (i + j) / 2; |
| 815 | if (isempty(luaH_getint(t, m))) j = m; |
| 816 | else i = m; |
| 817 | } |
| 818 | return i; |
| 819 | } |
| 820 | |
| 821 | |
| 822 | static unsigned int binsearch (const TValue *array, unsigned int i, |
no test coverage detected