#include <sys/file.h>
#include <stdio.h>
#include <strings.h>

#include "context.h"
#include "magic.h"

#include "c.h"
#include "os.h"
#include "clib.h"

#include "align.h"
#include "block.h"
#include "buf.h"
#include "bufmgr.h"
#include "bufpage.h"
#include "itemid.h"
#include "off.h"
#include "page.h"
#include "part.h"

#include "anum.h"
#include "catalog.h"
#include "catname.h"
#include "rel.h"
#include "trange.h"
#include "heapam.h"
#include "datum.h"
#include "genam.h"
#include "oid.h"
#include "htup.h"
#include "itup.h"
#include "xtim.h"
#include "xlog.h"
#include "xid.h"
#include "skey.h"
#include "tim.h"
#include "fmgr.h"
#include "ftup.h"
#include "log.h"
#include "tuple.h"
#include "tqual.h"

RcsId("$Header: vacuum.c,v 1.2 89/02/02 17:00:00 dillon Exp $");

#define LIVELIST 0
#define DEADLIST 1
#define DOCNTLIST 2
#define CTUPLIST 3
#define RULELIST 4
#define TEMPLIST 5
#define NLISTS 6

struct {
    char *listname;
} lists[] = {
	"LIVELIST",
	"DEADLIST",
	"DOCNTLIST",
	"CTUPLIST",
	"RULELIST",
	"TEMPLIST"
};

/* #define VACDEBUG 1 */
#define VACOUTPUT 1
#define VACONESHOT 1
#define VACPRINTTIMES 1

#define RULEREASON 0
#define ABORTREASON 1
#define PURGEREASON 2
#define DOCNTREASONA 3
#define DOCNTREASONB 4
#define CTUPREASON 5
#define LIVEREASON 6
#define CTUPTOLIVEREASON 7
#define DOCNTTOLIVEREASON 8
#define CTUPTODEADREASON 9
#define RULETODEADREASON 10
#define RULETOLIVEREASON 11
#define DEADTOTEMPREASONA 12
#define DEADTOTEMPREASONB 13

struct {
    char *reasonline;
} reason[] = {
    "rule; add to rule list",
    "aborted; add to dead list",
    "purged; add to dead list",
    "docnt; add to docnt list",
    "docnt; add to ctup list",
    "ctup; add to ctup list",
    "default; add to live list",
    "changing from ctup to live list",
    "changing from docnt to live list",
    "changing from ctup to dead list",
    "changing from rule to dead list",
    "changing from rule to live list",
	"changing from dead to temp list",
	"changing from dead to temp list"
};

struct VacTidListData {
	ObjectId VacRelOID;
    ItemPointerData VacTid;
    ItemPointerData VacContTid;
    bool VacHasContTid;
    ItemPointerData VacRuleTid;
    bool VacHasRuleTid;
    int VacReasonCode;
    struct VacTidListData *NextVacTid;
};

struct RelNameListData {
	char relname[20];
	char relkind;
	struct RelNameListData *next;
};

struct {
    struct VacTidListData *ListHead;
    struct VacTidListData *ListTail;
    int ListCount;
} ListHT[NLISTS];

struct RelNameListData *RelNameList;
ObjectId RelOID;
ObjectId testbufrelOID;
int RelNpages;

extern char *abstimeout(), *reltimeout();	/* ../adt/date.c */

#define VACSLEEPTIME (5*60)

vacuuminit()
{
	int i;
	struct RelNameListData *ptr, *saveptr;

	for (i=0; i<NLISTS; i++) {
		ListHT[i].ListHead = ListHT[i].ListTail = NULL;
		ListHT[i].ListCount = 0;
	}
	RelOID = InvalidObjectId;
	RelNpages = 0;
	if (RelNameList != NULL) {
		ptr = RelNameList;
		while (ptr != NULL) {
			saveptr = ptr->next;
			free(ptr);
			ptr = saveptr;
		}
	}
	RelNameList = NULL;
}

