ind_ins.c

免费的Sql数据库系统

      a += ksz;
    }
  b = mas + n1;
  size = lastb - b;
  bcopy (b, a, size);
  a += size;
  indph->ind_nextpn = (u2_t) ~ 0;
  indph->ind_off = a - asp;
  indph->ind_wpage = wpage;
  offn = indph->ind_off;
  assert (check_ind_page (asp) == 0);
  putwul (&pgn, 'm');
  inf1 = (char *) &newpn1;
  inf2 = (char *) &newpn2;
  asp = pg->p_shm;
  indph = (struct ind_page *) asp;
  idm = ++((struct p_head *) asp)->idmod;
  a = asp + sizeof (struct p_head);
  b = asp + indph->ind_off;
  recmjform (OLD, seg_n, pg->p_pn, idm, a - asp, b - a, a, 0);
  a = asp + indphsize + size2b;
  bcopy (lnkey, a, ksz);
  a += ksz;
  bcopy (lnkey2, a, k2sz);
  a += k2sz;
  t2bpack (newpn1, a);
  a += size2b;
  if (cmpkeys (k_n, afn, d_f, lkey, lnkey) == 0)
    nels = 2;
  else
    {
      nels = 1;
      t2bpack (nels, a);
      a += size2b;
      ksz = kszcal (lkey, afn, d_f);
      bcopy (lkey, a, ksz);
      a += ksz;
    }
  t2bpack (nels, asp + indphsize);
  bcopy (lkey2, a, k2sz);
  a += k2sz;
  t2bpack (newpn2, a);
  a += size2b;
  indph->ind_nextpn = (u2_t) ~ 0;
  indph->ind_off = a - asp;
  indph->ind_wpage = IROOT;
  assert (check_ind_page (asp) == 0);
  putwul (pg, 'm');
  return (0);
}

static i4_t rbrup (u2_t pn, u2_t rbrpn, char *mas, i4_t massz,
                  char *last_key, char *last_k2);

static char *
findkey (char *asp, char *key, char *key2, i4_t elsz, char **loc)
{
  char *a, *lastb, *bbeg;
  u2_t n;
  i4_t ksz;

  lastb = asp + ((struct ind_page *) asp)->ind_off;
  for (a = asp + indphsize; a < lastb; a += ksz + n * elsz)
    {
      bbeg = a;
      n = t2bunpack (a);
      a += size2b;
      ksz = kszcal (a, afn, d_f);
      if (cmpkeys (k_n, afn, d_f, a, key) == 0)
	{
	  a += ksz;
	  for (; n != 0; n--, a += elsz)
	    if (cmp2keys (d_f2->field_type, a, key2) == 0)
	      {
		*loc = a;
		return (bbeg);
	      }
	}
    }
  return (NULL);
}

static int
div_upmod (char *lkey, char *lkey2, char *lnkey,
           char *lnkey2, u2_t pn, u2_t * newpn)
{
  char *asp, *a, *inf, *lastb;
  char *beg, *loc;
  i4_t elsz, insz, off;
  struct ind_page *indph;
  struct A pg;
  i4_t idm;
  char ninf[size2b];

  t2bpack (pn, ninf);
  pn = *(--thread_s.u);
  asp = getwl (&pg, seg_n, pn);	/* get pn without lock */
  indph = (struct ind_page *) asp;
  elsz = k2sz + size2b;
  beg = findkey (asp, lkey, lkey2, elsz, &loc);
  inf = loc + k2sz;
  off = indph->ind_off;
  lastb = asp + off;
  insz = insrep (asp, lastb, lnkey, lnkey2, elsz, &beg, &loc);
  assert (insz != 0);
  if (off + insz > BD_PAGESIZE)
    {
      char *mas, *d;
      i4_t massz, ans;
      massz = off + insz - indphsize;
      mas = (char *) xmalloc (massz);
      d = asp + indphsize;
      bcopy (d, mas, off - indphsize);
      *newpn = getempt (seg_n);
      t2bpack (*newpn, mas + (inf - d));
      beg = mas + (beg - d);
      loc = mas + (loc - d);
      lastb = mas + massz - insz;
      icp_insrec (lnkey, lnkey2, ninf, size2b, beg, loc, lastb, 0, NULL, 0);
      if (indph->ind_wpage != IROOT)
	{
          char last_key[BD_PAGESIZE];
          char last_k2[BD_PAGESIZE];
          u2_t rbrpn, keysz = 0 ;
          
          FIND_LAST_KEY (asp, elsz, lkey, lkey2, keysz);
          assert (keysz != 0 );
          bcopy (lkey, last_key, keysz);
          bcopy (lkey2, last_k2, k2sz);
          rbrpn = indph->ind_nextpn;
	  putwul (&pg, 'n');
	  ans = rbrup (pn, rbrpn, mas, massz, last_key, last_k2);
	}
      else
        ans = crnlev (&pg, mas, lastb + insz, BTWN);
      if (ans < 0)
	emptypg (seg_n, *newpn, 'n');
      xfree ((void *) mas);
      return (ans);
    }
  upunlock ();
  if (lenforce ()< 0)
    {
      putwul (&pg, 'n');
      return (-1);
    }
  *newpn = getempt (seg_n);
  idm = ++((struct p_head *) asp)->idmod;
  recmjform (OLD, seg_n, pn, idm, inf - asp, size2b, inf, 0);
  t2bpack (*newpn, inf);
  icp_insrec (lnkey, lnkey2, ninf, size2b, beg, loc, lastb, pn, asp, idm);
  a = (char *) &indph->ind_off;
  recmjform (OLD, seg_n, pn, idm, a - asp, size2b, a, 0);
  indph->ind_off += insz;
  assert (check_ind_page (asp) == 0);
  putwul (&pg, 'm');
  return (0);
}

static int
divsn (u2_t pn, char *mas, i4_t massz, u2_t nextpn,
       i4_t wpage, char *last_key, char *last_key2)
{
  char *lastb, *a, *b, *middleb, *asp;
  i4_t n1, lbeg, lnbeg, pr, elsz;
  char *lkey, *lkey2, *lnkey, *lnkey2;
  u2_t nels, newpn;
  i4_t idm;
  struct ind_page *indph;
  struct A pg;

  lastb = mas + massz;
  middleb = mas + massz / 2;
  if (wpage == LEAF)
    elsz = k2sz + inf_size;
  else
    elsz = k2sz + size2b;
  repttn (mas, lastb, elsz, middleb, &lkey, &lkey2, &lnkey, &lnkey2,
          &n1, &nels, &lbeg, &lnbeg, &pr, (char *) NULL);
  if (div_upmod (last_key, last_key2, lnkey, lnkey2, pn, &newpn) < 0)
    return (-1);
  asp = getwl (&pg, seg_n, pn);	/* get pn without lock */
  indph = (struct ind_page *) asp;
  idm = ++((struct p_head *) asp)->idmod;
  a = asp + sizeof (struct p_head);
  b = asp + indph->ind_off;
  recmjform (OLD, seg_n, pn, idm, a - asp, b - a, a, 0);
  bcopy (mas, asp + indphsize, n1);
  if (nels != 0) 
    mod_nels ((-nels), asp + lnbeg);
  indph->ind_off = n1 + indphsize;
  indph->ind_nextpn = newpn;
  assert (check_ind_page (asp) == 0);
  putwul (&pg, 'm');
  asp = getnew (&pg, seg_n, newpn);	/* get newpn without lock */
  indph = (struct ind_page *) asp;
  lkey = lastb - lbeg + size2b;
  indph->ind_off = indphsize;
  b = pereliv (asp, 0, nels, lkey, mas + n1, massz - n1);
  indph->ind_off = b - asp;
  indph->ind_nextpn = nextpn;
  indph->ind_wpage = wpage;
  assert (check_ind_page (asp) == 0);
  putwul (&pg, 'm');		/* put page without unlock */
  return (0);
}

static int
mlrep1 (char *asp, char *key, char *key2, char *nkey, i4_t *orbeg,
        i4_t *orloc, i4_t *oibeg, i4_t *oiloc, i4_t *sz)
{
  i4_t remsz, elsz, offbef;
  char *rbeg, *rloc;

  elsz = k2sz + size2b;
  remsz = remrep (asp, key, key2, elsz, &rbeg, &rloc, &offbef);
  *orbeg = rbeg - asp;
  *orloc = rloc - asp;
  if (cmpkeys (k_n, afn, d_f, key, nkey) == 0)
    {
      *oibeg = *orbeg;
      *oiloc = *orloc;
      *sz = remsz;
    }
  else
    {
      char *a;
      u2_t n;
      a = asp + offbef;
      *oibeg = offbef;
      n = t2bunpack (a);
      assert (n < BD_PAGESIZE / 2);
      a += size2b;
      *oiloc = *oibeg;
      if (cmpkeys (k_n, afn, d_f, a, nkey) == 0)
        {
          *oiloc += size2b + kszcal (nkey, afn, d_f) + n * elsz;
          *sz = elsz;
        }
      else
        {
          *oibeg = *oiloc = *orbeg;
          *sz = size2b + kszcal (nkey, afn, d_f) + elsz;
        }
    }
  return (remsz);
}

static int
upmod_2_3 (char *lkey, char *lkey2, char *lnkey, char *lnkey2,
           char *nkey, char *nkey2, u2_t * newpn)
{ /* a repetition of a modification of an uplevel for a division 2 on 3 */
  char *a, *asp, *lastb;
  u2_t uppn;
  struct ind_page *indph;
  struct A pg;
  i4_t rbeg, rloc, ibeg1, iloc1, ibeg2, iloc2;
  i4_t remsz, sz1, sz2, elsz, ksz_lnkey, ksz_nkey, off, dopsz;
  char inf1[size2b], inf2[size2b], *beg, *loc;
  i4_t idm;

  uppn = *(--thread_s.u);
  asp = getwl (&pg, seg_n, uppn);	/* get pn without lock */
  indph = (struct ind_page *) asp;
  elsz = k2sz + size2b;
  remsz = mlrep1 (asp, lkey, lkey2, lnkey, &rbeg, &rloc, &ibeg1, &iloc1, &sz1);
  ksz_nkey = kszcal (nkey, afn, d_f);
  ksz_lnkey = kszcal (lnkey, afn, d_f);
  if (cmpkeys (k_n, afn, d_f, lnkey, nkey) == 0)
    {
      sz2 = elsz;
      ibeg2 = ibeg1;
      if (ibeg1 == iloc1)
        iloc2 = ibeg1 + sz1 + elsz;
      else
        iloc2 = iloc1 + elsz;
    }
  else
    {
      sz2 = size2b + ksz_nkey + elsz;
      ibeg2 = iloc2 = iloc1 + sz1;
    }
  bcopy (asp + rloc + k2sz, inf1, size2b);
  off = indph->ind_off;
  dopsz = sz1 + sz2 - remsz;
  if (off + dopsz > BD_PAGESIZE)
    {
      char *mas;
      i4_t massz, ans, size;
      
      lastb = asp + off;
      massz = off + dopsz - indphsize;
      mas = (char *) xmalloc (massz);
      size = off - indphsize;
      bcopy (asp + indphsize, mas, size);
      lastb = mas + size;
      beg = mas + rbeg - indphsize;
      loc = mas + rloc - indphsize; 
      icp_remrec (beg, loc, remsz, lastb, elsz, 0, NULL, 0);
      lastb -= remsz;
      beg = mas + ibeg1 - indphsize;
      loc = mas + iloc1 - indphsize;
      icp_insrec (lnkey, lnkey2, inf1, size2b, beg, loc, lastb, 0, NULL, 0);
      lastb += sz1;
      *newpn = getempt (seg_n);
      beg = mas + ibeg2 - indphsize;
      loc = mas + iloc2 - indphsize;
      t2bpack (*newpn, inf2);
      icp_insrec (nkey, nkey2, inf2, size2b, beg, loc, lastb, 0, NULL, 0);
      if (indph->ind_wpage != IROOT)
	{
          char last_key[BD_PAGESIZE];
          char last_k2[BD_PAGESIZE];
          u2_t rbrpn, keysz = 0 ;
          
          if (rloc + elsz != off)     /* lkey isn't the last key in pn */
            {
              FIND_LAST_KEY (asp, elsz, lkey, lkey2, keysz);
            }
          else
            keysz = kszcal (lkey, afn, d_f);
          assert ( keysz != 0 ) ;
          bcopy (lkey, last_key, keysz);
          bcopy (lkey2, last_k2, k2sz);
	  rbrpn = indph->ind_nextpn;
	  putwul (&pg, 'n');
	  ans = rbrup (uppn, rbrpn, mas, massz, last_key, last_k2);
	}
      else
        ans = crnlev (&pg, mas, mas + massz, BTWN);
      if (ans < 0)
	emptypg (seg_n, *newpn, 'n');
      xfree ((void *) mas);
      return (ans);
    }
  else if (rloc + elsz == off && indph->ind_wpage != IROOT)
    {
      putwul (&pg, 'n');
      if (mlreddi (lkey, lkey2, nkey, nkey2, uppn) < 0)
        return (-1);
      asp = getwl (&pg, seg_n, uppn);
    }
  else
    {
      upunlock ();
      if (lenforce ()< 0)
	{
	  putwul (&pg, 'n');
	  return (-1);
	}
    }
  *newpn = getempt (seg_n);
  idm = ++((struct p_head *) asp)->idmod;
  lastb = asp + off;
  icp_remrec (asp + rbeg, asp + rloc, remsz, lastb, elsz, uppn, asp, idm);
  lastb -= remsz;
  beg = asp + ibeg1;
  loc = asp + iloc1;
  icp_insrec (lnkey, lnkey2, inf1, size2b, beg, loc, lastb, uppn, asp, idm);
  lastb += sz1;
  insrep (asp, lastb, nkey, nkey2, elsz, &beg, &loc);
  t2bpack (*newpn, inf2);
  icp_insrec (nkey, nkey2, inf2, size2b, beg, loc, lastb, uppn, asp, idm);
  a = (char *) &indph->ind_off;
  recmjform (OLD, seg_n, uppn, idm, a - asp, size2b, a, 0);
  indph->ind_off += dopsz;
  assert (check_ind_page (asp) == 0);
  putwul (&pg, 'm');
  return (0);
}

