Creating simple code for BinaryTree: Declare a BinaryTree object using the heade
ID: 3786832 • Letter: C
Question
Creating simple code for BinaryTree:
Declare a BinaryTree object using the header file and constuct as like figure 1 :
Header file :
#ifndef _BINARYTREE_H_
#define _BINARYTREE_H_
//#include <Windows.h>
#include <list>
#include <string>
typedef std::string Elem; // base element type
class BinaryTree {
protected:
struct Node { // a node of the tree
Elem elt; // element value
Node* par; // parent
Node* left; // left child
Node* right; // right child
Node() : elt(), par( NULL ), left( NULL ), right( NULL ) {} // constructor
};
public:
class Position { // position in the tree
private:
Node* v; // pointer to the node
public:
Position( Node* _v = NULL ) : v( _v ) {} // constructor
Elem& operator*() const // get element
{
return v->elt;
}
Position left() const // get left child
{
return Position( v->left );
}
Position right() const // get right child
{
return Position( v->right );
}
Position parent() const // get parent
{
return Position( v->par );
}
bool isRoot() const // root of the tree?
{
return v->par == NULL;
}
bool isExternal() const // an external node?
{
return v->left == NULL && v->right == NULL;
}
friend class BinaryTree; // give tree access
};
typedef std::list<Position> PositionList; // list of positions
public:
BinaryTree(); // constructor
int size() const; // number of nodes
bool empty() const; // is tree empty?
Position root() const; // get the root
PositionList positions() const; // list of nodes
void addRoot(); // add root to empty tree
void expandExternal( const Position& p ); // expand external node
Position removeAboveExternal( const Position& p ); // remove p and parent
// housekeeping functions omitted...
protected: // local utilities
void preorder( Node* v, PositionList& pl ) const; // preorder utility
private:
Node* _root; // pointer to the root
int n; // number of nodes
};
#endif // _BINARYTREE_H_
Figure 1:
I have started the main code with following:
#include <cstdio>
#include <cstdlib>
#include "BinaryTree.h"
int main()
{
// What goes here?
system( "pause" );
return EXIT_SUCCESS;
}
// 4 7 3 2 5 9 3 3Explanation / Answer
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <string.h>
typedef long eAdrType; /* record address for external record */
typedef long bAdrType; /* record address for btree node */
#define CC_EQ 0
#define CC_GT 1
#define CC_LT -1
typedef int (*bCompType)(const void *key1, const void *key2);
int maxHeight; /* maximum height attained */
int nNodesIns; /* number of nodes inserted */
int nNodesDel; /* number of nodes deleted */
int nKeysIns; /* number of keys inserted */
int nKeysDel; /* number of keys deleted */
int nDiskReads; /* number of disk reads */
int nDiskWrites; /* number of disk writes */
int bErrLineNo;
typedef enum {false, true} bool;
typedef enum {
bErrOk,
bErrKeyNotFound,
bErrDupKeys,
bErrSectorSize,
bErrFileNotOpen,
bErrFileExists,
bErrIO,
bErrMemory
} bErrType;
typedef void *bHandleType;
typedef struct { /* info for bOpen() */
char *iName; /* name of index file */
int keySize; /* length, in bytes, of key */
bool dupKeys; /* true if duplicate keys allowed */
int sectorSize; /* size of sector on disk */
bCompType comp; /* pointer to compare function */
} bOpenType;
bErrType bOpen(bOpenType info, bHandleType *handle);bErrType bClose(bHandleType handle);
bErrType bInsertKey(bHandleType handle, void *key, eAdrType rec);
bErrType bDeleteKey(bHandleType handle, void *key, eAdrType *rec);
bErrType bFindKey(bHandleType handle, void *key, eAdrType *rec);
bErrType bFindFirstKey(bHandleType handle, void *key, eAdrType *rec);
bErrType bFindLastKey(bHandleType handle, void *key, eAdrType *rec);
bErrType bFindNextKey(bHandleType handle, void *key, eAdrType *rec);
bErrType bFindPrevKey(bHandleType handle, void *key, eAdrType *rec);
#define bAdr(p) *(bAdrType *)(p)
#define eAdr(p) *(eAdrType *)(p)
/* based on k = &[key,rec,childGE] */
#define childLT(k) bAdr((char *)k - sizeof(bAdrType))
#define key(k) (k)
#define rec(k) eAdr((char *)(k) + h->keySize)
#define childGE(k) bAdr((char *)(k) + h->keySize + sizeof(eAdrType))
/* based on b = &bufType */
#define leaf(b) b->p->leaf
#define ct(b) b->p->ct
#define next(b) b->p->next
#define prev(b) b->p->prev
#define fkey(b) &b->p->fkey
#define lkey(b) (fkey(b) + ks((ct(b) - 1)))
#define p(b) (char *)(b->p)
/* shortcuts */
#define ks(ct) ((ct) * h->ks)
typedef char keyType; /* keys entries are treated as char arrays */
typedef struct {
unsigned int leaf:1; /* first bit = 1 if leaf */
unsigned int ct:15; /* count of keys present */
bAdrType prev; /* prev node in sequence (leaf) */
bAdrType next; /* next node in sequence (leaf) */
bAdrType childLT; /* child LT first key */
/* ct occurrences of [key,rec,childGE] */
keyType fkey; /* first occurrence */
} nodeType;
typedef struct bufTypeTag { /* location of node */
struct bufTypeTag *next; /* next */
struct bufTypeTag *prev; /* previous */
bAdrType adr; /* on disk */
nodeType *p; /* in memory */
bool valid; /* true if buffer contents valid */
bool modified; /* true if buffer modified */
} bufType;
/* one node for each open handle */
typedef struct hNodeTag {
struct hNodeTag *prev; /* previous node */
struct hNodeTag *next; /* next node */
FILE *fp; /* idx file */
int keySize; /* key length */
bool dupKeys; /* true if duplicate keys */
int sectorSize; /* block size for idx records */
bCompType comp; /* pointer to compare routine */
bufType root; /* root of b-tree, room for 3 sets */
bufType bufList; /* head of buf list */
void *malloc1; /* malloc'd resources */
void *malloc2; /* malloc'd resources */
bufType gbuf; /* gather buffer, room for 3 sets */
bufType *curBuf; /* current location */
keyType *curKey; /* current key in current node */
unsigned int maxCt; /* minimum # keys in node */
int ks; /* sizeof key entry */
bAdrType nextFreeAdr; /* next free b-tree record address */
} hNode;
static hNode hList; /* list of hNodes */
static hNode *h; /* current hNode */
#define error(rc) lineError(__LINE__, rc)
static bErrType lineError(int lineno, bErrType rc) {
if (rc == bErrIO || rc == bErrMemory)
if (!bErrLineNo)
bErrLineNo = lineno;
return rc;
}
static bAdrType allocAdr(void) {
bAdrType adr;
adr = h->nextFreeAdr;
h->nextFreeAdr += h->sectorSize;
return adr;
}
static bErrType flush(bufType *buf) {
int len; /* number of bytes to write */
/* flush buffer to disk */
len = h->sectorSize;
if (buf->adr == 0) len *= 3; /* root */
if (fseek(h->fp, buf->adr, SEEK_SET)) return error(bErrIO);
if (fwrite(buf->p, len, 1, h->fp) != 1) return error(bErrIO);
buf->modified = false;
nDiskWrites++;
return bErrOk;
}
static bErrType flushAll(void) {
bErrType rc; /* return code */
bufType *buf; /* buffer */
if (h->root.modified)
if ((rc = flush(&h->root)) != 0) return rc;
buf = h->bufList.next;
while (buf != &h->bufList) {
if (buf->modified)
if ((rc = flush(buf)) != 0) return rc;
buf = buf->next;
}
}
static bErrType assignBuf(bAdrType adr, bufType **b) {
/* assign buf to adr */
bufType *buf; /* buffer */
bErrType rc; /* return code */
if (adr == 0) {
*b = &h->root;
return bErrOk;
}
/* search for buf with matching adr */
buf = h->bufList.next;
while (buf->next != &h->bufList) {
if (buf->valid && buf->adr == adr) break;
buf = buf->next;
}
/* either buf points to a match, or it's last one in list (LRR) */
if (buf->valid) {
if (buf->adr != adr) {
if (buf->modified) {
if ((rc = flush(buf)) != 0) return rc;
}
buf->adr = adr;
buf->valid = false;
}
} else {
buf->adr = adr;
}
/* remove from current position and place at front of list */
buf->next->prev = buf->prev;
buf->prev->next = buf->next;
buf->next = h->bufList.next;
buf->prev = &h->bufList;
buf->next->prev = buf;
buf->prev->next = buf;
*b = buf;
return bErrOk;
}
static bErrType writeDisk(bufType *buf) {
/* write buf to disk */
buf->valid = true;
buf->modified = true;
return bErrOk;
}
static bErrType readDisk(bAdrType adr, bufType **b) {
/* read data into buf */
int len;
bufType *buf; /* buffer */
bErrType rc; /* return code */
if ((rc = assignBuf(adr, &buf)) != 0) return rc;
if (!buf->valid) {
len = h->sectorSize;
if (adr == 0) len *= 3; /* root */
if (fseek(h->fp, adr, SEEK_SET)) return error(bErrIO);
if (fread(buf->p, len, 1, h->fp) != 1) return error(bErrIO);
buf->modified = false;
buf->valid = true;
nDiskReads++;
}
*b = buf;
return bErrOk;
}
typedef enum { MODE_FIRST, MODE_MATCH } modeEnum;
static int search(
bufType *buf,
void *key,
eAdrType rec,
keyType **mkey,
modeEnum mode) {
/*
* input:
* p pointer to node
* key key to find
* rec record address (dupkey only)
* output:
* k pointer to keyType info
* returns:
* CC_EQ key = mkey
* CC_LT key < mkey
* CC_GT key > mkey
*/
int cc; /* condition code */
int m; /* midpoint of search */
int lb; /* lower-bound of binary search */
int ub; /* upper-bound of binary search */
bool foundDup; /* true if found a duplicate key */
/* scan current node for key using binary search */
foundDup = false;
lb = 0;
ub = ct(buf) - 1;
while (lb <= ub) {
m = (lb + ub) / 2;
*mkey = fkey(buf) + ks(m);
cc = h->comp(key, key(*mkey));
if (cc < 0)
/* key less than key[m] */
ub = m - 1;
else if (cc > 0)
/* key greater than key[m] */
lb = m + 1;
else {
/* keys match */
if (h->dupKeys) {
switch (mode) {
case MODE_FIRST:
/* backtrack to first key */
ub = m - 1;
foundDup = true;
break;
case MODE_MATCH:
/* rec's must also match */
if (rec < rec(*mkey)) {
ub = m - 1;
cc = CC_LT;
} else if (rec > rec(*mkey)) {
lb = m + 1;
cc = CC_GT;
} else {
return CC_EQ;
}
break;
}
} else {
return cc;
}
}
}
if (ct(buf) == 0) {
/* empty list */
*mkey = fkey(buf);
return CC_LT;
}
if (h->dupKeys && (mode == MODE_FIRST) && foundDup) {
/* next key is first key in set of duplicates */
*mkey += ks(1);
return CC_EQ;
}
/* didn't find key */
return cc;
}
static bErrType scatterRoot(void) {
bufType *gbuf;
bufType *root;
/* scatter gbuf to root */
root = &h->root;
gbuf = &h->gbuf;
memcpy(fkey(root), fkey(gbuf), ks(ct(gbuf)));
childLT(fkey(root)) = childLT(fkey(gbuf));
ct(root) = ct(gbuf);
leaf(root) = leaf(gbuf);
return bErrOk;
}
static bErrType scatter(bufType *pbuf, keyType *pkey, int is, bufType **tmp) {
bufType *gbuf; /* gather buf */
keyType *gkey; /* gather buf key */
bErrType rc; /* return code */
int iu; /* number of tmp's used */
int k0Min; /* min #keys that can be mapped to tmp[0] */
int knMin; /* min #keys that can be mapped to tmp[1..3] */
int k0Max; /* max #keys that can be mapped to tmp[0] */
int knMax; /* max #keys that can be mapped to tmp[1..3] */
int sw; /* shift width */
int len; /* length of remainder of buf */
int base; /* base count distributed to tmps */
int extra; /* extra counts */
int ct;
int i;
/*
* input:
* pbuf parent buffer of gathered keys
* pkey where we insert a key if needed in parent
* is number of supplied tmps
* tmp array of tmp's to be used for scattering
* output:
* tmp array of tmp's used for scattering
*/
/* scatter gbuf to tmps, placing 3/4 max in each tmp */
gbuf = &h->gbuf;
gkey = fkey(gbuf);
ct = ct(gbuf);
/****************************************
* determine number of tmps to use (iu) *
****************************************/
iu = is;
/* determine limits */
if (leaf(gbuf)) {
/* minus 1 to allow for insertion */
k0Max= h->maxCt - 1;
knMax= h->maxCt - 1;
/* plus 1 to allow for deletion */
k0Min= (h->maxCt / 2) + 1;
knMin= (h->maxCt / 2) + 1;
} else {
/* can hold an extra gbuf key as it's translated to a LT pointer */
k0Max = h->maxCt - 1;
knMax = h->maxCt;
k0Min = (h->maxCt / 2) + 1;
knMin = ((h->maxCt+1) / 2) + 1;
}
/* calculate iu, number of tmps to use */
while(1) {
if (iu == 0 || ct > (k0Max + (iu-1)*knMax)) {
/* add a buffer */
if ((rc = assignBuf(allocAdr(), &tmp[iu])) != 0)
return rc;
/* update sequential links */
if (leaf(gbuf)) {
/* adjust sequential links */
if (iu == 0) {
/* no tmps supplied when splitting root for first time */
prev(tmp[0]) = 0;
next(tmp[0]) = 0;
} else {
prev(tmp[iu]) = tmp[iu-1]->adr;
next(tmp[iu]) = next(tmp[iu-1]);
next(tmp[iu-1]) = tmp[iu]->adr;
}
}
iu++;
nNodesIns++;
} else if (iu > 1 && ct < (k0Min + (iu-1)*knMin)) {
/* del a buffer */
iu--;
/* adjust sequential links */
if (leaf(gbuf) && tmp[iu-1]->adr) {
next(tmp[iu-1]) = next(tmp[iu]);
}
next(tmp[iu-1]) = next(tmp[iu]);
nNodesDel++;
} else {
break;
}
}
/* establish count for each tmp used */
base = ct / iu;
extra = ct % iu;
for (i = 0; i < iu; i++) {
int n;
n = base;
/* distribute extras, one at a time */
/* don't do to 1st node, as it may be internal and can't hold it */
if (i && extra) {
n++;
extra--;
}
ct(tmp[i]) = n;
}
/**************************************
* update sequential links and parent *
**************************************/
if (iu != is) {
/* link last node to next */
if (leaf(gbuf) && next(tmp[iu-1])) {
bufType *buf;
if ((rc = readDisk(next(tmp[iu-1]), &buf)) != 0) return rc;
prev(buf) = tmp[iu-1]->adr;
if ((rc = writeDisk(buf)) != 0) return rc;
}
/* shift keys in parent */
sw = ks(iu - is);
if (sw < 0) {
len = ks(ct(pbuf)) - (pkey - fkey(pbuf)) + sw;
memmove(pkey, pkey - sw, len);
} else {
len = ks(ct(pbuf)) - (pkey - fkey(pbuf));
memmove(pkey + sw, pkey, len);
}
/* don't count LT buffer for empty parent */
if (ct(pbuf))
ct(pbuf) += iu - is;
else
ct(pbuf) += iu - is - 1;
}
/*******************************
* distribute keys to children *
*******************************/
for (i = 0; i < iu; i++) {
/* update LT pointer and parent nodes */
if (leaf(gbuf)) {
/* update LT, tmp[i] */
childLT(fkey(tmp[i])) = 0;
/* update parent */
if (i == 0) {
childLT(pkey) = tmp[i]->adr;
} else {
memcpy(pkey, gkey, ks(1));
childGE(pkey) = tmp[i]->adr;
pkey += ks(1);
}
} else {
if (i == 0) {
/* update LT, tmp[0] */
childLT(fkey(tmp[i])) = childLT(gkey);
/* update LT, parent */
childLT(pkey) = tmp[i]->adr;
} else {
/* update LT, tmp[i] */
childLT(fkey(tmp[i])) = childGE(gkey);
/* update parent key */
memcpy(pkey, gkey, ks(1));
childGE(pkey) = tmp[i]->adr;
gkey += ks(1);
pkey += ks(1);
ct(tmp[i])--;
}
}
/* install keys, tmp[i] */
memcpy(fkey(tmp[i]), gkey, ks(ct(tmp[i])));
leaf(tmp[i]) = leaf(gbuf);
gkey += ks(ct(tmp[i]));
}
leaf(pbuf) = false;
/************************
* write modified nodes *
************************/
if ((rc = writeDisk(pbuf)) != 0) return rc;
for (i = 0; i < iu; i++)
if ((rc = writeDisk(tmp[i])) != 0) return rc;
return bErrOk;
}
static bErrType gatherRoot(void) {
bufType *gbuf;
bufType *root;
/* gather root to gbuf */
root = &h->root;
gbuf = &h->gbuf;
memcpy(p(gbuf), root->p, 3 * h->sectorSize);
leaf(gbuf) = leaf(root);
ct(root) = 0;
return bErrOk;
}
static bErrType gather(bufType *pbuf, keyType **pkey, bufType **tmp) {
bErrType rc; /* return code */
bufType *gbuf;
keyType *gkey;
/* find 3 adjacent buffers */
if (*pkey == lkey(pbuf))
*pkey -= ks(1);
if ((rc = readDisk(childLT(*pkey), &tmp[0])) != 0) return rc;
if ((rc = readDisk(childGE(*pkey), &tmp[1])) != 0) return rc;
if ((rc = readDisk(childGE(*pkey + ks(1)), &tmp[2])) != 0) return rc;
/* gather nodes to gbuf */
gbuf = &h->gbuf;
gkey = fkey(gbuf);
/* tmp[0] */
childLT(gkey) = childLT(fkey(tmp[0]));
memcpy(gkey, fkey(tmp[0]), ks(ct(tmp[0])));
gkey += ks(ct(tmp[0]));
ct(gbuf) = ct(tmp[0]);
/* tmp[1] */
if (!leaf(tmp[1])) {
memcpy(gkey, *pkey, ks(1));
childGE(gkey) = childLT(fkey(tmp[1]));
ct(gbuf)++;
gkey += ks(1);
}
memcpy(gkey, fkey(tmp[1]), ks(ct(tmp[1])));
gkey += ks(ct(tmp[1]));
ct(gbuf) += ct(tmp[1]);
/* tmp[2] */
if (!leaf(tmp[2])) {
memcpy(gkey, *pkey+ks(1), ks(1));
childGE(gkey) = childLT(fkey(tmp[2]));
ct(gbuf)++;
gkey += ks(1);
}
memcpy(gkey, fkey(tmp[2]), ks(ct(tmp[2])));
ct(gbuf) += ct(tmp[2]);
leaf(gbuf) = leaf(tmp[0]);
return bErrOk;
}
bErrType bOpen(bOpenType info, bHandleType *handle) {
bErrType rc; /* return code */
int bufCt; /* number of tmp buffers */
bufType *buf; /* buffer */
int maxCt; /* maximum number of keys in a node */
bufType *root;
int i;
nodeType *p;
if ((info.sectorSize < sizeof(hNode)) || (info.sectorSize % 4))
return bErrSectorSize;
/* determine sizes and offsets */
/* leaf/n, prev, next, [childLT,key,rec]... childGE */
/* ensure that there are at least 3 children/parent for gather/scatter */
maxCt = info.sectorSize - (sizeof(nodeType) - sizeof(keyType));
maxCt /= sizeof(bAdrType) + info.keySize + sizeof(eAdrType);
if (maxCt < 6) return bErrSectorSize;
/* copy parms to hNode */
if ((h = malloc(sizeof(hNode))) == NULL) return error(bErrMemory);
memset(h, 0, sizeof(hNode));
h->keySize = info.keySize;
h->dupKeys = info.dupKeys;
h->sectorSize = info.sectorSize;
h->comp = info.comp;
/* childLT, key, rec */
h->ks = sizeof(bAdrType) + h->keySize + sizeof(eAdrType);
h->maxCt = maxCt;
/* Allocate buflist.
* During insert/delete, need simultaneous access to 7 buffers:
* - 4 adjacent child bufs
* - 1 parent buf
* - 1 next sequential link
* - 1 lastGE
*/
bufCt = 7;
if ((h->malloc1 = malloc(bufCt * sizeof(bufType))) == NULL)
return error(bErrMemory);
buf = h->malloc1;
/*
* Allocate bufs.
* We need space for the following:
* - bufCt buffers, of size sectorSize
* - 1 buffer for root, of size 3*sectorSize
* - 1 buffer for gbuf, size 3*sectorsize + 2 extra keys
* to allow for LT pointers in last 2 nodes when gathering 3 full nodes
*/
if ((h->malloc2 = malloc((bufCt+6) * h->sectorSize + 2 * h->ks)) == NULL)
return error(bErrMemory);
p = h->malloc2;
/* initialize buflist */
h->bufList.next = buf;
h->bufList.prev = buf + (bufCt - 1);
for (i = 0; i < bufCt; i++) {
buf->next = buf + 1;
buf->prev = buf - 1;
buf->modified = false;
buf->valid = false;
buf->p = p;
p = (nodeType *)((char *)p + h->sectorSize);
buf++;
}
h->bufList.next->prev = &h->bufList;
h->bufList.prev->next = &h->bufList;
/* initialize root */
root = &h->root;
root->p = p;
p = (nodeType *)((char *)p + 3*h->sectorSize);
h->gbuf.p = p; /* done last to include extra 2 keys */
h->curBuf = NULL;
h->curKey = NULL;
/* initialize root */
if ((h->fp = fopen(info.iName, "r+b")) != NULL) {
/* open an existing database */
if ((rc = readDisk(0, &root)) != 0) return rc;
if (fseek(h->fp, 0, SEEK_END)) return error(bErrIO);
if ((h->nextFreeAdr = ftell(h->fp)) == -1) return error(bErrIO);
} else if ((h->fp = fopen(info.iName, "w+b")) != NULL) {
/* initialize root */
memset(root->p, 0, 3*h->sectorSize);
leaf(root) = 1;
h->nextFreeAdr = 3 * h->sectorSize;
} 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 ", __LINE__, rc);
exit(0);
}
key = 0x11;
if ((rc = bInsertKey(handle, &key, 0x300)) != bErrOk) {
printf("line %d: rc = %d ", __LINE__, rc);
exit(0);
}
bClose(handle);
printf("statistics: ");
printf(" maximum height: %8d ", maxHeight);
printf(" nodes inserted: %8d ", nNodesIns);
printf(" nodes deleted: %8d ", nNodesDel);
printf(" keys inserted: %8d ", nKeysIns);
printf(" keys deleted: %8d ", nKeysDel);
printf(" disk reads: %8d ", nDiskReads);
printf(" disk writes: %8d ", nDiskWrites);
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.