home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / database / db12 / db_idx.c next >
Encoding:
C/C++ Source or Header  |  1987-11-15  |  30.4 KB  |  1,008 lines
  1. /****************************************************************************/
  2. /*                                                                          */
  3. /*                                                                          */
  4. /*      db_idx.c      (c) 1987  Ken Harris                                  */
  5. /*                                                                          */
  6. /*                                                                          */
  7. /****************************************************************************/
  8. /*                                                                          */
  9. /*      This software is made available on an AS-IS basis. Unrestricted     */
  10. /*      use is granted provided that the copywrite notice remains intack.   */
  11. /*      The author makes no warranties expressed or implied.                */
  12. /*                                                                          */
  13. /****************************************************************************/
  14.  
  15. #include <stdio.h>
  16. #ifdef MSC
  17. #include <fcntl.h>
  18. #include <sys\types.h>
  19. #include <sys\stat.h>
  20. #endif
  21. #include "db.h"
  22.  
  23. /*
  24.  *      db_add_idx  -  Add record to an index file
  25.  */
  26.  
  27. void db_add_idx(ds, user_data)
  28.  DATA_SET ds;
  29.  char *user_data;
  30. {
  31.         FILE_HDR    fh;
  32.         INDEX_HDR ihdr;
  33.         INDEX_REC irec;
  34.         BUFFER     buf;
  35.         char     *rbuf, *src, *dst;
  36.         ushort     rec;
  37.         int        cnt;
  38.  
  39.         db_error     = 0;
  40.  
  41.         fh   = (FILE_HDR) ds->ds_fhdr->buf_data;
  42.         buf  = ds->ds_buf;
  43.         ihdr = (INDEX_HDR) buf->buf_data;
  44.         rbuf = buf->buf_data + sizeof(struct db_index_hdr);
  45.  
  46.         if (!fh->fh_root_ptr)
  47.         {       db_get_next_avail(ds, buf);
  48.                 if (db_error) return;
  49.         }
  50.         else
  51.         {       db_find_insert_idx(ds, user_data, fh->fh_key_size);
  52.                 if (db_match_blk)
  53.                         if (!(fh->fh_file_stat & DB_DUP_ALLOWED))
  54.                         {       db_error = DB_DUP_NOT_ALLOWED;
  55.                                 return;
  56.                         }
  57.         }
  58.                  
  59.         ihdr->idx_rec_cnt++;
  60.         rec = buf->buf_rec_inx;
  61.  
  62.         db_add_blk = buf->buf_cur_blk;
  63.         db_add_rec = buf->buf_rec_inx;
  64.  
  65.         if (rec <= ihdr->idx_rec_cnt)
  66.         {       src = rbuf + (rec - 1) * fh->fh_rec_size;
  67.                 dst = src + fh->fh_rec_size;
  68.                 cnt = (ihdr->idx_rec_cnt - rec + 1) * fh->fh_rec_size;
  69.                 memcpy(dst, src, cnt);
  70.         }                             
  71.         
  72.         irec = (INDEX_REC) src;
  73.         irec->idx_idx_ptr = 0;
  74.         dst = (char *) irec + fh->fh_ctl_size;
  75.         memcpy(dst, user_data, fh->fh_data_size);
  76.  
  77.         fh->fh_rec_cnt++;
  78.  
  79.         db_split_blk_idx(ds);
  80.         if (db_error) return;
  81.  
  82.         db_put_blk(ds, ds->ds_fhdr);
  83. }
  84.       
  85. /*
  86.  *      db_find_insert_idx  -  Find Insert Point in an index File
  87.  */
  88.  
  89. void db_find_insert_idx(ds, key, key_size)
  90.  DATA_SET ds;
  91.  char *key;                         
  92.  int   key_size;
  93. {
  94.         FILE_HDR    fh;
  95.         INDEX_HDR ihdr;
  96.         INDEX_REC irec;
  97.         BUFFER     buf;
  98.         char     *rbuf, *ikey;
  99.         ulong      blk;
  100.         ushort     rec;
  101.         int          x;
  102.                        
  103.  
  104.         db_error     = 0;
  105.         db_match_blk = 0;
  106.         db_match_rec = 0;
  107.  
  108.         fh   = (FILE_HDR) ds->ds_fhdr->buf_data;
  109.         buf  = ds->ds_buf;
  110.         ihdr = (INDEX_HDR) buf->buf_data;
  111.         blk  = fh->fh_root_ptr;
  112.  
  113.         if (!key_size) key_size = fh->fh_key_size;
  114.  
  115.         while (blk)
  116.         {       db_get_blk(ds, blk, buf);
  117.                 if (db_error) return;
  118.  
  119.                 rbuf = buf->buf_data + sizeof(struct db_index_hdr);
  120.  
  121.                 for (rec=1; rec <= ihdr->idx_rec_cnt; rec++)
  122.                 {       irec = (INDEX_REC) rbuf;
  123.                         ikey = rbuf + fh->fh_ctl_size;
  124.  
  125.                         x = memcmp(key, ikey, key_size);
  126.         
  127.                         if (x == 0)
  128.                         {       db_match_blk = blk;
  129.                                 db_match_rec = rec;
  130.                                 blk = irec->idx_idx_ptr;
  131.                                 break;
  132.                         }
  133.  
  134.                         if (x < 0)
  135.                         {       blk = irec->idx_idx_ptr;
  136.                                 break;
  137.                         }
  138.  
  139.                         rbuf += fh->fh_rec_size;
  140.  
  141.                         if (rec == ihdr->idx_rec_cnt)
  142.                         {       irec = (INDEX_REC) rbuf;
  143.                                 blk  = irec->idx_idx_ptr;
  144.                         }
  145.                 }        
  146.         }
  147.         buf->buf_rec_inx = rec;
  148. }
  149.  
  150. /*
  151.  *      db_split_blk_idx  -  Check for a block split
  152.  */
  153.  
  154. void db_split_blk_idx(ds)
  155.  DATA_SET ds;
  156. {
  157.         FILE_HDR   fh;
  158.         BUFFER     buf,  tmp,  aux;
  159.         INDEX_HDR ihdr,  thdr, ahdr;
  160.         INDEX_REC  idx;
  161.         char     *hold, *rbuf, *src,  *dst;
  162.         ushort     cnt,  cnt1,  cnt2;
  163.         ushort     rec,  left, right;
  164.  
  165.         db_error = 0;
  166.  
  167.         fh  = (FILE_HDR) ds->ds_fhdr->buf_data;
  168.         buf = ds->ds_buf;
  169.         tmp = ds->ds_tmp;
  170.  
  171.         ihdr = (INDEX_HDR) buf->buf_data;
  172.  
  173.         if (ihdr->idx_rec_cnt <= fh->fh_recs_per_blk)
  174.         {       db_put_blk(ds, buf);
  175.                 return;
  176.         }
  177.  
  178.         buf        = ds->ds_tmp;
  179.         tmp        = ds->ds_buf;
  180.         ds->ds_buf = buf;
  181.         ds->ds_tmp = tmp;
  182.         aux        = ds->ds_aux;
  183.  
  184.         db_get_next_avail(ds, buf);
  185.         if (db_error) return;
  186.  
  187.         ihdr = (INDEX_HDR) buf->buf_data;
  188.         thdr = (INDEX_HDR) tmp->buf_data;
  189.         ahdr = (INDEX_HDR) aux->buf_data;
  190.  
  191.         left   = tmp->buf_cur_blk;
  192.         right  = buf->buf_cur_blk;
  193.  
  194.         cnt1 = thdr->idx_rec_cnt / 2;
  195.         cnt2 = thdr->idx_rec_cnt - (cnt1 + 1);
  196.  
  197.         ihdr->idx_parent  = thdr->idx_parent;
  198.         ihdr->idx_rec_cnt = cnt2;         
  199.  
  200.         src = tmp->buf_data + sizeof(struct db_index_hdr)
  201.                                                 + (cnt1 + 1) * fh->fh_rec_size;
  202.         dst = buf->buf_data + sizeof(struct db_index_hdr);
  203.         cnt = (cnt2 + 1) * fh->fh_rec_size;
  204.         memcpy(dst, src, cnt);
  205.  
  206.         db_put_blk(ds, buf);
  207.         if (db_error) return;
  208.  
  209.         if (db_add_blk == tmp->buf_cur_blk)
  210.                 if (db_add_rec > cnt1 + 1)
  211.                 {       db_add_blk  =  buf->buf_cur_blk;
  212.                         db_add_rec -= cnt1 + 1;         
  213.                 }
  214.  
  215.         rbuf = buf->buf_data + sizeof(struct db_index_hdr);
  216.         if (!thdr->idx_parent)
  217.         {       if (tmp->buf_cur_blk != fh->fh_root_ptr)
  218.                 {       db_error = DB_INVALID_INDEX;
  219.                         return;
  220.                 }
  221.                 db_get_next_avail(ds, buf);
  222.                 thdr->idx_parent = buf->buf_cur_blk;
  223.                 fh->fh_root_ptr  = buf->buf_cur_blk;
  224.                 idx              = (INDEX_REC) rbuf;
  225.                 rec              = 1;
  226.         }
  227.         else
  228.         {       db_get_blk(ds, (long)thdr->idx_parent, buf);
  229.                 if (db_error) return;
  230.  
  231.                 for (rec=1; rec <= ihdr->idx_rec_cnt+1; rec++)
  232.                 {       idx = (INDEX_REC) rbuf;
  233.  
  234.                         if (idx->idx_idx_ptr == left)
  235.                                 break;
  236.  
  237.                         rbuf += fh->fh_rec_size;
  238.                 }
  239.  
  240.                 if (idx->idx_idx_ptr != left)
  241.                 {       db_error = DB_INVALID_INDEX;
  242.                         return;
  243.                 }
  244.         }
  245.  
  246.         idx->idx_idx_ptr = right;
  247.  
  248.         if (db_add_blk == tmp->buf_cur_blk)
  249.                 if (db_add_rec == cnt1 + 1)
  250.                 {       db_add_blk =  buf->buf_cur_blk;
  251.                         db_add_rec =  rec;
  252.                 }
  253.  
  254.         src = rbuf;
  255.         dst = rbuf + fh->fh_rec_size;
  256.         cnt = ((ihdr->idx_rec_cnt + 1) - rec + 1) * fh->fh_rec_size;
  257.         memcpy(dst, src, cnt);
  258.  
  259.         src = tmp->buf_data + sizeof(struct db_index_hdr)
  260.                                          + cnt1 * fh->fh_rec_size;
  261.         dst = rbuf;
  262.         cnt = fh->fh_rec_size;
  263.         memcpy(dst, src, cnt);
  264.  
  265.         idx->idx_idx_ptr = left;
  266.         ihdr->idx_rec_cnt++;
  267.  
  268.         thdr->idx_rec_cnt = cnt1;
  269.         db_put_blk(ds, tmp);
  270.         if (db_error) return;
  271.  
  272.         db_get_blk(ds, (long) right, tmp);
  273.         if (db_error) return;
  274.  
  275.         if (thdr->idx_parent != buf->buf_cur_blk)
  276.         {       thdr->idx_parent = buf->buf_cur_blk;
  277.                 db_put_blk(ds, tmp);
  278.                 if (db_error) return;
  279.         }
  280.  
  281.         rbuf = tmp->buf_data + sizeof(struct db_index_hdr);
  282.         for (cnt=1; cnt <= thdr->idx_rec_cnt + 1; cnt++)
  283.         {       idx = (INDEX_REC) rbuf;
  284.  
  285.                 if (idx->idx_idx_ptr)
  286.                 {       db_get_blk(ds, (long)idx->idx_idx_ptr, aux);
  287.                         if (db_error) return;
  288.  
  289.                         ahdr->idx_parent = tmp->buf_cur_blk;
  290.                         db_put_blk(ds, aux);
  291.                         if (db_error) return;
  292.                 }
  293.  
  294.                 rbuf += fh->fh_rec_size;
  295.         }
  296.  
  297.         db_split_blk_idx(ds);
  298. }
  299.  
  300. /*
  301.  *      db_read_first_idx  -  Read First Record in an Index File
  302.  */
  303.  
  304. void db_read_first_idx(ds, blk, user_data)                           
  305.  DATA_SET ds;
  306.  ushort blk;
  307.  char *user_data;
  308. {
  309.         FILE_HDR    fh;
  310.         BUFFER     buf;
  311.         INDEX_HDR ihdr;
  312.         INDEX_REC  idx;
  313.         char      *src;
  314.  
  315.                     
  316.         db_error = 0;
  317.  
  318.         if (!blk)
  319.         {       db_error = DB_END_OF_FILE;
  320.                 return;
  321.         }
  322.  
  323.         fh   = (FILE_HDR) ds->ds_fhdr->buf_data;
  324.         buf  = ds->ds_buf;
  325.         ihdr = (INDEX_HDR)  buf->buf_data;
  326.         idx  = (INDEX_REC) (buf->buf_data + sizeof(struct db_index_hdr));
  327.  
  328.         while (blk)
  329.         {       db_get_blk(ds, (long) blk, buf);
  330.                 if (db_error) return;
  331.          
  332.  
  333.                 if (!ihdr->idx_rec_cnt)
  334.                 {       db_error = DB_INVALID_INDEX;
  335.                         return;
  336.                 }
  337.  
  338.                 blk = idx->idx_idx_ptr;
  339.         }                              
  340.  
  341.         src = buf->buf_data + sizeof(struct db_index_hdr) + fh->fh_ctl_size;
  342.         buf->buf_rec_inx = 1;
  343.         memcpy(user_data, src, fh->fh_data_size);
  344. }
  345.  
  346. /*
  347.  *      db_read_next_idx  -  Read Next Record in an Index File
  348.  */
  349.  
  350. void db_read_next_idx(ds, user_data)
  351.  DATA_SET ds;
  352.  char *user_data;
  353. {
  354.         FILE_HDR    fh;
  355.         BUFFER     buf;
  356.         INDEX_HDR ihdr;
  357.         INDEX_REC  idx;
  358.         char      *src;
  359.  
  360.                     
  361.         db_error = 0;
  362.  
  363.         fh   = (FILE_HDR) ds->ds_fhdr->buf_data;
  364.         buf  = ds->ds_buf;
  365.         ihdr = (INDEX_HDR)  buf->buf_data;
  366.                                                
  367.         db_get_blk(ds, ds->ds_prev_blk, buf);
  368.         if (db_error) return;
  369.  
  370.         buf->buf_rec_inx = ds->ds_prev_rec;
  371.  
  372.         if (buf->buf_rec_inx > ihdr->idx_rec_cnt)
  373.         {       while (buf->buf_rec_inx > ihdr->idx_rec_cnt)
  374.                 {       db_get_parent_idx(ds);
  375.                         if (db_error) return;
  376.                 }
  377.  
  378.                 src = buf->buf_data + sizeof(struct db_index_hdr)
  379.                     + (buf->buf_rec_inx - 1) * fh->fh_rec_size
  380.                     + fh->fh_ctl_size;
  381.  
  382.                 memcpy(user_data, src, fh->fh_data_size);
  383.                 return;
  384.         }
  385.  
  386.         buf->buf_rec_inx++;
  387.  
  388.         idx = (INDEX_REC) (buf->buf_data + sizeof(struct db_index_hdr)
  389.             + (buf->buf_rec_inx - 1) * fh->fh_rec_size);
  390.  
  391.         if (idx->idx_idx_ptr)
  392.         {       db_read_first_idx(ds, idx->idx_idx_ptr, user_data);
  393.                 return;
  394.         }
  395.  
  396.         if (buf->buf_rec_inx > ihdr->idx_rec_cnt)
  397.         {       ds->ds_prev_rec = buf->buf_rec_inx;
  398.                 db_read_next_idx(ds, user_data);
  399.                 return;
  400.         }
  401.  
  402.         src = ((char *) idx) + fh->fh_ctl_size;
  403.         memcpy(user_data, src, fh->fh_data_size);
  404. }
  405.  
  406. /*
  407.  *    db_read_last_idx  -  Read Last Record in an Index File
  408.  */
  409.  
  410. void db_read_last_idx(ds, blk, user_data)
  411.  DATA_SET ds;
  412.  ushort blk;
  413.  char *user_data;
  414. {
  415.         FILE_HDR    fh;
  416.         BUFFER     buf;
  417.         INDEX_HDR ihdr;
  418.         INDEX_REC  idx;
  419.         char      *src;
  420.  
  421.                     
  422.         db_error = 0;
  423.  
  424.         if (!blk)
  425.         {       db_error = DB_END_OF_FILE;
  426.                 return;
  427.         }
  428.  
  429.         fh   = (FILE_HDR) ds->ds_fhdr->buf_data;
  430.         buf  = ds->ds_buf;
  431.         ihdr = (INDEX_HDR)  buf->buf_data;
  432.  
  433.         while (blk)
  434.         {       db_get_blk(ds, (long) blk, buf);
  435.                 if (db_error) return;
  436.          
  437.  
  438.                 if (!ihdr->idx_rec_cnt)
  439.                 {       db_error = DB_INVALID_INDEX;
  440.                         return;
  441.                 }
  442.  
  443.         idx  = (INDEX_REC) (buf->buf_data + sizeof(struct db_index_hdr)
  444.                    + ihdr->idx_rec_cnt * fh->fh_rec_size);
  445.  
  446.                 blk = idx->idx_idx_ptr;
  447.         }                              
  448.  
  449.     src = buf->buf_data + sizeof(struct db_index_hdr)
  450.         + (ihdr->idx_rec_cnt - 1) * fh->fh_rec_size + fh->fh_ctl_size;
  451.  
  452.     buf->buf_rec_inx = ihdr->idx_rec_cnt;
  453.         memcpy(user_data, src, fh->fh_data_size);
  454. }
  455.  
  456. /*
  457.  *    db_read_prev_idx  -  Read Prev Record in an Index File
  458.  */
  459.  
  460. void db_read_prev_idx(ds, user_data)
  461.  DATA_SET ds;
  462.  char *user_data;
  463. {
  464.         FILE_HDR    fh;
  465.         BUFFER     buf;
  466.         INDEX_HDR ihdr;
  467.         INDEX_REC  idx;
  468.         char      *src;
  469.  
  470.                     
  471.         db_error = 0;
  472.  
  473.         fh   = (FILE_HDR) ds->ds_fhdr->buf_data;
  474.         buf  = ds->ds_buf;
  475.         ihdr = (INDEX_HDR)  buf->buf_data;
  476.                                                
  477.         db_get_blk(ds, ds->ds_prev_blk, buf);
  478.         if (db_error) return;
  479.  
  480.         buf->buf_rec_inx = ds->ds_prev_rec;
  481.  
  482.         idx = (INDEX_REC) (buf->buf_data + sizeof(struct db_index_hdr)
  483.             + (buf->buf_rec_inx - 1) * fh->fh_rec_size);
  484.  
  485.     if (buf->buf_rec_inx == 1 && idx->idx_idx_ptr == 0)
  486.     {    while (buf->buf_rec_inx == 1)
  487.                 {       db_get_parent_idx(ds);
  488.                         if (db_error) return;
  489.                 }
  490.                         
  491.         buf->buf_rec_inx--;
  492.  
  493.                 src = buf->buf_data + sizeof(struct db_index_hdr)
  494.                     + (buf->buf_rec_inx - 1) * fh->fh_rec_size
  495.                     + fh->fh_ctl_size;
  496.  
  497.                 memcpy(user_data, src, fh->fh_data_size);
  498.                 return;
  499.         }
  500.  
  501.         if (idx->idx_idx_ptr)
  502.     {    db_read_last_idx(ds, idx->idx_idx_ptr, user_data);
  503.                 return;
  504.         }
  505.  
  506.     buf->buf_rec_inx--;
  507.  
  508.         idx = (INDEX_REC) (buf->buf_data + sizeof(struct db_index_hdr)
  509.             + (buf->buf_rec_inx - 1) * fh->fh_rec_size);
  510.  
  511.         src = ((char *) idx) + fh->fh_ctl_size;
  512.         memcpy(user_data, src, fh->fh_data_size);
  513. }
  514.  
  515.  
  516. /*
  517.  *      db_get_parent_idx  -  Get Parent Block
  518.  */
  519.  
  520. void db_get_parent_idx(ds)
  521.  DATA_SET ds;        
  522. {
  523.         FILE_HDR     fh;
  524.         BUFFER      buf;
  525.         INDEX_HDR  ihdr;
  526.         INDEX_REC   idx;
  527.         char      *rbuf;
  528.         ushort hold_blk;
  529.         int         rec;
  530.  
  531.                     
  532.         db_error = 0;
  533.  
  534.         fh   = (FILE_HDR) ds->ds_fhdr->buf_data;
  535.         buf  = ds->ds_buf;
  536.         rbuf = buf->buf_data + sizeof(struct db_index_hdr);
  537.         ihdr = (INDEX_HDR)  buf->buf_data;                 
  538.  
  539.         hold_blk = buf->buf_cur_blk;
  540.         if (!ihdr->idx_parent)
  541.         {       db_error = DB_END_OF_FILE;
  542.                 return;
  543.         }
  544.  
  545.         db_get_blk(ds, (long)ihdr->idx_parent, buf);
  546.         if (db_error) return;
  547.  
  548.         for (rec=1; rec <= ihdr->idx_rec_cnt + 1; rec++)
  549.         {       idx = (INDEX_REC) rbuf;
  550.  
  551.                 if (idx->idx_idx_ptr == hold_blk)
  552.                         break;
  553.  
  554.                 rbuf += fh->fh_rec_size;
  555.         }
  556.  
  557.         if (idx->idx_idx_ptr != hold_blk)
  558.         {       db_error = DB_INVALID_INDEX;
  559.                 return;
  560.         }
  561.  
  562.         buf->buf_rec_inx = rec;
  563. }
  564.  
  565. /*
  566.  *      db_find_first_idx  -  Find First Record
  567.  */
  568.  
  569. void db_find_first_idx(ds, user_data, key, key_size)
  570.  DATA_SET ds;
  571.  char *user_data;
  572.  char *key;
  573.  int   key_size;
  574. {
  575.         FILE_HDR  fh;
  576.         BUFFER   buf;
  577.         char   *rbuf;
  578.  
  579.         db_error = 0;
  580.  
  581.         fh   = (FILE_HDR) ds->ds_fhdr->buf_data;
  582.         buf  = ds->ds_buf;
  583.  
  584.         db_find_insert_idx(ds, key, key_size);
  585.         if (db_error) return;
  586.  
  587.         if (!db_match_blk)
  588.         {       db_error = DB_REC_NOT_FOUND;
  589.                 return;
  590.         }
  591.  
  592.         db_get_blk(ds, db_match_blk, buf);
  593.         if (db_error) return;
  594.  
  595.         buf->buf_rec_inx = db_match_rec;
  596.  
  597.         rbuf = buf->buf_data + sizeof(struct db_index_hdr)
  598.              + (buf->buf_rec_inx - 1) * fh->fh_rec_size + fh->fh_ctl_size;
  599.  
  600.         memcpy(user_data, rbuf, fh->fh_data_size);
  601. }
  602.  
  603. /*
  604.  *      db_delete_idx  -  Delete an Index Record
  605.  */
  606.  
  607. void db_delete_idx(ds)
  608.  DATA_SET ds;
  609. {
  610.         FILE_HDR     fh;
  611.         BUFFER      buf;
  612.         INDEX_HDR  ihdr;
  613.         char       *src, *dst;
  614.         int         cnt, move_flag;
  615.  
  616.         db_error = 0;
  617.  
  618.         move_flag = db_move_to_leaf_idx(ds);
  619.         if (db_error) return;       
  620.  
  621.         fh   = (FILE_HDR) ds->ds_fhdr->buf_data;
  622.         buf  = ds->ds_buf;
  623.         ihdr = (INDEX_HDR) buf->buf_data;
  624.  
  625.         dst = buf->buf_data + sizeof(struct db_index_hdr)
  626.                             + (buf->buf_rec_inx - 1) * fh->fh_rec_size;
  627.         src = dst + fh->fh_rec_size;
  628.         cnt = (ihdr->idx_rec_cnt - buf->buf_rec_inx + 1) * fh->fh_rec_size;
  629.  
  630.         if (cnt) memcpy(dst, src, cnt);
  631.  
  632.         ds->ds_prev_blk = buf->buf_cur_blk;
  633.         ds->ds_prev_rec = buf->buf_rec_inx - 1;
  634.  
  635.         ihdr->idx_rec_cnt--;
  636.         if (fh->fh_rec_cnt) fh->fh_rec_cnt--;
  637.  
  638.         if (buf->buf_cur_blk == fh->fh_root_ptr  &&  ihdr->idx_rec_cnt == 0)
  639.         {       fh->fh_root_ptr = 0;
  640.                 db_free_rec(ds, buf);
  641.                 if (db_error) return;
  642.         }
  643.         else
  644.         {       db_balance_idx(ds);
  645.                 if (db_error) return;
  646.         }
  647.  
  648.         db_put_blk(ds, ds->ds_fhdr);
  649.  
  650.         if (move_flag)
  651.                 db_read_next(ds, ds->ds_tmp->buf_data);
  652. }
  653.  
  654. /*
  655.  *      db_move_to_leaf_idx  -  Move index record to a leaf node 
  656.  *                              before deleting it
  657.  */
  658.  
  659. short db_move_to_leaf_idx(ds)
  660.  DATA_SET ds;
  661. {
  662.         FILE_HDR     fh;
  663.         BUFFER      buf, tmp;
  664.         INDEX_HDR  ihdr, thdr;
  665.         INDEX_REC   idx, tdx;
  666.         ulong       blk;
  667.  
  668.         db_error = 0;
  669.  
  670.         fh  = (FILE_HDR) ds->ds_fhdr->buf_data;
  671.         buf = ds->ds_buf;
  672.  
  673.         tdx = (INDEX_REC)(buf->buf_data + sizeof(struct db_index_hdr)
  674.                                 + (buf->buf_rec_inx - 1) * fh->fh_rec_size);
  675.  
  676.         if (!tdx->idx_idx_ptr) return(0);
  677.  
  678.         tmp        = ds->ds_buf;
  679.         buf        = ds->ds_tmp;
  680.         ds->ds_buf = buf;
  681.         ds->ds_tmp = tmp;
  682.                    
  683.         ihdr = (INDEX_HDR) buf->buf_data;
  684.         thdr = (INDEX_HDR) tmp->buf_data;
  685.  
  686.         blk = tdx->idx_idx_ptr;
  687.  
  688.         while (blk)
  689.         {       db_get_blk(ds, blk, buf);
  690.                 if (db_error) return(0);
  691.  
  692.                 idx = (INDEX_REC)(buf->buf_data + sizeof(struct db_index_hdr)
  693.                                        + ihdr->idx_rec_cnt * fh->fh_rec_size);
  694.  
  695.                 blk = idx->idx_idx_ptr;
  696.         }
  697.  
  698.         idx = (INDEX_REC)((char *) idx - fh->fh_rec_size);
  699.  
  700.         idx->idx_idx_ptr = tdx->idx_idx_ptr;
  701.         memcpy(tdx, idx, fh->fh_rec_size);
  702.         idx->idx_idx_ptr = 0;
  703.  
  704.         db_put_blk(ds, tmp);
  705.         if (db_error) return(0);
  706.  
  707.         buf->buf_rec_inx = ihdr->idx_rec_cnt;
  708.  
  709.         return(1);
  710. }
  711.  
  712. /*
  713.  *      db_balance_idx  -  Rebalance tree after a delete
  714.  */
  715.  
  716. void db_balance_idx(ds)
  717.  DATA_SET ds;
  718. {
  719.         FILE_HDR    fh;
  720.         BUFFER     buf,  tmp,  aux;
  721.         INDEX_HDR ihdr, thdr, ahdr;
  722.         INDEX_REC  idx,  tdx,  adx;
  723.         int    min_cnt, hold,  cnt,  op;
  724.         char      *src, *dst;  
  725.  
  726.         db_error = 0;
  727.  
  728.         fh   = (FILE_HDR) ds->ds_fhdr->buf_data;
  729.         buf  = ds->ds_buf;
  730.         ihdr = (INDEX_HDR) buf->buf_data;
  731.  
  732.         if (buf->buf_cur_blk == fh->fh_root_ptr)
  733.         {       db_put_blk(ds, buf);
  734.                 return;
  735.         }
  736.  
  737.         min_cnt = (fh->fh_recs_per_blk + 1) / 2;
  738.         if (ihdr->idx_rec_cnt >= min_cnt)
  739.         {       db_put_blk(ds, buf);
  740.                 return;
  741.         }
  742.  
  743.         tmp        = ds->ds_buf;
  744.         buf        = ds->ds_tmp;
  745.         ds->ds_buf = buf;
  746.         ds->ds_tmp = tmp;
  747.         aux        = ds->ds_aux;
  748.  
  749.         thdr = (INDEX_HDR) tmp->buf_data;
  750.         ahdr = (INDEX_HDR) aux->buf_data;
  751.         ihdr = (INDEX_HDR) buf->buf_data;
  752.  
  753.         buf->buf_cur_blk = tmp->buf_cur_blk;
  754.         buf->buf_rec_inx = tmp->buf_rec_inx;
  755.         ihdr->idx_parent = thdr->idx_parent;
  756.  
  757.         db_get_parent_idx(ds);
  758.         if (db_error) return;
  759.  
  760.         idx  = (INDEX_REC)(buf->buf_data + sizeof(struct db_index_hdr)
  761.                                 + (buf->buf_rec_inx - 1) * fh->fh_rec_size);
  762.  
  763.         if (buf->buf_rec_inx == 1)
  764.         {       adx = (INDEX_REC) ((char *) idx + fh->fh_rec_size);
  765.                 op  = 1;
  766.         }
  767.         else
  768.         {       idx = adx = (INDEX_REC) ((char *) idx - fh->fh_rec_size);
  769.                 buf->buf_rec_inx--;
  770.                 op  = 2;          
  771.         }                              
  772.  
  773.         db_get_blk(ds, (long)adx->idx_idx_ptr, aux);
  774.         if (db_error) return;
  775.  
  776.         if (ahdr->idx_rec_cnt < min_cnt) op += 2;
  777.  
  778.         switch (op)
  779.         {   case 1: /* Rotate Left */
  780.                 if (ds->ds_prev_blk == aux->buf_cur_blk &&
  781.                     ds->ds_prev_rec == 0)
  782.                 {       ds->ds_prev_blk = buf->buf_cur_blk;
  783.                         ds->ds_prev_rec = buf->buf_rec_inx;
  784.                 }
  785.  
  786.                 if (ds->ds_prev_blk == buf->buf_cur_blk &&
  787.                     ds->ds_prev_rec == buf->buf_rec_inx)
  788.                 {       ds->ds_prev_blk = tmp->buf_cur_blk;
  789.                         ds->ds_prev_rec = thdr->idx_rec_cnt + 1;
  790.                 }                       
  791.                 else
  792.                 if (ds->ds_prev_blk == aux->buf_cur_blk &&
  793.                     ds->ds_prev_rec == 1)
  794.                 {       ds->ds_prev_blk = buf->buf_cur_blk;
  795.                         ds->ds_prev_rec = buf->buf_rec_inx;
  796.                 }
  797.                 else
  798.                 if (ds->ds_prev_blk == aux->buf_cur_blk)
  799.                         ds->ds_prev_rec--;
  800.  
  801.                 tdx = (INDEX_REC)(tmp->buf_data + sizeof(struct db_index_hdr)
  802.                             + thdr->idx_rec_cnt * fh->fh_rec_size);
  803.                 adx = (INDEX_REC)(aux->buf_data + sizeof(struct db_index_hdr));
  804.  
  805.                 hold = tdx->idx_idx_ptr;
  806.                 memcpy(tdx, idx, fh->fh_rec_size);
  807.                 tdx->idx_idx_ptr = hold;
  808.                 tdx = (INDEX_REC) ((char *) tdx + fh->fh_rec_size);
  809.                 tdx->idx_idx_ptr = adx->idx_idx_ptr;
  810.                 thdr->idx_rec_cnt++;
  811.                 db_put_blk(ds,tmp);
  812.                 if (db_error) return;
  813.  
  814.                 if (tdx->idx_idx_ptr)
  815.                 {       hold = tmp->buf_cur_blk;
  816.                         db_get_blk(ds, (long)tdx->idx_idx_ptr, tmp);
  817.                         if (db_error) return;
  818.  
  819.                         thdr->idx_parent = hold;
  820.                         db_put_blk(ds, tmp);
  821.                         if (db_error) return;
  822.                 }
  823.  
  824.                 hold = idx->idx_idx_ptr;
  825.                 memcpy(idx, adx, fh->fh_rec_size);
  826.                 idx->idx_idx_ptr = hold;
  827.                 db_put_blk(ds, buf);
  828.                 if (db_error) return;
  829.  
  830.                 src = (char*) adx + fh->fh_rec_size;
  831.                 cnt = ahdr->idx_rec_cnt * fh->fh_rec_size;
  832.                 memcpy(adx, src, cnt);
  833.                 ahdr->idx_rec_cnt--;
  834.                 db_put_blk(ds, aux);
  835.                 if (db_error) return;
  836.                 return;
  837.  
  838.             case 2: /* Rotate Right */ 
  839.                 if (ds->ds_prev_blk == buf->buf_cur_blk &&
  840.                     ds->ds_prev_rec == buf->buf_rec_inx)
  841.                 {       ds->ds_prev_blk = tmp->buf_cur_blk;
  842.                         ds->ds_prev_rec = 1;
  843.                 }                       
  844.                 else
  845.                 if (ds->ds_prev_blk == aux->buf_cur_blk &&
  846.                     ds->ds_prev_rec == ahdr->idx_rec_cnt)
  847.                 {       ds->ds_prev_blk = buf->buf_cur_blk;
  848.                         ds->ds_prev_rec = buf->buf_rec_inx;
  849.                 }
  850.                 else
  851.                 if (ds->ds_prev_blk == tmp->buf_cur_blk)
  852.                         ds->ds_prev_rec++;
  853.  
  854.                 tdx = (INDEX_REC)(tmp->buf_data + sizeof(struct db_index_hdr));
  855.                 adx = (INDEX_REC)(aux->buf_data + sizeof(struct db_index_hdr)
  856.                                        + ahdr->idx_rec_cnt * fh->fh_rec_size);
  857.  
  858.                 dst = (char *) tdx + fh->fh_rec_size;
  859.                 cnt = (thdr->idx_rec_cnt + 1) * fh->fh_rec_size;
  860.                 memcpy(dst, tdx, cnt);
  861.                 memcpy(tdx, idx, fh->fh_rec_size);
  862.                 tdx->idx_idx_ptr = adx->idx_idx_ptr;
  863.                 thdr->idx_rec_cnt++;
  864.                 db_put_blk(ds, tmp);
  865.                 if (db_error) return;
  866.  
  867.                 if (tdx->idx_idx_ptr)
  868.                 {       hold = tmp->buf_cur_blk;
  869.                         db_get_blk(ds, (long)tdx->idx_idx_ptr, tmp);
  870.                         if (db_error) return;
  871.  
  872.                         thdr->idx_parent = hold;
  873.                         db_put_blk(ds, tmp);
  874.                         if (db_error) return;
  875.                 }
  876.  
  877.                 hold = idx->idx_idx_ptr;
  878.                 adx  = (INDEX_REC) ((char *) adx - fh->fh_rec_size);
  879.                 memcpy(idx, adx, fh->fh_rec_size);
  880.                 idx->idx_idx_ptr = hold;
  881.                 db_put_blk(ds, buf);
  882.                 if (db_error) return;
  883.  
  884.                 ahdr->idx_rec_cnt--;
  885.                 db_put_blk(ds, aux);
  886.                 if (db_error) return;
  887.                 return;
  888.  
  889.             case 4: /* Merge Right */
  890.                 tmp        = ds->ds_aux;
  891.                 aux        = ds->ds_tmp;
  892.                 ds->ds_aux = aux;
  893.                 ds->ds_tmp = tmp;
  894.                 thdr       = (INDEX_HDR) tmp->buf_data;
  895.                 ahdr       = (INDEX_HDR) aux->buf_data;
  896.  
  897.             case 3: /* Merge Left */      
  898.                 if (ds->ds_prev_blk == buf->buf_cur_blk &&
  899.                     ds->ds_prev_rec == buf->buf_rec_inx)
  900.                 {       ds->ds_prev_blk = tmp->buf_cur_blk;
  901.                         ds->ds_prev_rec = thdr->idx_rec_cnt + 1;
  902.                 }                       
  903.                 else
  904.                 if (ds->ds_prev_blk == aux->buf_cur_blk)
  905.                 {       ds->ds_prev_blk  = tmp->buf_cur_blk;
  906.                         ds->ds_prev_rec += thdr->idx_rec_cnt + 1;
  907.                 }                       
  908.  
  909.                 tdx = (INDEX_REC)(tmp->buf_data + sizeof(struct db_index_hdr)
  910.                             + thdr->idx_rec_cnt * fh->fh_rec_size);
  911.                 adx = (INDEX_REC)(aux->buf_data + sizeof(struct db_index_hdr));
  912.  
  913.                 hold = tdx->idx_idx_ptr;
  914.                 memcpy(tdx, idx, fh->fh_rec_size);
  915.                 tdx->idx_idx_ptr = hold;
  916.                 tdx = (INDEX_REC) ((char *) tdx + fh->fh_rec_size);
  917.                 thdr->idx_rec_cnt++;
  918.  
  919.                 cnt = ahdr->idx_rec_cnt * fh->fh_rec_size + fh->fh_ctl_size;
  920.                 memcpy(tdx, adx, cnt);
  921.                 thdr->idx_rec_cnt += ahdr->idx_rec_cnt;
  922.  
  923.                 src = (char *) idx + fh->fh_rec_size;
  924.                 cnt = (ihdr->idx_rec_cnt - buf->buf_rec_inx)
  925.                                        * fh->fh_rec_size + fh->fh_ctl_size;
  926.                 memcpy(idx, src, cnt);
  927.                 idx->idx_idx_ptr = tmp->buf_cur_blk;
  928.                 ihdr->idx_rec_cnt--;
  929.  
  930.                 src = buf->buf_data + sizeof(struct db_index_hdr)
  931.                     + ihdr->idx_rec_cnt * fh->fh_rec_size + fh->fh_ctl_size;
  932.                 cnt = fh->fh_rec_size;
  933.                 memset(src, 0, cnt);
  934.  
  935.                 if (!ihdr->idx_rec_cnt)
  936.                         thdr->idx_parent = 0;
  937.  
  938.                 db_put_blk(ds, tmp);
  939.                 if (db_error) return;
  940.  
  941.                 hold = ahdr->idx_rec_cnt + 1;
  942.                 db_free_rec(ds, aux);
  943.                 if (db_error) return;
  944.  
  945.                 for (cnt=1; cnt <= hold; cnt++)
  946.                 {       if (tdx->idx_idx_ptr)
  947.                         {       db_get_blk(ds, (long)tdx->idx_idx_ptr, aux);
  948.                                 if (db_error) return;
  949.  
  950.                                 ahdr->idx_parent = tmp->buf_cur_blk;
  951.                                 db_put_blk(ds, aux);
  952.                                 if (db_error) return;
  953.                         }
  954.                         tdx = (INDEX_REC)((char *) tdx + fh->fh_rec_size);
  955.                 }
  956.  
  957.                 if (buf->buf_cur_blk == fh->fh_root_ptr)
  958.                 {       if (!ihdr->idx_rec_cnt)
  959.                         {       fh->fh_root_ptr = tmp->buf_cur_blk;
  960.                                 db_free_rec(ds, buf);
  961.                                 if (db_error) return;
  962.                         }
  963.                         else
  964.                         {       db_put_blk(ds, buf);
  965.                                 if (db_error) return;
  966.                         }
  967.                 }
  968.                 else
  969.                 {       db_balance_idx(ds);
  970.                         if (db_error) return;
  971.                 }
  972.  
  973.                 return;
  974.         }
  975. }
  976.  
  977. /*
  978.  *      db_update_idx - Update an Index record
  979.  */
  980.  
  981. void db_update_idx(ds, user_data)
  982.  DATA_SET  ds;
  983.  char     *user_data;
  984. {
  985.         INDEX_HDR   ihdr;
  986.         FILE_HDR    fh;
  987.         BUFFER      buf;
  988.         char       *rbuf;
  989.  
  990.         db_error = 0;
  991.  
  992.         fh   = (FILE_HDR) ds->ds_fhdr->buf_data;
  993.         buf  = ds->ds_buf;
  994.         ihdr = (INDEX_HDR) buf->buf_data;
  995.  
  996.         if (ihdr->idx_rec_cnt < buf->buf_rec_inx)
  997.         {       db_error = DB_DELETED_REC;
  998.                 return;
  999.         }
  1000.  
  1001.         rbuf = buf->buf_data + sizeof(struct db_index_hdr)
  1002.              + (buf->buf_rec_inx - 1) * fh->fh_rec_size;
  1003.  
  1004.         memcpy(rbuf+fh->fh_ctl_size, user_data, fh->fh_data_size);
  1005.         db_put_blk(ds, buf);
  1006.         return;
  1007. }
  1008.