static void
per_2_3 (u2_t pn, u2_t newpn, u2_t rbrpn, char *mas, i4_t massz, i4_t n1,
         i4_t n2, u2_t nels, i4_t pr, i4_t lbeg, i4_t lnbeg, i4_t wpage)
{
  char *a, *b, *b1, *asp, *aspn, *lkey;
  struct ind_page *indph, *indphn;
  i4_t idm;
  struct A pg, pgn;
  i4_t size;

  asp = getwl (&pg, seg_n, pn);	/* get pn without lock */
  indph = (struct ind_page *) asp;
  idm = ++((struct p_head *) asp)->idmod;
  a = asp + sizeof (struct p_head);
  b = asp + indph->ind_off;
  recmjform (OLD, seg_n, pn, idm, a - asp, b - a, a, 0);
  bcopy (mas, asp + indphsize, n1);
  indph->ind_off = n1 + indphsize;
  if (nels != 0)
    mod_nels ((-nels), asp + lnbeg);
  indph->ind_nextpn = newpn;
  assert (check_ind_page (asp) == 0);
  putwul (&pg, 'm');
  aspn = getnew (&pgn, seg_n, newpn);	/* get new page */
  indphn = (struct ind_page *) aspn;
  indphn->ind_off = indphsize;
  lkey = mas + lnbeg + size2b;
  b = pereliv (aspn, 0, nels, lkey, mas + n1, massz - n1);
  asp = getwl (&pg, seg_n, rbrpn);	/* get rbrpn without lock */
  indph = (struct ind_page *) asp;
  idm = ++((struct p_head *) asp)->idmod;
  a = asp + sizeof (struct p_head);
  b1 = asp + indph->ind_off;
  recmjform (OLD, seg_n, rbrpn, idm, a - asp, b1 - a, a, 0);
  a = asp + indphsize;
  if (pr == 0)
    {
      u2_t fnels;
      fnels = t2bunpack (a);
      a += size2b;
      a += kszcal (a, afn, d_f);
      mod_nels (fnels, b - lbeg);
    }
  size = asp + n2 - a;
  bcopy (a, b, size);
  b += size;
  bcopy (asp + n2, asp + indphsize, indph->ind_off - n2);
  indphn->ind_off = b - aspn;
  indphn->ind_nextpn = rbrpn;
  indphn->ind_wpage = wpage;
  assert (check_ind_page (aspn) == 0);
  putwul (&pgn, 'm');
  indph->ind_off -= n2 - indphsize;
  assert (check_ind_page (asp) == 0);
  putwul (&pg, 'm');
}

static int
rbrnup (u2_t pn, struct A *pgr, char *mas, i4_t massz,
        char *last_key, char *last_k2)
{  /* need rbrpn and a new page for a deletion and an insertion */
  i4_t elsz, n1, n2, pr, lbeg, lnbeg;
  char *lnkey, *lnkey2, *nkey, *nkey2, *aspr;
  u2_t newpn, nels;
  char newkey[BD_PAGESIZE];
  char newk2[BD_PAGESIZE];  

  aspr = pgr->p_shm;
  elsz = k2sz + size2b;
  n2 = rep_2_3 (mas, massz, elsz, aspr, &n1, &nels,
                &lbeg, &lnbeg, &nkey, &nkey2, &pr);
  if (n2 == 0)
    {
      putwul (pgr, 'n');
      return (divsn (pn, mas, massz, pgr->p_pn, BTWN, last_key, last_k2));
    }
  bcopy ( nkey, newkey, kszcal (nkey, afn, d_f));
  bcopy ( nkey2, newk2, k2sz);
  putwul (pgr, 'n');
  lnkey = mas + lnbeg + size2b;
  lnkey2 = mas + n1 - elsz;
  if (upmod_2_3 (last_key, last_k2, lnkey, lnkey2, newkey, newk2, &newpn) < 0)
    return (-1);
  per_2_3 (pn, newpn, pgr->p_pn, mas, massz, n1, n2, nels, pr, lbeg, lnbeg, BTWN);
  return (0);
}

