sort.c

免费的Sql数据库系统

/*
 *  sort.c - Sort a temporary table, a filter by keys values and a filter by tids
 *           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: sort.c,v 1.245 1997/03/31 03:46:38 kml Exp $ */

#include "setup_os.h"

#include "dessrt.h"
#include "pupsi.h"
#include "sctp.h"
#include "fdclsrt.h"
 
/*------------Global sort variables -----------------------*/
i4_t N;
i4_t NFP;
i4_t NE;
i4_t NB;
u2_t kn;
u2_t fdfn;
u2_t trn;
i4_t EXNSSIZE;
u2_t pnex,lastpnex;
u2_t inpn,outpn;
u2_t freesz;
u2_t offset;
char *adrseg;
char *regakr;
char *akr;
char **regpkr;
struct A *outpage,*inpage;
u2_t *arrpn;
u2_t *arrfpn;
u2_t *cutfpn;
struct A mpage[PINIT];
char *masp[PINIT];
char *outasp;
char *inasp;
char *nonsense;
COST cost;
i4_t pinit;
i4_t need_free_pages;

/*---------------------------------------------------------*/
extern i4_t segsize;
 
#define PRINT(x) PRINTF(x) 

int
trsort(u2_t *fpn, struct des_field *adf,
       u2_t *mfn, char prdbl, char *drctn)
{
  char *asp;
  u2_t pn, ind, *ai, *ali;
  struct A page[2];
  struct el_tree *q = NULL;

  inpage = page;
  outpage = page + 1;
  
  PRINT (("SRT: trsort:    trn = %d,    kn = %d,     fdfn = %d\n",
          trn, kn, fdfn));
  
  bgnng ();
  for (pn = *fpn; pn != (u2_t) ~ 0;)
    {
      asp = getpage (inpage, NRSNUM, pn);
      ai = (u2_t *) (asp + phtrsize);
      ali = ai + ((struct p_h_tr *) asp)->linptr;
      if (ai == ali && pn == *fpn)
	{
	  outpn = pn;
	  goto end;
	}
      for (ind = 0; ai <= ali; ai++, ind++)
        if (*ai != 0)
          rkfrm (asp + *ai, pn, ind, prdbl, drctn, MINIT, adf, mfn);
      pn = ((struct listtob *) asp)->nextpn;
      putpage (inpage, 'n');
    }
  PRINT (("SRT: trsort:  2 N = %d, kn = %d, fdfn = %d\n", N, kn, fdfn));  
  
  if (NB == 0)
    {
      char *pkr;
      i4_t i;
      NE = 0;
      quicksort (MINIT, prdbl, drctn, mfn, adf);      
      *fpn = outpn = pnex;
      outasp = getnew (outpage, NRSNUM, pnex);
      ((struct listtob *) outasp)->prevpn = (u2_t) ~ 0;
      freesz = BD_PAGESIZE - phtrsize;
      for ( i = 0; i < N; i++)
	if (regpkr[i] != nonsense)
	  break;
      inpn = t2bunpack (regpkr[i] + size2b);
      inasp = getpage (inpage, NRSNUM, inpn);
      for ( ; i < N; i++)
	{
	  pkr = regpkr[i];
	  if (pkr != nonsense)
	    putcrt (pkr);
	}
    }
  else
    {
      char *a;
      struct el_tree tree[PINIT];
      q = extsort (MINIT, prdbl, drctn, mfn, adf, tree);
      a = q->pket + size2b;
      inpn = t2bunpack (a);
      inasp = getpage (inpage, NRSNUM, inpn);
      outpn = getfpn ();
      *fpn = outpn;
      freesz = BD_PAGESIZE - phtrsize;
      need_free_pages = NO;
      push (putcrt, tree, q, prdbl, drctn, mfn, adf, NB);
    }
  ((struct listtob *) outasp)->nextpn = (u2_t) ~ 0;
  putpage (outpage, 'm');  
  
end:
  putpage (inpage, 'n');
  ADMT_putext (arrfpn, NE);
  return (outpn);
}

