lua/src/ltablib.c

293 ** precondition: a[lo] <= P == a[up-1] <= a[up],
294 ** so it only needs to do the partition from lo + 1 to up - 2.
295 ** Pos-condition: a[lo .. i - 1] <= a[i] == P <= a[i + 1 .. up]
298 static IdxT partition (lua_State *L, IdxT lo, IdxT up) {
299   IdxT i = lo;  /* will be incremented before first use */
301   /* loop invariant: a[lo .. i] <= P <= a[j .. up] */
309     /* after the loop, a[i] >= P and a[lo .. i - 1] < P */
318       /* a[lo .. i - 1] <= P <= a[j + 1 .. i .. up] */
331 ** Choose an element in the middle (2nd-3th quarters) of [lo,up]
334 static IdxT choosePivot (IdxT lo, IdxT up, unsigned int rnd) {
335   IdxT r4 = (up - lo) / 4;  /* range/4 */
336   IdxT p = rnd % (r4 * 2) + (lo + r4);
337   lua_assert(lo + r4 <= p && p <= up - r4);
345 static void auxsort (lua_State *L, IdxT lo, IdxT up,
347   while (lo < up) {  /* loop for tail recursion */
350     /* sort elements 'lo', 'p', and 'up' */
351     lua_geti(L, 1, lo);
353     if (sort_comp(L, -1, -2))  /* a[up] < a[lo]? */
354       set2(L, lo, up);  /* swap a[lo] - a[up] */
357     if (up - lo == 1)  /* only 2 elements? */
359     if (up - lo < RANLIMIT || rnd == 0)  /* small interval or no randomize? */
360       p = (lo + up)/2;  /* middle element is a good pivot */
362       p = choosePivot(lo, up, rnd);
364     lua_geti(L, 1, lo);
365     if (sort_comp(L, -2, -1))  /* a[p] < a[lo]? */
366       set2(L, p, lo);  /* swap a[p] - a[lo] */
368       lua_pop(L, 1);  /* remove a[lo] */
375     if (up - lo == 2)  /* only 3 elements? */
381     p = partition(L, lo, up);
382     /* a[lo .. p - 1] <= a[p] == P <= a[p + 1 .. up] */
383     if (p - lo < up - p) {  /* lower interval is smaller? */
384       auxsort(L, lo, p - 1, rnd);  /* call recursively for lower interval */
385       n = p - lo;  /* size of smaller interval */
386       lo = p + 1;  /* tail call for [p + 1 .. up] (upper interval) */
391       up = p - 1;  /* tail call for [lo .. p - 1]  (lower interval) */
393     if ((up - lo) / 128 > n) /* partition too imbalanced? */
395   }  /* tail call auxsort(L, lo, up, rnd) */