radix.c

一个内存数据库的源代码这是服务器端还有客户端

	/* this accounts for 95% of processing cost; so it is optimized */
	int dst_bunsize = BUNsize(bn);
	int src_bunsize = BUNsize(b);
	int htpe = ATOMstorage(bn->htype);
	BUN src = start;

	if (b->htype == TYPE_void) {
		oid o = *(oid*) BUNhead(b,src);	/* void => oid materialization */
		while(src < end) {
			ptr p = BUNtloc(b,src);
			hash_t x = int_RADIX(p,mask) >> shift;
			BUN dst = base + cur[x];

			if (cur[x] == lim[x])
				break;
			*(oid*) BUNhloc(bn,dst) = o;
			if (o != oid_nil) o++;
			*(int*) BUNtloc(bn,dst) = *(int*) p;
			cur[x] += dst_bunsize; src += src_bunsize;
			int_CHECK(*maxbits, p);
		}
	} else if (htpe == TYPE_int) {	     /* most common case */
		while(src < end) {
			ptr p = BUNtloc(b,src);
			hash_t x = int_RADIX(p,mask) >> shift;
			BUN dst = base + cur[x];

			if (cur[x] == lim[x])
				break;
			*(int*) BUNhloc(bn,dst) = *(int*) BUNhloc(b,src);
			*(int*) BUNtloc(bn,dst) = *(int*) p;
			cur[x] += dst_bunsize; src += src_bunsize;
			int_CHECK(*maxbits, p);
		}
	} else
		while(src < end) {
			ptr p = BUNtloc(b,src);
			hash_t x = int_RADIX(p,mask) >> shift;
			BUN dst = base + cur[x];

			if (cur[x] == lim[x])
				break;
			ATOMput(htpe, bn->hheap, BUNhloc(bn,dst), BUNhead(b,src));
			*(int*) BUNtloc(bn,dst) = *(int*) p;
			cur[x] += dst_bunsize; src += src_bunsize;
			int_CHECK(*maxbits, p);
		}
	return src;
  bunins_failed:
	return NULL;
}


#line 1968 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/mal/radix.mx"


#line 1907 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/mal/radix.mx"
static BUN
radix_buns_lng(BAT *bn, BAT *b, BUN start, BUN end, BUN base,
	      size_t* cur, size_t* lim, size_t mask, int shift, oid *maxbits)
{
	/* this accounts for 95% of processing cost; so it is optimized */
	int dst_bunsize = BUNsize(bn);
	int src_bunsize = BUNsize(b);
	int htpe = ATOMstorage(bn->htype);
	BUN src = start;

	if (b->htype == TYPE_void) {
		oid o = *(oid*) BUNhead(b,src);	/* void => oid materialization */
		while(src < end) {
			ptr p = BUNtloc(b,src);
			hash_t x = lng_RADIX(p,mask) >> shift;
			BUN dst = base + cur[x];

			if (cur[x] == lim[x])
				break;
			*(oid*) BUNhloc(bn,dst) = o;
			if (o != oid_nil) o++;
			*(lng*) BUNtloc(bn,dst) = *(lng*) p;
			cur[x] += dst_bunsize; src += src_bunsize;
			lng_CHECK(*maxbits, p);
		}
	} else if (htpe == TYPE_int) {	     /* most common case */
		while(src < end) {
			ptr p = BUNtloc(b,src);
			hash_t x = lng_RADIX(p,mask) >> shift;
			BUN dst = base + cur[x];

			if (cur[x] == lim[x])
				break;
			*(int*) BUNhloc(bn,dst) = *(int*) BUNhloc(b,src);
			*(lng*) BUNtloc(bn,dst) = *(lng*) p;
			cur[x] += dst_bunsize; src += src_bunsize;
			lng_CHECK(*maxbits, p);
		}
	} else
		while(src < end) {
			ptr p = BUNtloc(b,src);
			hash_t x = lng_RADIX(p,mask) >> shift;
			BUN dst = base + cur[x];

			if (cur[x] == lim[x])
				break;
			ATOMput(htpe, bn->hheap, BUNhloc(bn,dst), BUNhead(b,src));
			*(lng*) BUNtloc(bn,dst) = *(lng*) p;
			cur[x] += dst_bunsize; src += src_bunsize;
			lng_CHECK(*maxbits, p);
		}
	return src;
  bunins_failed:
	return NULL;
}


#line 1969 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/mal/radix.mx"