StartVacuum()
{
	char currentrelationrelname[20];
	char currentrelationrelkind;
	struct RelNameListData *currentrel, *newrel;
    Relation relation;
    HeapScan sdesc;
    HeapTuple tup;
    int count, i, j, fd;
    Buffer buffer;
    Page page;
	bool done;
#ifdef VACONESHOT
	bool firsttime = true;
#endif
	
	vacuuminit();

	while (true) {
		StartTransactionCommand();
		relation = amopenr(RelationRelationName);
		sdesc = ambeginscan(relation, false, NowTimeQual, 0, 
			(ScanKey) NULL);

		while ((tup = amgetnext(sdesc, false, (Buffer *) 0)) != NULL) {
			newrel = (struct RelNameListData *) calloc(1, sizeof(struct
				RelNameListData));

			if (RelNameList == NULL) 
				RelNameList = newrel;
			else {
				currentrel = RelNameList;
				while (currentrel->next != NULL)
					currentrel = currentrel->next;
				currentrel->next = newrel;
			}
			newrel->next = NULL;

			/* printf("%s\n", ((struct relation *)GETSTRUCT(tup))->relname); */
			strcpy(newrel->relname,
				((struct relation *)GETSTRUCT(tup))->relname);
			newrel->relkind = ((struct relation *)GETSTRUCT(tup))->relkind;
		}
		amendscan(sdesc);
		amclose(relation);
		CommitTransactionCommand();

		done = false;

		count = 0;

		while (done == false) {
			currentrel = RelNameList;
			if (currentrel != NULL) {
				for (i=0; i<count; i++) 
					currentrel = currentrel->next;
				currentrel = currentrel->next;
			}
			if (currentrel != NULL) {
				strcpy(currentrelationrelname, currentrel->relname);
				currentrelationrelkind = currentrel->relkind;
				count++;
			} else
				done = true;

			if (done == false && currentrelationrelkind == 'r') {
				StartTransactionCommand();
#ifdef VACOUTPUT
				printf("%s; ", currentrelationrelname);
#endif
				relation = amopenr(currentrelationrelname);
				RelOID = (ObjectId) relation->rd_att.data[0]->attrelid;
#ifdef VACOUTPUT
				printf("relation OID: %d; ", RelOID);
				if (!strcmp(currentrelationrelname, "testbufrel")) {
					testbufrelOID = RelOID;
					printf("testbufrel OID: %d\n", testbufrelOID);
				}
#endif
				RelNpages = RelationGetNumberOfBlocks(relation);
#ifdef VACOUTPUT
				printf("number of blocks: %d\n", RelNpages);
#endif
				for (j=0; j < RelNpages; j++) {
					buffer = RelationGetBuffer(relation, j, L_PIN);
					page = BufferSimpleGetPage(buffer);
					ProcessPage(relation, page, j, 0);
					BufferPut(buffer, L_UNPIN);
				}
				amclose(relation);

				if (j != 0) {
#ifdef VACOUTPUT
					printf("before analysis:\n");
					printlistcounts();
#endif
					analyzelists();
#ifdef VACOUTPUT
					printf("after analysis:\n");
					printlistcounts();
#endif
					scavenge_space();
				}

				/*
				printf("after scavenging space on pages:\n");
				printlistcounts();
				*/

				for (i=0; i<NLISTS; i++)
					deletefromlist(i, InvalidObjectId, (ItemPointer) NULL, 
						(struct VacTidListData **) NULL);

				/*
				printf("after freeing lists:\n");
				printlistcounts();
				*/

				CommitTransactionCommand();
			} 
		}
		if (RelNameList != NULL) {
			currentrel = RelNameList;
			while (currentrel != NULL) {
				newrel = currentrel->next;
				free(currentrel);
				currentrel = newrel;
			}
		}
		RelNameList = NULL;

#ifdef VACONESHOT
		if (firsttime == true) {
			firsttime = false;
#ifdef VACOUTPUT
			printf("----------------------------------------------------\n");
#endif
		} else
			break;
#else
		sleep(VACSLEEPTIME);
#endif
	}
}

printlistcounts()
{
    printf("# of elements on LIVELIST: %d\n", ListHT[LIVELIST].ListCount);
	if (RelOID == testbufrelOID) 
		printlist(LIVELIST);
    printf("# of elements on DEADLIST: %d\n", ListHT[DEADLIST].ListCount);
	if (RelOID == testbufrelOID) 
		printlist(DEADLIST);
    printf("# of elements on DOCNTLIST: %d\n", ListHT[DOCNTLIST].ListCount);
	if (RelOID == testbufrelOID) 
		printlist(DOCNTLIST);
    printf("# of elements on CTUPLIST: %d\n", ListHT[CTUPLIST].ListCount);
	if (RelOID == testbufrelOID) 
		printlist(CTUPLIST);
    printf("# of elements on RULELIST: %d\n", ListHT[RULELIST].ListCount);
	if (RelOID == testbufrelOID) 
		printlist(RULELIST);
}

analyzelists()
{
    checkdocntctup();
    checkrules();

	updatestats(RelOID, RelNpages, ListHT[LIVELIST].ListCount);
}

checkdocntctup()
{
    struct VacTidListData *docntp = ListHT[DOCNTLIST].ListHead;
    struct VacTidListData *ctupp;
    struct VacTidListData *savenext;
    struct VacTidListData *searchlist();
	ObjectId reloid;
    ItemPointer tidp;
    int i, limit = ListHT[DOCNTLIST].ListCount;

    for (i=0; i<limit; i++) {
        Assert(docntp != NULL);
		reloid = docntp->VacRelOID;
        tidp = &(docntp->VacContTid);
        /* follow list of DOCNTs to end.  not really necessary, due to */
        /* order of insertions (1st DOCNT inserted last)... */
        while (1) {
            ctupp = searchlist(CTUPLIST, reloid, tidp, false, false);
            Assert(ctupp != NULL);
            changelists(CTUPLIST, LIVELIST, ctupp, CTUPTOLIVEREASON);
            if (ctupp->VacHasContTid == true) {
				reloid = ctupp->VacRelOID;
                tidp = &(ctupp->VacContTid);
            } else
                break;
        }
        /* note: due to order of insertions (1st DOCNT inserted last), */
        /* no need to check if DOCNTLIST items go on DEADLIST... */
		savenext = docntp->NextVacTid;
        changelists(DOCNTLIST, LIVELIST, docntp, DOCNTTOLIVEREASON);
        docntp = savenext;
    }

    /* fragments go on dead list */
    limit = ListHT[CTUPLIST].ListCount;
    ctupp = ListHT[CTUPLIST].ListHead;
    for (i=0; i<limit; i++) {
        Assert(ctupp != NULL);
		savenext = ctupp->NextVacTid;
        changelists(CTUPLIST, DEADLIST, ctupp, CTUPTODEADREASON);
        ctupp = savenext;
    }
}

checkrules()
{
    struct VacTidListData *rulep = ListHT[RULELIST].ListHead;
    struct VacTidListData *livep;
    struct VacTidListData *savenext;
    struct VacTidListData *searchlist();
    int i, rulelimit = ListHT[RULELIST].ListCount;
    int j, livelimit = ListHT[LIVELIST].ListCount;

    for(i=0; i<rulelimit; i++) {
        Assert(rulep != NULL);
        livep = searchlist(LIVELIST, rulep->VacRelOID, &(rulep->VacTid),
			true, false);
        savenext = rulep->NextVacTid;
        if (livep == NULL)
            changelists(RULELIST, DEADLIST, rulep, RULETODEADREASON);
        else
            changelists(RULELIST, LIVELIST, rulep, RULETOLIVEREASON);
        rulep = savenext;
    }
}

printlist(list)
	int list;
{
	int i;
	struct VacTidListData *vtlp;

#ifndef VACDEBUG
	return;
#endif
	for (i=0, vtlp = ListHT[list].ListHead; 
			i < ListHT[list].ListCount && vtlp != NULL;
			i++, vtlp = vtlp->NextVacTid) {
		printf("VacRelOID: %d\n", vtlp->VacRelOID);
		printf("VacTid: "); displaytid(&(vtlp->VacTid)); printf("\n");
		printf("VacContTid: "); displaytid(&(vtlp->VacContTid)); 
			printf("\n");
		printf("VacHasContTid: %d\n", vtlp->VacHasContTid);
		printf("VacRuleTid: "); displaytid(&(vtlp->VacRuleTid)); 
			printf("\n");
		printf("VacHasRuleTid: %d\n", vtlp->VacHasRuleTid);
		printf("VacReasonCode: %d\n", vtlp->VacReasonCode);
		printf("\t(reason translation: %s)\n",
			reason[vtlp->VacReasonCode].reasonline);
	}
}

scavenge_space()
{
    int i;
	Relation relation;
	Buffer buffer;
	Page page;
	ObjectId reloid;
	ItemPointer tidp;
	struct VacTidListData *searchlist(), *vtlp, *listentry;
	ItemId lp;
	struct VacTidListData *auxp;
	OffsetIndex offsetindex;
	Offset upper;
	Size alignedSize;

	while (ListHT[DEADLIST].ListCount > 0) {
#ifdef VACDEBUG
		printf("DEADLIST follows:\n");
		printlist(DEADLIST);
#endif
		/* free entries on TEMPLIST */
		deletefromlist(TEMPLIST, InvalidObjectId, (ItemPointer) NULL, 
			(struct VacTidListData **) NULL);

		listentry = ListHT[DEADLIST].ListHead;
		reloid = listentry->VacRelOID;
		tidp = &(listentry->VacTid);
		changelists(DEADLIST, TEMPLIST, listentry, DEADTOTEMPREASONA);

		relation = amopen(ListHT[TEMPLIST].ListHead->VacRelOID);
		buffer = RelationGetBuffer(relation, 
			ItemPointerGetBlockNumber(&(ListHT[TEMPLIST].ListHead->VacTid)),
			/* ItemPointerGetPageNumber(&(ListHT[TEMPLIST].ListHead->VacTid),
			SinglePagePartition),*/ L_EX);
		page = BufferSimpleGetPage(buffer);

		while ((vtlp = searchlist(DEADLIST, reloid, tidp, false, true)) 
			!= NULL)
				changelists(DEADLIST, TEMPLIST, vtlp, DEADTOTEMPREASONB);
#ifdef VACDEBUG
		printf("after finding dead items on same page as 1st in list,\n");
		printf("TEMPLIST follows:\n");
		printlist(TEMPLIST);
#endif
		auxp = ListHT[TEMPLIST].ListHead;
		for (i=0; i<ListHT[TEMPLIST].ListCount; i++) {
			Assert(auxp != NULL);
			offsetindex = ItemPointerGetOffsetIndex(&(auxp->VacTid),
				SinglePagePartition);
#ifdef VACDEBUG
			printf("marking the following item as unused: ");
			displaytid(&(auxp->VacTid)); printf("\n");
#endif
			lp = ((PageHeader)page)->pd_linp + offsetindex;
#ifdef VACDEBUG
			printf("\tflags: %x\n", (*lp).lp_flags);
#endif
				/* logically delete heap tuple */
			(*lp).lp_flags &= ~LP_USED;	
				/* phys delete index tuple */
			deleteindexrecord(auxp->VacRelOID, &(auxp->VacTid)); 
			auxp = auxp->NextVacTid;
		}

		PageRepairFragmentation(page);	/* physically delete heap tups on pg */
		BufferPut(buffer,L_WRITE|L_UN|L_EX);
		amclose(relation);
	}
}

/*
 * algorithm for deleteindexrecord(): 
 *
 * scan IndexRelationName, foreach tuple which has heaprelOID == 
 *		OID of heap rel:
 *	amopen the index OID
 *	scan that (index) relation, using
 *		IndexScanGetRetrieveIndexResult() to get 
 *		back heap/index tids
 *	if heap tid of heap tuple == heap tid of index tuple
 *		call RelationDeleteIndexTuple(indexrelation, index tid)
 */

deleteindexrecord(heapreloid, heaptidp)
	ObjectId heapreloid;
	ItemPointer heaptidp;
{
	Relation	heapRelation;
	Relation	indexRelation;
	HeapScan	heapscan;
	IndexScan	indexscan;
	HeapTuple	heapTuple;
	Buffer		buffer;
	TupleDescriptor	heapDescriptor;
	ObjectId	indexRelationId;
	ObjectId	heapRelationId;
	Boolean		attributeIsNull;
	RetrieveIndexResult retrieveIndexResult;
	int nindextuples;

	heapRelation = RelationNameOpenHeapRelation(IndexRelationName);
	heapDescriptor = RelationGetTupleDescriptor(heapRelation);

	heapscan = RelationBeginHeapScan(heapRelation, 0, (struct trange *)NULL,
		0, (ScanKey)NULL);

	while (HeapTupleIsValid(
			heapTuple = HeapScanGetNextTuple(heapscan, 0, &buffer))) {

		indexRelationId = DatumGetObjectId(
			HeapTupleGetAttributeValue(heapTuple, buffer, 
				IndexRelationIdAttributeNumber, heapDescriptor,
				&attributeIsNull));

		heapRelationId = DatumGetObjectId(
			HeapTupleGetAttributeValue(heapTuple, buffer, 
				IndexHeapRelationIdAttributeNumber,
				heapDescriptor, &attributeIsNull));

		/* process heapRelationId, indexRelationID ... */
		if (heapRelationId == heapreloid) {
			/*
			 *	amopen the index OID
			 *	scan that (index) relation, using
			 *		IndexScanGetRetrieveIndexResult() to get 
			 *		back heap/index tids
			 *	if heap tid of heap tuple == heap tid of index tuple
			 *		call RelationDeleteIndexTuple(indexrelation, index tid)
			 */
			indexRelation = ObjectIdOpenIndexRelation(indexRelationId);
			indexscan = RelationGetIndexScan(indexRelation, false, 0, 
				(ScanKey)NULL);

			nindextuples = 0;

				/* scan the index */
			while (RetrieveIndexResultIsValid(retrieveIndexResult =
					IndexScanGetRetrieveIndexResult(indexscan, false))) {
				if (ItemPointerEquals(heaptidp,
					RetrieveIndexResultGetHeapItemPointer(
						retrieveIndexResult))) {

					RelationDeleteIndexTuple(indexRelation,
						RetrieveIndexResultGetIndexItemPointer(
							retrieveIndexResult));

					/* 1-{0,1,n} correspondence between index/heap tups */
				} else
					nindextuples++;
			}
			IndexScanEnd(indexscan);
			RelationCloseIndexRelation(indexRelation);
			updatestats(indexRelationId, 
				RelationGetNumberOfBlocks(indexRelationId), nindextuples);
		}
	}
	HeapScanEnd(heapscan);
	RelationCloseHeapRelation(heapRelation);
}

ProcessPage(relation, page, blockNumber, pageNumber)
    Relation relation;
    Page    page;
    int blockNumber;
    int pageNumber;
{
    ItemId      lp;
    HeapTuple   tup;
    int     flags, i, nline;
    ItemPointerData tidstruct;
    ItemPointer tidptr;
	bool isctup;
	ABSTIME newtime, currenttime;

#ifdef VACDUMPBPAGE
    printf("\t[%d]:lower=%d:upper=%d:special=%d\n", pageNumber,
        ((PageHeader)page)->pd_lower, ((PageHeader)page)->pd_upper,
        ((PageHeader)page)->pd_special);

    printf("\t:MaxOffsetIndex=%d:InternalFragmentation=%d\n",
        (int16)PageGetMaxOffsetIndex(page),
        PageGetInternalFragmentation(page));
#endif

    nline = 1 + (int16)PageGetMaxOffsetIndex(page);

#ifdef VACDUMPBPAGE
    /* add printing of the specially allocated fields */
{
    int i;
    char    *cp;

    i = PageGetSpecialSize(page);
    cp = PageGetSpecialPointer(page);

    printf("\t:SpecialData=");

    while (i > 0) {
        printf(" 0x%02x", *cp);
        cp += 1;
        i -= 1;
    }
    printf("\n");
}
#endif

    for (i = 0; i < nline; i++) {
        lp = ((PageHeader)page)->pd_linp + i;
        flags = (*lp).lp_flags;

        if ((flags & LP_USED) == 0)
            continue;
        if (flags & LP_LOCK) {
            ItemPointerSimpleSet(&tidstruct, blockNumber, i + 1);
            addtolist(RULELIST, &tidstruct, 
                (struct VacTidListData *) NULL, (ItemPointer) NULL,
                (ItemPointer) NULL, RULEREASON);
            continue;
        }

#ifdef VACDUMPBPAGE
        printf("[%u,%u,%u]:off=%d:flags=0x%x:len=%d", blockNumber,
            pageNumber, i + 1, (*lp).lp_off, flags, (*lp).lp_len);
        if (flags & LP_USED)
            printf(":USED");
        if (flags & LP_IVALID) 
            printf(":IVALID"); 
        if (flags & LP_DOCNT) {
            PagePartition   partition;
            ItemPointer pointer;

            partition = CreatePagePartition(BLCKSZ,
                PageGetPageSize(page));
            pointer = (ItemPointer)(uint16 *)
                ((char *)page + (*lp).lp_off);
            
            printf(":DOCNT@[%u,%u,%u]",
                ItemPointerGetBlockNumber(pointer),
                ItemPointerGetPageNumber(pointer, partition),
                ItemPointerGetOffsetNumber(pointer, partition));
        }
        if (flags & LP_CTUP)
            printf(":CTUP");
        if (flags & LP_LOCK)
            printf(":LOCK");
        if (flags & LP_IVALID)
            printf(":IVALID");
        putchar('\n');
#endif
		if ((flags & LP_CTUP) == 0) {
			isctup = false;
			tup = (HeapTuple)&((char *)page)[(*lp).lp_off +
				((flags & LP_DOCNT) ? TCONTPAGELEN : 0)];
		} else {
			isctup = true;
			tup = (HeapTuple) NULL;
		}

		/* if has a tuple header (!isctup), check for aborted insert
		 * and purged tup
		 */
		if (!isctup) {
        	/* check for insert that aborted */
			if ((flags & LP_IVALID) == 0) {
				if (TransactionIdIsValid(tup->t_xmin)) {
					if (TransactionIdDidAbort(tup->t_xmin) == true) {
						addtolist(DEADLIST, &(tup->t_ctid), 
						  (struct VacTidListData *) NULL, (ItemPointer) NULL,
						  &(tup->t_lock.l_ltid), ABORTREASON);
						continue;
					} else if (TransactionIdDidCommit(tup->t_xmin) == true &&
						TimeIsValid(tup->t_tmin) == false)
						tup->t_tmin = TransactionIdGetCommitTime(tup->t_xmin);
				}
			}

        	/* check for purged tup */
			if (TransactionIdIsValid(tup->t_xmax)) {
				if (TransactionIdDidCommit(tup->t_xmax) == true) {
					if (TimeIsValid(tup->t_tmax) == false) 
						tup->t_tmax = 
							TransactionIdGetCommitTime(tup->t_xmax);

					/* use either restrictive time... either could be invalid,
					 * if both are invalid, preserve forever... 
					 */
#ifdef VACPRINTTIMES
					if (TimeIsValid(relation->rd_rel->relexpires) == true) {
						printf("relexpires: %s\n", 
							abstimeout(relation->rd_rel->relexpires));
						printf("tup->t_tmax: %s\n", abstimeout(tup->t_tmax));
					}
					if (TimeIsValid(relation->rd_rel->relpreserved) == true) {
						printf("relpreserved: %s\n",
							reltimeout(relation->rd_rel->relpreserved));
						printf("current time: %s\n", 
							abstimeout(currenttime = GetCurrentTime()));
						newtime = currenttime + relation->rd_rel->relpreserved;
						printf("newtime (current + relpreserved): %s\n",
							abstimeout(newtime));
						printf("tup->t_tmax: %s\n", abstimeout(tup->t_tmax));
					}
#endif
					if ((TimeIsValid(relation->rd_rel->relexpires) == true &&
						tup->t_tmax < relation->rd_rel->relexpires) ||
						(TimeIsValid(relation->rd_rel->relpreserved) == true &&
						tup->t_tmax < (newtime = GetCurrentTime() + 
						relation->rd_rel->relpreserved))) {
							addtolist(DEADLIST, &(tup->t_ctid), 
								(struct VacTidListData *) NULL, 
								(ItemPointer) NULL, &(tup->t_lock.l_ltid),
								PURGEREASON);
							continue;
					}
				} else if (TransactionIdDidAbort(tup->t_xmax) == true) {
					tup->t_tmax = InvalidTime;
					PointerStoreInvalidTransactionId(tup->t_xmax);
				}
			}
		}

        if (flags & LP_DOCNT) {
            /* if first in DOCNT-CTUP(,DOCNT)-...-CTUP chain, */
            /* put on DOCNTLIST.  Otherwise, put on CTUPLIST. */
            ItemPointerSimpleSet(&tidstruct, blockNumber, i + 1);
            tidptr = (ItemPointer)&((char *)page)[(*lp).lp_off];
            addtolist(!isctup? DOCNTLIST:CTUPLIST,
                &tidstruct, (struct VacTidListData *) NULL, tidptr,
                !isctup? &(tup->t_lock.l_ltid) : (ItemPointer) NULL, 
                !isctup? DOCNTREASONA:DOCNTREASONB);
			continue;
        }
        if (isctup) {	/* flags & LP_CTUP */
            ItemPointerSimpleSet(&tidstruct, blockNumber, i + 1);
            addtolist(CTUPLIST, &tidstruct,
                (struct VacTidListData *) NULL, (ItemPointer) NULL,
				(ItemPointer) NULL, CTUPREASON);
			continue;
        }

		addtolist(LIVELIST, &(tup->t_ctid),
			(struct VacTidListData *) NULL, (ItemPointer) NULL,
			&(tup->t_lock.l_ltid), LIVEREASON);

#ifdef VACDUMPBPAGE
        printf("\tlen=%ld:ctid=", tup->t_len);
        displaytid(&tup->t_ctid);
        printf(":oid=%ld:", tup->t_oid);
        printf("chain=");
        displaytid(&tup->t_chain);
        printf(":anchor=");
        displaytid(&tup->t_anchor);
        printf("natts=%d:thoff=%d:vtype=`%c'\n", tup->t_natts,
            tup->t_hoff, tup->t_vtype);
#endif
    }
}

