cpi.c

uClinux下用的数据库

cpi *cpiOpen(path, envPtr)
	char	*path;
	cpi_env	*envPtr;
{
	cpi_ch	*cacheEntry;
	cpi	*new;


	/*
	** Open the file and map the superblock.  Ensure that the
	** file is an CPI file and it's the correct CPI version.
	*/
	apiInit();
	new = (cpi *)malloc(sizeof(cpi));
	new->fd = open(path, O_RDWR, 0);
	if (new->fd < 0)
	{
		perror("cpiOpen - open()");
		free(new);
		return(NULL);
	}
	new->opaque = (void *)mmap(NULL, getpagesize(),
		(PROT_READ|PROT_WRITE), MAP_SHARED, new->fd, (off_t)0);
	if (CPI_SBK(new)->magic != CPI_MAGIC)
	{
		free(new);
		fprintf(stderr, "\nCPI_ERROR : %s is not an CPI file!\n\n",
			path);
		return(NULL);
	}
	if (CPI_SBK(new)->version != CPI_VERSION)
	{
		free(new);
		fprintf(stderr, 
			"\nCPI_ERROR : Wrong version for %s (%d not %d)!\n\n",
			path, CPI_SBK(new)->version, CPI_VERSION);
		return(NULL);
	}
	new->path = (char *)strdup(path);

	/*
	** Initialise the cache and prime it with the important pages
	*/
	cacheInitialise(new);
	cacheEntry = readPage(new, 0);
	cacheEntry = readPage(new, 1);
	return(new);
}




void cpiSync(idx)
	cpi	*idx;
{
	char	*cp;
	cpi_ch	*cur;
	int	count;

	apiInit();
	cp = idx->cache;
	for(count = 0; count < CPI_SBK(idx)->cacheSize; count++)
	{
		cur = (cpi_ch *)cp;
		if (cur->ptr == NULL)
			continue;
		MSYNC(cur->ptr, CPI_SBK(idx)->mapSize,0);
                cp += sizeof(cpi_ch);
	}
}




void cpiClose(idx)
	cpi	*idx;
{
	char	*cp;
	cpi_ch	*cur;
	int	count;

	apiInit();
	cp = idx->cache;
	for(count = 0; count < CPI_SBK(idx)->cacheSize; count++)
	{
		cur = (cpi_ch *)cp;
		if (cur->ptr == NULL)
			continue;
		munmap(cur->ptr, CPI_SBK(idx)->mapSize);
		cur->ptr = NULL;
                cp += sizeof(cpi_ch);
	}
	free(idx->cache);
	idx->cache = NULL;
	munmap(idx->opaque, getpagesize());
	close(idx->fd);
}



int cpiInsert(idx, key, data)
	cpi	*idx;
	char	*key;
	u_int	data;
{
	cpi_ch	*cachePtr;
	cpi_nod	nodeBuf;
	cpi_hdr	headerBuf;
	cpi_cls	clusterBuf;
	int	insertPos,
		res;


	apiInit();
	if (cpiDebug)
	{
		char	*file;

		file = (char *)rindex(idx->path,'/');
		if (!file)
			file = idx->path;
		printf("DEBUG  Inserting '");
		printValue(key, CPI_SBK(idx)->keyType);
		printf("':%u in '%s'\n",data, file);
	}
	/*
	** Find the header of the page we're going to drop this
	** record into
	*/
	res = privateLookup(idx, key, &clusterBuf, &headerBuf,
		&nodeBuf, CPI_CLOSEST);
	if (res == -1)
		return(-1);
	if (res == CPI_ERR_NOT_FOUND)
	{
		/* The new value key is larger than any other key */
		nodeBuf.clusterNum = CPI_SBK(idx)->numClusters - 1;
		if (nodeBuf.clusterNum == -1)
		{
			/* First value in index */
			nodeBuf.clusterNum = 0;
		}
		cachePtr = readPage(idx,CPI_CLS_PAGE(idx,nodeBuf.clusterNum));
		getCluster(idx, cachePtr, nodeBuf.clusterNum, &clusterBuf);
		if (*clusterBuf.numHeaders == 0)
			nodeBuf.headerNum = 0;
		else
			nodeBuf.headerNum = *clusterBuf.numHeaders - 1;
		getHeader(idx, cachePtr, nodeBuf.clusterNum, nodeBuf.headerNum,
			&headerBuf);
	}

	/*
	** If there's room in this header then find the correct record pos.
	** Special case code for the first insertion (the only time we
	** create a new header without splitting into it)
	*/
	insertPos = -1;
	if (*headerBuf.numRecords == 0 && headerBuf.headerNum == 0 &&
		headerBuf.clusterNum == 0)
	{
		insertPos = 0;
		*(clusterBuf.numHeaders) += 1;
		getFreePage(idx, headerBuf.pageNum);
	}
	else
	{
		if (*headerBuf.numRecords < CPI_SBK(idx)->recsPerPage)
		{
			if (res != CPI_ERR_NOT_FOUND)
				insertPos = nodeBuf.recordNum;
			else
				insertPos = *headerBuf.numRecords;
		}
	}

	/*
	** If there's no room in this page we have to make some room.
	** Either we shift the headers to make a spare slot or we split
	** the cluster if there's no room left in this cluster.
	** The desired header position may have moved to another
	** cluster to just take the easy option and recurse on this
	** insertion rather than trying to remember where things are at.
	*/
	if (insertPos == -1)
	{
		if (*clusterBuf.numHeaders == CPI_SBK(idx)->hdrsPerPage)
		{
			createSpaceForCluster(idx, nodeBuf.clusterNum);
		}
		else
		{
			createSpaceForHeader(idx, nodeBuf.clusterNum, 
				nodeBuf.headerNum);
		}
		return(cpiInsert(idx,key,data));
	}

	/*
	** OK, insert the record at the determined position
	*/
	nodeBuf.key = key;
	nodeBuf.data = data;
	if (shiftDataPage(idx,&clusterBuf,&headerBuf,insertPos,CPI_SHIFT_UP)<0)
	{
		return(-1);
	}
	if (writeRecord(idx, nodeBuf.clusterNum, nodeBuf.headerNum, 
		insertPos, &nodeBuf) < 0)
	{
		return(-1);
	}
	*(headerBuf.numRecords) += 1;
	setMaxValue(idx, nodeBuf.clusterNum, nodeBuf.headerNum, key, 
		CPI_IF_NEEDED);
	if (cpiVerbose)
		cpiDumpIndex(idx);
	return(0);
}


