gdk_setop.mx

来自「这个是内存数据库中的一个管理工具」· MX 代码 · 共 807 行 · 第 1/2 页

					}
				}
				continue;
			}
		}
		MISS@1(h, t);
	}
  end@2@3:;
	END@1(BUNh@2(l,p1), BUNtail(l,p1));
@= hashcheck
	BUN p1, q1, w;
	int ins, s1;
	hash_t s2;
	ptr h, t, t2 = NULL, h2 = hnil;

	ALGODEBUG THRprintf(GDKout, "#BATins_@1@2: hashcheck[@1, @2, @3, @4, @5];\n");
	pin = 1;
	BATmmap_pin(r);
	if (BATprepareHash(r))
		goto bunins_failed;
	BATloopFast(l, p1, q1, s1) {
		h = BUNh@2(l, p1);
		t = BUNtail(l,p1);
		ins = TRUE;
		if (@6) /* check for not-nil (nils don't match anyway) */
			HASHloop@4(r, r->hhash, s2, h, w) {
				t2 = BUNtail(r,w);
				if (EQUAL@5(t,t2)) {
					HIT@1(h, t);
					ins = FALSE;
					break;
				}
			}
		if (!ins)
			continue;
		MISS@1(h,t);
	}
	if (t2 || h2)
		ins = 0;	       /* dummy action for the compiler */
	BATmmap_unpin(r);

@= voidcheck
	{
		BUN p1 = BUNfirst(r), q1 = BUNlast(r);
		oid rl = *(oid*) BUNhead(r,p1);
		oid rh = rl + BATcount(r);
		ptr h, t = NULL, t2 = NULL;

		(void) t2;

		ALGODEBUG THRprintf(GDKout, "#BATins_@1@2: voidcheck[@1, @2];\n");
		if (BAThdense(l)) {
			oid ll = *(oid*) BUNhead(l,(p1=BUNfirst(l)));
			oid lh = ll + BATcount(l);
			BUN hit_start = (q1 = BUNlast(l)), hit_end = q1, w = BUNfirst(r);
			int s1 = BUNsize(l);
			int s2 = BUNsize(r);
			size_t off = BUNindex(l,p1);

			h = (ptr) ≪

			if (rl >= ll && rl < lh) {
				hit_start = BUNptr(l, off+(rl-ll));
			} else if (rl < ll && rh > ll) {
				hit_start = p1;
				w += s2*(ll-rl);
			}
			if (rh >= ll && rh < lh) {
				hit_end = BUNptr(l, off+(rh-ll));
			}
			while(p1 < hit_start) {
				t = BUNtail(l,p1);
				MISS@1(h,t);
				ll++;
				p1 += s1;
			}
			while(p1 < hit_end) {
				t = BUNtail(l,p1);
				t2 = BUNtail(r,w);
				if (EQUAL@2(t,t2)) {
					HIT@1(h,t);
				} else {
					MISS@1(h,t);
				}
				ll++;
				p1 += s1;
				w += s2;
			}
			while(p1 < q1) {
				t = BUNtail(l,p1);
				MISS@1(h,t);
				ll++;
				p1 += s1;
			}
		} else {
			int s1;
			size_t off = BUNindex(r,p1);

			BATloopFast(l, p1, q1, s1) {
				oid o = *(oid*) BUNhloc(l, p1);

				h = (ptr) &o;
				t = BUNtail(l,p1);

				if (o >= rl && o < rh) {
					BUN w = BUNptr(r,off+(o-rl));

					t2 = BUNtail(r,w);
					if (EQUAL@2(t,t2)) {
						HIT@1(h, t);
						continue;
					}
				}
				MISS@1(h,t);
			}
		}
	}

@= check
	if (BAThdense(l)) {
		@:hashcheck(@1,pos,@2,@3,@5,TRUE)@
	} else if (hash) {
		@:hashcheck(@1,@2,@2,@3,@5,@4)@
	} else {
		@:mergecheck(@1,@2,@3,@4,@5)@
	}
	break;

