gdk_ssort.c

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

	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;
	}
}



#line 741 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_ssort.mx"

#endif
#ifndef NOEXPAND_BTE

#line 199 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_ssort.mx"
/* binarysort is the best method for sorting small arrays: it does
   few compares, but can do data movement quadratic in the number of
   elements.
   [lo, hi) is a contiguous slice of a list, and is sorted via
   binary insertion.  This sort is stable.
   On entry, must have lo <= start <= hi, and that [lo, start) is already
   sorted (pass start == lo if you don't know!). */
static void
binarysort_bte(void *lo, void *hi, void *start, MergeState *ms)
{
	register void *l, *p, *r;

	assert(lo <= start && start <= hi);
	/* assert [lo, start) is sorted */
	if (lo == start)
		start = PTRADD(start, 1, ms->width);
	/* [lo,start) is sorted, insert start (the pivot) into this
	   area, finding its position using binary search. */
	for (; start < hi; start = PTRADD(start, 1, ms->width)) {
		/* set l to where start belongs */
		l = lo;
		r = start;
		/* ms->t is the pivot */
		COPY(ms->t, r, ms->width);
		/* Invariants:
		   pivot >= all in [lo, l).
		   pivot  < all in [r, start).
		   The second is vacuously true at the start.
		 */
		assert(l < r);
		do {
			p = PTRADD(l, (((char *) r - (char *) l) / ms->width) >> 1, ms->width);
			if (ISLT_bte(ms->t, p, ms))
				r = p;
			else
				l = PTRADD(p, 1, ms->width);
		} while (l < r);
		assert(l == r);
		/* The invariants still hold, so pivot >= all in [lo, l) and
		   pivot < all in [l, start), so pivot belongs at l.  Note
		   that if there are elements equal to pivot, l points to the
		   first slot after them -- that's why this sort is stable.
		   Slide over to make room.
		   Caution: using memmove is much slower under MSVC 5;
		   we're not usually moving many slots. */
		for (p = start, r = PTRADD(p, -1, ms->width); p > l; p = r, r = PTRADD(p, -1, ms->width))
			COPY(p, r, ms->width);
		COPY(l, ms->t, ms->width);
	}
}

/* Locate the proper position of key in a sorted vector; if the vector contains
   an element equal to key, return the position immediately to the left of
   the leftmost equal element.  [gallop_right() does the same except returns
   the position to the right of the rightmost equal element (if any).]

   "a" is a sorted vector with n elements, starting at a[0].  n must be > 0.

   "hint" is an index at which to begin the search, 0 <= hint < n.  The closer
   hint is to the final result, the faster this runs.

   The return value is the int k in 0..n such that

	a[k-1] < key <= a[k]

   pretending that *(a-1) is minus infinity and a[n] is plus infinity.  IOW,
   key belongs at index k; or, IOW, the first k elements of a should precede
   key, and the last n-k should follow key.

   Returns -1 on error.  See listsort.txt for info on the method. */
static ssize_t
gallop_left_bte(void *key, void *a, ssize_t n, ssize_t hint, MergeState *ms)
{
	ssize_t ofs;
	ssize_t lastofs;
	ssize_t k;

	assert(key && a && n > 0 && hint >= 0 && hint < n);

	a = PTRADD(a, hint, ms->width);
	lastofs = 0;
	ofs = 1;
	if (ISLT_bte(a, key, ms)) {
		/* a[hint] < key -- gallop right, until
		   a[hint + lastofs] < key <= a[hint + ofs]
		 */
		const ssize_t maxofs = n - hint;	/* &a[n-1] is highest */
		while (ofs < maxofs) {
			if (ISLT_bte(PTRADD(a, ofs, ms->width), key, ms)) {
				lastofs = ofs;
				ofs = (ofs << 1) + 1;
				if (ofs <= 0)	/* int overflow */
					ofs = maxofs;
			} else	/* key <= a[hint + ofs] */
				break;
		}
		if (ofs > maxofs)
			ofs = maxofs;
		/* Translate back to offsets relative to &a[0]. */
		lastofs += hint;
		ofs += hint;
	} else {
		/* key <= a[hint] -- gallop left, until
		   a[hint - ofs] < key <= a[hint - lastofs]
		 */
		const ssize_t maxofs = hint + 1;	/* &a[0] is lowest */
		while (ofs < maxofs) {
			if (ISLT_bte(PTRADD(a, -ofs, ms->width), key, ms))
				break;
			/* key <= a[hint - ofs] */
			lastofs = ofs;
			ofs = (ofs << 1) + 1;
			if (ofs <= 0)	/* int overflow */
				ofs = maxofs;
		}
		if (ofs > maxofs)
			ofs = maxofs;
		/* Translate back to positive offsets relative to &a[0]. */
		k = lastofs;
		lastofs = hint - ofs;
		ofs = hint - k;
	}
	a = PTRADD(a, -hint, ms->width);

	assert(-1 <= lastofs && lastofs < ofs && ofs <= n);
	/* Now a[lastofs] < key <= a[ofs], so key belongs somewhere to the
	   right of lastofs but no farther right than ofs.  Do a binary
	   search, with invariant a[lastofs-1] < key <= a[ofs].
	 */
	++lastofs;
	while (lastofs < ofs) {
		ssize_t m = lastofs + ((ofs - lastofs) >> 1);

		if (ISLT_bte(PTRADD(a, m, ms->width), key, ms))
			lastofs = m + 1; /* a[m] < key */
		else
			ofs = m;	/* key <= a[m] */
	}
	assert(lastofs == ofs);		/* so a[ofs-1] < key <= a[ofs] */
	return ofs;
}