vacuumdebug(p1, p2)
	BlockNumber p1, p2;
{
}

addtolist(list, tidp, vtlp, conttidp, ruletidp, reasoncode)
    int list;
    ItemPointer tidp;
    struct VacTidListData *vtlp;
    ItemPointer conttidp, ruletidp;
    int reasoncode;
{
    struct VacTidListData *oldlast;

	/*
	if (list == DEADLIST)
		vacuumdebug();
	*/

	if (reasoncode == ABORTREASON) {
		printf("found aborted insert in relation id: %d\n", RelOID);
	}
    if (vtlp == NULL) {
        vtlp = (struct VacTidListData *) palloc(sizeof(struct VacTidListData));
		bzero((char *) vtlp, sizeof(struct VacTidListData));
        ItemPointerCopy(tidp, &(vtlp->VacTid));
		vtlp->VacRelOID = RelOID;
        /* if (conttidp != NULL) { */
        if (ItemPointerIsValid(conttidp)) {
            ItemPointerCopy(conttidp, &(vtlp->VacContTid));
            vtlp->VacHasContTid = true;
        } else
            vtlp->VacHasContTid = false;
        /* if (ruletidp != NULL) { */
        if (ItemPointerIsValid(ruletidp)) {
            ItemPointerCopy(ruletidp, &(vtlp->VacRuleTid));
            vtlp->VacHasRuleTid = true;
        } else
            vtlp->VacHasRuleTid = false;
    }
    vtlp->VacReasonCode = reasoncode;

		/* check for empty list */
    if (ListHT[list].ListHead == NULL && ListHT[list].ListTail == NULL) {
        ListHT[list].ListHead = ListHT[list].ListTail = vtlp;
    } else {
		Assert(ListHT[list].ListTail != NULL);
        oldlast = ListHT[list].ListTail;
        oldlast->NextVacTid = ListHT[list].ListTail = vtlp;
    }
    vtlp->NextVacTid = NULL;
    ListHT[list].ListCount++;
#ifdef VACDEBUG
    printf("addtolist: list: %s, reloid: %d, reason: %s\n",
		lists[list].listname, vtlp->VacRelOID, 
		reason[reasoncode].reasonline);
	if (ItemPointerIsValid(tidp)) {
		printf("tidp: ");
		displaytid(tidp);
		printf("; ");
	}
	if (ItemPointerIsValid(conttidp)) {
		printf("conttidp: ");
		displaytid(conttidp);
		printf("; ");
	}
	if (ItemPointerIsValid(ruletidp)) {
		printf("ruletidp: ");
		displaytid(ruletidp);
		printf("; ");
	}
	printf("\n");
#endif
}

