/*	SELECT.C	- 
**
**
** Copyright (c) 1996  Hughes Technologies Pty Ltd
**
** Permission to use, copy, and distribute for non-commercial purposes,
** is hereby granted without fee, providing that the above copyright
** notice appear in all copies and that both the copyright notice and this
** permission notice appear in supporting documentation.
**
** The software may be modified for your own purposes, but modified versions
** may not be distributed.
**
** This software is provided "as is" without any expressed or implied warranty.
**
**
*/


#include <stdio.h>
#include <fcntl.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <netdb.h>

#ifdef OS2
#  include <types.h>
#else
#  include <arpa/inet.h>
#  include <unistd.h>
#  include <stdlib.h>
#  include <string.h>
#endif


#ifdef OS2
#  include <common/mman.h>
#else
#  include <sys/mman.h>
#endif

#ifdef HAVE_DIRENT_H
#  ifdef OS2
#    include <common/dirent.h>
#  else
#    include <dirent.h>
#  endif
#endif

#ifdef HAVE_SYS_DIR_H
#  include <sys/dir.h>
#endif

#ifdef WIN32
#  include <winsock.h>
#endif

#include <common/debug.h>
#include <common/site.h>
#include <common/portability.h>



#if defined(OS2) || defined(WIN32)
#  include "msql_yacc.h"
#else
#  include "y.tab.h"
#endif

#define _MSQL_SERVER_SOURCE

#include "msql_priv.h"
#include "msql.h"
#include "errmsg.h"

#define REG             register




typedef struct {
	cond_t	*head,
		*t1,
		*t2;
} join_t;




extern	char	*packet,
		errMsg[];
extern	int	selectWildcard,
		selectDistinct,
		outSock;




void mergeRows(result, row,table1,t1Row,table2,t2Row)
	cache_t	*result;
	row_t	*row,
		*t1Row,
		*t2Row;
	cache_t	*table1,
		*table2;
{
	field_t	*curField;
	char	*cp;
	int	sysvarRow;

	/*
	** Drag the 2 rows over
	*/
	(void)bcopy(t1Row->data,row->data,table1->rowDataLen);
	(void)bcopy(t2Row->data,row->data+table1->rowDataLen,
		table2->rowDataLen);
	cp = (char *)row->data + table1->rowDataLen + table2->rowDataLen;

	/*
	** If there are any system variables in the join result we
	** have to manaully add them.  createTmpTable() forces them
	** to be at the end of the table row so we just need to append
	** to correct values to the newly created row.
	*/
	curField = result->def;
	while(curField)
	{
		if (*curField->name == '_')
		{
			sysvarRow = 0;
			if (strcmp(curField->table,table1->table)==0)
				sysvarRow = 1;
			if (strcmp(curField->table,table2->table)==0)
				sysvarRow = 2;
			if (sysvarRow == 0)
			{
				curField = curField->next;
				continue;
			}
			if (sysvarRow == 1)
				getSysVar(table1,t1Row,curField);
			else
				getSysVar(table2,t2Row,curField);
			*cp = 1;
			cp++;
			copyValue(cp,curField->value,curField->type,
				curField->length,1);
			cp += curField->length;
		}
		curField = curField->next;
	}
}




int checkForPartialMatch(conds)
	cond_t	*conds;
{
	cond_t	*curCond;
	int	res;

	if (!conds)
		return(0);	
	res = 1;
	curCond = conds;
	while(curCond)
	{
		if (curCond->value->type == IDENT_TYPE)
		{
			return(0);
		}
		if (curCond->bool == OR_BOOL)
		{
			return(0);
		}
		curCond=curCond->next;
	}
	return(res);
}





static field_t *buildIdentList(entry, conds, flist)
	cache_t	*entry;
	cond_t	*conds;
	int	*flist;
{
	field_t	*identFields,
		*tail,
		*curField;
	cond_t	*curCond;
	int 	*curOffset;

	tail = identFields = NULL;
	curCond = conds;
	curOffset = flist;
	while(curCond)
	{

		/*
		** Find an IDENT cond and setup the field struct
		*/
		if (curCond->value->type != IDENT_TYPE)
		{
			curCond = curCond->next;
			continue;
		}
		curField = (field_t *)malloc(sizeof(field_t));
		strcpy(curField->name, curCond->name);
		strcpy(curField->table, curCond->table);
		if (tail)
		{
			tail->next = curField;
		}
		else
		{
			identFields = curField;
		}
		tail = curField;
		curField->next = NULL;

		/*
		** Fill in the blanks
		*/
		curField = entry->def;
		*curOffset = 0;
		while(curField)
		{
			if (strcmp(curField->name, 
				curCond->value->val.identVal->seg2)!=0)
			{
				*curOffset += curField->dataLength + 1;
				curField = curField->next;
				continue;
			}
			tail->dataLength = curField->dataLength;
			tail->length = curField->length;
			tail->type = curField->type;
			tail->offset = *curOffset;
			tail->fieldID = curCond->fieldID;
			curOffset++;
			break;
		}
		curCond = curCond->next;
	}
	*curOffset = -1;
	return(identFields);
}



static int invertOp(op)
	int	op;
{
	switch(op)
	{
		case GT_OP:
			return(LT_OP);
		case LT_OP:
			return(GT_OP);
		case GE_OP:
			return(LE_OP);
		case LE_OP:
			return(GE_OP);
	}
	return(op);
}



