gdk_ssort.mx

这个是内存数据库中的一个管理工具

			 */
			for (;;) {
				assert(na > 1 && nb > 0);
				k = ISLT_@1@2(pb, pa, ms);
				if (k) {
					COPY(dest, pb, ms->width);
					dest = PTRADD(dest, 1, ms->width);
					pb = PTRADD(pb, 1, ms->width);
					++bcount;
					acount = 0;
					--nb;
					if (nb == 0)
						goto SucceedA;
					if (bcount >= min_gallop)
						break;
				} else {
					COPY(dest, pa, ms->width);
					dest = PTRADD(dest, 1, ms->width);
					pa = PTRADD(pa, 1, ms->width);
					++acount;
					bcount = 0;
					--na;
					if (na == 1)
						goto CopyB;
					if (acount >= min_gallop)
						break;
				}
			}

			/* One run is winning so consistently that galloping may
			   be a huge win.  So try that, and continue galloping until
			   (if ever) neither run appears to be winning consistently
			   anymore.
			 */
			++min_gallop;
			do {
				assert(na > 1 && nb > 0);
				min_gallop -= min_gallop > 1;
				ms->min_gallop = min_gallop;
				k = gallop_right_@1@2(pb, pa, na, 0, ms);
				acount = k;
				if (k) {
					COPY(dest, pa, k * ms->width);
					dest = PTRADD(dest, k, ms->width);
					pa = PTRADD(pa, k, ms->width);
					na -= k;
					if (na == 1)
						goto CopyB;
					/* na==0 is impossible now if the comparison
					   function is consistent, but we can't assume
					   that it is.
					 */
					if (na == 0)
						goto SucceedA;
				}
				COPY(dest, pb, ms->width);
				dest = PTRADD(dest, 1, ms->width);
				pb = PTRADD(pb, 1, ms->width);
				--nb;
				if (nb == 0)
					goto SucceedA;

				k = gallop_left_@1@2(pa, pb, nb, 0, ms);
				bcount = k;
				if (k) {
					memmove(dest, pb, k * ms->width);
					dest = PTRADD(dest, k, ms->width);
					pb = PTRADD(pb, k, ms->width);
					nb -= k;
					if (nb == 0)
						goto SucceedA;
				}
				COPY(dest, pa, ms->width);
				dest = PTRADD(dest, 1, ms->width);
				pa = PTRADD(pa, 1, ms->width);
				--na;
				if (na == 1)
					goto CopyB;
			} while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP);
			++min_gallop;	/* penalize it for leaving galloping mode */
			ms->min_gallop = min_gallop;
		}
	SucceedA:
		if (na)
			COPY(dest, pa, na * ms->width);
		return 0;
	CopyB:
		assert(na == 1 && nb > 0);
		/* The last element of pa belongs at the end of the merge. */
		memmove(dest, pb, nb * ms->width);
		COPY(PTRADD(dest, nb, ms->width), pa, ms->width);
		return 0;
	} else {
/* Merge the na elements starting at pa with the nb elements starting at pb
   in a stable way, in-place.  na and nb must be > 0, and pa + na == pb.
   Must also have that *pb < *pa, that pa[na-1] belongs at the end of the
   merge, and should have na >= nb.  See listsort.txt for more info.
   Return 0 if successful, -1 if error. */
		void *dest;
		void *basea;
		void *baseb;
		ssize_t min_gallop = ms->min_gallop;

		assert(ms && pa && pb && na > 0 && nb > 0 && PTRADD(pa, na, ms->width) == pb);
		if (MERGE_GETMEM(ms, nb) < 0)
			return -1;
		dest = PTRADD(pb, nb - 1, ms->width);
		COPY(ms->a, pb, nb * ms->width);
		basea = pa;
		baseb = ms->a;
		pb = PTRADD(ms->a, nb - 1, ms->width);
		pa = PTRADD(pa, na - 1, ms->width);

		COPY(dest, pa, ms->width);
		dest = PTRADD(dest, -1, ms->width);
		pa = PTRADD(pa, -1, ms->width);
		--na;
		if (na == 0)
			goto SucceedB;
		if (nb == 1)
			goto CopyA;

		for (;;) {
			ssize_t acount = 0;	/* # of times A won in a row */
			ssize_t bcount = 0;	/* # of times B won in a row */

			/* Do the straightforward thing until (if ever) one run
			   appears to win consistently.
			 */
			for (;;) {
				assert(na > 0 && nb > 1);
				k = ISLT_@1@2(pb, pa, ms);
				if (k) {
					COPY(dest, pa, ms->width);
					dest = PTRADD(dest, -1, ms->width);
					pa = PTRADD(pa, -1, ms->width);
					++acount;
					bcount = 0;
					--na;
					if (na == 0)
						goto SucceedB;
					if (acount >= min_gallop)
						break;
				} else {
					COPY(dest, pb, ms->width);
					dest = PTRADD(dest, -1, ms->width);
					pb = PTRADD(pb, -1, ms->width);
					++bcount;
					acount = 0;
					--nb;
					if (nb == 1)
						goto CopyA;
					if (bcount >= min_gallop)
						break;
				}
			}

			/* One run is winning so consistently that galloping may
			   be a huge win.  So try that, and continue galloping until
			   (if ever) neither run appears to be winning consistently
			   anymore.
			 */
			++min_gallop;
			do {
				assert(na > 0 && nb > 1);
				min_gallop -= min_gallop > 1;
				ms->min_gallop = min_gallop;
				k = gallop_right_@1@2(pb, basea, na, na - 1, ms);
				k = na - k;
				acount = k;
				if (k) {
					dest = PTRADD(dest, -k, ms->width);
					pa = PTRADD(pa, -k, ms->width);
					memmove(PTRADD(dest, 1, ms->width),
						PTRADD(pa, 1, ms->width),
						k * ms->width);
					na -= k;
					if (na == 0)
						goto SucceedB;
				}
				COPY(dest, pb, ms->width);
				dest = PTRADD(dest, -1, ms->width);
				pb = PTRADD(pb, -1, ms->width);
				--nb;
				if (nb == 1)
					goto CopyA;

				k = gallop_left_@1@2(pa, baseb, nb, nb - 1, ms);
				k = nb - k;
				bcount = k;
				if (k) {
					dest = PTRADD(dest, -k, ms->width);
					pb = PTRADD(pb, -k, ms->width);
					memmove(PTRADD(dest, 1, ms->width),
						PTRADD(pb, 1, ms->width),
						k * ms->width);
					nb -= k;
					if (nb == 1)
						goto CopyA;
					/* nb==0 is impossible now if the comparison
					   function is consistent, but we can't assume
					   that it is.
					 */
					if (nb == 0)
						goto SucceedB;
				}
				COPY(dest, pa, ms->width);
				dest = PTRADD(dest, -1, ms->width);
				pa = PTRADD(pa, -1, ms->width);
				--na;
				if (na == 0)
					goto SucceedB;
			} while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP);
			++min_gallop;	/* penalize it for leaving galloping mode */
			ms->min_gallop = min_gallop;
		}
	SucceedB:
		if (nb)
			COPY(PTRADD(dest, 1 - nb, ms->width), baseb, nb * ms->width);
		return 0;
	CopyA:
		assert(nb == 1 && na > 0);
		/* The first element of pb belongs at the front of the merge. */
		dest = PTRADD(dest, -na, ms->width);
		pa = PTRADD(pa, -na, ms->width);
		memmove(PTRADD(dest, 1, ms->width),
			PTRADD(pa, 1, ms->width),
			na * ms->width);
		COPY(dest, pb, ms->width);
		return 0;
	}
}

