cpi.c

uClinux下用的数据库

/*
** cpi.c   - Clusteres Page Index library (CPI)
**
** Copyright (c) 1998  Hughes Technologies Pty Ltd
**
** This library was written for Mini SQL 3.
**
*/

#include <stdio.h>
#include <fcntl.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/mman.h>
#include <sys/stat.h> 

#include <common/config.h>
#include <common/config_extras.h>
#include <common/portability.h>

#ifdef HAVE_STRINGS_H
#  include <strings.h>
#endif

#include "cpi_priv.h"

#define	_REG register

/*************************************************************************
**************************************************************************
**
**                        CACHE ROUTINES
**
**************************************************************************
*************************************************************************/

static void cacheInitialise(idx)
	cpi	*idx;
{
	char	*cp;
	_REG	cpi_ch	*cur;
	_REG	int	count;

	idx->cache = (char *)malloc(CPI_SBK(idx)->cacheSize * sizeof(cpi_ch));
	cp = idx->cache;
	for (count = 0; count < CPI_SBK(idx)->cacheSize; count++)
	{
		cur = (cpi_ch *)cp;
		cur->age = -1;
		cur->page = -1;
		cur->ptr = NULL;  
		cur->slot = count;
		cp += sizeof(cpi_ch);
	}
}



static cpi_ch *readPage(idx, pageNum)
	cpi	*idx;
	u_int	pageNum;
{
	char	*cp;
	int	slot,
		age,
		hash,
		oldHash;
	off_t	offset;
	static	cpi_cch accessHash[CPI_CCH_SIZE];
	_REG	int count;
	_REG	cpi_ch	*cur;

	/*
	** To speed up access to cached pages we "cache" the last 
	** accesses to the cache in a "cache cache hash".  Sounds wierd
	** but it doubles the overall performance of various ops.
	*/
	hash = pageNum % CPI_CCH_SIZE;
	if (accessHash[hash].pageNum == pageNum && accessHash[hash].idx == idx)
	{
		CPI_SBK(idx)->cacheLookups++;
		CPI_SBK(idx)->cacheHits++;
		cur = accessHash[hash].page;
		cur->age = 0;
		return(cur);
	}
	
	/*
	** Scan the cache for the page and keep note of any slots we
	** can use if we need to load the page
	*/
	cur = NULL;
	CPI_SBK(idx)->cacheLookups++;
	age = 0;
	slot = count = 0;
	cp = idx->cache;
	while(count < CPI_SBK(idx)->cacheSize)
	{
		cur = (cpi_ch *)cp;
		if (cur->page == pageNum)
		{
			cur->age = 0;
			CPI_SBK(idx)->cacheHits++;
			accessHash[hash].pageNum = pageNum;
			accessHash[hash].idx = idx;
			accessHash[hash].page = cur;
			return(cur);
		}
		if (cur->age == -1)
		{
			/* free slot */
			age = -1;
			slot = count;
			break;
		}
		cur->age++;
		if (cur->age > age)
		{
			age = cur->age;
			slot = count;
		}
		cp += sizeof(cpi_ch);
		count++;
	}

	/*
	** OK, we didn't find it in the cache so load it at the oldest
	** location (or empty location if we found an age of -1).
	*/
	cur = (cpi_ch*) (idx->cache + slot * sizeof(cpi_ch));
	if (age != -1)
	{
		if (cpiDebugCache)
		{
			printf("DEBUG  Unloading page %d from slot %d\n",
				cur->page, slot);
		}
		oldHash = cur->page % CPI_CCH_SIZE;
		if (accessHash[oldHash].pageNum == cur->page &&
			accessHash[oldHash].idx == idx)
		{
			accessHash[oldHash].idx = NULL;
		}
			
		munmap(cur->ptr, CPI_SBK(idx)->mapSize);
		cur->ptr = NULL;
	}
	if (cpiDebugCache)
	{
		printf("DEBUG  Cache load of page %d into slot %d\n", 
			pageNum, slot);
	}
	cur->age = 0;
	cur->page = pageNum;
	offset = (off_t) CPI_PAGE_OFFSET(idx, pageNum);
	cur->ptr = (caddr_t)mmap(NULL, CPI_SBK(idx)->mapSize, 
		(PROT_READ|PROT_WRITE), MAP_SHARED, idx->fd,  offset);
	accessHash[hash].pageNum = pageNum;
	accessHash[hash].idx = idx;
	accessHash[hash].page = cur;
	return(cur);
}