int swapIdentConds(cond1, cond2)
	cond_t	**cond1,
		**cond2;
{
	cond_t	*tail,
		*cur,
		*tmp,
		*prev;
	ident_t	*newIdent,
		*curIdent;
	int	count;

	tail = prev = NULL;
	count = 0;
	cur = *cond2;
	while (cur)
	{
		tail = cur;
		cur = cur->next;
	}
	cur = *cond1;
	while (cur)
	{
		if (cur->value->type == IDENT_TYPE)
		{
			/*
			** ensure we don't have this already
			*/
			tmp = *cond2;
			while(tmp)
			{
				if (tmp->value->type != IDENT_TYPE)
				{
					tmp = tmp->next;
					continue;
				}
				curIdent = cur->value->val.identVal;
				if(*tmp->table != *curIdent->seg1 ||
				   *tmp->name != *curIdent->seg2)
				{
					tmp=tmp->next;
					continue;
				}
				if(strcmp(tmp->table,curIdent->seg1)!=0 ||
				   strcmp(tmp->name,curIdent->seg2)!=0)
				{
					tmp = tmp->next;
					continue;
				}
				curIdent = tmp->value->val.identVal;

				if(strcmp(cur->table,curIdent->seg1)!=0 ||
				   strcmp(cur->name,curIdent->seg2)!=0)
				{
					tmp = tmp->next;
					continue;
				}
				break;
			}
			if (tmp)
			{
				/* Dodge it.  It's already there! */
				cur = cur->next;
				continue;
			}
			count++;
			newIdent = (ident_t *)msqlCreateIdent(cur->table, 
				cur->name);
			strcpy(cur->table,cur->value->val.identVal->seg1);
			strcpy(cur->name,cur->value->val.identVal->seg2);
			free(cur->value->val.identVal);
			cur->value->val.identVal = newIdent;
			cur->op = invertOp(cur->op);
			if (prev)
			{
				prev->next = cur->next;
			}
			else
			{
				*cond1 = cur->next;
			}
			if (tail)
			{
				tail->next = cur;
			}
			else
			{
				*cond2 = cur;
			}
			cur->next = NULL;
			tail = cur;
		}
		cur = cur->next;
	}
	return(count);
}


static cond_t *condDup(cond)
	cond_t	*cond;
{
	cond_t	*new;

	new = (cond_t*)fastMalloc(sizeof(cond_t));
	bcopy(cond,new,sizeof(cond_t));
	new->value = (val_t *)fastMalloc(sizeof(val_t));
	bcopy(cond->value,new->value,sizeof(val_t));
	new->next = NULL;
	switch(new->value->type)
	{
		case CHAR_TYPE:
			new->value->val.charVal = (u_char *)strdup(
				cond->value->val.charVal);
			break;
		case IDENT_TYPE:
			new->value->val.identVal = (ident_t *)fastMalloc(
				sizeof(ident_t));
			bcopy(cond->value->val.identVal,
				new->value->val.identVal, sizeof(ident_t));
			break;
	}
	return(new);
}



static void setJoinTableDone(tables,name)
	tname_t	*tables;
	char	*name;
{
	tname_t	*cur;

	cur = tables;
	while(cur)
	{
		if (strcmp(cur->name, name) == 0)
		{
			cur->done = 1;
			return;
		}
		cur = cur->next;
	}
	return;
}

static int checkJoinTableDone(tables,name)
	tname_t	*tables;
	char	*name;
{
	tname_t	*cur;

	cur = tables;
	while(cur)
	{
		if (strcmp(cur->name, name) == 0)
		{
			return(cur->done);
		}
		cur = cur->next;
	}
	return(0);
}