@c
#ifndef NOEXPAND_CHR
@:ssort(chr,)@
@:ssort(chr,_rev)@
#endif
#ifndef NOEXPAND_BTE
@:ssort(bte,)@
@:ssort(bte,_rev)@
#endif
#ifndef NOEXPAND_SHT
@:ssort(sht,)@
@:ssort(sht,_rev)@
#endif
#ifndef NOEXPAND_INT
@:ssort(int,)@
@:ssort(int,_rev)@
#endif
#ifndef NOEXPAND_LNG
@:ssort(lng,)@
@:ssort(lng,_rev)@
#endif
#ifndef NOEXPAND_FLT
@:ssort(flt,)@
@:ssort(flt,_rev)@
#endif
#ifndef NOEXPAND_DBL
@:ssort(dbl,)@
@:ssort(dbl,_rev)@
#endif
#ifndef NOEXPAND_OID
@:ssort(oid,)@
@:ssort(oid,_rev)@
#endif
@:ssort(any,)@
@:ssort(any,_rev)@

static ssize_t
merge_compute_minrun(ssize_t n)
{
	ssize_t r = 0;		/* becomes 1 if any 1 bits are shifted off */

	assert(n >= 0);
	while (n >= 16) {
		r |= n & 1;
		n >>= 1;
	}
	return n + r;
}