#define getCluster(idx, cachePtr, cluster, clusterPtr) { 		\
	(clusterPtr)->clusterNum = (cluster);				\
	(clusterPtr)->cacheSlot = cachePtr->slot;			\
	(clusterPtr)->numHeaders = (int *)cachePtr->ptr;		\
	(clusterPtr)->pageNum = (int *)(cachePtr->ptr + sizeof(u_int));	\
	(clusterPtr)->maxValue = cachePtr->ptr + (2 * sizeof(u_int));	\
}

#define getHeader(idx, cachePtr, cluster, header, headerPtr) {		\
	char	*basePtr;						\
	basePtr=cachePtr->ptr+CPI_CLS_SIZE(idx)+((header)*CPI_HDR_SIZE(idx));\
	(headerPtr)->numRecords = (int *)basePtr;			\
	(headerPtr)->pageNum = (int *)(basePtr + sizeof(int));		\
	(headerPtr)->maxValue = basePtr + (2 * sizeof(int));		\
	(headerPtr)->clusterNum = cluster;				\
	(headerPtr)->headerNum = header;				\
}

#define getRecord(idx, cachePtr, cluster, header, record, nodePtr) { 	\
	char	*basePtr; 						\
	basePtr = cachePtr->ptr + ((record) * CPI_REC_SIZE(idx));	\
	(nodePtr)->key = basePtr;					\
	(nodePtr)->data = *(u_int *)(basePtr + CPI_KEY_SIZE(idx));	\
	(nodePtr)->clusterNum = cluster;				\
	(nodePtr)->headerNum = header;					\
	(nodePtr)->recordNum = record;					\
}

/*************************************************************************
**************************************************************************
**
**                        DEBUG ROUTINES
**
**************************************************************************
*************************************************************************/


void cpiPrintIndexStats(idx)
	cpi	*idx;
{
        printf("CPI Index stats\n===============\n\n");
        printf("Path = %s\n",idx->path);
        printf("Version = %d\n",CPI_SBK(idx)->version);
        printf("Key Size = %d\n",CPI_SBK(idx)->keySize);
        printf("Rec Size = %d\n",(int)CPI_REC_SIZE(idx));
        printf("Page Size = %d\n",CPI_SBK(idx)->pageSize);
        printf("Records Per Page = %d\n",CPI_SBK(idx)->recsPerPage);
        printf("Headers Per Page = %d\n",CPI_SBK(idx)->hdrsPerPage);
        printf("Cache Size = %d\n",CPI_SBK(idx)->cacheSize);
        printf("Num Clusters = %d\n",CPI_SBK(idx)->numClusters);
        printf("Num Records = %d\n",CPI_SBK(idx)->numRecords);
        printf("Num Keys = %d\n",CPI_SBK(idx)->numKeys);
        printf("Cache Lookups = %.0f\n",CPI_SBK(idx)->cacheLookups);
        printf("Cache Hits = %.0f\n",CPI_SBK(idx)->cacheHits);
        printf("Cache Hit Rate = %d%%\n",CPI_CACHE_HIT_RATE(idx));
        printf("\n\n");
}



static void printValue(val, type)
	char	*val;
	int	type;
{
	switch(type)
	{
		case CPI_CHAR:
			printf("%s",val);
			return;

		case CPI_INT:
			printf("%d",(int)*(int *)val);
			return;

		case CPI_UINT:
			printf("%u",(u_int)*(u_int *)val);
			return;

		case CPI_REAL:
			printf("%f",(double)*(double *)val);
			return;

		default:
			printf("xxx");
			return;
	}
}



