gdk_batop.c

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

		size_t _lo = batcnt / 2, _hi = _lo + 105;
		BAT *tmp1;
		ALGODEBUG THRprintf(GDKout, "#BAT_select_(b=%s): sampling: tmp1 = BATslice(b=%s, _lo=" SZFMT ", _hi=" SZFMT ");\n", BATgetId(b), BATgetId(b), _lo, _hi);

		tmp1 = BATslice(b, _lo, _hi);	/* slice keeps all parent properties */
		if (tmp1) {
			BAT *tmp2;
			ALGODEBUG THRprintf(GDKout, "#BAT_select_(b=%s): sampling: tmp2 = BAT_select_(tmp1=%s, tl, th, tail);\n", BATgetId(b), BATgetId(tmp1));

			tmp2 = BAT_select_(tmp1, tl, th, li, hi, tail, FALSE);
			if (tmp2) {
				/* reserve 105% of what has been estimated */
				estimate = (size_t) ((((lng) BATcount(tmp2)) * (lng) batcnt) / LL_CONSTANT(100));
				BBPreclaim(tmp2);
			}
			BBPreclaim(tmp1);
		}
	} else {
		estimate = MAX(estimate, BATguess(b));
	}


#line 869 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_batop.mx"
	if (ht == TYPE_void && tt == TYPE_void) {
		ht = TYPE_oid;
	}
	bn = BATnew(ht, tt, estimate);
	if (bn) {
		int nocheck = (estimate >= batcnt);

		if (!preserve_order && equi && b->thash) {
			ALGODEBUG THRprintf(GDKout, "#BAT_select_(b=%s): BAT_hashselect(b=%s, bn=%s, tl); (using existing hash-table)\n", BATgetId(b), BATgetId(b), BATgetId(bn));

			bn = BAT_hashselect(b, bn, tl);
		} else if (!preserve_order && equi && ATOMsize(b->ttype) > 1 && estimate * 100 < batcnt && batcnt * 2 * sizeof(int) < (GDK_mem_maxsize / 4)) {
			/* Build a hash-table on the fly for equi-select if the selectivity is low
			 * and it is not too big */
			ALGODEBUG THRprintf(GDKout, "#BAT_select_(b=%s): BAT_hashselect(b=%s, bn=%s, tl); (building hash-table on the fly)\n", BATgetId(b), BATgetId(b), BATgetId(bn));

			bn = BAT_hashselect(b, bn, tl);
		} else {
			ALGODEBUG THRprintf(GDKout, "#BAT_select_(b=%s): BAT_scanselect(b=%s, bn=%s, tl, th, equi=%d, lval=%d, hval=%d, nocheck=%d);\n", BATgetId(b), BATgetId(b), BATgetId(bn), equi, lval, hval, nocheck);

			bn = BAT_scanselect(b, bn, tl, th, li, hi, equi, lval, hval, nocheck);
		}
	}
	if (bn == NULL) {
		return NULL;	/* error occurred */
	}


#line 899 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_batop.mx"
	if (BATcount(bn)) {
		BATkey(bn, b->hkey);
		BATkey(BATmirror(bn), b->tkey);
	} else {
		BATkey(bn, TRUE);
		BATkey(BATmirror(bn), TRUE);
	}
	if (equi && tail) {
		BATsetprop_wrd(bn, GDK_AGGR_CARD, (wrd) (BATcount(bn) > 0));
		if (b->ttype == TYPE_bit) {
			BATsetprop_wrd(bn, GDK_AGGR_SIZE, (*(bit *) tl == TRUE) ? BATcount(bn) : 0);
		}
	}
	if (equi && b->thash) {
		bn->hsorted = bn->tsorted = FALSE;
	} else {
		if (BATcount(bn) == BATcount(b))
			ALIGNset(bn, b);
		bn->hsorted = BAThordered(b);
		bn->tsorted = BATtordered(b);
	}
	ALGODEBUG THRprintf(GDKout, "#BAT_select_(b=%s): %s: hkey=%d, tkey=%d, hsorted=%d, tsorted=%d.\n", BATgetId(b), BATgetId(bn), bn->hkey, bn->tkey, bn->hsorted, bn->tsorted);
	ESTIDEBUG THRprintf(GDKout, "#BAT_select_(b=%s): resultsize: estimated " SZFMT ", got " SZFMT ".\n", BATgetId(b), estimate, BATcount(bn));

	return bn;
}