static BUN
radix_buns_any(BAT *bn, BAT *b, BUN src, BUN end, BUN base, size_t * dst, size_t * lim, size_t mask, int shift, oid *maxbits)
{
	int dst_bunsize = BUNsize(bn);
	int src_bunsize = BUNsize(b);
	int htpe = BAThtype(b);
	int ttpe = BATttype(b);
	int any = ttpe;


#line 2000 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/mal/radix.mx"


		while (src < end) {
			hash_t x = any_RADIX(BUNtail(b, src), mask) >> shift;
			BUN p = base + dst[x];

			if (dst[x] == lim[x])
				break;
			ATOMput(htpe, bn->hheap, BUNhloc(bn, p), BUNhead(b, src));
			ATOMput(ttpe, bn->theap, BUNtloc(bn, p), BUNtail(b, src));
			dst[x] += dst_bunsize;
			src += src_bunsize;
		}
	*maxbits = 0;
	return src;
      bunins_failed:
	return NULL;
}



#line 2034 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/mal/radix.mx"

#line 2020 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/mal/radix.mx"
static void
cnt_buns_oid(BAT *bn, BAT *b, BUN src, BUN end, size_t *cnt,
	    size_t mask, int shift)
{
	int dst_bunsize = BUNsize(bn);
	int src_bunsize = BUNsize(b);

	/* count what's left for each chunk */
	for(src += b->tloc, end += b->tloc; src < end; src += src_bunsize) {
		hash_t x = oid_RADIX(src,mask) >> shift;
		cnt[x] += dst_bunsize;
	}
}


#line 2034 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/mal/radix.mx"


#line 2020 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/mal/radix.mx"
static void
cnt_buns_int(BAT *bn, BAT *b, BUN src, BUN end, size_t *cnt,
	    size_t mask, int shift)
{
	int dst_bunsize = BUNsize(bn);
	int src_bunsize = BUNsize(b);

	/* count what's left for each chunk */
	for(src += b->tloc, end += b->tloc; src < end; src += src_bunsize) {
		hash_t x = int_RADIX(src,mask) >> shift;
		cnt[x] += dst_bunsize;
	}
}


#line 2035 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/mal/radix.mx"


#line 2020 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/mal/radix.mx"
static void
cnt_buns_lng(BAT *bn, BAT *b, BUN src, BUN end, size_t *cnt,
	    size_t mask, int shift)
{
	int dst_bunsize = BUNsize(bn);
	int src_bunsize = BUNsize(b);

	/* count what's left for each chunk */
	for(src += b->tloc, end += b->tloc; src < end; src += src_bunsize) {
		hash_t x = lng_RADIX(src,mask) >> shift;
		cnt[x] += dst_bunsize;
	}
}


#line 2036 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/mal/radix.mx"


static void
cnt_buns_any(BAT *bn, BAT *b, BUN src, BUN end, size_t * cnt, size_t mask, int shift)
{
	int dst_bunsize = BUNsize(bn);
	int src_bunsize = BUNsize(b);
	int any = b->ttype;

	/* count what's left for each chunk */
	for (; src < end; src += src_bunsize) {
		hash_t x = any_RADIX(BUNtail(b, src), mask) >> shift;

		cnt[x] += dst_bunsize;
	}
}



#line 2109 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/mal/radix.mx"

#line 2054 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/mal/radix.mx"
static int
radix_chunk_oid(BAT *bn, BAT *b, BAT *limits, BUN start, BUN init, BUN end, BUN out,
	       size_t *lim, int nbits, int shift, size_t *dst, size_t *cnt, oid *maxbits)
{
	BUN lo_limit, hi_limit, cur;
	size_t ntuples = BUNindex(b,end)-BUNindex(b,start);
	size_t nchunks = (size_t) 1 << nbits;
	size_t chunksize = ntuples/nchunks;
	size_t i;
	size_t mask = (nchunks-1) << shift;
	move_t buf[512], *mov = (nchunks>512)?(move_t*)GDKmalloc(nchunks*sizeof(move_t)):buf;

	/* kick off with uniform boundaries */
	for (i=0; i<nchunks; i++) {
		lim[i] = chunksize*BUNsize(bn);
		ntuples -= chunksize;
	}
	for (i=0; ntuples > 0; ntuples--) {
		lim[i] += BUNsize(bn);
		if (++i >= nchunks)
			i = 0;
	}
	for (dst[0]=0,i=1; i<nchunks; i++) {
		dst[i] = lim[i-1];
		lim[i] += dst[i];
	}
	lo_limit = start + MAX((size_t) (0.1*(double)(init-start)), 20*nchunks*BUNsize(bn));
	hi_limit = MIN(start + (size_t) (0.9*(double)lim[i-1]), end - 32768);

	cur = radix_buns_oid(bn, b, start, init, out, dst, lim, mask, shift, maxbits);

	/* out of memory in some bucket: sample and continue */
	if (cur && cur < hi_limit && cur > lo_limit && limits == NULL) {
		sample_buns(bn, b, start, cur, end, dst, lim, cnt, nchunks);
		rearrange_chunks(bn, NULL, mov, out, dst, lim, cnt, nchunks);
		cur = radix_buns_oid(bn, b, cur, end, out, dst, lim, mask, shift, maxbits);
	}

	/* out of memory in some bucket: count and finish */
	if (cur) {
		if (cur < end) {
			memset(cnt, 0, nchunks*sizeof(size_t));
			cnt_buns_oid(bn, b, cur, end, cnt, mask, shift);
			rearrange_chunks(bn, limits, mov, out, dst, lim, cnt, nchunks);
			radix_buns_oid(bn, b, cur, end, out, dst, lim, mask, shift, maxbits);
		} else if (limits) {
			memset(cnt, 0, nchunks*sizeof(size_t));
			rearrange_chunks(bn, limits, mov, out, dst, lim, cnt, nchunks);
		}
	}
	if (nchunks>512)
		GDKfree(mov);
	return cur?0:-1;
}


