home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
rtsi.com
/
2014.01.www.rtsi.com.tar
/
www.rtsi.com
/
OS9
/
OSK
/
APPS
/
hl10osrc.lzh
/
Include
/
vBTree.h
< prev
next >
Wrap
Text File
|
1994-04-23
|
5KB
|
161 lines
/* -*- Mode: C -*- */
/* vBTree.h - virtual BTrees - a modification of the BTree class
* described in "C++, a guide for C programmers", by
* Sharam Hekmatpour, (c) 1990 by Prentice Hall of
* Australia Pty Ltd.
*
* Created by Robert Heller on Fri Dec 6 20:55:06 1991
*
* ------------------------------------------------------------------
* Home Libarian by Deepwoods Software
* Common Header Files
* ------------------------------------------------------------------
* Modification History:
* ------------------------------------------------------------------
* Contents:
* ------------------------------------------------------------------
*
*
* Copyright (c) 1991,1992 by Robert heller (D/B/A Deepwoods Software)
* All Rights Reserved
*
*/
#ifndef _VBTREE_
#define _VBTREE_
#include <common.h>
#include <vm.h>
// This class implements a Library Card Catalog as a group a four
// (virtual) BTrees of Order 10.
// The nodes of the BTrees are handled using the virtual memory management
// of the PageFile class.
class vBTree : public PageFile {
OpenStatus openstat; // open status
HomeBlock homeblock; // home (header) block
Boolean homedirty; // has the home block been modified?
Item* buf; // scratch buffer
DiskPage LastSearchPage; // Last page searched. Set by SearchAux,
// used and updated by SearchAgain
Key LastSearchKey; // Last search key.
int LastSearchIdx; // Last search index
LSType LastSearchType; // Last search type
ErrFun errFun; // Error hander function
DiskPage NewPage (); // Get a new empty page
void FreePage (DiskPage page); // Free up a page
// Searching functions
Boolean SearchAux (DiskPage dtree,Key key,CoreItem* item);
Boolean SearchAgain (CoreItem* item);
Boolean BinarySearch (Page* node,Key key,int* idx);
// Insertion function
Item* InsertAux (Item* item,DiskPage dnode);
// Deletion functions
void DeleteAux1 (Key key,DiskPage dnode,Boolean* underflow);
void DeleteAux2 (DiskPage dparent,DiskPage dnode,int idx,
Boolean* underflow);
void Underflow (DiskPage dnode,DiskPage dchild,int idx,
Boolean* underflow);
// Parentage adjustment
void AdjustParent (DiskPage dparent);
// Item vector hacking
int CopyItems (Item* src,Item* dest,int count);
int InsertItem (Item* item,Item* items,int idx,int size);
int DeleteItem (Item* items,int idx,int size);
// Raw tree print function
void PrintAux (DiskPage node,int margin);
// Page counter
int CountPagesAux (DiskPage node);
// Key compare function
int CompareKeys (Key keypat, Key key);
// Tree traversal function
void TravAux (DiskPage node,TravFunc tfun,int level);
public:
OpenStatus OpenStat() {return openstat;}
// Error function reference operator
ErrFun& ErrorFun () {return errFun;}
// Error handler
void Error (ErrKind err,const char* msg);
// Open file function
OpenStatus open (char *filename,OpenMode mode = ReadOnly,
int nfree = MaxNumFree / 10);
// Constructors
vBTree ();
vBTree (char *filename,OpenMode mode = ReadOnly,
int nfree = MaxNumFree / 10);
// Destructor
~vBTree ();
// Search Id tree
Boolean SearchId (Key key,CoreItem* item)
{LastSearchType = id;
LastSearchIdx = -1;
return(SearchAux(homeblock.IdRoot,key,
item));}
Boolean SearchIdAgain (CoreItem* item)
{return(LastSearchType == id &&
SearchAgain(item));}
// Search Title tree
Boolean SearchTitle (Key key,CoreItem* item)
{LastSearchType = title;
LastSearchIdx = -1;
return(SearchAux(homeblock.TitleRoot,
key,item));}
Boolean SearchTitleAgain (CoreItem* item)
{return(LastSearchType == title &&
SearchAgain(item));}
// Search Author tree
Boolean SearchAuthor (Key key,CoreItem* item)
{LastSearchType = author;
LastSearchIdx = -1;
return(SearchAux(homeblock.AuthorRoot,
key,item));}
Boolean SearchAuthorAgain (CoreItem* item)
{return(LastSearchType == author &&
SearchAgain(item));}
// Search Subject tree
Boolean SearchSubj (Key key,CoreItem* item)
{LastSearchType = subj;
LastSearchIdx = -1;
return(SearchAux(homeblock.SubjRoot,
key,item));}
Boolean SearchSubjAgain (CoreItem* item)
{return(LastSearchType == subj &&
SearchAgain(item));}
// Insertion
DiskRecord InsertId (Key key,Record* newdata);
DiskRecord InsertTitle (Key key,Record* newdata);
DiskRecord InsertAuthor (Key key,Record* newdata);
DiskRecord InsertSubj (Key key,Record* newdata);
// Deletion
void DeleteId (Key key);
void DeleteTitle (Key key);
void DeleteAuthor (Key key);
void DeleteSubj (Key key);
// Raw printing
void Print (int margin=0)
{
PrintAux(homeblock.IdRoot,margin);
PrintAux(homeblock.TitleRoot,margin);
PrintAux(homeblock.AuthorRoot,margin);
PrintAux(homeblock.SubjRoot,margin);
}
// Page counter
int CountPages ()
{
return (CountPagesAux(homeblock.IdRoot) +
CountPagesAux(homeblock.TitleRoot) +
CountPagesAux(homeblock.AuthorRoot) +
CountPagesAux(homeblock.SubjRoot));
}
// Tree traversal
void TraverseId (TravFunc tfun)
{TravAux(homeblock.IdRoot,tfun,0);}
void TraverseAuthor (TravFunc tfun)
{TravAux(homeblock.AuthorRoot,tfun,0);}
void TraverseTitle (TravFunc tfun)
{TravAux(homeblock.TitleRoot,tfun,0);}
void TraverseSubj (TravFunc tfun)
{TravAux(homeblock.SubjRoot,tfun,0);}
};
#endif