gdk_search.c

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

		 * 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;
		}
	} else if (cmp == 0) {
		cur += bunsize;
	}
	return cur;
}

BUN
SORTfnd_flt(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,flt);
		if (cmp < 0) {
			lo = ++mid;
			cur += bunsize;
		} else if (cmp > 0) {
			hi = mid;
		} else {
			break;
		}
	}
	return cmp ? NULL : cur;
}



#line 805 "/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_dbl(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, dbl)>=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, dbl);
		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,dbl))
				break;
		}
		cur += bunsize;
	}
	return cur;
}

BUN
SORTfndlast_dbl(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, dbl)<=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,dbl);
		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,dbl))
				break;
		}
	} else if (cmp == 0) {
		cur += bunsize;
	}
	return cur;
}

BUN
SORTfnd_dbl(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,dbl);
		if (cmp < 0) {
			lo = ++mid;
			cur += bunsize;
		} else if (cmp > 0) {
			hi = mid;
		} else {
			break;
		}
	}
	return cmp ? NULL : cur;
}



#line 806 "/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_loc(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 || atom_CMP(BUNtloc(b, cur), v, b->ttype)>=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 = atom_CMP(BUNtloc(b, cur), v, b->ttype);
		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 (!atom_EQ(BUNtloc(b,cur),v,b->ttype))
				break;
		}
		cur += bunsize;
	}
	return cur;
}

BUN
SORTfndlast_loc(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 || atom_CMP(BUNtloc(b, cur-bunsize), v, b->ttype)<=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 = atom_CMP(BUNtloc(b,cur),v,b->ttype);
		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 (!atom_EQ(BUNtloc(b,cur),v,b->ttype))
				break;
		}
	} else if (cmp == 0) {
		cur += bunsize;
	}
	return cur;
}

BUN
SORTfnd_loc(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 = atom_CMP(BUNtloc(b,cur),v,b->ttype);
		if (cmp < 0) {
			lo = ++mid;
			cur += bunsize;
		} else if (cmp > 0) {
			hi = mid;
		} else {
			break;
		}
	}
	return cmp ? NULL : cur;
}



#line 807 "/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_var(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 || atom_CMP(BUNtvar(b, cur), v, b->ttype)>=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 = atom_CMP(BUNtvar(b, cur), v, b->ttype);
		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 (!atom_EQ(BUNtvar(b,cur),v,b->ttype))
				break;
		}
		cur += bunsize;
	}
	return cur;
}

BUN
SORTfndlast_var(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 || atom_CMP(BUNtvar(b, cur-bunsize), v, b->ttype)<=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 = atom_CMP(BUNtvar(b,cur),v,b->ttype);
		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 (!atom_EQ(BUNtvar(b,cur),v,b->ttype))
				break;
		}
	} else if (cmp == 0) {
		cur += bunsize;
	}
	return cur;
}

BUN
SORTfnd_var(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 = atom_CMP(BUNtvar(b,cur),v,b->ttype);
		if (cmp < 0) {
			lo = ++mid;
			cur += bunsize;
		} else if (cmp > 0) {
			hi = mid;
		} else {
			break;
		}
	}
	return cmp ? NULL : cur;
}



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



#line 756 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_search.mx"
BUN
SORTfnd(BAT *b, ptr v)
{
	if (b && b->hsorted&1) {
		switch(ATOMstorage(b->htype)) {
#ifndef NOEXPAND_CHR
		case TYPE_chr:
			return SORTfnd_chr(b,v);
#endif
#ifndef NOEXPAND_BTE
		case TYPE_bte:
			return SORTfnd_bte(b,v);
#endif
#ifndef NOEXPAND_SHT
		case TYPE_sht:
			return SORTfnd_sht(b,v);
#endif
#ifndef NOEXPAND_INT
		case TYPE_int:
			return SORTfnd_int(b,v);
#endif
#ifndef NOEXPAND_FLT
		case TYPE_flt:
			return SORTfnd_flt(b,v);
#endif
#ifndef NOEXPAND_DBL
		case TYPE_dbl:
			return SORTfnd_dbl(b,v);
#endif
#ifndef NOEXPAND_LNG
		case TYPE_lng:
			return SORTfnd_lng(b,v);
#endif
		default:
			if (b->hvarsized) {
				return SORTfnd_var(b,v);
			} else {
				return SORTfnd_loc(b,v);
			}
		}
	}
	return NULL;
}


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


#line 756 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_search.mx"
BUN
SORTfndlast(BAT *b, ptr v)
{
	if (b && b->tsorted&1) {
		switch(ATOMstorage(b->ttype)) {
#ifndef NOEXPAND_CHR
		case TYPE_chr:
			return SORTfndlast_chr(b,v);
#endif
#ifndef NOEXPAND_BTE
		case TYPE_bte:
			return SORTfndlast_bte(b,v);
#endif
#ifndef NOEXPAND_SHT
		case TYPE_sht:
			return SORTfndlast_sht(b,v);
#endif
#ifndef NOEXPAND_INT
		case TYPE_int:
			return SORTfndlast_int(b,v);
#endif
#ifndef NOEXPAND_FLT
		case TYPE_flt:
			return SORTfndlast_flt(b,v);
#endif
#ifndef NOEXPAND_DBL
		case TYPE_dbl:
			return SORTfndlast_dbl(b,v);
#endif
#ifndef NOEXPAND_LNG
		case TYPE_lng:
			return SORTfndlast_lng(b,v);
#endif
		default:
			if (b->tvarsized) {
				return SORTfndlast_var(b,v);
			} else {
				return SORTfndlast_loc(b,v);
			}
		}
	}
	return NULL;
}


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


#line 756 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_search.mx"
BUN
SORTfndfirst(BAT *b, ptr v)
{
	if (b && b->tsorted&1) {
		switch(ATOMstorage(b->ttype)) {
#ifndef NOEXPAND_CHR
		case TYPE_chr:
			return SORTfndfirst_chr(b,v);
#endif
#ifndef NOEXPAND_BTE
		case TYPE_bte:
			return SORTfndfirst_bte(b,v);
#endif
#ifndef NOEXPAND_SHT
		case TYPE_sht:
			return SORTfndfirst_sht(b,v);
#endif
#ifndef NOEXPAND_INT
		case TYPE_int:
			return SORTfndfirst_int(b,v);
#endif
#ifndef NOEXPAND_FLT
		case TYPE_flt:
			return SORTfndfirst_flt(b,v);
#endif
#ifndef NOEXPAND_DBL
		case TYPE_dbl:
			return SORTfndfirst_dbl(b,v);
#endif
#ifndef NOEXPAND_LNG
		case TYPE_lng:
			return SORTfndfirst_lng(b,v);
#endif
		default:
			if (b->tvarsized) {
				return SORTfndfirst_var(b,v);
			} else {
				return SORTfndfirst_loc(b,v);
			}
		}
	}
	return NULL;
}


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




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



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