static void
CLKsignal(int nr)
{
	/* int restype; */
	int k = timerTop;
	int t;

	(void) nr;

	if (signal(SIGALRM, CLKsignal) == SIG_ERR) {
		GDKsyserror("CLKsignal: call failed\n");
	}

	if (timerTop == 0) {
		return;
	}
	t = time(0);
	while (k-- && t >= timer[k].alarm_time) {
		if (timer[k].action) {
			/* monet_eval(timer[k].action, &restype); */
			GDKfree(timer[k].action);
		} else {
			MT_sema_up(&timer[k].sema, "CLKsignal");
		}
		timerTop--;
	}
	if (timerTop > 0) {
		alarm(timer[timerTop - 1].alarm_time - time(0));
	}
}

/*
 * Determine the variables being used and clear non-used onces.
 */
void
MSresetVariables(Client cntxt, MalBlkPtr mb, MalStkPtr glb, int start)
{
	int i;
	bit *used = GDKzalloc(mb->vtop * sizeof(bit));
	if( used == NULL){
		GDKerror("MSresetVariables" MAL_MALLOC_FAIL);
		return;
	}

	for (i = 0; i < start && start < mb->vtop; i++)
		used[i] = 1;
	if (mb->errors == 0)
		for (i = start; i < mb->vtop; i++) {
			if (used[i] || !isTmpVar(mb, i)) {
				assert(!mb->var[i]->value.vtype || isVarConstant(mb, i));
				used[i] = 1;
			}
			if (glb && !used[i]) {
				if (isVarConstant(mb, i))
					garbageElement(cntxt, &glb->stk[i]);
				/* clean stack entry */
				glb->stk[i].vtype = TYPE_int;
				glb->stk[i].len = 0;
				glb->stk[i].val.pval = 0;
			}
		}

	if (mb->errors == 0)
		trimMalVariables_(mb, used, glb);
	GDKfree(used);
}

void 
mal_client_reset(void)
{
	MAL_MAXCLIENTS = 0;
	if (mal_clients)
		GDKfree(mal_clients);
}

/*
 * Display routines
 */
str
MDBlifespan(Client cntxt, MalBlkPtr mb, MalStkPtr stk, InstrPtr p)
{
	Lifespan span;
	str modnme;
	str fcnnme;
	Symbol s = NULL;

	(void) cntxt;
	if (stk != 0) {
		modnme = *getArgReference_str(stk, p, 1);
		fcnnme = *getArgReference_str(stk, p, 2);
	} else {
		modnme = getArgDefault(mb, p, 1);
		fcnnme = getArgDefault(mb, p, 2);
	}

	s = findSymbol(cntxt->nspace, putName(modnme), putName(fcnnme));

	if (s == NULL)
		throw(MAL, "mdb.inspect", RUNTIME_SIGNATURE_MISSING);
	span = setLifespan(s->def);
	if( span == NULL)
		throw(MAL,"mdb.inspect", MAL_MALLOC_FAIL);
	debugLifespan(cntxt, s->def, span);
	GDKfree(span);
	(void) p;
	(void) stk;
	return MAL_SUCCEED;
}

/* Remote execution of MAL calls for more type/property information to be exchanged */
str
mal2str(MalBlkPtr mb, int first, int last)
{
	str ps = NULL, *txt;
	int i, *len, totlen = 0;

	txt = GDKmalloc(sizeof(str) * mb->stop);
	len = GDKmalloc(sizeof(int) * mb->stop);

	if( txt == NULL || len == NULL){
		GDKerror("mal2str: " MAL_MALLOC_FAIL);
		if( txt ) GDKfree(txt);
		if( len ) GDKfree(len);
		return NULL;
	}
	for (i = first; i < last; i++) {
		if( i == 0)
			txt[i] = instruction2str(mb, 0, getInstrPtr(mb, i), LIST_MAL_NAME | LIST_MAL_TYPE  | LIST_MAL_PROPS);
		else
			txt[i] = instruction2str(mb, 0, getInstrPtr(mb, i), LIST_MAL_CALL | LIST_MAL_PROPS | LIST_MAL_REMOTE);
#ifdef _DEBUG_LISTING_
		mnstr_printf(GDKout,"%s\n",txt[i]);
#endif

		if ( txt[i])
			totlen += len[i] = (int)strlen(txt[i]);
	}
	ps = GDKmalloc(totlen + mb->stop + 1);
	if( ps == NULL)
		GDKerror("mal2str: " MAL_MALLOC_FAIL);

	totlen = 0;
	for (i = first; i < last; i++) {
		if( txt[i]){
			if( ps){
				strncpy(ps + totlen, txt[i], len[i]);
				ps[totlen + len[i]] = '\n';
				ps[totlen + len[i] + 1] = 0;
				totlen += len[i] + 1;
			}
			GDKfree(txt[i]);
		}
	}
	GDKfree(len);
	GDKfree(txt);
	return ps;
}

