** Does the partition: Pivot P is at the top of the stack. ** precondition: a[lo] <= P == a[up-1] <= a[up], ** so it only needs to do the partition from lo + 1 to up - 2. ** Pos-condition: a[lo .. i - 1] <= a[i] == P <= a[i + 1 .. up] ** returns 'i'. */
| 292 | ** returns 'i'. |
| 293 | */ |
| 294 | static IdxT partition (lua_State *L, IdxT lo, IdxT up) { |
| 295 | IdxT i = lo; /* will be incremented before first use */ |
| 296 | IdxT j = up - 1; /* will be decremented before first use */ |
| 297 | /* loop invariant: a[lo .. i] <= P <= a[j .. up] */ |
| 298 | for (;;) { |
| 299 | /* next loop: repeat ++i while a[i] < P */ |
| 300 | while ((void)geti(L, 1, ++i), sort_comp(L, -1, -2)) { |
| 301 | if (l_unlikely(i == up - 1)) /* a[up - 1] < P == a[up - 1] */ |
| 302 | luaL_error(L, "invalid order function for sorting"); |
| 303 | lua_pop(L, 1); /* remove a[i] */ |
| 304 | } |
| 305 | /* after the loop, a[i] >= P and a[lo .. i - 1] < P (a) */ |
| 306 | /* next loop: repeat --j while P < a[j] */ |
| 307 | while ((void)geti(L, 1, --j), sort_comp(L, -3, -1)) { |
| 308 | if (l_unlikely(j < i)) /* j <= i - 1 and a[j] > P, contradicts (a) */ |
| 309 | luaL_error(L, "invalid order function for sorting"); |
| 310 | lua_pop(L, 1); /* remove a[j] */ |
| 311 | } |
| 312 | /* after the loop, a[j] <= P and a[j + 1 .. up] >= P */ |
| 313 | if (j < i) { /* no elements out of place? */ |
| 314 | /* a[lo .. i - 1] <= P <= a[j + 1 .. i .. up] */ |
| 315 | lua_pop(L, 1); /* pop a[j] */ |
| 316 | /* swap pivot (a[up - 1]) with a[i] to satisfy pos-condition */ |
| 317 | set2(L, up - 1, i); |
| 318 | return i; |
| 319 | } |
| 320 | /* otherwise, swap a[i] - a[j] to restore invariant and repeat */ |
| 321 | set2(L, i, j); |
| 322 | } |
| 323 | } |
| 324 | |
| 325 | |
| 326 | /* |
no test coverage detected