ind_ins.c

免费的Sql数据库系统

  massz = size + sz;
  mas = (char *) xmalloc (massz);
  bcopy (asp + indphsize, mas, size);
  beg = mas + ibeg - indphsize;
  loc = mas + iloc - indphsize;
  lastb = mas + size;
  icp_insrec (key, key2, inf, inf_size, beg, loc, lastb, 0, NULL, 0);
  elsz = k2sz + inf_size;
  putwul (pg, 'n');
  n2 = rep_2_3 (mas, massz, elsz, aspr, &n1, &nels, &lbeg, &lnbeg, &nkey, &nkey2, &pr);
  lastb = mas + massz;
  lkey = lastb - lbeg + size2b;
  lkey2 = lastb - elsz;
  if (n2 == 0)
    {
      putwul (pgr, 'n');
      ans = divsn (pg->p_pn, mas, massz, pgr->p_pn, LEAF, lkey, lkey2);
    }
  else
    {
      char *lnkey, *lnkey2;
      char newkey[BD_PAGESIZE];
      char newk2[BD_PAGESIZE];

      lnkey = mas + lnbeg + size2b;
      lnkey2 = mas + n1 - elsz;
      bcopy (nkey, newkey, kszcal (nkey, afn, d_f));
      bcopy (nkey2, newk2, k2sz);
      putwul (pgr, 'n');
      ans = upmod_2_3 (lkey, lkey2, lnkey, lnkey2, newkey, newk2, &newpn);
      if (ans >= 0)
        per_2_3 (pg->p_pn, newpn, pgr->p_pn, mas, massz,
                 n1, n2, nels, pr, lbeg, lnbeg, LEAF);
    }
  xfree ((void *) mas);
  return (ans);
}

static int
div12 (struct A *pg, i4_t sz, char *key, char *key2,
       char *inf, char *beg, char *loc)
{
  char *a, *b, *asp, *aspn, *lastb, *middleb, *lastb2;
  i4_t elsz, pr, off, n1, lbeg, lnbeg, middle, n2, prpg, ans;
  struct ind_page *indph, *indphn;
  struct A pgn;
  char *lnkey, *lnkey2, *lkey, *lkey2;
  u2_t nels, newpn, pn;
  i4_t idm;
  
  asp = pg->p_shm;
  indph = (struct ind_page *) asp;
  elsz = k2sz + inf_size;
  off = indph->ind_off;
  lastb = asp + off;
  middle = (off + sz + indphsize) / 2;
  if (loc - asp + sz <= middle)
    {			/* An insertion in the first page */
      middleb = asp + middle - sz;
      lnkey = key;
      lnkey2 = key2;
      n2 = repet1 (asp, beg, loc, elsz, middleb, &lkey, &lkey2, &lnkey,
                   &lnkey2, &n1, &nels, &lbeg, &lnbeg, &pr, NULL);
      prpg = 1;
    }
  else
    {				/* An insertion in the second page */
      middleb = asp + middle;
      n2 = repttn (asp + indphsize, lastb, elsz, middleb, &lkey, &lkey2,
                   &lnkey, &lnkey2, &n1, &nels, &lbeg, &lnbeg, &pr, NULL);
      n1 += indphsize;
      prpg = 2;
    }
  pn = pg->p_pn;
  ans = (div_upmod (lkey, lkey2, lnkey, lnkey2, pn, &newpn) < 0);
  if (ans == -1)
    {
      putwul (pg, 'n');
      return (-1);
    }
  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);
  if (nels != 0)
    mod_nels ((-nels), asp + lnbeg);
  lastb = asp + n1;
  aspn = getnew (&pgn, seg_n, newpn);	/* get newpn */
  indphn = (struct ind_page *) aspn;
  indphn->ind_off = indphsize;
  lastb2 = pereliv (aspn, 0, nels, lnkey, lastb, off - n1);
  if (prpg == 1)
    {				/* An insertion in the first page */
      icp_insrec (key, key2, inf, inf_size, beg, loc, lastb, 0, NULL, 0);
      n1 += sz;
    }
  else
    {
      sz = insrep (aspn, lastb2, key, key2, elsz, &beg, &loc);
      icp_insrec (key, key2, inf, inf_size, beg, loc, lastb2, 0, NULL, 0);
      n2 += sz; 
    }
  indph->ind_off = n1;
  indph->ind_nextpn = newpn;
  assert (check_ind_page (asp) == 0);
  putwul (pg, 'm');		/* put page without unlock */
  indphn->ind_off = n2 + indphsize;
  indphn->ind_nextpn = (u2_t) ~ 0;
  indphn->ind_wpage = LEAF;
  assert (check_ind_page (aspn) == 0);
  putwul (&pgn, 'm');		/* put new page */
  return (0);
}

static int
rbrobr (struct A *pg, i4_t sz, char *key, char *key2,
        char *inf, char *beg, char *loc)
{	/* right brother request for an insertion */
  char *aspr, *frkey, *asp;
  char *middleb, *lnkey, *lnkey2, *lkey, *lkey2;
  i4_t elsz, n1, n2, rfreesz, lbeg, ans, off1, off2;
  i4_t lnbeg, prpg, pr, ksz, offbeg, offloc, middle;
  u2_t nels, rbrpn, pn;
  struct A pgr;
  char oldkey[BD_PAGESIZE];
  char oldk2[BD_PAGESIZE];  
  char nkey[BD_PAGESIZE];
  char nkey2[BD_PAGESIZE];

  asp = pg->p_shm;
  rbrpn = ((struct ind_page *) asp)->ind_nextpn;
  if (rbrpn == (u2_t) ~ 0)
    return (div12 (pg, sz, key, key2, inf, beg, loc));
  if ((aspr = getpg (&pgr, seg_n, rbrpn, 's')) == NULL)
    return ( -1);
  thread_s_put (rbrpn);
  off2 = ((struct ind_page *) aspr)->ind_off;
  rfreesz = BD_PAGESIZE - off2;
  offbeg = beg - asp;
  offloc = loc - asp;
  if (rfreesz < sz)
    return (rbrnew (pg, &pgr, sz, key, key2, inf, offbeg, offloc));
  /* A location is enough in the right brother */
  elsz = k2sz + inf_size;
  off1 = ((struct ind_page *) asp)->ind_off;
  middle = (off1 + off2 + sz) / 2;
  frkey = aspr + indphsize + size2b;
  if (offloc + sz <= middle)
    {				/* An insertion in the first page */
      middleb = asp + middle - sz;
      lnkey = key;
      lnkey2 = key2;
      n2 = repet1 (asp, beg, loc, elsz, middleb, &lkey, &lkey2, &lnkey, &lnkey2,
		   &n1, &nels, &lbeg, &lnbeg, &pr, frkey);
      if (n2 > rfreesz)
	return (rbrnew (pg, &pgr, sz, key, key2, inf, offbeg, offloc));
      ksz = kszcal (lnkey, afn, d_f);
      prpg = 1;
    }
  else
    {				/* An insertion in the right brother page */
      char * mas, *a, *b, *lastb;
      i4_t massz, size;
      middleb = asp + middle;
      lastb = asp + off1;
      n2 = repttn (asp + indphsize, lastb, elsz, middleb, &lkey, &lkey2, &lnkey,
		   &lnkey2, &n1, &nels, &lbeg, &lnbeg, &pr, frkey);
      ksz = kszcal (lnkey, afn, d_f);
      n1 += indphsize;
      lnbeg += indphsize;
      massz = off1 - n1 + size2b + ksz + elsz + indphsize;
      mas = (char *) xmalloc (massz);
      a = mas + indphsize;
      if (nels != 0)
	{
	  t2bpack (nels, a);
	  a += size2b;
          bcopy (lnkey, a, ksz);
          a += ksz;
	}
      b = asp + n1;
      size = lastb - b;
      bcopy (b, a, size);
      sz = insrep (mas, mas + massz, key, key2, elsz, &beg, &loc);
      n2 += sz;
      if (n2 > rfreesz)
	{
	  xfree ((void *) mas);
	  return (rbrnew (pg, &pgr, sz, key, key2, inf, offbeg, offloc));
	}
      offbeg = beg - mas;
      offloc = loc - mas;
      xfree ((void *) mas);
      prpg = 2;
    }
  bcopy (lkey, oldkey, kszcal (lkey, afn, d_f));
  bcopy (lkey2, oldk2, k2sz);
  bcopy (lnkey, nkey, ksz);
  bcopy (lnkey2, nkey2, k2sz);
  putwul (pg, 'n');		/* put pn without unlock */
  putwul (&pgr, 'n');		/* put rbrpn without unlock */
  pn = pg->p_pn;
  ans = mlreddi (oldkey, oldk2, nkey, nkey2, pn);
  if (ans == -1)
    return (-1);
  per22 (pn, rbrpn, n1, n2, nels, lbeg, lnbeg, pr, prpg,
         sz, key, key2, inf, nkey, offbeg, offloc);
  return (0);
}

static int
inroot (struct A *pg, i4_t insz, char *key, char *key2,
        char *inf, char *bbeg, char *loc, i4_t wpage)
{
  char *a, *b, *lastb;
  i4_t off, size, ans, infsz, ibeg, iloc;
  char *mas;
  char *asp;

  if (wpage == LEAF)
    infsz = inf_size;
  else
    infsz = size2b;
  asp = pg->p_shm;
  ibeg = bbeg - asp;
  iloc = loc - asp;
  off = ((struct ind_page *) asp)->ind_off;
  size = off - indphsize;
  mas = (char *) xmalloc (size + insz);
  bcopy (asp + indphsize, mas, size);
  lastb = mas + size;
  a = mas + ibeg - indphsize;
  b = mas + iloc - indphsize;
  icp_insrec (key, key2, inf, infsz, a, b, lastb, 0, NULL, 0);
  ans = crnlev (pg, mas, lastb + insz, wpage);
  xfree ((void *) mas);
  return (ans);
}

static int
largest_key (struct A *pg, char *key, char *key2, char *inf, i4_t wpage);

static int
addlast (char *key, char *key2, u2_t * newpn)
{
  u2_t uppn;
  struct A pg;
  char *asp;
  char inf[size2b];

  uppn = *(--thread_s.u);
  asp = getwl (&pg, seg_n, uppn);	/* get uppn without lock */
  *newpn = getempt (seg_n);
  t2bpack (*newpn, inf);
  if (largest_key (&pg, key, key2, inf, BTWN) < 0)
    {
      emptypg (seg_n, *newpn, 'n');
      return (-1);
    }
  return (0);
}

static int
largest_key (struct A *pg, char *key, char *key2, char *inf, i4_t wpage)
{
  char *lastb, *bbeg, *loc, *asp;
  i4_t elsz, sz, off, infsz;
  u2_t pn;
  i4_t idm;
  struct ind_page *indph;

  asp = pg->p_shm;
  indph = (struct ind_page *) asp;
  if (wpage == LEAF)
    infsz = inf_size;
  else
    infsz = size2b;
  elsz = k2sz + infsz;
  off = indph->ind_off;
  lastb = asp + off;
  sz = insrep (asp, lastb, key, key2, elsz, &bbeg, &loc);
  if (sz == 0 )
    return (1);
  pn = pg->p_pn;
  if (sz + off > BD_PAGESIZE)
    {
      if (indph->ind_wpage == IROOT)
        {
          return (inroot (pg, sz, key, key2, inf, bbeg, loc, wpage));
        }
      else
	{
          u2_t newpn, keysz;
	  putwul (pg, 'n');
	  if (addlast (key, key2, &newpn) < 0)
	    return (-1);
	  asp = getnew (pg, seg_n, newpn);	/* get pn without lock */
	  loc = asp + indphsize;
	  t2bpack (1, loc);
          loc += size2b;
          keysz = kszcal (key, afn, d_f);
          bcopy (key, loc, keysz);
          loc += keysz;
          bcopy (key2, loc, k2sz);
          loc += k2sz;
          bcopy (inf, loc, infsz);
	  indph = (struct ind_page *) asp;
	  indph->ind_nextpn = (u2_t) ~ 0;
	  indph->ind_off = indphsize + size2b + keysz + k2sz + infsz;
	  indph->ind_wpage = wpage;
          assert (check_ind_page (asp) == 0);
	  putwul (pg, 'm');
	  asp = getwl (pg, seg_n, pn);	/* get pn without lock */
	  indph = (struct ind_page *) asp;
	  idm = ++((struct p_head *) asp)->idmod;
	  loc = (char *) &indph->ind_nextpn;
	  recmjform (OLD, seg_n, pn, idm, loc - asp, size2b, loc, 0);
	  indph->ind_nextpn = newpn;
	}
    }
  else
    {
      if (indph->ind_wpage != IROOT)
	{			/* pn is not root */
          char *oldkey;
          char old_key[BD_PAGESIZE];
          char oldk2[BD_PAGESIZE];
          i4_t offbeg, offloc;
	  offbeg = bbeg - asp;
	  offloc = loc - asp;
	  if (sz != elsz)
	    {
              char *a;
              u2_t keysz = 0 , n;
              for (a = asp + indphsize; a < lastb; a += keysz + n * elsz)
                {
                  n = t2bunpack (a);
                  a += size2b;
                  loc = a;
                  keysz = kszcal (a, afn, d_f);
                }
	      oldkey = old_key;
              assert ( keysz != 0 );
              bcopy (loc, oldkey, keysz);
	    }
	  else
	    oldkey = key;
          bcopy (lastb - elsz, oldk2, k2sz);
	  putwul (pg, 'n');
	  if (modlast (oldkey, oldk2, key, key2, pn) < 0)
	    return (-1);
	  asp = getwl (pg, seg_n, pn);	/* get pn without lock */
	  indph = (struct ind_page *) asp;
	  bbeg = offbeg + asp;
	  loc = offloc + asp;
          lastb = asp + indph->ind_off;
	}
      else
	{
	  upunlock ();
	  if (lenforce ()< 0)
	    {
	      putwul (pg, 'n');
	      return (-1);
	    }
	}
      idm = ++((struct p_head *) asp)->idmod;
      icp_insrec (key, key2, inf, infsz, bbeg, loc, lastb, pn, asp, idm);
      loc = (char *) &indph->ind_off;
      recmjform (OLD, seg_n, pn, idm, loc - asp, size2b, loc, 0);
      indph->ind_off += sz;
    }
  assert (check_ind_page (asp) == 0);
  putwul (pg, 'm');
  return (0);
}