deletefromlist(list, reloid, tidp, vtlpp)
    int list;
	ObjectId reloid;
    ItemPointer tidp;
    struct VacTidListData **vtlpp;
{
    struct VacTidListData *element;
    struct VacTidListData *p; /* predecessor */
    struct VacTidListData *s; /* successor */

    if (tidp == NULL) {	/* delete entire list if tidp == NULL */
        element = ListHT[list].ListHead;
        while (element != NULL) {
            s = element->NextVacTid;
            pfree(element);
            element = s;
        }
        ListHT[list].ListHead = ListHT[list].ListTail = NULL;
        ListHT[list].ListCount = 0;
        return(0);
    }

    Assert(ListHT[list].ListCount > 0);

    p = NULL;
    element = ListHT[list].ListHead;

    while (element != NULL) {
        if (element->VacRelOID == reloid &&
			ItemPointerEquals(&(element->VacTid), tidp))
            break;
        p = element;
        element = element->NextVacTid;
    }
    if (element == NULL)
        return(-1);

    /* check for 1 element list */
    if (ListHT[list].ListHead == ListHT[list].ListTail) 
        ListHT[list].ListHead = ListHT[list].ListTail = NULL;

    else {	/* >1 elements in list */

        /* check for search element == 1st element */
        if (element == ListHT[list].ListHead)
            ListHT[list].ListHead = element->NextVacTid;

		/* check for search element == last element */
        else if (element == ListHT[list].ListTail) { 
			ListHT[list].ListTail = p;
			p->NextVacTid = NULL;

		} else
            p->NextVacTid = element->NextVacTid;
    }
    if (vtlpp == NULL)
        pfree(element);
    else
        *vtlpp = element;
    ListHT[list].ListCount--;
    return(0);
}

struct VacTidListData *
searchlist(list, reloid, tidp, ruletidsearch, pagenumsearch)
    int list;
	ObjectId reloid;
    ItemPointer tidp;
    bool ruletidsearch;
	bool pagenumsearch;
{
    struct VacTidListData *auxp;
	bool comparetidpagenums();

    auxp = ListHT[list].ListHead;

    while (auxp != NULL) {
        if (ruletidsearch == false && pagenumsearch == false) {
#ifdef VACDEBUG
			printf("auxp->VacRelOID: %d, reloid: %d\n",
				auxp->VacRelOID, reloid);
			printf("\tauxp->VacTid: (block: %d, offset: %d)\n",
				ItemPointerGetBlockNumber(&(auxp->VacTid)),
				ItemPointerGetOffsetNumber(&(auxp->VacTid), 
				SinglePagePartition));
			printf("\ttid: (block: %d, offset: %d)\n",
				ItemPointerGetBlockNumber(tidp),
				ItemPointerGetOffsetNumber(tidp, SinglePagePartition));
#endif
            if (auxp->VacRelOID == reloid &&
				ItemPointerEquals(&(auxp->VacTid), tidp))
                return(auxp);
        } else if (ruletidsearch == true) {
            if (auxp->VacHasRuleTid == true &&
                auxp->VacRelOID == reloid &&
				ItemPointerEquals(&(auxp->VacRuleTid), tidp))
                    return(auxp);
        } else if (pagenumsearch == true) {
#ifdef VACDEBUG
			printf("searchlist trace data follows: \n");
			printf("auxp->VacRelOID: %d, reloid: %d\n",
				auxp->VacRelOID, reloid);
			printf("\tauxp->VacTid: (block: %d, offset: %d)\n",
				ItemPointerGetBlockNumber(&(auxp->VacTid)),
				ItemPointerGetOffsetNumber(&(auxp->VacTid), 
				SinglePagePartition));
			printf("\ttid: (block: %d, offset: %d)\n",
				ItemPointerGetBlockNumber(tidp),
				ItemPointerGetOffsetNumber(tidp, SinglePagePartition));
#endif
			if (auxp->VacRelOID == reloid &&
				comparetidpagenums(&(auxp->VacTid), tidp) == true) {
				/* printf("page numbers match\n"); */
				return(auxp);
			}
		}
        auxp = auxp->NextVacTid;
    }
    return(NULL);
}

