group.c

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

#line 232 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/kernel/group.mx"
#include "mal_config.h"
#include "group.h"
#include "algebra.h"
static int TYPE_mapentry;
static int TYPE_idxentry;


int
grp_new(BAT *b, BAT *h)
{
	if (h) {
		BATkey(h, TRUE);
		BATkey(BATmirror(h), FALSE);
		h->tsorted = 0;
		if ((h->hsorted = BAThordered(b)) & 1) {
			if (BATcount(h) == BATcount(b)) {
				ALIGNsetH(h, BATmirror(b));
			}
		} else if (BATorder(h) == NULL) {
			BBPreclaim(h);
			if (b) BBPreclaim(b);
			return GDK_FAIL;
		}
		BBPkeepref(h->batCacheid);
	} else {
		assert(h);
	}
	BBPkeepref(b->batCacheid);
	return GDK_SUCCEED;
}




#line 279 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/kernel/group.mx"
#define HASH_chr(p) ((hash_t) (*(unsigned char*) (p)))
#define HASH_sht(p) ((hash_t) (*(unsigned short*) (p)))
#define HASH_int(p) ((hash_t) *(unsigned int*) (p))
#define HASH_lng(p) ((hash_t)(((unsigned int*)(p))[0]^((unsigned int*)(p))[1]))
#define HASH_any(p) ((*hashfcn)(p))

#define match_sync(b,p,r) r += yy
#define match_hash(b,p,r) BUNfndOID(r,b,p); if (r == NULL) continue;

#define declare_atom int any = b->ttype; hash_t (*hashfcn)(ptr) = BATatoms[any].atomHash;
#define declare_simple	/* any and hash would otherwise give unused variable warning */

#define htype_sync(b) BAThdense(b)?TYPE_void:TYPE_oid
#define htype_hash(b) TYPE_oid

#define ttype_simple(b,t) t
#define ttype_atom(b,t) b->ttype

#define STANDARD_MASK ((hash_t) 1023)

/*
   Note:
	following macros take advantage of clustered property;
	if b is clustered, then we can stop early traversing collision lists.

	BTW, simply stopping possibly breaks chain construction, so the resulting
	map is not directly reuseable as a hash table; the current Monet cannot
	however handle multiple accellerators, so this ain't a real problem for now :)
 */

#define declare_unclustered	/* avoid warning */
#define declare_clustered   int samecluster = TRUE;

#define chain_unclustered   for (zz = hash[c]; zz != HASH_MAX; zz = e->link)
#define chain_clustered     for (zz = hash[c]; (zz != HASH_MAX) && (samecluster); zz = e->link)

#define tst_grp_unclustered(eq,p,t)    (eq(p, tcur, t))
#define tst_grp_clustered(eq,p,t)      (samecluster = eq(p, tcur, t))

#define tst_derive_unclustered(eq,p,t) (e->hcur == hcur && eq(p, tcur, t))
#define tst_derive_clustered(eq,p,t)   ((samecluster = e->hcur == hcur) && eq(p, tcur, t))

/* NOTE: the first two fields of idxentry_t and mapentry_t MUST be the
   same */
typedef struct {
	oid hcur;		/* old group id */
	hash_t link;		/* hash link */
} idxentry_t;

typedef struct {
	oid hcur;		/* old group id */
	hash_t link;		/* hash link */
	oid gid;		/* new group id */
	int cnt;		/* histogram count */
} mapentry_t;

typedef struct {
	BAT *map;		/* [mapentry,value] elements */
	hash_t *hash, mask;	/* hash buckets and mask */
	Heap hp;		/* storage for hash buckets */
} map_T;


#line 345 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/kernel/group.mx"
#define map_init_STANDARD(map,hash,mask,entry,mapsize)			\
	if (m) {							\
		map = m->map; hash = m->hash; mask = m->mask;		\
	} else {							\
		hash_t yy;						\
		map = BATnew(TYPE_mapentry, tailtype(b,TRUE), 4096);	\
		hash = (hash_t*) GDKmalloc((int)(sizeof(hash_t)*((mask=STANDARD_MASK)+1))); \
		for (yy=0; yy<=STANDARD_MASK; yy++) {				\
			hash[yy] = HASH_MAX;				\
		}							\
	}								\
	entry.cnt = 1;							\
	mapsize = BUNindex(map, BUNlast(map));


#line 341 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/kernel/group.mx"


#line 345 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/kernel/group.mx"
#define map_init_CUSTOM(map,hash,mask,entry,mapsize)			\
	if (m) {							\
		map = m->map; hash = m->hash; mask = m->mask;		\
	} else {							\
		hash_t yy;						\
		map = BATnew(TYPE_mapentry, tailtype(b,TRUE), custom_rng);	\
		hash = (hash_t*) GDKmalloc((int)(sizeof(hash_t)*((mask=custom_MASK)+1))); \
		for (yy=0; yy<=custom_MASK; yy++) {				\
			hash[yy] = HASH_MAX;				\
		}							\
	}								\
	entry.cnt = 1;							\
	mapsize = BUNindex(map, BUNlast(map));


#line 342 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/kernel/group.mx"




#line 359 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/kernel/group.mx"
void
map_free(map_T m)
{
	BBPreclaim(m.map);
	HEAPfree(&m.hp);
}

#ifndef offsetof
#define offsetof(type, member)	((size_t) &((type *) 0)->member)
#endif

BAT *
map2histo(BAT *map)
{
	if (map == NULL || map->htype != TYPE_mapentry || VIEWparent(map) || map->batSharecnt > 1 || BATgetaccess(map) != BAT_WRITE) {
		if (map)
			BBPreclaim(map);
		return NULL;
	}
	/* trickily transform a bat[mapentry,any] into bat[oid,int] */
	map->htype = BATmirror(map)->ttype = TYPE_oid;
	map->ttype = BATmirror(map)->htype = TYPE_int;
	if (map->tvarsized && map->theap) {
		HEAPfree(map->theap);
		GDKfree(map->theap);
		map->theap = NULL;
	}
	BATmirror(map)->hvarsized = map->tvarsized = 0;
	/* do these in the right order: map->dims.headloc is used, so
	 * change it at end
	 */
	BATmirror(map)->dims.headloc = map->dims.tailloc = map->dims.headloc + (int) offsetof(mapentry_t, cnt);
	BATmirror(map)->dims.tailloc = map->dims.headloc = map->dims.headloc + (int) offsetof(mapentry_t, gid);

	return map;
}


#line 396 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/kernel/group.mx"


#line 426 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/kernel/group.mx"
#define group_params_STANDARD	/* fixed */
#define group_params_CUSTOM   hash_t custom_MASK, int custom_rng,



#line 518 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/kernel/group.mx"
int
tailtype(BAT *b, int str_trick)
{
	int tpe = ATOMstorage(b->ttype);	/* standard type remappings */

	/* more daring remappings possible under simple equality */
	if (tpe == TYPE_flt) {
		return TYPE_int;
	} else if (tpe == TYPE_dbl) {
		return TYPE_lng;
	} else if (tpe == TYPE_str && str_trick && GDK_ELIMDOUBLES((b->theap))) {
		return TYPE_var;	/* string offsets are identifying integers */
	}
	return tpe;
}

/* Generate both 'normal' CTgroup and clustered CTgroups */


#line 548 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/kernel/group.mx"

#line 544 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/kernel/group.mx"

#line 536 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/kernel/group.mx"

#line 430 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/kernel/group.mx"
BAT *
CTgroup_chr_unclustered_STANDARD(group_params_STANDARD BAT *b, BAT *bn, map_T *m)
{
	oid *dst = (oid*) BUNfirst(bn);
	hash_t xx=0, *hash, mask;
	size_t zz, mapsize;
	mapentry_t entry, *e;
	BUN p, q, r;
	BAT *map = NULL;
	declare_simple
#ifdef MKspeedup
	size_t idx;
#endif

	map_init_STANDARD(map,hash,mask,entry,mapsize);
	if (map == NULL)
		return NULL;

	/* core hash grouping algorithm */
#ifdef MKspeedup
/* MK: Experimental code. Should be triggered when you attempt
to consume a lot of your physical memory. First indication, a factor 2.
*/
		(void) q;

        if( BATprepareHash(BATmirror(b))){
            stream_printf(GDKout,"#M5 IO group join\n");
            for( idx=0; idx< b->thash->mask; idx++)
            for( xx=b->thash->hash[idx]; xx != HASH_MAX; xx= b->thash->link[xx]){
		declare_unclustered
		ptr tcur;
		p= BUNptr(b,xx);
		tcur = BUNtloc(b,p);

#else
	BATloopFast(b, p, q, xx) {
		declare_unclustered
		ptr tcur = BUNtloc(b,p);
#endif

		/* hash-lookup of 'tcur' in map */
		hash_t c = HASH_chr(tcur);
		c = mix_int(c) & mask;
		chain_unclustered {
			r = BUNptr(map,zz);
			e = (mapentry_t*) BUNhloc(map,r);
			if (tst_grp_unclustered(simple_EQ, BUNtloc(map,r), chr)) {
				if (m == NULL)
					e->cnt++;
				goto found;
			}
		}

		/* not found-> insert new element in map (and hash) */
		if (m) {
			zz = mapsize;
		} else {
			entry.gid = *(oid*) BUNhead(b,p);
		}
		entry.link = hash[c];
		hash[c] = mapsize++;
		bunfastins(map, &entry, tcur);
		e = &entry;

found:		/* ultra-fast 'insert' of [oid,gid] into ct */
		if (bn->htype)
			*dst++ = *(oid*) BUNhead(b,p);
		*dst++ = m?zz:e->gid;
	}
#ifdef MKspeedup
	BATsort(BATmirror(bn));
	}
#endif
	bn->batBuns->free = ((BUN) dst) - bn->batBuns->base;
	BATsetcount(bn, bn->batBuns->free/BUNsize(bn));
	bn->tsorted = 0;
	if (!(bn->batDirty&2)) bn = BATsetaccess(bn, BAT_READ);
	ALIGNsetH(bn,b);
	if (hash && !m)
		GDKfree(hash);
	return m ? NULL : map2histo(map);
bunins_failed:
	BBPreclaim(bn);
	if (hash && !m)
		GDKfree(hash);
	return NULL;
}


#line 536 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/kernel/group.mx"


#line 430 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/kernel/group.mx"
BAT *
CTgroup_sht_unclustered_STANDARD(group_params_STANDARD BAT *b, BAT *bn, map_T *m)
{
	oid *dst = (oid*) BUNfirst(bn);
	hash_t xx=0, *hash, mask;
	size_t zz, mapsize;
	mapentry_t entry, *e;
	BUN p, q, r;
	BAT *map = NULL;
	declare_simple
#ifdef MKspeedup
	size_t idx;
#endif

	map_init_STANDARD(map,hash,mask,entry,mapsize);
	if (map == NULL)
		return NULL;

	/* core hash grouping algorithm */
#ifdef MKspeedup
/* MK: Experimental code. Should be triggered when you attempt
to consume a lot of your physical memory. First indication, a factor 2.
*/
		(void) q;

        if( BATprepareHash(BATmirror(b))){
            stream_printf(GDKout,"#M5 IO group join\n");
            for( idx=0; idx< b->thash->mask; idx++)
            for( xx=b->thash->hash[idx]; xx != HASH_MAX; xx= b->thash->link[xx]){
		declare_unclustered
		ptr tcur;
		p= BUNptr(b,xx);
		tcur = BUNtloc(b,p);

#else
	BATloopFast(b, p, q, xx) {
		declare_unclustered
		ptr tcur = BUNtloc(b,p);
#endif

		/* hash-lookup of 'tcur' in map */
		hash_t c = HASH_sht(tcur);
		c = mix_int(c) & mask;
		chain_unclustered {
			r = BUNptr(map,zz);
			e = (mapentry_t*) BUNhloc(map,r);
			if (tst_grp_unclustered(simple_EQ, BUNtloc(map,r), sht)) {
				if (m == NULL)
					e->cnt++;
				goto found;
			}
		}

		/* not found-> insert new element in map (and hash) */
		if (m) {
			zz = mapsize;
		} else {
			entry.gid = *(oid*) BUNhead(b,p);
		}
		entry.link = hash[c];
		hash[c] = mapsize++;
		bunfastins(map, &entry, tcur);
		e = &entry;

found:		/* ultra-fast 'insert' of [oid,gid] into ct */
		if (bn->htype)
			*dst++ = *(oid*) BUNhead(b,p);
		*dst++ = m?zz:e->gid;
	}
#ifdef MKspeedup
	BATsort(BATmirror(bn));
	}
#endif
	bn->batBuns->free = ((BUN) dst) - bn->batBuns->base;
	BATsetcount(bn, bn->batBuns->free/BUNsize(bn));
	bn->tsorted = 0;
	if (!(bn->batDirty&2)) bn = BATsetaccess(bn, BAT_READ);
	ALIGNsetH(bn,b);
	if (hash && !m)
		GDKfree(hash);
	return m ? NULL : map2histo(map);
bunins_failed:
	BBPreclaim(bn);
	if (hash && !m)
		GDKfree(hash);
	return NULL;
}


#line 537 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/kernel/group.mx"


#line 430 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/kernel/group.mx"
BAT *
CTgroup_int_unclustered_STANDARD(group_params_STANDARD BAT *b, BAT *bn, map_T *m)
{
	oid *dst = (oid*) BUNfirst(bn);
	hash_t xx=0, *hash, mask;
	size_t zz, mapsize;
	mapentry_t entry, *e;
	BUN p, q, r;
	BAT *map = NULL;
	declare_simple
#ifdef MKspeedup
	size_t idx;
#endif

	map_init_STANDARD(map,hash,mask,entry,mapsize);
	if (map == NULL)
		return NULL;

	/* core hash grouping algorithm */
#ifdef MKspeedup
/* MK: Experimental code. Should be triggered when you attempt
to consume a lot of your physical memory. First indication, a factor 2.
*/
		(void) q;

        if( BATprepareHash(BATmirror(b))){
            stream_printf(GDKout,"#M5 IO group join\n");
            for( idx=0; idx< b->thash->mask; idx++)
            for( xx=b->thash->hash[idx]; xx != HASH_MAX; xx= b->thash->link[xx]){
		declare_unclustered
		ptr tcur;
		p= BUNptr(b,xx);
		tcur = BUNtloc(b,p);

#else
	BATloopFast(b, p, q, xx) {
		declare_unclustered
		ptr tcur = BUNtloc(b,p);
#endif

		/* hash-lookup of 'tcur' in map */
		hash_t c = HASH_int(tcur);
		c = mix_int(c) & mask;
		chain_unclustered {
			r = BUNptr(map,zz);
			e = (mapentry_t*) BUNhloc(map,r);
			if (tst_grp_unclustered(simple_EQ, BUNtloc(map,r), int)) {
				if (m == NULL)
					e->cnt++;
				goto found;
			}
		}

		/* not found-> insert new element in map (and hash) */
		if (m) {
			zz = mapsize;
		} else {
			entry.gid = *(oid*) BUNhead(b,p);
		}
		entry.link = hash[c];
		hash[c] = mapsize++;
		bunfastins(map, &entry, tcur);
		e = &entry;

found:		/* ultra-fast 'insert' of [oid,gid] into ct */
		if (bn->htype)
			*dst++ = *(oid*) BUNhead(b,p);
		*dst++ = m?zz:e->gid;
	}
#ifdef MKspeedup
	BATsort(BATmirror(bn));
	}
#endif
	bn->batBuns->free = ((BUN) dst) - bn->batBuns->base;
	BATsetcount(bn, bn->batBuns->free/BUNsize(bn));
	bn->tsorted = 0;
	if (!(bn->batDirty&2)) bn = BATsetaccess(bn, BAT_READ);
	ALIGNsetH(bn,b);
	if (hash && !m)
		GDKfree(hash);
	return m ? NULL : map2histo(map);
bunins_failed:
	BBPreclaim(bn);
	if (hash && !m)
		GDKfree(hash);
	return NULL;
}


#line 538 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/kernel/group.mx"


#line 430 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/kernel/group.mx"
BAT *
CTgroup_lng_unclustered_STANDARD(group_params_STANDARD BAT *b, BAT *bn, map_T *m)
{
	oid *dst = (oid*) BUNfirst(bn);
	hash_t xx=0, *hash, mask;
	size_t zz, mapsize;
	mapentry_t entry, *e;
	BUN p, q, r;
	BAT *map = NULL;
	declare_simple
#ifdef MKspeedup
	size_t idx;
#endif

	map_init_STANDARD(map,hash,mask,entry,mapsize);
	if (map == NULL)
		return NULL;

	/* core hash grouping algorithm */
#ifdef MKspeedup
/* MK: Experimental code. Should be triggered when you attempt
to consume a lot of your physical memory. First indication, a factor 2.
*/
		(void) q;

        if( BATprepareHash(BATmirror(b))){
            stream_printf(GDKout,"#M5 IO group join\n");