csbtree.h

CSLIB, a C++ database library.

/***********************************************************************

                      CSDB Library, Free Evaluation Version 2.2.0 
                                           Release: June 9th 1997 

       BTREE classes.

                                           Copyright(c) 1994-1997 
                                                          ComBits 
                                                  The Netherlands 
***********************************************************************/

#ifndef __CSBTREE_H
#define __CSBTREE_H

#include "cstbase.h"
#include "cscopton.h"



////////////////////////////////////////////////////////////////////////////
// The Class used by the BTREE to store its data.
// We can use TBASE or RBASE.
//

class BBASE: public TBASE {};
//#define BBASE TBASE

/////////////////////////////////////////////////////////////////////////////////
/////////////////////////// Btree POINTER. //////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////


typedef U32 BPOINT;


/////////////////////////////////////////////////////////////////////////////////
/////////////////////////// Functions for comparing keys. //////////////////////////
/////////////////////////////////////////////////////////////////////////////////


inline int cs_comp_bin(void *a,void *b,int len)
{
   return memcmp(a,b,len);
}

inline int cs_comp_int(void *a,void *b)
{
  if(*(int *)a < *(int *)b) return -1;
  if(*(int *)a > *(int *)b) return  1;
  return 0;
}

inline int cs_comp_cha(void *a,void *b)
{
  return ((int)*(S8 *)a)-((int)*(S8 *)b);
}

inline int cs_comp_lon(void *a,void *b)
{
  if(*(long *)a < *(long *)b) return -1;
  if(*(long *)a > *(long *)b) return  1;
  return 0;
}

inline int cs_comp_flo(void *a,void *b)
{
  if(*(float *)a < *(float *)b) return -1;
  if(*(float *)a > *(float *)b) return	1;
  return 0;
}


inline int cs_comp_dou(void *a,void *b)
{
  if(*(double *)a < *(double *)b) return -1;
  if(*(double *)a > *(double *)b) return  1;
  return 0;
}

inline int cs_comp_asc(void *a,void *b,int len)
{
   return pStrnicmp((csCHAR *)a,(csCHAR *)b,len);
}




/////////////////////////////////////////////////////////////////////////////////
/////////////////////////// Current Pointer structure. //////////////////////////
/////////////////////////////////////////////////////////////////////////////////


typedef struct
{
   int	  nr;	 // The current number in the block
   int	  mk_n;  // The current number in the frame
   BPOINT block; // The current block
   BPOINT mk_f;  // The current frame
} BTCP; 	 // BTree Current Pointer



/////////////////////////////////////////////////////////////////////////////////
/////////////////////////// Generic BTREE class. ////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////


class BTREE: public BBASE
{

   protected:

       typedef struct
       {
	  BPOINT rnr;	// .................right .........
	  BPOINT tr;	// This Record
	  BPOINT up;	// Up pointer
	  BPOINT lnr;	// Record number of left neighbour
	  U8	 nr;	// Number of keys
       } d_block;

       typedef struct
       {
	  BPOINT lnr;	// Record number of left neighbour (Previous)
	  BPOINT rnr;	// .................right ......... (Next)
	  U8	 nr;	// Number of data elements
       } m_block;



    protected:

      BPOINT root;	 // Root of the btree.
      BPOINT empt;	 // Empty block chain.
      BPOINT *paal;	 // PAth ALlocation.
      BPOINT *path;	 // Path from the root to the leave.
      BPOINT mk_empt;	 // mk_ Empty data frames.
      int    levels;	 // Number of levels in the btree, including DATA layer
      int    datlen;	 // Length of data field.
      int    keylen;	 // Length of key field.
      int    kdlen;	 // Length of key- and data field combined.
      int    kdmklen;	 // Length of key- + data field + mk.
      int    kplen;	 // Length of keyfield and BPOINT combined.
      int    pml;	 // Path Max Length.
      int    mulkey;	 // Multiple keys allowed.
      void   *tmp_key;	 // Storage for temporary keys.
      long   num_key;	 // Number of Keys in Btree.
      BPOINT curr_block; // The current block.
      int    curr_nr;	 // The current number in the block.
      BPOINT curr_mk_f;  // The current frame.
      int    curr_mk_n;  // The current number in the frame.


    protected:

    /////////////////////// Multiple Key Support //////////////////////
    //	mdf:	Multiple Data Frame

      int   nimdf;     // Number of data elements In a mdf.
      int   mkop;      // Number of Multiple data frames on a page.
      int   somdf;     // Size Of a mdf. (Number of bytes in a mdf.)
      int   mk_shift;
      int   mk_and;

      int   mk_oib_a;
      int   mk_oimdf_a;

      int   mk_oib(int n)	   { return mk_oib_a+n*somdf; }
      int   mk_oimdf(int n)	   { return mk_oimdf_a+n*datlen; }

      csCHAR *mk_p2cp(void *p,int n) { return (csCHAR *)p+mk_oib(n); }

      BPOINT &mk_n_mdf(void *p)   { return (((m_block *)p)->rnr); }
      BPOINT  mk_n_mdf(BPOINT b)  { return mk_n_mdf(mk_p2mdf(b)); }
      BPOINT &mk_n_mdfd(BPOINT b) { return mk_n_mdf(mk_p2mdfd(b)); }
      BPOINT &mk_p_mdf(void *p)   { return (((m_block *)p)->lnr); }
      BPOINT  mk_p_mdf(BPOINT b)  { return mk_p_mdf(mk_p2mdf(b)); }
      BPOINT &mk_p_mdfd(BPOINT b) { return mk_p_mdf(mk_p2mdfd(b)); }