join_t *setupJoinConditions(table1, table2, conds, tables)
	cache_t	*table1,
		*table2;
	cond_t	*conds;
	tname_t	*tables;
{
	cond_t	*head,
		*tail,
		*t1,
		*t2,
		*cur,
		*newCond;
	char	buf[NAME_LEN + 1];
	static  join_t new;


	/*
	** Build a list of all conditions related to the join as a whole
	*/
	head = NULL;
	cur = conds;
	while(cur)
	{
		if (cur->subCond)
		{
			cur = cur->next;
			continue;
		}
		if (strcmp(table1->table,cur->table) == 0 ||
			strcmp(table2->table,cur->table) == 0)
		{
			if (cur->value->type == IDENT_TYPE)
			{
				if (checkJoinTableDone(tables,
					cur->value->val.identVal->seg1) == 0)
				{
					cur = cur->next;
					continue;
				}
			}
			newCond = condDup(cur);
			if (!head)
			{
				tail = head = newCond;
			}
			else
			{
				tail->next = newCond;
				tail = newCond;
			}
			cur = cur->next;
			continue;
		}

		if (cur->value->type == IDENT_TYPE &&
		    (strcmp(table1->table,cur->value->val.identVal->seg1)==0||
		     strcmp(table2->table,cur->value->val.identVal->seg1)==0))
		{
			if (checkJoinTableDone(tables,cur->table) == 0)
			{
				cur = cur->next;
				continue;
			}
			newCond = condDup(cur);
			if (!head)
			{
				tail = head = newCond;
			}
			else
			{
				tail->next = newCond;
				tail = newCond;
			}
			cur = cur->next;
			continue;
		}
		cur = cur->next;
	}    


	/*
	** Build a list for T1 if it isn't a result table.
	*/
	t1 = tail = NULL;
	if (table1->result == 0)
	{
		cur = head;
		while(cur)
		{
			if (strcmp(table1->table, cur->table) == 0)
			{
				newCond = condDup(cur);
				if (!t1)
				{
					t1 = tail = newCond;
				}
				else
				{
					tail->next = newCond;
					tail = newCond;
				}
			}
			else
			if (cur->value->type == IDENT_TYPE &&
		  	strcmp(table1->table,cur->value->val.identVal->seg1)==0)
			{
				newCond = condDup(cur);
				if (!t1)
				{
					t1 = tail = newCond;
				}
				else
				{
					tail->next = newCond;
					tail = newCond;
				}
				strcpy(buf, newCond->table);
				strcpy(newCond->table, 
					newCond->value->val.identVal->seg1);
				strcpy(newCond->value->val.identVal->seg1, buf);
	
				strcpy(buf, newCond->name);
				strcpy(newCond->name, 
					newCond->value->val.identVal->seg2);
				strcpy(newCond->value->val.identVal->seg2, buf);
			}
			cur = cur->next;
		}
	}

	/*
	** Build a list for T2 if it isn't a result table
	*/
	t2 = tail = NULL;
	if (table2->result == 0)
	{
		cur = head;
		while(cur)
		{
			if (strcmp(table2->table, cur->table) == 0)
			{
				newCond = condDup(cur);
				if (!t2)
				{
					t2 = tail = newCond;
				}
				else
				{
					tail->next = newCond;
					tail = newCond;
				}
			}
			else
			if (cur->value->type == IDENT_TYPE &&
		  	strcmp(table2->table,cur->value->val.identVal->seg1)==0)
			{
				newCond = condDup(cur);
				if (!t2)
				{
					t2 = tail = newCond;
				}
				else
				{
					tail->next = newCond;
					tail = newCond;
				}
				strcpy(buf, newCond->table);
				strcpy(newCond->table, 
					newCond->value->val.identVal->seg1);
				strcpy(newCond->value->val.identVal->seg1, buf);
	
				strcpy(buf, newCond->name);
				strcpy(newCond->name, 
					newCond->value->val.identVal->seg2);
				strcpy(newCond->value->val.identVal->seg2, buf);
			}
			cur = cur->next;
		}
	}

	new.head = head;
	new.t1 = t1;
	new.t2 = t2;
	return(&new);
}