static char *
find_largest_key (struct A *pg)
{
  char  *a, *asp;
  u2_t  pn;
  struct ind_page *indph;

  asp = pg->p_shm;
  indph = (struct ind_page *) asp;
  do
    {
      a = asp + indph->ind_off - size2b;
      pn = t2bunpack (a);
      putwul (pg, 'n');
      thread_s_put (pn);
      if ((asp = getpg (pg, seg_n, pn, 's')) == NULL)
	return (NULL);		/* Lock and request */
      indph = (struct ind_page *) asp;
    }
  while (indph->ind_wpage != LEAF);
  thread_s.u = thread_s.d - 1;
  return (asp);
}

static int
divsn_modlast (char *key, char *key2, u2_t pn, char *mas, i4_t massz);

static int
divup_modlast (char *key, char *key2, char *nkey, char *nkey2,
               char *lnkey, char *lnkey2, u2_t * newpn)
{
  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, 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, key, key2, nkey, &rbeg, &rloc, &ibeg1, &iloc1, &sz1);
  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 + kszcal (lnkey, afn, d_f) + 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 (nkey, nkey2, 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)
        {
          putwul (&pg, 'n');
          ans = divsn_modlast (key, key2, uppn, mas, massz);
        }
      else
        ans = crnlev (&pg, mas, mas + massz, BTWN);
      if (ans < 0)
	emptypg (seg_n, *newpn, 'n');
      xfree ((void *) mas);
      return (ans);
    }
  else
    {
      if (indph->ind_wpage != IROOT)
	{			/* pn is not root */
	  putwul (&pg, 'n');
	  if (modlast (key, key2, nkey, nkey2, uppn) < 0)
	    return (-1);
	  asp = getwl (&pg, seg_n, uppn);	/* get pn without lock */
	  indph = (struct ind_page *) asp;
	}
      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 int
divsn_modlast (char *key, char *key2, u2_t pn, char *mas, i4_t massz)
{
  char *lastb, *a, *b, *middleb, *asp;
  i4_t n1, lbeg, lnbeg, pr;
  char *nkey, *nkey2, *lnkey, *lnkey2;
  u2_t nels, newpn;
  i4_t idm;
  struct ind_page *indph;
  struct A pg;

  lastb = mas + massz;
  middleb = mas + massz / 2;
  repttn (mas, lastb, k2sz + size2b, middleb, &nkey, &nkey2, &lnkey,
          &lnkey2, &n1, &nels, &lbeg, &lnbeg, &pr, (char *) NULL);
  if (divup_modlast (key, key2, nkey, nkey2, lnkey, lnkey2, &newpn) < 0)
    return (-1);
  asp = getwl (&pg, seg_n, pn);	/* get pn without lock */
  indph = (struct ind_page *) asp;