# 2.11BSD#431 - /usr/ingres/source/dbu/ksort.c

##### Functions

    acc_err           X
    cant              X
    cmpa              X
    get_page          X
    main              X
    makfile           X
    merge             X
    mintup            X
    newfile           X
    oldfile           X
    resetacc          X
    rline             X
    setfil            X
    sort              X
    term              X

##### Variables

    Acc_head          X
    Accbuf            X
    Accuread          X
    Accuwrite         X
    Bucket            X
    Ccount            X
    Desc              X
    Descsort          X
    File              X
    Filep             X
    Fileset           X
    Infile            X
    Lspace            X
    Nfiles            X
    Nlines            X
    Outfile           X
    Trace             X
    Tspace            X
    Tupsize           X
    Tupsout           X

##### Macros

    BUCKETSIZE        X
    ENDKEY            X
    MEM               X
    N                 X

##### struct's

    merg              X

       1: # include   <stdio.h>
       2:
       3: # include   "../ingres.h"
       4: # include   "../aux.h"
       5: # include   "../symbol.h"
       6: # include   "../access.h"
       7:
       8: # define    N   7
       9: # define    MEM (32768 - 2)
      10: # define    BUCKETSIZE  4
      11: # define    ENDKEY  MAXDOM + 1
      12:
      13: /*
      14: **	Trace info comes from trace flag Z23 passed as the
      15: **	second parameter. The bits used are:
      16: **
      17: **		0001	main trace info
      18: **		0002	secondary trace info
      19: **		0004	terciary trace info
      20: **		0010	don't truncate temps
      21: **		0020	don't unlink temps
      22: **		0040	print am page refs
      23: **		0100	print am tuple gets
      24: */
      25:
      26: char            *Infile;
      27: char            *Outfile;
      28: struct descriptor   Desc;
      29: char            Descsort[MAXDOM+1];
      30: FILE            *Oiop;
      31: int         Trace;
      32: int         Tupsize;
      33: int         Bucket;
      34: char            File[15];
      35: char            *Fileset;
      36: char            *Filep;
      37: int         Nfiles = 1;
      38: int         Nlines;
      39: long            Ccount;
      40: char            **Lspace;
      41: char            *Tspace;
      42: extern          term();
      43: extern int      cmpa();
      44: long            Tupsout;
      45:
      46: main(argc, argv)
      47: char **argv;
      48: {
      49:     extern char *Proc_name;
      50:     extern      (*Exitfn)();
      51:     register int    i;
      52:     register int    j;
      53:     register char   *mem;
      54:     char        *start;
      55:     int     maxkey, rev;
      56:     char        *sbrk();
      57:
      58:     Proc_name = "KSORT";
      59:     Exitfn = &term;
      60:
      61:     Fileset = *++argv;
      62:     atoi(*++argv, &Trace);
      63:     if ((i = open(*++argv, 0)) < 0)
      64:         cant(*argv);
      65:     if (read(i, &Desc, sizeof Desc) < sizeof Desc)
      66:         syserr("read(Desc)");
      67:     close(i);
      68:
      69:     /* set up Descsort to indicate the sort order for tuple */
      70:     /* if domain zero is given prepare to generate "hash bucket"
      71: 	** value for tuple */
      72:
      73:     maxkey = 0;
      74:     for (i = 0; i <= Desc.relatts; i++)
      75:         if (j = Desc.relgiven[i])
      76:         {
      77:             if ((rev = j) < 0)
      78:                 j = -j;
      79:             if (maxkey < j)
      80:                 maxkey = j;
      81:             Descsort[--j] = rev < 0 ? -i : i;
      82:         }
      83:
      84:     Descsort[maxkey] = ENDKEY;  /* mark end of list */
      85:
      86:     Tupsize = Desc.relwid;
      87:
      88:     if (Bucket = (Descsort[0] == 0))
      89:     {
      90:         /* we will be generating hash bucket */
      91:         Tupsize += BUCKETSIZE;
      92:         Desc.relfrml[0] = BUCKETSIZE;
      93:         Desc.relfrmt[0] = INT;
      94:         Desc.reloff[0] = Desc.relwid;
      95:     }
      96:
      97:     if (Trace & 01)
      98:     {
      99:         printf("Bucket is %d,Sort is:\n", Bucket);
     100:         for (i = 0; (j = Descsort[i]) != ENDKEY; i++)
     101:             printf("Descsort[%d]=%d\n", i, j);
     102:     }
     103:     if (i = (maxkey - Bucket - Desc.relatts))
     104:         syserr("%d domains missing\n", -i);
     105:     Infile = *++argv;
     106:     Outfile = *++argv;
     107:
     108:     /* get up to 2**15 - 1 bytes of memory for buffers */
     109:     /* note that mem must end up positive so that Nlines computation is right */
     110:     start = sbrk(0); Lspace = (char **) start;
     111:     mem = start + MEM;  /* take at most 2**15 - 1 bytes */
     112:     while (brk(mem) == -1)
     113:         mem -= 512;
     114:     mem -= start;
     115:
     116:     /* compute pointers and sizes into buffer memory */
     117:     Nlines = (unsigned int) mem / (Tupsize + 2);
     118:     Tspace = (char *) (Lspace + Nlines);
     119:     if (Trace & 01)
     120:         printf("Tspace=%l,Lspace=%l,Nlines=%l,mem=%l,start=%l\n",
     121:         Tspace, Lspace, Nlines, mem, start);
     122:
     123:     /* set up temp files */
     124:     concat(ztack("_SYSS", Fileset), "Xaa", File);
     125:     Filep = File;
     126:     while (*Filep != 'X')
     127:         Filep++;
     128:     Filep++;
     129:     if ((signal(2, 1) & 01) == 0)
     130:         signal(2, term);
     131:
     132:     /* sort stage -- create a bunch of temporaries */
     133:     Ccount = 0;
     134:     if (Trace & 01)
     135:         printf("sorting\n");
     136:     sort();
     137:     close(0);
     138:     if (Trace & 01)
     139:     {
     140:         printf("done sorting\n%s tuples written to %d files\n", locv(Tupsout), Nfiles - 1);
     141:         printf("sort required %s compares\n", locv(Ccount));
     142:     }
     143:
     144:     /* merge stage -- merge up to N temps into a new temp */
     145:     Ccount = 0;
     146:     for (i = 1; i + N < Nfiles; i += N)
     147:     {
     148:         newfile();
     149:         merge(i, i + N);
     150:     }
     151:
     152:     /* merge last set of temps into target file */
     153:     if (i != Nfiles)
     154:     {
     155:         oldfile();
     156:         merge(i, Nfiles);
     157:     }
     158:     if (Trace & 01)
     159:     {
     160:         printf("%s tuples in out file\n", locv(Tupsout));
     161:         printf("merge required %s compares\n", locv(Ccount));
     162:     }
     163:     term(0);
     164: }
     165:
     166: sort()
     167: {
     168:     register char   *cp;
     169:     register char   **lp;
     170:     register int    i;
     171:     int     done;
     172:     long        ntups;
     173:     struct tup_id   tid, ltid;
     174:     char        *xp;
     175:     long        pageid;
     176:     long        rhash();
     177:
     178:     done = 0;
     179:     ntups = 0;
     180:     Tupsout = 0;
     181:     if ((Desc.relfp = open(Infile, 0)) < 0)
     182:         cant(Infile);
     183:     Desc.relopn = (Desc.relfp + 1) * 5;
     184:
     185:     /* initialize tids for full scan */
     186:     pageid = 0;
     187:     tid.line_id = -1;
     188:     stuff_page(&tid, &pageid);
     189:     pageid = -1;
     190:     ltid.line_id = -1;
     191:     stuff_page(&ltid, &pageid);
     192:
     193:     do
     194:     {
     195:         cp = Tspace;
     196:         lp = Lspace;
     197:         while (lp < Lspace + Nlines)
     198:         {
     199:             if ((i = get(&Desc, &tid, &ltid, cp, TRUE)) != 0)
     200:             {
     201:                 if (i < 0)
     202:                     syserr("get %d", i);
     203:                 close(Desc.relfp);
     204:                 Desc.relopn = 0;
     205:                 done++;
     206:                 break;
     207:             }
     208:             if (Bucket)
     209:             {
     210:                 /* compute hash bucket and insert at end */
     211:                 pageid = rhash(&Desc, cp);
     212:                 bmove(&pageid, cp + Desc.relwid, BUCKETSIZE);
     213:             }
     214:             *lp++ = cp;
     215:             cp += Tupsize;
     216:             ntups++;
     217:         }
     218:         qsort(Lspace, lp - Lspace, 2, &cmpa);
     219:         if (done == 0 || Nfiles != 1)
     220:             newfile();
     221:         else
     222:             oldfile();
     223:         while (lp > Lspace)
     224:         {
     225:             cp = *--lp;
     226:             xp = cp;
     227:             if ((lp == Lspace) || (cmpa(&xp, &lp[-1]) != 0))
     228:             {
     229:                 if ((i = fwrite(cp, 1, Tupsize, Oiop)) != Tupsize)
     230:                     syserr("cant write outfile %d (%d)", i, Nfiles);
     231:                 Tupsout++;
     232:             }
     233:         }
     234:         fclose(Oiop);
     235:     } while (done == 0);
     236:     if (Trace & 01)
     237:         printf("%s tuples in\n", locv(ntups));
     238: }
     239:
     240: struct merg
     241: {
     242:     char        tup[MAXTUP+BUCKETSIZE];
     243:     int     file_num;
     244:     FILE        *fiop;
     245: };
     246:
     247: merge(a, b)
     248: int a;
     249: int b;
     250: {
     251:     register struct merg    *merg;
     252:     register int        i, j;
     253:     char            *f, *yesno;
     254:     struct merg     *mbuf[N + 1];
     255:     char            *setfil();
     256:
     257:     if (Trace & 02)
     258:         printf("merge %d to %d\n", a, b);
     259:     merg = (struct merg *) Lspace;
     260:     j = 0;
     261:     for (i = a; i < b; i++)
     262:     {
     263:         f = setfil(i);
     264:         mbuf[j] = merg;
     265:         merg->file_num = i;
     266:         if ((merg->fiop = fopen(f, "r")) == NULL)
     267:             cant(f);
     268:         if (!rline(merg))
     269:             j++;
     270:         merg++;
     271:     }
     272:
     273:     i = j - 1;
     274:     if (Trace & 04)
     275:         printf("start merg with %d\n", i);
     276:     while (i >= 0)
     277:     {
     278:         if (Trace & 04)
     279:             printf("mintup %d\n", i);
     280:         if (mintup(mbuf, i, &cmpa))
     281:         {
     282:             if (fwrite(mbuf[i]->tup, 1, Tupsize, Oiop) != Tupsize)
     283:                 syserr("cant write merge output");
     284:             Tupsout++;
     285:         }
     286:         merg = mbuf[i];
     287:         if (rline(merg))
     288:         {
     289:             yesno = "not ";
     290:             if (!(Trace & 010))
     291:             {
     292:                 /* truncate temporary files to zero length */
     293:                 yesno = "";
     294:                 close(creat(setfil(merg->file_num), 0600));
     295:             }
     296:             if (Trace & 02 || Trace & 010)
     297:                 printf("dropping and %struncating %s\n", yesno, setfil(merg->file_num));
     298:             i--;
     299:         }
     300:     }
     301:
     302:     fclose(Oiop);
     303: }
     304:
     305:
     306: mintup(mbuf, cnt, cmpfunc)
     307: struct merg *mbuf[];
     308: int     cnt;
     309: int     (*cmpfunc)();
     310:
     311: /*
     312: **	Mintup puts the smallest tuple in mbuf[cnt-1].
     313: **	If the tuple is a duplicate of another then
     314: **	mintup returns 0, else 1.
     315: **
     316: **	Cnt is the number of compares to make; i.e.
     317: **	mbuf[cnt] is the last element.
     318: */
     319:
     320: {
     321:     register struct merg    **next, **last;
     322:     struct merg     *temp;
     323:     register int        nodup;
     324:     int         j;
     325:
     326:     nodup = TRUE;
     327:     next = mbuf;
     328:     last = &next[cnt];
     329:
     330:     while (cnt--)
     331:     {
     332:         if (j = (*cmpfunc)(last, next))
     333:         {
     334:             /* tuples not equal. keep smallest */
     335:             if (j < 0)
     336:             {
     337:                 /* exchange */
     338:                 temp = *last;
     339:                 *last = *next;
     340:                 *next = temp;
     341:                 nodup = TRUE;
     342:             }
     343:         }
     344:         else
     345:             nodup = FALSE;
     346:
     347:         next++;
     348:     }
     349:     return (nodup);
     350: }
     351:
     352:
     353: rline(mp)
     354: struct merg *mp;
     355: {
     356:     register struct merg    *merg;
     357:     register int        i;
     358:
     359:     merg = mp;
     360:     if ((i = fread(merg->tup, 1, Tupsize, merg->fiop)) != Tupsize)
     361:     {
     362:         if (i == 0)
     363:         {
     364:             fclose(merg->fiop);
     365:             return (1);
     366:         }
     367:         syserr("rd err %d on %s", i, setfil(merg->file_num));
     368:     }
     369:     return (0);
     370: }
     371:
     372: newfile()
     373: {
     374:     char    *setfil();
     375:
     376:     makfile(setfil(Nfiles));
     377:     Nfiles++;
     378: }
     379:
     380: char *setfil(i)
     381: int i;
     382:
     383: /*
     384: **	Convert the number i to a char
     385: **	sequence aa, ab, ..., az, ba, etc.
     386: */
     387:
     388: {
     389:     register int    j;
     390:
     391:     j = i;
     392:     j--;
     393:     Filep[0] = j/26 + 'a';
     394:     Filep[1] = j%26 + 'a';
     395:     return (File);
     396: }
     397:
     398: oldfile()
     399: {
     400:     makfile(Outfile);
     401:     Tupsout = 0;
     402: }
     403:
     404: makfile(name)
     405: char    *name;
     406:
     407: /*
     408: **	Create a file by the name "name"
     409: **	and place its fio pointer in Oiop
     410: */
     411:
     412: {
     413:     if ((Oiop = fopen(name, "w")) == NULL)
     414:         cant(name);
     415: }
     416:
     417: cant(f)
     418: char    *f;
     419: {
     420:     syserr("open %s", f);
     421: }
     422:
     423: term(error)
     424: int error;
     425: {
     426:     register int    i;
     427:
     428:     if (Nfiles == 1)
     429:         Nfiles++;
     430:     if (Trace & 020)
     431:         printf("temp files not removed\n");
     432:     else
     433:         for (i = 1; i < Nfiles; i++)
     434:         {
     435:             unlink(setfil(i));
     436:         }
     437:     exit(error);
     438: }
     439:
     440: cmpa(a, b)
     441: char    **a;
     442: char    **b;
     443: {
     444:     int         af[4];
     445:     int         bf[4];
     446:     char            *pa, *pb;
     447:     register char       *tupa, *tupb;
     448:     int         dom;
     449:     register int        frml;
     450:     int         frmt;
     451:     int         off;
     452:     int         temp;
     453:     int         rt;
     454:     char            *dp;
     455:
     456:     pa = *a;
     457:     pb = *b;
     458:     Ccount++;
     459:     dp = Descsort;
     460:     while ((temp = *dp++) != ENDKEY)
     461:     {
     462:         if ((dom = temp) < 0)
     463:             dom = -temp;
     464:         frml = Desc.relfrml[dom];
     465:         frmt = Desc.relfrmt[dom];
     466:         off = Desc.reloff[dom];
     467:         tupa = &pa[off];
     468:         tupb = &pb[off];
     469:         if (temp < 0)
     470:         {
     471:             tupb = tupa;
     472:             tupa = &pb[off];
     473:         }
     474:         if (frmt == CHAR)
     475:         {
     476:             frml &= 0377;
     477:             if (rt = scompare(tupb, frml, tupa, frml))
     478:                 return (rt);
     479:             continue;
     480:         }
     481:
     482:         /* domain is a numeric type */
     483:         if (bequal(tupa, tupb, frml))
     484:             continue;
     485:         /* copy to even word boundary */
     486:         bmove(tupa, af, frml);
     487:         bmove(tupb, bf, frml);
     488:         tupa = (char *) &af[0];
     489:         tupb = (char *) &bf[0];
     490:
     491:         switch (frmt)
     492:         {
     493:
     494:           case INT:
     495:             switch (frml)
     496:             {
     497:
     498:               case 1:
     499:                 return (i1deref(tupa) > i1deref(tupb) ? -1 : 1);
     500:
     501:               case 2:
     502:                 return (i2deref(tupa) > i2deref(tupb) ? -1 : 1);
     503:
     504:               case 4:
     505:                 return (i4deref(tupa) > i4deref(tupb) ? -1 : 1);
     506:             }
     507:
     508:           case FLOAT:
     509:             switch (frml)
     510:             {
     511:
     512:               case 4:
     513:                 return (f4deref(tupa) > f4deref(tupb) ? -1 : 1);
     514:
     515:               case 8:
     516:                 return (f8deref(tupa) > f8deref(tupb) ? -1 : 1);
     517:             }
     518:         }
     519:     }
     520:     return (0);
     521: }
     522:
     523:
     524:
     525: /*
     526: **	Replacement for access method routine get_page();
     527: **	and associated globals and routines.
     528: */
     529:
     530: struct accbuf   *Acc_head, Accbuf;
     531: long        Accuread, Accuwrite;
     532:
     533: get_page(d1, tid)
     534: struct descriptor   *d1;
     535: struct tup_id       *tid;
     536: {
     537:     register int            i;
     538:     register struct descriptor  *d;
     539:     long                pageid;
     540:     register struct accbuf      *b;
     541:
     542:     d = d1;
     543:     if (Trace & 0100)
     544:     {
     545:         printf("get_page: %.14s,", d->relid);
     546:         dumptid(tid);
     547:     }
     548:     b = Acc_head;
     549:     if (b == 0)
     550:     {
     551:         /* initialize buffer */
     552:         Acc_head = &Accbuf;
     553:         b = &Accbuf;
     554:         b->thispage = -1;
     555:     }
     556:     pluck_page(tid, &pageid);
     557:     i = 0;
     558:     if (b->thispage != pageid)
     559:     {
     560:         if (Trace & 040)
     561:             printf("get_page: rdg pg %s\n", locv(pageid));
     562:         b->thispage = pageid;
     563:         if ((lseek(d->relfp, pageid * PGSIZE, 0) < 0) ||
     564:             ((read(d->relfp, b, PGSIZE)) != PGSIZE))
     565:         {
     566:             i = AMREAD_ERR;
     567:         }
     568:         Accuread++;
     569:     }
     570:     return (i);
     571: }
     572:
     573: resetacc(buf)
     574: struct accbuf   *buf;
     575: {
     576:     return (0);
     577: }
     578:
     579: acc_err(err)
     580: int err;
     581: {
     582:     return (err);
     583: }