static int privateLookup(idx, key, clusterPtr, headerPtr, nodePtr, flags)
	cpi	*idx;
	char	*key;
	cpi_cls	*clusterPtr;
	cpi_hdr	*headerPtr;
	cpi_nod	*nodePtr;	
	int	flags;
{
	int	curCluster,
		curHeader,
		curRecord,
		res = 0,
		min, max, pivot;
	cpi_ch	*clsCachePtr,
		*hdrCachePtr,
		*nodeCachePtr;
	cpi_cls	tmpClusterBuf;
	cpi_hdr	tmpHeaderBuf;


	if (clusterPtr == NULL)
		clusterPtr = &tmpClusterBuf;
	if (headerPtr == NULL)
		headerPtr = &tmpHeaderBuf;

	/*
	** Traverse the clusters looking for the desired cluster
	*/
	curCluster = 0;
	while (curCluster < CPI_SBK(idx)->numClusters)
	{
		clsCachePtr = readPage(idx, CPI_CLS_PAGE(idx, curCluster));
		getCluster(idx, clsCachePtr, curCluster, clusterPtr);
		if (*clusterPtr->numHeaders == 0)
			return(CPI_ERR_NOT_FOUND);
		compareValues(idx, key, clusterPtr->maxValue, res);
		if (res <= 0)
			break;
		curCluster++;
	}
	if (curCluster == CPI_SBK(idx)->numClusters)
		return(CPI_ERR_NOT_FOUND);


	/*
	** OK, which header in this cluster is the one we want ?
	** Use binary search.
	*/
	pivot = 0;
	min = 0;
	max = *clusterPtr->numHeaders - 1;
	curHeader = 0;
	hdrCachePtr = readPage(idx, CPI_CLS_PAGE(idx, curCluster));
	while(1)
	{
		if (max - min < 3)
			break;
		pivot = max - ((max - min) / 2);
		getHeader(idx, hdrCachePtr, curCluster, pivot,headerPtr);
		compareValues(idx, key, headerPtr->maxValue, res);
		if (res < 0)
		{
			max = pivot;
			continue;
		}
		if (res > 0)
		{
			min = pivot;
			continue;
		}
		max = min = pivot;
		break;
	}
	curHeader = min;
	while(curHeader <= max)
	{
		getHeader(idx, hdrCachePtr, curCluster, curHeader,headerPtr);
		compareValues(idx, key, headerPtr->maxValue, res);
		if (res <= 0)
		{
			break;
		}
		curHeader++;
	}
	
	if (curHeader == *clusterPtr->numHeaders)
		return(CPI_ERR_NOT_FOUND);

	/*
	** OK, found the right header.  Find the record we're looking for
	** using a binary search to trim the scan set
	*/
	nodeCachePtr = readPage(idx, *headerPtr->pageNum);
	pivot = 0;
	res = -1;
	min = 0;
	max = *headerPtr->numRecords - 1;
	while(1)
	{
		if (max - min < 3)
			break;
		pivot = max - ((max - min) / 2);
		getRecord(idx, nodeCachePtr, clusterPtr->clusterNum,
			headerPtr->headerNum, pivot, nodePtr);
		compareValues(idx, nodePtr->key, key, res);
		if (res == 0)
			break;
		if (res < 0)
			min = pivot;
		if (res > 0)
			max = pivot;
	}

	if (res == 0)
	{
		curRecord = pivot;
	}
	else
	{
		curRecord = min;
		while (curRecord <= max)
		{
			getRecord(idx, nodeCachePtr, clusterPtr->clusterNum,
				headerPtr->headerNum, curRecord, nodePtr);
			compareValues(idx, nodePtr->key, key, res);
			if (res >= 0)
				break;
			curRecord++;
		}
		if (curRecord == *headerPtr->numRecords)
			return(CPI_ERR_NOT_FOUND);

		if (res > 0  &&  flags == CPI_EXACT)
			return(CPI_ERR_NOT_FOUND);
	}
	while(1)
	{
		curRecord--;
		if (curRecord < 0)
			break;
		getRecord(idx, nodeCachePtr, clusterPtr->clusterNum,
			headerPtr->headerNum, curRecord, nodePtr);
		compareValues(idx, nodePtr->key, key, res);
		if (res != 0)
			break;
	}
	curRecord++;
	getRecord(idx, nodeCachePtr, clusterPtr->clusterNum,
		headerPtr->headerNum, curRecord, nodePtr);
		

	nodePtr->clusterNum = idx->clusterNum = clusterPtr->clusterNum;
	nodePtr->headerNum = idx->headerNum = headerPtr->headerNum;
	nodePtr->recordNum = idx->recordNum =  curRecord;
	
	return(0);
}




int cpiLookup(idx, key, nodePtr, flags)
	cpi	*idx;
	char	*key;
	cpi_nod	*nodePtr;
	int	flags;
{
	apiInit();
	return(privateLookup(idx, key, NULL, NULL, nodePtr, flags));
}



void cpiSetCursor(idx, cursor)
	cpi	*idx;
	cpi_cur	*cursor;
{
	cursor->clusterNum = idx->clusterNum;
	cursor->headerNum = idx->headerNum;
	cursor->recordNum = idx->recordNum;
}





int cpiGetNext(idx, cursor, node)
	cpi	*idx;
	cpi_cur	*cursor;
	cpi_nod	*node;
{
	cpi_hdr	headerBuf;
	cpi_cls	clusterBuf;
	cpi_ch	*cachePtr,
		*nodeCachePtr;
	int	curCluster,
		curHeader,
		curRecord;


	apiInit();
	curCluster = cursor->clusterNum;
	curHeader = cursor->headerNum;
	curRecord = cursor->recordNum;

	curRecord++;
	cachePtr = readPage(idx, CPI_CLS_PAGE(idx, curCluster));
	getHeader(idx, cachePtr, curCluster, curHeader, &headerBuf);
	if (curRecord >= *headerBuf.numRecords)
	{
		curRecord = 0;
		curHeader++;
		getCluster(idx, cachePtr, curCluster, &clusterBuf);
		if (curHeader >= *clusterBuf.numHeaders)
		{
			curHeader = 0;
			curCluster++;
			if (curCluster >= CPI_SBK(idx)->numClusters)
				return(-1);
			cachePtr = readPage(idx, CPI_CLS_PAGE(idx, curCluster));
		}
		getHeader(idx, cachePtr, curCluster, curHeader, &headerBuf);
	}
	nodeCachePtr = readPage(idx, *headerBuf.pageNum);
	getRecord(idx, nodeCachePtr, curCluster, curHeader, curRecord, node);
	idx->clusterNum =  cursor->clusterNum = curCluster;
	idx->headerNum =  cursor->headerNum = curHeader;
	idx->recordNum =  cursor->recordNum = curRecord;
	return(0);
}





int cpiGetPrev(idx, cursor, node)
	cpi	*idx;
	cpi_cur	*cursor;
	cpi_nod	*node;
{
	cpi_hdr	headerBuf;
	cpi_cls	clusterBuf;
	cpi_ch	*cachePtr = NULL,
		*nodeCachePtr;
	int	curCluster,
		curHeader,
		curRecord;


	apiInit();
	curCluster = cursor->clusterNum;
	curHeader = cursor->headerNum;
	curRecord = cursor->recordNum;

	curRecord--;
	if (curRecord < 0)
	{
		curHeader--;
		if (curHeader < 0)
		{
			curCluster--;
			if (curCluster < 0)
				return(-1);
			cachePtr = readPage(idx, CPI_CLS_PAGE(idx,curCluster));
			getCluster(idx, cachePtr, curCluster, &clusterBuf);
			curHeader = *clusterBuf.numHeaders - 1;
		}
		if (!cachePtr)
			cachePtr = readPage(idx, CPI_CLS_PAGE(idx,curCluster));
		getHeader(idx, cachePtr, curCluster,curHeader,&headerBuf);
		curRecord = *headerBuf.numRecords - 1;
	}
	if (!cachePtr)
	{
		cachePtr = readPage(idx, CPI_CLS_PAGE(idx,curCluster));
		getHeader(idx, cachePtr, curCluster,curHeader,&headerBuf);
	}
	nodeCachePtr = readPage(idx, *headerBuf.pageNum);
	getRecord(idx, nodeCachePtr, curCluster, curHeader, curRecord, node);
	idx->clusterNum =  cursor->clusterNum = curCluster;
	idx->headerNum =  cursor->headerNum = curHeader;
	idx->recordNum =  cursor->recordNum = curRecord;
	return(0);
}



int cpiGetFirst(idx, node)
	cpi	*idx;
	cpi_nod	*node;
{
	cpi_ch	*cachePtr;

	apiInit();
	cachePtr = readPage(idx, 2); /* sbk id page 0, cluster is page 1 */
	getRecord(idx, cachePtr, 0, 0, 0, node);
	idx->clusterNum = 0;
	idx->headerNum = 0;
	idx->recordNum = 0;
	return(0);
}



