// ------------------------------- //
// -------- Start of File -------- //
// ------------------------------- //
// ----------------------------------------------------------- // 
// C++ Source Code File Name: btree.cpp 
// Compiler Used: MSVC40, DJGPP 2.7.2.1, GCC 2.7.2.1, HP CPP 10.24
// Produced By: Doug Gaer   
// File Creation Date: 02/12/1997 
// Date Last Modified: 03/15/1999
// Copyright (c) 1997 Douglas M. Gaer
// ----------------------------------------------------------- // 
// ------------- Program Description and Details ------------- // 
// ----------------------------------------------------------- // 
/*
The VBD C++ classes are copyright (c) 1997, by Douglas M. Gaer.
All those who put this code or its derivatives in a commercial
product MUST mention this copyright in their documentation for
users of the products in which this code or its derivative
classes are used. Otherwise, you have the freedom to redistribute
verbatim copies of this source code, adapt it to your specific
needs, or improve the code and release your improvements to the
public provided that the modified files carry prominent notices
stating that you changed the files and the date of any change.

THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT WARRANTY OF ANY KIND.
THE ENTIRE RISK OF THE QUALITY AND PERFORMANCE OF THIS SOFTWARE
IS WITH YOU. SHOULD ANY ELEMENT OF THIS SOFTWARE PROVE DEFECTIVE,
YOU WILL ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR, OR
CORRECTION.

Balanced multi-way file-base tree class used to create
file-based objects that reside on disk.
*/
// ----------------------------------------------------------- // 
#include <string.h>
#include "btree.h"

int Btree::Connect(VBDFilePtr &fptr, int create, FAU bha)
// Connect to an already open file. If create is 1, 
// creating a new btree (but not a new file.)
// Returns true if successful.
{
  f = fptr; bh_addr = bha;
  cache.Connect(f);
  if (create) {
     new(root) Mnode;
     bh.root_addr = root;
     bh.height = 1;
     bh.num_entries = 0;
     bh.num_nodes = 1;
     bh.order = NBR;
     WriteHdr();
  }
  else {
     ReadHdr();
     root = bh.root_addr;
  }
  if (f->IsOK()) return 1; else return 0;
}

void Btree::Disconnect()
// Disconnects the btree from the file.
{
  if (f) {
     WriteHdr();       
     root.Release();     // So there are no dangling ptrs
     cache.Disconnect(); // Disconnect cache from the file
     f = 0;              // And with the btree
  }
}

int Btree::Create(char *FName, FAU bha)
// Creates a new file to hold the btree. Disconnects from any 
// file that it may be connected to first. Returns true if successful.
{
  Disconnect();
  VBDFilePtr tmp(new VBDFile);
    VBDFilePtr nul = 0; // Used to satisfy overloaded == in RefCount class 
  if (tmp == nul) return 0;
  tmp->Create(FName, sizeof(BtreeHeader));
  if (!tmp->IsOK()) return 0;
  return Connect(tmp, 1, bha);
}

int Btree::Open(char *FName, VBDFile::AccessMode mode, FAU bha)
// Opens an existing file to hold the btree. Disconnect
// from any file that we may be connected to first.
// Returns true if successful.
{
  Disconnect();
  VBDFilePtr tmp(new VBDFile);
  VBDFilePtr nul = 0; // Used to satisfy overloaded == in RefCount class 
  if (tmp == nul) return 0;
  tmp->Open(FName, mode);
  if (!tmp->IsOK()) return 0;
  return Connect(tmp, 0, bha);
}

void Btree::WriteHdr()
{
  if (!f->ReadOnly())
     f->Write(&bh, sizeof(BtreeHeader), bh_addr);
}

void Btree::ReadHdr()
{
  f->Read(&bh, sizeof(BtreeHeader), bh_addr);
}

void Btree::Flush(int clear)
// Flush all buffers to disk
{
  if (f->IsOK()) {
     // When flushing the cache in read-only mode, no data
     // is actually written. However, Flush() is called 
     // anyway to check for dangling cache pointers.
     cache.Flush(clear);
     if (f->ReadyForWriting()) {
        WriteHdr();
        f->Flush();
     }
  }
}

int Btree::Search(EntryKey &e)
// Search the tree for the first node having a matching
// entry (the keys must match). If found, the key
// field of e is filled in. Returns true if successful.
{
  // Ensure that the in memory buffers and the file data
  // stay in sync during multiple file access.
  TestTree();
  
  CachePointer t(root);
  int rv, posn;

  while((__LWORD__)t) { 
    rv = t->Search(e, posn); // Searching node t
    if (rv == 0) {           // Found a match
       e = t->entry[posn];
       return 1;
    }
    t = t->Branch(posn);     // No match, keep walking
  }

  return 0;
}

