home *** CD-ROM | disk | FTP | other *** search
/ ftp.barnyard.co.uk / 2015.02.ftp.barnyard.co.uk.tar / ftp.barnyard.co.uk / cpm / walnut-creek-CDROM / CPM / PROGRAMS / SORT / B-SORT.ARK / B-SORT.C next >
C/C++ Source or Header  |  1983-09-09  |  12KB  |  433 lines
  1. /*
  2.     B-SORT        a sorting program
  3.  
  4.     This is a self-contained file except for the standard included
  5.     definitions and is part of the  larger development of a message-
  6.     retrieval system. Since the algorithms involved are well known
  7.     it is felt that putting this program in public domain would serve
  8.     a useful purpose, namely provide some examples of some programming
  9.     techniques using the 'C' language. The compiler used is the BDS
  10.     vs 1.46 and use is made of at least one special feature of this
  11.     compiler(see 'printf' function).
  12.  
  13.     Nominally this is a sorting program and can certainly be used for
  14.     that purpose. However, since the main benefit of using a B-tree is
  15.     when using disk-based structures, it is quite possible that this
  16.     will not be your hot-dog sort utility. It is relatively fast though
  17.     and I would be interested in any comparisons anyone makes. A later
  18.     effort is planned to build a virtual memory support package which
  19.     will then allow the 'nodes' of the b-tree to be stored as disk
  20.     sectors and at that point this program will allow sorting of
  21.     arbitrarily large text files. Again, that is still not the main
  22.     objective for it, information retrieval is.
  23.  
  24.     I will not attempt to give even an introduction to B-trees here. My
  25.     primary reference and, in fact, the bareface source of this program
  26.     is N. Wirth's wonderful book "Algorithms+Data Structures=Programs".
  27.     I passed this book up several times in the past, but when I was 
  28.     looking for a treatment of this subject, I found that it had a very
  29.     nice balance between explanation and example(the best way I learn)
  30.     and since 'C' and PASCAL are 'kissin cousins', it was 'straight
  31.     forward' to do the transcribing. So go to god and read section
  32.     4.51 if you want to understand what is going on here. Also you can
  33.     get a little contrast of the styles which result from the different
  34.     features of the two languages(especially w re pointer variables).
  35.  
  36.     Things to note in this program which you may not already be
  37.     familiar with are the following:
  38.  
  39.         1) A nested data structure(PAGE) is used. This is possible
  40.            in PASCAL and PL/I too and makes life a lot more pleasant.
  41.            Try doing the same thing in BASIC or FORTRAN, what a
  42.            mess! In a sense it would be easier in assembler.
  43.  
  44.         2) Note that the tree structure used is a balanced one
  45.            so that no single branch gets long at the expense of
  46.            others. To see the depth level of the tree, turn on
  47.            the SPRINT parameter and note the first column of the
  48.            output on any sort. There is a trade-off here, though
  49.            in that it takes longer to build the tree than if it
  50.            were just a binary tree(not an AVL though). Thats why
  51.            b-trees are best for retrieval rather than simple
  52.            sorts.
  53.  
  54.         3) The logic uses a rather interesting recursive structure
  55.            in which 'emerging' items are handed back through higher
  56.            levels until perhaps to the root of the tree. See the
  57.            variable called 'u' in function 'search'.
  58.  
  59.         4) The parameter KEYPTR allows the option of including the
  60.            string storage area in the nodes themselves as opposed
  61.            to allocated areas. The latter is faster since no move-
  62.            ment of strings is necessary after they have been given
  63.            initial allocations. However, for disk-based use the
  64.            strings(keys) would need to be in the nodes. To see the
  65.            difference in performance(big!) just undefine(comment
  66.            out) this parameter.
  67.  
  68.         5) For further perfomance comparison play with the FAST
  69.            parameter. If undefined, the compiler will build a
  70.            version of B-sort with a high-level version of two
  71.            block move operations. These same functions are imple-
  72.            mented in assembler code in the file BDSNEW.CSM. By
  73.            linking with that special library, you can get a version
  74.            of this program which runs quite a bit faster. Let me
  75.            know if you get any amazing results.
  76.  
  77.         6) One peculiarity of the 'C' language came up in an earlier
  78.            version of B-sort, it would not sort itself! Clue, this
  79.            had to do with the way that 'printf' works. See if you
  80.            can figure out how this happened and how it was fixed.
  81.  
  82.     I hope this program is useful for some in learning more about the
  83.     'C' language and an interesting algorithm(the key to better software).
  84.     If you make any improvements give me a copy. If you mutilate it, keep
  85.     it to yourself.
  86.                 Jack Riley (303) 499-9169 RCPM, Boulder, CO.
  87. */
  88.  
  89. #include "bdscio1.h"    /* version with ALLOC_ON true */
  90.  
  91. #DEFINE N        2  /* half-size of b-tree node */
  92.  
  93. /* options for customizing the program */
  94.  
  95. #DEFINE FAST        /* uses external 'move' functions for assemlber vs */
  96. /* #DEFINE SPRINT */        /* provides statistics on keys in output */
  97. #DEFINE KEYPTR        /* uses pointer references to strings instead of
  98.                arrays in the b-tree nodes */
  99. /* #DEFINE DIAGNOSE */    /* turns on voluminous trace information on actions
  100.                taken by program logic.. perhaps instructive */
  101. /* special assigned values */
  102.  
  103. #DEFINE KEYSIZE        80
  104. #DEFINE MAX_LEN        20
  105. #DEFINE MAXPRINT    3000
  106.  
  107. /* dependent parameters */
  108.  
  109. #DEFINE NN        N+N
  110. #DEFINE NM1        N-1
  111. #DEFINE NM2        N-2
  112. #DEFINE    NP1        N+1
  113.  
  114. /* structure definitions */
  115.  
  116. #DEFINE ITEM         struct sitem
  117. #DEFINE PAGE         struct spage
  118.  
  119. ITEM {
  120. #ifndef KEYPTR
  121.     CHAR KEY[KEYSIZE];
  122. #endif
  123. #ifdef KEYPTR
  124.     CHAR *KEY;
  125. #endif
  126.     PAGE *P;
  127.     UNSIGNED COUNT;
  128.     } oneitem;
  129.  
  130. PAGE {
  131.     UNSIGNED M;
  132.     PAGE *P0;
  133.     ITEM E[NN];
  134.     } onepage;
  135.  
  136. /* external variables */
  137.  
  138. PAGE *root,*q;
  139. ITEM g;
  140. FILE infile,l_buffer;
  141. CHAR infilnam[MAX_LEN], instrg[MAXLINE], o_flg;
  142. INT sizitem,sizpage, maxcount, nkeys, tokcount;
  143.  
  144. /* beginning of programs */
  145.  
  146. use_err() /* Usage message: */
  147.  
  148.        { printfc("\nERROR: Invalid parameter specification\n\n");
  149.        printfc("Usage: b-sort <filename> <flag(s)>\n\n");
  150.        printfc("       -o <filename> = Write output to named file\n");
  151.        exit(0); }
  152.  
  153. main(argc,argv)
  154. int argc;
  155. char **argv;
  156. {
  157.     char *arg;
  158.  
  159.     o_flg=FALSE;        /* output file flag */
  160.  
  161.     if (argc < 2) use_err();
  162.  
  163.     strcpy(infilnam,*++argv);
  164.  
  165.     if( fopen(infilnam,infile) == ERROR )
  166.         { printfc("\nERROR: Unable to open input file: %s\n",infilnam);
  167.           EXIT(0); }
  168.  
  169.     if(--argc > 0)
  170.        if(*(arg=*++argv) == '-')
  171.         if(tolower(*++arg) == 'o')
  172.             { o_flg++;
  173.             if(--argc == 0)
  174.                 {printfc("\nneed output file name");use_err();}
  175.             if(fcreat(*++argv,l_buffer) == ERROR)
  176.              {printfc("ERROR: Unable to create output file - %s\n",
  177.                         *argv); exit(0);}
  178.             }
  179.  
  180.     _allocp=NULL;
  181.     root=NULL; sizitem=sizeof(oneitem); sizpage=sizeof(onepage);
  182.     tokcount=nkeys=0;
  183.  
  184. #ifdef DIAGNOSE
  185.     printf("\n&root=%x,g=%x,sizi=%d,sizp=%d",&root,g,sizitem,sizpage);
  186. #endif
  187.  
  188.     while( fgets(instrg,infile) )
  189.         {
  190.         if( trim(instrg) <= 0 ) continue;
  191.  
  192.         instrg[KEYSIZE-1]='\0';
  193.  
  194. #ifdef DIAGNOSE
  195.         printf("\n\nsearch key= %s",instrg);
  196. #endif
  197.         if( search(instrg,root,g) )
  198.             { q=root; 
  199.              if( (root=alloc(sizpage)) == NULL)
  200.                 { printfc("\nERROR unable to allocate page");
  201.                   EXIT(0); }
  202. #ifdef DIAGNOSE
  203. printf("  root=%x, q=%x",root,q);
  204. #endif
  205.  
  206.             root->M=1; root->P0=q; moveb(root->E[0] , g ,sizitem);
  207.  
  208.             }
  209.         }
  210.  
  211.     printfc("\nEnd of input\n");
  212.  
  213.     printfc("\nnumber of unique keys=%d, total key count=%d\n",
  214.                     nkeys,tokcount);
  215.     if(!o_flg) pause();
  216.  
  217.     maxcount=MAXPRINT; printtree(root,1);
  218.  
  219.     printf("\n");
  220.     if(o_flg)
  221.         { putc(CPMEOF,l_buffer); fflush(l_buffer); fclose(l_buffer); }
  222. }
  223. CHAR search(x,a,v)
  224. CHAR *x;
  225. PAGE *a;
  226. ITEM *v;
  227. {
  228.     INT i,k,l,r,cmp; PAGE *q,*b; ITEM u; CHAR *t;
  229.  
  230. /*    Search for key x on page a */
  231.  
  232.     if(a==NULL)         /* ITEM with key x is not in tree */
  233.         { 
  234.         ++tokcount; ++nkeys; defkey(&v->KEY,x);
  235.  
  236. #ifdef DIAGNOSE
  237. printf("\n             a ==  null v(=%x)->KEY=%s",v,v->KEY);
  238. #endif
  239.  
  240.         v->COUNT=1;
  241.         v->P=NULL;  return (TRUE) ; /* TRUE means not found */
  242.         }
  243.     else
  244.         { l=0; r=a->M-1;  /* binary array search */
  245.         do {
  246.             k=(l+r)/2;
  247.             cmp= strcmp(x,t=(a->E[k].KEY));
  248.  
  249. #ifdef DIAGNOSE
  250. printf("\ncmp=%d,r=%d,l=%d,a(=%x)->P0=%x/E[k=%d].P=%x/E[k].KEY=%x=%s",
  251.             cmp,r,l,a,a->P0,k,a->E[k].P,t,t );
  252. #endif
  253.  
  254.             if( cmp <= 0) r=k-1;
  255.             if( cmp >= 0) l=k+1;
  256.  
  257.            } while ( r >= l );
  258.  
  259.         if( cmp == 0 ) /* found it, bump counter */
  260.             { ++tokcount; ++a->E[k].COUNT;  return(FALSE); }
  261.  
  262.         else    /* test if item is not on this page   */
  263.             {
  264.             q = ( r < 0 ) ? a->P0 : a->E[r].P;
  265.  
  266.             if( !search(x,q,u) ) return(FALSE);
  267.             }
  268.         }
  269.  
  270. /* ---- insert an item */
  271.  
  272.     if (a->M < NN)
  273.         { /* page not full yet, add to it. 'Bump' items from r+1 to
  274.                             M-1 */
  275.         movdnb( a->E[r+2] , a->E[r+1] , sizitem*((a->M++)-r-1) );
  276.         moveb( a->E[r+1] , u , sizitem );
  277.  
  278.         return(FALSE);
  279.         }
  280.     else
  281.         { /* page full, split it and push center item upward in tree */
  282.         if( (b = alloc(sizpage)) == NULL )
  283.             printf("\nOut of memory");
  284.  
  285. #ifdef DIAGNOSE
  286. printf("\n\n ******  new node at %x",b);
  287. #endif
  288.  
  289.         if ( r <= NM1 ) /* put new item in old page */
  290.             {
  291.             if ( r == NM1 )  moveb( v , u , sizitem );
  292.             else
  293.                 { /* 'bump' down items from r+2 to N-1 */
  294.  
  295.                 moveb( v , a->E[NM1] , sizitem );
  296.                 movdnb( a->E[r+2] , a->E[r+1] ,
  297.                             sizitem*(NM2-r) );
  298.                 moveb( a->E[r+1] , u , sizitem );
  299.                 }
  300.             moveb( b->E[0] , a->E[N] , sizitem*N );
  301.             }
  302.         else
  303.             {/* move upper N items and new item to new page */
  304.  
  305.             moveb( v , a->E[N] , sizitem ) ;
  306.  
  307.             if( (r = r - N) > 0 )    
  308.                 moveb( b->E[0] , a->E[NP1] , sizitem*r );
  309.  
  310.             moveb( b->E[r] , u , sizitem );
  311.  
  312.             if( (i = NM1-r) > 0 )
  313.                 moveb( b->E[r+1], a->E[NP1+r], sizitem * i );
  314.             }
  315.  
  316.         a->M = b->M = N ; b->P0 = v->P; v->P = b ;
  317.         }
  318.  
  319.     return (TRUE);
  320. }
  321. trim(strg)
  322. char *strg;
  323. {
  324.     INT l;
  325.  
  326.     l=strlen(strg);
  327.     while ( strg[l] <= ' ' )
  328.         { if( l <= 0 ) break;  strg[l--]='\0'; }
  329.     return(l);
  330. }
  331. moveb(a,b,c)
  332. char *a,*b;
  333. int c;
  334. {
  335.     int i;
  336. #ifdef FAST        /* use potentially faster move routine */
  337.     move(a,b,c); return;
  338. #endif
  339. #ifndef FAST
  340.     for ( i=0 ; i < c ; ++i ) a[i]=b[i] ;
  341. #endif
  342. }
  343. movdnb(a,b,c)
  344. char *a,*b;
  345. int c;
  346. {
  347.     int i;
  348. #ifdef FAST        /* use potentially faster move routine */
  349.     movdn(a,b,c); return;
  350. #endif
  351. #ifndef FAST
  352.     for ( ; --c >= 0 ; c ) a[c]=b[c] ;
  353. #endif
  354. }
  355. printtree(p,l)
  356. PAGE *p;
  357. INT l;
  358. {
  359.     INT i,j;  CHAR *t;
  360.  
  361.     if(maxcount <= 0) return;
  362.  
  363.     if ( p != NULL )
  364.         {
  365.  
  366.         printtree(p->P0, l+1 );
  367.  
  368.         for ( i=0; i <= (j=p->M-1) ; ++i )
  369.             { --maxcount;
  370.             printf("\n");
  371. #ifdef SPRINT
  372.             printf(" %d %d ",l,p->E[i].COUNT );
  373. #endif
  374.             prints(p->E[i].KEY);
  375.  
  376.             printtree(p->E[i].P,l+1); 
  377.             }
  378.         }
  379. }
  380. defkey(a,b)
  381. char **a,*b;
  382. {
  383. #ifdef KEYPTR
  384.     if ( (*a=alloc(strlen(b)+1)) == NULL )
  385.         {printfc("\ninsufficient string storage in defkey\n");EXIT(0);}
  386.     strcpy(*a,b);
  387. #endif
  388. #ifndef KEYPTR
  389.     strcpy(a,b);
  390. #endif
  391. }
  392. prints(str)
  393. char *str;
  394. {
  395.     if(o_flg)
  396.         fputs(str,l_buffer);
  397.     else
  398.         puts(str);        /* and print out the line     */
  399. }
  400. /* Note: The following two functions where obtained from the BDS STDLIB2.C
  401.      file and may be quite dependent on this compiler since the 'C'
  402.      language does specify where arguments are to be found.  */
  403.  
  404. printfc(format)
  405. char *format;
  406. {
  407.     char line[MAXLINE];
  408.     _spr(line,&format);    /* use "_spr" to form the output */
  409.  
  410.     puts(line);        /* and print out the line     */
  411. }
  412. printf(format)
  413. char *format;
  414. {
  415.     char line[MAXLINE];
  416.     _spr(line,&format);    /* use "_spr" to form the output */
  417.  
  418.     prints(line);
  419. }
  420. fputs(s,iobuf)
  421. char *s;
  422. struct _buf *iobuf;
  423. {
  424.     char c;
  425.     while (c = *s++) {
  426.         if (c == '\r' || c == '\0') return;
  427.  
  428.         if (c == '\n') putc('\r',iobuf);
  429.         if (putc(c,iobuf) == ERROR) return ERROR;
  430.     }
  431.     return OK;
  432. }