radix.c

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

#line 1237 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/mal/radix.mx"
#include "mal_config.h"
#include "mal.h"
#include "mal_exception.h"
#include "mal_interpreter.h"  /* for getArgReference() */
#include <math.h>

#include "radix.h"


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


#ifdef HAVE_XMMINTRIN_H 
/* constants for use with _mm_prefetch */
#include <xmmintrin.h>
#endif

/* math.h files do not have M_PI/M_E defined */
#ifndef M_PI
# define M_PI		3.14159265358979323846	/* pi */
#endif
#ifndef M_E
# define M_E		2.7182818284590452354	/* e */
#endif

#define int_HUSSLE(x)	(((x)>>7)^((x)>>13)^((x)>>21)^(x))



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

int
M4_RDX_BATuniform(BAT **bn, oid *base, int *size, int *domain)
{
	size_t n = (size_t) * size, i, r;
	BAT *b = NULL;
	char *firstbun;
	int bunsize;		/* initialized in BATloopFast */
	oid bs = *base;
	int j = 0;
	BUN p, q;

	if (*size < 0) {
		GDKerror("BATuniform: size must not be negative");
		return GDK_FAIL;
	}

	b = BATnew(TYPE_oid, TYPE_int, n);
	if (b == NULL)
		return GDK_FAIL;
	if (n == 0) {
		b->tsorted = GDK_SORTED;
		b->hsorted = GDK_SORTED;
		b->hdense = TRUE;
		BATseqbase(b, *base);
		BATkey(b, TRUE);
		BATkey(BATmirror(b), TRUE);
		*bn = b;
		return GDK_SUCCEED;
	}

	firstbun = (char *) BUNfirst(b);
	/* preset b->batBuns->free to make BATloopFast work */
	b->batBuns->free = n * BUNsize(b);
	BATsetcount(b, n);
	/* create BUNs with uniform distribution */
	BATloopFast(b, p, q, bunsize) {
		*(oid *) BUNhloc(b, p) = bs ++;

		*(int *) BUNtloc(b, p) = j;
		if (++j >= *domain)
			j = 0;
	}
	/* mix BUNs randomly */
	for (r = i = 0; i < n; i++) {
		size_t idx = i + ((r += rand()) % (n - i));
		int val;

		p = (BUN) (firstbun + i * bunsize);	/* fast version of BUNptr */
		q = (BUN) (firstbun + idx * bunsize);
		val = *(int *) BUNtloc(b, p);
		*(int *) BUNtloc(b, p) = *(int *) BUNtloc(b, q);
		*(int *) BUNtloc(b, q) = val;
	}
	b->tsorted = FALSE;
	b->hdense = TRUE;
	BATseqbase(b, *base);
	BATkey(b, TRUE);
	*bn = b;
	return GDK_SUCCEED;
}

int
M4_RDX_BATuniform_b(BAT **bn, int *size, int *domain)
{
	oid base = 0;
	return M4_RDX_BATuniform(bn, &base, size, domain);
}

int
M4_RDX_BATuniform_bd(BAT **bn, int *size)
{
	oid base = 0;
	return M4_RDX_BATuniform(bn, &base, size, size);
}

int
M4_RDX_BATnormal(BAT **bn, oid *base, int *size, int *domain, int *stddev, int *mean)
{
	size_t n = (size_t) * size, i;
	unsigned int r = (unsigned int) n;
	size_t d = (size_t) * domain;
	BAT *b = NULL;
	char *firstbun;
	int bunsize;
	BUN p, q;
	int m = *mean, s = *stddev;
	oid bs = *base;
	int *itab;
	flt *ftab, tot = 0.0;

	if (*size < 0) {
		GDKerror("BATnormal: size must not be negative");
		return GDK_FAIL;
	}

        b = BATnew(TYPE_oid, TYPE_int, n);
	if (b == NULL)
		return GDK_FAIL;
	if (n == 0) {
		b->tsorted = GDK_SORTED;
		b->hsorted = GDK_SORTED;
		b->hdense = TRUE;
		BATseqbase(b, *base);
		BATkey(b, TRUE);
		BATkey(BATmirror(b), TRUE);
		*bn = b;
		return GDK_SUCCEED;
	}

	firstbun = (char *) BUNfirst(b);
	itab = (int *) GDKmalloc(d * sizeof(int));
	ftab = (flt *) itab;

	/* assert(0 <= *mean && *mean < *size); */

	/* created inverted table */
	for (i = 0; i < d; i++) {
		dbl tmp = (dbl) ((i - m) * (i - m));

		tmp = pow(M_E, -tmp / (2 * s * s)) / sqrt(2 * M_PI * s * s);
		ftab[i] = (flt) tmp;
		tot += ftab[i];
	}
	for (tot = (flt) (1.0 / tot), i = 0; i < d; i++) {
		itab[i] = (int) ((flt) n * ftab[i] * tot);
		r -= itab[i];
	}
	itab[m] += r;

	/* preset b->batBuns->free to make BATloopFast work */
	b->batBuns->free = n * BUNsize(b);
	BATsetcount(b, n);
	/* create BUNs with normal distribution */
	BATloopFast(b, p, q, bunsize) {
		*(oid *) BUNhloc(b, p) = bs ++;

		while (itab[r] == 0)
			r++;
		itab[r]--;
		*(int *) BUNtloc(b, p) = (int) r;
	}
	GDKfree(itab);

	/* mix BUNs randomly */
	for (r = 0, i = 0; i < n; i++) {
		size_t idx = i + ((r += rand()) % (n - i));
		int val;

		p = (BUN) (firstbun + i * bunsize);	/* fast version of BUNptr */
		q = (BUN) (firstbun + idx * bunsize);
		val = *(int *) BUNtloc(b, p);
		*(int *) BUNtloc(b, p) = *(int *) BUNtloc(b, q);
		*(int *) BUNtloc(b, q) = val;
	}
	b->tsorted = FALSE;
	b->hdense = TRUE;
	BATseqbase(b, *base);
	BATkey(b, TRUE);
	*bn = b;
	return GDK_SUCCEED;
}