cache_t *joinTables(table1,table2,conds,db,tables, fields)
	cache_t	*table1,
		*table2;
	cond_t	*conds;
	char	*db;
	tname_t	*tables;
	field_t	*fields;
{
	cache_t	*tmpTable,
		*outer,
		*inner;
	int	outerRowNum, 	innerRowNum,
		identFList[MAX_FIELDS],
		t1Partial,	t2Partial,
		doPartial,	res;
	cond_t	*newCondHead, 
		*t1CondHead, 	*t2CondHead, 	
		*outerConds, 	*innerConds,
		*newCond, 	*curCond;
	field_t	*curField, 	*tmpField,
		*identFields;
	row_t	outerRow, 	innerRow,
		*row;
	cand_t	*outerCand, 	*innerCand,
		*t1Cand,	*t2Cand;
	join_t	*joinInfo;



        msqlTrace(TRACE_IN,"joinTables()");


	/*
	** Work out the conditions that apply to the join as a whole and
	** the two tables individually
	*/
	msqlSetupConds(table1,conds);
	msqlSetupConds(table2,conds);
	joinInfo = setupJoinConditions(table1, table2, conds, tables);
	newCondHead = joinInfo->head;
	t1CondHead = joinInfo->t1;
	t2CondHead = joinInfo->t2;

	/*
	** See if we can do partial match optimisation on either table
	*/
	t1Partial = checkForPartialMatch(t1CondHead);
	t2Partial = checkForPartialMatch(t2CondHead);


	/*
	** What about index based lookups?  Look for a straight literal
	** index first and then an IDENT based key if we don't have
	** anything.  If we end up with 2 IDENT based indices then we
	** drop the first and make it sequential.
	*/
	if(msqlSetupConds(table1,t1CondHead) < 0)
	{
		return(NULL);
	}
	t1Cand = msqlSetupCandidate(table1, t1CondHead, NULL, IGNORE_IDENT);
	if (!t1Cand)
		return(NULL);
	if (t1Cand->type == CAND_SEQ)
	{
		freeCandidate(t1Cand);
		t1Cand = msqlSetupCandidate(table1,t1CondHead,NULL,KEEP_IDENT);
	}
	if (!t1Cand)
		return(NULL);

	if(msqlSetupConds(table2,t2CondHead) < 0)
	{
		return(NULL);
	}
	t2Cand = msqlSetupCandidate(table2, t2CondHead, NULL, IGNORE_IDENT);
	if (!t2Cand)
	{
		freeCandidate(t1Cand);
		return(NULL);
	}
	if (t2Cand->type == CAND_SEQ)
	{
		freeCandidate(t2Cand);
		t2Cand=msqlSetupCandidate(table2,t2CondHead,NULL,KEEP_IDENT);
	}
	if (!t2Cand)
	{
		freeCandidate(t1Cand);
		return(NULL);
	}

	if (t1Cand->type > CAND_SEQ && t2Cand->type > CAND_SEQ)
	{
		if (t1Cand->ident && t2Cand->ident)
		{
			t1Cand->type = CAND_SEQ;
			t1Cand->lastPos = NO_POS;
#ifdef BERK_DB
			t1Cand->file->close(t1Cand->file);
			t1Cand->file = NULL;
#endif

		}
	}

	/*
	** OK, we know all there is to know.  Now what can we do with it?
	*/
	if (t1Cand->type > CAND_SEQ)
	{
		/* We've got an index on T1 */
		if (t1Cand->ident == 0)
		{
			if (swapIdentConds(&t1CondHead, &t2CondHead) > 0)
			{
				msqlSetupConds(table1,t1CondHead);
				msqlSetupConds(table2,t2CondHead);
			}
			outer = table1;
			outerConds = t1CondHead;
			outerCand = t1Cand;
			inner = table2;
			innerConds = t2CondHead;
			freeCandidate(t2Cand);
			t2Cand=msqlSetupCandidate(table2,t2CondHead,NULL,
				KEEP_IDENT);
			innerCand = t2Cand;
			doPartial = 0;
		}
		else
		{
			if (swapIdentConds(&t2CondHead, &t1CondHead) > 0)
			{
				msqlSetupConds(table1,t1CondHead);
				msqlSetupConds(table2,t2CondHead);
			}
			outer = table2;
			outerConds = t2CondHead;
			outerCand = t2Cand;
			inner = table1;
			innerConds = t1CondHead;
			freeCandidate(t1Cand);
			t1Cand=msqlSetupCandidate(table1,t1CondHead,NULL,
				KEEP_IDENT);
			innerCand = t1Cand;
			doPartial = 0;
		}
	} else 
	if (t2Cand->type > CAND_SEQ)
	{
		/* We've got an index on T2 */
		if (t2Cand->ident == 0)
		{
			if (swapIdentConds(&t2CondHead, &t1CondHead) > 0)
			{
				msqlSetupConds(table1,t1CondHead);
				msqlSetupConds(table2,t2CondHead);
			}
			outer = table2;
			outerConds = t2CondHead;
			outerCand = t2Cand;
			inner = table1;
			innerConds = t1CondHead;
			freeCandidate(t1Cand);
			t1Cand=msqlSetupCandidate(table1,t1CondHead,NULL,
				KEEP_IDENT);
			innerCand = t1Cand;
			doPartial = 0;
		}
		else
		{
			if (swapIdentConds(&t1CondHead, &t2CondHead) > 0)
			{
				msqlSetupConds(table1,t1CondHead);
				msqlSetupConds(table2,t2CondHead);
			}
			outer = table1;
			outerConds = t1CondHead;
			outerCand = t1Cand;
			inner = table2;
			innerConds = t2CondHead;
			freeCandidate(t2Cand);
			t2Cand=msqlSetupCandidate(table2,t2CondHead,NULL,
				KEEP_IDENT);
			innerCand = t2Cand;
			doPartial = 0;
		}
	} else 
	if (t1Partial)
	{
		/* We've got a partial match on T1 */

		outer = table1;
		outerConds = t1CondHead;
		outerCand = t1Cand;
		inner = table2;
		innerConds = t2CondHead;
		innerCand = t2Cand;
		doPartial = 1;
	} else 
	if (t2Partial)
	{
		/* We've got a partial match on T2 */

		outer = table2;
		outerConds = t2CondHead;
		outerCand = t2Cand;
		inner = table1;
		innerConds = t1CondHead;
		innerCand = t1Cand;
		doPartial = 1;
	}
	else
	{
		/* We've got nothing to speed this up */

		outer = table1;
		outerConds = t1CondHead;
		outerCand = t1Cand;

		inner = table2;
		innerConds = t2CondHead;
		innerCand = t2Cand;
		doPartial = 0;
	} 
	
	
	/*
	** Now that we know the inner table, we need to create a field
	** list containing the fields from the outer table that are used
	** as IDENT_TYPE conditions for the inner table.  Without this
	** we can't do candidate based lookups for the inner table.
	*/

	identFields = buildIdentList(outer, innerConds, identFList);


	/*
	** Create a table definition for the join result.  We can't do
	** this earlier as we must know which is the inner and outer table
	*/
	tmpTable = createTmpTable(outer,inner,fields,ALL_FIELDS);
	if (!tmpTable)
	{
		freeCandidate(innerCand);
		freeCandidate(outerCand);
        	msqlTrace(TRACE_OUT,"joinTables()");
		return(NULL);
	}
	(void)sprintf(tmpTable->resInfo,"'%s (%s+%s)'",tmpTable->table,
		table1->table, table2->table);


	/*
	** Do the join
	*/

	row = &(tmpTable->row);
	if (msqlSetupConds(tmpTable,newCondHead) < 0)
	{
		freeCandidate(innerCand);
		freeCandidate(outerCand);
		freeTmpTable(tmpTable);
        	msqlTrace(TRACE_OUT,"joinTables()");
		return(NULL);
	}

	outerRowNum = getCandidate(outer, outerCand);
	while(outerRowNum != NO_POS)
	{
		rowRead(outer,&outerRow,outerRowNum);
		/*
		** Dodge holes 
		*/
		if (!outerRow.header->active)
		{
			outerRowNum = getCandidate(outer, outerCand);
			continue;
		}

		/* 
		** Partial match optimisation ??
		*/
		if(doPartial)
		{
			if (matchRow(outer,&outerRow,outerConds)!=1)
			{
				outerRowNum = getCandidate(outer, outerCand);
				continue;
			}
		}


		/*
		** Go ahead and join this row with the inner table
		*/

		extractValues(outer,&outerRow,identFields,identFList);
		if (setCandidateValues(inner, innerCand, identFields, 
			innerConds, &outerRow) < 0)
		{
			freeTmpTable(tmpTable);
			return(NULL);
		}
		resetCandidate(innerCand, MSQL_SELECT);
		innerRowNum = getCandidate(inner, innerCand);
		while(innerRowNum != NO_POS)
		{
			rowRead(inner,&innerRow,innerRowNum);
			if (!innerRow.header->active)
			{
				innerRowNum = getCandidate(inner, innerCand);
				continue;
			}
			row->header->active = 1;
			mergeRows(tmpTable,row,outer,&outerRow,inner,&innerRow);
			res=matchRow(tmpTable,row,newCondHead);

			if (res < 0)
			{
				freeCandidate(innerCand);
				freeCandidate(outerCand);
        			msqlTrace(TRACE_OUT,"joinTables()");
				freeTmpTable(tmpTable);
				return(NULL);
			}
			if (res == 1)
			{
				if(rowWrite(tmpTable,NULL,NO_POS) < 0)
				{
        				msqlTrace(TRACE_OUT,
						"joinTables()");
					freeTmpTable(tmpTable);
					freeCandidate(outerCand);
					freeCandidate(innerCand);
					return(NULL);
				}
			}
			innerRowNum = getCandidate(inner, innerCand);
		}
		outerRowNum = getCandidate(outer, outerCand);
	}
	freeCandidate(innerCand);
	freeCandidate(outerCand);

	/*
	** Free up the space allocated to the new condition list.
	** We don't need to free the value structs as we just copied
	** the pointers to them.  They'll be freed during msqlClen();
	*/
	curCond = newCondHead;
	while(curCond)
	{
                newCond = curCond;
                curCond = curCond->next;
		if (newCond->value)
			msqlFreeValue(newCond->value);
                (void)free(newCond);
	}
	curCond = t1CondHead;
	while(curCond)
	{
                newCond = curCond;
                curCond = curCond->next;
		if (newCond->value)
			msqlFreeValue(newCond->value);
                (void)free(newCond);
	}
	curCond = t2CondHead;
	while(curCond)
	{
                newCond = curCond;
                curCond = curCond->next;
		if (newCond->value)
			msqlFreeValue(newCond->value);
                (void)free(newCond);
	}

	if (identFields)
	{
		curField = identFields;
		while(curField)
		{
			tmpField = curField;
			curField = curField->next;
			if (tmpField->value)
				msqlFreeValue(tmpField->value);
			free(tmpField);
		}
	}

	msqlTrace(TRACE_OUT,"joinTables()");
	return(tmpTable);
}