/* Search for occurrence of the function in the library identified by the filename.  */
MALfcn
getAddress(str fcnname)
{
	void *dl;
	MALfcn adr;
	int idx=0;
	static int prev= -1;

	/* First try the last module loaded */
	if( prev >= 0){
		adr = (MALfcn) dlsym(filesLoaded[prev].handle, fcnname);
		if( adr != NULL)
			return adr; /* found it */
	}
	/*
	 * Search for occurrence of the function in any library already loaded.
	 * This deals with the case that files are linked together to reduce
	 * the loading time, while the signatures of the functions are still
	 * obtained from the source-file MAL script.
	 */
	for (idx =0; idx < lastfile; idx++)
		if (idx != prev &&		/* skip already searched module */
			filesLoaded[idx].handle &&
			(idx == 0 || filesLoaded[idx].handle != filesLoaded[0].handle)) {
			adr = (MALfcn) dlsym(filesLoaded[idx].handle, fcnname);
			if (adr != NULL)  {
				prev = idx;
				return adr; /* found it */
			}
		}

	if (lastfile)
		return NULL;
	/*
	 * Try the program libraries at large or run through all
	 * loaded files and try to resolve the functionname again.
	 *
	 * the first argument must be the same as the base name of the
	 * library that is created in src/tools */
	dl = mdlopen("libmonetdb5", RTLD_NOW | RTLD_GLOBAL);
	if (dl == NULL) 
		return NULL;

	adr = (MALfcn) dlsym(dl, fcnname);
	filesLoaded[lastfile].modname = GDKstrdup("libmonetdb5");
	if(filesLoaded[lastfile].modname == NULL) {
		dlclose(dl);
		return NULL;
	}
	filesLoaded[lastfile].fullname = GDKstrdup("libmonetdb5");
	if(filesLoaded[lastfile].fullname == NULL) {
		dlclose(dl);
		GDKfree(filesLoaded[lastfile].modname);
		return NULL;
	}
	filesLoaded[lastfile].handle = dl;
	lastfile ++;
	return adr;
}

void
MCpopClientInput(Client c)
{
	ClientInput *x = c->bak;
	if (c->fdin) {
		/* missing protection against closing stdin stream */
		(void) bstream_destroy(c->fdin);
	}
	GDKfree(c->prompt);
	c->fdin = x->fdin;
	c->yycur = x->yycur;
	c->listing = x->listing;
	c->prompt = x->prompt;
	c->promptlength = strlen(c->prompt);
	c->bak = x->next;
	GDKfree(x);
}

static void
MRcleanCloud(void)
{
	int i;

	MT_lock_set(&mal_contextLock, "mapreduce");
	for (i = 0; mapnodes[i].uri; i++) {
		if (mapnodes[i].uri != NULL)
			GDKfree(mapnodes[i].uri);
		if (mapnodes[i].user != NULL)
			GDKfree(mapnodes[i].user);
		if (mapnodes[i].pass != NULL)
			GDKfree(mapnodes[i].pass);
		mapnodes[i].uri = mapnodes[i].user = mapnodes[i].pass = 0;
	}
	MT_lock_unset(&mal_contextLock, "mapreduce");
}

