gdk_setop.c

来自「这个是内存数据库中的一个管理工具」· C语言 代码 · 共 2,964 行 · 第 1/5 页

			}
		}
	}


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

	if (unique && bn->batSet == FALSE) {
		/* we inserted unique BUNs into an empty BAT;
		   hence, the resulting BAT is (now) unique/set ... */
		BATset(bn,TRUE);
	}
	return bn;
      bunins_failed:
	BBPreclaim(bn);
	return NULL;
}




#line 260 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_setop.mx"
BAT *
BATkunique(BAT *b)
{
	BAT *bn;

	BATcheck(b, "BATkunique:");

	if (b->hkey) {
		bn = BATcopy(b, b->htype, b->ttype, FALSE);
	} else {
		size_t cnt = BATcount(b);

		if (cnt > 10000) {
			BAT *tmp2 = NULL, *tmp1, *tmp0 = VIEWhead_(b, BAT_WRITE);

			if (tmp0) {
				tmp1 = BATsample(b, 1000);
				if (tmp1) {
					tmp2 = BATkunique(tmp1);
					if (tmp2) {
						cnt = (size_t) ((((lng) BATcount(tmp2)) * cnt) / 900);
						BBPreclaim(tmp2);
					}
					BBPreclaim(tmp1);
				}
				BBPreclaim(tmp0);
			}
			if (tmp2 == NULL)
				return NULL;
		}
		bn = BATnew(BAThtype(b), BATttype(b), cnt);
		if (bn == NULL || BATins_kunique(bn, b) == NULL)
			return NULL;
	}

	/* property management */
	if (b->halign == 0) {
		b->halign = OIDnew(1);
	}
	BATkey(bn, TRUE);	/* this we accomplished */
	BATkey(BATmirror(bn), b->tkey);
	bn->hsorted = BAThordered(b);
	bn->tsorted = BATtordered(b);
	if (BATcount(bn) == BATcount(b)) {
		ALIGNset(bn, b);
	}
	return bn;
}

BAT *
BATukunique(BAT *b)
{
	BAT *v, *bn;

	BATcheck(b, "BATukunique:");
	bn = BATkunique(v = VIEWhead(b));
	BBPreclaim(v);
	return bn;
}

BAT *
BATsunique(BAT *b)
{
	BAT *bn;

	BATcheck(b, "BATsnique:");

	if (b->hkey || b->tkey || b->batSet) {
		bn = BATcopy(b, b->htype, b->ttype, FALSE);
	} else {
		size_t cnt = BATcount(b);

		if (cnt > 10000) {
			BAT *tmp2 = NULL, *tmp1 = BATsample(b, 1000);

			if (tmp1) {
				tmp2 = BATkunique(tmp1);
				if (tmp2) {
					cnt = BATcount(tmp2) * (cnt / 1000);
					BBPreclaim(tmp2);
				}
				BBPreclaim(tmp1);
			}
			if (tmp2 == NULL)
				return NULL;
		}
		bn = BATnew(BAThtype(b), BATttype(b), cnt);
		if (bn == NULL || BATins_sunique(bn, b) == NULL)
			return NULL;
	}

	/* property management */
	BATset(bn, TRUE);	/* this we accomplished */
	BATkey(bn, b->hkey);
	BATkey(BATmirror(bn), b->tkey);
	bn->hsorted = BAThordered(b);
	bn->tsorted = BATtordered(b);
	if (BATcount(bn) == BATcount(b)) {
		ALIGNset(bn, b);
	}
	return bn;
}



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


#line 660 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_setop.mx"
#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)