int Btree::Search(char *key)
// Search the tree for the first node having a matching
// entry (the keys must match). If found, the key
// field of e is filled in. Returns true if successful.
{
  EntryKey e(key);
  int rv = Search(e);
  return rv;
}

int Btree::FullSearch(char *key, FAU object_address, FAU class_id)
{
  EntryKey e(key, object_address, class_id);
  int rv = FullSearch(e);
  return rv;
}
  
int Btree::FullSearch(const EntryKey &e)
// Like Search(), except the key, object address, and class ID must match.
// Returns true if successful.
{
  // Ensure that the in memory buffers and the file data
  // stay in sync during multiple file access.
  TestTree();

  CachePointer t(root);
  int rv, posn;

  while((__LWORD__)t) {
    rv = t->FullSearch(e, posn);  // Searching node t
    if (rv == 0) {                // Found a full match
       return 1;
    }
    t = t->Branch(posn);          // No match, keep walking
  }

  return 0;
}

int Btree::Insert(EntryKey &e, CachePointer t)
// Recursive function that tries to insert entry e into subtree t.
// Returns true, __DUPLKEY__, __ALLOCERR__, or __NODE_OVERFLOW__. 
// If __NODE_OVERFLOW__, then e becomes the median_entry to pass 
// back to t's parent.
{
  int rv, posn;

  if ((__LWORD__)t == 0) {
     // Went beyond the leaves. Pretend that it overflowed
     e.right = 0;
     return __NODE_OVERFLOW__;
  }

  // Search the node t. If entry found, send back duplicate key error
  rv = t->FullSearch(e, posn);
  if (rv == 0) return __DUPLKEY__;

  // Entry not found, walk down to the appropriate leaf to store entry.
  CachePointer child(t);
  child = t->Branch(posn);
  t.Release(); // Prevents cache from filling up
  rv = Insert(e, child);
  
  // Back from recursion, see if we have an overflow
  child.Release(); // Prevents cache from filling up
  if (rv != __NODE_OVERFLOW__) return rv;

  // It has overflowed the node below.
  // Try to insert the entry e (now the median) into node t.

  posn++; // Move to the appropriate entry for insertion

  if (!t->IsFull()) { // Simply add t to node t
     t->InsEntryKey(e, posn);
     t->SetDirty();
     return 1;
  }
  else { // Need to split node t.

    // Create new node to be the right node. t will be the left node.
    CachePointer r(t);
    new(r) Mnode;
    if ((__LWORD__)r == 0) return __ALLOCERR__;
    bh.num_nodes++;

    // Move roughly half the nodes to the right node. If inserting
    // entry into left node, need to move the split position back
    // one, so that when the median is taken, the split node will have
    // enough entries.
    int split_posn = NBR/2;
    if (posn < split_posn) split_posn--;
    t->Split(*r, split_posn);
    t->SetDirty();

    // Figure out where entry e should go
    if (posn > split_posn) { // e goes to the right node
      // First entry of right node is the median
      EntryKey median_entry = r->entry[0]; 
      r->DelEntryKey(0);
      // Insert e into right spot
      r->InsEntryKey(e, posn-split_posn-1);
      e = median_entry; // For passing up the tree
    }
    else if (posn < split_posn) { // e goes to the left node
       t->InsEntryKey(e, posn);
       t->SetDirty();
       e = r->entry[0]; // Get median from the right
       r->DelEntryKey(0);
    }

    // At this point, e is median entry to add to parent. 
    // Record what e's right pointer is going to be.
    r->left = e.right;
    e.right = r;

    return __NODE_OVERFLOW__; // The node was split
  }
}

int Btree::Add(char *key, FAU object_address, FAU class_id, int flush)
// Creates a new entry key, and attempts to add the entry to
// the tree. Returns true, __DUPLKEY__, or __ALLOCERR__.
{
  EntryKey e(key, object_address, class_id);
  return Add(e, flush);
}

int Btree::Add(EntryKey &e, int flush)
// Creates a new entry key, and attempts to add the entry to
// the tree. Returns true, __DUPLKEY__, or __ALLOCERR__.
{
  int rv = Insert(e, root);
  if  (rv == __NODE_OVERFLOW__) { // Need to grow a new root
    CachePointer old_root(root);
    new(root) Mnode;
    if ((__LWORD__)root == 0) return __ALLOCERR__;
    bh.num_nodes++; bh.height++;
    bh.root_addr = root;
    root->left = old_root;
    root->InsEntryKey(e, 0);
    rv = 1;
  }
  if (rv == 1)  bh.num_entries++;
  
  // 10/08/1998: Ensure that the Btree file header stays in sync
  // during multiple file access.
  if(flush) {
    WriteHdr();
    Flush();
  }

  return rv;
}

