gdk_batop.c

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

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

			}
			break;
		}
	}
	GDKfree(mark);

	/* propagate alignment info */
	if (BATcount(bn) == BATcount(b))
		ALIGNset(bn, b);

	ESTIDEBUG THRprintf(GDKout, "#BATrestrict: actual resultsize: " SZFMT "\n", BATcount(bn));

	return bn;

      bunins_failed:
	GDKfree(mark);
	BBPreclaim(bn);
	return NULL;
}



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


#line 1343 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_batop.mx"
#ifdef HAVE_RESTRICT
#define __r     restrict
#else
#ifdef HAVE___RESTRICT__
#define __r     __restrict__
#else
#define __r
#endif
#endif


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

#line 1357 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_batop.mx"
static int
chk_order_chr(chr*__r col)
{
	size_t i, r = 1;

	for (i = 0; i < 128; i += 4) {
		r &= (col[i+1] >= col[i+0]) &
		     (col[i+2] >= col[i+1]) &
		     (col[i+3] >= col[i+2]) &
		     (col[i+4] >= col[i+3]);
	}
	return r != 0;
}



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


#line 1357 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_batop.mx"
static int
chk_order_bte(bte*__r col)
{
	size_t i, r = 1;

	for (i = 0; i < 128; i += 4) {
		r &= (col[i+1] >= col[i+0]) &
		     (col[i+2] >= col[i+1]) &
		     (col[i+3] >= col[i+2]) &
		     (col[i+4] >= col[i+3]);
	}
	return r != 0;
}



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


#line 1357 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_batop.mx"
static int
chk_order_sht(sht*__r col)
{
	size_t i, r = 1;

	for (i = 0; i < 128; i += 4) {
		r &= (col[i+1] >= col[i+0]) &
		     (col[i+2] >= col[i+1]) &
		     (col[i+3] >= col[i+2]) &
		     (col[i+4] >= col[i+3]);
	}
	return r != 0;
}



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


#line 1357 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_batop.mx"
static int
chk_order_int(int*__r col)
{
	size_t i, r = 1;

	for (i = 0; i < 128; i += 4) {
		r &= (col[i+1] >= col[i+0]) &
		     (col[i+2] >= col[i+1]) &
		     (col[i+3] >= col[i+2]) &
		     (col[i+4] >= col[i+3]);
	}
	return r != 0;
}



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


#line 1357 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_batop.mx"
static int
chk_order_lng(lng*__r col)
{
	size_t i, r = 1;

	for (i = 0; i < 128; i += 4) {
		r &= (col[i+1] >= col[i+0]) &
		     (col[i+2] >= col[i+1]) &
		     (col[i+3] >= col[i+2]) &
		     (col[i+4] >= col[i+3]);
	}
	return r != 0;
}



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


#line 1357 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_batop.mx"
static int
chk_order_flt(flt*__r col)
{
	size_t i, r = 1;

	for (i = 0; i < 128; i += 4) {
		r &= (col[i+1] >= col[i+0]) &
		     (col[i+2] >= col[i+1]) &
		     (col[i+3] >= col[i+2]) &
		     (col[i+4] >= col[i+3]);
	}
	return r != 0;
}



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


#line 1357 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_batop.mx"
static int
chk_order_dbl(dbl*__r col)
{
	size_t i, r = 1;

	for (i = 0; i < 128; i += 4) {
		r &= (col[i+1] >= col[i+0]) &
		     (col[i+2] >= col[i+1]) &
		     (col[i+3] >= col[i+2]) &
		     (col[i+4] >= col[i+3]);
	}
	return r != 0;
}



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


static int
chk_order_oid_oid(oid*__r col)
{
	size_t i, r = 1;

	for (i = 0; i < 256; i += 8) {
		r &= (col[i+2] >= col[i+0]) &
		     (col[i+4] >= col[i+2]) &
		     (col[i+6] >= col[i+4]) &
		     (col[i+8] >= col[i+6]);
	}
	return r != 0;
}