static str
JSONfilterInternal(json *ret, json *js, str *expr, str other)
{
	pattern terms[MAXTERMS];
	int tidx = 0;
	JSON *jt;
	str j = *js, msg = MAL_SUCCEED, s;
	json result = 0;
	size_t l;

	(void) other;
	if (strNil(j)) {
		*ret = GDKstrdup(j);
		return MAL_SUCCEED;
	}
	memset((char *) terms, 0, MAXTERMS * sizeof(pattern));
	msg = JSONcompile(*expr, terms);
	if (msg)
		return msg;
	jt = JSONparse(j, FALSE);
	CHECK_JSON(jt);

	result = s = JSONmatch(jt, 0, terms, tidx);
	// process all other PATH expression
	for (tidx++; tidx < MAXTERMS && terms[tidx].token; tidx++)
		if (terms[tidx].token == END_STEP && tidx + 1 < MAXTERMS && terms[tidx + 1].token) {
			s = JSONmatch(jt, 0, terms, ++tidx);
			result = JSONglue(result, s, ',');
		}
	if (result) {
		l = strlen(result);
		if (result[l - 1] == ',')
			result[l - 1] = 0;
	} else
		l = 3;
	s = GDKzalloc(l + 3);
	snprintf(s, l + 3, "[%s]", (result ? result : ""));
	GDKfree(result);

	for (l = 0; terms[l].token; l++)
		if (terms[l].name)
			GDKfree(terms[l].name);
	JSONfree(jt);
	*ret = s;
	return msg;
}

static AGGRtask*
GROUPcollect( Client cntxt, MalBlkPtr mb, MalStkPtr stk, InstrPtr pci){
	AGGRtask *a;
	int i;
	BAT *b, *bs, *bh = NULL;
	BUN sample;

	(void) mb;
	(void) cntxt;
	a= (AGGRtask *) GDKzalloc(sizeof(*a));
	if ( a == NULL)
		return NULL;
	a->bid = (bat*) GDKzalloc(pci->argc * sizeof(bat));
	a->cols = (BAT**) GDKzalloc(pci->argc * sizeof(BAT*));
	a->unique = (BUN *) GDKzalloc(pci->argc * sizeof(BUN));
	if ( a->cols == NULL || a->bid == NULL || a->unique == NULL){
		if(a->cols) GDKfree(a->cols);
		if(a->bid) GDKfree(a->bid);
		if(a->unique) GDKfree(a->unique);
		GDKfree(a);
		return NULL;
	}
	for ( i= pci->retc; i< pci->argc; i++, a->last++) {
		a->bid[a->last] = *getArgReference_bat(stk,pci,i);
		b = a->cols[a->last]= BATdescriptor(a->bid[a->last]);
		if ( a->cols[a->last] == NULL){
			for(a->last--; a->last>=0; a->last--)
				BBPunfix(a->cols[a->last]->batCacheid);
			GDKfree(a->cols);
			GDKfree(a->bid);
			GDKfree(a->unique);
			GDKfree(a);
			return NULL;
		}
		sample = BATcount(b) < 1000 ? BATcount(b): 1000;
		bs = BATsample( b, sample);
		if (bs) {
			bh = BATunique(b, bs);
			if (bh) {
				a->unique[a->last] = BATcount(bh);
				BBPunfix(bh->batCacheid);
			}
			BBPunfix(bs->batCacheid);
		}
		if ( b->tsorted)
			a->unique[a->last] = 1000; /* sorting helps grouping */
		a->size = BATcount(b);
	}

#ifdef _DEBUG_GROUPBY_
	for(i=0; i<a->last; i++)
		fprintf(stderr,"#group %d unique "BUNFMT "\n", i, a->unique[i]);
#endif
	return a;
}

/* Clear V to an empty value (type void, value nil), freeing any
 * memory allocated for external types.  See VALempty for when V does
 * not yet contain a value. */
void
VALclear(ValPtr v)
{
	if (ATOMextern(v->vtype)) {
		if (v->val.pval && v->val.pval != ATOMnilptr(v->vtype))
			GDKfree(v->val.pval);
	}
	VALempty(v);
}