int Btree::Remove(char *key, FAU object_address, FAU class_id, int flush)
// Deletes entry key from the tree. Returns true if successful.
// Returns false if no entry is found.
{
  EntryKey e(key, object_address, class_id);
  return Remove(e, flush);
}

int Btree::Remove(EntryKey &e, int flush)
// Deletes entry key from the tree. Returns true if successful.
// Returns false if no entry is found.
{
  int rv = Delete(e, root);

  // Found the entry
  if (rv == 1 && root->IsEmpty() && bh.height > 1)  {
     // Finish last merging operation which shortens the tree.
    CachePointer p = root;
    root = root->Branch(-1);
    bh.root_addr = root;
    bh.num_nodes--; bh.height--;
    p.Delete();
  }

  // 10/08/1998: Ensure that the Btree file header stays in sync
  // during multiple file access.
  if(flush) {
    WriteHdr();
    Flush();
  }
  
  return rv;
}

int Btree::Delete(EntryKey &e, CachePointer p)
// Recursive function that deletes entry e from the subtree
// with root p. Returns true if successful. Returns false
// if no entry is found
{
  CachePointer t(p), s(p);
  EntryKey se; // Must be here or compiler generates the wrong code
  int rv, posn, sr;

  sr = p->FullSearch(e, posn); // Search node p
  t = p->Branch(posn);         // Get ready to walk down the tree

  if (sr == 0) {
     // p has entry to delete. Replace the entry with its
     // successor, if there is one.
     if ((__LWORD__)t) {
        s = t;
        while(s->Branch(-1)) s = s->Branch(-1);
        p->entry[posn] = s->entry[0];
        p->Branch(posn) = t; // Restore the branch
        p->SetDirty();       // Set dirty bit
        // Now, using recursion, delete the successor entry
        // Release the cache pointers in use, to keep cache from
        // filling up during the recursion, and to prevent
        // dangling pointer exceptions
        p.Release();
        se = s->entry[0];
        s.Release();
        if (Delete(se, t) != 1)
#ifdef CPP_EXCEPTIONS
	  throw CAssertError();
#else
	  Error->SignalException(EHandler::AssertError);
#endif
     }
     else { // At a leaf
        p->DelEntryKey(posn);
        p->SetDirty();
        bh.num_entries--;
     }
     rv = 1;
  }
  else {
     if ((__LWORD__)t) {
        // Walk down the tree, keep looking for entry
        p.Release(); // Keep cache from filling up on recursive call
        rv = Delete(e, t);
     }
     else return 0; // Could not find entry
  }

  if (rv == 1 && (__LWORD__)t && t->IsPoor()) {
     // The node below p doesn't have enough entries. Need to
     // move some entries to it and thereby restore the balance.
     t.Release(); // To prevent dangling ptrs
     RestoreBalance(p, posn);
  }

  return rv;
}

void Btree::RestoreBalance(CachePointer p, int posn)
// Node down the branch at position posn in node p has one too
// few entries. Give it an entry from either its left or right
// sibling, or merge the node with a sibling.
{
  CachePointer t(p);
  if (posn == -1) {
     // No left sibling, trying the right sibling
     t = p->Branch(0);
     if (t->IsPlentiful()) { // Try to borrow from the right
        RotateLeft(p, 0);    
     }
     else { // Right sibling has no spare entries.
       t.Release(); // To prevent dangling ptr errors
       Merge(p, 0); // Merge with right node and parent entry
     }
  }
  else if (posn == p->LastPosn()) {
     // No right sibling, trying the left sibling
     t = p->Branch(posn-1);
     if (t->IsPlentiful()) {  // Trying to borrow from the left
        RotateRight(p, posn); 
     }
     else { // Left sibling has no spare entries.
        t.Release();    // To prevent dangling ptr errors
        Merge(p, posn); // Merge with left node and parent entry
     }
  }
  else {
    // There are both left and right siblings
    t = p->Branch(posn-1);
    if (t->IsPlentiful()) {  // Try to borrow from the left
       RotateRight(p, posn); 
    }
    else { 
       t = p->Branch(posn+1);
       if (t->IsPlentiful()) {   // Can we borrow from the right?
          RotateLeft(p, posn+1); // Do so.
       }
       else {
          // Neither the left or right sibling has spare entries.
          // Merge arbitrarily with the left node.
          t.Release();    // To prevent dangling ptr errors
          Merge(p, posn); // Merging with the left
       }
    }
  }
}