      void   mk_connect(BPOINT l,BPOINT r)
	       { if(l) mk_n_mdfd(l)=r; if(r) mk_p_mdfd(r)=l; }
      void   mk_empty(BPOINT b);
      void   mk_new_page(void);

      BPOINT  mk_new_frame(void);
      BPOINT  mk_2mkp(BPOINT b,int i)	{ return ((b<<mk_shift)|i); }

      csCHAR  *mk_p2mdf(BPOINT b)  { return p2cp(b>>mk_shift)+mk_oib(b&mk_and);  }
      csCHAR  *mk_p2mdfd(BPOINT b) { return p2cpd(b>>mk_shift)+mk_oib(b&mk_and); }

      csCHAR  *mk_dataif(void *p,int i) { return (csCHAR *)p+mk_oimdf(i); }
      csCHAR  *mk_data_l(void *p)	{ return mk_dataif(p,mk_nr(p)); }
      csCHAR  *mk_search(BPOINT &b,void *dat, int &nr);
      csCHAR  *mk_insert(BPOINT &b,void *dat);

      int   mk_delet(BPOINT &b,void *dat);

      void  mk_free_chain(BPOINT b);
      void  mk_zap(void);
      void  mk_define(void);
      void  mk_close(void);
      void  mk_open(void);
      void  mk_last(BPOINT b)	 { curr_mk_n=mk_nr(mk_p2mdf(curr_mk_f=mk_p_mdf(b))); }
      void *mk_last_p(BPOINT b);

      U8    &mk_nr(void *p)	 { return (((m_block *)p)->nr); }


    /////////////////////// Accessing Header Block ////////////////////

	 U8 &DNR(void *p)  { return (((d_block *)(p))->nr);  }
     BPOINT &DLNR(void *p) { return (((d_block *)(p))->lnr); }
     BPOINT &DRNR(void *p) { return (((d_block *)(p))->rnr); }
     BPOINT &BTR(void *p)  { return (((d_block *)(p))->tr);  }

    /////////////////////// Splitting Data Block //////////////////////

      int   dmnk;      // Data Max Number of Keys
      int   dnbc;      // Data Number of Bytes Copied
      int   dsco;      // Data Source Copy Offset
      int   ddco;      // Data Destination Copy Offset
      U8    dnnr;      // Data New NumbeR; the higher keys
      U8    donr;      // Data Old NumbeR; the lower keys

    /////////////////////// Splitting Index Block //////////////////////

      int   imnk;      // Index Max Number of Keys
      int   inbc;      // Index Number of Bytes Copied
      int   isco;      // Index Source Copy Offset
      int   idco;      // Index Destination Copy Offset
      U8    innr;      // Index New NumbeR; the higher keys
      U8    ionr;      // Index Old NumbeR; the lower keys

      int a_oiib;      // Offset in indexblock calculation
      int b_oiib;

      int a_oidb;      // Offset in datablock calculation
      int b_oidb;

 protected:

     int  moving_min(BPOINT &b,int &n,int delta,void *&bp);
     int  moving_plus(BPOINT &b,int &n,int delta,void *&bp);

     int  moving_plus(void *&bp,int &n);
     int  moving_min(void *&bp,int &n);

     int  prev_u(int n,void *&key,void *&data);
     int  prev(int n,void *&bp);
     int  next(int n,void *&bp);
     int  next_u(int n,void *&key,void *&data);

    /////////////////////// Skipping fields  within a Block //////////////////
      csCHAR   *skfidb(void *p)      { return (((csCHAR *)p)+keylen); }
      BPOINT   *s2fidb(void *p)      { return (BPOINT *)(((csCHAR *)p)+kdlen); }
      csCHAR   *skfiib(void *p)      { return (((csCHAR *)p)+keylen); }
      csCHAR   *spfiib(void *p)      { return (((csCHAR *)p)+sizeof(BPOINT));  }
      csCHAR   *fkiib(void *p)	     { return (((csCHAR *)p)+sizeof(d_block)); }
      csCHAR   *lkiib(void *p)	     { return (((csCHAR *)p)+oiib(DNR(p)));    }
      csCHAR   *nkiib(void *p,int n) { return (csCHAR *)p+oiib(n); }

      csCHAR   *lkidb(void *p)	     { return (csCHAR *)p+oidb(DNR(p)); }
      csCHAR   *nkidb(void *p,int n) { return (csCHAR *)p+oidb(n);}
      csCHAR   *fkidb(void *p)	     { return (csCHAR *)p+sizeof(d_block); }

    ///////////////////////// DB Header ///////////////////////////////////
      virtual int read_header(void);
      virtual int write_header(void);


    /////////////////////// type of database ////////////////////////////////
      virtual int check_id(U32 id);
      virtual void set_id(void);

    /////////////////////// Copying /////////////////////////////////////////
      void  copy_dat(void *d,void *s)	      { memcpy(d,s,datlen); }
      void  copy_poi(void *d,BPOINT &s)       { *(BPOINT *)d=s; }
      virtual void copy_key(void *d,void *s)  { memcpy(d,s,keylen); }

    /////////////////////// Delete Aid //////////////////////////////////////
      void  delet(void *b,void *KeyPos,int KeyNr);

    /////////////////////// Create/Free Block //////////////////////////////////
      void  c_root(void *keyl,BPOINT l,void *keyr,BPOINT r);
      void  c_root(void *keyl,BPOINT l);
    csCHAR *c_block(void);
      void  f_block(void *p);