BAT *
BAT_select(BAT *b, ptr h, ptr t, bit tail)
{
	return BAT_select_(b, h, t, TRUE, TRUE, tail, FALSE);
}

BAT *
BATselect_(BAT *b, ptr h, ptr t, bit li, bit hi)
{
	return BAT_select_(b, h, t, li, hi, TRUE, FALSE);
}

BAT *
BATuselect_(BAT *b, ptr h, ptr t, bit li, bit hi)
{
	return BAT_select_(b, h, t, li, hi, FALSE, FALSE);
}

BAT *
BATselect(BAT *b, ptr h, ptr t)
{
	return BAT_select_(b, h, t, TRUE, TRUE, TRUE, FALSE);
}

BAT *
BATuselect(BAT *b, ptr h, ptr t)
{
	return BAT_select_(b, h, t, TRUE, TRUE, FALSE, FALSE);
}



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


#line 966 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_batop.mx"
size_t
BATtopN(BAT *b, size_t topN)
{
	BATcheck(b, "BATtopN");
	if (topN > BATcount(b)) {
		GDKerror("BATtopN: not enough tuples in target\n");
	} else if (topN * BUNsize(b) > b->batBuns->size) {
		GDKerror("BATtopN: not enough capacity to keep result\n");
	} else if (b->dims.headvarsized || b->dims.tailvarsized) {
		HASHremove(b);
		while (BATcount(b) > topN)
			BUNdelete(b, BUNlast(b), FALSE);
	} else {
		HASHremove(b);
		b->batBuns->free = BUNptr(b, topN) - Bunbase(b);
		BATsetcount(b, topN);
	}
	return 0;
}



#line 988 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_batop.mx"
BAT *
BATsample(BAT *b, size_t size)
{
	size_t cnt, i, r = 0, n, j;
	size_t *choice, *dst;
	BAT *bn;

	BATcheck(b, "BATsample: source BAT");

	cnt = BATcount(b);
	n = MIN(size, BATcount(b));

	bn = BATnew(BAThtype(b), BATttype(b), n);
	BATcheck(bn, "BATsample: dest BAT");

	if (n == 0)
		return bn;
	dst = choice = (size_t *) GDKmalloc(n * sizeof(size_t));

	if (n * 2 < BATcount(b)) {	/* nondense sample */
		char *vec = (char *) GDKzalloc(1 + (cnt / 8));

		for (j = 0; j < n; j++) {
			r += rand();
			i = r % cnt;
			for (;;) {
				int mask = 1 << (i & 7);

				if (vec[i >> 3] & mask) {
					if (++i == cnt)
						i = 0;
				} else {
					vec[i >> 3] |= mask;
					break;
				}
			}
			*dst++ = i;
		}
		GDKfree(vec);
	} else if (cnt < 65536) {
		unsigned short *vec = (unsigned short *) GDKmalloc(cnt * sizeof(unsigned short));

		for (i = 0; i < cnt; i++)
			vec[i] = (unsigned short) i;
		for (j = 0; j < n; j++) {
			r += rand();
			i = r % cnt;
			*dst++ = vec[i];
			vec[i] = vec[--cnt];
		}
		GDKfree(vec);
	} else {
		size_t *vec = (size_t *) GDKmalloc(cnt * sizeof(size_t));

		for (i = 0; i < cnt; i++)
			vec[i] = i;
		for (j = 0; j < n; j++) {
			r += rand();
			i = r % cnt;
			*dst++ = vec[i];
			vec[i] = vec[--cnt];
		}
		GDKfree(vec);
	}

	/* merge all positions into a sorted list */
	qsort((void *) choice, n, sizeof(size_t),
#if SIZEOF_SIZE_T == SIZEOF_INT
	      (int (*)(const void *, const void *)) intCmp
#else
	      (int (*)(const void *, const void *)) lngCmp
#endif
	    );

	/* insert the sorted sample */
	cnt = BUNindex(b, BUNfirst(b));
	for (j = 0; j < n; j++) {
		BUN p = BUNptr(b, cnt + choice[j]);

		bunfastins(bn, BUNhead(b, p), BUNtail(b, p));
	}
	GDKfree(choice);	/* clean up choice array of BUN positions */

	/* set sorted flags by hand, because we used BUNfastins() */
	bn->hsorted = BAThordered(b);
	bn->tsorted = BATtordered(b);
	BATkey(bn, b->hkey);
	BATkey(BATmirror(bn), b->tkey);
	return bn;
      bunins_failed:
	BBPreclaim(bn);
	return NULL;
}