int
BATordered(BAT* b)
{
	size_t cnt = BATcount(b);

	if ((BAThordered(b) & 1) == 0 && cnt > 0) {
		int (*cmp) (ptr, ptr) = BATatoms[b->htype].atomCmp;
		char *cur = (char *) BUNhloc(b, BUNfirst(b));
		char *end = (char *) BUNhloc(b, BUNlast(b));
		int xx = BUNsize(b);

		/* we may have negative information already; this saves a scan */
		if (b->H->nosorted > BUNindex(b, cur) && b->H->nosorted < BUNindex(b, end) && cmp(BUNhead(b, BUNptr(b, b->H->nosorted - 1)), BUNhead(b, BUNptr(b, b->H->nosorted))) > 0) {
			return FALSE;
		}

		/* for [tpe,void] and [OID,OID] bats, we have fast 128-at-a-time routines */
		if (ATOMstorage(b->htype) == ATOMstorage(TYPE_oid) && BUNsize(b) == 2 * ATOMsize(TYPE_oid)) {
			while (cur + 256 * sizeof(oid) < end) {
				if (!chk_order_oid_oid((oid *) cur))
					break;
				cur += 256 * sizeof(oid);
			}
		} else if (ATOMstorage(b->htype) == TYPE_chr && BUNsize(b) == sizeof(chr)) {
			while (cur + 128 * sizeof(chr) < end) {
				if (!chk_order_chr((chr *) cur))
					break;
				cur += 128 * sizeof(chr);
			}
		} else if (ATOMstorage(b->htype) == TYPE_bte && BUNsize(b) == sizeof(bte)) {
			while (cur + 128 * sizeof(bte) < end) {
				if (!chk_order_bte((bte *) cur))
					break;
				cur += 128 * sizeof(bte);
			}
		} else if (ATOMstorage(b->htype) == TYPE_sht && BUNsize(b) == sizeof(sht)) {
			while (cur + 128 * sizeof(sht) < end) {
				if (!chk_order_sht((sht *) cur))
					break;
				cur += 128 * sizeof(sht);
			}
		} else if (ATOMstorage(b->htype) == TYPE_int && BUNsize(b) == sizeof(int)) {
			while (cur + 128 * sizeof(int) < end) {
				if (!chk_order_int((int *) cur))
					break;
				cur += 128 * sizeof(int);
			}
		} else if (ATOMstorage(b->htype) == TYPE_lng && BUNsize(b) == sizeof(lng)) {
			while (cur + 128 * sizeof(lng) < end) {
				if (!chk_order_lng((lng *) cur))
					break;
				cur += 128 * sizeof(lng);
			}
		} else if (ATOMstorage(b->htype) == TYPE_flt && BUNsize(b) == sizeof(flt)) {
			while (cur + 128 * sizeof(flt) < end) {
				if (!chk_order_flt((flt *) cur))
					break;
				cur += 128 * sizeof(flt);
			}
		} else if (ATOMstorage(b->htype) == TYPE_dbl && BUNsize(b) == sizeof(dbl)) {
			while (cur + 128 * sizeof(dbl) < end) {
				if (!chk_order_dbl((dbl *) cur))
					break;
				cur += 128 * sizeof(dbl);
			}
		}

		/* check sortedness tuple-by-tuple */
		if (b->hheap) {
			BUN base = b->hheap->base;
			char *prv = base + *(var_t *) cur;

			cur += xx;
			while (cur < end) {
				char *val = base + *(var_t *) cur;

				if (cmp(prv, val) > 0) {
					/* record negative position info */
					b->H->nosorted = BUNindex(b, cur);
					return FALSE;
				}
				prv = val;
				cur += xx;
			}
		} else {
			char *prv = cur;

			cur += xx;
			while (cur < end) {
				if (cmp(prv, cur) > 0) {
					/* record negative position info */
					b->H->nosorted = BUNindex(b, cur);
					return FALSE;
				}
				prv = cur;
				cur += xx;
			}
		}
	}
	/* it is sorted! set the properties */
	if ((b->hsorted & (bit) GDK_SORTED) == 0) {
		b->batDirtydesc = TRUE;
	}
	b->hsorted |= (bit) GDK_SORTED;
	return TRUE;
}