/* 
** The new sorting routine 
**
** This is an implementation of qSort
*/

static void swapRows(entry, low, high)
	cache_t	*entry;
	u_int	low,
		high;
{
	row_t	lowRow,
		highRow,
		*tmp;

	rowRead(entry,&lowRow,low);
	rowRead(entry,&highRow,high);
	tmp = dupRow(entry,&lowRow,&(entry->row));
	rowPlace(entry, &highRow, low);
	rowPlace(entry, tmp, high);
}


void qSort(entry, order, olist, lBound, uBound)
	cache_t	*entry;
	order_t	*order;
	int	*olist;
	u_int	lBound,
		uBound;
{
	int	lCount,
		uCount,
		res;
	row_t	curRow,
		pivotRow;

	res = rowRead(entry, &pivotRow, lBound);
	if (res < 0)
		return;
	lCount = lBound + 1;
	uCount = uBound;

	while(lCount <= uCount)
	{
		res = rowRead(entry,&curRow, lCount);
		if (res < 0)
			return;
		while(lCount <= uBound &&
			compareRows(entry,&curRow, &pivotRow, order, olist)<=0)
		{
			lCount++;
			res = rowRead(entry,&curRow, lCount);
			if (res < 0)
			{
				return;
			}
		}

		res =  rowRead(entry,&curRow, uCount);
		if (res < 0)
			return;
		while(uCount > lBound &&
			compareRows(entry,&curRow, &pivotRow, order, olist)>=0)
		{
			uCount--;
			res = rowRead(entry,&curRow, uCount);
			if (res < 0)
			{
				return;
			}
		}

		if (lCount < uCount)
		{
			swapRows(entry, lCount, uCount);
			lCount++;
			uCount--;
		}
	}

	/*
	** Move the pivot into place
	*/
	swapRows(entry, uCount, lBound);
	if (uCount != lBound)
	{
		qSort(entry, order, olist, lBound, uCount - 1);
	}
	if (uCount < uBound)
	{
		qSort(entry, order, olist, uCount+1, uBound);
	}
}



int createSortedTable(entry,order)
	cache_t	*entry;
	order_t	*order;
{
	int	olist[MAX_FIELDS];

	msqlTrace(TRACE_IN,"createSortedTable()");

	if(initTable(entry,FULL_REMAP) < 0)
	{
		msqlTrace(TRACE_OUT,"createSortedTable()");
		return(-1);
	}
	if (msqlSetupOrder(entry,olist,order) < 0)
	{
		msqlTrace(TRACE_OUT,"createSortedTable()");
		return(-1);
	}


	if (entry->sblk->numRows > 0)
	{
		qSort(entry, order, olist, 0, entry->sblk->numRows - 1);
	}

	msqlTrace(TRACE_OUT,"createSortedTable()");
	return(0);
}