int
M4_RDX_BATnormal_b(BAT **bn, int *size, int *domain, int *stddev, int *mean)
{
	oid base = 0;
	return M4_RDX_BATnormal(bn, &base, size, domain, stddev, mean);
}

int
M4_RDX_BATnormal_m(BAT **bn, oid *base, int *size, int *domain, int *stddev)
{
	int mean = *domain / 2;
	return M4_RDX_BATnormal(bn, base, size, domain, stddev, &mean);
}

int
M4_RDX_BATnormal_bm(BAT **bn, int *size, int *domain, int *stddev)
{
	oid base = 0;
	int mean = *domain / 2;
	return M4_RDX_BATnormal(bn, &base, size, domain, stddev, &mean);
}

int
M4_RDX_BATnormal_vm(BAT **bn, oid *base, int *size, int *domain)
{
	int stddev = *domain / 10;
	int mean = *domain / 2;
	return M4_RDX_BATnormal(bn, base, size, domain, &stddev, &mean);
}

int
M4_RDX_BATnormal_bvm(BAT **bn, int *size, int *domain)
{
	oid base = 0;
	int stddev = *domain / 10;
	int mean = *domain / 2;
	return M4_RDX_BATnormal(bn, &base, size, domain, &stddev, &mean);
}

int
M4_RDX_BATnormal_dvm(BAT **bn, oid *base, int *size)
{
	int domain = *size;
	int stddev = domain / 10;
	int mean = domain / 2;
	return M4_RDX_BATnormal(bn, base, size, &domain, &stddev, &mean);
}

int
M4_RDX_BATnormal_bdvm(BAT **bn, int *size)
{
	oid base = 0;
	int domain = *size;
	int stddev = domain / 10;
	int mean = domain / 2;
	return M4_RDX_BATnormal(bn, &base, size, &domain, &stddev, &mean);
}



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





#line 1759 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/mal/radix.mx"
#define any_RADIX(p,rd) ((hash_t)((*BATatoms[any].atomHash)(p) & rd))
#define oid_RADIX(p,rd) ((hash_t) *(oid*) (p) & rd)
#define int_RADIX(p,rd) ((hash_t)int_HUSSLE(*(unsigned int*) (p)) & rd)
#define lng_RADIX(p,rd) ((hash_t)int_HUSSLE(((unsigned int*)(p))[0]^((unsigned int*)(p))[1]) & rd)

typedef struct {
	size_t src;		/* offset of chunk where it is now */
	size_t dst;		/* offset of chunk where it should go */
	size_t size;		/* size of chunk (in bytes) */
} move_t;


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

#define HTYPE(b) BAThtype(b)
#define TTYPE(b) HTYPE(BATmirror(b))

static BAT *
quickbat(BAT *b, size_t cap)
{
	BAT *bn = BATnew(HTYPE(b), BATttype(b), cap);

	if (bn == NULL)
		return NULL;
	bn->hsorted = bn->tsorted = 0;
	if (b->hkey)
		BATkey(bn, TRUE);
	if (b->tkey)
		BATkey(BATmirror(bn), TRUE);
	return bn;
}

/* take care: block sequences that are copied to the right should be done from
 *	      right to left; and vice versa! Otherwise you overwrite blocks.
 */
static void
move_chunks(move_t *mov, BUN base, size_t from, size_t end)
{
	assert(((ssize_t) end) >= 0);	/* make sure that cop=(ssize_t)from does not overflow */
	while (from < end) {
		ssize_t cur, cop = (ssize_t) from;

		while (++from < end) {
			if (mov[from].src >= mov[from].dst)
				break;
		}
		for (cur = from - 1; cur >= cop; cur--) {
			if (mov[cur].size) {
				memcpy(base + mov[cur].dst, base + mov[cur].src, mov[cur].size);
			}
		}
	}
}