@= do_ssort
		do {
			int descending;
			ssize_t n;

			/* Identify next run. */
			{
/* Return the length of the run beginning at lo, in the slice [lo,
   hi).  lo < hi is required on entry.  "A run" is the longest
   ascending sequence, with

	lo[0] <= lo[1] <= lo[2] <= ...

   or the longest descending sequence, with

	lo[0] > lo[1] > lo[2] > ...

   Boolean descending is set to 0 in the former  case, or to 1 in the
   latter.  For its intended use in a stable mergesort, the strictness
   of the defn of "descending" is needed so that the caller can safely
   reverse a descending sequence without violating stability (strict >
   ensures there are no equal elements to get out of order). */
				void *nlo;
				void *olo;

				assert(lo < hi);
				descending = 0;
				olo = lo;
				nlo = PTRADD(lo, 1, width);
				if (nlo == hi) {
					n = 1;
				} else {
					n = 2;
					if (ISLT_@1@2(nlo, olo, &ms)) {
						descending = 1;
						for (olo = nlo, nlo = PTRADD(nlo, 1, width);
						     nlo < hi;
						     olo = nlo, nlo = PTRADD(nlo, 1, width), ++n) {
							if (!ISLT_@1@2(nlo, olo, &ms))
								break;
						}
					}
					else {
						for (olo = nlo, nlo = PTRADD(nlo, 1, width);
						     nlo < hi;
						     olo = nlo, nlo = PTRADD(nlo, 1, width), ++n) {
							if (ISLT_@1@2(nlo, olo, &ms))
								break;
						}
					}
				}
			}
			if (descending)
				reverse_slice(lo, PTRADD(lo, n, width), &ms);
			/* If short, extend to min(minrun, nremaining). */
			if (n < minrun) {
				ssize_t force = nremaining <= minrun ? nremaining : minrun;

				binarysort_@1@2(lo, PTRADD(lo, force, width), PTRADD(lo, n, width), &ms);
				n = force;
			}
			/* Push run onto pending-runs stack, and maybe merge. */
			assert(ms.n < MAX_MERGE_PENDING);
			ms.pending[ms.n].base = lo;
			ms.pending[ms.n].len = n;
			ms.n++;
			{
/* Examine the stack of runs waiting to be merged, merging adjacent runs
   until the stack invariants are re-established:

   1. len[-3] > len[-2] + len[-1]
   2. len[-2] > len[-1]

   See listsort.txt for more info.

   Returns 0 on success, -1 on error. */
				struct slice *p = ms.pending;

				while (ms.n > 1) {
					ssize_t i = ms.n - 2;

					if (i > 0 && p[i - 1].len <= p[i].len + p[i + 1].len) {
						if (p[i - 1].len < p[i + 1].len)
							--i;
						if (merge_at_@1@2(&ms, i) < 0)
							goto fail;
					} else if (p[i].len <= p[i + 1].len) {
						 if (merge_at_@1@2(&ms, i) < 0)
							goto fail;
					} else
						break;
				}
			}
			/* Advance to find next run. */
			lo = PTRADD(lo, n, width);
			nremaining -= n;
		} while (nremaining > 0);
		assert(lo == hi);

		{
/* Regardless of invariants, merge all runs on the stack until only one
   remains.  This is used at the end of the mergesort.

   Returns 0 on success, -1 on error. */
			struct slice *p = ms.pending;

			while (ms.n > 1) {
				ssize_t n = ms.n - 2;

				if (n > 0 && p[n - 1].len < p[n + 1].len)
			      		--n;
				if (merge_at_@1@2(&ms, n) < 0)
					goto fail;
			}
		}