int createDistinctTable(entry)
	cache_t	*entry;
{

	row_t	row,
		*cur = NULL;
	u_int	rowNum,
		curRowNum;
	int	flist[MAX_FIELDS],
		res,
		haveVarChar;
	field_t	*curField;
	

	if(initTable(entry,FULL_REMAP) < 0)
	{
		return(-1);
	}
	if(entry->sblk->numRows == 0)
	{
		return(0);
	}
	if (msqlSetupFields(entry,flist,entry->def) < 0)
	{
		return(-1);
	}

	haveVarChar = 0;
	curField = entry->def;
	while(curField)
	{
		if (curField->type == TEXT_TYPE)
			haveVarChar++;
		curField = curField->next;
	}

	curRowNum = 0;
	while(rowRead(entry,&row,curRowNum) > 0)
	{
		if (!row.header->active)
		{
			curRowNum++;
			continue;
		}
		cur = dupRow(entry,&row, &(entry->row));
		rowNum = curRowNum;

		while(rowRead(entry,&row,rowNum) > 0)
		{
			if (!row.header->active)
			{
				rowNum++;
				continue;
			}
			if (rowNum == curRowNum)
			{
				rowNum++;
				continue;
			}
			if (*(cur->data) != *(row.data))
			{
				rowNum++;
				continue;
			}

			if (haveVarChar)
			{
				res = checkDupRow(entry,cur->data,row.data);
			}
			else
			{
				res = bcmp(cur->data,row.data,entry->rowLen);
			}
			if (res == 0)
			{
				deleteRow(entry,rowNum);
			}
			rowNum++;
		}
		curRowNum++;
	}
	return(0);
}




int doSelect(cacheEntry, tables, fields,conds,dest,tmpTable)
	cache_t	*cacheEntry;
	tname_t	*tables;
	field_t	*fields;
	cond_t	*conds;
	int	dest;
	cache_t	*tmpTable;
{
	int	flist[MAX_FIELDS],
		tmpFlist[MAX_FIELDS],
		rowLen,
		rowNum,
		numFields,
		count,
		res;
	char	outBuf[100],
		outBuf2[100];
	row_t	row;
	cand_t	*candidate;
	field_t	*identFields;
	REG 	field_t *curField;
	extern 	int msqlSelectLimit;


	msqlTrace(TRACE_IN,"doSelect()");

	fieldHead = fields;
	identFields = NULL;
	
	numFields = 0;
	curField = fieldHead;
	while(curField)
	{
		numFields++;
		curField = curField->next;
	}

	/*
	** Find the offsets of the given fields and condition
	*/
	if (msqlSetupFields(cacheEntry,flist,fields) < 0)
	{
		msqlTrace(TRACE_OUT,"doSelect()");
		return(-1);
	}
	if (msqlSetupConds(cacheEntry,conds) < 0)
	{
		msqlTrace(TRACE_OUT,"doSelect()");
		return(-1);
	}


	if (tmpTable)
	{
		if (msqlSetupFields(tmpTable,tmpFlist,fields) < 0)
		{
			msqlTrace(TRACE_OUT,"doSelect()");
			return(-1);
		}
	}

	candidate = msqlSetupCandidate(cacheEntry, conds, fields, IGNORE_IDENT);
	if (!candidate)
	{
		return(-1);
	}

	rowLen = cacheEntry->rowLen;

	if (initTable(cacheEntry,FULL_REMAP) < 0)
	{
		freeCandidate(candidate);
		msqlTrace(TRACE_OUT,"doSelect()");
		return(-1);
	}

	/*
	** Tell the client how many fields there are in a row
	*/

	if (dest == DEST_CLIENT)
	{
		sprintf(packet,"1:%d:\n",numFields);
		writePkt(outSock);
	}


	/*
	** Special case for singe field sys var access.  Check the comments
	** in msqlSetupCandidate() for info on why this is needed
	*/
	if (candidate->type == CAND_SYS_VAR)
	{
		extractValues(cacheEntry, NULL,fields, flist);
		formatPacket(packet,fields);
		writePkt(outSock);
		sprintf(packet,"-100:\n");
		writePkt(outSock);

		/*
		** Send the field info down the line to the client
		*/
		sprintf(outBuf,"%d",fields->length);
		sprintf(outBuf2,"%d",fields->type);
		sprintf(packet,"%d:%s%d:%s%d:%s%d:%s1:%s1:%s", 
			(int)strlen(fields->table), fields->table,
			(int)strlen(fields->name), fields->name, 
			(int)strlen(outBuf2), outBuf2,
			(int)strlen(outBuf), outBuf, 
			fields->flags & NOT_NULL_FLAG ? "Y":"N",
			" ");
		writePkt(outSock);
		sprintf(packet,"-100:\n");
		writePkt(outSock);
		msqlTrace(TRACE_OUT,"doSelect()");
		freeCandidate(candidate);
		return(0);
	}

	/*
	** OK, no more wierd stuff.  Just do the usual
	*/

	count = 0;
	rowNum = getCandidate(cacheEntry, candidate);
	while (rowNum != NO_POS)
	{
		rowRead(cacheEntry,&row,rowNum);
		if (row.header->active)
		{
			res = matchRow(cacheEntry,&row,conds);
			if (res < 0)
			{
				freeCandidate(candidate);
				return(-1);
			}
			if (res == 1)
			{
				extractValues(cacheEntry, &row,fields,
					flist);
				if (dest == DEST_CLIENT)
				{
					formatPacket(packet,fields);
					writePkt(outSock);
				}
				else
				{
					bzero(tmpTable->row.data,
						tmpTable->rowLen);
					fillRow(cacheEntry,
						&(tmpTable->row),
						fields, tmpFlist);
					rowWrite(tmpTable,NULL,NO_POS);
				}
				count++;
			}
		}
		if (dest == DEST_CLIENT && msqlSelectLimit > 0)
		{
			if (count == msqlSelectLimit)
				break;
		}
		rowNum = getCandidate(cacheEntry, candidate);
	}
	if (dest == DEST_CLIENT)
	{
		sprintf(packet,"-100:\n");
		writePkt(outSock);

		/*
		** Send the field info down the line to the client
		*/
		curField = fields;
		while(curField)
		{
			sprintf(outBuf,"%d",curField->length);
			sprintf(outBuf2,"%d",curField->type);
			sprintf(packet,"%d:%s%d:%s%d:%s%d:%s1:%s1:%s", 
				(int)strlen(curField->table), curField->table,
				(int)strlen(curField->name), curField->name, 
				(int)strlen(outBuf2), outBuf2,
				(int)strlen(outBuf), outBuf, 
				curField->flags & NOT_NULL_FLAG ? "Y":"N",
				" ");
			writePkt(outSock);
			curField = curField->next;
		}
		sprintf(packet,"-100:\n");
		writePkt(outSock);
	}
	msqlTrace(TRACE_OUT,"doSelect()");
	freeCandidate(candidate);
	return(0);
}