static void
rearrange_chunks(BAT *b, BAT *limits, move_t *mov, BUN base, size_t * dst, size_t * lim, size_t * cnt, size_t n)
{
	size_t i, cur = 0, start = 0;
	ssize_t id = -1;

	if (limits && BATcount(limits)) {
		id = *(ssize_t *) BUNhloc(limits, BUNlast(limits) - BUNsize(limits));
	}
	for (i = 0; i < n; i++) {
		size_t end = dst[i];
		size_t siz = end - start;
		size_t nxt = cur + siz + cnt[i];

		if (start <= cur && end >= cur) {
			/* overlap at start of cur */
			mov[i].src = start;
			mov[i].dst = end;
			mov[i].size = cur - start;
			if (limits) {
				ssize_t i0 = ++id;
				size_t i1 = BUNindex(b, ((start == cur) ? nxt : end));
				size_t i2 = i1 - BUNindex(b, cur);
				size_t i3 = BUNindex(b, nxt) - i1;

				BUNins(limits, &i0, &i2, FALSE);
				if (i3)
					BUNins(limits, &i0, &i3, FALSE);
			}
		} else if (start >= cur && start <= nxt) {
			/* overlap just before nxt */
			size_t hole = start - cur;

			if (hole > siz)
				hole = siz;
			mov[i].src = end - hole;
			mov[i].dst = cur;
			mov[i].size = hole;
			if (limits) {
				ssize_t i0 = ++id;
				size_t i1 = BUNindex(b, cur + hole);
				size_t i2 = i1 - BUNindex(b, cur);
				size_t i3 = BUNindex(b, nxt) - i1;

				if (i2)
					BUNins(limits, &i0, &i2, FALSE);
				BUNins(limits, &i0, &i3, FALSE);
			}
		} else {
			/* no overlap: copy all */
			mov[i].src = start;
			mov[i].dst = cur;
			mov[i].size = siz;
			if (limits) {
				ssize_t i0 = ++id;
				size_t i1 = BUNindex(b, cur);
				size_t i2 = BUNindex(b, nxt) - i1;

				BUNins(limits, &i0, &i2, FALSE);
			}
		}
		start = lim[i];
		lim[i] = cur = nxt;
		dst[i] = nxt - cnt[i];
	}
	move_chunks(mov, base, 0, n);
}

static void
sample_buns(BAT *bn, BAT *b, BUN src, BUN cur, BUN end, size_t * dst, size_t * lim, size_t * cnt, size_t n)
{
	size_t ntuples = (end - src) / BUNsize(b);
	size_t done = (cur - src) / BUNsize(b);
	int bunsize = BUNsize(bn);
	size_t total = (ntuples - done);
	size_t i, oldlim;

	/* extrapolate all processed buns as if they were a sample */
	for (oldlim = i = 0; i < n; oldlim = lim[i], i++) {
		cnt[i] = (((dst[i] - oldlim) / bunsize) * (ntuples - done)) / done;
		total -= cnt[i];
		cnt[i] *= bunsize;
	}

	/* add left-overs */
	for (i = 0; total > 0; total--) {
		cnt[i] += bunsize;
		if (++i >= n)
			i = 0;
	}
}




#line 1963 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/mal/radix.mx"
#define lng_CHECK(dst,v) dst = 0	/* dummy */
#define int_CHECK(dst,v) dst = 0	/* dummy */
#define oid_CHECK(dst,v) dst |= *(oid*) (v)


#line 1907 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/mal/radix.mx"
static BUN
radix_buns_oid(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 = oid_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++;
			*(oid*) BUNtloc(bn,dst) = *(oid*) p;
			cur[x] += dst_bunsize; src += src_bunsize;
			oid_CHECK(*maxbits, p);
		}
	} else if (htpe == TYPE_int) {	     /* most common case */
		while(src < end) {
			ptr p = BUNtloc(b,src);
			hash_t x = oid_RADIX(p,mask) >> shift;
			BUN dst = base + cur[x];

			if (cur[x] == lim[x])
				break;
			*(int*) BUNhloc(bn,dst) = *(int*) BUNhloc(b,src);
			*(oid*) BUNtloc(bn,dst) = *(oid*) p;
			cur[x] += dst_bunsize; src += src_bunsize;
			oid_CHECK(*maxbits, p);
		}
	} else
		while(src < end) {
			ptr p = BUNtloc(b,src);
			hash_t x = oid_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));
			*(oid*) BUNtloc(bn,dst) = *(oid*) p;
			cur[x] += dst_bunsize; src += src_bunsize;
			oid_CHECK(*maxbits, p);
		}
	return src;
  bunins_failed:
	return NULL;
}


#line 1967 "/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_int(BAT *bn, BAT *b, BUN start, BUN end, BUN base,
	      size_t* cur, size_t* lim, size_t mask, int shift, oid *maxbits)
{