#line 2109 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/mal/radix.mx"


#line 2054 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/mal/radix.mx"
static int
radix_chunk_int(BAT *bn, BAT *b, BAT *limits, BUN start, BUN init, BUN end, BUN out,
	       size_t *lim, int nbits, int shift, size_t *dst, size_t *cnt, oid *maxbits)
{
	BUN lo_limit, hi_limit, cur;
	size_t ntuples = BUNindex(b,end)-BUNindex(b,start);
	size_t nchunks = (size_t) 1 << nbits;
	size_t chunksize = ntuples/nchunks;
	size_t i;
	size_t mask = (nchunks-1) << shift;
	move_t buf[512], *mov = (nchunks>512)?(move_t*)GDKmalloc(nchunks*sizeof(move_t)):buf;

	/* kick off with uniform boundaries */
	for (i=0; i<nchunks; i++) {
		lim[i] = chunksize*BUNsize(bn);
		ntuples -= chunksize;
	}
	for (i=0; ntuples > 0; ntuples--) {
		lim[i] += BUNsize(bn);
		if (++i >= nchunks)
			i = 0;
	}
	for (dst[0]=0,i=1; i<nchunks; i++) {
		dst[i] = lim[i-1];
		lim[i] += dst[i];
	}
	lo_limit = start + MAX((size_t) (0.1*(double)(init-start)), 20*nchunks*BUNsize(bn));
	hi_limit = MIN(start + (size_t) (0.9*(double)lim[i-1]), end - 32768);

	cur = radix_buns_int(bn, b, start, init, out, dst, lim, mask, shift, maxbits);

	/* out of memory in some bucket: sample and continue */
	if (cur && cur < hi_limit && cur > lo_limit && limits == NULL) {
		sample_buns(bn, b, start, cur, end, dst, lim, cnt, nchunks);
		rearrange_chunks(bn, NULL, mov, out, dst, lim, cnt, nchunks);
		cur = radix_buns_int(bn, b, cur, end, out, dst, lim, mask, shift, maxbits);
	}

	/* out of memory in some bucket: count and finish */
	if (cur) {
		if (cur < end) {
			memset(cnt, 0, nchunks*sizeof(size_t));
			cnt_buns_int(bn, b, cur, end, cnt, mask, shift);
			rearrange_chunks(bn, limits, mov, out, dst, lim, cnt, nchunks);
			radix_buns_int(bn, b, cur, end, out, dst, lim, mask, shift, maxbits);
		} else if (limits) {
			memset(cnt, 0, nchunks*sizeof(size_t));
			rearrange_chunks(bn, limits, mov, out, dst, lim, cnt, nchunks);
		}
	}
	if (nchunks>512)
		GDKfree(mov);
	return cur?0:-1;
}


#line 2110 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/mal/radix.mx"


