1698 lines
41 KiB
C++
1698 lines
41 KiB
C++
/*****************************************************************************
|
|
* *
|
|
* BTREE.C *
|
|
* *
|
|
* Copyright (C) Microsoft Corporation 1989-1994. *
|
|
* All Rights reserved. *
|
|
* *
|
|
******************************************************************************
|
|
* *
|
|
* Module Intent *
|
|
* *
|
|
* Btree manager general functions: open, close, etc. *
|
|
* *
|
|
*****************************************************************************/
|
|
|
|
#include "stdafx.h"
|
|
|
|
#include "btpriv.h"
|
|
|
|
#ifdef _DEBUG
|
|
#undef THIS_FILE
|
|
static char THIS_FILE[] = __FILE__;
|
|
#endif
|
|
|
|
__inline static RC_TYPE STDCALL RcSplitLeaf(PCACHE pcacheOld, PCACHE pcacheNew, QBTHR qbthr);
|
|
__inline static void STDCALL SplitInternal(PCACHE pcacheOld, PCACHE pcacheNew, QBTHR qbthr, int* qi);
|
|
__inline static QMAPBT STDCALL HmapbtCreateHbt(QBTHR qbthr);
|
|
static RC_TYPE STDCALL RcInsertInternal(BK bk, KEY key, int wLevel, QBTHR qbthr);
|
|
static BOOL STDCALL InitQbthr(char chType, QBTHR qbthr);
|
|
static BOOL FASTCALL KtToLcid(KT kt);
|
|
static int STDCALL WCmpSz(LPCSTR sz1, LPCSTR sz2);
|
|
|
|
/*
|
|
* Global btree error code. This contains the error status for the most
|
|
* recent btree function call. This error code is shared for all btrees,
|
|
* and, if the DLL version is used, it's shared for all instances (this is
|
|
* probably a bug.)
|
|
*/
|
|
|
|
RC_TYPE rcBtreeError = RC_Success;
|
|
|
|
typedef int (STDCALL *STRCMP)(const char *, const char *);
|
|
STRCMP pstrcmp;
|
|
|
|
/***************************************************************************
|
|
|
|
FUNCTION: RcMakeCache
|
|
|
|
PURPOSE: Allocate a btree cache with one block per level
|
|
|
|
PARAMETERS:
|
|
qbthr
|
|
|
|
RETURNS:
|
|
|
|
COMMENTS:
|
|
|
|
MODIFICATION DATES:
|
|
29-Apr-1994 [ralphw]
|
|
|
|
***************************************************************************/
|
|
|
|
void STDCALL RcMakeCache(QBTHR qbthr)
|
|
{
|
|
ASSERT(qbthr->bth.cLevels > 0);
|
|
if (qbthr->bth.cLevels > 0) { // would it work to just alloc 0 bytes???
|
|
qbthr->pCache =
|
|
(PBYTE) lcCalloc(qbthr->bth.cLevels * CbCacheBlock(qbthr));
|
|
}
|
|
ConfirmOrDie(qbthr->pCache);
|
|
}
|
|
|
|
/***************************************************************************\
|
|
*
|
|
- Function: RcGetBtreeError()
|
|
-
|
|
* Purpose: Return the current global btree error status.
|
|
*
|
|
* ASSUMES
|
|
* globals IN: rcBtreeError
|
|
*
|
|
* PROMISES
|
|
* returns: current btree error status RC
|
|
*
|
|
* Bugs: A single RC_TYPE is kept for all btrees. If the DLL is used,
|
|
* it's shared between all instances.
|
|
*
|
|
\***************************************************************************/
|
|
|
|
RC_TYPE STDCALL RcGetBtreeError(void)
|
|
{
|
|
return rcBtreeError;
|
|
}
|
|
|
|
/***************************************************************************\
|
|
*
|
|
- Function: HbtCreateBtreeSz( psz, qbtp )
|
|
-
|
|
* Purpose: Create and open a btree.
|
|
*
|
|
* ASSUMES
|
|
* args IN: psz - name of the btree
|
|
* qbtp - pointer to btree params: NO default because we
|
|
* need an HFS.
|
|
* .bFlags - FS_IS_DIRECTORY to create an FS directory
|
|
* PROMISES
|
|
* returns: handle to the new btree
|
|
* globals OUT: rcBtreeError
|
|
*
|
|
* Note: KT supported: KT_SZ, KT_LONG, KT_SZI, KT_SZISCAND.
|
|
* +++
|
|
*
|
|
* Method: Btrees are files inside a FS. The FS directory is a
|
|
* special file in the FS.
|
|
*
|
|
* Note: FS_IS_DIRECTORY flag set in qbthr->bth.bFlags if indicated
|
|
*
|
|
\***************************************************************************/
|
|
|
|
const char txtBtreeFormatDefault[] = "z4";
|
|
|
|
QBTHR STDCALL HbtCreateBtreeSz(PCSTR pszTreeName, BTREE_PARAMS* pbtp)
|
|
{
|
|
HF hf;
|
|
|
|
// see if we support key type
|
|
|
|
// REVIEW: 09-May-1994 [ralphw] Should we make this a debug-only check?
|
|
|
|
if (pbtp == NULL ||
|
|
( pbtp->rgchFormat[0] != KT_SZ &&
|
|
pbtp->rgchFormat[0] != KT_LONG &&
|
|
pbtp->rgchFormat[0] != KT_SZI &&
|
|
pbtp->rgchFormat[0] != KT_SZISCAND &&
|
|
pbtp->rgchFormat[0] != KT_SZIJAPAN &&
|
|
pbtp->rgchFormat[0] != KT_SZIKOREA &&
|
|
pbtp->rgchFormat[0] != KT_SZITAIWAN &&
|
|
pbtp->rgchFormat[0] != KT_SZICZECH &&
|
|
pbtp->rgchFormat[0] != KT_SZIPOLISH &&
|
|
pbtp->rgchFormat[0] != KT_SZIHUNGAR &&
|
|
pbtp->rgchFormat[0] != KT_SZIRUSSIAN &&
|
|
pbtp->rgchFormat[0] != KT_NLSI &&
|
|
pbtp->rgchFormat[0] != KT_NLS
|
|
|
|
))
|
|
{
|
|
rcBtreeError = RC_BadArg;
|
|
return NULL;
|
|
}
|
|
|
|
// allocate btree handle struct, must zero-init the memory
|
|
|
|
QBTHR qbthr = (QBTHR) lcCalloc(sizeof(BTH_RAM));
|
|
|
|
// initialize bthr struct
|
|
|
|
pbtp->rgchFormat[MAXFORMAT] = '\0'; // REVIEW: 10-Jan-1994 [ralphw] why?
|
|
strcpy(qbthr->bth.rgchFormat,
|
|
pbtp->rgchFormat[0] == '\0'
|
|
? (PSTR) txtBtreeFormatDefault : pbtp->rgchFormat);
|
|
|
|
if (!InitQbthr(pbtp->rgchFormat[0], qbthr)) {
|
|
rcBtreeError = RC_BadArg;
|
|
lcFree(qbthr);
|
|
return NULL;
|
|
}
|
|
|
|
// create the btree file
|
|
|
|
hf = HfCreateFileHfs(pbtp->hfs, pszTreeName, pbtp->bFlags);
|
|
|
|
qbthr->bth.wMagic = WBTREEMAGIC;
|
|
qbthr->bth.bVersion = BBTREEVERSION;
|
|
|
|
qbthr->bth.bFlags = pbtp->bFlags | FS_DIRTY;
|
|
qbthr->bth.cbBlock = pbtp->cbBlock ? pbtp->cbBlock : CBBTREEBLOCKDEFAULT;
|
|
|
|
qbthr->bth.bkFirst =
|
|
qbthr->bth.bkLast =
|
|
qbthr->bth.bkRoot =
|
|
qbthr->bth.bkFree = bkNil;
|
|
|
|
qbthr->hf = hf;
|
|
|
|
LcbWriteHf(qbthr->hf, &(qbthr->bth), sizeof(BTH)); // why???
|
|
|
|
rcBtreeError = RC_Success;
|
|
return qbthr;
|
|
}
|
|
|
|
/***************************************************************************\
|
|
*
|
|
- Function: RcCloseOrFlushHbt( qbthr, fClose )
|
|
-
|
|
* Purpose: Close or flush the btree. Flush only works for directory
|
|
* btree. (Is this true? If so, why?)
|
|
*
|
|
* ASSUMES
|
|
* args IN: qbthr
|
|
* fClose - TRUE to close the btree, FALSE to flush it
|
|
*
|
|
* PROMISES
|
|
* returns: rc
|
|
* args OUT: qbthr - the btree is still open and cache still exists
|
|
*
|
|
* NOTE: This function gets called by RcCloseOrFlushHfs() even if
|
|
* there was an error (just to clean up memory.)
|
|
*
|
|
\***************************************************************************/
|
|
|
|
RC_TYPE STDCALL RcCloseOrFlushHbt(QBTHR qbthr, BOOL fClose)
|
|
{
|
|
rcBtreeError = RC_Success;
|
|
HF hf = qbthr->hf;
|
|
|
|
// Confirm that qbthr->pCache is valid
|
|
|
|
ASSERT(qbthr->pCache)
|
|
|
|
if (qbthr->bth.bFlags & FS_DIRTY) {
|
|
ASSERT(!(qbthr->bth.bFlags & (FS_READ_ONLY | FS_OPEN_READ_ONLY)));
|
|
|
|
if (qbthr->pCache && RcFlushCache(qbthr) != RC_Success)
|
|
goto error_return;
|
|
|
|
qbthr->bth.bFlags &= ~(FS_DIRTY);
|
|
Ensure(LSeekHf(hf, 0, SEEK_SET), 0);
|
|
LcbWriteHf(hf, &(qbthr->bth), sizeof(BTH));
|
|
}
|
|
|
|
error_return:
|
|
|
|
if (RcCloseOrFlushHf(hf, fClose,
|
|
qbthr->bth.bFlags & FS_CDROM ? sizeof(BTH) : 0)
|
|
!= RC_Success && RC_Success == rcBtreeError)
|
|
rcBtreeError = rcFSError;
|
|
|
|
if (fClose) {
|
|
if (qbthr->pCache)
|
|
lcFree(qbthr->pCache);
|
|
lcFree(qbthr);
|
|
}
|
|
|
|
return rcBtreeError;
|
|
}
|
|
|
|
/***************************************************************************\
|
|
*
|
|
- Function: RcAbandonHbt( qbthr )
|
|
-
|
|
* Purpose: Abandon an open btree. All changes since btree was opened
|
|
* will be lost. If btree was opened with a create, it is
|
|
* as if the create never happened.
|
|
*
|
|
* ASSUMES
|
|
* args IN: qbthr
|
|
*
|
|
* PROMISES
|
|
* returns: rc
|
|
* globals OUT: rcBtreeError
|
|
* +++
|
|
*
|
|
* Method: Just abandon the file and free memory.
|
|
*
|
|
\***************************************************************************/
|
|
|
|
RC_TYPE STDCALL RcAbandonHbt(QBTHR qbthr)
|
|
{
|
|
if (qbthr->pCache)
|
|
lcFree(qbthr->pCache);
|
|
|
|
rcBtreeError = RcAbandonHf(qbthr->hf);
|
|
|
|
lcFree(qbthr);
|
|
|
|
return rcBtreeError;
|
|
}
|
|
|
|
/***************************************************************************\
|
|
*
|
|
- Function: HmapbtCreateHbt(qbthr)
|
|
-
|
|
* Purpose: Create a HMAPBT index struct of a btree.
|
|
*
|
|
* ASSUMES
|
|
* args IN: qbthr - the btree to map
|
|
*
|
|
* PROMISES
|
|
* returns: the map struct
|
|
* +++
|
|
*
|
|
* Method: Traverse leaf nodes of the btree. Store BK and running
|
|
* total count of previous keys in the map array.
|
|
*
|
|
\***************************************************************************/
|
|
|
|
__inline static QMAPBT STDCALL HmapbtCreateHbt(QBTHR qbthr)
|
|
{
|
|
BK bk;
|
|
int wLevel, cBk;
|
|
QMAPBT qb;
|
|
|
|
ASSERT(qbthr);
|
|
|
|
// If the btree exists but is empty, return an empty map
|
|
|
|
if ((wLevel = qbthr->bth.cLevels) == 0) {
|
|
qb = (QMAPBT) lcCalloc(LcbFromBk(0));
|
|
qb->cTotalBk = 0;
|
|
return qb;
|
|
}
|
|
--wLevel;
|
|
|
|
if (!qbthr->pCache)
|
|
RcMakeCache(qbthr);
|
|
|
|
qb = (QMAPBT) lcCalloc(LcbFromBk(qbthr->bth.bkEOF));
|
|
|
|
QMAPREC qbT = qb->table;
|
|
cBk = 0;
|
|
int cKeys = 0;
|
|
|
|
PCACHE pcache;
|
|
for (bk = qbthr->bth.bkFirst;; bk = BkNext(pcache)) {
|
|
if (bk == bkNil)
|
|
break;
|
|
|
|
if ((pcache = QFromBk(bk, wLevel, qbthr)) == NULL) {
|
|
lcFree(qb);
|
|
goto error_return;
|
|
}
|
|
|
|
cBk++;
|
|
qbT->cPreviousKeys = cKeys;
|
|
qbT->bk = bk;
|
|
qbT++;
|
|
cKeys += pcache->db.cKeys;
|
|
}
|
|
|
|
qb->cTotalBk = cBk;
|
|
|
|
return (QMAPBT) lcReAlloc(qb, LcbFromBk(cBk));
|
|
|
|
error_return:
|
|
|
|
rcBtreeError = RC_Failure;
|
|
return NULL;
|
|
}
|
|
|
|
/*--------------------------------------------------------------------------*
|
|
| Public functions |
|
|
*--------------------------------------------------------------------------*/
|
|
|
|
|
|
/***************************************************************************\
|
|
*
|
|
- Function: RcCreateBTMapHfs( hfs, qbthr, szName )
|
|
-
|
|
* Purpose: Create and store a btmap index of the btree qbthr, putting
|
|
* it into a file called szName in the file system hfs.
|
|
*
|
|
* ASSUMES
|
|
* args IN: hfs - file system where lies the btree
|
|
* qbthr - handle of btree to map
|
|
* szName - name of file to store map file in
|
|
*
|
|
* PROMISES
|
|
* returns: rc
|
|
* args OUT: hfs - map file is stored in this file system
|
|
*
|
|
\***************************************************************************/
|
|
|
|
RC_TYPE STDCALL RcCreateBTMapHfs(HFS hfs, QBTHR qbthr, PSTR szName)
|
|
{
|
|
HF hf;
|
|
QMAPBT qmapbt;
|
|
int lcb;
|
|
|
|
if (!hfs || !qbthr)
|
|
return rcBtreeError = RC_BadHandle;
|
|
if (!(qmapbt = HmapbtCreateHbt(qbthr)))
|
|
return rcBtreeError = RC_Failure;
|
|
|
|
hf = HfCreateFileHfs(hfs, szName, FS_OPEN_READ_WRITE);
|
|
|
|
lcb = LcbFromBk(qmapbt->cTotalBk);
|
|
LSeekHf(hf, 0, SEEK_SET);
|
|
LcbWriteHf(hf, (void*) qmapbt, lcb);
|
|
|
|
if (RcCloseHf(hf) != RC_Success) {
|
|
RcUnlinkFileHfs(hfs, szName);
|
|
goto error_return;
|
|
}
|
|
lcFree(qmapbt);
|
|
return rcBtreeError = RC_Success;
|
|
|
|
error_return:
|
|
if (qmapbt)
|
|
lcFree(qmapbt);
|
|
return rcBtreeError = RC_Failure;
|
|
}
|
|
|
|
/***************************************************************************\
|
|
*
|
|
- Function: BkScanLInternal( bk, key, wLevel, qbthr )
|
|
-
|
|
* Purpose: Scan an internal node for a int key and return child BK.
|
|
*
|
|
* ASSUMES
|
|
* args IN: bk - BK of internal node to scan
|
|
* key - key to search for
|
|
* wLevel - level of btree bk lives on
|
|
* qbthr - btree header containing cache, and btree specs
|
|
*
|
|
* PROMISES
|
|
* returns: bk of subtree that might contain key; bkNil on error
|
|
* args OUT: qbthr->pCache - bk's block will be cached
|
|
*
|
|
* Side Effects: bk's block will be cached
|
|
* +++
|
|
*
|
|
* Method: Should use binary search. Doesn't, yet.
|
|
*
|
|
\***************************************************************************/
|
|
|
|
BK STDCALL BkScanLInternal(BK bk, KEY key, int wLevel, QBTHR qbthr,
|
|
int* piKey)
|
|
{
|
|
PCACHE pcache;
|
|
PBYTE q;
|
|
LONG cKeys;
|
|
|
|
if ((pcache = QFromBk(bk, wLevel, qbthr)) == (PCACHE) NULL)
|
|
return bkNil;
|
|
q = pcache->db.rgbBlock;
|
|
cKeys = pcache->db.cKeys;
|
|
bk = *(BK *) q;
|
|
q += sizeof(BK);
|
|
|
|
while (cKeys-- > 0) {
|
|
if (*(LONG *) key >= *(int *) q) {
|
|
q += sizeof(LONG);
|
|
bk = *(BK *) q;
|
|
q += sizeof(BK);
|
|
}
|
|
else
|
|
break;
|
|
}
|
|
|
|
if (piKey)
|
|
*piKey = q - (PBYTE) pcache->db.rgbBlock;
|
|
|
|
return bk;
|
|
}
|
|
|
|
/***************************************************************************\
|
|
*
|
|
- Function: RcScanLLeaf( bk, key, wLevel, qbthr, qRec, qBtpos )
|
|
-
|
|
* Purpose: Scan a leaf node for a key and copy the associated data.
|
|
*
|
|
* ASSUMES
|
|
* args IN: bk - the leaf block
|
|
* key - the key we're looking for
|
|
* wLevel - the level of leaves (unnecessary)
|
|
* qbthr - the btree header
|
|
*
|
|
* PROMISES
|
|
* returns: RC_Success if found; RC_NoExists if not found
|
|
* args OUT: qRec - if found, record gets copied into this buffer
|
|
* qbtpos - pos of first key >= key goes here
|
|
*
|
|
* Notes: If we are scanning for a key greater than any key in this
|
|
* block, the pos returned will be invalid and will point just
|
|
* past the last valid key in this block.
|
|
* +++
|
|
*
|
|
* Method: Should use binary search if fixed record size. Doesn't, yet.
|
|
*
|
|
\***************************************************************************/
|
|
|
|
RC_TYPE STDCALL RcScanLLeaf(BK bk, KEY key, int wLevel, QBTHR qbthr, void* qRec,
|
|
QBTPOS qbtpos)
|
|
{
|
|
PCACHE pcache;
|
|
PBYTE qb;
|
|
int cKey;
|
|
|
|
if (!(pcache = QFromBk(bk, wLevel, qbthr)))
|
|
return rcBtreeError;
|
|
|
|
rcBtreeError = RC_NoExists;
|
|
|
|
qb = pcache->db.rgbBlock + 2 * sizeof(BK);
|
|
|
|
if (qbthr->cbRecordSize) {
|
|
for (cKey = 0; cKey < pcache->db.cKeys; cKey++) {
|
|
if (*(LONG *) key > *(LONG *) qb) // still looking for key
|
|
qb += sizeof(LONG) + qbthr->cbRecordSize;
|
|
else if (*(LONG *) key < *(LONG *) qb) // key not found
|
|
break;
|
|
else { // matched the key
|
|
if (qRec != NULL) {
|
|
memmove(qRec, qb + sizeof(LONG), qbthr->cbRecordSize);
|
|
}
|
|
|
|
rcBtreeError = RC_Success;
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
else {
|
|
for (cKey = 0; cKey < pcache->db.cKeys; cKey++) {
|
|
if (*(LONG *) key > *(LONG *) qb) { // still looking for key
|
|
qb += sizeof(LONG);
|
|
qb += CbSizeRec(qb, qbthr);
|
|
}
|
|
else if (*(LONG *) key < *(LONG *) qb) { // key not found
|
|
break;
|
|
}
|
|
else { // matched the key
|
|
if (qRec != NULL) {
|
|
memmove(qRec,
|
|
qb + sizeof(LONG),
|
|
(LONG) CbSizeRec(qb + sizeof(LONG), qbthr));
|
|
}
|
|
|
|
rcBtreeError = RC_Success;
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
if (qbtpos != (QBTPOS) NULL) {
|
|
qbtpos->bk = bk;
|
|
qbtpos->iKey = qb - (PBYTE) pcache->db.rgbBlock;
|
|
qbtpos->cKey = cKey;
|
|
}
|
|
|
|
return rcBtreeError;
|
|
}
|
|
|
|
/***************************************************************************\
|
|
*
|
|
- Function: BkScanSziInternal( bk, key, wLevel, qbthr )
|
|
-
|
|
* Purpose: Scan an internal node for a key and return child BK.
|
|
*
|
|
* ASSUMES
|
|
* args IN: bk - BK of internal node to scan
|
|
* key - key to search for
|
|
* wLevel - level of btree bk lives on
|
|
* qbthr - btree header containing cache, and btree specs
|
|
* piKey - address of an int or NULL to not get it
|
|
*
|
|
* PROMISES
|
|
* returns: bk of subtree that might contain key; bkNil on error
|
|
* args OUT: qbthr->pCache - bk's block will be cached
|
|
* piKey - index into rgbBlock of first key >= key
|
|
*
|
|
* Side Effects: bk's block will be cached
|
|
*
|
|
\***************************************************************************/
|
|
|
|
BK STDCALL BkScanSziInternal(BK bk, KEY key, int wLevel, QBTHR qbthr, int* piKey)
|
|
{
|
|
PCACHE pcache;
|
|
|
|
if ((pcache = QFromBk(bk, wLevel, qbthr)) == NULL)
|
|
return bkNil;
|
|
PBYTE pb = pcache->db.rgbBlock;
|
|
int cKeys = pcache->db.cKeys;
|
|
|
|
bk = *(BK *) pb;
|
|
pb += sizeof(BK);
|
|
|
|
while (cKeys-- > 0) {
|
|
if (WCmpiSz((PSTR) key, (PSTR) pb) >= 0) {
|
|
pb += strlen((PSTR) pb) + 1;
|
|
bk = *(BK *) pb;
|
|
pb += sizeof(BK);
|
|
}
|
|
else
|
|
break;
|
|
}
|
|
|
|
if (piKey != NULL)
|
|
*piKey = pb - (PBYTE) pcache->db.rgbBlock;
|
|
|
|
return bk;
|
|
}
|
|
|
|
/***************************************************************************\
|
|
*
|
|
- Function: BkScanSziScandInternal( bk, key, wLevel, qbthr )
|
|
-
|
|
* Purpose: Scan an internal node for a key and return child BK.
|
|
*
|
|
* ASSUMES
|
|
* args IN: bk - BK of internal node to scan
|
|
* key - key to search for
|
|
* wLevel - level of btree bk lives on
|
|
* qbthr - btree header containing cache, and btree specs
|
|
* piKey - address of an int or NULL to not get it
|
|
*
|
|
* PROMISES
|
|
* returns: bk of subtree that might contain key; bkNil on error
|
|
* args OUT: qbthr->pCache - bk's block will be cached
|
|
* piKey - index into rgbBlock of first key >= key
|
|
*
|
|
* Side Effects: bk's block will be cached
|
|
*
|
|
\***************************************************************************/
|
|
|
|
BK STDCALL BkScanSziScandInternal(BK bk, KEY key, int wLevel, QBTHR qbthr, int* piKey)
|
|
{
|
|
PCACHE pcache;
|
|
PBYTE q;
|
|
int cKeys;
|
|
|
|
if ((pcache = QFromBk(bk, wLevel, qbthr)) == NULL)
|
|
return bkNil;
|
|
q = pcache->db.rgbBlock;
|
|
cKeys = pcache->db.cKeys;
|
|
|
|
bk = *(BK *) q;
|
|
q += sizeof(BK);
|
|
|
|
while (cKeys-- > 0) {
|
|
if (WCmpiScandSz((PSTR) key, (PSTR) q) >= 0) {
|
|
q += strlen((PSTR) q) + 1;
|
|
bk = *(BK *) q;
|
|
q += sizeof(BK);
|
|
}
|
|
else
|
|
break;
|
|
}
|
|
|
|
if (piKey != NULL)
|
|
*piKey = q - (PBYTE) pcache->db.rgbBlock;
|
|
|
|
return bk;
|
|
}
|
|
|
|
/***************************************************************************\
|
|
*
|
|
- Function: RcScanSziScandLeaf( bk, key, wLevel, qbthr, qRec, qbtpos )
|
|
-
|
|
* Purpose: Scan a leaf node for a key and copy the associated data.
|
|
*
|
|
* ASSUMES
|
|
* args IN: bk - the leaf block
|
|
* key - the key we're looking for
|
|
* wLevel - the level of leaves (unnecessary)
|
|
* qbthr - the btree header
|
|
*
|
|
* PROMISES
|
|
* returns: RC_Success if found; RC_NoExists if not found
|
|
* args OUT: qRec - if found, record gets copied into this buffer
|
|
* qbtpos - pos of first key >= key goes here
|
|
*
|
|
* Notes: If we are scanning for a key greater than any key in this
|
|
* block, the pos returned will be invalid and will point just
|
|
* past the last valid key in this block.
|
|
*
|
|
*
|
|
\***************************************************************************/
|
|
|
|
RC_TYPE STDCALL RcScanSziScandLeaf(BK bk, KEY key, int wLevel, QBTHR qbthr, void* qRec, QBTPOS qbtpos )
|
|
{
|
|
PCACHE pcache;
|
|
PSTR sz;
|
|
int w, cKey;
|
|
PBYTE qb;
|
|
|
|
|
|
if ((pcache = QFromBk(bk, wLevel, qbthr)) == NULL)
|
|
return rcBtreeError;
|
|
|
|
rcBtreeError = RC_NoExists;
|
|
|
|
sz = (PSTR) pcache->db.rgbBlock + 2 * sizeof(BK);
|
|
|
|
for (cKey = 0; cKey < pcache->db.cKeys; cKey++) {
|
|
w = WCmpiScandSz((PSTR) key, sz);
|
|
|
|
if (w > 0) { // still looking for key
|
|
sz += strlen(sz) + 1;
|
|
sz += CbSizeRec(sz, qbthr);
|
|
}
|
|
else if (w < 0) // key not found
|
|
break;
|
|
else { // matched the key
|
|
if (qRec != NULL) {
|
|
qb = (PBYTE) sz + strlen(sz) + 1;
|
|
memmove(qRec, qb, (int) CbSizeRec(qb, qbthr));
|
|
}
|
|
|
|
rcBtreeError = RC_Success;
|
|
break;
|
|
}
|
|
}
|
|
|
|
if (qbtpos != NULL) {
|
|
qbtpos->bk = bk;
|
|
qbtpos->cKey = cKey;
|
|
qbtpos->iKey = (PBYTE) sz - (PBYTE) pcache->db.rgbBlock;
|
|
}
|
|
|
|
return rcBtreeError;
|
|
}
|
|
|
|
/***************************************************************************\
|
|
*
|
|
- Function: RcInsertHbt()
|
|
-
|
|
* Purpose: Insert a key and record into a btree
|
|
*
|
|
* ASSUMES
|
|
* args IN: qbthr - btree handle
|
|
* key - key to insert
|
|
* qvRec - record associated with key to insert
|
|
* state IN: cache unlocked
|
|
*
|
|
* PROMISES
|
|
* returns: RC_Success, RC_Exists (duplicate key)
|
|
* state OUT: cache unlocked, all ancestor blocks cached
|
|
*
|
|
* Notes: compressed keys unimplemented
|
|
*
|
|
\***************************************************************************/
|
|
|
|
RC_TYPE STDCALL RcInsertHbt(QBTHR qbthr, KEY key, void* qvRec)
|
|
{
|
|
int cbAdd, cbKey, cbRec;
|
|
PCACHE pcacheLeaf, pcacheNew;
|
|
KEY keyNew;
|
|
PBYTE qb;
|
|
BTPOS btpos;
|
|
|
|
#ifdef _DEBUG
|
|
PSTR lpszKey = (PSTR) key; // for Codeview
|
|
#endif
|
|
|
|
HF hf = qbthr->hf;
|
|
|
|
{
|
|
RC_TYPE rc = RcLookupByKeyAux(qbthr, key, &btpos, NULL, TRUE);
|
|
|
|
/*
|
|
* After lookup, all nodes on path from root to correct leaf are
|
|
* guaranteed to be cached, with iKey valid.
|
|
*/
|
|
|
|
if (rc != RC_NoExists) {
|
|
rcBtreeError = (rc == RC_Success ? RC_Exists : rc);
|
|
return rcBtreeError;
|
|
}
|
|
}
|
|
if (qbthr->bth.cLevels == 0) {
|
|
|
|
// need to build a valid root block
|
|
|
|
qbthr->pCache = (PBYTE) lcCalloc(CbCacheBlock(qbthr));
|
|
PCACHE pcache = (PCACHE) qbthr->pCache;
|
|
|
|
qbthr->bth.cLevels = 1;
|
|
pcache->bk = BkAlloc(qbthr);
|
|
qbthr->bth.bkFirst =
|
|
qbthr->bth.bkLast =
|
|
qbthr->bth.bkRoot = (BK) pcache->bk;
|
|
if (pcache->bk == bkNil)
|
|
goto error_cache_locked;
|
|
pcache->bFlags = CACHE_DIRTY | CACHE_VALID;
|
|
pcache->db.cbSlack = qbthr->bth.cbBlock - sizeof(DISK_BLOCK) + 1 -
|
|
2 * sizeof(BK);
|
|
pcache->db.cKeys = 0;
|
|
SetBkPrev(pcache, bkNil);
|
|
SetBkNext(pcache, bkNil);
|
|
btpos.iKey = 2 * sizeof(BK);
|
|
}
|
|
|
|
cbKey = CbSizeKey(key, qbthr, FALSE);
|
|
cbRec = qbthr->cbRecordSize ? qbthr->cbRecordSize :
|
|
CbSizeRec(qvRec, qbthr);
|
|
cbAdd = cbKey + cbRec;
|
|
|
|
// check to see if key and rec can fit harmoniously in a block
|
|
|
|
if (cbAdd > qbthr->bth.cbBlock / 2) {
|
|
rcBtreeError = RC_Failure;
|
|
goto error_cache_locked;
|
|
}
|
|
|
|
pcacheLeaf = QCacheBlock(qbthr, qbthr->bth.cLevels - 1);
|
|
|
|
if (cbAdd > pcacheLeaf->db.cbSlack) {
|
|
|
|
// new key and rec don't fit in leaf: split the block
|
|
// create new leaf block
|
|
|
|
pcacheNew = (PCACHE) lcCalloc(CbCacheBlock(qbthr));
|
|
|
|
if ((pcacheNew->bk = BkAlloc(qbthr)) == bkNil)
|
|
goto error_gh_locked;
|
|
|
|
if (RcSplitLeaf(pcacheLeaf, pcacheNew, qbthr) != RC_Success)
|
|
goto error_gh_locked;
|
|
|
|
keyNew = (KEY) pcacheNew->db.rgbBlock + 2 * sizeof(BK);
|
|
|
|
// insert new leaf into parent block
|
|
|
|
if (RcInsertInternal((BK) pcacheNew->bk, keyNew, qbthr->bth.cLevels - 1,
|
|
qbthr) != RC_Success)
|
|
goto error_gh_locked;
|
|
|
|
// InsertInternal can invalidate cache block pointers..
|
|
|
|
pcacheLeaf = QCacheBlock(qbthr, qbthr->bth.cLevels - 1);
|
|
|
|
// find out which leaf to put new key and rec in and cache it
|
|
|
|
if (WCmpKey(key, keyNew, (KT) qbthr->bth.rgchFormat[0]) >= 0) {
|
|
|
|
// key goes in new block. Write out old one and cache the new one
|
|
|
|
if (RcWriteBlock(pcacheLeaf, qbthr) != RC_Success)
|
|
goto error_gh_locked;
|
|
ASSERT(CbCacheBlock(qbthr) < UINT_MAX);
|
|
memmove(pcacheLeaf, pcacheNew, CbCacheBlock(qbthr));
|
|
|
|
// get pos
|
|
|
|
if (qbthr->RcScanLeaf((BK) pcacheLeaf->bk, key, qbthr->bth.cLevels - 1,
|
|
qbthr, NULL, &btpos) != RC_NoExists) {
|
|
if (rcBtreeError == RC_Success)
|
|
rcBtreeError = RC_Failure;
|
|
goto error_gh_locked;
|
|
}
|
|
}
|
|
else {
|
|
|
|
// key goes in old block. Write out the new one
|
|
|
|
if (RcWriteBlock(pcacheNew, qbthr) != RC_Success)
|
|
goto error_gh_locked;
|
|
}
|
|
|
|
lcFree(pcacheNew);
|
|
}
|
|
|
|
// insert new key and rec into the leaf block
|
|
|
|
ASSERT(btpos.iKey + cbAdd <= (INT) (qbthr->bth.cbBlock -
|
|
sizeof(DISK_BLOCK) + 1));
|
|
|
|
qb = (PBYTE) (pcacheLeaf->db.rgbBlock) + btpos.iKey;
|
|
|
|
memmove(qb + cbAdd, qb,
|
|
qbthr->bth.cbBlock - btpos.iKey -
|
|
pcacheLeaf->db.cbSlack - sizeof(DISK_BLOCK) + 1);
|
|
|
|
memmove(qb, (void*) key, cbKey);
|
|
memmove(qb + cbKey, qvRec, cbRec);
|
|
|
|
pcacheLeaf->db.cKeys++;
|
|
pcacheLeaf->db.cbSlack -= cbAdd;
|
|
pcacheLeaf->bFlags |= CACHE_DIRTY;
|
|
|
|
qbthr->bth.lcEntries++;
|
|
qbthr->bth.bFlags |= FS_DIRTY;
|
|
|
|
return rcBtreeError = RC_Success;
|
|
|
|
error_gh_locked:
|
|
lcFree(pcacheNew);
|
|
|
|
error_cache_locked:
|
|
lcClearFree(&qbthr->pCache);
|
|
|
|
return rcBtreeError;
|
|
}
|
|
|
|
/***************************************************************************\
|
|
*
|
|
- Function: RcUpdateHbt( qbthr, key, qvRec )
|
|
-
|
|
* Purpose: Update the record for an existing key. If the key wasn't
|
|
* there already, it will not be inserted.
|
|
*
|
|
* ASSUMES
|
|
* args IN: qbthr
|
|
* key - key that already exists in btree
|
|
* qvRec - new record
|
|
*
|
|
* PROMISES
|
|
* returns: RC_Success; RC_NoExists
|
|
* args OUT: qbthr - if key was in btree, it now has a new record.
|
|
* +++
|
|
*
|
|
* Method: If the records are the same size, copy the new over
|
|
* the old.
|
|
* Otherwise, delete the old key/rec and insert the new.
|
|
*
|
|
\***************************************************************************/
|
|
|
|
RC_TYPE STDCALL RcUpdateHbt(QBTHR qbthr, KEY key, void* qvRec)
|
|
{
|
|
PBYTE qb;
|
|
PCACHE pcache;
|
|
BTPOS btpos;
|
|
|
|
RC_TYPE rc = (RC_TYPE) RcLookupByKey(qbthr, key, &btpos, NULL);
|
|
|
|
if (rc != RC_Success)
|
|
return rcBtreeError = rc;
|
|
|
|
ASSERT(qbthr->bth.cLevels > 0);
|
|
|
|
pcache = QCacheBlock(qbthr, qbthr->bth.cLevels - 1);
|
|
qb = pcache->db.rgbBlock + btpos.iKey;
|
|
|
|
qb += CbSizeKey((KEY) qb, qbthr, FALSE);
|
|
|
|
if (CbSizeRec(qvRec, qbthr) != CbSizeRec(qb, qbthr)) {
|
|
|
|
// Someday do something clever, but for now, just:
|
|
|
|
rc = RcDeleteHbt(qbthr, key);
|
|
|
|
if (rc == RC_Success)
|
|
rc = RcInsertHbt(qbthr, key, qvRec);
|
|
}
|
|
else {
|
|
memmove(qb, qvRec, (int) CbSizeRec(qvRec, qbthr));
|
|
|
|
pcache->bFlags |= CACHE_DIRTY;
|
|
qbthr->bth.bFlags |= FS_DIRTY;
|
|
}
|
|
|
|
return rcBtreeError = rc;
|
|
}
|
|
|
|
/***************************************************************************\
|
|
*
|
|
- Function: RcSplitLeaf( pcacheOld, pcacheNew, qbthr )
|
|
-
|
|
* Status: compressed keys not implemented
|
|
*
|
|
* Purpose: Split a leaf node when a new key won't fit into it.
|
|
*
|
|
* ASSUMES
|
|
* args IN: pcacheOld - the leaf to be split
|
|
* pcacheNew - a leaf buffer to get half the contents of pcacheOld;
|
|
* pcacheNew->bk must be set
|
|
* qbthr
|
|
*
|
|
* PROMISES
|
|
* returns: RC_Success, RC_OutOfMemory
|
|
* args OUT: pcacheOld - cbSlack, cKeys, bkPrev, bkNext updated
|
|
* pcacheNew - about half of the old contents of pcacheOld
|
|
* get put here. cbSlack, cKeys set.
|
|
* qbthr - qbthr->bkFirst and bkLast can be changed
|
|
* globals OUT: rcBtreeError
|
|
* +++
|
|
*
|
|
* Note: For fixed length keys and records, could just split at
|
|
* middle key rather than scanning from the beginning.
|
|
*
|
|
* The new block is always after the old block. This is
|
|
* why we don't have to adjust pointers to the old block
|
|
* (i.e. qbthr->bth.bkFirst).
|
|
*
|
|
\***************************************************************************/
|
|
|
|
__inline static RC_TYPE STDCALL RcSplitLeaf(PCACHE pcacheOld, PCACHE pcacheNew,
|
|
QBTHR qbthr)
|
|
{
|
|
int iOK, iNext, iHalf, cbKey, cbRec, cKeys;
|
|
PBYTE pb;
|
|
|
|
ASSERT(pcacheOld->bFlags & CACHE_VALID);
|
|
|
|
iOK = 0;
|
|
pb = pcacheOld->db.rgbBlock + 2 * sizeof(BK);
|
|
iHalf = (qbthr->bth.cbBlock / 2) - sizeof(BK);
|
|
|
|
for (cKeys = pcacheOld->db.cKeys;;) {
|
|
ASSERT(cKeys > 0);
|
|
|
|
cbKey = CbSizeKey((KEY) pb, qbthr, TRUE);
|
|
cbRec = CbSizeRec(pb + cbKey, qbthr);
|
|
|
|
iNext = iOK + cbKey + cbRec;
|
|
|
|
if (iNext > iHalf)
|
|
break;
|
|
|
|
pb += cbKey + cbRec;
|
|
iOK = iNext;
|
|
cKeys--;
|
|
}
|
|
|
|
// >>>> if compressed, expand first key
|
|
|
|
memmove(pcacheNew->db.rgbBlock + 2 * sizeof(BK),
|
|
pcacheOld->db.rgbBlock + 2 * sizeof(BK) + iOK,
|
|
(int) qbthr->bth.cbBlock - iOK -
|
|
pcacheOld->db.cbSlack - 2 * sizeof(BK));
|
|
|
|
pcacheNew->db.cKeys = cKeys;
|
|
pcacheOld->db.cKeys -= cKeys;
|
|
|
|
pcacheNew->db.cbSlack = pcacheOld->db.cbSlack + iOK;
|
|
pcacheOld->db.cbSlack =
|
|
qbthr->bth.cbBlock - sizeof(DISK_BLOCK) + 1 -
|
|
iOK - 2 * sizeof(BK);
|
|
|
|
pcacheOld->bFlags |= CACHE_DIRTY | CACHE_VALID;
|
|
pcacheNew->bFlags = CACHE_DIRTY | CACHE_VALID;
|
|
|
|
SetBkPrev(pcacheNew, pcacheOld->bk);
|
|
SetBkNext(pcacheNew, BkNext(pcacheOld));
|
|
SetBkNext(pcacheOld, pcacheNew->bk);
|
|
|
|
if (BkNext(pcacheNew) == bkNil)
|
|
qbthr->bth.bkLast = (BK) pcacheNew->bk;
|
|
else {
|
|
|
|
// set new->next->prev = new;
|
|
|
|
CMem mem(CbCacheBlock(qbthr));
|
|
PCACHE pcache = (PCACHE) mem.pb;
|
|
|
|
pcache->bk = BkNext(pcacheNew);
|
|
|
|
if (!FReadBlock(pcache, qbthr))
|
|
return rcBtreeError;
|
|
|
|
SetBkPrev(pcache, pcacheNew->bk);
|
|
if (RcWriteBlock(pcache, qbthr) != RC_Success)
|
|
return rcBtreeError;
|
|
}
|
|
|
|
return rcBtreeError = RC_Success;
|
|
}
|
|
|
|
/***************************************************************************\
|
|
*
|
|
- Function: RcInsertInternal( bk, key, wLevel, qbthr )
|
|
-
|
|
* Status: compressed keys unimplemented
|
|
*
|
|
* Purpose: Insert a bk and key into an internal block.
|
|
*
|
|
* Method: Works recursively. Splits root if need be.
|
|
*
|
|
* ASSUMES
|
|
* args IN: bk - BK to insert
|
|
* key - least key in bk
|
|
* wLevel - level of the block we're inserting
|
|
* qbthr - btree header
|
|
* state IN: We've just done a lookup, so all ancestors are cached.
|
|
* Cache is locked.
|
|
*
|
|
* PROMISES
|
|
* returns: RC_Success, RC_OutOfMemory, RC_BadHandle
|
|
* args OUT: qbthr->cLevels - incremented if root is split
|
|
* qbthr->ghCache, qbthr->pCache - may change if root is
|
|
* split and cache therefore grows
|
|
* state OUT: Cache locked, all ancestors cached.
|
|
*
|
|
* Side Effects: Cache could be different after this call than it was before.
|
|
* Pointers or handles to it from before this call could be
|
|
* invalid. Use qbthr->ghCache or qbthr->pCache to be safe.
|
|
*
|
|
\***************************************************************************/
|
|
|
|
static RC_TYPE STDCALL RcInsertInternal(BK bk, KEY key, int wLevel,
|
|
QBTHR qbthr)
|
|
{
|
|
PCACHE pcache, pcacheNew, pcacheRoot;
|
|
int cLevels, cbKey, cbCBlock = CbCacheBlock(qbthr);
|
|
int iKey;
|
|
PBYTE qb;
|
|
KEY keyNew;
|
|
DWORD bkRoot;
|
|
int iKeySav = 0;
|
|
|
|
cbKey = CbSizeKey(key, qbthr, TRUE);
|
|
|
|
if (wLevel == 0) { // inserting another block at root level
|
|
|
|
// allocate new root bk;
|
|
|
|
bkRoot = BkAlloc(qbthr);
|
|
if (bkRoot == bkNil)
|
|
return rcBtreeError;
|
|
|
|
// grow cache by one cache block;
|
|
|
|
qbthr->bth.cLevels++;
|
|
|
|
qb = (PBYTE) lcCalloc(cbCBlock * qbthr->bth.cLevels);
|
|
|
|
memmove(qb + cbCBlock, qbthr->pCache,
|
|
cbCBlock * (qbthr->bth.cLevels - 1));
|
|
|
|
/*
|
|
* Since key points into the cache if this is a recursive call, we
|
|
* can't free the old cache until a bit later.
|
|
*/
|
|
|
|
PBYTE pOldCache = qbthr->pCache;
|
|
qbthr->pCache = qb;
|
|
|
|
// put old root bk, key, bk into new root block;
|
|
|
|
pcacheRoot = (PCACHE)qbthr->pCache;
|
|
|
|
pcacheRoot->bk = bkRoot;
|
|
pcacheRoot->bFlags = CACHE_DIRTY | CACHE_VALID;
|
|
pcacheRoot->db.cbSlack = qbthr->bth.cbBlock - sizeof( DISK_BLOCK ) + 1
|
|
- ( 2 * sizeof( BK ) + cbKey );
|
|
pcacheRoot->db.cKeys = 1;
|
|
|
|
*(BK *)(pcacheRoot->db.rgbBlock) = qbthr->bth.bkRoot;
|
|
|
|
memmove(pcacheRoot->db.rgbBlock + sizeof(BK), (PBYTE) key, cbKey);
|
|
|
|
// OK, now we're done with key, so we can safely free the old cache.
|
|
|
|
lcFree(pOldCache);
|
|
|
|
*(BK *)(pcacheRoot->db.rgbBlock + sizeof( BK ) + cbKey) = bk;
|
|
|
|
qbthr->bth.bkRoot = (BK) bkRoot;
|
|
return rcBtreeError = RC_Success;
|
|
}
|
|
|
|
pcache = QCacheBlock(qbthr, wLevel - 1);
|
|
|
|
if (cbKey + (int) sizeof(BK) > pcache->db.cbSlack) {
|
|
|
|
// new key and BK won't fit in block so split the block;
|
|
|
|
pcacheNew = (PCACHE) lcCalloc(CbCacheBlock(qbthr));
|
|
|
|
if ((pcacheNew->bk = BkAlloc(qbthr)) == bkNil) {
|
|
lcFree(pcacheNew);
|
|
return rcBtreeError;
|
|
}
|
|
SplitInternal(pcache, pcacheNew, qbthr, &iKey);
|
|
keyNew = (KEY) pcache->db.rgbBlock + iKey;
|
|
|
|
cLevels = qbthr->bth.cLevels;
|
|
|
|
if (wLevel < cLevels - 1) {
|
|
|
|
/*
|
|
* This is a recursive call (the arg bk doesn't refer to a leaf.)
|
|
* This means that the arg key points into the cache, so it will be
|
|
* invalid if the root is split. Verify with some asserts that key
|
|
* points into the cache.
|
|
*/
|
|
|
|
ASSERT( (PBYTE)key > qbthr->pCache + CbCacheBlock( qbthr ) );
|
|
ASSERT( (PBYTE)key < qbthr->pCache + wLevel * CbCacheBlock( qbthr ) );
|
|
|
|
/* Save the offset of key into the cache block. Recall that key
|
|
** is the first invalid key in an internal node that has just
|
|
** been split. It points into the part that is still in the cache.
|
|
*/
|
|
iKeySav = (PBYTE)key - ( qbthr->pCache + wLevel * CbCacheBlock( qbthr ) );
|
|
}
|
|
|
|
if (RcInsertInternal((BK) pcacheNew->bk, (KEY) pcache->db.rgbBlock + iKey,
|
|
wLevel - 1, qbthr) != RC_Success ) {
|
|
lcFree(pcacheNew);
|
|
return rcBtreeError;
|
|
}
|
|
|
|
// RcInsertInternal() can change cache and qbthr->bth.cLevels
|
|
|
|
if (cLevels != qbthr->bth.cLevels) {
|
|
|
|
ASSERT(cLevels + 1 == qbthr->bth.cLevels);
|
|
|
|
wLevel++;
|
|
pcache = QCacheBlock(qbthr, wLevel - 1);
|
|
keyNew = (KEY) pcache->db.rgbBlock + iKey;
|
|
|
|
// Also restore the arg "key" if it pointed into the cache.
|
|
|
|
if (iKeySav)
|
|
key = (KEY) (qbthr->pCache + wLevel * CbCacheBlock(qbthr) + iKeySav);
|
|
}
|
|
|
|
// find out which block to put new key and bk in, and cache it
|
|
|
|
if (WCmpKey(key, keyNew, (KT) qbthr->bth.rgchFormat[0]) < 0) {
|
|
if (RcWriteBlock(pcacheNew, qbthr) != RC_Success) {
|
|
lcFree(pcacheNew);
|
|
return rcBtreeError;
|
|
}
|
|
}
|
|
else {
|
|
|
|
// write old block and cache the new one
|
|
|
|
if (RcWriteBlock(pcache, qbthr) != RC_Success) {
|
|
lcFree(pcacheNew);
|
|
return rcBtreeError;
|
|
}
|
|
memmove(pcache, pcacheNew, (int) CbCacheBlock(qbthr));
|
|
}
|
|
|
|
lcFree(pcacheNew);
|
|
}
|
|
|
|
// slide stuff over and insert the new key, bk
|
|
|
|
// get pos
|
|
|
|
if (qbthr->BkScanInternal((BK) pcache->bk, key, wLevel - 1, qbthr, &iKey)
|
|
== bkNil)
|
|
return rcBtreeError;
|
|
|
|
ASSERT(iKey + cbKey + sizeof(BK) <
|
|
qbthr->bth.cbBlock - sizeof(DISK_BLOCK) + 1);
|
|
|
|
qb = (PBYTE) (pcache->db.rgbBlock) + iKey;
|
|
|
|
memmove(qb + cbKey + sizeof(BK), qb,
|
|
(int) qbthr->bth.cbBlock - iKey - pcache->db.cbSlack
|
|
- sizeof(DISK_BLOCK) + 1);
|
|
|
|
memmove(qb, (PBYTE) key, cbKey);
|
|
*(BK *) (qb + cbKey) = bk;
|
|
|
|
pcache->db.cKeys++;
|
|
pcache->db.cbSlack -= (cbKey + sizeof(BK));
|
|
pcache->bFlags |= CACHE_DIRTY;
|
|
|
|
return rcBtreeError = RC_Success;
|
|
}
|
|
|
|
/***************************************************************************\
|
|
*
|
|
- Function: SplitInternal( pcacheOld, pcacheNew, qbthr, qi )
|
|
-
|
|
* Status: compressed keys not implemented
|
|
*
|
|
* Purpose: Split an internal node node when a new key won't fit into it.
|
|
* Old node gets BKs and KEYs up to the first key that won't
|
|
* fit in half the block size. (Leave that key there with iKey
|
|
* pointing at it). The new block gets the BKs and KEYs after
|
|
* that key.
|
|
*
|
|
* ASSUMES
|
|
* args IN: pcacheOld - the block to split
|
|
* pcacheNew - pointer to a pcache
|
|
* qbthr -
|
|
*
|
|
* PROMISES
|
|
* args OUT: pcacheNew - keys and records copied to this buffer.
|
|
* cbSlack, cKeys set.
|
|
* pcacheOld - cbSlack and cKeys updated.
|
|
* qi - index into pcacheOld->db.rgbBlock of discriminating key
|
|
*
|
|
* NOTE: *qi is index of a key that is not valid for pcacheOld. This
|
|
* key gets copied into the parent node.
|
|
*
|
|
\***************************************************************************/
|
|
|
|
__inline static void STDCALL SplitInternal(PCACHE pcacheOld, PCACHE pcacheNew,
|
|
QBTHR qbthr, int* qi)
|
|
{
|
|
int iOK, iNext, iHalf, cb, cKeys, cbTotal;
|
|
PBYTE q;
|
|
|
|
ASSERT(pcacheOld->bFlags & CACHE_VALID);
|
|
|
|
iOK = iNext = sizeof(BK);
|
|
q = pcacheOld->db.rgbBlock + sizeof(BK);
|
|
iHalf = qbthr->bth.cbBlock / 2;
|
|
|
|
for (cKeys = pcacheOld->db.cKeys;; cKeys--) {
|
|
ASSERT(cKeys > 0);
|
|
|
|
cb = CbSizeKey((KEY) q, qbthr, TRUE) + sizeof(BK);
|
|
iNext = iOK + cb;
|
|
|
|
if (iNext > iHalf) break;
|
|
|
|
q += cb;
|
|
iOK = iNext;
|
|
}
|
|
|
|
// have to expand first key if compressed
|
|
|
|
cbTotal = qbthr->bth.cbBlock - sizeof(DISK_BLOCK) + 1;
|
|
|
|
memmove(pcacheNew->db.rgbBlock,
|
|
pcacheOld->db.rgbBlock + iNext - sizeof(BK),
|
|
(int) cbTotal - pcacheOld->db.cbSlack - iNext + sizeof(BK));
|
|
|
|
*qi = iOK;
|
|
|
|
pcacheNew->db.cKeys = cKeys - 1;
|
|
pcacheOld->db.cKeys -= cKeys;
|
|
|
|
pcacheNew->db.cbSlack = pcacheOld->db.cbSlack + iNext - sizeof(BK);
|
|
pcacheOld->db.cbSlack = cbTotal - iOK;
|
|
|
|
pcacheOld->bFlags |= CACHE_DIRTY | CACHE_VALID;
|
|
pcacheNew->bFlags = CACHE_DIRTY | CACHE_VALID;
|
|
}
|
|
|
|
/***************************************************************************\
|
|
*
|
|
- Function: HbtOpenBtreeSz( sz, hfs, bFlags )
|
|
-
|
|
* Purpose: open an existing btree
|
|
*
|
|
* ASSUMES
|
|
* args IN: sz - name of the btree (ignored if isdir is set)
|
|
* hfs - hfs btree lives in
|
|
* bFlags - open mode, isdir flag
|
|
*
|
|
* PROMISES
|
|
* returns: handle to the open btree or NULL on failure
|
|
* isdir flag set in qbthr->bth.bFlags if indicated
|
|
* globals OUT: rcBtreeError set
|
|
*
|
|
\***************************************************************************/
|
|
|
|
QBTHR STDCALL HbtOpenBtreeSz(PCSTR psz, HFS hfs, BYTE bFlags)
|
|
{
|
|
HF hf;
|
|
int lcb;
|
|
|
|
// allocate struct
|
|
|
|
QBTHR qbthr = (QBTHR) lcCalloc(sizeof(BTH_RAM));
|
|
|
|
// open btree file
|
|
|
|
hf = HfOpenHfs((QFSHR) hfs, psz, bFlags);
|
|
if (hf == NULL) {
|
|
rcBtreeError = rcFSError;
|
|
goto error_locked;
|
|
}
|
|
|
|
// read header from file
|
|
|
|
lcb = LcbReadHf(hf, &(qbthr->bth), sizeof(BTH));
|
|
if (lcb != sizeof(BTH)) {
|
|
rcBtreeError = (rcFSError == RC_Success ? RC_Invalid : rcFSError);
|
|
goto error_openfile;
|
|
}
|
|
|
|
qbthr->bth.bFlags |= FS_IS_DIRECTORY;
|
|
|
|
if (qbthr->bth.wMagic != WBTREEMAGIC) { // check magic number
|
|
rcBtreeError = RC_Invalid;
|
|
goto error_openfile;
|
|
}
|
|
|
|
if (qbthr->bth.bVersion != BBTREEVERSION) { // support >1 vers someday
|
|
rcBtreeError = RC_BadVersion;
|
|
goto error_openfile;
|
|
}
|
|
|
|
// initialize stuff
|
|
|
|
RcMakeCache(qbthr);
|
|
|
|
qbthr->hf = hf;
|
|
qbthr->cbRecordSize = 0;
|
|
|
|
if (InitQbthr(qbthr->bth.rgchFormat[0], qbthr)) {
|
|
if ((bFlags | qbthr->bth.bFlags) & (FS_READ_ONLY | FS_OPEN_READ_ONLY))
|
|
qbthr->bth.bFlags |= FS_OPEN_READ_ONLY;
|
|
|
|
return qbthr;
|
|
}
|
|
|
|
error_openfile:
|
|
RcCloseHf(hf);
|
|
|
|
error_locked:
|
|
lcFree(qbthr);
|
|
return NULL;
|
|
}
|
|
|
|
/***************************************************************************\
|
|
*
|
|
- Function: RcScanSzLeaf( bk, key, wLevel, qbthr, qRec, qbtpos )
|
|
-
|
|
* Purpose: Scan a leaf node for a key and copy the associated data.
|
|
*
|
|
* ASSUMES
|
|
* args IN: bk - the leaf block
|
|
* key - the key we're looking for
|
|
* wLevel - the level of leaves (unnecessary)
|
|
* qbthr - the btree header
|
|
*
|
|
* PROMISES
|
|
* returns: rcSuccess if found; rcNoExists if not found
|
|
* args OUT: qRec - if found, record gets copied into this buffer
|
|
* qbtpos - pos of first key >= key goes here
|
|
*
|
|
* Notes: If we are scanning for a key greater than any key in this
|
|
* block, the pos returned will be invalid and will point just
|
|
* past the last valid key in this block.
|
|
*
|
|
\***************************************************************************/
|
|
|
|
RC_TYPE STDCALL RcScanSzLeaf(BK bk, KEY key, int wLevel, QBTHR qbthr,
|
|
LPVOID qRec, QBTPOS qbtpos)
|
|
{
|
|
PCACHE qcb;
|
|
LPSTR sz;
|
|
int w, cKey;
|
|
PBYTE qb;
|
|
|
|
if ((qcb = QFromBk(bk, wLevel, qbthr)) == NULL)
|
|
return rcBtreeError;
|
|
|
|
rcBtreeError = RC_NoExists;
|
|
|
|
sz = (PSTR) (qcb->db.rgbBlock + 2 * sizeof(BK));
|
|
|
|
for (cKey = 0; cKey < qcb->db.cKeys; cKey++) {
|
|
w = qbthr->SzCmp((LPSTR) key, sz);
|
|
|
|
if (w > 0) { // still looking for key
|
|
sz += lstrlen(sz) + 1;
|
|
if (qbthr->cbRecordSize)
|
|
sz += qbthr->cbRecordSize;
|
|
else
|
|
sz += CbSizeRec(sz, qbthr);
|
|
}
|
|
else if (w < 0) { // key not found
|
|
break;
|
|
}
|
|
else { // matched the key
|
|
if (qRec != NULL) {
|
|
qb = (PBYTE) sz + lstrlen(sz) + 1;
|
|
MoveMemory(qRec, qb, (LONG) CbSizeRec(qb, qbthr));
|
|
}
|
|
|
|
rcBtreeError = RC_Success;
|
|
break;
|
|
}
|
|
}
|
|
|
|
if (qbtpos != NULL) {
|
|
qbtpos->bk = bk;
|
|
qbtpos->cKey = cKey;
|
|
qbtpos->iKey = (PBYTE) sz - (PBYTE) qcb->db.rgbBlock;
|
|
}
|
|
|
|
return rcBtreeError;;
|
|
}
|
|
|
|
RC_TYPE STDCALL RcScanLeaf(BK bk, KEY key, int wLevel, QBTHR qbthr,
|
|
void* qRec, QBTPOS qbtpos)
|
|
{
|
|
PCACHE pcache;
|
|
|
|
if ((pcache = QFromBk(bk, wLevel, qbthr)) == NULL)
|
|
return rcBtreeError;
|
|
|
|
rcBtreeError = RC_NoExists;
|
|
|
|
PSTR psz = (PSTR) pcache->db.rgbBlock + 2 * sizeof(BK);
|
|
|
|
for (int cKey = 0; cKey < pcache->db.cKeys; cKey++) {
|
|
int w = pstrcmp((PSTR) key, psz);
|
|
|
|
if (w > 0) { // still looking for key
|
|
psz += strlen(psz) + 1;
|
|
psz += CbSizeRec(psz, qbthr);
|
|
}
|
|
else if (w < 0) { // key not found
|
|
break;
|
|
}
|
|
else { // matched the key
|
|
if (qRec != NULL) {
|
|
PBYTE qb = (PBYTE) psz + strlen(psz) + 1;
|
|
memmove(qRec, qb, CbSizeRec(qb, qbthr));
|
|
}
|
|
|
|
rcBtreeError = RC_Success;
|
|
break;
|
|
}
|
|
}
|
|
|
|
if (qbtpos != NULL) {
|
|
qbtpos->bk = bk;
|
|
qbtpos->cKey = cKey;
|
|
qbtpos->iKey = (PBYTE) psz - (PBYTE) pcache->db.rgbBlock;
|
|
}
|
|
|
|
return rcBtreeError;;
|
|
}
|
|
|
|
BK STDCALL BkScanInternal(BK bk, KEY key, int wLevel, QBTHR qbthr, int* piKey)
|
|
{
|
|
PCACHE pcache;
|
|
|
|
if ((pcache = QFromBk(bk, wLevel, qbthr)) == NULL)
|
|
return bkNil;
|
|
PBYTE pb = pcache->db.rgbBlock;
|
|
int cKeys = pcache->db.cKeys;
|
|
|
|
bk = *(BK *) pb;
|
|
pb += sizeof(BK);
|
|
|
|
while (cKeys-- > 0) {
|
|
if (pstrcmp((PSTR) key, (PSTR) pb) >= 0) {
|
|
pb += strlen((PSTR) pb) + 1;
|
|
bk = *(BK *) pb;
|
|
pb += sizeof(BK);
|
|
}
|
|
else
|
|
break;
|
|
}
|
|
|
|
if (piKey != NULL)
|
|
*piKey = pb - (PBYTE) pcache->db.rgbBlock;
|
|
|
|
return bk;
|
|
}
|
|
|
|
static BOOL STDCALL InitQbthr(char chType, QBTHR qbthr)
|
|
{
|
|
if (chType == KT_LONG) {
|
|
qbthr->BkScanInternal = BkScanLInternal;
|
|
qbthr->RcScanLeaf = RcScanLLeaf;
|
|
}
|
|
else {
|
|
qbthr->BkScanInternal = BkScanSzInternal;
|
|
qbthr->RcScanLeaf = RcScanSzLeaf;
|
|
}
|
|
|
|
switch ((KT) chType) {
|
|
case KT_LONG:
|
|
return TRUE;
|
|
|
|
case KT_SZ:
|
|
qbthr->SzCmp = WCmpSz;
|
|
return TRUE;
|
|
|
|
case KT_SZI:
|
|
qbthr->SzCmp = WCmpiSz;
|
|
return TRUE;
|
|
|
|
case KT_SZISCAND:
|
|
qbthr->SzCmp = WCmpiScandSz;
|
|
return TRUE;
|
|
|
|
case KT_NLSI:
|
|
qbthr->SzCmp = WNlsCmpiSz;
|
|
return TRUE;
|
|
|
|
case KT_NLS:
|
|
qbthr->SzCmp = WNlsCmpSz;
|
|
return TRUE;
|
|
|
|
case KT_SZIKOREA:
|
|
qbthr->SzCmp = WCmpiKoreaSz;
|
|
return TRUE;
|
|
|
|
case KT_SZIJAPAN:
|
|
qbthr->SzCmp = WCmpiJapanSz;
|
|
return TRUE;
|
|
|
|
case KT_SZITAIWAN:
|
|
qbthr->SzCmp = WCmpiTaiwanSz;
|
|
return TRUE;
|
|
|
|
default:
|
|
if (KtToLcid((KT) chType)) {
|
|
qbthr->SzCmp = WNlsCmpiSz;
|
|
return TRUE;
|
|
}
|
|
// unsupported KT
|
|
|
|
rcBtreeError = RC_Invalid;
|
|
return FALSE;
|
|
}
|
|
}
|
|
|
|
static BOOL FASTCALL KtToLcid(KT kt)
|
|
{
|
|
if (lcid)
|
|
return TRUE; // already set
|
|
|
|
switch (kt) {
|
|
case KT_SZICZECH:
|
|
lcid = MAKELCID(0x0405, SORT_DEFAULT);
|
|
return TRUE;
|
|
|
|
case KT_SZIHUNGAR:
|
|
lcid = MAKELCID(0x040E, SORT_DEFAULT);
|
|
return TRUE;
|
|
|
|
case KT_SZIPOLISH:
|
|
lcid = MAKELCID(0x0415, SORT_DEFAULT);
|
|
return TRUE;
|
|
|
|
case KT_SZIRUSSIAN:
|
|
lcid = MAKELCID(0x0419, SORT_DEFAULT);
|
|
return TRUE;
|
|
}
|
|
return FALSE;
|
|
}
|
|
|
|
/***************************************************************************\
|
|
*
|
|
- Function: BkScanSzInternal( bk, key, wLevel, qbthr )
|
|
-
|
|
* Purpose: Scan an internal node for a key and return child BK.
|
|
*
|
|
* ASSUMES
|
|
* args IN: bk - BK of internal node to scan
|
|
* key - key to search for
|
|
* wLevel - level of btree bk lives on
|
|
* qbthr - btree header containing cache, and btree specs
|
|
* qiKey - address of an int or NULL to not get it
|
|
*
|
|
* PROMISES
|
|
* returns: bk of subtree that might contain key; bkNil on error
|
|
* args OUT: qbthr->qCache - bk's block will be cached
|
|
* qiKey - index into rgbBlock of first key >= key
|
|
*
|
|
* Side Effects: bk's block will be cached
|
|
*
|
|
\***************************************************************************/
|
|
|
|
BK STDCALL BkScanSzInternal(BK bk, KEY key, int wLevel, QBTHR qbthr, int* qiKey)
|
|
{
|
|
PCACHE qcb;
|
|
PBYTE pb;
|
|
int cKeys;
|
|
|
|
if (!(qcb = QFromBk(bk, wLevel, qbthr)))
|
|
return bkNil;
|
|
|
|
pb = qcb->db.rgbBlock;
|
|
cKeys = qcb->db.cKeys;
|
|
|
|
bk = *(BK *) pb;
|
|
pb += sizeof(BK);
|
|
|
|
while (cKeys-- > 0) {
|
|
if (qbthr->SzCmp((LPSTR) key, (LPSTR) pb) >= 0) {
|
|
pb += lstrlen((LPSTR) pb) + 1;
|
|
bk = *(BK *) pb;
|
|
pb += sizeof(BK);
|
|
}
|
|
else
|
|
break;
|
|
}
|
|
|
|
if (qiKey != NULL)
|
|
*qiKey = pb - (LPBYTE) qcb->db.rgbBlock;
|
|
|
|
return bk;
|
|
}
|
|
|
|
/***************************************************************************
|
|
|
|
FUNCTION: WCmpSz
|
|
|
|
PURPOSE: Enclosed in a STDCALL function.
|
|
|
|
PARAMETERS:
|
|
sz1
|
|
sz2
|
|
|
|
RETURNS:
|
|
|
|
COMMENTS:
|
|
|
|
MODIFICATION DATES:
|
|
21-Nov-1993 [ralphw]
|
|
|
|
***************************************************************************/
|
|
|
|
static int STDCALL WCmpSz(LPCSTR sz1, LPCSTR sz2)
|
|
{
|
|
return strcmp(sz1, sz2); // must NOT be lstrcmp. Sort order differs
|
|
}
|