int
flsort(u2_t segn, u2_t *fpn, struct des_field *adf,
       u2_t *mfn, char prdbl, char *drctn)
{
  char *asp, *aspfl, *lastb;
  u2_t pn, ind, flpn, *ai, *afi, oldpn;
  struct el_tree *q = NULL;
  struct des_tid *tid;
  struct A page[3], *inflpage;
  
  inpage = page;
  outpage = page + 1;
  inflpage = page + 2;
  
  PRINT (("SRT: flsort:    trn = %d,    kn = %d,     fdfn = %d\n",
          trn, kn, fdfn));
  
  bgnng ();
  for (flpn = *fpn; flpn != (u2_t) ~ 0;)
    {
      aspfl = getpage (inflpage, NRSNUM, flpn);
      lastb = aspfl + ((struct p_h_f *) aspfl)->freeoff;
      tid = (struct des_tid *) (aspfl + phfsize);
      oldpn = tid->tpn;
      asp = getpage (inpage, segn, oldpn);
      afi = (u2_t *) (asp + phsize);
      for (; tid < (struct des_tid *) lastb; tid++)
	{
	  pn = tid->tpn;
	  if (oldpn != pn)
	    {
	      putpage (inpage, 'n');
	      asp = getpage (inpage, segn, pn);
	      oldpn = pn;
	      afi = (u2_t *) (asp + phsize);
	    }
	  ind = tid->tindex;
	  ai = afi + ind;
	  if (*ai != 0)
	    rkfrm (asp + *ai, pn, ind, prdbl, drctn, MINIT, adf, mfn);
	}
      flpn = ((struct listtob *) aspfl)->nextpn;
      putpage (inflpage, 'n');      
    }
  if (NB == 0)
    {
      char *pkr;
      i4_t i;
      NE = 0;
      quicksort (MINIT, prdbl, drctn, mfn, adf);      
      *fpn = outpn = pnex;
      outasp = getnew (outpage, NRSNUM, pnex);
      ((struct listtob *) outasp)->prevpn = (u2_t) ~ 0;
      offset = phfsize;
      for ( i = 0; i < N; i++)
	if (regpkr[i] != nonsense)
	  break;
      inpn = t2bunpack (regpkr[i] + size2b);
      inasp = getpage (inpage, NRSNUM, inpn);
      for ( ; i < N; i++)
	{
	  pkr = regpkr[i];
	  if (pkr != nonsense)
	    puttid (pkr);
	}
    }
  else
    {
      struct el_tree tree[PINIT];
      q = extsort (MINIT, prdbl, drctn, mfn, adf, tree);
      inpn = t2bunpack (q->pket + size2b);
      inasp = getpage (inpage, NRSNUM, inpn);
      outpn = getfpn ();
      *fpn = outpn;
      offset = phfsize;
      need_free_pages = NO;      
      push (puttid, tree, q, prdbl, drctn, mfn, adf, NB);
    }
  ((struct listtob *) outasp)->nextpn = (u2_t) ~ 0;
  putpage (outpage, 'm');   
  putpage (inpage, 'n');
  ADMT_putext (arrfpn, NE);
  return (outpn);
}

int
tidsort (u2_t * fpn)
{
  char *aspfl, *lastb;
  i4_t recsz;
  u2_t flpn;
  struct el_tree *q = NULL;
  struct des_tid *tid;
  struct A page[2];

  inpage = page;
  outpage = page + 1;
  
  PRINT (("SRT: tidsort:    trn = %d\n", trn));
  
  bgnng ();
  fdfn = 2;
  kn = 2;
  recsz = 2 * size2b;
  for (flpn = *fpn; flpn != (u2_t) ~ 0;)
    {
      aspfl = getpage (inpage, NRSNUM, flpn);
      lastb = aspfl + ((struct p_h_f *) aspfl)->freeoff;
      tid = (struct des_tid *) (aspfl + phfsize);
      for (; tid < (struct des_tid *) lastb; tid++)
	{
	  if (freesz < recsz)
	    {			/* initial cut form */
	      quick_sort_tid (MINIT);
	      puts_tid ();
	      N = 0;
	      if ((NB % pinit) == 0)
		cutfpn = (u2_t *) realloc ((void *) cutfpn,
                                            (size_t) (pinit + NB) * size2b);
	    }
          bcopy ((char *) tid, akr, recsz);
          akr += recsz;
	  freesz -= recsz;
	}
      flpn = ((struct listtob *) aspfl)->nextpn;
      putpage (inpage, 'n');      
    }
  if (NB == 0)
    {
      i4_t i;
      NE = 0;
      quick_sort_tid (MINIT);      
      *fpn = outpn = pnex;
      outasp = getnew (outpage, NRSNUM, pnex);
      ((struct listtob *) outasp)->prevpn = (u2_t) ~ 0;
      offset = phfsize;
      for (i = 0; i < N; i++, regakr += tidsize)
	put_tid (regakr);
    }
  else
    {
      struct el_tree tree[PINIT];
      q = ext_sort_tid (MINIT, tree);
      outpn = getfpn ();
      *fpn = outpn;
      offset = phfsize;
      freesz = BD_PAGESIZE - offset;
      need_free_pages = NO;      
      push_tid (put_tid, tree, q, N);
    }
  ((struct listtob *) outasp)->nextpn = (u2_t) ~ 0;
  putpage (outpage, 'm');    
  ADMT_putext (arrfpn, NE);
  return (outpn);
}

void
bgnng (void)
{
  cost = (COST) 0;
  N = 0;
  NB = 0;
  NE = 0;
  addext ();
  regakr = adrseg;
  regpkr = (char **) (adrseg + segsize);
  freesz = segsize;
  akr = regakr;
}

u2_t 
getfpn (void)
{
  pnex = getext ();
  lastpnex = pnex + EXNSSIZE;
  outasp = getnew (outpage, NRSNUM, pnex);
  ((struct listtob *) outasp)->prevpn = (u2_t) ~ 0;
  return (pnex);
}

void
addext (void)
{
  pnex = getext ();
  arrfpn[NE++] = pnex;
  lastpnex = pnex + EXNSSIZE;
  if ((NE % pinit) == 0)
    arrfpn = (u2_t *) realloc ((void *) arrfpn, (size_t) (NE + pinit) * size2b);
}