home *** CD-ROM | disk | FTP | other *** search
/ Resource for Source: C/C++ / Resource for Source - C-C++.iso / misc_src / cslib16b / include / csbtree.h < prev    next >
Encoding:
C/C++ Source or Header  |  1995-11-01  |  17.2 KB  |  466 lines
  1.  
  2. /***********************************************************************
  3.  
  4.                                       CSDB Library, Version 1.6.b 
  5.                                          Released: March 2nd 1995 
  6.  
  7.        BTREE classes.
  8.  
  9.                                            Copyright(c) 1994,1995 
  10.                                                            Combis 
  11.                                                   The Netherlands 
  12. ***********************************************************************/
  13.  
  14. #ifndef __CSBTREE_H
  15. #define __CSBTREE_H
  16.  
  17.  
  18. #ifndef __CSTBASE_H
  19. #include "cstbase.h"
  20. #endif
  21.  
  22.  
  23. #pragma warn -sig
  24.  
  25. /////////////////////////////////////////////////////////////////////////////////
  26.  
  27.  
  28. typedef U32 BPOINT;
  29.  
  30. class BTREE: public TBASE
  31. {
  32.  
  33.    protected:
  34.  
  35.  
  36.        typedef struct
  37.        {
  38.       BPOINT up;    // Up pointer
  39.       U8     nr;    // Number of keys
  40.       BPOINT tr;    // This Record
  41.       BPOINT lnr;    // Record number of left neighbour
  42.       BPOINT rnr;    // .................right .........
  43.        } d_block;
  44.  
  45.        typedef struct
  46.        {
  47.       U8     nr;    // Number of data elements
  48.       BPOINT lnr;    // Record number of left neighbour (Previous)
  49.       BPOINT rnr;    // .................right ......... (Next)
  50.        } m_block;
  51.  
  52.  
  53.     protected:
  54.  
  55.       BPOINT root;     // Points to the root of the btree
  56.       BPOINT empt;     // Empty block chain
  57.       BPOINT *paal;     // PAth ALlocation
  58.       BPOINT *path;     // Path from the root to the leave
  59.       BPOINT mk_empt;     // mk_ Empty data frames.
  60.       int    levels;     // Number of levels in the btree, including DATA layer
  61.       int    datlen;     // Length of data field
  62.       int    keylen;     // Length of key field
  63.       int    kdlen;     // Length of key- and data field combined.
  64.       int    kdmklen;     // Length of key- and data field and mk combined.
  65.       int    kplen;     // Length of keyfield and BPOINT combined.
  66.       int    pml;     // Path Max Length
  67.       int    mulkey;     // Multiple keys allowed.
  68.       void   *tmp_key;     // Storage for temporary keys
  69.       long   num_key;     // Number of Keys in Btree.
  70.       BPOINT curr_block; // The current block
  71.       int    curr_nr;     // The current number in the block
  72.       BPOINT curr_mk_f;  // The current frame
  73.       int    curr_mk_n;  // The current number in the frame
  74.  
  75.  
  76.     protected:
  77.  
  78.     /////////////////////// Multiple Key Support //////////////////////
  79.     //    mdf:    Multiple Data Frame
  80.  
  81.       int   nimdf;     // Number of data elements In a mdf.
  82.       int   mkop;      // Number of Multiple data frames on a page.
  83.       int   somdf;     // Size Of a mdf. (Number of bytes in a mdf.)
  84.       int   mk_shift;
  85.       int   mk_and;
  86.  
  87.       int   mk_oib_a;
  88.       int   mk_oimdf_a;
  89.  
  90.       int   mk_oib(int n)       { return mk_oib_a+n*somdf; }
  91.       int   mk_oimdf(int n)       { return mk_oimdf_a+n*datlen; }
  92.  
  93.       CSCHAR *mk_p2cp(void *p,int n) { return (CSCHAR *)p+mk_oib(n); }
  94.  
  95.       BPOINT &mk_n_mdf(void *p)   { return (((m_block *)p)->rnr); }
  96.       BPOINT  mk_n_mdf(BPOINT b)  { return mk_n_mdf(mk_p2mdf(b)); }
  97.       BPOINT &mk_n_mdfd(BPOINT b) { return mk_n_mdf(mk_p2mdfd(b)); }
  98.       BPOINT &mk_p_mdf(void *p)   { return (((m_block *)p)->lnr); }
  99.       BPOINT  mk_p_mdf(BPOINT b)  { return mk_p_mdf(mk_p2mdf(b)); }
  100.       BPOINT &mk_p_mdfd(BPOINT b) { return mk_p_mdf(mk_p2mdfd(b)); }
  101.  
  102.       void   mk_connect(BPOINT l,BPOINT r) { if(l) mk_n_mdfd(l)=r; if(r) mk_p_mdfd(r)=l; }
  103.       void   mk_empty(BPOINT b);
  104.       void   mk_new_page(void);
  105.  
  106.       BPOINT mk_new_frame(void);
  107.       BPOINT mk_2mkp(BPOINT b,int i) { return ((b<<mk_shift)|i); }
  108.  
  109.       CSCHAR  *mk_p2mdf(BPOINT b)  { return p2cp(b>>mk_shift)+mk_oib(b&mk_and);  }
  110.       CSCHAR  *mk_p2mdfd(BPOINT b) { return p2cpd(b>>mk_shift)+mk_oib(b&mk_and); }
  111.  
  112.       CSCHAR  *mk_dataif(void *p,int i) { return (CSCHAR *)p+mk_oimdf(i); }
  113.  
  114.       CSCHAR  *mk_data_l(void *p)    { return mk_dataif(p,mk_nr(p)); }
  115.       CSCHAR  *mk_search(BPOINT &b,void *dat, int &nr);
  116.       CSCHAR  *mk_insert(BPOINT &b,void *dat);
  117.  
  118.       int   mk_delet(BPOINT &b,void *dat);
  119.  
  120.       void  mk_free_chain(BPOINT b);
  121.       void  mk_zap(void);
  122.       void  mk_define(void)     { set_nill(head->cl.BTREE.btr_mk_emp); }
  123.       void  mk_close(void)     { head->cl.BTREE.btr_mk_emp=mk_empt;    }
  124.       void  mk_open(void);
  125.       void  mk_last(BPOINT b)     { curr_mk_n=mk_nr(mk_p2mdf(curr_mk_f=mk_p_mdf(b))); }
  126.       void *mk_last_p(BPOINT b);
  127.  
  128.       U8    &mk_nr(void *p)   { return (((m_block *)p)->nr); }
  129.  
  130.  
  131.     /////////////////////// Accessing Header Block ////////////////////
  132.  
  133.      U8 &DNR(void *p)  { return (((d_block *)(p))->nr);  }
  134.      BPOINT &DLNR(void *p) { return (((d_block *)(p))->lnr); }
  135.      BPOINT &DRNR(void *p) { return (((d_block *)(p))->rnr); }
  136.      BPOINT &BTR(void *p)  { return (((d_block *)(p))->tr);  }
  137.  
  138.     /////////////////////// Splitting Data Block //////////////////////
  139.  
  140.       int   dmnk;      // Data Max Number of Keys
  141.       int   dnbc;      // Data Number of Bytes Copied
  142.       int   dsco;      // Data Source Copy Offset
  143.       int   ddco;      // Data Destination Copy Offset
  144.       U8    dnnr;      // Data New NumbeR; the higher keys
  145.       U8    donr;      // Data Old NumbeR; the lower keys
  146.  
  147.     /////////////////////// Splitting Index Block //////////////////////
  148.  
  149.       int   imnk;      // Index Max Number of Keys
  150.       int   inbc;      // Index Number of Bytes Copied
  151.       int   isco;      // Index Source Copy Offset
  152.       int   idco;      // Index Destination Copy Offset
  153.       U8    innr;      // Index New NumbeR; the higher keys
  154.       U8    ionr;      // Index Old NumbeR; the lower keys
  155.  
  156.       int a_oiib;      // Offset in indexblock calculation
  157.       int b_oiib;
  158.  
  159.       int a_oidb;      // Offset in datablock calculation
  160.       int b_oidb;
  161.  
  162.  protected:
  163.  
  164.      int  moving_min(BPOINT &b,int &n,int delta,void *&bp);
  165.      int  moving_plus(BPOINT &b,int &n,int delta,void *&bp);
  166.  
  167.      int  moving_plus(void *&bp,int &n);
  168.      int  moving_min(void *&bp,int &n);
  169.  
  170.      int  prev_u(int n,void *&key,void *&data);
  171.      int  prev(int n,void *&bp);
  172.      int  next(int n,void *&bp);
  173.      int  next_u(int n,void *&key,void *&data);
  174.  
  175.     /////////////////////// Skipping fields  within a Block //////////////////
  176.       CSCHAR   *skfidb(void *p)      { return (((CSCHAR *)p)+keylen); }
  177.       BPOINT   *s2fidb(void *p)      { return (BPOINT *)(((CSCHAR *)p)+kdlen); }
  178.       CSCHAR   *skfiib(void *p)      { return (((CSCHAR *)p)+keylen); }
  179.       CSCHAR   *spfiib(void *p)      { return (((CSCHAR *)p)+sizeof(BPOINT));  }
  180.       CSCHAR   *fkiib(void *p)         { return (((CSCHAR *)p)+sizeof(d_block)); }
  181.       CSCHAR   *lkiib(void *p)         { return (((CSCHAR *)p)+oiib(DNR(p)));    }
  182.       CSCHAR   *nkiib(void *p,int n) { return (CSCHAR *)p+oiib(n); }
  183.  
  184.       CSCHAR   *lkidb(void *p)         { return (CSCHAR *)p+oidb(DNR(p)); }
  185.       CSCHAR   *nkidb(void *p,int n) { return (CSCHAR *)p+oidb(n);}
  186.       CSCHAR   *fkidb(void *p)         { return (CSCHAR *)p+sizeof(d_block); }
  187.  
  188.     /////////////////////// Identify type of database ////////////////////////
  189.       virtual void check_id(U32 id);
  190.       virtual void set_id(void);
  191.  
  192.     /////////////////////// Copying /////////////////////////////////////////
  193.       void  copy_dat(void *d,void *s)    { memcpy(d,s,datlen); }
  194.       void  copy_key(void *d,void *s)    { memcpy(d,s,keylen); }
  195.       void  copy_poi(void *d,BPOINT &s) { *(BPOINT *)d=s; }
  196.  
  197.     /////////////////////// Delete Aid //////////////////////////////////////
  198.       void  delet(void *b,void *KeyPos,int KeyNr);
  199.  
  200.     /////////////////////// Create/Free Block //////////////////////////////////
  201.       void  c_root(void *keyl,BPOINT l,void *keyr,BPOINT r);
  202.       void  c_root(void *keyl,BPOINT l);
  203.       CSCHAR *c_block(void);
  204.       void  f_block(void *p);
  205.  
  206.     /////////////////////// Connecting blocks //////////////////////////////
  207.       void  connect(void *l,void *r)   { DRNR(l)=BTR(r); DLNR(r)=BTR(l); }
  208.       void  connect(BPOINT l,void *r);
  209.       void  connect(void *l,BPOINT p);
  210.       void  connect(BPOINT l,BPOINT p);
  211.  
  212.     /////////////////////// Splitting blocks ////////////////////////////////
  213.       void  calc_split_info(int ig,int dg);
  214.       void  split_data(void *lb,CSCHAR *&hb);
  215.       void  split_index(void *b,CSCHAR *&c);
  216.  
  217.     /////////////////////// Removing key from block /////////////////////////
  218.       int   rkajib(void *b,void *KeyPos,int KeyNr);
  219.       void  rkajdb(void *b,void *KeyPos,int KeyNr);
  220.       void  rkfib(void *block,void *KeyPos,int KeyNr);
  221.       void  rkfdb(void *block,void *KeyPos,int KeyNr);
  222.  
  223.     /////////////////////// Insert key in block ////////////////////////////////
  224.       void  ikasdb(void *b,CSCHAR *kp,int nr,void *key,void *data);
  225.       void  ikiib(void *b,CSCHAR *kp,int nr,void *key,BPOINT dat);
  226.       void  ikidb(void *b,CSCHAR *kp,int nr,void *key,void *data);
  227.       void  insert_index(void *key,BPOINT dow);
  228.  
  229.     /////////////////////// Searching for a key ////////////////////////////////
  230.       CSCHAR *ski2ib(void *b,void *key,int &nr);
  231.       CSCHAR *skiib(void *b,void *key,int &nr);
  232.       CSCHAR *ski2ib(void *b,void *key) { int nr; return ski2ib(b,key,nr); }
  233.       CSCHAR *skiib(void *b,void *key)    { int nr; return skiib(b,key,nr);  }
  234.       CSCHAR *skidb(void *b,void *key)    { int nr; return skidb(b,key,nr);  }
  235.       CSCHAR *skidb(void *b,void *key,int &nr);
  236.  
  237.     /////////////////////// Reading from file //////////////////////////////////
  238.       CSCHAR *p2cpd(BPOINT p)          { return (CSCHAR *)locate_rec_d(p); }
  239.       CSCHAR *p2cp(BPOINT p)          { return (CSCHAR *)locate_rec(p); }
  240.       CSCHAR *p2cpl(BPOINT p)          { return (CSCHAR *)locate_rec_l(p); }
  241.  
  242.     /////////////////////// Comparing keys /////////////////////////////////////////////
  243.       virtual int t_key(void *a,void *b)=0;
  244.       int  t_dat(void *a,void *b) { return memcmp(a,b,datlen); }
  245.  
  246.     /////////////////////// Dirty /////////////////////////////////////////////
  247.       void  block_dirty(void *block) { TBASE::dirty(block); }
  248.  
  249.     /////////////////////// Miscellaneous /////////////////////////////////////
  250.       void   reporter(FILE *fp,BPOINT p,int lev);
  251.       void   expand(void *key,void *data);
  252.  
  253.       int    oiib(int n)     { return a_oiib+n*b_oiib; }
  254.       int    oidb(int n)     { return a_oidb+n*b_oidb; }
  255.  
  256.       int    nill(BPOINT &p)     { return !p; }
  257.       int    index_full(void *p) { return (DNR(p)==imnk); }
  258.       int    data_full(void *p)  { return (DNR(p)==dmnk); }
  259.       int    data_low(void *p)     { return (DNR(p)<=donr); }
  260.       int    index_low(void *p)  { return (DNR(p)<=ionr); }
  261.       BPOINT set_nill(BPOINT &p) { return (p=0); }
  262.       BPOINT sdb(void *key);
  263.  
  264.       void   nill_mk(void *kp)     { if(multiple_keys()) set_nill(*s2fidb(kp)); }
  265.  
  266.       int    search_gt(void *key,void *&kp);
  267.       int    search_ge(void *key,void *&kp);
  268.       int    search_le_u(void *key,void *&kp,void *&da);
  269.       int    search_lt_u(void *key,void *&kp,void *&da);
  270.  
  271.  
  272.  
  273. ////////////////////////////////////////////////////////////////////////
  274. ////////////////////// PUBLIC FUNCTIONS ////////////////////////////////
  275. ////////////////////////////////////////////////////////////////////////
  276.  
  277.     public:
  278.  
  279.  
  280.       BTREE(void );
  281.       ~BTREE(void );
  282.  
  283.  
  284. //////////////////////// Definition //////////////////////////////////////////
  285.       void  define(CSCHAR *name, int key_l,int dat_l);
  286.  
  287. //////////////////////// Open & Close ////////////////////////////////////////
  288.       int   open(CSCHAR *name, int kb_buff=32);
  289.       int   open(void)      { return already_open(); }
  290.       void  close(void);
  291.  
  292. ////////////////////////// Deleting ////////////////////////////////////////////
  293.       int   delet(void *key);
  294.       int   delet(void *key,void *data);
  295.  
  296. ////////////////////////// Inserting ///////////////////////////////////////////
  297.       void  insert(void *key,void *data);
  298.  
  299. ////////////////////////  Testing Begin & End /////////////////////////////////
  300.       int   tBOF(void);    // test Begin Of File
  301.       int   tEOF(void);    // test End     Of File
  302.  
  303. ////////////////////////  First and Last entries //////////////////////////////
  304.       int   min(void);
  305.       int   min(void *Key,void *Data);
  306.       int   min_dat(void *Data);
  307.       int   min_key(void *Key);
  308.  
  309.       int   max(void);
  310.       int   max(void *Key,void *Data);
  311.       int   max_dat(void *Data);
  312.       int   max_key(void *Key);
  313.  
  314. //////////////////////// Checking for Existence //////////////////////////////
  315.       int   find(void *key,void *data);
  316.       int   find(void *key);
  317.  
  318. //////////////////////// Searching ////////////////////////////////////////////
  319.       int   search(void *key,void *Data);
  320.  
  321.       int   search_gt(void *key,void *Key,void *Data);
  322.       int   search_ge(void *key,void *Key,void *Data);
  323.       int   search_lt(void *key,void *Key,void *Data);
  324.       int   search_le(void *key,void *Key,void *Data);
  325.  
  326.       int   search_dat_gt(void *key,void *Data);
  327.       int   search_dat_ge(void *key,void *Data);
  328.       int   search_dat_lt(void *key,void *Data);
  329.       int   search_dat_le(void *key,void *Data);
  330.  
  331.       int   search_key_gt(void *key,void *Key);
  332.       int   search_key_ge(void *key,void *Key);
  333.       int   search_key_lt(void *key,void *Key);
  334.       int   search_key_le(void *key,void *Key);
  335.  
  336.  
  337. //////////////////////// Skipping /////////////////////////////////////////////
  338.       int   prev(void);
  339.       int   prev(int n);
  340.       int   prev_key(int n,void *Key);
  341.       int   prev_dat(int n,void *Data);
  342.       int   prev(int n,void *Key,void *Data);
  343.  
  344.       int   next(void);
  345.       int   next(int n);
  346.       int   next_key(int n,void *Key);
  347.       int   next_dat(int n,void *Data);
  348.       int   next(int n,void *Key,void *Data);
  349.  
  350.       int   skip(int n) { return ((n>0) ? next(n): -prev(-n)); }
  351.  
  352.       int   skip(int n,void *Key,void *Data)
  353.         {  if(n>0) return  next( n,Key,Data);
  354.            else    return -prev(-n,Key,Data); }
  355.       int   skip_key(int n,void *Key)
  356.         {  if(n>0) return  next_key( n,Key);
  357.            else    return -prev_key(-n,Key); }
  358.       int   skip_dat(int n,void *Dat)
  359.         {  if(n>0) return  next_dat( n,Dat);
  360.            else    return -prev_dat(-n,Dat); }
  361.  
  362. //////////////////////// Current location /////////////////////////////////////
  363.       int   current(void *Key,void *Data);
  364.       int   current_key(void *Key);
  365.       int   current_dat(void *Data);
  366.  
  367. //////////////////////// Report Writing //////////////////////////////////////
  368.       void  report(CSCHAR *rname,int sub=1);
  369.       void  report(FILE *fp,int sub=1);
  370.  
  371. //////////////////////// Number of Keys //////////////////////////////////////
  372.       long  numkey(void)  { return num_key; }
  373.  
  374. ////////////////////////// Miscellaneous ///////////////////////////////////////
  375.       int   pack(void);
  376.       void  zap(void);
  377.       void  info(void );
  378.       void  empty(void);
  379.       void  multiple_keys(int TrueOrFalse);
  380.       void  multiple_keys_YES(void)       { multiple_keys(TRUE);  }
  381.       void  multiple_keys_NO(void)       { multiple_keys(FALSE); }
  382.       int   multiple_keys(void    )       { return mulkey; }
  383.       virtual int class_ID(void)       { return CS_CLID_BTREE; }
  384.  
  385.  
  386. };
  387.  
  388.  
  389.  
  390. /////////////////////////////////////////////////////////////////////////////////
  391. class BTREEb: public BTREE
  392. {
  393.     virtual int t_key(void *a,void *b) { return memcmp(a,b,keylen);}
  394.     virtual int class_ID(void)    { return CS_CLID_BTREEb; }
  395. };
  396. /////////////////////////////////////////////////////////////////////////////////
  397. class BTREEi: public BTREE
  398. {
  399.  
  400.    virtual int t_key(void *a,void *b)
  401.     {
  402.       if(*(int *)a < *(int *)b) return -1;
  403.       if(*(int *)a > *(int *)b) return    1;
  404.       return 0;
  405.     }
  406.  
  407.  
  408. //  You can use this for integers between -16000 & +16000
  409. //  virtual int t_key(void *a,void *b) { return *(int *)a-*(int *)b; }
  410.  
  411.     virtual int class_ID(void)    { return CS_CLID_BTREEi; }
  412.  
  413. };
  414. /////////////////////////////////////////////////////////////////////////////////
  415. class BTREEc: public BTREE
  416. {
  417.     virtual int t_key(void *a,void *b) { return ((int)*(S8 *)a)-((int)*(S8 *)b); }
  418.     virtual int class_ID(void)    { return CS_CLID_BTREEc; }
  419. };
  420. /////////////////////////////////////////////////////////////////////////////////
  421. class BTREEl: public BTREE
  422. {
  423.    virtual int t_key(void *a,void *b)
  424.     {
  425.       if(*(long *)a < *(long *)b) return -1;
  426.       if(*(long *)a > *(long *)b) return  1;
  427.       return 0;
  428.     }
  429.    virtual int class_ID(void)  { return CS_CLID_BTREEl; }
  430.  
  431. };
  432. /////////////////////////////////////////////////////////////////////////////////
  433. class BTREEf: public BTREE
  434. {
  435.     virtual int t_key(void *a,void *b)
  436.     {
  437.       if(*(float *)a < *(float *)b) return -1;
  438.       if(*(float *)a > *(float *)b) return  1;
  439.       return 0;
  440.     }
  441.     virtual int class_ID(void)    { return CS_CLID_BTREEf; }
  442. };
  443. /////////////////////////////////////////////////////////////////////////////////
  444. class BTREEd: public BTREE
  445. {
  446.     virtual int t_key(void *a,void *b)
  447.     {
  448.       if(*(double *)a < *(double *)b) return -1;
  449.       if(*(double *)a > *(double *)b) return  1;
  450.       return 0;
  451.     }
  452.     virtual int class_ID(void)    { return CS_CLID_BTREEd; }
  453. };
  454. /////////////////////////////////////////////////////////////////////////////////
  455. class BTREEa: public BTREE
  456. {
  457.     virtual int t_key(void *a,void *b)
  458.         { return strnicmp((CSCHAR *)a,(CSCHAR *)b,keylen);}
  459.     virtual int class_ID(void)    { return CS_CLID_BTREEa; }
  460. };
  461.  
  462.  
  463. #pragma warn .sig
  464.  
  465. #endif
  466.