/* Exactly like gallop_left(), except that if key already exists in a[0:n],
   finds the position immediately to the right of the rightmost equal value.

   The return value is the int k in 0..n such that

	a[k-1] <= key < a[k]

   or -1 if error.

   The code duplication is massive, but this is enough different given that
   we're sticking to "<" comparisons that it's much harder to follow if
   written as one routine with yet another "left or right?" flag. */
static ssize_t
gallop_right_bte(void *key, void *a, ssize_t n, ssize_t hint, MergeState *ms)
{
	ssize_t ofs;
	ssize_t lastofs;
	ssize_t k;

	assert(key && a && n > 0 && hint >= 0 && hint < n);

	a = PTRADD(a, hint, ms->width);
	lastofs = 0;
	ofs = 1;
	if (ISLT_bte(key, a, ms)) {
		/* key < a[hint] -- gallop left, until
		   a[hint - ofs] <= key < a[hint - lastofs]
		 */
		const ssize_t maxofs = hint + 1;	/* &a[0] is lowest */
		while (ofs < maxofs) {
			if (ISLT_bte(key, PTRADD(a, -ofs, ms->width), ms)) {
				lastofs = ofs;
				ofs = (ofs << 1) + 1;
				if (ofs <= 0)	/* int overflow */
					ofs = maxofs;
			} else	/* a[hint - ofs] <= key */
				break;
		}
		if (ofs > maxofs)
			ofs = maxofs;
		/* Translate back to positive offsets relative to &a[0]. */
		k = lastofs;
		lastofs = hint - ofs;
		ofs = hint - k;
	} else {
		/* a[hint] <= key -- gallop right, until
		   a[hint + lastofs] <= key < a[hint + ofs]
		*/
		const ssize_t maxofs = n - hint;	/* &a[n-1] is highest */
		while (ofs < maxofs) {
			if (ISLT_bte(key, PTRADD(a, ofs, ms->width), ms))
				break;
			/* a[hint + ofs] <= key */
			lastofs = ofs;
			ofs = (ofs << 1) + 1;
			if (ofs <= 0)	/* int overflow */
				ofs = maxofs;
		}
		if (ofs > maxofs)
			ofs = maxofs;
		/* Translate back to offsets relative to &a[0]. */
		lastofs += hint;
		ofs += hint;
	}
	a = PTRADD(a, -hint, ms->width);

	assert(-1 <= lastofs && lastofs < ofs && ofs <= n);
	/* Now a[lastofs] <= key < a[ofs], so key belongs somewhere to the
	   right of lastofs but no farther right than ofs.  Do a binary
	   search, with invariant a[lastofs-1] <= key < a[ofs].
	 */
	++lastofs;
	while (lastofs < ofs) {
		ssize_t m = lastofs + ((ofs - lastofs) >> 1);

		if (ISLT_bte(key, PTRADD(a, m, ms->width), ms))
			ofs = m;	/* key < a[m] */
		else
			lastofs = m+1;	/* a[m] <= key */
	}
	assert(lastofs == ofs);		/* so a[ofs-1] <= key < a[ofs] */
	return ofs;
}

/* Merge the two runs at stack indices i and i+1.
   Returns 0 on success, -1 on error. */
static ssize_t
merge_at_bte(MergeState *ms, ssize_t i)
{
	void *pa, *pb;
	ssize_t na, nb;
	ssize_t k;

	assert(ms != NULL);
	assert(ms->n >= 2);
	assert(i >= 0);
	assert(i == ms->n - 2 || i == ms->n - 3);

	pa = ms->pending[i].base;
	na = ms->pending[i].len;
	pb = ms->pending[i + 1].base;
	nb = ms->pending[i + 1].len;
	assert(na > 0 && nb > 0);
	assert(PTRADD(pa, na, ms->width) == pb);

	/* Record the length of the combined runs; if i is the 3rd-last
	   run now, also slide over the last run (which isn't involved
	   in this merge).  The current run i+1 goes away in any case.
	 */
	ms->pending[i].len = na + nb;
	if (i == ms->n - 3)
		ms->pending[i + 1] = ms->pending[i + 2];
	--ms->n;

	/* Where does b start in a?  Elements in a before that can be
	   ignored (already in place).
	 */
	k = gallop_right_bte(pb, pa, na, 0, ms);
	pa = PTRADD(pa, k, ms->width);
	na -= k;
	if (na == 0)
		return 0;

	/* Where does a end in b?  Elements in b after that can be
	   ignored (already in place).
	 */
	nb = gallop_left_bte(PTRADD(pa, na - 1, ms->width), pb, nb, nb-1, ms);
	if (nb <= 0)
		return nb;

	/* Merge what remains of the runs, using a temp array with
	   min(na, nb) elements.
	 */
	if (na <= nb) {
/* 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;
		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, na) < 0)
			return -1;
		COPY(ms->a, pa, na * ms->width);
		dest = pa;
		pa = ms->a;

		COPY(dest, pb, ms->width);
		dest = PTRADD(dest, 1, ms->width);
		pb = PTRADD(pb, 1, ms->width);
		--nb;
		if (nb == 0)
			goto SucceedA;
		if (na == 1)
			goto CopyB;

		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 > 1 && nb > 0);
				k = ISLT_bte(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_bte(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_bte(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;