#### Defined functions

acc_err defined in line 579; never used
cant defined in line 417; used 4 times

- in line 64, 182, 267, 414

cmpa defined in line 440; used 4 times

- in line 43, 218, 227, 280

get_page defined in line 533; used 1 times

- in /usr/ingres/source/dbu/modify.c line 666

main defined in line 46; never used
makfile defined in line 404; used 2 times

- in line 376, 400

merge defined in line 247; used 2 times

- in line 149, 156

mintup defined in line 306; used 1 times

- in line 280

newfile defined in line 372; used 2 times

- in line 148, 220

oldfile defined in line 398; used 2 times

- in line 155, 222

resetacc defined in line 573; used 1 times

- in /usr/ingres/source/dbu/modify.c line 975

rline defined in line 353; used 2 times

- in line 268, 287

setfil defined in line 380; used 8 times

- in line 255, 263, 294-297(2), 367, 374-376(2), 435

sort defined in line 166; used 1 times

- in line 136

term defined in line 423; used 4 times

- in line 42, 59, 130, 163

#### Defined variables

Acc_head defined in line 530; used 2 times

- in line 548-552(2)

Accbuf defined in line 530; used 2 times

- in line 552-553(2)

Accuread defined in line 531; used 1 times

- in line 568

Accuwrite defined in line 531; never used
Bucket defined in line 33; used 4 times

