gdk_search.c

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

BUN
SORTfndlast_chr(BAT *b, ptr v)
{
	BUN end = BUNlast(b), cur = end;
	size_t lo = BUNindex(b,BUNfirst(b)), hi = BUNindex(b,end);
	int cmp = 1, bunsize = BUNsize(b);

        if (lo >= hi || simple_CMP(BUNtloc(b, cur-bunsize), v, chr)<=0) {
		/* shortcut: if BAT is empty or last (and hence all) tail
		 * value is <= v, we're done. */
		return cur;
	}
	while (lo < hi) {
		size_t mid = (lo+hi)>>1;
		cur = BUNptr(b, mid);
		cmp = simple_CMP(BUNtloc(b,cur),v,chr);
		if (cmp < 0) {
			lo = ++mid;
			cur += bunsize;
		} else if (cmp > 0) {
			hi = mid;
		} else {
			break;
		}
	}
	if (cmp == 0 && b->tkey == 0) {  /* shift over multiple equals */
		while((cur+=bunsize) < end) {
			if (!simple_EQ(BUNtloc(b,cur),v,chr))
				break;
		}
	} else if (cmp == 0) {
		cur += bunsize;
	}
	return cur;
}

BUN
SORTfnd_chr(BAT *m, ptr v)
{
	BAT *b = BATmirror(m);
	size_t lo = BUNindex(b,BUNfirst(b)), hi = BUNindex(b,BUNlast(b));
	int cmp = 1, bunsize = BUNsize(b);
	BUN cur = NULL;

	while (lo < hi) {
		size_t mid = (lo+hi)>>1;
		cur = BUNptr(b, mid);
		cmp = simple_CMP(BUNtloc(b,cur),v,chr);
		if (cmp < 0) {
			lo = ++mid;
			cur += bunsize;
		} else if (cmp > 0) {
			hi = mid;
		} else {
			break;
		}
	}
	return cmp ? NULL : cur;
}



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


#line 659 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_search.mx"
BUN
SORTfndfirst_bte(BAT *b, ptr v)
{
	BUN end = BUNfirst(b), cur = end;
	size_t lo = BUNindex(b,end), hi = BUNindex(b,BUNlast(b));
	int cmp = 1, bunsize = BUNsize(b);

        if (lo >= hi || simple_CMP(BUNtloc(b, cur), v, bte)>=0) {
		/* shortcut: if BAT is empty or first (and hence all) tail
		 * value is >= v, we're done. */
		return cur;
	}
	while (lo < hi) {
		size_t mid = (lo+hi)>>1;

		cur = BUNptr(b, mid);
		cmp = simple_CMP(BUNtloc(b, cur), v, bte);
		if (cmp < 0) {
			lo = ++mid;
			cur += bunsize;
		} else if (cmp > 0) {
			hi = mid;
		} else {
			break;
		}
	}
	if (cmp == 0 && b->tkey == 0) {  /* shift over multiple equals */
		while((cur-=bunsize) >= end) {
			if (!simple_EQ(BUNtloc(b,cur),v,bte))
				break;
		}
		cur += bunsize;
	}
	return cur;
}

BUN
SORTfndlast_bte(BAT *b, ptr v)
{
	BUN end = BUNlast(b), cur = end;
	size_t lo = BUNindex(b,BUNfirst(b)), hi = BUNindex(b,end);
	int cmp = 1, bunsize = BUNsize(b);

        if (lo >= hi || simple_CMP(BUNtloc(b, cur-bunsize), v, bte)<=0) {
		/* shortcut: if BAT is empty or last (and hence all) tail
		 * value is <= v, we're done. */
		return cur;
	}
	while (lo < hi) {
		size_t mid = (lo+hi)>>1;
		cur = BUNptr(b, mid);
		cmp = simple_CMP(BUNtloc(b,cur),v,bte);
		if (cmp < 0) {
			lo = ++mid;
			cur += bunsize;
		} else if (cmp > 0) {
			hi = mid;
		} else {
			break;
		}
	}
	if (cmp == 0 && b->tkey == 0) {  /* shift over multiple equals */
		while((cur+=bunsize) < end) {
			if (!simple_EQ(BUNtloc(b,cur),v,bte))
				break;
		}
	} else if (cmp == 0) {
		cur += bunsize;
	}
	return cur;
}