static void printHeader(idx, headerPtr)
	cpi	*idx;
	cpi_hdr	*headerPtr;
{
	printf("DEBUG  Header %d : Page=%d, Items=%d, Max=",
		headerPtr->headerNum, *headerPtr->pageNum, 
		*headerPtr->numRecords);
	printValue(headerPtr->maxValue, CPI_SBK(idx)->keyType);
	printf("\n");
}



static void printCluster(idx, clusterPtr)
	cpi	*idx;
	cpi_cls	*clusterPtr;
{
	printf("DEBUG  Cluster %d : Page=%d, Headers=%d, Max=",
		clusterPtr->clusterNum, *clusterPtr->pageNum, 
		*clusterPtr->numHeaders);
	printValue(clusterPtr->maxValue, CPI_SBK(idx)->keyType);
	printf("\n");
}




void cpiDumpIndex(idx)
	cpi	*idx;
{
	char	*lastValue = NULL,
		*barfReason = NULL;
	cpi_nod	nodeBuf;
	cpi_hdr	headerBuf;
	cpi_cls	clusterBuf;
	cpi_ch	*cachePtr;
	int	numHeaders,
		numRecords,
		res = 0,
		curCluster,
		curHeader,
		curRecord,
		barfCluster = -1,
		barfHeader = -1;
	

	curCluster = 0;
	while(curCluster < CPI_SBK(idx)->numClusters)
	{
		cachePtr = readPage(idx, CPI_CLS_PAGE(idx,curCluster));
		getCluster(idx, cachePtr, curCluster, &clusterBuf);
		numHeaders = *clusterBuf.numHeaders;
		curHeader = 0;
		while (curHeader < numHeaders)
		{
			cachePtr=readPage(idx,CPI_CLS_PAGE(idx,curCluster));
			getHeader(idx,cachePtr,curCluster,curHeader,&headerBuf);
			numRecords = *headerBuf.numRecords;
			curRecord = 0;
			printf("+H%d:%d P%d ---------------- Max = '", 
				curCluster,curHeader, *headerBuf.pageNum);
			printValue(headerBuf.maxValue, CPI_SBK(idx)->keyType);
			printf("'\n");

			cachePtr = readPage(idx, *headerBuf.pageNum);
			while (curRecord < numRecords)
			{
				getRecord(idx, cachePtr, curCluster,
					curHeader, curRecord, &nodeBuf);
				printf("|\t");
				printValue(nodeBuf.key, CPI_SBK(idx)->keyType);
				printf("\n");
				curRecord++;
				lastValue = nodeBuf.key;
			}
			compareValues(idx,lastValue,headerBuf.maxValue,res);
			if (res != 0)
			{
				if (barfCluster == -1)
				{
					barfCluster = curCluster;
					barfHeader = curHeader;
					barfReason = "Bad header max for %d:%d";
				}
			}
			curHeader++;
		}
		compareValues(idx,lastValue,clusterBuf.maxValue,res);
		if (res != 0)
		{
			if (barfCluster == -1)
			{
				barfCluster = curCluster;
				barfHeader = curHeader;
				barfReason = "Bad cluster max for %d";
			}
		}
		curCluster++;
	}
	printf("+------------------------\n\n");
	if (barfCluster != -1)
	{
		printf("\n\nERROR : Index corrupted\n\n\t");
		printf(barfReason,barfCluster, barfHeader);
		printf("\n\n");
		exit(1);
	}
	return;
}