#line 2054 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/mal/radix.mx"
static int
radix_chunk_lng(BAT *bn, BAT *b, BAT *limits, BUN start, BUN init, BUN end, BUN out,
	       size_t *lim, int nbits, int shift, size_t *dst, size_t *cnt, oid *maxbits)
{
	BUN lo_limit, hi_limit, cur;
	size_t ntuples = BUNindex(b,end)-BUNindex(b,start);
	size_t nchunks = (size_t) 1 << nbits;
	size_t chunksize = ntuples/nchunks;
	size_t i;
	size_t mask = (nchunks-1) << shift;
	move_t buf[512], *mov = (nchunks>512)?(move_t*)GDKmalloc(nchunks*sizeof(move_t)):buf;

	/* kick off with uniform boundaries */
	for (i=0; i<nchunks; i++) {
		lim[i] = chunksize*BUNsize(bn);
		ntuples -= chunksize;
	}
	for (i=0; ntuples > 0; ntuples--) {
		lim[i] += BUNsize(bn);
		if (++i >= nchunks)
			i = 0;
	}
	for (dst[0]=0,i=1; i<nchunks; i++) {
		dst[i] = lim[i-1];
		lim[i] += dst[i];
	}
	lo_limit = start + MAX((size_t) (0.1*(double)(init-start)), 20*nchunks*BUNsize(bn));
	hi_limit = MIN(start + (size_t) (0.9*(double)lim[i-1]), end - 32768);

	cur = radix_buns_lng(bn, b, start, init, out, dst, lim, mask, shift, maxbits);

	/* out of memory in some bucket: sample and continue */
	if (cur && cur < hi_limit && cur > lo_limit && limits == NULL) {
		sample_buns(bn, b, start, cur, end, dst, lim, cnt, nchunks);
		rearrange_chunks(bn, NULL, mov, out, dst, lim, cnt, nchunks);
		cur = radix_buns_lng(bn, b, cur, end, out, dst, lim, mask, shift, maxbits);
	}

	/* out of memory in some bucket: count and finish */
	if (cur) {
		if (cur < end) {
			memset(cnt, 0, nchunks*sizeof(size_t));
			cnt_buns_lng(bn, b, cur, end, cnt, mask, shift);
			rearrange_chunks(bn, limits, mov, out, dst, lim, cnt, nchunks);
			radix_buns_lng(bn, b, cur, end, out, dst, lim, mask, shift, maxbits);
		} else if (limits) {
			memset(cnt, 0, nchunks*sizeof(size_t));
			rearrange_chunks(bn, limits, mov, out, dst, lim, cnt, nchunks);
		}
	}
	if (nchunks>512)
		GDKfree(mov);
	return cur?0:-1;
}


#line 2111 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/mal/radix.mx"


#line 2054 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/mal/radix.mx"
static int
radix_chunk_any(BAT *bn, BAT *b, BAT *limits, BUN start, BUN init, BUN end, BUN out,
	       size_t *lim, int nbits, int shift, size_t *dst, size_t *cnt, oid *maxbits)
{
	BUN lo_limit, hi_limit, cur;
	size_t ntuples = BUNindex(b,end)-BUNindex(b,start);
	size_t nchunks = (size_t) 1 << nbits;
	size_t chunksize = ntuples/nchunks;
	size_t i;
	size_t mask = (nchunks-1) << shift;
	move_t buf[512], *mov = (nchunks>512)?(move_t*)GDKmalloc(nchunks*sizeof(move_t)):buf;

	/* kick off with uniform boundaries */
	for (i=0; i<nchunks; i++) {
		lim[i] = chunksize*BUNsize(bn);
		ntuples -= chunksize;
	}
	for (i=0; ntuples > 0; ntuples--) {
		lim[i] += BUNsize(bn);
		if (++i >= nchunks)
			i = 0;
	}
	for (dst[0]=0,i=1; i<nchunks; i++) {
		dst[i] = lim[i-1];
		lim[i] += dst[i];
	}
	lo_limit = start + MAX((size_t) (0.1*(double)(init-start)), 20*nchunks*BUNsize(bn));
	hi_limit = MIN(start + (size_t) (0.9*(double)lim[i-1]), end - 32768);

	cur = radix_buns_any(bn, b, start, init, out, dst, lim, mask, shift, maxbits);

	/* out of memory in some bucket: sample and continue */
	if (cur && cur < hi_limit && cur > lo_limit && limits == NULL) {
		sample_buns(bn, b, start, cur, end, dst, lim, cnt, nchunks);
		rearrange_chunks(bn, NULL, mov, out, dst, lim, cnt, nchunks);
		cur = radix_buns_any(bn, b, cur, end, out, dst, lim, mask, shift, maxbits);
	}

	/* out of memory in some bucket: count and finish */
	if (cur) {
		if (cur < end) {
			memset(cnt, 0, nchunks*sizeof(size_t));
			cnt_buns_any(bn, b, cur, end, cnt, mask, shift);
			rearrange_chunks(bn, limits, mov, out, dst, lim, cnt, nchunks);
			radix_buns_any(bn, b, cur, end, out, dst, lim, mask, shift, maxbits);
		} else if (limits) {
			memset(cnt, 0, nchunks*sizeof(size_t));
			rearrange_chunks(bn, limits, mov, out, dst, lim, cnt, nchunks);
		}
	}
	if (nchunks>512)
		GDKfree(mov);
	return cur?0:-1;
}


#line 2112 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/mal/radix.mx"


static int
radix_cluster_va(BAT **ret, BAT *b, str nme, flt *perc, int *nbits, va_list ap)
{
	int shift = ABS(*nbits), total_shift, res = 0;
	size_t n;
	size_t cap = BATcount(b);
	int radix[MAXPARAMS], argc = 1, *p;
	size_t *lim;
	oid maxbits = 0;
	bat limitid = BBPindex(nme);
	BAT *bn = b, *limits = NULL;
	flt prc = *perc;
	/*va_list ap;*/

	if (limitid) {
		limits = BATdescriptor(limitid);