#line 1505 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_batop.mx"
BAT *
BATsort(BAT *b)
{
	BAT *bn;
	int tt = b->ttype;

	BATcheck(b, "BATsort: BAT");
	if (b->htype == TYPE_void && b->hseqbase == oid_nil) {
		/* b's head is void-nil, hence we return a read-only copy/view of b */
		return BATcopy(b, b->htype, b->ttype, FALSE);
	}
	if ((GDK_SORTED == GDK_SORTED && b->htype == TYPE_void) || (b->htype != TYPE_void && BATordered(b))) {
		/* b is already ordered as desired, hence we return a read-only copy/view of b */
		return BATcopy(b, b->htype, b->ttype, FALSE);
	}
	if (BATcount(b) < 2) {
		/* with fewer than 2 BUNs, b is ordered, hence we return a read-only copy/view of b */
		b->hsorted = (bit) GDK_SORTED;
		if (b->htype == TYPE_oid) {
			oid h = * (oid *) BUNhloc(b, BUNfirst(b));

			if (h != oid_nil) {
				b->hdense = 1;
				b->hseqbase = h;
			}
		}
		return BATcopy(b, b->htype, b->ttype, FALSE);
	}
	/* a void tail column 0,1,2,3,... must be materialized to oid before sorting */
	if (tt == TYPE_void && b->tseqbase != oid_nil) {
		tt = TYPE_oid;
	}
	if ((GDK_SORTED == GDK_SORTED_REV && b->htype == TYPE_void) || 
	    (b->htype != TYPE_void && (b->hkey || 'q' != 's') && BATordered_rev(b))) {
		/* b is ordered in the opposite direction, hence we return a reverted copy of b */
		/* a void head column must be materialized to oid before reverting */
		int ht = b->htype;

		if (ht == TYPE_void && b->hseqbase != oid_nil) {
			ht = TYPE_oid;
		}
		bn = BATrevert(BATcopy(b, ht, tt, TRUE));
		if (bn == NULL)
			return bn;

		return bn;
	}
	bn = BATcopy(b, b->htype, tt, TRUE);
	if (bn == NULL)
		return bn;
	return BATorder(bn);
}

BAT *
BATorder(BAT *b)
{
	BATcheck(b, "BATorder: BAT");
	if (b->htype == TYPE_void && b->hseqbase == oid_nil) {
		/* b's head is void-nil, hence we return b as is */
		return BATcopy(b, b->htype, b->ttype, FALSE);
	}
	if ((GDK_SORTED == GDK_SORTED && b->htype == TYPE_void) || (b->htype != TYPE_void && BATordered(b))) {
		/* b is already ordered as desired, hence we return b as is */
		return b;
	}
	if (BATcount(b) < 2) {
		/* with less than 2 BUNs, b is ordered, hence we return b as is */
		b->hsorted = (bit) GDK_SORTED;
		return b;
	}
	if (b->ttype == TYPE_void && b->tseqbase != oid_nil) {
		/* materialize void-tail in-place */
		b = BATmaterializet(b, BATcount(b));
	}
	if ((GDK_SORTED == GDK_SORTED_REV && b->htype == TYPE_void) || 
	    (b->htype != TYPE_void && (b->hkey || 'q' != 's') && BATordered_rev(b))) {
		/* b is ordered in the opposite direction, hence we revert b */
		b = BATrevert(b);
		return b;
	}
	GDKqsort(BUNfirst(b), (b->hheap)?b->hheap->base:NULL, BATcount(b), BUNsize(b), b->htype, b->hloc);
	HASHdestroy(b);
	ALIGNdel(b, "BATorder", FALSE);
	b->hsorted = (bit) GDK_SORTED;
	b->tsorted = FALSE;
	b->hdense = FALSE;
	b->batDirtydesc = b->batDirtybuns = TRUE;

	return b;
}


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