int cpiGetLast(idx, nodePtr)
	cpi	*idx;
	cpi_nod	*nodePtr;
{
	cpi_cls	clusterBuf;
	cpi_ch	*cachePtr,
		*nodeCachePtr;
	cpi_hdr	headerBuf;
	int	curCluster,
		curHeader,
		curRecord;

	apiInit();
	curCluster = CPI_SBK(idx)->numClusters - 1;
	cachePtr = readPage(idx,CPI_CLS_PAGE(idx,curCluster));
	getCluster(idx, cachePtr, curCluster, &clusterBuf);
	curHeader = *clusterBuf.numHeaders - 1;
	getHeader(idx, cachePtr, curCluster, curHeader, &headerBuf);

	nodeCachePtr = readPage(idx, *headerBuf.pageNum);
	curRecord = *headerBuf.numRecords - 1;
	getRecord(idx, nodeCachePtr, curCluster, curHeader, curRecord, nodePtr);
	idx->clusterNum = curCluster;
	idx->headerNum = curHeader;
	idx->recordNum = curRecord;
	return(0);
}



int cpiExists(idx, key, data)
	cpi	*idx;
	char	*key;
	u_int	data;
{
	int	res = 0,
		found;
	cpi_nod	nodeBuf;
	cpi_cur	cursor;

	/*
	** Scan the index for an item with matching key AND data values
	*/
	if (cpiLookup(idx, key, &nodeBuf, CPI_EXACT) < 0)
		return(-1);
	cpiSetCursor(idx, &cursor);
	found = 0;
	compareValues(idx, key, nodeBuf.key, res);
	while(res == 0)
	{
		if (nodeBuf.data == data)
		{
			found = 1;
			break;
		}
		if (cpiGetNext(idx, &cursor, &nodeBuf) < 0)
			return(-1);
		compareValues(idx, key, nodeBuf.key, res);
	}
	if (!found)
		return(-1);
	return(0);
}

int cpiDelete(idx, key, data)
	cpi	*idx;
	char	*key;
	u_int	data;
{
	int	res= 0,
		found;
	cpi_ch	*cachePtr;
	cpi_hdr	headerBuf;
	cpi_cls	clusterBuf;
	cpi_nod	nodeBuf;
	cpi_cur	cursor;

	/*
	** Scan the index for an item with matching key AND data values
	*/
	if (cpiLookup(idx, key, &nodeBuf, CPI_EXACT) < 0)
		return(-1);
	cpiSetCursor(idx, &cursor);
	found = 0;
	compareValues(idx, key, nodeBuf.key, res);
	while(res == 0)
	{
		if (nodeBuf.data == data)
		{
			found = 1;
			break;
		}
		if (cpiGetNext(idx, &cursor, &nodeBuf) < 0)
			return(-1);
		compareValues(idx, key, nodeBuf.key, res);
	}
	if (!found)
		return(-1);
	
	/*
	** OK, found it.  Now blow it away
	*/
	cachePtr = readPage(idx, CPI_CLS_PAGE(idx, nodeBuf.clusterNum));
	getCluster(idx, cachePtr, nodeBuf.clusterNum, &clusterBuf);
	getHeader(idx, cachePtr, nodeBuf.clusterNum, nodeBuf.headerNum, 
		&headerBuf);
	shiftDataPage(idx,&clusterBuf,&headerBuf,nodeBuf.recordNum,
		CPI_SHIFT_DOWN);
	(*headerBuf.numRecords) -= 1;
	if (*headerBuf.numRecords == 0)
	{
		shiftHeaderPage(idx, nodeBuf.clusterNum, nodeBuf.headerNum,
			CPI_SHIFT_DOWN);
	}
	resetMaxValue(idx, nodeBuf.clusterNum, nodeBuf.headerNum);
	if (cpiVerbose)
		cpiDumpIndex(idx);
	return(0);
}