BUN
SORTfnd_bte(BAT *m, ptr v)
{
	BAT *b = BATmirror(m);
	size_t lo = BUNindex(b,BUNfirst(b)), hi = BUNindex(b,BUNlast(b));
	int cmp = 1, bunsize = BUNsize(b);
	BUN cur = NULL;

	while (lo < hi) {
		size_t mid = (lo+hi)>>1;
		cur = BUNptr(b, mid);
		cmp = simple_CMP(BUNtloc(b,cur),v,bte);
		if (cmp < 0) {
			lo = ++mid;
			cur += bunsize;
		} else if (cmp > 0) {
			hi = mid;
		} else {
			break;
		}
	}
	return cmp ? NULL : cur;
}



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


#line 659 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_search.mx"
BUN
SORTfndfirst_sht(BAT *b, ptr v)
{
	BUN end = BUNfirst(b), cur = end;
	size_t lo = BUNindex(b,end), hi = BUNindex(b,BUNlast(b));
	int cmp = 1, bunsize = BUNsize(b);

        if (lo >= hi || simple_CMP(BUNtloc(b, cur), v, sht)>=0) {
		/* shortcut: if BAT is empty or first (and hence all) tail
		 * value is >= v, we're done. */
		return cur;
	}
	while (lo < hi) {
		size_t mid = (lo+hi)>>1;

		cur = BUNptr(b, mid);
		cmp = simple_CMP(BUNtloc(b, cur), v, sht);
		if (cmp < 0) {
			lo = ++mid;
			cur += bunsize;
		} else if (cmp > 0) {
			hi = mid;
		} else {
			break;
		}
	}
	if (cmp == 0 && b->tkey == 0) {  /* shift over multiple equals */
		while((cur-=bunsize) >= end) {
			if (!simple_EQ(BUNtloc(b,cur),v,sht))
				break;
		}
		cur += bunsize;
	}
	return cur;
}

BUN
SORTfndlast_sht(BAT *b, ptr v)
{
	BUN end = BUNlast(b), cur = end;
	size_t lo = BUNindex(b,BUNfirst(b)), hi = BUNindex(b,end);
	int cmp = 1, bunsize = BUNsize(b);

        if (lo >= hi || simple_CMP(BUNtloc(b, cur-bunsize), v, sht)<=0) {
		/* shortcut: if BAT is empty or last (and hence all) tail
		 * value is <= v, we're done. */
		return cur;
	}
	while (lo < hi) {
		size_t mid = (lo+hi)>>1;
		cur = BUNptr(b, mid);
		cmp = simple_CMP(BUNtloc(b,cur),v,sht);
		if (cmp < 0) {
			lo = ++mid;
			cur += bunsize;
		} else if (cmp > 0) {
			hi = mid;
		} else {
			break;
		}
	}
	if (cmp == 0 && b->tkey == 0) {  /* shift over multiple equals */
		while((cur+=bunsize) < end) {
			if (!simple_EQ(BUNtloc(b,cur),v,sht))
				break;
		}
	} else if (cmp == 0) {
		cur += bunsize;
	}
	return cur;
}

BUN
SORTfnd_sht(BAT *m, ptr v)
{
	BAT *b = BATmirror(m);
	size_t lo = BUNindex(b,BUNfirst(b)), hi = BUNindex(b,BUNlast(b));
	int cmp = 1, bunsize = BUNsize(b);
	BUN cur = NULL;

	while (lo < hi) {
		size_t mid = (lo+hi)>>1;
		cur = BUNptr(b, mid);
		cmp = simple_CMP(BUNtloc(b,cur),v,sht);
		if (cmp < 0) {
			lo = ++mid;
			cur += bunsize;
		} else if (cmp > 0) {
			hi = mid;
		} else {
			break;
		}
	}
	return cmp ? NULL : cur;
}



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