#line 1084 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_batop.mx"
BAT *
BATfragment(BAT *b, ptr hl, ptr hh, ptr tl, ptr th)
{
	BATcheck(b, "BATfragment:BAT required\n");
	if ((hl == NULL) && (hh == NULL)) {
		return BATselect(b, tl, th);
	}
	if ((BAThordered(b) & 1) == FALSE && (BATtordered(b) & 1)) {
		return BATmirror(BATrestrict(BATmirror(b), tl, th, hl, hh));
	}
	return BATrestrict(b, hl, hh, tl, th);
}



#line 1156 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_batop.mx"
BAT *
BATrestrict(BAT *b, ptr hl, ptr hh, ptr tl, ptr th)
{
	BAT *bn;
	BUN p = NULL, l;
	BUN *mark, *m, *i;
	size_t s;
	int t;

	BATcheck(hl, "BATrestrict:hl is null");
	BATcheck(hh, "BATrestrict:hh is null");
	BATcheck(tl, "BATrestrict:tl is null");
	BATcheck(th, "BATrestrict:th is null");
	bn = BATnew(BAThtype(b), BATttype(b), BATguess(b));
	ESTIDEBUG THRprintf(GDKout, "#BATrestrict: estimated resultsize: " SZFMT "\n", BATguess(b));

	if (bn == NULL) {
		return NULL;
	}
	BATkey(bn, b->hkey);
	BATkey(BATmirror(bn), b->tkey);
	bn->hsorted = BAThordered(b);
	bn->tsorted = BATtordered(b);

	s = BATcount(b);
	if (s == 0) {
		ESTIDEBUG THRprintf(GDKout, "#BATrestrict: actual resultsize: " SZFMT "\n", BATcount(bn));

		return bn;
	}
	mark = (BUN *) GDKmalloc((unsigned) s * sizeof(BUN));
	m = mark;
	i = mark;
	switch (ATOMstorage(t = b->htype)) {
#ifndef NOEXPAND_CHR
	case TYPE_chr:
		
#line 1110 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_batop.mx"
	if (BAThordered(b)&1) {
		int offset;
		BUN p1, p2;

		b= BATmirror(b);
		SORTloop(b, p1, p2, hl, hh, offset) {
			*m++ = p1;
		}
		b= BATmirror(b);
	} else {
		int lval = !simple_EQ(ATOMnilptr(t),hl,chr);
		int hval = !simple_EQ(ATOMnilptr(t),hh,chr);

		if (hval && lval && simple_GT(hl,hh,chr)) {
			GDKerror("BATrestrict: illegal head range.\n");
		} else {
			int xx;

			BATloopFast(b, p, l, xx) {
				if ((!lval || simple_LE(hl, BUNhloc(b, p),chr)) &&
				    (!hval || simple_LE(BUNhloc(b, p), hh,chr))) {
					*m++ = p;
				}
			}
		}
	}


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

		break;
#endif
#ifndef NOEXPAND_BTE
	case TYPE_bte:
		
#line 1110 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_batop.mx"
	if (BAThordered(b)&1) {
		int offset;
		BUN p1, p2;

		b= BATmirror(b);
		SORTloop(b, p1, p2, hl, hh, offset) {
			*m++ = p1;
		}
		b= BATmirror(b);
	} else {
		int lval = !simple_EQ(ATOMnilptr(t),hl,bte);
		int hval = !simple_EQ(ATOMnilptr(t),hh,bte);

		if (hval && lval && simple_GT(hl,hh,bte)) {
			GDKerror("BATrestrict: illegal head range.\n");
		} else {
			int xx;

			BATloopFast(b, p, l, xx) {
				if ((!lval || simple_LE(hl, BUNhloc(b, p),bte)) &&
				    (!hval || simple_LE(BUNhloc(b, p), hh,bte))) {
					*m++ = p;
				}
			}
		}
	}


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

		break;
#endif
#ifndef NOEXPAND_SHT
	case TYPE_sht:
		
#line 1110 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_batop.mx"
	if (BAThordered(b)&1) {
		int offset;
		BUN p1, p2;

		b= BATmirror(b);
		SORTloop(b, p1, p2, hl, hh, offset) {
			*m++ = p1;
		}
		b= BATmirror(b);
	} else {
		int lval = !simple_EQ(ATOMnilptr(t),hl,sht);
		int hval = !simple_EQ(ATOMnilptr(t),hh,sht);

		if (hval && lval && simple_GT(hl,hh,sht)) {
			GDKerror("BATrestrict: illegal head range.\n");
		} else {
			int xx;

			BATloopFast(b, p, l, xx) {
				if ((!lval || simple_LE(hl, BUNhloc(b, p),sht)) &&
				    (!hval || simple_LE(BUNhloc(b, p), hh,sht))) {
					*m++ = p;
				}
			}
		}
	}


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

		break;
#endif
#ifndef NOEXPAND_INT
	case TYPE_int:
		
#line 1110 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_batop.mx"
	if (BAThordered(b)&1) {
		int offset;
		BUN p1, p2;

		b= BATmirror(b);
		SORTloop(b, p1, p2, hl, hh, offset) {
			*m++ = p1;
		}
		b= BATmirror(b);
	} else {
		int lval = !simple_EQ(ATOMnilptr(t),hl,int);
		int hval = !simple_EQ(ATOMnilptr(t),hh,int);

		if (hval && lval && simple_GT(hl,hh,int)) {
			GDKerror("BATrestrict: illegal head range.\n");
		} else {
			int xx;

			BATloopFast(b, p, l, xx) {
				if ((!lval || simple_LE(hl, BUNhloc(b, p),int)) &&
				    (!hval || simple_LE(BUNhloc(b, p), hh,int))) {
					*m++ = p;
				}
			}
		}
	}


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

		break;
#endif
#ifndef NOEXPAND_FLT
	case TYPE_flt:
		
#line 1110 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_batop.mx"
	if (BAThordered(b)&1) {
		int offset;
		BUN p1, p2;

		b= BATmirror(b);
		SORTloop(b, p1, p2, hl, hh, offset) {
			*m++ = p1;
		}
		b= BATmirror(b);
	} else {
		int lval = !simple_EQ(ATOMnilptr(t),hl,flt);
		int hval = !simple_EQ(ATOMnilptr(t),hh,flt);

		if (hval && lval && simple_GT(hl,hh,flt)) {
			GDKerror("BATrestrict: illegal head range.\n");
		} else {
			int xx;

			BATloopFast(b, p, l, xx) {
				if ((!lval || simple_LE(hl, BUNhloc(b, p),flt)) &&
				    (!hval || simple_LE(BUNhloc(b, p), hh,flt))) {
					*m++ = p;
				}
			}
		}
	}


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

		break;
#endif
#ifndef NOEXPAND_DBL
	case TYPE_dbl:
		
#line 1110 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_batop.mx"
	if (BAThordered(b)&1) {
		int offset;
		BUN p1, p2;

		b= BATmirror(b);
		SORTloop(b, p1, p2, hl, hh, offset) {
			*m++ = p1;
		}
		b= BATmirror(b);
	} else {
		int lval = !simple_EQ(ATOMnilptr(t),hl,dbl);
		int hval = !simple_EQ(ATOMnilptr(t),hh,dbl);

		if (hval && lval && simple_GT(hl,hh,dbl)) {
			GDKerror("BATrestrict: illegal head range.\n");
		} else {
			int xx;

			BATloopFast(b, p, l, xx) {
				if ((!lval || simple_LE(hl, BUNhloc(b, p),dbl)) &&
				    (!hval || simple_LE(BUNhloc(b, p), hh,dbl))) {
					*m++ = p;
				}
			}
		}
	}


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

		break;
#endif
#ifndef NOEXPAND_LNG
	case TYPE_lng:
		
#line 1110 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_batop.mx"
	if (BAThordered(b)&1) {
		int offset;
		BUN p1, p2;

		b= BATmirror(b);
		SORTloop(b, p1, p2, hl, hh, offset) {
			*m++ = p1;
		}
		b= BATmirror(b);
	} else {
		int lval = !simple_EQ(ATOMnilptr(t),hl,lng);
		int hval = !simple_EQ(ATOMnilptr(t),hh,lng);

		if (hval && lval && simple_GT(hl,hh,lng)) {
			GDKerror("BATrestrict: illegal head range.\n");
		} else {
			int xx;

			BATloopFast(b, p, l, xx) {
				if ((!lval || simple_LE(hl, BUNhloc(b, p),lng)) &&
				    (!hval || simple_LE(BUNhloc(b, p), hh,lng))) {
					*m++ = p;
				}
			}
		}
	}