static int
rbrup (u2_t pn, u2_t rbrpn, char *mas, i4_t massz,
       char *last_key, char *last_k2)
	/* rbrobr with a deletion and an insertion */
{
  i4_t off2, dopsz, n1, lbeg, lnbeg, pr, rfreesz, n2;
  char *frkey, *middleb, *lkey, *lkey2, *lnkey, *lnkey2, *asp, *a, *b;
  u2_t nels, fnels;
  struct A pg;
  struct ind_page *indph;
  i4_t idm;

  if (rbrpn == (u2_t) ~ 0)
    return (divsn (pn, mas, massz, (u2_t) ~ 0, BTWN, last_key, last_k2));
  if ((asp = getpg (&pg, seg_n, rbrpn, 's')) == NULL)
    return ( -1);
  thread_s_put (rbrpn);
  frkey = asp + indphsize + size2b;
  off2 = ((struct ind_page *) asp)->ind_off;
  dopsz = massz + indphsize - BD_PAGESIZE;
  rfreesz = BD_PAGESIZE - off2;
  if (rfreesz < dopsz)
    return (rbrnup (pn, &pg, mas, massz, last_key, last_k2));
  /* A location is enough in the right brother */
  middleb = mas + (massz + off2 - indphsize) / 2;
  n2 = repttn (mas, mas + massz, k2sz + size2b, middleb, &lkey, &lkey2,
               &lnkey, &lnkey2, &n1, &nels, &lbeg, &lnbeg, &pr, frkey);
  if (n2 > rfreesz)
    return (rbrnup (pn, &pg, mas, massz, last_key, last_k2));
  putwul (&pg, 'n');
  if (mlreddi (last_key, last_k2, lnkey, lnkey2, pn) < 0)
    return (-1);
  asp = getwl (&pg, seg_n, pn);   /* get pn without lock */
  indph = (struct ind_page *) asp;
  idm = ++((struct p_head *) asp)->idmod;
  a = asp + sizeof (struct p_head);
  b = asp + indph->ind_off;
  recmjform (OLD, seg_n, pn, idm, a - asp, b - a, a, 0);
  bcopy (mas, asp + indphsize, n1);
  indph->ind_off = indphsize + n1;
  if (nels != 0)
    mod_nels ((-nels), asp + lnbeg);
  assert (check_ind_page (asp) == 0);
  putwul (&pg, 'm');
  
  asp = getwl (&pg, seg_n, rbrpn);/* get rbrpn without lock */
  indph = (struct ind_page *) asp;
  idm = ++((struct p_head *) asp)->idmod;
  a = asp + sizeof (struct p_head);
  b = asp + indph->ind_off;
  recmjform (OLD, seg_n, rbrpn, idm, a - asp, b - a, a, 0);
  fnels = t2bunpack (asp + indphsize);
  lkey = mas + lnbeg + size2b;
  a = pereliv (asp, n2, nels, lkey, mas + n1, massz - n1);
  if (pr == 0)
    mod_nels (fnels, a - lbeg);
  indph->ind_off += n2;
  assert (check_ind_page (asp) == 0);
  putwul (&pg, 'm');		/* put page without unlock */
  return (0);
}

static int
rbrnew (struct A *pg, struct A *pgr, i4_t sz, char *key,
        char *key2, char *inf, i4_t ibeg, i4_t iloc)
     /* a division 2 on 3 with an insertion at the last level */
{
  char *mas, *lastb, *beg, *loc;
  i4_t massz, n1, n2, lbeg, lnbeg, pr, elsz, ans, size;
  char *lkey, *lkey2, *nkey, *nkey2, *asp, *aspr;
  u2_t newpn, nels;
  
  asp = pg->p_shm;
  aspr = pgr->p_shm;
  size = ((struct ind_page *) asp)->ind_off - indphsize;