tidsrt.c

免费的Sql数据库系统

/*  tidsrt.c - Functions dealing with sort a filter by tid's
 *             Kernel of GNU SQL-server. Sorter     
 *
 *  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: tidsrt.c,v 1.245 1997/03/31 03:46:38 kml Exp $ */

#include "xmem.h"
#include "dessrt.h"
#include "f1f2decl.h"
#include "fdclsrt.h"

extern i4_t N, NB, NFP;
extern i4_t pinit;
extern char *nonsense;
extern char *regakr;
extern char *outasp;
extern struct A *outpage;
extern u2_t pnex, lastpnex, freesz;
extern u2_t offset;
extern i4_t EXNSSIZE;
extern u2_t *arrpn;
extern u2_t *cutfpn;
extern u2_t outpn;
extern char *masp[];
extern struct A mpage[];
extern char *akr;
extern char **regpkr;
extern i4_t segsize;
extern i4_t need_free_pages;

void
quick_sort_tid (i4_t M)
{
  i4_t bstek[STEKSZ];
  i4_t *stek, l, r, i, j, v;
  char **ptp, *curpk;

  ptp = (char **) regakr;
  stek = bstek;
  for (l = 1, r = N;;)
    {
      if ((r - l) < M)
	{			/* The simple insertion sort */
	  for (j = l + 1; j <= r; j++)
	    {
	      curpk = ptp[j];
	      for (i = j - 1; i >= l;)
		if ((v = cmp_tid (curpk, ptp[i])) < 0)
		  {
		    ptp[i + 1] = ptp[i];
		    i--;
		  }
		else
		  break;
	      ptp[i + 1] = curpk;
	    }
	  if (stek == bstek)
	    break;
	  r = *stek--;
	  l = *stek--;
	  continue;
	}
      i = l;			/* quicksort */
      j = r;
      curpk = ptp[l];
  m1:
      for (v = -1; v < 0; j--)
	v = cmp_tid (curpk, ptp[j]);
      if (i >= j)
	{
	  ptp[i] = curpk;
	  goto m3;
	}
      ptp[i++] = ptp[j];
      for (v = -1; v < 0; i++)
	v = cmp_tid (ptp[i], curpk);
      if (i < j)
	{
	  ptp[j] = ptp[i];
	  j--;
	  goto m1;
	}
      ptp[j] = curpk;
      i = j;
    m3:if ((i - l) <= (r - i))
	{
	  *stek++ = i + 1;
	  *stek++ = r;
	  r = i - 1;
	}
      else
	{
	  *stek++ = l;
	  *stek++ = i - 1;
	  l = i + 1;
	}
    }
}

void
puts_tid (void)
{
  char *asp, *a;
  i4_t i;
  u2_t off, fpn;
  struct des_tid *tid;

  asp = getnew (outpage, NRSNUM, pnex);
  off = size4b;
  a = asp + off;
  fpn = pnex;  
  for (tid = (struct des_tid *) regakr, i = 0; i < N; i++, tid++)
    {
      if ((tidsize + off) > BD_PAGESIZE)
	{
	  ++pnex;
	  if (pnex == lastpnex)
	    addext ();
	  t2bpack (pnex, asp);
	  t2bpack (off, asp + size2b);
	  putpage (outpage, 'm');
	  asp = getnew (outpage, NRSNUM, pnex);
	  off = size4b;
	  a = asp + off;
	}
      bcopy ((char *) tid, a, tidsize);
      a += tidsize;
      off += tidsize;
    }
  t2bpack ((u2_t) ~ 0, asp);
  t2bpack (off, asp + size2b);
  putpage (outpage, 'm');
  cutfpn[NB] = fpn;
  NB++;
  pnex++;
  if (pnex == lastpnex)
    addext ();
  akr = regakr;
  freesz = segsize;  
}