static int checkConds(conds, tables)
	tname_t	*tables;
	cond_t	*conds;
{
	REG	cond_t	*curCond;
	REG	tname_t	*curTable;
	
	curCond = conds;
	while(curCond)
	{
		if (curCond->subCond)
		{
			if (checkConds(curCond->subCond, tables) < 0)
				return(-1);
			curCond = curCond->next;
			continue;
		}
		curTable = tables;
		while(curTable)
		{
			if ( *(curCond->table) != *(curTable->name))
			{
				curTable = curTable->next;
				continue;
			}
			if (strcmp(curCond->table,curTable->name) != 0)
			{
				curTable = curTable->next;
				continue;
			}
			break;
		}
		if (!curTable)
		{
			sprintf(errMsg,UNSELECT_ERROR,(char *)curCond->table);
			return(-1);
		}
		curCond = curCond->next;
	}
	return(0);
}


extern	field_t	*fieldHead;

int msqlServerSelect(tables,fields,conds,order,db)
	tname_t	*tables;
	field_t	*fields;
	cond_t	*conds;
	order_t	*order;
	char	*db;
{
	cache_t	*cacheEntry,
		*table1,
		*table2,
		*tmpTable;
	REG	tname_t	*curTable;
	REG	field_t	*curField;
	int	join,
		foundTable;

	msqlTrace(TRACE_IN,"msqlSelect()");

	/*
	** Check out the tables and fields specified in the query.  If
	** multiple tables are specified all field specs must be
	** qualified and they must reference a selected table.
	*/

	curTable = tables;
	tmpTable = NULL;
	if (curTable->next)
	{
		join = 1;
	}
	else
	{
		/*
		** If there's no joins ensure that each condition and field
		** is fully qualified with the correct table
		*/
		msqlQualifyFields(tables->name,fields);
		msqlQualifyConds(tables->name,conds);
		msqlQualifyOrder(tables->name,order);
		join = 0;
	}

	/*
	** Ensure that any field or condition refers to fields of 
	** selected tables
	*/
	curField = fields;
	while(curField)
	{
		curTable = tables;
		while(curTable)
		{
			if ( *(curField->table) != *(curTable->name))
			{
				curTable = curTable->next;
				continue;
			}
			if (strcmp(curField->table,curTable->name) != 0)
			{
				curTable = curTable->next;
				continue;
			}
			break;
		}
		if (!curTable)
		{
			sprintf(errMsg,UNSELECT_ERROR,curField->table);
			msqlTrace(TRACE_OUT,"msqlSelect()");
			return(-1);
		}
		curField = curField->next;
	}
	if (checkConds(conds,tables) < 0)
	{
		msqlTrace(TRACE_OUT,"msqlSelect()");
		return(-1);
	}


	curField = fields;
	while (curField)
	{
		if (*(curField->table) == 0)
		{
			if (join)
			{
				sprintf(errMsg, UNQUAL_JOIN_ERROR, 
					curField->name);
				msqlTrace(TRACE_OUT,"msqlSelect()");
				return(-1);
			}
			curField = curField->next;
			continue;
		}
		curTable = tables;
		foundTable = 0;
		while(curTable)
		{
			if ( *(curTable->name) != *(curField->table))
			{
				curTable = curTable->next;
				continue;
			}
			if (strcmp(curTable->name,curField->table) != 0)
			{
				curTable = curTable->next;
				continue;
			}
			foundTable = 1;
			break;
		}
		if (!foundTable)
		{
			sprintf(errMsg,UNSELECT_ERROR, curField->table);
			msqlTrace(TRACE_OUT,"msqlSelect()");
			return(-1);
		}
		curField = curField->next;
	}


	/*
	** If there's multiple tables, join the suckers.
	*/

	if (join)
	{
		curTable = tables;
		while(curTable)
		{
			if (curTable == tables)
			{
				table1 = loadTableDef(curTable->name,
					curTable->cname,db);
				if (!table1)
				{
					msqlTrace(TRACE_OUT,"msqlSelect()");
					return(-1);
				}
				if (initTable(table1,FULL_REMAP) < 0)
				{
					msqlTrace(TRACE_OUT,"msqlSelect()");
					return(-1);
				}
				curTable = curTable->next;
				table2 = loadTableDef(curTable->name,
					curTable->cname,db);
				if (!table2)
				{
					msqlTrace(TRACE_OUT,"msqlSelect()");
					return(-1);
				}
				if (initTable(table2,FULL_REMAP) < 0)
				{
					msqlTrace(TRACE_OUT,"msqlSelect()");
					return(-1);
				}
				if (!table1 || !table2)
				{
					msqlTrace(TRACE_OUT,"msqlSelect()");
					return(-1);
				}
				setJoinTableDone(tables,table1->table);
				setJoinTableDone(tables,table2->table);
				tmpTable = joinTables(table1,table2,conds,db,
					tables, fields);
				if (!tmpTable)
				{
					msqlTrace(TRACE_OUT,"msqlSelect()");
					return(-1);
				}
					
			}
			else
			{
				table1 = tmpTable;
				table2 = loadTableDef(curTable->name,
					curTable->cname,db);
				if (!table2)
				{
					msqlTrace(TRACE_OUT,"msqlSelect()");
					return(-1);
				}
				if (initTable(table1,FULL_REMAP) < 0)
				{
					msqlTrace(TRACE_OUT,"msqlSelect()");
					return(-1);
				}
				if (initTable(table2,FULL_REMAP) < 0)
				{
					msqlTrace(TRACE_OUT,"msqlSelect()");
					return(-1);
				}
				setJoinTableDone(tables,table1->table);
				setJoinTableDone(tables,table2->table);
				tmpTable = joinTables(table1,table2,conds,db,
					tables, fields);
				if (table1->result)
				{
					freeTmpTable(table1);
				}
				if (!tmpTable)
				{
					msqlTrace(TRACE_OUT,"msqlSelect()");
					return(-1);
				}
			}
			curTable = curTable->next;
		}
	}

	/*
	** Perform the actual select.  If there's an order clause or
	** a pending DISTINCT, send the results to a table for further 
	** processing.
	**
	** Look for the wildcard field spec.  Must do this before we
	** "setup" because it edits the field list.  selectWildcard
	** is a global set from inside the yacc parser.  Wild card
	** expansion is only called if this is set otherwise it will
	** consume 50% of the execution time of selects!
	*/

	if (!tmpTable)
	{
		if((cacheEntry = loadTableDef(tables->name,tables->cname,
			db)) == NULL)
		{
			msqlTrace(TRACE_OUT,"msqlSelect()");
			return(-1);
		}
	}
	else
	{
		cacheEntry = tmpTable;
	}
	if (selectWildcard)
	{
		fields = expandFieldWildCards(cacheEntry,fields);
		fieldHead = fields;
	}

	if (!order && !selectDistinct)
	{
		if (doSelect(cacheEntry,tables,fields,conds,
			DEST_CLIENT,NULL) < 0)
		{
			if(cacheEntry->result)
				freeTmpTable(cacheEntry);
			msqlTrace(TRACE_OUT,"msqlSelect()");
			return(-1);
		}
		if (cacheEntry->result)
		{
			freeTmpTable(cacheEntry);
		}
		msqlTrace(TRACE_OUT,"msqlSelect()");
		return(0);
	}

	/*
	** From here on we just want a table with the required fields
	** (i.e. not all the fields of a join)
	*/
	tmpTable = createTmpTable(cacheEntry,NULL,fields, QUERY_FIELDS_ONLY);
	if (!tmpTable)
	{
		if (cacheEntry->result)
			freeTmpTable(cacheEntry);
		return(-1);
	}
	(void)sprintf(tmpTable->resInfo,"'%s (stripped %s)'",
		tmpTable->table,cacheEntry->table);
	if (doSelect(cacheEntry,tables,fields,conds,
		DEST_TABLE,tmpTable) < 0)
	{
		if (cacheEntry->result)
			freeTmpTable(cacheEntry);
		freeTmpTable(tmpTable);
		msqlTrace(TRACE_OUT,"msqlSelect()");
		return(-1);
	}
	if (cacheEntry->result)
	{
		freeTmpTable(cacheEntry);
	}
	cacheEntry = tmpTable;

	/*
	** Blow away multiples if required
	*/
	if (selectDistinct)
	{
		if (createDistinctTable(cacheEntry) < 0)
		{
			if(cacheEntry->result)
				freeTmpTable(cacheEntry);
			msqlTrace(TRACE_OUT,"msqlSelect()");
			return(-1);
		}
	}
	
	/*
	** Sort the result if required
	*/
	if (order)
	{
		if (createSortedTable(cacheEntry,order) < 0)
		{
			if(cacheEntry->result)
				freeTmpTable(cacheEntry);
			msqlTrace(TRACE_OUT,"msqlSelect()");
			return(-1);
		}
	}


	/*
	** Send the result to the client if we haven't yet.
	*/
	if (doSelect(cacheEntry,tables,fields,NULL,DEST_CLIENT,NULL)<0)
	{
		if(cacheEntry->result)
			freeTmpTable(cacheEntry);
		msqlTrace(TRACE_OUT,"msqlSelect()");
		return(-1);
	}

	/*
	** Free the result table
	*/
	if (cacheEntry->result)
	{
		freeTmpTable(cacheEntry);
	}


	msqlTrace(TRACE_OUT,"msqlSelect()");
	return(0);
}


