home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / sort / b-sort / b-sort.c
Encoding:
Text File  |  1985-10-10  |  16.4 KB  |  474 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 sort 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 sort utility. It is relatively fast though   */
  17. /* and I would be interested in any comparisons anyone makes. 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 an introduction to B-trees here.    */
  25. /* My primary reference and, in fact, the source of this program is  */
  26. /* 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    */
  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 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. /*     1983/10/14 09:45                                                 */
  89. /*     Adapted for IBM PC and Aztec C II Compiler by                    */
  90. /*           William Hutchison, President                               */
  91. /*           Algorithmic Technology, Inc.                               */
  92. /*           P.O. Box 278                                               */
  93. /*           Exton, PA 19341-0278                                       */
  94. /*           CompuServe [70665,1307]                                    */
  95. /*                                                                      */
  96. /*     Send an SASE if you would like a copy of our software catalog    */
  97. /*                                                                      */
  98.  
  99. #include <algodef.h>
  100. #ifdef MS_DOS
  101. #define FCREAT(x,y) fopen(x,y)
  102. VOID
  103. pause()
  104. {
  105. int x;
  106.  
  107. x= getchar();
  108. }                                      /* end pause */
  109. #endif
  110.  
  111. #define N 2 /* half-size of b-tree node */
  112.  
  113. /* options for customizing the program */
  114.  
  115. #undef FAST      /* uses external 'move' functions for assemlber vs */
  116. #undef SPRINT     /* provides statistics on keys in output */
  117. #define KEYPTR    /* uses pointer references to strings instead of */
  118.                   /* arrays in the b-tree nodes */
  119. #undef DIAGNOSE   /* turns on voluminous trace information on actions */
  120.                   /* taken by program logic.. perhaps instructive */
  121. /* special assigned values */
  122.  
  123. #define KEYSIZE 80
  124. #define MAX_LEN 20
  125. #define MAXPRINT 3000
  126.  
  127. /* dependent parameters */
  128.  
  129. #define NN N+N
  130. #define NM1 N-1
  131. #define NM2 N-2
  132. #define NP1 N+1
  133.  
  134. /* structure definitions */
  135.  
  136. #define ITEM struct sitem
  137. #define PAGE struct spage
  138.  
  139. ITEM  {
  140. #ifndef KEYPTR
  141.         char KEY[KEYSIZE];
  142. #endif 
  143. #ifdef KEYPTR
  144.         char *KEY;
  145. #endif 
  146.         PAGE *P;
  147.         unsigned COUNT;
  148. } 
  149. oneitem;
  150.  
  151. PAGE  {
  152.         unsigned M;
  153.         PAGE *P0;
  154.         ITEM E[NN];
  155. } 
  156. onepage;
  157.  
  158. /* external variables */
  159.  
  160. PAGE *root,*q;
  161. ITEM g;
  162.  
  163. FILE *infile, *outfile;
  164. char infilnam[MAX_LEN], instrg[MAXLINE], o_flg;
  165.  
  166. int sizitem,sizpage, maxcount, nkeys, tokcount;
  167.  
  168. /* beginning of programs */
  169.  
  170. use_err() /* Usage message: */
  171. {
  172.         fprintf(STDERR,"\nERROR: Invalid parameter specification\n\n");
  173.         fprintf(STDERR,"Usage: b-sort <filename> <flag(s)>\n\n");
  174.         fprintf(STDERR," -o <filename> = Write output to named file\n");
  175.         exit(0); 
  176. }
  177.  
  178. main(argc,argv)
  179. int argc;
  180. char **argv;
  181. {
  182.  
  183.         char *arg;
  184.  
  185.         o_flg=NO; /* output file flag */
  186.  
  187.         if (argc < 2) use_err();
  188.  
  189.         strcpy(infilnam,*++argv);
  190.  
  191.         if ((infile= fopen(infilnam, READ)) == NULL){
  192.                 fprintf(STDERR,"\nERROR: Unable to open input file: %s\n",infilnam);
  193.                 exit(1); 
  194.         }
  195.  
  196.         if (--argc > 0)
  197.                 if (*(arg=*++argv) == '-')
  198.                         if (tolower(*++arg) == 'o'){
  199.                                 o_flg++;
  200.                                 if (--argc == 0){
  201.                                         fprintf(STDERR,"\nneed output file name");
  202.                                         use_err();
  203.                                 }
  204.                                 if ((outfile= FCREAT(*++argv, WRITE)) == NULL){
  205.                                         fprintf(STDERR,"ERROR: Unable to create output file - %s\n",
  206.                                         *argv); 
  207.                                         exit(0);
  208.                                 }
  209.                         }
  210.  
  211.         root=NULL; 
  212.         sizitem=sizeof(oneitem); 
  213.         sizpage=sizeof(onepage);
  214.         tokcount=nkeys=0;
  215.  
  216. #ifdef DIAGNOSE
  217.         fprintf(STDERR,"\n&root=%x,g=%x,sizi=%d,sizp=%d",&root,g,sizitem,sizpage);
  218. #endif 
  219.  
  220.         while (fgets(instrg, MAXLINE, infile)){
  221.  
  222.                 if (trim(instrg) <= 0 ) continue;
  223.  
  224.                 instrg[KEYSIZE-1]='\0';
  225.  
  226. #ifdef DIAGNOSE
  227.                 fprintf(STDERR,"\n\nsearch key= %s",instrg);
  228. #endif 
  229.                 if (search(instrg,root,&g) ){
  230.                         q=root; 
  231.                         if ((root=alloc(sizpage)) == NULL){
  232.                                 fprintf(STDERR,"\nERROR unable to allocate page");
  233.                                 exit(2); 
  234.                         }
  235. #ifdef DIAGNOSE
  236.                         fprintf(STDERR," root=%x, q=%x",root,q);
  237. #endif 
  238.  
  239.                         root->M=1; 
  240.                         root->P0=q; 
  241.                         moveb((char *)&root->E[0], (char *)&g, sizitem);
  242.  
  243.                 }
  244.         }
  245.  
  246. #ifdef DIAGNOSE
  247.         fprintf(STDERR,"\nEnd of input\n");
  248.  
  249.         fprintf(STDERR,"\nnumber of unique keys=%d, total key count=%d\n",
  250.         nkeys,tokcount);
  251.         if (!o_flg) pause();
  252. #endif
  253.  
  254.         maxcount=MAXPRINT; 
  255.         printtree(root,1);
  256.  
  257.         fprintf(STDERR,"\n");
  258.         if (o_flg){
  259.  
  260.                 fflush(outfile); 
  261.                 fclose(outfile); 
  262.         }
  263. }
  264. char search(x,a,v)
  265. char *x;
  266. PAGE *a;
  267. ITEM *v;
  268. {
  269.  
  270.         int i,k,l,r,cmp; 
  271.         PAGE *q,*b; 
  272.         ITEM u; 
  273.         char *t;
  274.  
  275.         /* Search for key x on page a */
  276.  
  277.         if (a==NULL) /* ITEM with key x is not in tree */ {
  278.  
  279.                 ++tokcount; 
  280.                 ++nkeys; 
  281.                 defkey(&v->KEY,x);
  282.  
  283. #ifdef DIAGNOSE
  284.                 fprintf(STDERR,"\n a == null v(=%x)->KEY=%s",v,v->KEY);
  285. #endif 
  286.  
  287.                 v->COUNT=1;
  288.                 v->P=NULL; 
  289.                 return (YES) ; /* YES means not found */
  290.         }
  291.         else {
  292.                 l=0; 
  293.                 r=a->M-1; /* binary array search */
  294.                 do  {
  295.                         k=(l+r)/2;
  296.                         cmp= strcmp(x,t=(a->E[k].KEY));
  297.  
  298. #ifdef DIAGNOSE
  299.                         fprintf(STDERR,"\ncmp=%d,r=%d,l=%d,a(=%x)->P0=%x/E[k=%d].P=%x/E[k].KEY=%x=%s",
  300.                         cmp,r,l,a,a->P0,k,a->E[k].P,t,t );
  301. #endif 
  302.  
  303.                         if (cmp <= 0) r=k-1;
  304.                         if (cmp >= 0) l=k+1;
  305.  
  306.                 } 
  307.                 while (r >= l );
  308.  
  309.                 if (cmp == 0 ) /* found it, bump counter */ {
  310.                         ++tokcount; 
  311.                         ++a->E[k].COUNT; 
  312.                         return(NO); 
  313.                 }
  314.  
  315.                 else /* test if item is not on this page */ {
  316.  
  317.                         q = (r < 0 ) ? a->P0 : a->E[r].P;
  318.  
  319.                         if (!search(x,q,&u) ) return(NO);
  320.                 }
  321.         }
  322.  
  323.         /* ---- insert an item */
  324.  
  325.         if (a->M < NN){
  326.                 /* page not full yet, add to it. 'Bump' items from r+1 to
  327.                 M-1 */
  328.                 movdnb((char *)&a->E[r+2], (char *)&a->E[r+1],
  329.                         sizitem*((a->M++)-r-1) );
  330.                 moveb((char *)&a->E[r+1], (char *)&u, sizitem);
  331.  
  332.                 return(NO);
  333.         }
  334.         else {
  335.                 /* page full, split it and push center item upward in tree */
  336.                 if ((b = alloc(sizpage)) == NULL )
  337.                         fprintf(STDERR,"\nOut of memory");
  338.  
  339. #ifdef DIAGNOSE
  340.                 fprintf(STDERR,"\n\n ****** new node at %x",b);
  341. #endif 
  342.  
  343.                 if (r <= NM1 ) /* put new item in old page */ {
  344.  
  345.                         if (r == NM1 ) moveb((char *)v, (char *)&u, sizitem );
  346.                         else {
  347.                                 /* 'bump' down items from r+2 to N-1 */
  348.  
  349.                                 moveb((char *)v, (char *)&a->E[NM1], sizitem);
  350.                                 movdnb((char *)&a->E[r+2], (char *)&a->E[r+1],
  351.                                  sizitem*(NM2-r));
  352.                                 moveb((char *)&a->E[r+1], (char *)&u,sizitem);
  353.                         }
  354.                         moveb((char *)&b->E[0], (char *)&a->E[N], sizitem*N);
  355.                 }
  356.                 else {
  357.                         /* move upper N items and new item to new page */
  358.  
  359.                         moveb((char *)v, (char *)&a->E[N], sizitem ) ;
  360.  
  361.                         if ((r = r - N) > 0 ) 
  362.                                 moveb((char *)&b->E[0],
  363.                                       (char *)&a->E[NP1], sizitem*r);
  364.  
  365.                         moveb((char *)&b->E[r], (char *)&u, sizitem);
  366.  
  367.                         if ((i = NM1-r) > 0 )
  368.                                 moveb((char *)&b->E[r+1],
  369.                                       (char *)&a->E[NP1+r], sizitem * i);
  370.                 }
  371.  
  372.                 a->M = b->M = N ; 
  373.                 b->P0 = v->P; 
  374.                 v->P = b ;
  375.         }
  376.  
  377.         return (YES);
  378. }
  379. trim(strg)
  380. char *strg;
  381. {
  382.  
  383.         int l;
  384.  
  385.         l=strlen(strg);
  386.         while (strg[l] <= ' ' ){
  387.                 if (l <= 0 ) break; 
  388.                 strg[l--]='\0'; 
  389.         }
  390.         return(l);
  391. }
  392. moveb(a,b,c)
  393. char *a,*b;
  394. int c;
  395. {
  396.  
  397.         int i;
  398. #ifdef FAST /* use potentially faster move routine */
  399.         move(a,b,c); 
  400.         return;
  401. #else 
  402. /*      for (i=0 ; i < c ; ++i ) a[i]=b[i] ;     */
  403.         while (c-- > 0)
  404.             *a++= *b++;
  405. #endif 
  406. }
  407. movdnb(a,b,c)
  408. char *a,*b;
  409. int c;
  410. {
  411.  
  412.         int i;
  413. #ifdef FAST /* use potentially faster move routine */
  414.         movdn(a,b,c); 
  415.         return;
  416. #else 
  417. /*      for (; --c >= 0 ; c ) a[c]=b[c] ;        */
  418.         for (a+= c, b+= c; c-- > 0; )
  419.             *--a= *--b;
  420. #endif 
  421. }
  422.  
  423. printtree(p,l)
  424. PAGE *p;
  425. int l;
  426. {
  427.  
  428.         int i,j; 
  429.         char *t;
  430.  
  431.         if (maxcount <= 0) return;
  432.  
  433.         if (p != NULL ){
  434.  
  435.  
  436.                 printtree(p->P0, l+1 );
  437.  
  438.                 for (i=0; i <= (j=p->M-1) ; ++i ){
  439.                         --maxcount;
  440.                         fprintf(STDERR,"\n");
  441. #ifdef SPRINT
  442.                         fprintf(STDERR," %d %d ",l,p->E[i].COUNT );
  443. #endif 
  444.                         prints(p->E[i].KEY);
  445.  
  446.                         printtree(p->E[i].P,l+1); 
  447.                 }
  448.         }
  449. }
  450. defkey(a,b)
  451. char **a,*b;
  452. {
  453.  
  454. #ifdef KEYPTR
  455.         if ((*a=alloc(strlen(b)+1)) == NULL ){
  456.                 fprintf(STDERR,"\ninsufficient string storage in defkey\n");
  457.                 exit(3);
  458.         }
  459.         strcpy(*a,b);
  460. #endif 
  461. #ifndef KEYPTR
  462.         strcpy(a,b);
  463. #endif 
  464. }
  465. prints(str)
  466. char *str;
  467. {
  468.  
  469.         if (o_flg)
  470.                fputs(str,outfile);
  471.         else
  472.                fputs(str,STDOUT); /* and print out the line */
  473. }
  474.