📄 btr.c
字号:
} else {
/* something's wrong */
free(h);
return bErrFileNotOpen;
}
/* append node to hList */
if (hList.next) {
h->prev = hList.next;
h->next = &hList;
h->prev->next = h;
h->next->prev = h;
} else {
/* first item in hList */
h->prev = h->next = &hList;
hList.next = hList.prev = h;
}
*handle = h;
return bErrOk;
}
bErrType bClose(bHandleType handle) {
h = handle;
if (h == NULL) return bErrOk;
/* remove from list */
if (h->next) {
h->next->prev = h->prev;
h->prev->next = h->next;
}
/* flush idx */
if (h->fp) {
flushAll();
fclose(h->fp);
}
if (h->malloc2) free(h->malloc2);
if (h->malloc1) free(h->malloc1);
free(h);
return bErrOk;
}
bErrType bFindKey(bHandleType handle, void *key, eAdrType *rec) {
keyType *mkey; /* matched key */
bufType *buf; /* buffer */
bErrType rc; /* return code */
h = handle;
buf = &h->root;
/* find key, and return address */
while (1) {
if (leaf(buf)) {
if (search(buf, key, 0, &mkey, MODE_FIRST) == 0) {
*rec = rec(mkey);
h->curBuf = buf; h->curKey = mkey;
return bErrOk;
} else {
return bErrKeyNotFound;
}
} else {
if (search(buf, key, 0, &mkey, MODE_FIRST) < 0) {
if ((rc = readDisk(childLT(mkey), &buf)) != 0) return rc;
} else {
if ((rc = readDisk(childGE(mkey), &buf)) != 0) return rc;
}
}
}
}
bErrType bInsertKey(bHandleType handle, void *key, eAdrType rec) {
int rc; /* return code */
keyType *mkey; /* match key */
int len; /* length to shift */
int cc; /* condition code */
bufType *buf, *root;
bufType *tmp[4];
unsigned int keyOff;
bool lastGEvalid; /* true if GE branch taken */
bool lastLTvalid; /* true if LT branch taken after GE branch */
bAdrType lastGE; /* last childGE traversed */
unsigned int lastGEkey; /* last childGE key traversed */
int height; /* height of tree */
h = handle;
root = &h->root;
lastGEvalid = false;
lastLTvalid = false;
/* check for full root */
if (ct(root) == 3 * h->maxCt) {
/* gather root and scatter to 4 bufs */
/* this increases b-tree height by 1 */
if ((rc = gatherRoot()) != 0) return rc;
if ((rc = scatter(root, fkey(root), 0, tmp)) != 0) return rc;
}
buf = root;
height = 0;
while(1) {
if (leaf(buf)) {
/* in leaf, and there' room guaranteed */
if (height > maxHeight) maxHeight = height;
/* set mkey to point to insertion point */
switch(search(buf, key, rec, &mkey, MODE_MATCH)) {
case CC_LT: /* key < mkey */
if (!h->dupKeys && h->comp(key, mkey) == CC_EQ)
return bErrDupKeys;
break;
case CC_EQ: /* key = mkey */
return bErrDupKeys;
break;
case CC_GT: /* key > mkey */
if (!h->dupKeys && h->comp(key, mkey) == CC_EQ)
return bErrDupKeys;
mkey += ks(1);
break;
}
/* shift items GE key to right */
keyOff = mkey - fkey(buf);
len = ks(ct(buf)) - keyOff;
if (len) memmove(mkey + ks(1), mkey, len);
/* insert new key */
memcpy(key(mkey), key, h->keySize);
rec(mkey) = rec;
childGE(mkey) = 0;
ct(buf)++;
if ((rc = writeDisk(buf)) != 0) return rc;
/* if new key is first key, then fixup lastGE key */
if (!keyOff && lastLTvalid) {
bufType *tbuf;
keyType *tkey;
if ((rc = readDisk(lastGE, &tbuf)) != 0) return rc;
tkey = fkey(tbuf) + lastGEkey;
memcpy(key(tkey), key, h->keySize);
rec(tkey) = rec;
if ((rc = writeDisk(tbuf)) != 0) return rc;
}
nKeysIns++;
break;
} else {
/* internal node, descend to child */
bufType *cbuf; /* child buf */
height++;
/* read child */
if ((cc = search(buf, key, rec, &mkey, MODE_MATCH)) < 0) {
if ((rc = readDisk(childLT(mkey), &cbuf)) != 0) return rc;
} else {
if ((rc = readDisk(childGE(mkey), &cbuf)) != 0) return rc;
}
/* check for room in child */
if (ct(cbuf) == h->maxCt) {
/* gather 3 bufs and scatter */
if ((rc = gather(buf, &mkey, tmp)) != 0) return rc;
if ((rc = scatter(buf, mkey, 3, tmp)) != 0) return rc;
/* read child */
if ((cc = search(buf, key, rec, &mkey, MODE_MATCH)) < 0) {
if ((rc = readDisk(childLT(mkey), &cbuf)) != 0) return rc;
} else {
if ((rc = readDisk(childGE(mkey), &cbuf)) != 0) return rc;
}
}
if (cc >= 0 || mkey != fkey(buf)) {
lastGEvalid = true;
lastLTvalid = false;
lastGE = buf->adr;
lastGEkey = mkey - fkey(buf);
if (cc < 0) lastGEkey -= ks(1);
} else {
if (lastGEvalid) lastLTvalid = true;
}
buf = cbuf;
}
}
return bErrOk;
}
bErrType bDeleteKey(bHandleType handle, void *key, eAdrType *rec) {
int rc; /* return code */
keyType *mkey; /* match key */
int len; /* length to shift */
int cc; /* condition code */
bufType *buf; /* buffer */
bufType *tmp[4];
unsigned int keyOff;
bool lastGEvalid; /* true if GE branch taken */
bool lastLTvalid; /* true if LT branch taken after GE branch */
bAdrType lastGE; /* last childGE traversed */
unsigned int lastGEkey; /* last childGE key traversed */
bufType *root;
bufType *gbuf;
h = handle;
root = &h->root;
gbuf = &h->gbuf;
lastGEvalid = false;
lastLTvalid = false;
buf = root;
while(1) {
if (leaf(buf)) {
/* set mkey to point to deletion point */
if (search(buf, key, *rec, &mkey, MODE_MATCH) == 0)
*rec = rec(mkey);
else
return bErrKeyNotFound;
/* shift items GT key to left */
keyOff = mkey - fkey(buf);
len = ks(ct(buf)-1) - keyOff;
if (len) memmove(mkey, mkey + ks(1), len);
ct(buf)--;
if ((rc = writeDisk(buf)) != 0) return rc;
/* if deleted key is first key, then fixup lastGE key */
if (!keyOff && lastLTvalid) {
bufType *tbuf;
keyType *tkey;
if ((rc = readDisk(lastGE, &tbuf)) != 0) return rc;
tkey = fkey(tbuf) + lastGEkey;
memcpy(key(tkey), mkey, h->keySize);
rec(tkey) = rec(mkey);
if ((rc = writeDisk(tbuf)) != 0) return rc;
}
nKeysDel++;
break;
} else {
/* internal node, descend to child */
bufType *cbuf; /* child buf */
/* read child */
if ((cc = search(buf, key, *rec, &mkey, MODE_MATCH)) < 0) {
if ((rc = readDisk(childLT(mkey), &cbuf)) != 0) return rc;
} else {
if ((rc = readDisk(childGE(mkey), &cbuf)) != 0) return rc;
}
/* check for room to delete */
if (ct(cbuf) == h->maxCt/2) {
/* gather 3 bufs and scatter */
if ((rc = gather(buf, &mkey, tmp)) != 0) return rc;
/* if last 3 bufs in root, and count is low enough... */
if (buf == root
&& ct(root) == 2
&& ct(gbuf) < (3*(3*h->maxCt))/4) {
/* collapse tree by one level */
scatterRoot();
nNodesDel += 3;
continue;
}
if ((rc = scatter(buf, mkey, 3, tmp)) != 0) return rc;
/* read child */
if ((cc = search(buf, key, *rec, &mkey, MODE_MATCH)) < 0) {
if ((rc = readDisk(childLT(mkey), &cbuf)) != 0) return rc;
} else {
if ((rc = readDisk(childGE(mkey), &cbuf)) != 0) return rc;
}
}
if (cc >= 0 || mkey != fkey(buf)) {
lastGEvalid = true;
lastLTvalid = false;
lastGE = buf->adr;
lastGEkey = mkey - fkey(buf);
if (cc < 0) lastGEkey -= ks(1);
} else {
if (lastGEvalid) lastLTvalid = true;
}
buf = cbuf;
}
}
return bErrOk;
}
bErrType bFindFirstKey(bHandleType handle, void *key, eAdrType *rec) {
bErrType rc; /* return code */
bufType *buf; /* buffer */
h = handle;
buf = &h->root;
while (!leaf(buf)) {
if ((rc = readDisk(childLT(fkey(buf)), &buf)) != 0) return rc;
}
if (ct(buf) == 0) return bErrKeyNotFound;
memcpy(key, key(fkey(buf)), h->keySize);
*rec = rec(fkey(buf));
h->curBuf = buf; h->curKey = fkey(buf);
return bErrOk;
}
bErrType bFindLastKey(bHandleType handle, void *key, eAdrType *rec) {
bErrType rc; /* return code */
bufType *buf; /* buffer */
h = handle;
buf = &h->root;
while (!leaf(buf)) {
if ((rc = readDisk(childGE(lkey(buf)), &buf)) != 0) return rc;
}
if (ct(buf) == 0) return bErrKeyNotFound;
memcpy(key, key(lkey(buf)), h->keySize);
*rec = rec(lkey(buf));
h->curBuf = buf; h->curKey = lkey(buf);
return bErrOk;
}
bErrType bFindNextKey(bHandleType handle, void *key, eAdrType *rec) {
bErrType rc; /* return code */
keyType *nkey; /* next key */
bufType *buf; /* buffer */
h = handle;
if ((buf = h->curBuf) == NULL) return bErrKeyNotFound;
if (h->curKey == lkey(buf)) {
/* current key is last key in leaf node */
if (next(buf)) {
/* fetch next set */
if ((rc = readDisk(next(buf), &buf)) != 0) return rc;
nkey = fkey(buf);
} else {
/* no more sets */
return bErrKeyNotFound;
}
} else {
/* bump to next key */
nkey = h->curKey + ks(1);
}
memcpy(key, key(nkey), h->keySize);
*rec = rec(nkey);
h->curBuf = buf; h->curKey = nkey;
return bErrOk;
}
bErrType bFindPrevKey(bHandleType handle, void *key, eAdrType *rec) {
bErrType rc; /* return code */
keyType *pkey; /* previous key */
keyType *fkey; /* first key */
bufType *buf; /* buffer */
h = handle;
if ((buf = h->curBuf) == NULL) return bErrKeyNotFound;
fkey = fkey(buf);
if (h->curKey == fkey) {
/* current key is first key in leaf node */
if (prev(buf)) {
/* fetch previous set */
if ((rc = readDisk(prev(buf), &buf)) != 0) return rc;
pkey = fkey(buf) + ks((ct(buf) - 1));
} else {
/* no more sets */
return bErrKeyNotFound;
}
} else {
/* bump to previous key */
pkey = h->curKey - ks(1);
}
memcpy(key, key(pkey), h->keySize);
*rec = rec(pkey);
h->curBuf = buf; h->curKey = pkey;
return bErrOk;
}
int comp(const void *key1, const void *key2) {
unsigned int const *p1;
unsigned int const *p2;
p1 = key1; p2 = key2;
return (*p1 == *p2) ? CC_EQ : (*p1 > *p2 ) ? CC_GT : CC_LT;
}
int main(void) {
bOpenType info;
bHandleType handle;
bErrType rc;
unsigned int key;
remove("t1.dat");
info.iName = "t1.dat";
info.keySize = sizeof(int);
info.dupKeys = false;
info.sectorSize = 256;
info.comp = comp;
if ((rc = bOpen(info, &handle)) != bErrOk) {
printf("line %d: rc = %d\n", __LINE__, rc);
exit(0);
}
key = 0x11;
if ((rc = bInsertKey(handle, &key, 0x300)) != bErrOk) {
printf("line %d: rc = %d\n", __LINE__, rc);
exit(0);
}
bClose(handle);
printf("statistics:\n");
printf(" maximum height: %8d\n", maxHeight);
printf(" nodes inserted: %8d\n", nNodesIns);
printf(" nodes deleted: %8d\n", nNodesDel);
printf(" keys inserted: %8d\n", nKeysIns);
printf(" keys deleted: %8d\n", nKeysDel);
printf(" disk reads: %8d\n", nDiskReads);
printf(" disk writes: %8d\n", nDiskWrites);
return 0;
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -