ind_ins.c

免费的Sql数据库系统

/*
 *  ind_ins.c  - Index Control Programm
 *               functions dealing with insertion into an index
 *               Kernel of GNU SQL-server 
 *
 * This file is a part of GNU SQL Server
 *
 *  Copyright (c) 1996, 1997, Free Software Foundation, Inc
 *  Developed at the Institute of System Programming
 *  This file is written by  Vera Ponomarenko
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 *
 *  Contacts:   [e-mail]
 *
 */

/* $Id: ind_ins.c,v 1.247 1997/04/15 11:45:41 vera Exp $ */

#include "xmem.h"
#include <assert.h>
#include "destrn.h"
#include "strml.h"
#include "fdcltrn.h"

struct des_field *d_f, *d_f2;
u2_t *afn;
u2_t k_n;
u2_t seg_n;
i4_t k2sz;
i4_t inf_size;
u2_t uniq_key;

ARR_DECL     (thread_s,u2_t,no_static); /* declaration of dynamic stack/array 'thread_s'. */
ARR_PROC_DECL(thread_s,u2_t,no_static); /* declaration of routines for it                 */

#define FIND_LAST_KEY(asp,elsz,lkey,lkey2,keysz)\
{\
  char *pnt, *lastb;\
  u2_t n;\
  lastb = asp + ((struct ind_page *) asp)->ind_off;\
  pnt = asp + indphsize;\
  assert(pnt < lastb);\
  while (pnt < lastb)\
    {\
      n = t2bunpack (pnt);\
      pnt += size2b;\
      lkey = pnt;\
      keysz = kszcal (lkey, afn, d_f);\
      pnt += keysz + n * elsz;\
    }\
  lkey2 = pnt - elsz;\
}

int
check_ind_page (char *asp)
{
  char *cur_key, *prev_key, *a, *lastb;
  u2_t n;
  i4_t ksz, elsz;
  struct ind_page *indph;

  indph = (struct ind_page *) asp;
  if (indph->ind_wpage == LEAF)
    elsz = k2sz + inf_size;
  else
    elsz = k2sz + size2b;
  lastb = asp + indph->ind_off;
  a = asp + indphsize;
  n = t2bunpack (a);
  a += size2b;
  prev_key = a;
  ksz = kszcal (prev_key, afn, d_f);
  a += ksz + n * elsz;
  while (a < lastb)
    {
      n = t2bunpack (a);
      a += size2b;
      cur_key = a;
      ksz = kszcal (cur_key, afn, d_f);
      if (cmpkeys (k_n, afn, d_f, cur_key, prev_key) <= 0)
        return -1;
      a += ksz + n * elsz;
      prev_key = cur_key;
    }
  return 0;
}

static int
insrep (char *asp, char *lastb, char *key, char *key2,
        i4_t elsz, char **bbeg, char **loc)
{
  char *a, *ckey;
  u2_t n;
  i4_t agsz = 0, keysz, ksz, l, l2;

  keysz = kszcal (key, afn, d_f);
  a = asp + indphsize;
  for (; a < lastb; a += agsz)
    {
      *bbeg = a;
      n = t2bunpack (a);
      assert (n < BD_PAGESIZE / 2);
      ckey = a + size2b;
      ksz = kszcal (ckey, afn, d_f);
      if ((l = cmpkeys (k_n, afn, d_f, ckey, key)) == 0)
	{
	  if (uniq_key == UNIQ)
	    return (0);
	  a += size2b + ksz;
	  for (; n != 0; n--, a += elsz)
            {
              if ((l2 = cmp2keys (d_f2->field_type, a, key2)) > 0)
                break;
              assert (l2 != 0);      /* Tne second key isn't unique */
            }
	  *loc = a;
	  return (elsz);
	}
      else if (l > 0)
	{
	  *loc = a;
	  return (size2b + keysz + elsz);
	}
      agsz = size2b + ksz + n * elsz;
    }
  *bbeg = a;
  *loc = a;
  return (size2b + keysz + elsz);
}

static void
icp_insrec (char *key, char *key2, char *inf, i4_t infsz, char *beg,
            char *loc, char *lastb, u2_t pn, char *asp, i4_t idm)
{
  char *src, *dst;
  u2_t fs;
  i4_t sz;

  fs = lastb - loc;
  if (beg == loc)
    {
      i4_t keysz;
      keysz = kszcal (key, afn, d_f);
      sz = size2b + keysz + k2sz + infsz;
      if (asp != NULL)
	recmjform (SHF, seg_n, pn, idm, loc - asp, fs, NULL, -sz);
      for (src = lastb - 1, dst = src + sz; fs != 0; fs--)
	*dst-- = *src--;
      t2bpack (1, beg);
      loc += size2b;
      bcopy (key, loc, keysz);
      loc += keysz;
    }
  else
    {
      sz = k2sz + infsz;
      if (asp != NULL)
	recmjform (SHF, seg_n, pn, idm, loc - asp, fs, NULL, -sz);
      for (src = lastb - 1, dst = src + sz; fs != 0; fs--)
	*dst-- = *src--;
      if (asp != NULL)
	recmjform (OLD, seg_n, pn, idm, beg - asp, size2b, beg, 0);
      mod_nels (1, beg);
    }
  bcopy (key2, loc, k2sz);
  bcopy (inf, loc + k2sz, infsz);
}

static int
repet1 (char *asp, char *bbeg, char *a, i4_t elsz, char *middleb, char **lkey,
        char **lkey2, char **lnkey, char **lnkey2, i4_t *n1, u2_t *nels,
        i4_t *lbeg, i4_t *lnbeg, i4_t *pr, char *frkey)
{
  char *lastb, *ckey;
  i4_t ksz, agsz, n2;
  u2_t n;

  lastb = asp + ((struct ind_page *) asp)->ind_off;
  ckey = *lnkey;
  n = t2bunpack (bbeg);
  assert (n < BD_PAGESIZE / 2);
  ksz = kszcal (bbeg + size2b, afn, d_f);
  if (bbeg != a)
    {				/* not new element */
      char *b;
      b = bbeg;
      b += size2b + ksz;
      for (; b != a; n--)
	b += elsz;
      for (; n != 0; n--)
	if (a + elsz < middleb)
	  {
	    *lnkey2 = a;
	    a += elsz;
	  }
	else
	  goto m1;
    }
  for (; a < lastb;)
    {
      bbeg = a;
      n = t2bunpack (a);
      assert (n < BD_PAGESIZE / 2);
      ksz = kszcal (a + size2b, afn, d_f);
      agsz = size2b + ksz + n * elsz;
      if (a + agsz < middleb)
	{
	  *lnkey = a + size2b;
	  a += agsz;
	  *lnkey2 = a - elsz;
	}
      else
	break;
    }
  ckey = a + size2b;
  agsz = size2b + ksz + elsz;
  if (a + agsz < middleb)
    {
      *lnkey = a + size2b;
      a += agsz;
      *lnkey2 = a - elsz;
      for (n--; n != 0; n--)
	if (a + elsz < middleb)
	  {
	    *lnkey2 = a;
	    a += elsz;
	  }
	else
	  break;
    }
  else
    n = 0;
m1:
  n2 = lastb - a;
  *n1 = a - asp;
  *lnbeg = bbeg - asp;
  if (n != 0)
    {
      ksz = kszcal (*lnkey, afn, d_f);
      n2 += size2b + ksz;
      *nels = n;
      a += n * elsz;
    }
  else
    *nels = 0;
  for (; a < lastb; a += ksz + n * elsz)
    {
      bbeg = a;
      n = t2bunpack (a);
      assert (n < BD_PAGESIZE / 2);
      a += size2b;
      ckey = a;
      ksz = kszcal (a, afn, d_f);
    }
  *lbeg = a - bbeg;
  if (frkey != NULL)
    if (cmpkeys (k_n, afn, d_f, ckey, frkey) == 0)
      {
	*pr = 0;
	n2 -= ksz + size2b;
      }
    else
      *pr = 1;
  *lkey = ckey;
  *lkey2 = lastb - elsz;
  return (n2);
}

static int
repttn (char *mas, char *lastb, i4_t elsz, char *middleb, char **lkey,
        char **lkey2, char **lnkey, char **lnkey2, i4_t *n1,
        u2_t *nels, i4_t *lbeg, i4_t *lnbeg, i4_t *pr, char *frkey)
{
  char *a, *bbeg, *ckey;
  i4_t agsz = 0, ksz, n2;
  u2_t n;

  a = mas;
  do      
    {
      n = t2bunpack (a);
      assert (n < BD_PAGESIZE / 2);
      bbeg = a - agsz;
      ksz = kszcal (a + size2b, afn, d_f);
      agsz = size2b + ksz + n * elsz;
      if (a + agsz > middleb)
	break;
      a += agsz;
    }
  while( a < lastb);
  *lnkey = bbeg + size2b;
  *lnkey2 = a - elsz;
  *lnbeg = bbeg - mas;
  bbeg = a;
  agsz = size2b + ksz + elsz;
  if (a + agsz < middleb)
    {
      *lnkey = a + size2b;
      *lnbeg = a - mas;
      a += agsz;
      *lnkey2 = a - elsz;
      for (n--; n != 0; n--)
	if (a + elsz < middleb)
	  {
	    *lnkey2 = a;
	    a += elsz;
	  }
	else
	  break;
    }
  else
    n = 0;
  *n1 = a - mas;
  n2 = lastb - a;
  if (n != 0)
    {
      n2 += size2b + ksz;
      *nels = n;
      a += n * elsz;
    }
  else
    *nels = 0;
  for (; a < lastb; a += ksz + n * elsz)
    {
      bbeg = a;
      n = t2bunpack (a);
      assert (n < BD_PAGESIZE / 2);
      a += size2b;
      ksz = kszcal (a, afn, d_f);
    }
  ckey = bbeg + size2b;
  *lbeg = a - bbeg;
  if (frkey != NULL)
    {
      if (cmpkeys (k_n, afn, d_f, ckey, frkey) == 0)
	{
	  *pr = 0;
	  n2 -= ksz + size2b;
	}
      else
	*pr = 1;
    }
  *lkey = ckey;
  *lkey2 = lastb - elsz;
  return (n2);
}

static char *
pereliv (char *asp, i4_t n, u2_t nels, char *key, char *mas, i4_t massz)
                /* n - a number of bytes from the first page */
     		/* nels - element number from the first page */
{
  char *a, *b, *c, *lastb;

  lastb = asp + ((struct ind_page *) asp)->ind_off;
  for (b = lastb - 1, a = b + n, c = asp + indphsize; b >= c;)
    *a-- = *b--;
  a = asp + indphsize;
  if (nels != 0)
    {
      i4_t ksz;
      t2bpack (nels, a);
      a += size2b;
      ksz = kszcal (key, afn, d_f);
      bcopy (key, a, ksz);
      a += ksz;
    }
  bcopy (mas, a, massz);
  return (a + massz);
}

static void
per22 (u2_t pn, u2_t rbrpn, i4_t n1, i4_t n2, u2_t nels, i4_t lbeg, i4_t lnbeg,
       i4_t pr, i4_t prpg, i4_t sz, char *key, char *key2, char *inf, char *lnkey,
       i4_t offbeg, i4_t offloc)         /* if pr==0 then lastkey==frkey */
{
  char *a, *lastb, *asp, *aspr, *end1;
  u2_t fnels;  /* element number of the first aggregate of a right brother */
  struct ind_page *indph, *indphr;
  i4_t idm, idmr;
  struct A pg, pgr;

  asp = getwl (&pg, seg_n, pn);	/* get pn without lock */
  aspr = getwl (&pgr, seg_n, rbrpn);	/* get pn without lock */
  indph = (struct ind_page *) asp;
  indphr = (struct ind_page *) aspr;
  idm = ++((struct p_head *) asp)->idmod;
  idmr = ++((struct p_head *) aspr)->idmod;
  if (pr == 0)
    recmjform (OLD, seg_n, rbrpn, idmr, indphsize, size2b, aspr + indphsize, 0);
  fnels = t2bunpack (aspr + indphsize);
  if (nels != 0)
    {
      recmjform (OLD, seg_n, pn, idm, lnbeg, size2b, asp + lnbeg, 0);
      mod_nels ((-nels), asp + lnbeg);
    } 
  lastb = asp + indph->ind_off;
  end1 = asp + n1;
  recmjform (OLD, seg_n, pn, idm, n1, lastb - end1, end1, 0);
  recmjform (SHF, seg_n, rbrpn, idmr, n2 + indphsize,
             indphr->ind_off - indphsize, NULL, -n2);
  a = pereliv (aspr, n2, nels, lnkey, end1, indph->ind_off - n1);
  if (pr == 0)
    {
      if (lbeg > n2)
	lbeg = n2;
      mod_nels (fnels, a - lbeg);
      if (lbeg == n2)
	{
          char *b;
          i4_t size;
	  b = a + size2b + kszcal (aspr + indphsize + size2b, afn, d_f);
          size = aspr + indphr->ind_off + n2 - b;
          bcopy (b, a, size);
	}
    }
  if (prpg == 1)
    {		/* An insertion in the first page */
      icp_insrec (key, key2, inf, inf_size, asp + offbeg,
                  asp + offloc, end1, pn, asp, idm);
      n1 += sz;
    }
  else		/* An insertion in the right brother page */
    icp_insrec (key, key2, inf, inf_size, aspr + offbeg,
                aspr + offloc, a, rbrpn, aspr, idmr);
  a = (char *) &indph->ind_off;
  recmjform (OLD, seg_n, pn, idm, a - asp, size2b, a, 0);
  indph->ind_off = n1;
  a = (char *) &indphr->ind_off;
  recmjform (OLD, seg_n, rbrpn, idmr, a - aspr, size2b, a, 0);
  indphr->ind_off += n2;
  assert (check_ind_page (asp) == 0);
  putwul (&pg, 'm');		/* put page without unlock */
  assert (check_ind_page (aspr) == 0);
  putwul (&pgr, 'm');
}

static int
rep_2_3 (char *mas, i4_t massz, i4_t elsz, char *aspr, i4_t *n1, u2_t * nels,
         i4_t *lbeg, i4_t *lnbeg, char **nkey, char **nkey2, i4_t *pr)
{
  char *middleb, *frkey, *lkey, *lkey2, *lnkey, *lnkey2;
  i4_t off, n2, middle;

  off = ((struct ind_page *) aspr)->ind_off;
  middleb = mas + (massz + off - indphsize) / 3;
  frkey = aspr + indphsize + size2b;
  n2 = repttn (mas, mas + massz, elsz, middleb, &lkey, &lkey2, &lnkey,
               &lnkey2, n1, nels, lbeg, lnbeg, pr, frkey);
  middle = (n2 + off - indphsize) / 2;
  if (off - middle > indphsize)
    {
      char *a;
      u2_t n, agsz = 0;
      middleb = aspr + ((n2 + off) / 2 - n2);
      for (a = aspr + indphsize; a + agsz < middleb;)
	{
	  a += agsz;
	  n = t2bunpack (a);
          assert (n < BD_PAGESIZE / 2);
	  a += size2b;
	  agsz = kszcal (a, afn, d_f) + n * elsz;
	}
      *nkey = a;
      *nkey2 = a + agsz - elsz;
      n2 = a + agsz - aspr;
      if (n2 == indphsize)
	n2 = 0;
    }
  else
    n2 = 0;
  return (n2);
}

static int
crnlev (struct A *pg, char *mas, char *lastb, i4_t wpage)
{			/* a creation of a new level */
  char *a, *b, *middleb, *asp;
  char *lnkey, *lnkey2, *lkey, *lkey2, *inf1, *inf2;
  i4_t n1, lbeg, lnbeg, pr, ksz, size, elsz;
  u2_t newpn1, newpn2, nels, offn;
  struct A pgn;
  struct ind_page *indph;
  i4_t idm;

  if (wpage == LEAF)
    elsz = k2sz + inf_size;
  else
    elsz = k2sz + size2b;
  middleb = mas + (lastb - mas) / 2;
  repttn (mas, lastb, elsz, middleb, &lkey, &lkey2, &lnkey,
          &lnkey2, &n1, &nels, &lbeg, &lnbeg, &pr, NULL);
  if (lenforce ()< 0)
    {
      putwul (pg, 'n');
      return (-1);
    }
  newpn1 = getempt (seg_n);
  asp = getnew (&pgn, seg_n, newpn1);	/* get new page */
  indph = (struct ind_page *) asp;
  bcopy (mas, asp + indphsize, n1);
  indph->ind_off = n1 + indphsize;
  if (nels != 0)
    mod_nels ((-nels), asp + lnbeg + indphsize);
  newpn2 = getempt (seg_n);
  indph->ind_nextpn = newpn2;
  indph->ind_wpage = wpage;
  offn = indph->ind_off;
  assert (check_ind_page (asp) == 0);
  putwul (&pgn, 'm');
  asp = getnew (&pgn, seg_n, newpn2);	/* get new page */
  indph = (struct ind_page *) asp;
  a = asp + indphsize;
  ksz = kszcal (lnkey, afn, d_f);
  if (nels != 0)
    {
      /*      write_key (nels, a, lnkey, ksz);*/
      t2bpack (nels, a);
      a += size2b;
      bcopy (lnkey, a, ksz);