struct el_tree *
ext_sort_tid (i4_t M, struct el_tree *tree)
{
  i4_t i, l, j, i1, v, nbnum, cutcnt;
  u2_t P;
  struct el_tree *ptr1, *ptr2, *ptr3, *q;

  quick_sort_tid (M);
  puts_tid ();
  
  need_free_pages = YES;
  for (i = 0; pnex != lastpnex; i++)
    {
      arrpn[i] = pnex++;
      if (i == NFP)
	{
	  NFP += EXNSSIZE;
	  arrpn = (u2_t *) realloc ((void *) arrpn, (size_t) NFP * size2b);
	}
    }
  for (; i < NFP; i++)
    arrpn[i] = (u2_t) ~ 0;
  q = NULL;
  for (cutcnt = 0; ; cutcnt = 0)
    {			/* The external sort by replacement selecting */
      for (P = 0; P < NB;)
	{
	  if (NB > pinit)
	    if (NB - P + cutcnt < pinit)
	      {
		for (i = P; P < NB; i++)
		  cutfpn[cutcnt++] = cutfpn[i];
		NB= cutcnt;
	      }	  
	  for (nbnum = 0; nbnum < pinit && P < NB; nbnum++, P++)
	    if ((masp[nbnum] = getpage (&mpage[nbnum], NRSNUM, cutfpn[P])) == NULL)
	      break;
	  if (nbnum == 0)
	    perror ("SRT.ext_sort_tid: No segments for key file pages");
	  if (P == 1)
	    {
	      tree->pket = masp[0] + size4b;
	      return (tree);
	    }
	  if (nbnum == 1)
	    perror ("SRT.extsort: Serious error nbnum == 1");	    

	  for (i = 0; i < nbnum; i++)
	    {			/* initial tree */
	      ptr1 = tree + i;
	      ptr1->pket = masp[i] + phfsize;
	      ptr1->fe = tree + (i + nbnum) / 2;
	      ptr1->fi = tree + i / 2;
	    }
	  l = nbnum / 2;
	  if (nbnum % 2 != 0)
	    l++;
	  for (j = nbnum - 1; j >= l; j--)
	    {			
	      i = (2 * j) % nbnum;	/* j - node counter, i - tree index */
	      i1 = i + 1;
	      ptr1 = tree + i;
	      ptr2 = tree + i1;
	      ptr3 = tree + j;
	      if ((v = cmp_tid (ptr1->pket, ptr2->pket)) <= 0)
		{
		  ptr3->lsr = ptr2;
		  ptr3->first = ptr1;
		}
	      else
		{
		  ptr3->lsr = ptr1;
		  ptr3->first = ptr2;
		}
	    }
	  for (; j > 0; j--)
	    {			
	      i = 2 * j;
	      if ((i1 = i + 1) == nbnum)
		i1 = 0;
	      tree->first = tree;
	      ptr1 = (tree + i)->first;
	      ptr2 = (tree + i1)->first;
	      ptr3 = tree + j;
	      if ((v = cmp_tid (ptr1->pket, ptr2->pket)) <= 0)
		{
		  ptr3->lsr = ptr2;
		  ptr3->first = ptr1;
		}
	      else
		{
		  ptr3->lsr = ptr1;
		  ptr3->first = ptr2;
		}
	    }
	  q = tree->lsr = (tree + 1)->first;	/* The new champion */
	  if (NB <= pinit)
	    {
	      NB = nbnum;
	      return (q);
	    }
	  getptmp ();
	  outasp = getnew (outpage, NRSNUM, outpn);	  
	  offset = size4b;
	  cutfpn[cutcnt++] = outpn;		  
	  push_tid (middle_put_tid, tree, q, nbnum);
	  t2bpack ((u2_t) ~0, outasp);
	  t2bpack (offset, outasp + size2b);
	  putpage (outpage, 'm');		  
	}
      NB = cutcnt;
    }
}

void
push_tid (void (*pnt_puttid) (), struct el_tree *tree, struct el_tree *q, i4_t nbnum)
{
  struct el_tree *ptree, *qq;
  char *pkr, *asp, *a;
  i4_t v;
  u2_t off, size, pn;
  struct A *ppage;

  if (nbnum != 1)
    {
      for (;; )
	{				/*To find a loser */
	  (*pnt_puttid) (q->pket);	
	  nbnum = get_el_tr_tid (nbnum, q, q - tree);
	  for (ptree = q->fe ;; ptree = ptree->fi)
	    {
	      if ((v = cmp_tid (ptree->lsr->pket, q->pket)) < 0)
		{
		  qq = q;
		  q = ptree->lsr;
		  ptree->lsr = qq;
		}
	      if (ptree == tree + 1)
		break;
	    }
          if (nbnum == 1)
            break;
	}
    }
  v = q - tree;
  a = masp[v];
  off = t2bunpack (a + size2b);
  pkr = q->pket;
  pn = t2bunpack (a);
  ppage = &mpage[v];
  for (size = a + off - pkr; size != 0; size -= tidsize)
    (*pnt_puttid) (pkr);
  putpage (ppage, 'n');  
  for (; pn != (u2_t) ~ 0;)
    {
      asp = getpage (ppage, NRSNUM, pn);
      pkr = asp + size4b;
      size = t2bunpack (asp + size2b) - size4b;
      for (; size != 0; size -= tidsize)
	(*pnt_puttid) (pkr);
      pn = t2bunpack (asp);      
      putpage (ppage, 'n');      
    }
}

int
get_el_tr_tid (i4_t nbnum, struct el_tree *q, i4_t i)
{
  char *pkr;

  pkr = q->pket;
  pkr += tidsize;
  return (next_el_tree (nbnum, q, i, pkr));
}

int
cmp_tid (char *pnt1, char *pnt2)
{
  i4_t i, v;

  for (i = 0; i < 2; i++)
    {
      if ((v = f2b (pnt1, pnt2, size2b, size2b)) != 0)
	return (v);
      pnt1 += size2b;
      pnt2 += size2b;
    }
  return (0);
}