@c

@= GDKsort
/* Stable sort an array "a".
   "nitems" is the number of items to sort; "width" is the size of the
   items, "tpe" is the type of the key within the items, "loc" is the
   location (offset) of the key within the item.  If "base" is
   non-NULL, the key is actually an offset relative to "base" and the
   actual key is found at that offset (MonetDB var-sized atoms).
 */
int
GDKssort@1(void *a, void *base, size_t nitems, int width, int tpe, int loc)
{
	MergeState ms;
	ssize_t nremaining;
	int result = -1;
	void *lo, *hi;
	ssize_t minrun;

	assert(a);
	assert(width > 0);
	assert(0 <= loc && loc < width);

	ms.a = (void *) ms.temparray;
	ms.alloced = MERGESTATE_TEMP_SIZE;
	ms.n = 0;
	ms.min_gallop = MIN_GALLOP;
	ms.compare = BATatoms[tpe].atomCmp;
	ms.base = base;
	ms.width = width;
	ms.loc = loc;
	ms.t = (size_t) width <= sizeof(ms.tempstorage) ? ms.tempstorage : alloca(width);

	nremaining = nitems;

	if (nremaining < 2)
		goto succeed;

	/* March over the array once, left to right, finding natural
	   runs, and extending short natural runs to minrun
	   elements. */
	lo = a;
	hi = PTRADD(lo, nremaining, width);
	minrun = merge_compute_minrun(nremaining);
	switch (tpe) {
#ifndef NOEXPAND_CHR
	case TYPE_chr:
		@:do_ssort(chr,@1)@
		break;
#endif
#ifndef NOEXPAND_BTE
	case TYPE_bte:
		@:do_ssort(bte,@1)@
		break;
#endif
#ifndef NOEXPAND_SHT
	case TYPE_sht:
		@:do_ssort(sht,@1)@
		break;
#endif
#ifndef NOEXPAND_INT
	case TYPE_int:
		@:do_ssort(int,@1)@
		break;
#endif
#ifndef NOEXPAND_LNG
	case TYPE_lng:
		@:do_ssort(lng,@1)@
		break;
#endif
#ifndef NOEXPAND_FLT
	case TYPE_flt:
		@:do_ssort(flt,@1)@
		break;
#endif
#ifndef NOEXPAND_DBL
	case TYPE_dbl:
		@:do_ssort(dbl,@1)@
		break;
#endif
#ifndef NOEXPAND_OID
	case TYPE_oid:
		@:do_ssort(oid,@1)@
		break;
#endif
	default:
		@:do_ssort(any,@1)@
		break;
	}
	assert(ms.n == 1);
	assert(ms.pending[0].base == a);
	assert(ms.pending[0].len == (ssize_t) nitems);

  succeed:
	result = 0;
  fail:
	merge_freemem(&ms);
	return result;
}

@c
@:GDKsort()@
@:GDKsort(_rev)@

@}