开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数据库系统 > SQL Server > 查看源码
ind_ins.c
资源名称：gnusql-0.7b5.1.tar.gz　[点击查看]
上传用户：dgyhgb
上传日期：2007-01-07
资源大小：676k
文件大小：56k
源码类别：

SQL Server

开发平台：

Unix_Linux

ind_ins.c：源码内容
  1. /*
  2.  *  ind_ins.c  - Index Control Programm
  3.  *               functions dealing with insertion into an index
  4.  *               Kernel of GNU SQL-server 
  5.  *
  6.  * This file is a part of GNU SQL Server
  7.  *
  8.  *  Copyright (c) 1996, 1997, Free Software Foundation, Inc
  9.  *  Developed at the Institute of System Programming
  10.  *  This file is written by  Vera Ponomarenko
  11.  *
  12.  *  This program is free software; you can redistribute it and/or modify
  13.  *  it under the terms of the GNU General Public License as published by
  14.  *  the Free Software Foundation; either version 2 of the License, or
  15.  *  (at your option) any later version.
  16.  *
  17.  *  This program is distributed in the hope that it will be useful,
  18.  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  19.  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20.  *  GNU General Public License for more details.
  21.  *
  22.  *  You should have received a copy of the GNU General Public License
  23.  *  along with this program; if not, write to the Free Software
  24.  *  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  25.  *
  26.  *  Contacts:   gss@ispras.ru
  27.  *
  28.  */
  30. /* $Id: ind_ins.c,v 1.247 1997/04/15 11:45:41 vera Exp $ */
  32. #include "xmem.h"
  33. #include <assert.h>
  34. #include "destrn.h"
  35. #include "strml.h"
  36. #include "fdcltrn.h"
  38. struct des_field *d_f, *d_f2;
  39. u2_t *afn;
  40. u2_t k_n;
  41. u2_t seg_n;
  42. i4_t k2sz;
  43. i4_t inf_size;
  44. u2_t uniq_key;
  46. ARR_DECL     (thread_s,u2_t,no_static); /* declaration of dynamic stack/array 'thread_s'. */
  47. ARR_PROC_DECL(thread_s,u2_t,no_static); /* declaration of routines for it                 */
  49. #define FIND_LAST_KEY(asp,elsz,lkey,lkey2,keysz)
  50. {
  51.   char *pnt, *lastb;
  52.   u2_t n;
  53.   lastb = asp + ((struct ind_page *) asp)->ind_off;
  54.   pnt = asp + indphsize;
  55.   assert(pnt < lastb);
  56.   while (pnt < lastb)
  57.     {
  58.       n = t2bunpack (pnt);
  59.       pnt += size2b;
  60.       lkey = pnt;
  61.       keysz = kszcal (lkey, afn, d_f);
  62.       pnt += keysz + n * elsz;
  63.     }
  64.   lkey2 = pnt - elsz;
  65. }
  67. int
  68. check_ind_page (char *asp)
  69. {
  70.   char *cur_key, *prev_key, *a, *lastb;
  71.   u2_t n;
  72.   i4_t ksz, elsz;
  73.   struct ind_page *indph;
  75.   indph = (struct ind_page *) asp;
  76.   if (indph->ind_wpage == LEAF)
  77.     elsz = k2sz + inf_size;
  78.   else
  79.     elsz = k2sz + size2b;
  80.   lastb = asp + indph->ind_off;
  81.   a = asp + indphsize;
  82.   n = t2bunpack (a);
  83.   a += size2b;
  84.   prev_key = a;
  85.   ksz = kszcal (prev_key, afn, d_f);
  86.   a += ksz + n * elsz;
  87.   while (a < lastb)
  88.     {
  89.       n = t2bunpack (a);
  90.       a += size2b;
  91.       cur_key = a;
  92.       ksz = kszcal (cur_key, afn, d_f);
  93.       if (cmpkeys (k_n, afn, d_f, cur_key, prev_key) <= 0)
  94.         return -1;
  95.       a += ksz + n * elsz;
  96.       prev_key = cur_key;
  97.     }
  98.   return 0;
  99. }
  101. static int
  102. insrep (char *asp, char *lastb, char *key, char *key2,
  103.         i4_t elsz, char **bbeg, char **loc)
  104. {
  105.   char *a, *ckey;
  106.   u2_t n;
  107.   i4_t agsz = 0, keysz, ksz, l, l2;
  109.   keysz = kszcal (key, afn, d_f);
  110.   a = asp + indphsize;
  111.   for (; a < lastb; a += agsz)
  112.     {
  113.       *bbeg = a;
  114.       n = t2bunpack (a);
  115.       assert (n < BD_PAGESIZE / 2);
  116.       ckey = a + size2b;
  117.       ksz = kszcal (ckey, afn, d_f);
  118.       if ((l = cmpkeys (k_n, afn, d_f, ckey, key)) == 0)
  119. {
  120.   if (uniq_key == UNIQ)
  121.     return (0);
  122.   a += size2b + ksz;
  123.   for (; n != 0; n--, a += elsz)
  124.             {
  125.               if ((l2 = cmp2keys (d_f2->field_type, a, key2)) > 0)
  126.                 break;
  127.               assert (l2 != 0);      /* Tne second key isn't unique */
  128.             }
  129.   *loc = a;
  130.   return (elsz);
  131. }
  132.       else if (l > 0)
  133. {
  134.   *loc = a;
  135.   return (size2b + keysz + elsz);
  136. }
  137.       agsz = size2b + ksz + n * elsz;
  138.     }
  139.   *bbeg = a;
  140.   *loc = a;
  141.   return (size2b + keysz + elsz);
  142. }
  144. static void
  145. icp_insrec (char *key, char *key2, char *inf, i4_t infsz, char *beg,
  146.             char *loc, char *lastb, u2_t pn, char *asp, i4_t idm)
  147. {
  148.   char *src, *dst;
  149.   u2_t fs;
  150.   i4_t sz;
  152.   fs = lastb - loc;
  153.   if (beg == loc)
  154.     {
  155.       i4_t keysz;
  156.       keysz = kszcal (key, afn, d_f);
  157.       sz = size2b + keysz + k2sz + infsz;
  158.       if (asp != NULL)
  159. recmjform (SHF, seg_n, pn, idm, loc - asp, fs, NULL, -sz);
  160.       for (src = lastb - 1, dst = src + sz; fs != 0; fs--)
  161. *dst-- = *src--;
  162.       t2bpack (1, beg);
  163.       loc += size2b;
  164.       bcopy (key, loc, keysz);
  165.       loc += keysz;
  166.     }
  167.   else
  168.     {
  169.       sz = k2sz + infsz;
  170.       if (asp != NULL)
  171. recmjform (SHF, seg_n, pn, idm, loc - asp, fs, NULL, -sz);
  172.       for (src = lastb - 1, dst = src + sz; fs != 0; fs--)
  173. *dst-- = *src--;
  174.       if (asp != NULL)
  175. recmjform (OLD, seg_n, pn, idm, beg - asp, size2b, beg, 0);
  176.       mod_nels (1, beg);
  177.     }
  178.   bcopy (key2, loc, k2sz);
  179.   bcopy (inf, loc + k2sz, infsz);
  180. }
  182. static int
  183. repet1 (char *asp, char *bbeg, char *a, i4_t elsz, char *middleb, char **lkey,
  184.         char **lkey2, char **lnkey, char **lnkey2, i4_t *n1, u2_t *nels,
  185.         i4_t *lbeg, i4_t *lnbeg, i4_t *pr, char *frkey)
  186. {
  187.   char *lastb, *ckey;
  188.   i4_t ksz, agsz, n2;
  189.   u2_t n;
  191.   lastb = asp + ((struct ind_page *) asp)->ind_off;
  192.   ckey = *lnkey;
  193.   n = t2bunpack (bbeg);
  194.   assert (n < BD_PAGESIZE / 2);
  195.   ksz = kszcal (bbeg + size2b, afn, d_f);
  196.   if (bbeg != a)
  197.     { /* not new element */
  198.       char *b;
  199.       b = bbeg;
  200.       b += size2b + ksz;
  201.       for (; b != a; n--)
  202. b += elsz;
  203.       for (; n != 0; n--)
  204. if (a + elsz < middleb)
  205.   {
  206.     *lnkey2 = a;
  207.     a += elsz;
  208.   }
  209. else
  210.   goto m1;
  211.     }
  212.   for (; a < lastb;)
  213.     {
  214.       bbeg = a;
  215.       n = t2bunpack (a);
  216.       assert (n < BD_PAGESIZE / 2);
  217.       ksz = kszcal (a + size2b, afn, d_f);
  218.       agsz = size2b + ksz + n * elsz;
  219.       if (a + agsz < middleb)
  220. {
  221.   *lnkey = a + size2b;
  222.   a += agsz;
  223.   *lnkey2 = a - elsz;
  224. }
  225.       else
  226. break;
  227.     }
  228.   ckey = a + size2b;
  229.   agsz = size2b + ksz + elsz;
  230.   if (a + agsz < middleb)
  231.     {
  232.       *lnkey = a + size2b;
  233.       a += agsz;
  234.       *lnkey2 = a - elsz;
  235.       for (n--; n != 0; n--)
  236. if (a + elsz < middleb)
  237.   {
  238.     *lnkey2 = a;
  239.     a += elsz;
  240.   }
  241. else
  242.   break;
  243.     }
  244.   else
  245.     n = 0;
  246. m1:
  247.   n2 = lastb - a;
  248.   *n1 = a - asp;
  249.   *lnbeg = bbeg - asp;
  250.   if (n != 0)
  251.     {
  252.       ksz = kszcal (*lnkey, afn, d_f);
  253.       n2 += size2b + ksz;
  254.       *nels = n;
  255.       a += n * elsz;
  256.     }
  257.   else
  258.     *nels = 0;
  259.   for (; a < lastb; a += ksz + n * elsz)
  260.     {
  261.       bbeg = a;
  262.       n = t2bunpack (a);
  263.       assert (n < BD_PAGESIZE / 2);
  264.       a += size2b;
  265.       ckey = a;
  266.       ksz = kszcal (a, afn, d_f);
  267.     }
  268.   *lbeg = a - bbeg;
  269.   if (frkey != NULL)
  270.     if (cmpkeys (k_n, afn, d_f, ckey, frkey) == 0)
  271.       {
  272. *pr = 0;
  273. n2 -= ksz + size2b;
  274.       }
  275.     else
  276.       *pr = 1;
  277.   *lkey = ckey;
  278.   *lkey2 = lastb - elsz;
  279.   return (n2);
  280. }
  282. static int
  283. repttn (char *mas, char *lastb, i4_t elsz, char *middleb, char **lkey,
  284.         char **lkey2, char **lnkey, char **lnkey2, i4_t *n1,
  285.         u2_t *nels, i4_t *lbeg, i4_t *lnbeg, i4_t *pr, char *frkey)
  286. {
  287.   char *a, *bbeg, *ckey;
  288.   i4_t agsz = 0, ksz, n2;
  289.   u2_t n;
  291.   a = mas;
  292.   do      
  293.     {
  294.       n = t2bunpack (a);
  295.       assert (n < BD_PAGESIZE / 2);
  296.       bbeg = a - agsz;
  297.       ksz = kszcal (a + size2b, afn, d_f);
  298.       agsz = size2b + ksz + n * elsz;
  299.       if (a + agsz > middleb)
  300. break;
  301.       a += agsz;
  302.     }
  303.   while( a < lastb);
  304.   *lnkey = bbeg + size2b;
  305.   *lnkey2 = a - elsz;
  306.   *lnbeg = bbeg - mas;
  307.   bbeg = a;
  308.   agsz = size2b + ksz + elsz;
  309.   if (a + agsz < middleb)
  310.     {
  311.       *lnkey = a + size2b;
  312.       *lnbeg = a - mas;
  313.       a += agsz;
  314.       *lnkey2 = a - elsz;
  315.       for (n--; n != 0; n--)
  316. if (a + elsz < middleb)
  317.   {
  318.     *lnkey2 = a;
  319.     a += elsz;
  320.   }
  321. else
  322.   break;
  323.     }
  324.   else
  325.     n = 0;
  326.   *n1 = a - mas;
  327.   n2 = lastb - a;
  328.   if (n != 0)
  329.     {
  330.       n2 += size2b + ksz;
  331.       *nels = n;
  332.       a += n * elsz;
  333.     }
  334.   else
  335.     *nels = 0;
  336.   for (; a < lastb; a += ksz + n * elsz)
  337.     {
  338.       bbeg = a;
  339.       n = t2bunpack (a);
  340.       assert (n < BD_PAGESIZE / 2);
  341.       a += size2b;
  342.       ksz = kszcal (a, afn, d_f);
  343.     }
  344.   ckey = bbeg + size2b;
  345.   *lbeg = a - bbeg;
  346.   if (frkey != NULL)
  347.     {
  348.       if (cmpkeys (k_n, afn, d_f, ckey, frkey) == 0)
  349. {
  350.   *pr = 0;
  351.   n2 -= ksz + size2b;
  352. }
  353.       else
  354. *pr = 1;
  355.     }
  356.   *lkey = ckey;
  357.   *lkey2 = lastb - elsz;
  358.   return (n2);
  359. }
  361. static char *
  362. pereliv (char *asp, i4_t n, u2_t nels, char *key, char *mas, i4_t massz)
  363.                 /* n - a number of bytes from the first page */
  364.       /* nels - element number from the first page */
  365. {
  366.   char *a, *b, *c, *lastb;
  368.   lastb = asp + ((struct ind_page *) asp)->ind_off;
  369.   for (b = lastb - 1, a = b + n, c = asp + indphsize; b >= c;)
  370.     *a-- = *b--;
  371.   a = asp + indphsize;
  372.   if (nels != 0)
  373.     {
  374.       i4_t ksz;
  375.       t2bpack (nels, a);
  376.       a += size2b;
  377.       ksz = kszcal (key, afn, d_f);
  378.       bcopy (key, a, ksz);
  379.       a += ksz;
  380.     }
  381.   bcopy (mas, a, massz);
  382.   return (a + massz);
  383. }
  385. static void
  386. per22 (u2_t pn, u2_t rbrpn, i4_t n1, i4_t n2, u2_t nels, i4_t lbeg, i4_t lnbeg,
  387.        i4_t pr, i4_t prpg, i4_t sz, char *key, char *key2, char *inf, char *lnkey,
  388.        i4_t offbeg, i4_t offloc)         /* if pr==0 then lastkey==frkey */
  389. {
  390.   char *a, *lastb, *asp, *aspr, *end1;
  391.   u2_t fnels;  /* element number of the first aggregate of a right brother */
  392.   struct ind_page *indph, *indphr;
  393.   i4_t idm, idmr;
  394.   struct A pg, pgr;
  396.   asp = getwl (&pg, seg_n, pn); /* get pn without lock */
  397.   aspr = getwl (&pgr, seg_n, rbrpn); /* get pn without lock */
  398.   indph = (struct ind_page *) asp;
  399.   indphr = (struct ind_page *) aspr;
  400.   idm = ++((struct p_head *) asp)->idmod;
  401.   idmr = ++((struct p_head *) aspr)->idmod;
  402.   if (pr == 0)
  403.     recmjform (OLD, seg_n, rbrpn, idmr, indphsize, size2b, aspr + indphsize, 0);
  404.   fnels = t2bunpack (aspr + indphsize);
  405.   if (nels != 0)
  406.     {
  407.       recmjform (OLD, seg_n, pn, idm, lnbeg, size2b, asp + lnbeg, 0);
  408.       mod_nels ((-nels), asp + lnbeg);
  409.     } 
  410.   lastb = asp + indph->ind_off;
  411.   end1 = asp + n1;
  412.   recmjform (OLD, seg_n, pn, idm, n1, lastb - end1, end1, 0);
  413.   recmjform (SHF, seg_n, rbrpn, idmr, n2 + indphsize,
  414.              indphr->ind_off - indphsize, NULL, -n2);
  415.   a = pereliv (aspr, n2, nels, lnkey, end1, indph->ind_off - n1);
  416.   if (pr == 0)
  417.     {
  418.       if (lbeg > n2)
  419. lbeg = n2;
  420.       mod_nels (fnels, a - lbeg);
  421.       if (lbeg == n2)
  422. {
  423.           char *b;
  424.           i4_t size;
  425.   b = a + size2b + kszcal (aspr + indphsize + size2b, afn, d_f);
  426.           size = aspr + indphr->ind_off + n2 - b;
  427.           bcopy (b, a, size);
  428. }
  429.     }
  430.   if (prpg == 1)
  431.     { /* An insertion in the first page */
  432.       icp_insrec (key, key2, inf, inf_size, asp + offbeg,
  433.                   asp + offloc, end1, pn, asp, idm);
  434.       n1 += sz;
  435.     }
  436.   else /* An insertion in the right brother page */
  437.     icp_insrec (key, key2, inf, inf_size, aspr + offbeg,
  438.                 aspr + offloc, a, rbrpn, aspr, idmr);
  439.   a = (char *) &indph->ind_off;
  440.   recmjform (OLD, seg_n, pn, idm, a - asp, size2b, a, 0);
  441.   indph->ind_off = n1;
  442.   a = (char *) &indphr->ind_off;
  443.   recmjform (OLD, seg_n, rbrpn, idmr, a - aspr, size2b, a, 0);
  444.   indphr->ind_off += n2;
  445.   assert (check_ind_page (asp) == 0);
  446.   putwul (&pg, 'm'); /* put page without unlock */
  447.   assert (check_ind_page (aspr) == 0);
  448.   putwul (&pgr, 'm');
  449. }
  451. static int
  452. rep_2_3 (char *mas, i4_t massz, i4_t elsz, char *aspr, i4_t *n1, u2_t * nels,
  453.          i4_t *lbeg, i4_t *lnbeg, char **nkey, char **nkey2, i4_t *pr)
  454. {
  455.   char *middleb, *frkey, *lkey, *lkey2, *lnkey, *lnkey2;
  456.   i4_t off, n2, middle;
  458.   off = ((struct ind_page *) aspr)->ind_off;
  459.   middleb = mas + (massz + off - indphsize) / 3;
  460.   frkey = aspr + indphsize + size2b;
  461.   n2 = repttn (mas, mas + massz, elsz, middleb, &lkey, &lkey2, &lnkey,
  462.                &lnkey2, n1, nels, lbeg, lnbeg, pr, frkey);
  463.   middle = (n2 + off - indphsize) / 2;
  464.   if (off - middle > indphsize)
  465.     {
  466.       char *a;
  467.       u2_t n, agsz = 0;
  468.       middleb = aspr + ((n2 + off) / 2 - n2);
  469.       for (a = aspr + indphsize; a + agsz < middleb;)
  470. {
  471.   a += agsz;
  472.   n = t2bunpack (a);
  473.           assert (n < BD_PAGESIZE / 2);
  474.   a += size2b;
  475.   agsz = kszcal (a, afn, d_f) + n * elsz;
  476. }
  477.       *nkey = a;
  478.       *nkey2 = a + agsz - elsz;
  479.       n2 = a + agsz - aspr;
  480.       if (n2 == indphsize)
  481. n2 = 0;
  482.     }
  483.   else
  484.     n2 = 0;
  485.   return (n2);
  486. }
  488. static int
  489. crnlev (struct A *pg, char *mas, char *lastb, i4_t wpage)
  490. { /* a creation of a new level */
  491.   char *a, *b, *middleb, *asp;
  492.   char *lnkey, *lnkey2, *lkey, *lkey2, *inf1, *inf2;
  493.   i4_t n1, lbeg, lnbeg, pr, ksz, size, elsz;
  494.   u2_t newpn1, newpn2, nels, offn;
  495.   struct A pgn;
  496.   struct ind_page *indph;
  497.   i4_t idm;
  499.   if (wpage == LEAF)
  500.     elsz = k2sz + inf_size;
  501.   else
  502.     elsz = k2sz + size2b;
  503.   middleb = mas + (lastb - mas) / 2;
  504.   repttn (mas, lastb, elsz, middleb, &lkey, &lkey2, &lnkey,
  505.           &lnkey2, &n1, &nels, &lbeg, &lnbeg, &pr, NULL);
  506.   if (lenforce ()< 0)
  507.     {
  508.       putwul (pg, 'n');
  509.       return (-1);
  510.     }
  511.   newpn1 = getempt (seg_n);
  512.   asp = getnew (&pgn, seg_n, newpn1); /* get new page */
  513.   indph = (struct ind_page *) asp;
  514.   bcopy (mas, asp + indphsize, n1);
  515.   indph->ind_off = n1 + indphsize;
  516.   if (nels != 0)
  517.     mod_nels ((-nels), asp + lnbeg + indphsize);
  518.   newpn2 = getempt (seg_n);
  519.   indph->ind_nextpn = newpn2;
  520.   indph->ind_wpage = wpage;
  521.   offn = indph->ind_off;
  522.   assert (check_ind_page (asp) == 0);
  523.   putwul (&pgn, 'm');
  524.   asp = getnew (&pgn, seg_n, newpn2); /* get new page */
  525.   indph = (struct ind_page *) asp;
  526.   a = asp + indphsize;
  527.   ksz = kszcal (lnkey, afn, d_f);
  528.   if (nels != 0)
  529.     {
  530.       /*      write_key (nels, a, lnkey, ksz);*/
  531.       t2bpack (nels, a);
  532.       a += size2b;
  533.       bcopy (lnkey, a, ksz);
  534.       a += ksz;
  535.     }
  536.   b = mas + n1;
  537.   size = lastb - b;
  538.   bcopy (b, a, size);
  539.   a += size;
  540.   indph->ind_nextpn = (u2_t) ~ 0;
  541.   indph->ind_off = a - asp;
  542.   indph->ind_wpage = wpage;
  543.   offn = indph->ind_off;
  544.   assert (check_ind_page (asp) == 0);
  545.   putwul (&pgn, 'm');
  546.   inf1 = (char *) &newpn1;
  547.   inf2 = (char *) &newpn2;
  548.   asp = pg->p_shm;
  549.   indph = (struct ind_page *) asp;
  550.   idm = ++((struct p_head *) asp)->idmod;
  551.   a = asp + sizeof (struct p_head);
  552.   b = asp + indph->ind_off;
  553.   recmjform (OLD, seg_n, pg->p_pn, idm, a - asp, b - a, a, 0);
  554.   a = asp + indphsize + size2b;
  555.   bcopy (lnkey, a, ksz);
  556.   a += ksz;
  557.   bcopy (lnkey2, a, k2sz);
  558.   a += k2sz;
  559.   t2bpack (newpn1, a);
  560.   a += size2b;
  561.   if (cmpkeys (k_n, afn, d_f, lkey, lnkey) == 0)
  562.     nels = 2;
  563.   else
  564.     {
  565.       nels = 1;
  566.       t2bpack (nels, a);
  567.       a += size2b;
  568.       ksz = kszcal (lkey, afn, d_f);
  569.       bcopy (lkey, a, ksz);
  570.       a += ksz;
  571.     }
  572.   t2bpack (nels, asp + indphsize);
  573.   bcopy (lkey2, a, k2sz);
  574.   a += k2sz;
  575.   t2bpack (newpn2, a);
  576.   a += size2b;
  577.   indph->ind_nextpn = (u2_t) ~ 0;
  578.   indph->ind_off = a - asp;
  579.   indph->ind_wpage = IROOT;
  580.   assert (check_ind_page (asp) == 0);
  581.   putwul (pg, 'm');
  582.   return (0);
  583. }
  585. static i4_t rbrup (u2_t pn, u2_t rbrpn, char *mas, i4_t massz,
  586.                   char *last_key, char *last_k2);
  588. static char *
  589. findkey (char *asp, char *key, char *key2, i4_t elsz, char **loc)
  590. {
  591.   char *a, *lastb, *bbeg;
  592.   u2_t n;
  593.   i4_t ksz;
  595.   lastb = asp + ((struct ind_page *) asp)->ind_off;
  596.   for (a = asp + indphsize; a < lastb; a += ksz + n * elsz)
  597.     {
  598.       bbeg = a;
  599.       n = t2bunpack (a);
  600.       a += size2b;
  601.       ksz = kszcal (a, afn, d_f);
  602.       if (cmpkeys (k_n, afn, d_f, a, key) == 0)
  603. {
  604.   a += ksz;
  605.   for (; n != 0; n--, a += elsz)
  606.     if (cmp2keys (d_f2->field_type, a, key2) == 0)
  607.       {
  608. *loc = a;
  609. return (bbeg);
  610.       }
  611. }
  612.     }
  613.   return (NULL);
  614. }
  616. static int
  617. div_upmod (char *lkey, char *lkey2, char *lnkey,
  618.            char *lnkey2, u2_t pn, u2_t * newpn)
  619. {
  620.   char *asp, *a, *inf, *lastb;
  621.   char *beg, *loc;
  622.   i4_t elsz, insz, off;
  623.   struct ind_page *indph;
  624.   struct A pg;
  625.   i4_t idm;
  626.   char ninf[size2b];
  628.   t2bpack (pn, ninf);
  629.   pn = *(--thread_s.u);
  630.   asp = getwl (&pg, seg_n, pn); /* get pn without lock */
  631.   indph = (struct ind_page *) asp;
  632.   elsz = k2sz + size2b;
  633.   beg = findkey (asp, lkey, lkey2, elsz, &loc);
  634.   inf = loc + k2sz;
  635.   off = indph->ind_off;
  636.   lastb = asp + off;
  637.   insz = insrep (asp, lastb, lnkey, lnkey2, elsz, &beg, &loc);
  638.   assert (insz != 0);
  639.   if (off + insz > BD_PAGESIZE)
  640.     {
  641.       char *mas, *d;
  642.       i4_t massz, ans;
  643.       massz = off + insz - indphsize;
  644.       mas = (char *) xmalloc (massz);
  645.       d = asp + indphsize;
  646.       bcopy (d, mas, off - indphsize);
  647.       *newpn = getempt (seg_n);
  648.       t2bpack (*newpn, mas + (inf - d));
  649.       beg = mas + (beg - d);
  650.       loc = mas + (loc - d);
  651.       lastb = mas + massz - insz;
  652.       icp_insrec (lnkey, lnkey2, ninf, size2b, beg, loc, lastb, 0, NULL, 0);
  653.       if (indph->ind_wpage != IROOT)
  654. {
  655.           char last_key[BD_PAGESIZE];
  656.           char last_k2[BD_PAGESIZE];
  657.           u2_t rbrpn, keysz = 0 ;
  658.           
  659.           FIND_LAST_KEY (asp, elsz, lkey, lkey2, keysz);
  660.           assert (keysz != 0 );
  661.           bcopy (lkey, last_key, keysz);
  662.           bcopy (lkey2, last_k2, k2sz);
  663.           rbrpn = indph->ind_nextpn;
  664.   putwul (&pg, 'n');
  665.   ans = rbrup (pn, rbrpn, mas, massz, last_key, last_k2);
  666. }
  667.       else
  668.         ans = crnlev (&pg, mas, lastb + insz, BTWN);
  669.       if (ans < 0)
  670. emptypg (seg_n, *newpn, 'n');
  671.       xfree ((void *) mas);
  672.       return (ans);
  673.     }
  674.   upunlock ();
  675.   if (lenforce ()< 0)
  676.     {
  677.       putwul (&pg, 'n');
  678.       return (-1);
  679.     }
  680.   *newpn = getempt (seg_n);
  681.   idm = ++((struct p_head *) asp)->idmod;
  682.   recmjform (OLD, seg_n, pn, idm, inf - asp, size2b, inf, 0);
  683.   t2bpack (*newpn, inf);
  684.   icp_insrec (lnkey, lnkey2, ninf, size2b, beg, loc, lastb, pn, asp, idm);
  685.   a = (char *) &indph->ind_off;
  686.   recmjform (OLD, seg_n, pn, idm, a - asp, size2b, a, 0);
  687.   indph->ind_off += insz;
  688.   assert (check_ind_page (asp) == 0);
  689.   putwul (&pg, 'm');
  690.   return (0);
  691. }
  693. static int
  694. divsn (u2_t pn, char *mas, i4_t massz, u2_t nextpn,
  695.        i4_t wpage, char *last_key, char *last_key2)
  696. {
  697.   char *lastb, *a, *b, *middleb, *asp;
  698.   i4_t n1, lbeg, lnbeg, pr, elsz;
  699.   char *lkey, *lkey2, *lnkey, *lnkey2;
  700.   u2_t nels, newpn;
  701.   i4_t idm;
  702.   struct ind_page *indph;
  703.   struct A pg;
  705.   lastb = mas + massz;
  706.   middleb = mas + massz / 2;
  707.   if (wpage == LEAF)
  708.     elsz = k2sz + inf_size;
  709.   else
  710.     elsz = k2sz + size2b;
  711.   repttn (mas, lastb, elsz, middleb, &lkey, &lkey2, &lnkey, &lnkey2,
  712.           &n1, &nels, &lbeg, &lnbeg, &pr, (char *) NULL);
  713.   if (div_upmod (last_key, last_key2, lnkey, lnkey2, pn, &newpn) < 0)
  714.     return (-1);
  715.   asp = getwl (&pg, seg_n, pn); /* get pn without lock */
  716.   indph = (struct ind_page *) asp;
  717.   idm = ++((struct p_head *) asp)->idmod;
  718.   a = asp + sizeof (struct p_head);
  719.   b = asp + indph->ind_off;
  720.   recmjform (OLD, seg_n, pn, idm, a - asp, b - a, a, 0);
  721.   bcopy (mas, asp + indphsize, n1);
  722.   if (nels != 0) 
  723.     mod_nels ((-nels), asp + lnbeg);
  724.   indph->ind_off = n1 + indphsize;
  725.   indph->ind_nextpn = newpn;
  726.   assert (check_ind_page (asp) == 0);
  727.   putwul (&pg, 'm');
  728.   asp = getnew (&pg, seg_n, newpn); /* get newpn without lock */
  729.   indph = (struct ind_page *) asp;
  730.   lkey = lastb - lbeg + size2b;
  731.   indph->ind_off = indphsize;
  732.   b = pereliv (asp, 0, nels, lkey, mas + n1, massz - n1);
  733.   indph->ind_off = b - asp;
  734.   indph->ind_nextpn = nextpn;
  735.   indph->ind_wpage = wpage;
  736.   assert (check_ind_page (asp) == 0);
  737.   putwul (&pg, 'm'); /* put page without unlock */
  738.   return (0);
  739. }
  741. static int
  742. mlrep1 (char *asp, char *key, char *key2, char *nkey, i4_t *orbeg,
  743.         i4_t *orloc, i4_t *oibeg, i4_t *oiloc, i4_t *sz)
  744. {
  745.   i4_t remsz, elsz, offbef;
  746.   char *rbeg, *rloc;
  748.   elsz = k2sz + size2b;
  749.   remsz = remrep (asp, key, key2, elsz, &rbeg, &rloc, &offbef);
  750.   *orbeg = rbeg - asp;
  751.   *orloc = rloc - asp;
  752.   if (cmpkeys (k_n, afn, d_f, key, nkey) == 0)
  753.     {
  754.       *oibeg = *orbeg;
  755.       *oiloc = *orloc;
  756.       *sz = remsz;
  757.     }
  758.   else
  759.     {
  760.       char *a;
  761.       u2_t n;
  762.       a = asp + offbef;
  763.       *oibeg = offbef;
  764.       n = t2bunpack (a);
  765.       assert (n < BD_PAGESIZE / 2);
  766.       a += size2b;
  767.       *oiloc = *oibeg;
  768.       if (cmpkeys (k_n, afn, d_f, a, nkey) == 0)
  769.         {
  770.           *oiloc += size2b + kszcal (nkey, afn, d_f) + n * elsz;
  771.           *sz = elsz;
  772.         }
  773.       else
  774.         {
  775.           *oibeg = *oiloc = *orbeg;
  776.           *sz = size2b + kszcal (nkey, afn, d_f) + elsz;
  777.         }
  778.     }
  779.   return (remsz);
  780. }
  782. static int
  783. upmod_2_3 (char *lkey, char *lkey2, char *lnkey, char *lnkey2,
  784.            char *nkey, char *nkey2, u2_t * newpn)
  785. { /* a repetition of a modification of an uplevel for a division 2 on 3 */
  786.   char *a, *asp, *lastb;
  787.   u2_t uppn;
  788.   struct ind_page *indph;
  789.   struct A pg;
  790.   i4_t rbeg, rloc, ibeg1, iloc1, ibeg2, iloc2;
  791.   i4_t remsz, sz1, sz2, elsz, ksz_lnkey, ksz_nkey, off, dopsz;
  792.   char inf1[size2b], inf2[size2b], *beg, *loc;
  793.   i4_t idm;
  795.   uppn = *(--thread_s.u);
  796.   asp = getwl (&pg, seg_n, uppn); /* get pn without lock */
  797.   indph = (struct ind_page *) asp;
  798.   elsz = k2sz + size2b;
  799.   remsz = mlrep1 (asp, lkey, lkey2, lnkey, &rbeg, &rloc, &ibeg1, &iloc1, &sz1);
  800.   ksz_nkey = kszcal (nkey, afn, d_f);
  801.   ksz_lnkey = kszcal (lnkey, afn, d_f);
  802.   if (cmpkeys (k_n, afn, d_f, lnkey, nkey) == 0)
  803.     {
  804.       sz2 = elsz;
  805.       ibeg2 = ibeg1;
  806.       if (ibeg1 == iloc1)
  807.         iloc2 = ibeg1 + sz1 + elsz;
  808.       else
  809.         iloc2 = iloc1 + elsz;
  810.     }
  811.   else
  812.     {
  813.       sz2 = size2b + ksz_nkey + elsz;
  814.       ibeg2 = iloc2 = iloc1 + sz1;
  815.     }
  816.   bcopy (asp + rloc + k2sz, inf1, size2b);
  817.   off = indph->ind_off;
  818.   dopsz = sz1 + sz2 - remsz;
  819.   if (off + dopsz > BD_PAGESIZE)
  820.     {
  821.       char *mas;
  822.       i4_t massz, ans, size;
  823.       
  824.       lastb = asp + off;
  825.       massz = off + dopsz - indphsize;
  826.       mas = (char *) xmalloc (massz);
  827.       size = off - indphsize;
  828.       bcopy (asp + indphsize, mas, size);
  829.       lastb = mas + size;
  830.       beg = mas + rbeg - indphsize;
  831.       loc = mas + rloc - indphsize; 
  832.       icp_remrec (beg, loc, remsz, lastb, elsz, 0, NULL, 0);
  833.       lastb -= remsz;
  834.       beg = mas + ibeg1 - indphsize;
  835.       loc = mas + iloc1 - indphsize;
  836.       icp_insrec (lnkey, lnkey2, inf1, size2b, beg, loc, lastb, 0, NULL, 0);
  837.       lastb += sz1;
  838.       *newpn = getempt (seg_n);
  839.       beg = mas + ibeg2 - indphsize;
  840.       loc = mas + iloc2 - indphsize;
  841.       t2bpack (*newpn, inf2);
  842.       icp_insrec (nkey, nkey2, inf2, size2b, beg, loc, lastb, 0, NULL, 0);
  843.       if (indph->ind_wpage != IROOT)
  844. {
  845.           char last_key[BD_PAGESIZE];
  846.           char last_k2[BD_PAGESIZE];
  847.           u2_t rbrpn, keysz = 0 ;
  848.           
  849.           if (rloc + elsz != off)     /* lkey isn't the last key in pn */
  850.             {
  851.               FIND_LAST_KEY (asp, elsz, lkey, lkey2, keysz);
  852.             }
  853.           else
  854.             keysz = kszcal (lkey, afn, d_f);
  855.           assert ( keysz != 0 ) ;
  856.           bcopy (lkey, last_key, keysz);
  857.           bcopy (lkey2, last_k2, k2sz);
  858.   rbrpn = indph->ind_nextpn;
  859.   putwul (&pg, 'n');
  860.   ans = rbrup (uppn, rbrpn, mas, massz, last_key, last_k2);
  861. }
  862.       else
  863.         ans = crnlev (&pg, mas, mas + massz, BTWN);
  864.       if (ans < 0)
  865. emptypg (seg_n, *newpn, 'n');
  866.       xfree ((void *) mas);
  867.       return (ans);
  868.     }
  869.   else if (rloc + elsz == off && indph->ind_wpage != IROOT)
  870.     {
  871.       putwul (&pg, 'n');
  872.       if (mlreddi (lkey, lkey2, nkey, nkey2, uppn) < 0)
  873.         return (-1);
  874.       asp = getwl (&pg, seg_n, uppn);
  875.     }
  876.   else
  877.     {
  878.       upunlock ();
  879.       if (lenforce ()< 0)
  880. {
  881.   putwul (&pg, 'n');
  882.   return (-1);
  883. }
  884.     }
  885.   *newpn = getempt (seg_n);
  886.   idm = ++((struct p_head *) asp)->idmod;
  887.   lastb = asp + off;
  888.   icp_remrec (asp + rbeg, asp + rloc, remsz, lastb, elsz, uppn, asp, idm);
  889.   lastb -= remsz;
  890.   beg = asp + ibeg1;
  891.   loc = asp + iloc1;
  892.   icp_insrec (lnkey, lnkey2, inf1, size2b, beg, loc, lastb, uppn, asp, idm);
  893.   lastb += sz1;
  894.   insrep (asp, lastb, nkey, nkey2, elsz, &beg, &loc);
  895.   t2bpack (*newpn, inf2);
  896.   icp_insrec (nkey, nkey2, inf2, size2b, beg, loc, lastb, uppn, asp, idm);
  897.   a = (char *) &indph->ind_off;
  898.   recmjform (OLD, seg_n, uppn, idm, a - asp, size2b, a, 0);
  899.   indph->ind_off += dopsz;
  900.   assert (check_ind_page (asp) == 0);
  901.   putwul (&pg, 'm');
  902.   return (0);
  903. }
  905. static void
  906. per_2_3 (u2_t pn, u2_t newpn, u2_t rbrpn, char *mas, i4_t massz, i4_t n1,
  907.          i4_t n2, u2_t nels, i4_t pr, i4_t lbeg, i4_t lnbeg, i4_t wpage)
  908. {
  909.   char *a, *b, *b1, *asp, *aspn, *lkey;
  910.   struct ind_page *indph, *indphn;
  911.   i4_t idm;
  912.   struct A pg, pgn;
  913.   i4_t size;
  915.   asp = getwl (&pg, seg_n, pn); /* get pn without lock */
  916.   indph = (struct ind_page *) asp;
  917.   idm = ++((struct p_head *) asp)->idmod;
  918.   a = asp + sizeof (struct p_head);
  919.   b = asp + indph->ind_off;
  920.   recmjform (OLD, seg_n, pn, idm, a - asp, b - a, a, 0);
  921.   bcopy (mas, asp + indphsize, n1);
  922.   indph->ind_off = n1 + indphsize;
  923.   if (nels != 0)
  924.     mod_nels ((-nels), asp + lnbeg);
  925.   indph->ind_nextpn = newpn;
  926.   assert (check_ind_page (asp) == 0);
  927.   putwul (&pg, 'm');
  928.   aspn = getnew (&pgn, seg_n, newpn); /* get new page */
  929.   indphn = (struct ind_page *) aspn;
  930.   indphn->ind_off = indphsize;
  931.   lkey = mas + lnbeg + size2b;
  932.   b = pereliv (aspn, 0, nels, lkey, mas + n1, massz - n1);
  933.   asp = getwl (&pg, seg_n, rbrpn); /* get rbrpn without lock */
  934.   indph = (struct ind_page *) asp;
  935.   idm = ++((struct p_head *) asp)->idmod;
  936.   a = asp + sizeof (struct p_head);
  937.   b1 = asp + indph->ind_off;
  938.   recmjform (OLD, seg_n, rbrpn, idm, a - asp, b1 - a, a, 0);
  939.   a = asp + indphsize;
  940.   if (pr == 0)
  941.     {
  942.       u2_t fnels;
  943.       fnels = t2bunpack (a);
  944.       a += size2b;
  945.       a += kszcal (a, afn, d_f);
  946.       mod_nels (fnels, b - lbeg);
  947.     }
  948.   size = asp + n2 - a;
  949.   bcopy (a, b, size);
  950.   b += size;
  951.   bcopy (asp + n2, asp + indphsize, indph->ind_off - n2);
  952.   indphn->ind_off = b - aspn;
  953.   indphn->ind_nextpn = rbrpn;
  954.   indphn->ind_wpage = wpage;
  955.   assert (check_ind_page (aspn) == 0);
  956.   putwul (&pgn, 'm');
  957.   indph->ind_off -= n2 - indphsize;
  958.   assert (check_ind_page (asp) == 0);
  959.   putwul (&pg, 'm');
  960. }
  962. static int
  963. rbrnup (u2_t pn, struct A *pgr, char *mas, i4_t massz,
  964.         char *last_key, char *last_k2)
  965. {  /* need rbrpn and a new page for a deletion and an insertion */
  966.   i4_t elsz, n1, n2, pr, lbeg, lnbeg;
  967.   char *lnkey, *lnkey2, *nkey, *nkey2, *aspr;
  968.   u2_t newpn, nels;
  969.   char newkey[BD_PAGESIZE];
  970.   char newk2[BD_PAGESIZE];  
  972.   aspr = pgr->p_shm;
  973.   elsz = k2sz + size2b;
  974.   n2 = rep_2_3 (mas, massz, elsz, aspr, &n1, &nels,
  975.                 &lbeg, &lnbeg, &nkey, &nkey2, &pr);
  976.   if (n2 == 0)
  977.     {
  978.       putwul (pgr, 'n');
  979.       return (divsn (pn, mas, massz, pgr->p_pn, BTWN, last_key, last_k2));
  980.     }
  981.   bcopy ( nkey, newkey, kszcal (nkey, afn, d_f));
  982.   bcopy ( nkey2, newk2, k2sz);
  983.   putwul (pgr, 'n');
  984.   lnkey = mas + lnbeg + size2b;
  985.   lnkey2 = mas + n1 - elsz;
  986.   if (upmod_2_3 (last_key, last_k2, lnkey, lnkey2, newkey, newk2, &newpn) < 0)
  987.     return (-1);
  988.   per_2_3 (pn, newpn, pgr->p_pn, mas, massz, n1, n2, nels, pr, lbeg, lnbeg, BTWN);
  989.   return (0);
  990. }
  992. static int
  993. rbrup (u2_t pn, u2_t rbrpn, char *mas, i4_t massz,
  994.        char *last_key, char *last_k2)
  995. /* rbrobr with a deletion and an insertion */
  996. {
  997.   i4_t off2, dopsz, n1, lbeg, lnbeg, pr, rfreesz, n2;
  998.   char *frkey, *middleb, *lkey, *lkey2, *lnkey, *lnkey2, *asp, *a, *b;
  999.   u2_t nels, fnels;
  1000.   struct A pg;
  1001.   struct ind_page *indph;
  1002.   i4_t idm;
  1004.   if (rbrpn == (u2_t) ~ 0)
  1005.     return (divsn (pn, mas, massz, (u2_t) ~ 0, BTWN, last_key, last_k2));
  1006.   if ((asp = getpg (&pg, seg_n, rbrpn, 's')) == NULL)
  1007.     return ( -1);
  1008.   thread_s_put (rbrpn);
  1009.   frkey = asp + indphsize + size2b;
  1010.   off2 = ((struct ind_page *) asp)->ind_off;
  1011.   dopsz = massz + indphsize - BD_PAGESIZE;
  1012.   rfreesz = BD_PAGESIZE - off2;
  1013.   if (rfreesz < dopsz)
  1014.     return (rbrnup (pn, &pg, mas, massz, last_key, last_k2));
  1015.   /* A location is enough in the right brother */
  1016.   middleb = mas + (massz + off2 - indphsize) / 2;
  1017.   n2 = repttn (mas, mas + massz, k2sz + size2b, middleb, &lkey, &lkey2,
  1018.                &lnkey, &lnkey2, &n1, &nels, &lbeg, &lnbeg, &pr, frkey);
  1019.   if (n2 > rfreesz)
  1020.     return (rbrnup (pn, &pg, mas, massz, last_key, last_k2));
  1021.   putwul (&pg, 'n');
  1022.   if (mlreddi (last_key, last_k2, lnkey, lnkey2, pn) < 0)
  1023.     return (-1);
  1024.   asp = getwl (&pg, seg_n, pn);   /* get pn without lock */
  1025.   indph = (struct ind_page *) asp;
  1026.   idm = ++((struct p_head *) asp)->idmod;
  1027.   a = asp + sizeof (struct p_head);
  1028.   b = asp + indph->ind_off;
  1029.   recmjform (OLD, seg_n, pn, idm, a - asp, b - a, a, 0);
  1030.   bcopy (mas, asp + indphsize, n1);
  1031.   indph->ind_off = indphsize + n1;
  1032.   if (nels != 0)
  1033.     mod_nels ((-nels), asp + lnbeg);
  1034.   assert (check_ind_page (asp) == 0);
  1035.   putwul (&pg, 'm');
  1036.   
  1037.   asp = getwl (&pg, seg_n, rbrpn);/* get rbrpn without lock */
  1038.   indph = (struct ind_page *) asp;
  1039.   idm = ++((struct p_head *) asp)->idmod;
  1040.   a = asp + sizeof (struct p_head);
  1041.   b = asp + indph->ind_off;
  1042.   recmjform (OLD, seg_n, rbrpn, idm, a - asp, b - a, a, 0);
  1043.   fnels = t2bunpack (asp + indphsize);
  1044.   lkey = mas + lnbeg + size2b;
  1045.   a = pereliv (asp, n2, nels, lkey, mas + n1, massz - n1);
  1046.   if (pr == 0)
  1047.     mod_nels (fnels, a - lbeg);
  1048.   indph->ind_off += n2;
  1049.   assert (check_ind_page (asp) == 0);
  1050.   putwul (&pg, 'm'); /* put page without unlock */
  1051.   return (0);
  1052. }
  1054. static int
  1055. rbrnew (struct A *pg, struct A *pgr, i4_t sz, char *key,
  1056.         char *key2, char *inf, i4_t ibeg, i4_t iloc)
  1057.      /* a division 2 on 3 with an insertion at the last level */
  1058. {
  1059.   char *mas, *lastb, *beg, *loc;
  1060.   i4_t massz, n1, n2, lbeg, lnbeg, pr, elsz, ans, size;
  1061.   char *lkey, *lkey2, *nkey, *nkey2, *asp, *aspr;
  1062.   u2_t newpn, nels;
  1063.   
  1064.   asp = pg->p_shm;
  1065.   aspr = pgr->p_shm;
  1066.   size = ((struct ind_page *) asp)->ind_off - indphsize;
  1067.   massz = size + sz;
  1068.   mas = (char *) xmalloc (massz);
  1069.   bcopy (asp + indphsize, mas, size);
  1070.   beg = mas + ibeg - indphsize;
  1071.   loc = mas + iloc - indphsize;
  1072.   lastb = mas + size;
  1073.   icp_insrec (key, key2, inf, inf_size, beg, loc, lastb, 0, NULL, 0);
  1074.   elsz = k2sz + inf_size;
  1075.   putwul (pg, 'n');
  1076.   n2 = rep_2_3 (mas, massz, elsz, aspr, &n1, &nels, &lbeg, &lnbeg, &nkey, &nkey2, &pr);
  1077.   lastb = mas + massz;
  1078.   lkey = lastb - lbeg + size2b;
  1079.   lkey2 = lastb - elsz;
  1080.   if (n2 == 0)
  1081.     {
  1082.       putwul (pgr, 'n');
  1083.       ans = divsn (pg->p_pn, mas, massz, pgr->p_pn, LEAF, lkey, lkey2);
  1084.     }
  1085.   else
  1086.     {
  1087.       char *lnkey, *lnkey2;
  1088.       char newkey[BD_PAGESIZE];
  1089.       char newk2[BD_PAGESIZE];
  1091.       lnkey = mas + lnbeg + size2b;
  1092.       lnkey2 = mas + n1 - elsz;
  1093.       bcopy (nkey, newkey, kszcal (nkey, afn, d_f));
  1094.       bcopy (nkey2, newk2, k2sz);
  1095.       putwul (pgr, 'n');
  1096.       ans = upmod_2_3 (lkey, lkey2, lnkey, lnkey2, newkey, newk2, &newpn);
  1097.       if (ans >= 0)
  1098.         per_2_3 (pg->p_pn, newpn, pgr->p_pn, mas, massz,
  1099.                  n1, n2, nels, pr, lbeg, lnbeg, LEAF);
  1100.     }
  1101.   xfree ((void *) mas);
  1102.   return (ans);
  1103. }
  1105. static int
  1106. div12 (struct A *pg, i4_t sz, char *key, char *key2,
  1107.        char *inf, char *beg, char *loc)
  1108. {
  1109.   char *a, *b, *asp, *aspn, *lastb, *middleb, *lastb2;
  1110.   i4_t elsz, pr, off, n1, lbeg, lnbeg, middle, n2, prpg, ans;
  1111.   struct ind_page *indph, *indphn;
  1112.   struct A pgn;
  1113.   char *lnkey, *lnkey2, *lkey, *lkey2;
  1114.   u2_t nels, newpn, pn;
  1115.   i4_t idm;
  1116.   
  1117.   asp = pg->p_shm;
  1118.   indph = (struct ind_page *) asp;
  1119.   elsz = k2sz + inf_size;
  1120.   off = indph->ind_off;
  1121.   lastb = asp + off;
  1122.   middle = (off + sz + indphsize) / 2;
  1123.   if (loc - asp + sz <= middle)
  1124.     { /* An insertion in the first page */
  1125.       middleb = asp + middle - sz;
  1126.       lnkey = key;
  1127.       lnkey2 = key2;
  1128.       n2 = repet1 (asp, beg, loc, elsz, middleb, &lkey, &lkey2, &lnkey,
  1129.                    &lnkey2, &n1, &nels, &lbeg, &lnbeg, &pr, NULL);
  1130.       prpg = 1;
  1131.     }
  1132.   else
  1133.     { /* An insertion in the second page */
  1134.       middleb = asp + middle;
  1135.       n2 = repttn (asp + indphsize, lastb, elsz, middleb, &lkey, &lkey2,
  1136.                    &lnkey, &lnkey2, &n1, &nels, &lbeg, &lnbeg, &pr, NULL);
  1137.       n1 += indphsize;
  1138.       prpg = 2;
  1139.     }
  1140.   pn = pg->p_pn;
  1141.   ans = (div_upmod (lkey, lkey2, lnkey, lnkey2, pn, &newpn) < 0);
  1142.   if (ans == -1)
  1143.     {
  1144.       putwul (pg, 'n');
  1145.       return (-1);
  1146.     }
  1147.   idm = ++((struct p_head *) asp)->idmod;
  1148.   a = asp + sizeof (struct p_head);
  1149.   b = asp + indph->ind_off;
  1150.   recmjform (OLD, seg_n, pn, idm, a - asp, b - a, a, 0);
  1151.   if (nels != 0)
  1152.     mod_nels ((-nels), asp + lnbeg);
  1153.   lastb = asp + n1;
  1154.   aspn = getnew (&pgn, seg_n, newpn); /* get newpn */
  1155.   indphn = (struct ind_page *) aspn;
  1156.   indphn->ind_off = indphsize;
  1157.   lastb2 = pereliv (aspn, 0, nels, lnkey, lastb, off - n1);
  1158.   if (prpg == 1)
  1159.     { /* An insertion in the first page */
  1160.       icp_insrec (key, key2, inf, inf_size, beg, loc, lastb, 0, NULL, 0);
  1161.       n1 += sz;
  1162.     }
  1163.   else
  1164.     {
  1165.       sz = insrep (aspn, lastb2, key, key2, elsz, &beg, &loc);
  1166.       icp_insrec (key, key2, inf, inf_size, beg, loc, lastb2, 0, NULL, 0);
  1167.       n2 += sz; 
  1168.     }
  1169.   indph->ind_off = n1;
  1170.   indph->ind_nextpn = newpn;
  1171.   assert (check_ind_page (asp) == 0);
  1172.   putwul (pg, 'm'); /* put page without unlock */
  1173.   indphn->ind_off = n2 + indphsize;
  1174.   indphn->ind_nextpn = (u2_t) ~ 0;
  1175.   indphn->ind_wpage = LEAF;
  1176.   assert (check_ind_page (aspn) == 0);
  1177.   putwul (&pgn, 'm'); /* put new page */
  1178.   return (0);
  1179. }
  1181. static int
  1182. rbrobr (struct A *pg, i4_t sz, char *key, char *key2,
  1183.         char *inf, char *beg, char *loc)
  1184. { /* right brother request for an insertion */
  1185.   char *aspr, *frkey, *asp;
  1186.   char *middleb, *lnkey, *lnkey2, *lkey, *lkey2;
  1187.   i4_t elsz, n1, n2, rfreesz, lbeg, ans, off1, off2;
  1188.   i4_t lnbeg, prpg, pr, ksz, offbeg, offloc, middle;
  1189.   u2_t nels, rbrpn, pn;
  1190.   struct A pgr;
  1191.   char oldkey[BD_PAGESIZE];
  1192.   char oldk2[BD_PAGESIZE];  
  1193.   char nkey[BD_PAGESIZE];
  1194.   char nkey2[BD_PAGESIZE];
  1196.   asp = pg->p_shm;
  1197.   rbrpn = ((struct ind_page *) asp)->ind_nextpn;
  1198.   if (rbrpn == (u2_t) ~ 0)
  1199.     return (div12 (pg, sz, key, key2, inf, beg, loc));
  1200.   if ((aspr = getpg (&pgr, seg_n, rbrpn, 's')) == NULL)
  1201.     return ( -1);
  1202.   thread_s_put (rbrpn);
  1203.   off2 = ((struct ind_page *) aspr)->ind_off;
  1204.   rfreesz = BD_PAGESIZE - off2;
  1205.   offbeg = beg - asp;
  1206.   offloc = loc - asp;
  1207.   if (rfreesz < sz)
  1208.     return (rbrnew (pg, &pgr, sz, key, key2, inf, offbeg, offloc));
  1209.   /* A location is enough in the right brother */
  1210.   elsz = k2sz + inf_size;
  1211.   off1 = ((struct ind_page *) asp)->ind_off;
  1212.   middle = (off1 + off2 + sz) / 2;
  1213.   frkey = aspr + indphsize + size2b;
  1214.   if (offloc + sz <= middle)
  1215.     { /* An insertion in the first page */
  1216.       middleb = asp + middle - sz;
  1217.       lnkey = key;
  1218.       lnkey2 = key2;
  1219.       n2 = repet1 (asp, beg, loc, elsz, middleb, &lkey, &lkey2, &lnkey, &lnkey2,
  1220.    &n1, &nels, &lbeg, &lnbeg, &pr, frkey);
  1221.       if (n2 > rfreesz)
  1222. return (rbrnew (pg, &pgr, sz, key, key2, inf, offbeg, offloc));
  1223.       ksz = kszcal (lnkey, afn, d_f);
  1224.       prpg = 1;
  1225.     }
  1226.   else
  1227.     { /* An insertion in the right brother page */
  1228.       char * mas, *a, *b, *lastb;
  1229.       i4_t massz, size;
  1230.       middleb = asp + middle;
  1231.       lastb = asp + off1;
  1232.       n2 = repttn (asp + indphsize, lastb, elsz, middleb, &lkey, &lkey2, &lnkey,
  1233.    &lnkey2, &n1, &nels, &lbeg, &lnbeg, &pr, frkey);
  1234.       ksz = kszcal (lnkey, afn, d_f);
  1235.       n1 += indphsize;
  1236.       lnbeg += indphsize;
  1237.       massz = off1 - n1 + size2b + ksz + elsz + indphsize;
  1238.       mas = (char *) xmalloc (massz);
  1239.       a = mas + indphsize;
  1240.       if (nels != 0)
  1241. {
  1242.   t2bpack (nels, a);
  1243.   a += size2b;
  1244.           bcopy (lnkey, a, ksz);
  1245.           a += ksz;
  1246. }
  1247.       b = asp + n1;
  1248.       size = lastb - b;
  1249.       bcopy (b, a, size);
  1250.       sz = insrep (mas, mas + massz, key, key2, elsz, &beg, &loc);
  1251.       n2 += sz;
  1252.       if (n2 > rfreesz)
  1253. {
  1254.   xfree ((void *) mas);
  1255.   return (rbrnew (pg, &pgr, sz, key, key2, inf, offbeg, offloc));
  1256. }
  1257.       offbeg = beg - mas;
  1258.       offloc = loc - mas;
  1259.       xfree ((void *) mas);
  1260.       prpg = 2;
  1261.     }
  1262.   bcopy (lkey, oldkey, kszcal (lkey, afn, d_f));
  1263.   bcopy (lkey2, oldk2, k2sz);
  1264.   bcopy (lnkey, nkey, ksz);
  1265.   bcopy (lnkey2, nkey2, k2sz);
  1266.   putwul (pg, 'n'); /* put pn without unlock */
  1267.   putwul (&pgr, 'n'); /* put rbrpn without unlock */
  1268.   pn = pg->p_pn;
  1269.   ans = mlreddi (oldkey, oldk2, nkey, nkey2, pn);
  1270.   if (ans == -1)
  1271.     return (-1);
  1272.   per22 (pn, rbrpn, n1, n2, nels, lbeg, lnbeg, pr, prpg,
  1273.          sz, key, key2, inf, nkey, offbeg, offloc);
  1274.   return (0);
  1275. }
  1277. static int
  1278. inroot (struct A *pg, i4_t insz, char *key, char *key2,
  1279.         char *inf, char *bbeg, char *loc, i4_t wpage)
  1280. {
  1281.   char *a, *b, *lastb;
  1282.   i4_t off, size, ans, infsz, ibeg, iloc;
  1283.   char *mas;
  1284.   char *asp;
  1286.   if (wpage == LEAF)
  1287.     infsz = inf_size;
  1288.   else
  1289.     infsz = size2b;
  1290.   asp = pg->p_shm;
  1291.   ibeg = bbeg - asp;
  1292.   iloc = loc - asp;
  1293.   off = ((struct ind_page *) asp)->ind_off;
  1294.   size = off - indphsize;
  1295.   mas = (char *) xmalloc (size + insz);
  1296.   bcopy (asp + indphsize, mas, size);
  1297.   lastb = mas + size;
  1298.   a = mas + ibeg - indphsize;
  1299.   b = mas + iloc - indphsize;
  1300.   icp_insrec (key, key2, inf, infsz, a, b, lastb, 0, NULL, 0);
  1301.   ans = crnlev (pg, mas, lastb + insz, wpage);
  1302.   xfree ((void *) mas);
  1303.   return (ans);
  1304. }
  1306. static int
  1307. largest_key (struct A *pg, char *key, char *key2, char *inf, i4_t wpage);
  1309. static int
  1310. addlast (char *key, char *key2, u2_t * newpn)
  1311. {
  1312.   u2_t uppn;
  1313.   struct A pg;
  1314.   char *asp;
  1315.   char inf[size2b];
  1317.   uppn = *(--thread_s.u);
  1318.   asp = getwl (&pg, seg_n, uppn); /* get uppn without lock */
  1319.   *newpn = getempt (seg_n);
  1320.   t2bpack (*newpn, inf);
  1321.   if (largest_key (&pg, key, key2, inf, BTWN) < 0)
  1322.     {
  1323.       emptypg (seg_n, *newpn, 'n');
  1324.       return (-1);
  1325.     }
  1326.   return (0);
  1327. }
  1329. static int
  1330. largest_key (struct A *pg, char *key, char *key2, char *inf, i4_t wpage)
  1331. {
  1332.   char *lastb, *bbeg, *loc, *asp;
  1333.   i4_t elsz, sz, off, infsz;
  1334.   u2_t pn;
  1335.   i4_t idm;
  1336.   struct ind_page *indph;
  1338.   asp = pg->p_shm;
  1339.   indph = (struct ind_page *) asp;
  1340.   if (wpage == LEAF)
  1341.     infsz = inf_size;
  1342.   else
  1343.     infsz = size2b;
  1344.   elsz = k2sz + infsz;
  1345.   off = indph->ind_off;
  1346.   lastb = asp + off;
  1347.   sz = insrep (asp, lastb, key, key2, elsz, &bbeg, &loc);
  1348.   if (sz == 0 )
  1349.     return (1);
  1350.   pn = pg->p_pn;
  1351.   if (sz + off > BD_PAGESIZE)
  1352.     {
  1353.       if (indph->ind_wpage == IROOT)
  1354.         {
  1355.           return (inroot (pg, sz, key, key2, inf, bbeg, loc, wpage));
  1356.         }
  1357.       else
  1358. {
  1359.           u2_t newpn, keysz;
  1360.   putwul (pg, 'n');
  1361.   if (addlast (key, key2, &newpn) < 0)
  1362.     return (-1);
  1363.   asp = getnew (pg, seg_n, newpn); /* get pn without lock */
  1364.   loc = asp + indphsize;
  1365.   t2bpack (1, loc);
  1366.           loc += size2b;
  1367.           keysz = kszcal (key, afn, d_f);
  1368.           bcopy (key, loc, keysz);
  1369.           loc += keysz;
  1370.           bcopy (key2, loc, k2sz);
  1371.           loc += k2sz;
  1372.           bcopy (inf, loc, infsz);
  1373.   indph = (struct ind_page *) asp;
  1374.   indph->ind_nextpn = (u2_t) ~ 0;
  1375.   indph->ind_off = indphsize + size2b + keysz + k2sz + infsz;
  1376.   indph->ind_wpage = wpage;
  1377.           assert (check_ind_page (asp) == 0);
  1378.   putwul (pg, 'm');
  1379.   asp = getwl (pg, seg_n, pn); /* get pn without lock */
  1380.   indph = (struct ind_page *) asp;
  1381.   idm = ++((struct p_head *) asp)->idmod;
  1382.   loc = (char *) &indph->ind_nextpn;
  1383.   recmjform (OLD, seg_n, pn, idm, loc - asp, size2b, loc, 0);
  1384.   indph->ind_nextpn = newpn;
  1385. }
  1386.     }
  1387.   else
  1388.     {
  1389.       if (indph->ind_wpage != IROOT)
  1390. { /* pn is not root */
  1391.           char *oldkey;
  1392.           char old_key[BD_PAGESIZE];
  1393.           char oldk2[BD_PAGESIZE];
  1394.           i4_t offbeg, offloc;
  1395.   offbeg = bbeg - asp;
  1396.   offloc = loc - asp;
  1397.   if (sz != elsz)
  1398.     {
  1399.               char *a;
  1400.               u2_t keysz = 0 , n;
  1401.               for (a = asp + indphsize; a < lastb; a += keysz + n * elsz)
  1402.                 {
  1403.                   n = t2bunpack (a);
  1404.                   a += size2b;
  1405.                   loc = a;
  1406.                   keysz = kszcal (a, afn, d_f);
  1407.                 }
  1408.       oldkey = old_key;
  1409.               assert ( keysz != 0 );
  1410.               bcopy (loc, oldkey, keysz);
  1411.     }
  1412.   else
  1413.     oldkey = key;
  1414.           bcopy (lastb - elsz, oldk2, k2sz);
  1415.   putwul (pg, 'n');
  1416.   if (modlast (oldkey, oldk2, key, key2, pn) < 0)
  1417.     return (-1);
  1418.   asp = getwl (pg, seg_n, pn); /* get pn without lock */
  1419.   indph = (struct ind_page *) asp;
  1420.   bbeg = offbeg + asp;
  1421.   loc = offloc + asp;
  1422.           lastb = asp + indph->ind_off;
  1423. }
  1424.       else
  1425. {
  1426.   upunlock ();
  1427.   if (lenforce ()< 0)
  1428.     {
  1429.       putwul (pg, 'n');
  1430.       return (-1);
  1431.     }
  1432. }
  1433.       idm = ++((struct p_head *) asp)->idmod;
  1434.       icp_insrec (key, key2, inf, infsz, bbeg, loc, lastb, pn, asp, idm);
  1435.       loc = (char *) &indph->ind_off;
  1436.       recmjform (OLD, seg_n, pn, idm, loc - asp, size2b, loc, 0);
  1437.       indph->ind_off += sz;
  1438.     }
  1439.   assert (check_ind_page (asp) == 0);
  1440.   putwul (pg, 'm');
  1441.   return (0);
  1442. }
  1444. static char *
  1445. find_largest_key (struct A *pg)
  1446. {
  1447.   char  *a, *asp;
  1448.   u2_t  pn;
  1449.   struct ind_page *indph;
  1451.   asp = pg->p_shm;
  1452.   indph = (struct ind_page *) asp;
  1453.   do
  1454.     {
  1455.       a = asp + indph->ind_off - size2b;
  1456.       pn = t2bunpack (a);
  1457.       putwul (pg, 'n');
  1458.       thread_s_put (pn);
  1459.       if ((asp = getpg (pg, seg_n, pn, 's')) == NULL)
  1460. return (NULL); /* Lock and request */
  1461.       indph = (struct ind_page *) asp;
  1462.     }
  1463.   while (indph->ind_wpage != LEAF);
  1464.   thread_s.u = thread_s.d - 1;
  1465.   return (asp);
  1466. }
  1468. static int
  1469. divsn_modlast (char *key, char *key2, u2_t pn, char *mas, i4_t massz);
  1471. static int
  1472. divup_modlast (char *key, char *key2, char *nkey, char *nkey2,
  1473.                char *lnkey, char *lnkey2, u2_t * newpn)
  1474. {
  1475.   char *a, *asp, *lastb;
  1476.   u2_t uppn;
  1477.   struct ind_page *indph;
  1478.   struct A pg;
  1479.   i4_t rbeg, rloc, ibeg1, iloc1, ibeg2, iloc2;
  1480.   i4_t remsz, sz1, sz2, elsz, off, dopsz;
  1481.   char inf1[size2b], inf2[size2b], *beg, *loc;
  1482.   i4_t idm;
  1484.   uppn = *(--thread_s.u);
  1485.   asp = getwl (&pg, seg_n, uppn); /* get pn without lock */
  1486.   indph = (struct ind_page *) asp;
  1487.   elsz = k2sz + size2b;
  1488.   remsz = mlrep1 (asp, key, key2, nkey, &rbeg, &rloc, &ibeg1, &iloc1, &sz1);
  1489.   if (cmpkeys (k_n, afn, d_f, lnkey, nkey) == 0)
  1490.     {
  1491.       sz2 = elsz;
  1492.       ibeg2 = ibeg1;
  1493.       if (ibeg1 == iloc1)
  1494.         iloc2 = ibeg1 + sz1 +elsz;
  1495.       else
  1496.         iloc2 = iloc1 + elsz;
  1497.     }
  1498.   else
  1499.     {
  1500.       sz2 = size2b + kszcal (lnkey, afn, d_f) + elsz;
  1501.       ibeg2 = iloc2 = iloc1 + sz1;
  1502.     }
  1503.   bcopy (asp + rloc + k2sz, inf1, size2b);
  1504.   off = indph->ind_off;
  1505.   dopsz = sz1 + sz2 - remsz;
  1506.   if ((off + dopsz) > BD_PAGESIZE)
  1507.     {
  1508.       char *mas;
  1509.       i4_t massz, ans, size;
  1510.       lastb = asp + off;
  1511.       massz = off + dopsz - indphsize;
  1512.       mas = (char *) xmalloc (massz);
  1513.       size = off - indphsize;
  1514.       bcopy (asp + indphsize, mas, size);
  1515.       lastb = mas + size;
  1516.       beg = mas + rbeg - indphsize;
  1517.       loc = mas + rloc - indphsize; 
  1518.       icp_remrec (beg, loc, remsz, lastb, elsz, 0, NULL, 0);
  1519.       lastb -= remsz;
  1520.       beg = mas + ibeg1 - indphsize;
  1521.       loc = mas + iloc1 - indphsize;
  1522.       icp_insrec (nkey, nkey2, inf1, size2b, beg, loc, lastb, 0, NULL, 0);
  1523.       lastb += sz1;
  1524.       *newpn = getempt (seg_n);
  1525.       beg = mas + ibeg2 - indphsize;
  1526.       loc = mas + iloc2 - indphsize;
  1527.       t2bpack (*newpn, inf2);
  1528.       icp_insrec (nkey, nkey2, inf2, size2b, beg, loc, lastb, 0, NULL, 0);
  1529.       if (indph->ind_wpage != IROOT)
  1530.         {
  1531.           putwul (&pg, 'n');
  1532.           ans = divsn_modlast (key, key2, uppn, mas, massz);
  1533.         }
  1534.       else
  1535.         ans = crnlev (&pg, mas, mas + massz, BTWN);
  1536.       if (ans < 0)
  1537. emptypg (seg_n, *newpn, 'n');
  1538.       xfree ((void *) mas);
  1539.       return (ans);
  1540.     }
  1541.   else
  1542.     {
  1543.       if (indph->ind_wpage != IROOT)
  1544. { /* pn is not root */
  1545.   putwul (&pg, 'n');
  1546.   if (modlast (key, key2, nkey, nkey2, uppn) < 0)
  1547.     return (-1);
  1548.   asp = getwl (&pg, seg_n, uppn); /* get pn without lock */
  1549.   indph = (struct ind_page *) asp;
  1550. }
  1551.       else
  1552. {
  1553.   upunlock ();
  1554.   if (lenforce ()< 0)
  1555.     {
  1556.       putwul (&pg, 'n');
  1557.       return (-1);
  1558.     }
  1559. }
  1560.     }
  1561.   *newpn = getempt (seg_n);
  1562.   idm = ++((struct p_head *) asp)->idmod;
  1563.   lastb = asp + off;
  1564.   icp_remrec (asp + rbeg, asp + rloc, remsz, lastb, elsz, uppn, asp, idm);
  1565.   lastb -= remsz;
  1566.   beg = asp + ibeg1;
  1567.   loc = asp + iloc1;
  1568.   icp_insrec (lnkey, lnkey2, inf1, size2b, beg, loc, lastb, uppn, asp, idm);
  1569.   lastb += sz1;
  1570.   insrep (asp, lastb, nkey, nkey2, elsz, &beg, &loc);
  1571.   t2bpack (*newpn, inf2);
  1572.   icp_insrec (nkey, nkey2, inf2, size2b, beg, loc, lastb, uppn, asp, idm);
  1573.   a = (char *) &indph->ind_off;
  1574.   recmjform (OLD, seg_n, uppn, idm, a - asp, size2b, a, 0);
  1575.   indph->ind_off += dopsz;
  1576.   assert (check_ind_page (asp) == 0);
  1577.   putwul (&pg, 'm');
  1578.   return (0);
  1579. }
  1581. static int
  1582. divsn_modlast (char *key, char *key2, u2_t pn, char *mas, i4_t massz)
  1583. {
  1584.   char *lastb, *a, *b, *middleb, *asp;
  1585.   i4_t n1, lbeg, lnbeg, pr;
  1586.   char *nkey, *nkey2, *lnkey, *lnkey2;
  1587.   u2_t nels, newpn;
  1588.   i4_t idm;
  1589.   struct ind_page *indph;
  1590.   struct A pg;
  1592.   lastb = mas + massz;
  1593.   middleb = mas + massz / 2;
  1594.   repttn (mas, lastb, k2sz + size2b, middleb, &nkey, &nkey2, &lnkey,
  1595.           &lnkey2, &n1, &nels, &lbeg, &lnbeg, &pr, (char *) NULL);
  1596.   if (divup_modlast (key, key2, nkey, nkey2, lnkey, lnkey2, &newpn) < 0)
  1597.     return (-1);
  1598.   asp = getwl (&pg, seg_n, pn); /* get pn without lock */
  1599.   indph = (struct ind_page *) asp;
  1600.   idm = ++((struct p_head *) asp)->idmod;
  1601.   a = asp + sizeof (struct p_head);
  1602.   b = asp + indph->ind_off;
  1603.   recmjform (OLD, seg_n, pn, idm, a - asp, b - a, a, 0);
  1604.   bcopy (mas, asp + indphsize, n1);
  1605.   if (nels != 0)
  1606.     mod_nels ((-nels), asp + lnbeg);
  1607.   indph->ind_off = n1 + indphsize;
  1608.   indph->ind_nextpn = newpn;
  1609.   assert (check_ind_page (asp) == 0);
  1610.   putwul (&pg, 'm');
  1611.   asp = getnew (&pg, seg_n, newpn); /* get newpn without lock */
  1612.   indph = (struct ind_page *) asp;
  1613.   nkey = lastb - lbeg + size2b;
  1614.   indph->ind_off = indphsize;
  1615.   b = pereliv (asp, 0, nels, nkey, mas + n1, massz - n1);
  1616.   indph->ind_off = b - asp;
  1617.   indph->ind_nextpn = (u2_t) ~0;
  1618.   indph->ind_wpage = BTWN;
  1619.   assert (check_ind_page (asp) == 0);
  1620.   putwul (&pg, 'm'); /* put page without unlock */
  1621.   return (0);
  1622. }
  1624. int
  1625. icp_insrtn (struct ldesind *desind, char *key, char *key2,
  1626.             char *inf, i4_t infsz)
  1627. {
  1628.   i4_t lagelsz, agelsz, sz, off, ans, ans_lk;
  1629.   u2_t rootpn, d_fn;
  1630.   char *asp = NULL, *lastb, *bbeg, *loc;
  1631.   struct ind_page *indph;
  1632.   i4_t idm;
  1633.   struct A pg;
  1635.   thread_s_ini_check();
  1636.   
  1637.   seg_n = desind->i_segn;
  1638.   afn = (u2_t *) (desind + 1);
  1639.   k_n = desind->ldi.kifn & ~UNIQ & MSK21B;
  1640.   uniq_key = UNIQ & desind->ldi.kifn;
  1641.   d_f = desind->pdf;
  1642.   d_fn = k_n;
  1643.   if ((k_n % 2) != 0)
  1644.     d_fn += 1;
  1645.   d_f2 = (struct des_field *) (afn + d_fn);
  1646.   k2sz = d_f2->field_size;
  1647.   inf_size = infsz;
  1648.   lagelsz = k2sz + infsz;
  1649.   agelsz = k2sz + size2b;
  1650.   rootpn = desind->ldi.rootpn;
  1651.   beg_mop ();
  1652. try_again:
  1653.   while ((asp = getpg (&pg, seg_n, rootpn, 's')) == NULL); /* Lock and request */
  1654.   
  1655.   thread_s_ini();
  1656.   thread_s_put (rootpn);
  1657.   indph = (struct ind_page *) asp;
  1658.   if (indph->ind_wpage == LEAF)
  1659.     { /* root-leaf */
  1660.       off = indph->ind_off;
  1661.       lastb = asp + off;
  1662.       sz = insrep (asp, lastb, key, key2, lagelsz, &bbeg, &loc);
  1663.       if (sz == 0)
  1664. {
  1665.   putpg (&pg, 'n');
  1666.           thread_s_ini();
  1667.   return (NU);
  1668. }
  1669.       if (BD_PAGESIZE - off < sz)
  1670. {
  1671.   if (inroot (&pg, sz, key, key2, inf, bbeg, loc, LEAF) < 0)
  1672.     goto try_again;
  1673. }
  1674.       else
  1675. {
  1676.   if (lenforce ()< 0)
  1677.     {
  1678.       all_unlock ();
  1679.       goto try_again;
  1680.     }
  1681.   idm = ++((struct p_head *) asp)->idmod;
  1682.   icp_insrec (key, key2, inf, infsz, bbeg, loc, lastb,
  1683.       rootpn, asp, idm);
  1684.   loc = (char *) &indph->ind_off;
  1685.   recmjform (OLD, seg_n, rootpn, idm, loc - asp, size2b, loc, 0);
  1686.   indph->ind_off += sz;
  1687.           assert (check_ind_page (asp) == 0);
  1688.   putwul (&pg, 'm');
  1689. }
  1690.     }
  1691.   else
  1692.     {
  1693.       if ((ans = icp_spusk (&pg, agelsz, key, key2)) == -1)
  1694. {
  1695.   all_unlock ();
  1696.   goto try_again;
  1697. }
  1698.       else if (ans == 1)
  1699. {
  1700.   if ((ans_lk = largest_key (&pg, key, key2, inf, LEAF)) < 0)
  1701.             {
  1702.               all_unlock ();
  1703.               goto try_again;
  1704.             }
  1705.           else
  1706.             if (ans_lk == 1)
  1707.               {
  1708.                 putpg (&pg, 'n');
  1709.                 all_unlock ();
  1710.                 thread_s_ini();
  1711.                 return (NU);
  1712.               }
  1713. }
  1714.       else
  1715. {
  1716.   /* for the leaf */
  1717.           asp = pg.p_shm;
  1718.   indph = (struct ind_page *) asp;
  1719.   off = indph->ind_off;
  1720.   lastb = asp + off;
  1721.   sz = insrep (asp, lastb, key, key2, lagelsz, &bbeg, &loc);
  1722.   if (sz == 0)
  1723.     {
  1724.               putpg (&pg, 'n');
  1725.       all_unlock ();
  1726.               thread_s_ini();
  1727.       return (NU);
  1728.     }
  1729.   if (BD_PAGESIZE - off < sz)
  1730.     {
  1731.       if (rbrobr (&pg, sz, key, key2, inf, bbeg, loc) < 0)
  1732. goto try_again;
  1733.     }
  1734.           else
  1735.             {
  1736.               assert (loc != lastb);
  1737.               upunlock ();
  1738.               if (lenforce ()< 0)
  1739.                 {
  1740.                   all_unlock ();
  1741.                   goto try_again;
  1742.                 }
  1743.               idm = ++((struct p_head *) asp)->idmod;
  1744.       icp_insrec (key, key2, inf, infsz, bbeg, loc, lastb,
  1745.   pg.p_pn, asp, idm);
  1746.       loc = (char *) &indph->ind_off;
  1747.       recmjform (OLD, seg_n, pg.p_pn, idm, loc - asp, size2b, loc, 0);
  1748.       indph->ind_off += sz;
  1749.               assert (check_ind_page (asp) == 0);
  1750.       putwul (&pg, 'm');
  1751.     }
  1752. }
  1753.     }
  1754.   MJ_PUTBL ();
  1755.   downunlock ();
  1756.   
  1757.   thread_s_ini();
  1758.   
  1759.   return (OK);
  1760. }
  1762. int
  1763. icp_spusk (struct A *pg, i4_t elsz, char *key, char *key2)
  1764. {
  1765.   char *a, *lastb, *asp;
  1766.   u2_t n, pn;
  1767.   i4_t l, l2=0, ksz, i;
  1768.   struct ind_page *indph;
  1770.   asp = pg->p_shm;
  1771.   indph = (struct ind_page *)asp;
  1772.   lastb = asp + indph->ind_off;
  1773.   a = asp + indphsize;
  1774.   for (i = 0; indph->ind_wpage != LEAF; i++)
  1775.     {
  1776.       lastb = asp + indph->ind_off;
  1777.       for (a = asp + indphsize; a < lastb; )
  1778. {
  1779.   n = t2bunpack (a);
  1780.           assert (n < BD_PAGESIZE / 2);
  1781.   a += size2b;
  1782.   ksz = kszcal (a, afn, d_f);
  1783.   if ((l = cmpkeys (k_n, afn, d_f, a, key)) == 0)
  1784.     {
  1785.       a += ksz;
  1786.       for (; n != 0; n--, a += elsz)
  1787.                 if ((l2 = cmp2keys (d_f2->field_type, a, key2)) >= 0)
  1788.                   break;
  1789.               if (n == 0 && l2 < 0)
  1790.                 {
  1791.                   if (a == lastb)
  1792.                     assert (indph->ind_nextpn == (u2_t) ~0);
  1793.                   continue;
  1794.                 }
  1795.               if (n == 0)
  1796.                 a -= elsz;
  1797.       break;
  1798.     }
  1799.   else if (l > 0)
  1800.     {
  1801.       a += ksz;
  1802.       break;
  1803.     }
  1804.           a += ksz + n * elsz;
  1805. }
  1806.       if (a == lastb)
  1807. {
  1808.           assert (i==0);
  1809.   if ((asp = find_largest_key (pg)) == NULL)
  1810.     return (-1);
  1811.   return (1);
  1812. }
  1813.       a += k2sz;
  1814.       pn = t2bunpack (a);
  1815.       putwul (pg, 'n');
  1816.       if ((asp = getpg (pg, seg_n, pn, 's')) == NULL)
  1817. return (-1);
  1818.       thread_s_put (pn);
  1819.       indph = (struct ind_page *) asp;
  1820.     }
  1821.   thread_s.u = thread_s.d - 1;
  1822.   return (0);
  1823. }
  1825. int
  1826. remrep (char *asp, char *key, char *key2, i4_t elsz,
  1827.         char ** rbeg, char **rloc, i4_t *offbef)
  1828. {
  1829.   char *a, *lastb, *ckey, *bbeg;
  1830.   i4_t i, keysz, agsz = 0;
  1831.   u2_t n;
  1833.   lastb = asp + ((struct ind_page *) asp)->ind_off;
  1834.   for (a = asp + indphsize; a < lastb; a += agsz)
  1835.     {
  1836.       bbeg = a;
  1837.       n = t2bunpack (a);
  1838.       assert (n < BD_PAGESIZE / 2);
  1839.       ckey = a + size2b;
  1840.       keysz = kszcal (ckey, afn, d_f);
  1841.       if (cmpkeys (k_n, afn, d_f, ckey, key) == 0)
  1842. {
  1843.   a += size2b + keysz;
  1844.   for (i = 0; i != n; i++, a += elsz)
  1845.     if (cmp2keys (d_f2->field_type, a, key2) == 0)
  1846.       {
  1847. *rbeg = bbeg;
  1848. *offbef = bbeg - asp - agsz;
  1849. *rloc = a;
  1850. if (n == 1)
  1851.   return (size2b + keysz + elsz);
  1852. else
  1853.   return (elsz);
  1854.       }
  1855.           assert (i != n);
  1856. }
  1857.       agsz = size2b + keysz + n * elsz;
  1858.       assert (agsz < BD_PAGESIZE);
  1859.     }
  1860.   assert (a < lastb);
  1861.   return (0);
  1862. }
  1864. void
  1865. icp_remrec (char *beg, char *loc, i4_t sz, char *lastb,
  1866.             i4_t elsz, u2_t pn, char *asp, i4_t idm)
  1867. {
  1868.   char *b;
  1869.   i4_t size;
  1871.   if (sz == elsz)
  1872.     {
  1873.       b = loc + sz;
  1874.       size = lastb - b;
  1875.       if (asp != NULL)
  1876. recmjform (COMBL, seg_n, pn, idm, loc - asp, size, loc, sz);
  1877.       bcopy (b, loc, size);
  1878.       if (asp != NULL)
  1879. recmjform (OLD, seg_n, pn, idm, beg - asp, size2b, beg, 0);
  1880.       mod_nels (-1, beg);
  1881.     }
  1882.   else
  1883.     {
  1884.       b = beg + sz;
  1885.       size = lastb - b;
  1886.       if (asp != NULL)
  1887. recmjform (COMBL, seg_n, pn, idm, beg - asp, size, beg, sz);
  1888.       bcopy (b, beg, size);
  1889.     }
  1890. }
  1892. int
  1893. mlreddi (char *lkey, char *lkey2, char *lnkey, char *lnkey2, u2_t pn)
  1894. {
  1895.   char *asp, *pnt;
  1896.   i4_t sz, remsz, insz, off, orbeg, orloc, oibeg, oiloc, elsz, dopsz;
  1897.   struct ind_page *indph;
  1898.   i4_t idm;
  1899.   struct A pg;
  1900.   char ninf[size2b];
  1902.   t2bpack (pn, ninf);
  1903.   pn = *(--thread_s.u);
  1904.   asp = getwl (&pg, seg_n, pn); /* get pn without lock */
  1905.   remsz = mlrep1 (asp, lkey, lkey2, lnkey, &orbeg, &orloc, &oibeg, &oiloc, &insz);
  1906.   indph = (struct ind_page *) asp;
  1907.   off = indph->ind_off;
  1908.   dopsz = insz - remsz;
  1909.   sz = off + dopsz;
  1910.   elsz = k2sz + size2b;
  1911.   if (sz > BD_PAGESIZE)
  1912.     {
  1913.       char *mas, *b, *beg, *loc, *lastb;
  1914.       i4_t massz, ans, size;
  1915.       massz = sz - indphsize;
  1916.       mas = (char *) xmalloc (massz);
  1917.       size = off - indphsize;
  1918.       bcopy (asp + indphsize, mas, size);
  1919.       b = mas + size;
  1920.       beg = mas + orbeg - indphsize;
  1921.       loc = mas + orloc - indphsize;
  1922.       icp_remrec (beg, loc, remsz, b, elsz, 0, NULL, 0);
  1923.       lastb = b - remsz;
  1924.       beg = mas + oibeg - indphsize;
  1925.       loc = mas + oiloc - indphsize;
  1926.       icp_insrec (lnkey, lnkey2, ninf, size2b, beg, loc, lastb, 0, NULL, 0);
  1927.       if (indph->ind_wpage == IROOT)
  1928. { /* uppn is root */
  1929.   ans = crnlev (&pg, mas, mas + massz, BTWN);
  1930. }
  1931.       else
  1932. {
  1933.           char last_key[BD_PAGESIZE];
  1934.           char last_k2[BD_PAGESIZE];
  1935.           u2_t rbrpn, keysz = 0 ;
  1936.           
  1937.           if (orloc + elsz != off)     /* lkey isn't the last key in pn */
  1938.             {
  1939.               FIND_LAST_KEY (asp, elsz, lkey, lkey2, keysz);
  1940.             }
  1941.           else
  1942.             keysz = kszcal (lkey, afn, d_f);
  1943.           assert ( keysz != 0 );
  1944.           bcopy (lkey, last_key, keysz);
  1945.           bcopy (lkey2, last_k2, k2sz);
  1946.   rbrpn = indph->ind_nextpn;
  1947.   putwul (&pg, 'n');
  1948.   ans = rbrup (pn, rbrpn, mas, massz, last_key, last_k2);
  1949. }
  1950.       xfree ((void *) mas);
  1951.       return (ans);
  1952.     }
  1953.   if (orloc + elsz == off && indph->ind_wpage != IROOT)
  1954.     {
  1955.       putwul (&pg, 'n');
  1956.       if (mlreddi (lkey, lkey2, lnkey, lnkey2, pn) < 0)
  1957. return (-1);
  1958.       asp = getwl (&pg, seg_n, pn);
  1959.     }
  1960.   else
  1961.     {
  1962.       upunlock ();
  1963.       if (lenforce ()< 0)
  1964. {
  1965.   putwul (&pg, 'n');
  1966.   return (-1);
  1967. }
  1968.     }
  1969.   idm = ++((struct p_head *) asp)->idmod;
  1970.   indph = (struct ind_page *) asp;
  1971.   if (orloc == oiloc)
  1972.     { /* keys match */
  1973.       pnt = asp + orloc;
  1974.       recmjform (OLD, seg_n, pn, idm, orloc, k2sz, pnt, 0);
  1975.       bcopy (lnkey2, pnt, k2sz);
  1976.     }
  1977.   else
  1978.     {
  1979.       pnt = asp + indph->ind_off;
  1980.       icp_remrec (asp + orbeg, asp + orloc, remsz, pnt, elsz, pn, asp, idm);
  1981.       icp_insrec (lnkey, lnkey2, ninf, size2b, asp + oibeg,
  1982.   asp + oiloc, pnt - remsz, pn, asp, idm);
  1983.     }
  1984.   if (dopsz != 0)
  1985.     {
  1986.       pnt = (char *) &indph->ind_off;
  1987.       recmjform (OLD, seg_n, pn, idm, pnt - asp, size2b, pnt, 0);
  1988.       indph->ind_off += dopsz;
  1989.     }
  1990.   assert (check_ind_page (asp) == 0);
  1991.   putwul (&pg, 'm'); /* put page without unlock */
  1992.   return (0);
  1993. }
  1995. int
  1996. modlast (char *key, char *key2, char *nkey, char *nkey2, u2_t pn)
  1997. {
  1998.   char *lastb, *asp, *beg, *loc;
  1999.   struct ind_page *indph;
  2000.   i4_t sz = 0, remsz = 0, elsz, off;
  2001.   i4_t orbeg, orloc, oibeg, oiloc;
  2002.   i4_t idm;
  2003.   struct A pg;
  2004.   char ninf[size2b];
  2006.   t2bpack (pn, ninf);
  2007.   pn = *(--thread_s.u);
  2008.   asp = getwl (&pg, seg_n, pn); /* get uppn without lock */
  2009.   indph = (struct ind_page *) asp;
  2010.   off = indph->ind_off;
  2011.   elsz = k2sz + size2b;
  2012.   if (key != nkey)
  2013.     {
  2014.       if (cmpkeys (k_n, afn, d_f, key, nkey) == 0)
  2015.         nkey = key;
  2016.       else
  2017.         {
  2018.           i4_t insz;
  2019.           remsz = mlrep1 (asp, key, key2, nkey, &orbeg, &orloc, &oibeg, &oiloc, &insz);
  2020.           assert (insz != 0);
  2021.           sz = insz - remsz;
  2022.           if (sz + off > BD_PAGESIZE)
  2023.             {
  2024.               char *mas;
  2025.               i4_t massz, ans;
  2026.               massz = off + insz - indphsize;
  2027.               mas = (char *) xmalloc (massz);
  2028.               sz = off - indphsize;
  2029.               bcopy (asp + indphsize, mas, sz);
  2030.               lastb = mas + sz;
  2031.               icp_remrec (mas + orbeg, mas + orloc, remsz, lastb, elsz, 0, NULL, 0);
  2032.               lastb -= remsz;
  2033.               icp_insrec (nkey, nkey2, ninf, size2b, mas + oibeg, mas + oiloc,
  2034.                           lastb, 0, NULL, 0);
  2035.               if (indph->ind_wpage != IROOT)
  2036.                 {
  2037.                   putwul (&pg, 'n');
  2038.                   ans = divsn_modlast (key, key2, pn, mas, massz);
  2039.                 }
  2040.               else
  2041.                 ans = crnlev (&pg, mas, mas + massz, BTWN);
  2042.               xfree ((void *) mas);
  2043.               return (ans);
  2044.             }
  2045.         }
  2046.     }
  2047.   if (indph->ind_wpage != IROOT)
  2048.     { /* pn is not root */
  2049.       putwul (&pg, 'n');
  2050.       if (modlast (key, key2, nkey, nkey2, pn) < 0)
  2051.         return (-1);
  2052.       asp = getwl (&pg, seg_n, pn); /* get pn without lock */
  2053.       indph = (struct ind_page *) asp;
  2054.     }
  2055.   else
  2056.     {
  2057.       upunlock ();
  2058.       if (lenforce ()< 0)
  2059.         {
  2060.           putwul (&pg, 'n');
  2061.           return (-1);
  2062.         }
  2063.     }
  2064.   idm = ++((struct p_head *) asp)->idmod;
  2065.   lastb = asp + off;
  2066.   if (key == nkey)
  2067.     {
  2068.       loc = lastb - elsz;
  2069.       recmjform (OLD, seg_n, pn, idm, loc - asp, size2b, loc, 0);
  2070.       bcopy (nkey2, loc, k2sz);
  2071.     }
  2072.   else
  2073.     {
  2074.       beg = asp + orbeg;
  2075.       loc = asp + orloc;
  2076.       icp_remrec (beg, loc, remsz, lastb, elsz, pn, asp, idm);
  2077.       lastb -= remsz;
  2078.       beg = asp + oibeg;
  2079.       loc = asp + oiloc;
  2080.       icp_insrec (nkey, nkey2, ninf, size2b, beg, loc, lastb, pn, asp, idm);
  2081.     }
  2082.   if (sz != 0)
  2083.     {
  2084.       char *a;
  2085.       a = (char *) &indph->ind_off;
  2086.       recmjform (OLD, seg_n, pn, idm, a - asp, size2b, a, 0);
  2087.       indph->ind_off += sz;
  2088.     }
  2089.   assert (check_ind_page (asp) == 0);
  2090.   putwul (&pg, 'm');
  2091.   return (0);
  2092. }
  2094. void
  2095. all_unlock ()
  2096. {
  2097.   BUF_unlock (seg_n, thread_s.count, thread_s.arr);
  2098. }
  2100. void
  2101. upunlock ()
  2102. {
  2103.   i4_t i;
  2104.   i = thread_s.u - thread_s.arr;
  2105.   if (i)
  2106.     BUF_unlock (seg_n, i, thread_s.arr);
  2107. }
  2109. void
  2110. downunlock ()
  2111. {
  2112.   i4_t i;
  2113.   i = thread_s.d - thread_s.u;
  2114.   if (i)
  2115.     BUF_unlock (seg_n, i, thread_s.u);
  2116. }
  2118. int
  2119. lenforce ()
  2120. {
  2121.   u2_t *a;
  2123.   for (a = thread_s.u; a < thread_s.d; a++)
  2124.     if (BUF_enforce (seg_n, *a) < 0)
  2125.       {
  2126. downunlock ();
  2127. return (-1);
  2128.       }
  2129.   return (0);
  2130. }