int cpiTestIndex(idx)
	cpi	*idx;
{
	char	*lastValue = NULL,
		*barfReason = NULL;
	cpi_nod	nodeBuf;
	cpi_hdr	headerBuf;
	cpi_cls	clusterBuf;
	cpi_ch	*cachePtr;
	int	numHeaders,
		numRecords,
		res = 0,
		curCluster,
		curHeader,
		curRecord,
		barfCluster = -1,
		barfHeader = -1,
		recordCount;
	

	curCluster = 0;
	recordCount = 0;
	while(curCluster < CPI_SBK(idx)->numClusters)
	{
		cachePtr = readPage(idx, CPI_CLS_PAGE(idx,curCluster));
		getCluster(idx, cachePtr, curCluster, &clusterBuf);
		numHeaders = *clusterBuf.numHeaders;
		curHeader = 0;
		while (curHeader < numHeaders)
		{
			cachePtr=readPage(idx,CPI_CLS_PAGE(idx,curCluster));
			getHeader(idx,cachePtr,curCluster,curHeader,&headerBuf);
			numRecords = *headerBuf.numRecords;
			curRecord = 0;

			cachePtr = readPage(idx, *headerBuf.pageNum);
			while (curRecord < numRecords)
			{
				getRecord(idx, cachePtr, curCluster,
					curHeader, curRecord, &nodeBuf);
				curRecord++;
				recordCount++;
				lastValue = nodeBuf.key;
			}
			compareValues(idx,lastValue,headerBuf.maxValue,res);
			if (res != 0)
			{
				if (barfCluster == -1)
				{
					barfCluster = curCluster;
					barfHeader = curHeader;
					barfReason = "Bad header max for %d:%d";
				}
			}
			curHeader++;
		}
		compareValues(idx,lastValue,clusterBuf.maxValue,res);
		if (res != 0)
		{
			if (barfCluster == -1)
			{
				barfCluster = curCluster;
				barfHeader = curHeader;
				barfReason = "Bad cluster max for %d";
			}
		}
		curCluster++;
	}
	if (barfCluster != -1)
	{
		printf("\n\nERROR : Index corrupted\n\n\t");
		printf(barfReason,barfCluster, barfHeader);
		printf("\n\n");
		cpiDumpIndex(idx);
		printf("\n\n");
		exit(1);
	}
	return(recordCount);
}



/*************************************************************************
**************************************************************************
**
**                        UTILITY ROUTINES
**
**************************************************************************
*************************************************************************/



static int writeRecord(idx, clusterNum, headerNum, recordNum, nodePtr)
	cpi	*idx;
	int	clusterNum,
		headerNum,
		recordNum;
	cpi_nod	*nodePtr;
{
	static	cpi_hdr	headerBuf;
	static	cpi_ch	*cachePtr,
			*nodeCachePtr;
	static	char	*pagePtr;
	char	*basePtr;

	cachePtr = readPage(idx, CPI_CLS_PAGE(idx, clusterNum));

	getHeader(idx, cachePtr, clusterNum, headerNum, &headerBuf);
	nodeCachePtr = readPage(idx, *headerBuf.pageNum);
	pagePtr = nodeCachePtr->ptr;
	if (pagePtr == NULL)
		return(-1);
	basePtr = pagePtr + (recordNum * CPI_REC_SIZE(idx));

	bcopy(nodePtr->key, basePtr, CPI_KEY_SIZE(idx));
	*(int *)(basePtr + CPI_KEY_SIZE(idx)) = nodePtr->data;
	return(0);
}