@= batcheck
static BAT*
BATins_@1@2(BAT *bn, BAT *l, BAT *r)
{
	int hash = TRUE, (*cmp)(ptr, ptr), (*merge)(ptr, ptr) = NULL;
	ptr hnil, tnil;
	int pin = 0;

	/* determine how to do the intersect */
	if (BAThordered(l)&BAThordered(r)&1) {
		hash = FALSE;
	} else if (FLIP@1(l,r)) {
		int flip = (BATtordered(l)&BATtordered(r)&1);
		if (flip) {
			hash = FALSE;
		} else {
			flip = (r->hhash == NULL && r->thash != NULL);
		}
		if (flip) {
			merge = BATatoms[l->ttype].atomCmp;
			r= BATmirror(r);
			l= BATmirror(l);
			bn= BATmirror(bn);
		}
	}
	merge = BATatoms[l->htype].atomCmp;
	cmp = BATatoms[l->ttype].atomCmp;
	hnil = ATOMnilptr(l->htype);
	tnil = ATOMnilptr(l->ttype);
	(void) cmp;
	(void) tnil;
	(void) hnil;

	if (BAThdense(r)) {
		@:voidcheck(@2,@1)@
	} else {
		switch(ATOMstorage(r->htype)) {
#ifndef NOEXPAND_CHR
			case TYPE_chr:
				@:check(@2,loc,_chr,simple_CMP(h,h2,chr),@1)@
#endif
#ifndef NOEXPAND_BTE
			case TYPE_bte:
				@:check(@2,loc,_bte,simple_CMP(h,h2,bte),@1)@
#endif
#ifndef NOEXPAND_SHT
			case TYPE_sht:
				@:check(@2,loc,_sht,simple_CMP(h,h2,sht),@1)@
#endif
#ifndef NOEXPAND_INT
			case TYPE_int:
				@:check(@2,loc,_int,simple_CMP(h,h2,int),@1)@
#endif
#ifndef NOEXPAND_FLT
			case TYPE_flt:
				@:check(@2,loc,_flt,simple_CMP(h,h2,flt),@1)@
#endif
#ifndef NOEXPAND_DBL
			case TYPE_dbl:
				@:check(@2,loc,_dbl,simple_CMP(h,h2,dbl),@1)@
#endif
#ifndef NOEXPAND_LNG
			case TYPE_lng:
				@:check(@2,loc,_lng,simple_CMP(h,h2,lng),@1)@
#endif
			default:
			if (r->hvarsized) {
				@:check(@2,var,var,((*merge)(h,h2)),@1)@
			} else {
				@:check(@2,loc,loc,((*merge)(h,h2)),@1)@
			}
		}
	}
	return bn;
  bunins_failed:
	if (pin)
		BATmmap_unpin(r);
	BBPreclaim(bn);
	return NULL;
}

BAT *
BAT@1@2(BAT *l, BAT *r)
{
	size_t	smaller;
	BAT	*bn;

	ERRORcheck(l == NULL, "BAT@1@2: left is null");
	ERRORcheck(r == NULL, "BAT@1@2: right is null");
	ERRORcheck(TYPEerror(BAThtype(l), BAThtype(r)), "BUN@1@2: incompatible head-types");
	ERRORcheck(TAILCHECK@1(l,r), "BUN@1@2: incompatible tail-types");

	if (BATcount(r) == 0) {
		return EMPTYr@2(l);
	} else if (BATcount(l) == 0) {
		return EMPTYl@2(l);
	}
	smaller = @2_size(l,r);
	bn = BATnew(BAThtype(l), BATttype(l), MAX(smaller,BATTINY));
	if (bn == NULL)
		return NULL;

	/* fill result bat bn */
	ALGODEBUG THRprintf(GDKout, "#BAT@1@2: BATins_@1@2(bn, l, r);\n");
	if (BATins_@1@2(bn, l, r) == NULL) {
		return NULL;
	}

	/* propagate alignment info */
	if (BATcount(bn)==BATcount(l)) {
		ALIGNset(bn, l);
	}
	if (RALIGN@2(bn, l, r)) {
		ALIGNsetH(bn, r);
	}
	bn->hsorted = BAThordered(l);
	bn->tsorted = BATtordered(l);
	if (BATcount(bn)){
		BATkey(bn, l->hkey);
		BATkey(BATmirror(bn), l->tkey);
	} else {
		BATkey(bn, TRUE);
		BATkey(BATmirror(bn), TRUE);
	}
	return bn;
}
@c
#define EMPTYldiff(l) BATclone(l,10)
#define EMPTYrdiff(l) BATcopy(l, l->htype, l->ttype, FALSE)
#define EMPTYlintersect(l) BATclone(l,10)
#define EMPTYrintersect(l) EMPTYlintersect(l)

#define intersect_size(l,r) MIN(BATcount(l), BATcount(r))
#define diff_size(l,r) BATcount(l)

@:batcheck(s,intersect,)@
@:batcheck(s,diff,-)@
@:batcheck(k,intersect,)@
@:batcheck(k,diff,-)@


@+ Union
Union also consists of two versions: @`BATkunion@5(l,r), which
unites with double elimination over the head column only, and
@`BATsunion@5(l,r), that looks at both columns. Their
implementation uses the s/kdiff() and s/kunique() code for efficient
double elimination.
@c
#define KEYk	TRUE
#define KEYs	FALSE

static BAT *
BATmaterialize_(BAT *b, size_t size)
{
	BAT *bn = BATnew(TYPE_oid, b->ttype, size);
	BUN p, q;
	int xx;
	oid base;

	if (bn == NULL)
		return NULL;
	base = b->hseqbase;
	if (base == oid_nil) {
		BATloopFast(b, p, q, xx) {
			bunfastins(bn, &base, BUNtail(b, p));
		}
	} else {
		BATloopFast(b, p, q, xx) {
			bunfastins(bn, &base, BUNtail(b, p));
			base++;
		}
	}
	ALIGNsetH(bn, b);
	ALIGNsetT(bn, b);
	return bn;
      bunins_failed:
	BBPreclaim(bn);
	return NULL;
}

@:union(k)@
@:union(s)@

@= bndense
	/* r and l maybe void */
	bn@1dense = (BAThdense(r)&BAThdense(l)&1) && ( !hdisjunct ||
			( ( *(@3*)BUN@2(r,BUNfirst(r)) - *(@3*)BUN@2(l,BUNlast(l)-BUNsize(l)) ) == (@3)1 ) );
	break;
@= union
BAT *
BAT@1union(BAT *l, BAT *r)
{
	int hdisjunct, tdisjunct, bnhdense, bntdense;
	BAT *bn, *b=0;
	BUN p,q;
	int xx;

	BATcompatible(l, r);
	if (BATcount(l) == 0) {
		BAT* swap = l;
		l = r;
		r = swap;
	}
	if (BATcount(r) == 0) {
		return BATcopy(l, l->htype, l->ttype, FALSE);
	}
	if (l->htype == TYPE_void && l->hseqbase != oid_nil) {
		bn = BATmaterialize_(l, BATcount(l)+BATcount(r));
	} else if (l->ttype == TYPE_void && l->tseqbase != oid_nil) {
		bn = BATmirror(BATmaterialize_(BATmirror(l),
					       BATcount(l)+BATcount(r)));
	} else {
		bn = BATcopy(l, l->htype, l->ttype, TRUE);
	}
	if( bn == NULL)
		return NULL;

	hdisjunct = (BAThordered(r)&BAThordered(l)&1) && (ATOMcmp(l->htype,
	      BUNhead(l,BUNlast(l)-BUNsize(l)), BUNhead(r,BUNfirst(r))) < 0);
	tdisjunct = (BATtordered(r)&BATtordered(l)&1) && (ATOMcmp(l->ttype,
	      BUNtail(l,BUNlast(l)-BUNsize(l)), BUNtail(r,BUNfirst(r))) < 0);

	/* for now, only oid can be dense;
	   later, bte, sht, int, wrd, lng might become dense, too */
	switch (bn->htype) {
	case TYPE_oid:
		@:bndense(h,head,oid)@
	default:
	        bnhdense = (BAThdense(r)&BAThdense(l)&1) & !hdisjunct;
	}
	switch (bn->ttype) {
	case TYPE_oid:
		@:bndense(t,tail,oid)@
	default:
		bntdense = (BATtdense(r)&BATtdense(l)&1) & !tdisjunct;
	}

	if (!hdisjunct) {
		b = r = BAT@1diff(r, bn);
		if (b == NULL) {
			BBPreclaim(bn);
			return NULL;
		}
	}
	BATloopFast(r,p,q,xx) {
		bunfastins(bn, BUNhead(r,p), BUNtail(r,p));
	}
	if (b)
		BBPreclaim(b);
	HASHdestroy(bn);

	/* set alignment info */
	if (!bnhdense) {
		bn->hseqbase = oid_nil;
		bn->hdense = 0;
	}
	if (!bntdense) {
		bn->tseqbase = oid_nil;
		bn->tdense = 0;
	}
	bn->hsorted = hdisjunct?GDK_SORTED:FALSE;
	bn->tsorted = tdisjunct?GDK_SORTED:FALSE;
	bn->talign = bn->halign = 0;
	if (KEY@1 == FALSE && hdisjunct == FALSE)
		BATkey(bn, FALSE);
	BATkey(BATmirror(bn), tdisjunct?(l->tkey&&r->tkey):0);

	return bn;
  bunins_failed:
	BBPreclaim(bn);
	return NULL;
}
@}
@-