#line 659 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_search.mx"
BUN
SORTfndfirst_int(BAT *b, ptr v)
{
	BUN end = BUNfirst(b), cur = end;
	size_t lo = BUNindex(b,end), hi = BUNindex(b,BUNlast(b));
	int cmp = 1, bunsize = BUNsize(b);

        if (lo >= hi || simple_CMP(BUNtloc(b, cur), v, int)>=0) {
		/* shortcut: if BAT is empty or first (and hence all) tail
		 * value is >= v, we're done. */
		return cur;
	}
	while (lo < hi) {
		size_t mid = (lo+hi)>>1;

		cur = BUNptr(b, mid);
		cmp = simple_CMP(BUNtloc(b, cur), v, int);
		if (cmp < 0) {
			lo = ++mid;
			cur += bunsize;
		} else if (cmp > 0) {
			hi = mid;
		} else {
			break;
		}
	}
	if (cmp == 0 && b->tkey == 0) {  /* shift over multiple equals */
		while((cur-=bunsize) >= end) {
			if (!simple_EQ(BUNtloc(b,cur),v,int))
				break;
		}
		cur += bunsize;
	}
	return cur;
}

BUN
SORTfndlast_int(BAT *b, ptr v)
{
	BUN end = BUNlast(b), cur = end;
	size_t lo = BUNindex(b,BUNfirst(b)), hi = BUNindex(b,end);
	int cmp = 1, bunsize = BUNsize(b);

        if (lo >= hi || simple_CMP(BUNtloc(b, cur-bunsize), v, int)<=0) {
		/* shortcut: if BAT is empty or last (and hence all) tail
		 * value is <= v, we're done. */
		return cur;
	}
	while (lo < hi) {
		size_t mid = (lo+hi)>>1;
		cur = BUNptr(b, mid);
		cmp = simple_CMP(BUNtloc(b,cur),v,int);
		if (cmp < 0) {
			lo = ++mid;
			cur += bunsize;
		} else if (cmp > 0) {
			hi = mid;
		} else {
			break;
		}
	}
	if (cmp == 0 && b->tkey == 0) {  /* shift over multiple equals */
		while((cur+=bunsize) < end) {
			if (!simple_EQ(BUNtloc(b,cur),v,int))
				break;
		}
	} else if (cmp == 0) {
		cur += bunsize;
	}
	return cur;
}

BUN
SORTfnd_int(BAT *m, ptr v)
{
	BAT *b = BATmirror(m);
	size_t lo = BUNindex(b,BUNfirst(b)), hi = BUNindex(b,BUNlast(b));
	int cmp = 1, bunsize = BUNsize(b);
	BUN cur = NULL;

	while (lo < hi) {
		size_t mid = (lo+hi)>>1;
		cur = BUNptr(b, mid);
		cmp = simple_CMP(BUNtloc(b,cur),v,int);
		if (cmp < 0) {
			lo = ++mid;
			cur += bunsize;
		} else if (cmp > 0) {
			hi = mid;
		} else {
			break;
		}
	}
	return cmp ? NULL : cur;
}



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


#line 659 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_search.mx"
BUN
SORTfndfirst_lng(BAT *b, ptr v)
{
	BUN end = BUNfirst(b), cur = end;
	size_t lo = BUNindex(b,end), hi = BUNindex(b,BUNlast(b));
	int cmp = 1, bunsize = BUNsize(b);

        if (lo >= hi || simple_CMP(BUNtloc(b, cur), v, lng)>=0) {
		/* shortcut: if BAT is empty or first (and hence all) tail
		 * value is >= v, we're done. */
		return cur;
	}
	while (lo < hi) {
		size_t mid = (lo+hi)>>1;

		cur = BUNptr(b, mid);
		cmp = simple_CMP(BUNtloc(b, cur), v, lng);
		if (cmp < 0) {
			lo = ++mid;
			cur += bunsize;
		} else if (cmp > 0) {
			hi = mid;
		} else {
			break;
		}
	}
	if (cmp == 0 && b->tkey == 0) {  /* shift over multiple equals */
		while((cur-=bunsize) >= end) {
			if (!simple_EQ(BUNtloc(b,cur),v,lng))
				break;
		}
		cur += bunsize;
	}
	return cur;
}