static void initialiseCluster(idx, clusterNum)
	cpi	*idx;
	int	clusterNum;
{
	int	pageNum,
		listHead,
		fd;
	off_t	offset;
	u_int 	uval;
	_REG	int loop;


	if (cpiDebug)
	{
		printf("DEBUG  initialiseCluster %d\n",clusterNum);
	}
	/*
	** Setup the cluster / header page
	*/
	fd = idx->fd;
	pageNum = CPI_CLS_PAGE(idx,clusterNum);
	lseek(fd,CPI_PAGE_OFFSET(idx, pageNum), SEEK_SET);

	/* Cluster record */
	uval = 0;
	write(fd,&uval, sizeof(uval));
	uval = pageNum;
	write(fd,&uval, sizeof(uval));
	lseek(fd,CPI_SBK(idx)->keySize, SEEK_CUR);

	/* Header records */
	uval = 0;
	for (loop = 0; loop < CPI_SBK(idx)->hdrsPerPage; loop++)
	{
		write(fd,&uval, sizeof(uval));
		lseek(fd,CPI_SBK(idx)->keySize + sizeof(u_int), SEEK_CUR);
	}


	/*
	** Initialise the data pages and setup the free list.
	*/
	listHead = CPI_SBK(idx)->freeList;
	for (loop = 1; loop <= CPI_SBK(idx)->hdrsPerPage; loop++)
	{
		offset = CPI_PAGE_OFFSET(idx, pageNum + loop);
		lseek(fd,offset, SEEK_SET);
		if (loop < CPI_SBK(idx)->hdrsPerPage)
			uval = pageNum + loop + 1;
		else
			uval = listHead;  /* end of list */
		write(fd,&uval, sizeof(uval));
	}
	offset = CPI_PAGE_OFFSET(idx, pageNum + loop) - sizeof(uval);
	lseek(fd,offset, SEEK_SET);
	uval = 0;
	write(fd,&uval, sizeof(uval));

	/*
	** Update the super block
	*/
	CPI_SBK(idx)->numClusters += 1;
	CPI_SBK(idx)->freeList = pageNum + 1;
}



static char *getFreePage(idx, pageNum)
	cpi	*idx;
	int	*pageNum;
{
	cpi_ch	*cacheEntry;
	int	tmp;
	char	*pagePtr;

	/*
	** Pages in the free list have the page number of the next
	** free page stored in the first sizeof(int) bytes of the page.
	** The page num of the head of the free list is stored in the
	** superblock and must be reset on disk after we're done.
	*/
	if (CPI_SBK(idx)->freeList == 0)
	{
		abort();
	}
	*pageNum = CPI_SBK(idx)->freeList;
	if (cpiDebug)
	{
		printf("DEBUG  getFreePage returning page %d\n", *pageNum);
	}
	cacheEntry = readPage(idx, *pageNum);
	pagePtr = cacheEntry->ptr;
	tmp = (int)*(int *)pagePtr;
	CPI_SBK(idx)->freeList = tmp;
	return(pagePtr);
}




static int shiftDataPage(idx, clusterPtr, headerPtr, recordNum, direction)
	cpi	*idx;
	cpi_cls	*clusterPtr;
	cpi_hdr	*headerPtr;
	int	recordNum,
		direction;
{
	cpi_ch	*cacheEntry;
	char	*pagePtr,
		*cp,
		*cp1;

	/*
	** Get a pointer to the page holding the data records
	*/
	cacheEntry = readPage(idx, *headerPtr->pageNum);
	pagePtr = cacheEntry->ptr;
	if (pagePtr == NULL)
		return(-1);
	
	/*
	** Shuffle all the records in the page one slot starting
	** at the specified record.  
	*/
	if (cpiDebug)
	{
		printf("DEBUG  shiftDataPage %s %d:%d from %d\n",
			direction == CPI_SHIFT_UP?"up":"down",
			clusterPtr->clusterNum, headerPtr->headerNum, 
			recordNum);
	}
	if (direction == CPI_SHIFT_UP)
	{
		cp = pagePtr + (recordNum * CPI_REC_SIZE(idx));
		cp1 = cp + CPI_REC_SIZE(idx);
		bcopy(cp,cp1,(CPI_SBK(idx)->recsPerPage-recordNum-1) * 
			CPI_REC_SIZE(idx));
	}
	else
	{
		recordNum++;
		cp = pagePtr + (recordNum * CPI_REC_SIZE(idx));
		cp1 = cp - CPI_REC_SIZE(idx);
		bcopy(cp, cp1, (*headerPtr->numRecords-recordNum) * 
			CPI_REC_SIZE(idx));
	}
	return(0);
}




static void shiftHeaderPage(idx, clusterNum, headerNum, direction)
	cpi	*idx;
	int	clusterNum,
		headerNum,