void Btree::RotateRight(CachePointer p, int posn)
// Does a "right rotation" using the entry at node p,
// position posn as the pivot point. Assumes p is not
// a leaf and that there is a left and right child.
// Also assumes right child isn't full, and that p and
// left child aren't empty.
{
  CachePointer l(p), r(p);
  r = p->Branch(posn);   // Right child of p
  l = p->Branch(posn-1); // Left child of p

  // Move entry from parent p into rightmost entry of right node.
  // This entry will have the old left branch of right node. (The
  // left branch will be updated later.)
  p->Branch(posn) = r->left;
  p->SetDirty();
  r->InsEntryKey(p->entry[posn], 0);
  r->SetDirty();

  // Now, move rightmost entry of the left node into p. This
  // entry's branch becomes the right node's left pointer.
  // Be sure to point entry to right node.
  int last_posn = l->LastPosn();
  r->left = l->Branch(last_posn);
  r->SetDirty();
  l->Branch(last_posn) = r;
  l->SetDirty();
  p->entry[posn] = l->entry[last_posn];
  p->SetDirty();
  l->DelEntryKey(last_posn);
  l->SetDirty();
}

void Btree::RotateLeft(CachePointer p, int posn)
// Does a "left rotation" using the entry at node p,
// position posn as the pivot point. Assumes p is not
// a leaf and that there is a left and right child.
// Also assumes left child isn't full, and that p and
// right child aren't empty.
{
  CachePointer l(p), r(p);
  r = p->Branch(posn);   // Right child of p
  l = p->Branch(posn-1); // Left child of p

  // Move entry from parent p into leftmost entry of left node.
  // This entry gets the left pointer of the right node
  p->Branch(posn) = r->left;
  p->SetDirty();
  l->Cat(p->entry[posn]);   l->SetDirty();

  // Now, move rightmost entry of the right node into p. Make
  // sure this entry points to the right node. Also, we have
  // a new left branch of the right node.
  r->left = r->Branch(0);  
  r->Branch(0) = r;
  r->SetDirty();
  p->entry[posn] = r->entry[0];
  p->SetDirty();
  r->DelEntryKey(0);
  r->SetDirty();
}

void Btree::Merge(CachePointer p, int posn)
// Merges the node on the branch left of the entry at position
// posn of node p, with the entry of p and the node on the 
// branch to the right of the entry of p. Assumes posn in range.
{
  CachePointer l(p), r(p); // Pointers to left and right children
  r = p->Branch(posn);     // Right child of p
  l = p->Branch(posn-1);   // Left child of p

  // (1) Fixup entry of p to point to left branch of r
  // (2) Insert this into leftmost entry of l
  // (3) Add all of r's entries
  // (4) Delete entry from p, then delete r

  p->Branch(posn) = r->left;
  p->SetDirty();
  l->Cat(p->entry[posn]);
  l->SetDirty();
  l->Cat(*r); l->SetDirty();
  p->DelEntryKey(posn);
  p->SetDirty();
  r.Delete();
  bh.num_nodes--;
}

void Btree::ReInit(int flush)
// Reconnect the cache and the Btree header to ensure that the
// memory buffers and the file data stay in sync during multiple
// file access and multiple instances of the same application. 
// If the flush variable is true, the cache and the file buffers
// will be flushed to disk before reconnecting the cache.
{
  if(flush) Flush();
  root.Release(); // Release the root to prevent dangling ptrs
  cache.Disconnect(); 
  cache.Connect(f);   
  ReadHdr();          
  root = bh.root_addr; 
}

int Btree::TestTree()
// This function is used to ensure that the memory buffers
// and the file data stay in sync during multiple file access.
{
  int errors = 0;
  BtreeHeader fh;

  if(fh.root_addr != bh.root_addr) {
    ReInit();
    errors++;
  }

  if(fh.order != bh.order) {
    ReInit();
    errors++;
  }

  if(fh.num_entries != bh.num_entries) {
    ReInit();
    errors++;
  }

  if(fh.num_nodes != bh.num_nodes) {
    ReInit();
    errors++;
  }
  
  if(fh.height != bh.height) {
    ReInit();
    errors++;
  }

  return errors;
}
// ----------------------------------------------------------- //
// ------------------------------- //
// --------- End of File --------- //
// ------------------------------- //