#line 534 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_setop.mx"
static BAT*
BATins_sintersect(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 (FLIPs(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)) {
		
#line 447 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_setop.mx"
	{
		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_intersects: voidcheck[intersect, s];\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);
				MISSintersect(h,t);
				ll++;
				p1 += s1;
			}
			while(p1 < hit_end) {
				t = BUNtail(l,p1);
				t2 = BUNtail(r,w);
				if (EQUALs(t,t2)) {
					HITintersect(h,t);
				} else {
					MISSintersect(h,t);
				}
				ll++;
				p1 += s1;
				w += s2;
			}
			while(p1 < q1) {
				t = BUNtail(l,p1);
				MISSintersect(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 (EQUALs(t,t2)) {
						HITintersect(h, t);
						continue;
					}
				}
				MISSintersect(h,t);
			}
		}
	}



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

	} else {
		switch(ATOMstorage(r->htype)) {
#ifndef NOEXPAND_CHR
			case TYPE_chr:
				
#line 524 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_setop.mx"
	if (BAThdense(l)) {
		
#line 415 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_setop.mx"
	BUN p1, q1, w;
	int ins, s1;
	hash_t s2;
	ptr h, t, t2 = NULL, h2 = hnil;

	ALGODEBUG THRprintf(GDKout, "#BATins_intersectpos: hashcheck[intersect, pos, loc, _chr, s];\n");
	pin = 1;
	BATmmap_pin(r);
	if (BATprepareHash(r))
		goto bunins_failed;
	BATloopFast(l, p1, q1, s1) {
		h = BUNhpos(l, p1);
		t = BUNtail(l,p1);
		ins = TRUE;
		if (TRUE) /* check for not-nil (nils don't match anyway) */
			HASHloop_chr(r, r->hhash, s2, h, w) {
				t2 = BUNtail(r,w);
				if (EQUALs(t,t2)) {
					HITintersect(h, t);
					ins = FALSE;
					break;
				}
			}
		if (!ins)
			continue;
		MISSintersect(h,t);
	}
	if (t2 || h2)
		ins = 0;	       /* dummy action for the compiler */
	BATmmap_unpin(r);



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

	} else if (hash) {
		
#line 415 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_setop.mx"
	BUN p1, q1, w;
	int ins, s1;
	hash_t s2;
	ptr h, t, t2 = NULL, h2 = hnil;

	ALGODEBUG THRprintf(GDKout, "#BATins_intersectloc: hashcheck[intersect, loc, loc, _chr, s];\n");
	pin = 1;
	BATmmap_pin(r);
	if (BATprepareHash(r))
		goto bunins_failed;
	BATloopFast(l, p1, q1, s1) {
		h = BUNhloc(l, p1);
		t = BUNtail(l,p1);
		ins = TRUE;
		if (simple_CMP(h,h2,chr)) /* check for not-nil (nils don't match anyway) */
			HASHloop_chr(r, r->hhash, s2, h, w) {
				t2 = BUNtail(r,w);
				if (EQUALs(t,t2)) {
					HITintersect(h, t);
					ins = FALSE;
					break;
				}
			}
		if (!ins)
			continue;
		MISSintersect(h,t);
	}
	if (t2 || h2)
		ins = 0;	       /* dummy action for the compiler */
	BATmmap_unpin(r);



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

	} else {
		
#line 373 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_setop.mx"
	BUN p1 = BUNfirst(l), p2 = BUNfirst(r);
	BUN q1 = BUNlast(l),  q2 = BUNlast(r);
	int s1 = BUNsize(l),  s2 = BUNsize(r);

	ALGODEBUG THRprintf(GDKout, "#BATins_intersectloc: mergecheck[intersect, loc, _chr, simple_CMP(h,h2,chr), s];\n");
	if (p2 < q2) BATloopFast(l, p1, q1, s1) {
		ptr  h = BUNhloc(l,p1);
		ptr  t = BUNtail(l,p1);
		ptr h2 = BUNhloc(r,p2);
		int c;
		while ((c = simple_CMP(h,h2,chr)) > 0) {
			if ((p2 += s2) >= q2)
				goto endloc_chr;
			h2 = BUNhloc(r,p2);
		}
		if (c == 0) {
			h2 = hnil;
			if (simple_CMP(h,h2,chr)) { /* check for not-nil (nils don't match anyway) */
				BUN pb = p2;
				for (;;) {
					if (EQUALs(t, BUNtail(r,pb))) {
						HITintersect(h, t);
						break;
					}
					if ((pb += s2) >= q2) {
						MISSintersect(h, t);
						break;
					}
					h2 = BUNhloc(r,pb);
					if (simple_CMP(h,h2,chr)) {
						MISSintersect(h, t);
						break;
					}
				}
				continue;
			}
		}
		MISSintersect(h, t);
	}
  endloc_chr:;
	ENDintersect(BUNhloc(l,p1), BUNtail(l,p1));


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

	}
	break;



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

#endif
#ifndef NOEXPAND_BTE
			case TYPE_bte:
				
#line 524 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_setop.mx"
	if (BAThdense(l)) {
		
#line 415 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_setop.mx"
	BUN p1, q1, w;
	int ins, s1;
	hash_t s2;
	ptr h, t, t2 = NULL, h2 = hnil;

	ALGODEBUG THRprintf(GDKout, "#BATins_intersectpos: hashcheck[intersect, pos, loc, _bte, s];\n");
	pin = 1;
	BATmmap_pin(r);
	if (BATprepareHash(r))
		goto bunins_failed;
	BATloopFast(l, p1, q1, s1) {
		h = BUNhpos(l, p1);
		t = BUNtail(l,p1);
		ins = TRUE;
		if (TRUE) /* check for not-nil (nils don't match anyway) */
			HASHloop_bte(r, r->hhash, s2, h, w) {
				t2 = BUNtail(r,w);
				if (EQUALs(t,t2)) {
					HITintersect(h, t);
					ins = FALSE;
					break;
				}
			}
		if (!ins)
			continue;
		MISSintersect(h,t);
	}
	if (t2 || h2)
		ins = 0;	       /* dummy action for the compiler */
	BATmmap_unpin(r);



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

	} else if (hash) {
		
#line 415 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_setop.mx"
	BUN p1, q1, w;
	int ins, s1;
	hash_t s2;
	ptr h, t, t2 = NULL, h2 = hnil;

	ALGODEBUG THRprintf(GDKout, "#BATins_intersectloc: hashcheck[intersect, loc, loc, _bte, s];\n");
	pin = 1;
	BATmmap_pin(r);
	if (BATprepareHash(r))
		goto bunins_failed;
	BATloopFast(l, p1, q1, s1) {
		h = BUNhloc(l, p1);
		t = BUNtail(l,p1);
		ins = TRUE;
		if (simple_CMP(h,h2,bte)) /* check for not-nil (nils don't match anyway) */
			HASHloop_bte(r, r->hhash, s2, h, w) {
				t2 = BUNtail(r,w);
				if (EQUALs(t,t2)) {
					HITintersect(h, t);
					ins = FALSE;
					break;
				}
			}
		if (!ins)
			continue;
		MISSintersect(h,t);
	}
	if (t2 || h2)
		ins = 0;	       /* dummy action for the compiler */
	BATmmap_unpin(r);



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

	} else {
		
#line 373 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_setop.mx"
	BUN p1 = BUNfirst(l), p2 = BUNfirst(r);
	BUN q1 = BUNlast(l),  q2 = BUNlast(r);
	int s1 = BUNsize(l),  s2 = BUNsize(r);

	ALGODEBUG THRprintf(GDKout, "#BATins_intersectloc: mergecheck[intersect, loc, _bte, simple_CMP(h,h2,bte), s];\n");
	if (p2 < q2) BATloopFast(l, p1, q1, s1) {
		ptr  h = BUNhloc(l,p1);
		ptr  t = BUNtail(l,p1);
		ptr h2 = BUNhloc(r,p2);
		int c;
		while ((c = simple_CMP(h,h2,bte)) > 0) {
			if ((p2 += s2) >= q2)
				goto endloc_bte;
			h2 = BUNhloc(r,p2);
		}
		if (c == 0) {
			h2 = hnil;
			if (simple_CMP(h,h2,bte)) { /* check for not-nil (nils don't match anyway) */
				BUN pb = p2;
				for (;;) {
					if (EQUALs(t, BUNtail(r,pb))) {
						HITintersect(h, t);
						break;
					}
					if ((pb += s2) >= q2) {
						MISSintersect(h, t);
						break;
					}
					h2 = BUNhloc(r,pb);
					if (simple_CMP(h,h2,bte)) {
						MISSintersect(h, t);
						break;
					}
				}
				continue;
			}
		}
		MISSintersect(h, t);
	}
  endloc_bte:;
	ENDintersect(BUNhloc(l,p1), BUNtail(l,p1));


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

	}
	break;



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

#endif
#ifndef NOEXPAND_SHT
			case TYPE_sht:
				
#line 524 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_setop.mx"
	if (BAThdense(l)) {
		
#line 415 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_setop.mx"
	BUN p1, q1, w;
	int ins, s1;
	hash_t s2;
	ptr h, t, t2 = NULL, h2 = hnil;

	ALGODEBUG THRprintf(GDKout, "#BATins_intersectpos: hashcheck[intersect, pos, loc, _sht, s];\n");
	pin = 1;
	BATmmap_pin(r);
	if (BATprepareHash(r))
		goto bunins_failed;
	BATloopFast(l, p1, q1, s1) {
		h = BUNhpos(l, p1);
		t = BUNtail(l,p1);
		ins = TRUE;
		if (TRUE) /* check for not-nil (nils don't match anyway) */
			HASHloop_sht(r, r->hhash, s2, h, w) {
				t2 = BUNtail(r,w);
				if (EQUALs(t,t2)) {
					HITintersect(h, t);
					ins = FALSE;
					break;
				}
			}
		if (!ins)
			continue;
		MISSintersect(h,t);
	}
	if (t2 || h2)
		ins = 0;	       /* dummy action for the compiler */
	BATmmap_unpin(r);



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

	} else if (hash) {
		
#line 415 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_setop.mx"
	BUN p1, q1, w;
	int ins, s1;
	hash_t s2;
	ptr h, t, t2 = NULL, h2 = hnil;

	ALGODEBUG THRprintf(GDKout, "#BATins_intersectloc: hashcheck[intersect, loc, loc, _sht, s];\n");
	pin = 1;
	BATmmap_pin(r);
	if (BATprepareHash(r))
		goto bunins_failed;
	BATloopFast(l, p1, q1, s1) {
		h = BUNhloc(l, p1);
		t = BUNtail(l,p1);
		ins = TRUE;
		if (simple_CMP(h,h2,sht)) /* check for not-nil (nils don't match anyway) */
			HASHloop_sht(r, r->hhash, s2,