#line 1505 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_batop.mx"
BAT *
BATssort(BAT *b)
{
	BAT *bn;
	int tt = b->ttype;

	BATcheck(b, "BATsort: BAT");
	if (b->htype == TYPE_void && b->hseqbase == oid_nil) {
		/* b's head is void-nil, hence we return a read-only copy/view of b */
		return BATcopy(b, b->htype, b->ttype, FALSE);
	}
	if ((GDK_SORTED == GDK_SORTED && b->htype == TYPE_void) || (b->htype != TYPE_void && BATordered(b))) {
		/* b is already ordered as desired, hence we return a read-only copy/view of b */
		return BATcopy(b, b->htype, b->ttype, FALSE);
	}
	if (BATcount(b) < 2) {
		/* with fewer than 2 BUNs, b is ordered, hence we return a read-only copy/view of b */
		b->hsorted = (bit) GDK_SORTED;
		if (b->htype == TYPE_oid) {
			oid h = * (oid *) BUNhloc(b, BUNfirst(b));

			if (h != oid_nil) {
				b->hdense = 1;
				b->hseqbase = h;
			}
		}
		return BATcopy(b, b->htype, b->ttype, FALSE);
	}
	/* a void tail column 0,1,2,3,... must be materialized to oid before sorting */
	if (tt == TYPE_void && b->tseqbase != oid_nil) {
		tt = TYPE_oid;
	}
	if ((GDK_SORTED == GDK_SORTED_REV && b->htype == TYPE_void) || 
	    (b->htype != TYPE_void && (b->hkey || 's' != 's') && BATordered_rev(b))) {
		/* b is ordered in the opposite direction, hence we return a reverted copy of b */
		/* a void head column must be materialized to oid before reverting */
		int ht = b->htype;

		if (ht == TYPE_void && b->hseqbase != oid_nil) {
			ht = TYPE_oid;
		}
		bn = BATrevert(BATcopy(b, ht, tt, TRUE));
		if (bn == NULL)
			return bn;

		return bn;
	}
	bn = BATcopy(b, b->htype, tt, TRUE);
	if (bn == NULL)
		return bn;
	return BATsorder(bn);
}

BAT *
BATsorder(BAT *b)
{
	BATcheck(b, "BATorder: BAT");
	if (b->htype == TYPE_void && b->hseqbase == oid_nil) {
		/* b's head is void-nil, hence we return b as is */
		return BATcopy(b, b->htype, b->ttype, FALSE);
	}
	if ((GDK_SORTED == GDK_SORTED && b->htype == TYPE_void) || (b->htype != TYPE_void && BATordered(b))) {
		/* b is already ordered as desired, hence we return b as is */
		return b;
	}
	if (BATcount(b) < 2) {
		/* with less than 2 BUNs, b is ordered, hence we return b as is */
		b->hsorted = (bit) GDK_SORTED;
		return b;
	}
	if (b->ttype == TYPE_void && b->tseqbase != oid_nil) {
		/* materialize void-tail in-place */
		b = BATmaterializet(b, BATcount(b));
	}
	if ((GDK_SORTED == GDK_SORTED_REV && b->htype == TYPE_void) || 
	    (b->htype != TYPE_void && (b->hkey || 's' != 's') && BATordered_rev(b))) {
		/* b is ordered in the opposite direction, hence we revert b */
		b = BATrevert(b);
		return b;
	}
	GDKssort(BUNfirst(b), (b->hheap)?b->hheap->base:NULL, BATcount(b), BUNsize(b), b->htype, b->hloc);
	HASHdestroy(b);
	ALIGNdel(b, "BATorder", FALSE);
	b->hsorted = (bit) GDK_SORTED;
	b->tsorted = FALSE;
	b->hdense = FALSE;
	b->batDirtydesc = b->batDirtybuns = TRUE;

	return b;
}


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




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


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

#line 1357 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_batop.mx"
static int
chk_order_rev_chr(chr*__r col)
{
	size_t i, r = 1;

	for (i = 0; i < 128; i += 4) {
		r &= (col[i+1] <= col[i+0]) &
		     (col[i+2] <= col[i+1]) &
		     (col[i+3] <= col[i+2]) &
		     (col[i+4] <= col[i+3]);
	}
	return r != 0;
}



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


#line 1357 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_batop.mx"
static int
chk_order_rev_bte(bte*__r col)
{
	size_t i, r = 1;

	for (i = 0; i < 128; i += 4) {
		r &= (col[i+1] <= col[i+0]) &
		     (col[i+2] <= col[i+1]) &
		     (col[i+3] <= col[i+2