changelists(fromlist, tolist, listentry, reasoncode)
    int fromlist, tolist;
	struct VacTidListData *listentry;
    int reasoncode;
{
    struct VacTidListData *vtlp;

    Assert(deletefromlist(fromlist, listentry->VacRelOID, 
		&(listentry->VacTid), &vtlp) != -1);

    addtolist(tolist, &(listentry->VacTid), vtlp, (ItemPointer) NULL,
		(ItemPointer) NULL, reasoncode);
}

bool
comparetidpagenums(tidp1, tidp2)
    ItemPointer tidp1, tidp2;
{
	BlockNumber p1, p2;

    p1 = ItemPointerGetBlockNumber(tidp1);
    p2 = ItemPointerGetBlockNumber(tidp2);

#ifdef VACDEBUG
	printf("comparetidpagenum trace data follows: \n");
	printf("tidp1: "); displaytid(tidp1); printf("\n");
	printf("tidp2: "); displaytid(tidp2); printf("\n");
	printf("tidp1's page number: %d\n", p1);
	printf("tidp2's page number: %d\n", p2);

	vacuumdebug(p1, p2);
#endif

    if (p1 == p2)
        return(true);
    else
        return(false);
}

displaytid(tidP)
ItemPointer tidP;
{
    printf("(%d,%d,%d)", ((short *)tidP)[0], ((short *)tidP)[1],
        ((short *)tidP)[2]);
}

updatestats(reloid, npages, ntuples)
	ObjectId reloid;
	int npages, ntuples;
{
	register		i;
	Relation		relation;
	HeapScan		scan;
	static ScanKeyEntryData	key[1] = {
		{ 0, T_OID, F_OIDEQ }
	};
	Buffer			buffer;
	HeapTuple		newTuple, oldTuple;
	char			*values[RelationRelationNumberOfAttributes];
	char			nulls[RelationRelationNumberOfAttributes];
	char			replace[RelationRelationNumberOfAttributes];

	/*
	 * Find the RELATION relation tuple for the given relation.
	 */
	relation = RelationNameOpenHeapRelation(RelationRelationName->data);
	if (!RelationIsValid(relation)) {
		elog(WARN, "updatestats: could not open RELATION relation");
		return(0);
	}
	key[0].argument.objectId.value = reloid;
	scan = RelationBeginHeapScan(relation, 0, NowTimeQual, 1, 
				     (ScanKey) key);
	if (!HeapScanIsValid(scan)) {
		RelationCloseHeapRelation(relation);
		elog(WARN, "updatestats: cannot scan RELATION relation");
		return(0);
	}
	oldTuple = HeapScanGetNextTuple(scan, 0, &buffer);
	if (!HeapTupleIsValid(oldTuple)) {
		HeapScanEnd(scan);
		RelationCloseHeapRelation(relation);
		elog(WARN, "updatestats: no such relation: %d", reloid);
		return(0);
	}
	
	for (i = 0; i < RelationRelationNumberOfAttributes; ++i) {
		nulls[i] = ' ';
		values[i] = NULL;
		replace[i] = ' ';
	}
	if (npages != -1) {
		values[RelationPagesAttributeNumber-1] = (char *) npages;
		replace[RelationPagesAttributeNumber-1] = 'r';
	}
	if (ntuples != -1) {
		values[RelationTuplesAttributeNumber-1] = (char *) ntuples;
		replace[RelationTuplesAttributeNumber-1] = 'r';
	}
	
	/*
	 * Change the RELATION relation tuple for the given relation.
	 */
	newTuple = ModifyHeapTuple(oldTuple, buffer, relation, values,
				   nulls, replace);
	if (!HeapTupleIsValid(newTuple)) {
		HeapScanEnd(scan);
		RelationCloseHeapRelation(relation);
		elog(WARN, "updatestats: could not modify RELATION entry for %d",
		     reloid);
		return(0);
	}
	(void) RelationReplaceHeapTuple(relation, &newTuple->t_ctid, newTuple);
	pfree(newTuple);
	HeapScanEnd(scan);
	RelationCloseHeapRelation(relation);
	return(1);
}