• Home
  • Raw
  • Download

Lines Matching full:up

75       for (i = e; i > pos; i--) {  /* move up elements */  in tinsert()
291 ** precondition: a[lo] <= P == a[up-1] <= a[up],
292 ** so it only needs to do the partition from lo + 1 to up - 2.
293 ** Pos-condition: a[lo .. i - 1] <= a[i] == P <= a[i + 1 .. up]
296 static IdxT partition (lua_State *L, IdxT lo, IdxT up) { in partition() argument
298 IdxT j = up - 1; /* will be decremented before first use */ in partition()
299 /* loop invariant: a[lo .. i] <= P <= a[j .. up] */ in partition()
303 if (i == up - 1) /* a[i] < P but a[up - 1] == P ?? */ in partition()
314 /* after the loop, a[j] <= P and a[j + 1 .. up] >= P */ in partition()
316 /* a[lo .. i - 1] <= P <= a[j + 1 .. i .. up] */ in partition()
318 /* swap pivot (a[up - 1]) with a[i] to satisfy pos-condition */ in partition()
319 set2(L, up - 1, i); in partition()
329 ** Choose an element in the middle (2nd-3th quarters) of [lo,up]
332 static IdxT choosePivot (IdxT lo, IdxT up, unsigned int rnd) { in choosePivot() argument
333 IdxT r4 = (up - lo) / 4; /* range/4 */ in choosePivot()
335 lua_assert(lo + r4 <= p && p <= up - r4); in choosePivot()
343 static void auxsort (lua_State *L, IdxT lo, IdxT up, in auxsort() argument
345 while (lo < up) { /* loop for tail recursion */ in auxsort()
348 /* sort elements 'lo', 'p', and 'up' */ in auxsort()
350 lua_geti(L, 1, up); in auxsort()
351 if (sort_comp(L, -1, -2)) /* a[up] < a[lo]? */ in auxsort()
352 set2(L, lo, up); /* swap a[lo] - a[up] */ in auxsort()
355 if (up - lo == 1) /* only 2 elements? */ in auxsort()
357 if (up - lo < RANLIMIT || rnd == 0) /* small interval or no randomize? */ in auxsort()
358 p = (lo + up)/2; /* middle element is a good pivot */ in auxsort()
360 p = choosePivot(lo, up, rnd); in auxsort()
367 lua_geti(L, 1, up); in auxsort()
368 if (sort_comp(L, -1, -2)) /* a[up] < a[p]? */ in auxsort()
369 set2(L, p, up); /* swap a[up] - a[p] */ in auxsort()
373 if (up - lo == 2) /* only 3 elements? */ in auxsort()
377 lua_geti(L, 1, up - 1); /* push a[up - 1] */ in auxsort()
378 set2(L, p, up - 1); /* swap Pivot (a[p]) with a[up - 1] */ in auxsort()
379 p = partition(L, lo, up); in auxsort()
380 /* a[lo .. p - 1] <= a[p] == P <= a[p + 1 .. up] */ in auxsort()
381 if (p - lo < up - p) { /* lower interval is smaller? */ in auxsort()
384 lo = p + 1; /* tail call for [p + 1 .. up] (upper interval) */ in auxsort()
387 auxsort(L, p + 1, up, rnd); /* call recursively for upper interval */ in auxsort()
388 n = up - p; /* size of smaller interval */ in auxsort()
389 up = p - 1; /* tail call for [lo .. p - 1] (lower interval) */ in auxsort()
391 if ((up - lo) / 128 > n) /* partition too imbalanced? */ in auxsort()
393 } /* tail call auxsort(L, lo, up, rnd) */ in auxsort()