int
OPTgroupsImplementation(Client cntxt, MalBlkPtr mb, MalStkPtr stk, InstrPtr p)
{
	int i, actions=0;
	InstrPtr q;
	InstrPtr *old, *ref;
	int limit,slimit;

	(void) cntxt;
	(void) stk;
	if (varGetProp(mb, getArg(mb->stmt[0], 0), inlineProp) != NULL) {
		return 0;
	}

	/* beware, new variables and instructions are introduced */
	ref= (InstrPtr*) GDKzalloc(sizeof(InstrPtr) * mb->vtop); /* to find last assignment */
	if ( ref == NULL) {
		return 0;
	}

	old= mb->stmt;
	limit= mb->stop;
	slimit= mb->ssize;
	if ( newMalBlkStmt(mb,mb->ssize) <0) {
		GDKfree(ref);
		return 0;
	}

	for (i = 0; i<limit; i++){
		p= old[i];
		if (getModuleId(p) == groupRef && p->argc == 4 && getFunctionId(p) == subgroupRef ){
			setFunctionId(p, multicolumnsRef);
			ref[getArg(p,0)] = p;
			actions++;
			OPTDEBUGgroups {
				mnstr_printf(cntxt->fdout,"#new groups instruction\n");
				printInstruction(cntxt->fdout,mb, 0, p, LIST_MAL_ALL);
			}
		}
		if (getModuleId(p) == groupRef && p->argc == 5 && getFunctionId(p) == subgroupdoneRef && ref[getArg(p,4)] != NULL){
			/*
			 * Try to expand its argument list with what we have found so far.
			 * This creates a series of derive paths, many of which will be removed during deadcode elimination.
			 */
			q= copyInstruction(ref[getArg(p,4)]);
			q= pushArgument(mb, q, getArg(p,3));
			getArg(q,0) = getArg(p,0);
			getArg(q,1) = getArg(p,1);
			getArg(q,2) = getArg(p,2);
			ref[getArg(q,0)] = q;
			freeInstruction(p);
			p= q;
			OPTDEBUGgroups{
				mnstr_printf(cntxt->fdout,"#new groups instruction extension\n");
				printInstruction(cntxt->fdout,mb, 0, p, LIST_MAL_ALL);
			}
		} 

/*
 * For analysis of memory leaks we should cleanup the libraries before
 * we exit the server. This does not involve the libraries themselves,
 * because they may still be in use.
 */
void
mal_linker_reset(void)
{
	int i;

	MT_lock_set(&mal_contextLock);
	for (i = 0; i < lastfile; i++){
		if (filesLoaded[i].fullname) {
			/* dlclose(filesLoaded[i].handle);*/
			GDKfree(filesLoaded[i].modname);
			GDKfree(filesLoaded[i].fullname);
		}
		filesLoaded[i].modname = NULL;
		filesLoaded[i].fullname = NULL;
	}
	lastfile = 0;
	MT_lock_unset(&mal_contextLock);
}

/*
 * When you add a value to the stack, you should ensure that
 * there is space left. It should only be used for global
 * stack frames, because the others are allocated in the
 * runtime stack.
 */
void
freeStack(MalStkPtr stk)
{
	if (!stk) {
		return;
	}
	clearStack(stk);
	GDKfree(stk);
}

void
VALclear(ValPtr v)
{
	if (v->vtype == TYPE_str || ATOMextern(v->vtype)) {
		if (v->val.pval && v->val.pval != str_nil)
			GDKfree(v->val.pval);
	}
	VALempty(v);
}

/* actual implementation */
static char *
UDFBATreverse_(BAT **ret, BAT *src)
{
	BATiter li;
	BAT *bn = NULL;
	BUN p = 0, q = 0;

	/* assert calling sanity */
	assert(ret != NULL);

	/* handle NULL pointer */
	if (src == NULL)
		throw(MAL, "batudf.reverse", RUNTIME_OBJECT_MISSING);

	/* check tail type */
	if (src->ttype != TYPE_str) {
		throw(MAL, "batudf.reverse",
		      "tail-type of input BAT must be TYPE_str");
	}

	/* allocate result BAT */
	bn = BATnew(src->htype, TYPE_str, BATcount(src));
	if (bn == NULL) {
		throw(MAL, "batudf.reverse", MAL_MALLOC_FAIL);
	}
	BATseqbase(bn, src->hseqbase);

	/* create BAT iterator */
	li = bat_iterator(src);

	/* the core of the algorithm, expensive due to malloc/frees */
	BATloop(src, p, q) {
		char *tr = NULL, *err = NULL;

		/* get original head & tail value */
		ptr h = BUNhead(li, p);
		const char *t = (const char *) BUNtail(li, p);

		/* revert tail value */
		err = UDFreverse_(&tr, t);
		if (err != MAL_SUCCEED) {
			/* error -> bail out */
			BBPreleaseref(bn->batCacheid);
			return err;
		}

		/* assert logical sanity */
		assert(tr != NULL);

		/* insert original head and reversed tail in result BAT */
		/* BUNins() takes care of all necessary administration */
		BUNins(bn, h, tr, FALSE);

		/* free memory allocated in UDFreverse_() */
		GDKfree(tr);
	}

str
stringdiff_impl(int *res, str *s1, str *s2)
{
	str r = MAL_SUCCEED;
	char *S1 = NULL, *S2 = NULL;

	r = soundex_impl(&S1, s1);
	if( r != MAL_SUCCEED)
		return r;
	r = soundex_impl(&S2, s2);
	if( r != MAL_SUCCEED){
		GDKfree(S1);
		return r;
	}
	r = levenshteinbasic_impl(res, &S1, &S2);
	GDKfree(S1);
	GDKfree(S2);
	return r;
}

static BAT *
MATsort_bte( BAT **map, BAT **bats, int len, BUN cnt, int rev )
{
	BAT *res;
	int i;
	bte *resT, **batsT, *in;
	bte *mapT;
	BUN len1, len2;
	bte *map_in = NULL;

	res = BATnew(TYPE_void, bats[0]->ttype, cnt, TRANSIENT);
	*map = BATnew(TYPE_void, TYPE_bte, cnt, TRANSIENT);
	if (res == NULL || *map == NULL) {
		BBPreclaim(res);
		BBPreclaim(*map);
		*map = NULL;
		return NULL;
	}
	BATseqbase(res, 0);
	BATseqbase(*map, 0);
	resT = (bte*)Tloc(res, 0);
	mapT = (bte*)Tloc(*map, 0);
	batsT = (bte**)GDKmalloc(sizeof(bte*) * len);
	for (i=0; i<len; i++)
		batsT[i] = (bte*)Tloc(bats[i], 0);
	/* merge */
	in = batsT[0];
	len1 = BATcount(bats[0]);
	map_in = NULL;
	/* TODO: change into a tree version */
	for (i=1; i<len; i++) {
		len2 = BATcount(bats[i]);
		if (rev) {
			MATsortloop_bte_rev( resT+cnt-len1-len2, 
					mapT+cnt-len1-len2, 
				        in, map_in, len1, 
					batsT[i], i, len2);
		} else {
			MATsortloop_bte_( resT+cnt-len1-len2, 
					mapT+cnt-len1-len2, 
				        in, map_in, len1, 
					batsT[i], i, len2);
		}
		in = resT+cnt-len1-len2;
		map_in = mapT+cnt-len1-len2;
		len1 += len2;
	}
	BATsetcount(res, len1);
	BATsetcount(*map, len1);
	res->hrevsorted = len1 <= 1;
	(*map)->hrevsorted = len1 <= 1;
	GDKfree(batsT);
	return res;
}

static void
QEPfree(QEP qep)
{
	int i;
	if( qep == 0)
		return;
	for(i=0; i< qep->climit; i++)
	if( qep->children[i])
		QEPfree(qep->children[i]);
	GDKfree(qep);
}

/*
 * When a client needs to be terminated then the file descriptors for
 * its input/output are simply closed.  This leads to a graceful
 * degradation, but may take some time when the client is busy.  A more
 * forcefull method is to kill the client thread, but this may leave
 * locks and semaphores in an undesirable state.
 *
 * The routine freeClient ends a single client session, but through side
 * effects of sharing IO descriptors, also its children. Conversely, a
 * child can not close a parent.
 */
void
freeClient(Client c)
{
	Thread t = c->mythread;
	c->mode = FINISHING;

#ifdef MAL_CLIENT_DEBUG
	printf("# Free client %d\n", c->idx);
#endif
	MCexitClient(c);

	/* scope list and curprg can not be removed, because the client may
	 * reside in a quit() command. Therefore the scopelist is re-used.
	 */
	c->scenario = NULL;
	if (c->prompt)
		GDKfree(c->prompt);
	c->prompt = NULL;
	c->promptlength = -1;
	if (c->errbuf) {
		GDKsetbuf(0);
		if (c->father == NULL)
			GDKfree(c->errbuf);
		c->errbuf = 0;
	}
	c->father = 0;
	c->login = c->lastcmd = 0;
	c->qtimeout = 0;
	c->stimeout = 0;
	if (c->rcc) {
		GDKfree(c->rcc);
		c->rcc = NULL;
	}
	c->user = oid_nil;
	c->mythread = 0;
	c->mode = FREECLIENT;
	GDKfree(c->glb);
	c->glb = NULL;
	if (t)
		THRdel(t);  /* you may perform suicide */
}