BUN
SORTfndlast_lng(BAT *b, ptr v)
{
	BUN end = BUNlast(b), cur = end;
	size_t lo = BUNindex(b,BUNfirst(b)), hi = BUNindex(b,end);
	int cmp = 1, bunsize = BUNsize(b);

        if (lo >= hi || simple_CMP(BUNtloc(b, cur-bunsize), v, lng)<=0) {
		/* shortcut: if BAT is empty or last (and hence all) tail
		 * value is <= v, we're done. */
		return cur;
	}
	while (lo < hi) {
		size_t mid = (lo+hi)>>1;
		cur = BUNptr(b, mid);
		cmp = simple_CMP(BUNtloc(b,cur),v,lng);
		if (cmp < 0) {
			lo = ++mid;
			cur += bunsize;
		} else if (cmp > 0) {
			hi = mid;
		} else {
			break;
		}
	}
	if (cmp == 0 && b->tkey == 0) {  /* shift over multiple equals */
		while((cur+=bunsize) < end) {
			if (!simple_EQ(BUNtloc(b,cur),v,lng))
				break;
		}
	} else if (cmp == 0) {
		cur += bunsize;
	}
	return cur;
}

BUN
SORTfnd_lng(BAT *m, ptr v)
{
	BAT *b = BATmirror(m);
	size_t lo = BUNindex(b,BUNfirst(b)), hi = BUNindex(b,BUNlast(b));
	int cmp = 1, bunsize = BUNsize(b);
	BUN cur = NULL;

	while (lo < hi) {
		size_t mid = (lo+hi)>>1;
		cur = BUNptr(b, mid);
		cmp = simple_CMP(BUNtloc(b,cur),v,lng);
		if (cmp < 0) {
			lo = ++mid;
			cur += bunsize;
		} else if (cmp > 0) {
			hi = mid;
		} else {
			break;
		}
	}
	return cmp ? NULL : cur;
}



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


#line 659 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_search.mx"
BUN
SORTfndfirst_flt(BAT *b, ptr v)
{
	BUN end = BUNfirst(b), cur = end;
	size_t lo = BUNindex(b,end), hi = BUNindex(b,BUNlast(b));
	int cmp = 1, bunsize = BUNsize(b);

        if (lo >= hi || simple_CMP(BUNtloc(b, cur), v, flt)>=0) {
		/* shortcut: if BAT is empty or first (and hence all) tail
		 * value is >= v, we're done. */
		return cur;
	}
	while (lo < hi) {
		size_t mid = (lo+hi)>>1;

		cur = BUNptr(b, mid);
		cmp = simple_CMP(BUNtloc(b, cur), v, flt);
		if (cmp < 0) {
			lo = ++mid;
			cur += bunsize;
		} else if (cmp > 0) {
			hi = mid;
		} else {
			break;
		}
	}
	if (cmp == 0 && b->tkey == 0) {  /* shift over multiple equals */
		while((cur-=bunsize) >= end) {
			if (!simple_EQ(BUNtloc(b,cur),v,flt))
				break;
		}
		cur += bunsize;
	}
	return cur;
}

BUN
SORTfndlast_flt(BAT *b, ptr v)
{
	BUN end = BUNlast(b), cur = end;
	size_t lo = BUNindex(b,BUNfirst(b)), hi = BUNindex(b,end);
	int cmp = 1, bunsize = BUNsize(b);

        if (lo >= hi || simple_CMP(BUNtloc(b, cur-bunsize), v, flt)<=0) {
		/* shortcut: if BAT is empty or last (and hence all) tail