- in line 88, 99-103(2), 208

Ccount defined in line 39; used 5 times

- in line 133, 141-145(2), 161, 458

Desc defined in line 28; used 22 times

- in line 65(3), 74-75(2), 86, 92-94(4), 103, 181-183(3), 199-204(3), 211-212(2), 464-466(3)

Descsort defined in line 29; used 5 times

- in line 81-88(3), 100, 459

File defined in line 34; used 3 times

- in line 124-125(2), 395

Filep defined in line 36; used 6 times

- in line 125-128(4), 393-394(2)

Fileset defined in line 35; used 19 times

- in line 61, 124
- in /usr/ingres/source/dbu/modify.c line 538, 591-594(2), 618, 667, 976-980(2), 1007
- in /usr/ingres/source/dbu/modupdate.c line 39-40(2)
- in /usr/ingres/source/dbu/rdwrbatch.c line 91-92(2)
- in /usr/ingres/source/support/restore.c line 192, 211, 226
- in /usr/ingres/source/support/sysmod.c line 99, 217

Infile defined in line 26; used 3 times

- in line 105, 181-182(2)

Lspace defined in line 40; used 10 times

- in line 110, 118-121(2), 196-197(2), 218-227(4), 259

Nfiles defined in line 37; used 11 times

- in line 140, 146, 153-156(2), 219, 230, 376-377(2), 428-433(3)

Nlines defined in line 38; used 4 times

- in line 117-121(3), 197

Outfile defined in line 27; used 2 times

- in line 106, 400

Trace defined in line 31; used 16 times

- in line 62, 97, 119, 134-138(2), 158, 236, 257, 274-278(2), 290, 296(2), 430, 543, 560

Tspace defined in line 41; used 3 times

- in line 118-121(2), 195

Tupsize defined in line 32; used 10 times

- in line 86-91(2), 117, 215, 229(2), 282(2), 360(2)

Tupsout defined in line 44; used 6 times

- in line 140, 160, 180, 231, 284, 401

#### Defined struct's

merg defined in line 240; used 16 times

- in line 251-259(6), 307(2), 321-322(4), 354-356(4)

#### Defined macros

BUCKETSIZE defined in line 10; used 4 times

- in line 91-92(2), 212, 242

ENDKEY defined in line 11; used 3 times

- in line 84, 100, 460

MEM defined in line 9; used 1 times

- in line 111

N defined in line 8; used 4 times

- in line 146-149(3), 254

Last modified: 1995-02-12 Generated: 2016-12-26 | Generated by src2html V0.67 page hit count: 1664 |