home *** CD-ROM | disk | FTP | other *** search
/ World of Shareware - Software Farm 2 / wosw_2.zip / wosw_2 / CPROG / TDE31.ZIP / SORT.C < prev    next >
C/C++ Source or Header  |  1993-08-29  |  25KB  |  728 lines
  1. /*
  2.  * These functions sort lines according to keys in a marked BOX block.
  3.  *
  4.  * Being that the data structure was changed from a big text buffer to a
  5.  * linked list, we can replace the simple insertion sort algorithm with a
  6.  * much faster sort algorithm.  The classic search and sort reference is by
  7.  * Donald E. Knuth, _The Art of Computer Programming; Volume 3:  Sorting and
  8.  * Searching_.  One of the fastest and most widely used general purpose
  9.  * sorting algorithms is the "Quicksort" algorithm.
  10.  *
  11.  * For implementation hints and guidelines on the Quicksort algorithm, one
  12.  * might read the original Quicksort paper by C. A. R. Hoare or anything
  13.  * by Robert Sedgewick.  Although Dr. Sedgewick includes a chapter on
  14.  * Quicksort in his intro computer science textbooks, _Algorithms in X_,
  15.  * I prefer the detailed hints and guidelines in his 1978 CACM paper.
  16.  * Incidentally, Dr. Sedgewick's Ph.D. dissertation was on the modification
  17.  * and mathematical analysis of the Quicksort algorithm.
  18.  *
  19.  *
  20.  * See:
  21.  *
  22.  *   Charles Antony Richard Hoare, "Algorithm 63: Partition."  _Communications
  23.  *      of the ACM_, 4 (No. 7): 321, 1961.
  24.  *
  25.  *   Charles Antony Richard Hoare, "Algorithm 64: Quicksort."  _Communications
  26.  *      of the ACM_, 4 (No. 7): 321, 1961.
  27.  *
  28.  *   Charles Antony Richard Hoare, "Quicksort."  _The Computer Journal_,
  29.  *      5 (April 1962 - January 1963): 10-15, 1962.
  30.  *
  31.  * See also:
  32.  *
  33.  *   Donald Ervin Knuth, _The Art of Computer Programming; Volume 3:  Sorting
  34.  *     and Searching_, Addison-Wesley, Reading, Mass., 1973, Chapter 5,
  35.  *     Sorting, pp 114-123.  ISBN 0-201-03803-X.
  36.  *
  37.  *   Robert Sedgewick, "Implementing Quicksort Programs."  _Communications
  38.  *      of the ACM_, 21 (No. 10): 847-857, 1978.
  39.  *
  40.  *
  41.  *                           Quicksort in TDE
  42.  *
  43.  * Quicksort in TDE is a stable, non-recursive implementation based on
  44.  * Program 2, page 851, CACM, 21 (No. 10), 1978, by Robert Sedgewick.  My
  45.  * partition algorithm finds the median-of-three.  Then, it walks from the
  46.  * head of the list, comparing nodes, and uses the first occurrence of the
  47.  * key of the median-of-three as the partition node.  Mostly by accident
  48.  * and partly by design, my partition routine uses a "fat pivot" to keep
  49.  * equal nodes in the same relative order as they appear in the file (the
  50.  * definition of a stable sort).  By using the first median-of-three node
  51.  * as the partitioning node, 1) sorting a sorted list is fairly fast and
  52.  * 2) encountering a worst case is very unlikely.  TDE will sort, fairly
  53.  * fast, multiple keys ascending or descending, ignore or match case, and
  54.  * preserve order in the file, while using a custom sort sequence for your
  55.  * favorite domestic or foreign language.
  56.  *
  57.  * Found an error in the comparison function in versions 2.2 & 3.0.  Equal
  58.  * keys were not compared correctly.  Fixed in version 3.1.
  59.  *
  60.  * New editor name:  TDE, the Thomson-Davis Editor.
  61.  * Author:           Frank Davis
  62.  * Date:             June 5, 1991, version 1.0
  63.  * Date:             July 29, 1991, version 1.1
  64.  * Date:             October 5, 1991, version 1.2
  65.  * Date:             January 20, 1992, version 1.3
  66.  * Date:             February 17, 1992, version 1.4
  67.  * Date:             April 1, 1992, version 1.5
  68.  * Date:             June 5, 1992, version 2.0
  69.  * Date:             October 31, 1992, version 2.1
  70.  * Date:             April 1, 1993, version 2.2
  71.  * Date:             June 5, 1993, version 3.0
  72.  * Date:             August 29, 1993, version 3.1
  73.  *
  74.  * This code is released into the public domain, Frank Davis.
  75.  * You may use and distribute it freely.
  76.  */
  77.  
  78. #include "tdestr.h"
  79. #include "common.h"
  80. #include "tdefunc.h"
  81. #include "define.h"
  82.  
  83.  
  84. /*
  85.  * Name:    sort_box_block
  86.  * Purpose: sort lines according to text in marked BOX block
  87.  * Date:    June 5, 1992
  88.  * Passed:  window:  pointer to current window
  89.  * Notes:   quick sort and insertion sort the lines in the BOX buff according
  90.  *           to stuff in a box block.
  91.  */
  92. int  sort_box_block( WINDOW *window )
  93. {
  94. int  prompt_line;
  95. int  block_type;
  96. line_list_ptr ll;
  97. register file_infos *file;
  98. WINDOW *sw;
  99. int  rc;
  100. char line_buff[(MAX_COLS+1)*2]; /* buffer for char and attribute  */
  101.  
  102.    /*
  103.     * make sure block is marked OK
  104.     */
  105.    rc = OK;
  106.    prompt_line = window->bottom_line;
  107.    entab_linebuff( );
  108.    if (un_copy_line( window->ll, window, TRUE ) == ERROR)
  109.       return( ERROR );
  110.    check_block( );
  111.    if (g_status.marked == TRUE) {
  112.       file  = g_status.marked_file;
  113.       block_type = file->block_type;
  114.       if (block_type == BOX) {
  115.          /*
  116.           * sort ascending or descending?
  117.           */
  118.          rc = get_sort_order( window );
  119.          if (rc != ERROR) {
  120.             file->modified = TRUE;
  121.             if (mode.do_backups == TRUE) {
  122.                sw = g_status.window_list;
  123.                for (; ptoul( sw->file_info ) != ptoul( file );)
  124.                   sw = sw->next;
  125.                backup_file( sw );
  126.             }
  127.  
  128.             /*
  129.              * figure the width of the block.
  130.              */
  131.             sort.block_len = file->block_ec + 1 - file->block_bc;
  132.  
  133.             /*
  134.              * save the prompt line and print the quicksort message.
  135.              */
  136.             save_screen_line( 0, prompt_line, line_buff );
  137.             eol_clear( 0, prompt_line, g_display.text_color );
  138.             set_prompt( block22a, prompt_line );
  139.  
  140.             /*
  141.              * set up the sort structure.
  142.              */
  143.             sort.bc  = g_status.marked_file->block_bc;
  144.             sort.ec  = g_status.marked_file->block_ec;
  145.             sort.order_array = (mode.search_case == IGNORE) ?
  146.                                     sort_order.ignore : sort_order.match;
  147.  
  148.             /*
  149.              * save the previous node for use with insertion sort.
  150.              */
  151.             ll = file->block_start->prev;
  152.             quick_sort_block( file->block_br, file->block_er,
  153.                               file->block_start, file->block_end );
  154.  
  155.             /*
  156.              * get back previous node and clean up list with insertion
  157.              *   sort.
  158.              */
  159.             if (ll == NULL)
  160.                ll = file->line_list;
  161.             else
  162.                ll = ll->next;
  163.             set_prompt( block22b, prompt_line );
  164.             insertion_sort_block( file->block_br, file->block_er, ll );
  165.  
  166.             /*
  167.              * housekeeping.  mark the file as dirty and restore the
  168.              *   cursors, which are scrambled during the sort.
  169.              */
  170.             file->dirty = GLOBAL;
  171.             restore_cursors( file );
  172.             restore_screen_line( 0, prompt_line, line_buff );
  173.          }
  174.       } else {
  175.          /*
  176.           * can only sort box blocks
  177.           */
  178.          error( WARNING, prompt_line, block23 );
  179.          rc = ERROR;
  180.       }
  181.    } else {
  182.       /*
  183.        * box not marked
  184.        */
  185.       error( WARNING, prompt_line, block24 );
  186.       rc = ERROR;
  187.    }
  188.    return( rc );
  189. }
  190.  
  191.  
  192. /*
  193.  * Name:    quick_sort_block
  194.  * Purpose: sort lines according to text in marked BOX block
  195.  * Date:    Jaunary 10, 1993
  196.  * Passed:  low:        starting line in box block
  197.  *          high:       ending line in a box block
  198.  *          low_node:   starting node in box block
  199.  *          high_node:  ending node in box block
  200.  * Notes:   Quicksort lines in the BOX block according to keys in
  201.  *           a box block.
  202.  *          because the median of three method is used to find the partion
  203.  *           node,  high - low  should be greater than or equal to 2.
  204.  *          with end recursion removal and sorting the smallest sublist
  205.  *           first, our stack only needs room for log2 (N+1)/(M+2) nodes.
  206.  *           a stack size of 24 can reliably handle almost 500 million lines.
  207.  */
  208. void quick_sort_block( long low, long high, line_list_ptr low_node,
  209.                        line_list_ptr high_node )
  210. {
  211. long low_rline_stack[24];
  212. long high_rline_stack[24];
  213. line_list_ptr low_node_stack[24];
  214. line_list_ptr high_node_stack[24];
  215. long low_count;
  216. long high_count;
  217. long count;
  218. line_list_ptr low_start;
  219. line_list_ptr low_head;
  220. line_list_ptr low_tail;
  221. line_list_ptr high_end;
  222. line_list_ptr high_head;
  223. line_list_ptr high_tail;
  224. line_list_ptr equal_head;
  225. line_list_ptr equal_tail;
  226. line_list_ptr walk_node;
  227. line_list_ptr median_node;
  228. int  i;
  229. int  stack_pointer;
  230.  
  231.    assert( low_node->len != EOF);
  232.    assert( high_node->len != EOF);
  233.  
  234.    stack_pointer = 0;
  235.    for (;;) {
  236.  
  237.       /*
  238.        * being that a median-of-three is used as the partition algorithm,
  239.        *  we probably need to have at least 2 nodes in each sublist.  I
  240.        *  chose a minimum of 25 nodes as a SWAG (scientific wild ass guess).
  241.        *  a simple insertion sort mops the list after quicksort finishes.
  242.        */
  243.       while (high - low > 25) {
  244.  
  245.          assert( high >= 1 );
  246.          assert( low  >= 1 );
  247.          assert( low  <= high );
  248.  
  249.          /*
  250.           * start the walk node at the head of the list and walk to the
  251.           *  middle of the sublist.
  252.           */
  253.          walk_node  = low_node;
  254.          count = (high - low) / 2;
  255.          for (; count > 0; count--)
  256.             walk_node = walk_node->next;
  257.  
  258.          /*
  259.           * now, find the median of the low, middle, and high node.
  260.           *
  261.           * being that I am subject to error, let's assert that we really
  262.           *  did find the median-of-three.
  263.           */
  264.          load_pivot( low_node );
  265.          if (compare_pivot( walk_node ) < 0) {
  266.             low_head   = walk_node;
  267.             median_node = low_node;
  268.          } else {
  269.             low_head   = low_node;
  270.             median_node = walk_node;
  271.          }
  272.          high_head = high_node;
  273.          load_pivot( median_node );
  274.          if (compare_pivot( high_node ) < 0) {
  275.             high_head   = median_node;
  276.             median_node = high_node;
  277.          }
  278.          load_pivot( median_node );
  279.          if (compare_pivot( low_head ) > 0) {
  280.             low_tail    = median_node;
  281.             median_node = low_head;
  282.             low_head    = low_tail;
  283.          }
  284.  
  285.          load_pivot( median_node );
  286.  
  287.          assert( compare_pivot( low_head ) <= 0 );
  288.          assert( compare_pivot( high_head ) >= 0 );
  289.  
  290.          /*
  291.           * now, walk again from the head of the list comparing nodes and
  292.           *  use the first occurrence of the median node as the partition.
  293.           */
  294.          walk_node = low_node;
  295.          for (i = 0; ; walk_node = walk_node->next) {
  296.             if (compare_pivot( walk_node ) == 0)
  297.                break;
  298.             i = 1;
  299.          }
  300.  
  301.          /*
  302.           * initialize pointers and counters for this partition.
  303.           */
  304.          low_start  = low_node->prev;
  305.          high_end   = high_node->next;
  306.          low_head   = low_tail  = NULL;
  307.          high_head  = high_tail = NULL;
  308.          low_count  = high_count = 0;
  309.  
  310.          /*
  311.           * setup the first occurrence of the median node as a "fat pivot"
  312.           *  sublist.  there are two cases to consider 1) the first
  313.           *  occurrence of the median node is the first element in the
  314.           *  sublist, i == 0, or 2) the first occurrence of the median node
  315.           *  is somewhere in the sublist.
  316.           */
  317.          if (i == 0)
  318.             walk_node = equal_head = equal_tail = low_node;
  319.          else {
  320.             equal_head = equal_tail = walk_node;
  321.             equal_head->next->prev = equal_head->prev;
  322.             equal_head->prev->next = equal_head->next;
  323.             equal_head->next = low_node;
  324.             walk_node = equal_head;
  325.          }
  326.          load_pivot( equal_head );
  327.  
  328.          /*
  329.           * PARTITION:
  330.           *  put all nodes less than the pivot on the end of the low list.
  331.           *  put all nodes equal to the pivot on the end of the equal list.
  332.           *  put all nodes greater than the pivot on the end of the high list.
  333.           */
  334.          for (count=low+1; count <= high; count++) {
  335.             walk_node = walk_node->next;
  336.             i = compare_pivot( walk_node );
  337.             if (i > 0) {
  338.                if (high_head == NULL)
  339.                   high_head = high_tail = walk_node;
  340.                else {
  341.                   high_tail->next = walk_node;
  342.                   walk_node->prev = high_tail;
  343.                   high_tail = walk_node;
  344.                }
  345.  
  346.                /*
  347.                 * keep a count of the number of nodes in the high list.
  348.                 */
  349.                ++high_count;
  350.             } else if (i < 0) {
  351.                if (low_head == NULL)
  352.                   low_head = low_tail = walk_node;
  353.                else {
  354.                   low_tail->next = walk_node;
  355.                   walk_node->prev = low_tail;
  356.                   low_tail = walk_node;
  357.                }
  358.  
  359.                /*
  360.                 * keep a count of the number of nodes in the low list
  361.                 */
  362.                ++low_count;
  363.             } else {
  364.                equal_tail->next = walk_node;
  365.                walk_node->prev = equal_tail;
  366.                equal_tail = walk_node;
  367.             }
  368.          }
  369.  
  370.          assert( low_count >= 0 );
  371.          assert( low_count < high - low );
  372.          assert( high_count >= 0 );
  373.          assert( high_count < high - low );
  374.  
  375.          /*
  376.           * we just partitioned the sublist into low, equal, and high
  377.           *  sublists.  now, let's put the lists back together.
  378.           */
  379.          if (low_count > 0) {
  380.             low_head->prev = low_start;
  381.             if (low_start != NULL)
  382.                low_start->next = low_head;
  383.             else
  384.                g_status.marked_file->line_list = low_head;
  385.             low_tail->next = equal_head;
  386.             equal_head->prev = low_tail;
  387.          } else {
  388.             equal_head->prev = low_start;
  389.             if (low_start != NULL)
  390.                low_start->next = equal_head;
  391.             else
  392.                g_status.marked_file->line_list = equal_head;
  393.          }
  394.          if (high_count > 0) {
  395.             high_head->prev = equal_tail;
  396.             equal_tail->next = high_head;
  397.             high_tail->next = high_end;
  398.             high_end->prev  = high_tail;
  399.          } else {
  400.             equal_tail->next = high_end;
  401.             high_end->prev   = equal_tail;
  402.          }
  403.  
  404.          /*
  405.           * now, lets look at the low list and the high list.  save the node
  406.           *  pointers and counters of the longest sublist on the stack.
  407.           *  then, quicksort the shortest sublist.
  408.           */
  409.          if (low_count > high_count) {
  410.  
  411.             /*
  412.              * if fewer than 25 nodes in the high count, don't bother to
  413.              *  push the stack -- sort the low list.
  414.              */
  415.             if (high_count > 25) {
  416.                low_rline_stack[stack_pointer]  = low;
  417.                high_rline_stack[stack_pointer] = low + low_count - 1;
  418.                low_node_stack[stack_pointer]   = low_head;
  419.                high_node_stack[stack_pointer]  = low_tail;
  420.                ++stack_pointer;
  421.                low       = high - high_count + 1;
  422.                high      = high;
  423.                low_node  = high_head;
  424.                high_node = high_tail;
  425.             } else {
  426.                low       = low;
  427.                high      = low + low_count - 1;
  428.                low_node  = low_head;
  429.                high_node = low_tail;
  430.             }
  431.          } else {
  432.  
  433.             /*
  434.              * if fewer than 25 nodes in the low count, don't bother to
  435.              *  push the stack -- sort the high list.
  436.              */
  437.             if (low_count > 25) {
  438.                low_rline_stack[stack_pointer]  = high - high_count + 1;
  439.                high_rline_stack[stack_pointer] = high;
  440.                low_node_stack[stack_pointer]   = high_head;
  441.                high_node_stack[stack_pointer]  = high_tail;
  442.                ++stack_pointer;
  443.                low       = low;
  444.                high      = low + low_count - 1;
  445.                low_node  = low_head;
  446.                high_node = low_tail;
  447.             } else {
  448.                low       = high - high_count + 1;
  449.                high      = high;
  450.                low_node  = high_head;
  451.                high_node = high_tail;
  452.             }
  453.          }
  454.  
  455.          assert( stack_pointer < 24 );
  456.       }
  457.  
  458.       /*
  459.        * now that we have sorted the smallest sublist, we need to pop
  460.        *  the long sublist(s) that were pushed on the stack.
  461.        */
  462.       --stack_pointer;
  463.       if (stack_pointer < 0)
  464.          break;
  465.       low       = low_rline_stack[stack_pointer];
  466.       high      = high_rline_stack[stack_pointer];
  467.       low_node  = low_node_stack[stack_pointer];
  468.       high_node = high_node_stack[stack_pointer];
  469.    }
  470. }
  471.  
  472.  
  473. /*
  474.  * Name:    insertion_sort_block
  475.  * Purpose: sort small partitions passed in by qsort
  476.  * Date:    January 10, 1993
  477.  * Passed:  low:          starting line in box block
  478.  *          high:         ending line in a box block
  479.  *          first_node:   first linked list node to sort
  480.  * Notes:   Insertion sort the lines in the BOX buff according to stuff in
  481.  *           a box block.
  482.  */
  483. void insertion_sort_block( long low, long high, line_list_ptr first_node )
  484. {
  485. long down;                      /* relative line number for insertion sort */
  486. long pivot;                     /* relative line number of pivot in block */
  487. long count;
  488. line_list_ptr pivot_node;       /* pointer to actual text in block */
  489. line_list_ptr down_node;        /* pointer used to compare text */
  490. text_ptr key;
  491. int  dirty_flag;
  492. int  len;
  493.  
  494.    /*
  495.     * make sure we have more than 1 line to sort.
  496.     */
  497.    if (low < high) {
  498.  
  499.       count = (int)(high - low) + 1;
  500.       pivot_node = first_node->next;
  501.       for (pivot=1; pivot < count; pivot++) {
  502.          load_pivot( pivot_node );
  503.          key = pivot_node->line;
  504.          len = pivot_node->len;
  505.          dirty_flag = pivot_node->dirty;
  506.          down_node = pivot_node;
  507.          for (down=pivot-1; down >= 0; down--) {
  508.             /*
  509.              * lets keep comparing the keys until we find the hole for
  510.              *  pivot.
  511.              */
  512.             if (compare_pivot( down_node->prev ) > 0) {
  513.                down_node->line = down_node->prev->line;
  514.                down_node->len = down_node->prev->len;
  515.                down_node->dirty = down_node->prev->dirty;
  516.             } else
  517.                break;
  518.             down_node = down_node->prev;
  519.          }
  520.          down_node->line = key;
  521.          down_node->len  = len;
  522.          down_node->dirty = (char)dirty_flag;
  523.          pivot_node = pivot_node->next;
  524.       }
  525.    }
  526. }
  527.  
  528.  
  529. /*
  530.  * Name:    load_pivot
  531.  * Purpose: load pivot point for insertion sort
  532.  * Date:    June 5, 1992
  533.  * Passed:  text:  line that contains the pivot
  534.  */
  535. void load_pivot( line_list_ptr node )
  536. {
  537.    sort.pivot_ptr = node->line;
  538.    sort.pivot_len = node->len;
  539. }
  540.  
  541.  
  542. /*
  543.  * Name:    compare_pivot
  544.  * Purpose: compare pivot string with text string
  545.  * Date:    June 5, 1992
  546.  * Passed:  text:  pointer to current line
  547.  * Notes:   the sort structure keeps track of the pointer to the pivot line
  548.  *           and the pivot line length.
  549.  */
  550. int  compare_pivot( line_list_ptr node )
  551. {
  552. register int len;
  553. register int bc;
  554. int  rc;
  555. int  left_over;
  556.  
  557.    len = node->len;
  558.    bc  = sort.bc;
  559.  
  560.    assert( bc >= 0 );
  561.    assert( len >= 0 );
  562.  
  563.    /*
  564.     * is the current line length less than beginning column?  if so, just
  565.     *  look at the length of the pivot line.  no need to compare keys.
  566.     */
  567.    if (len < bc+1) {
  568.       if (sort.pivot_len < bc+1)
  569.          return( 0 );
  570.       else
  571.          return( sort.direction == ASCENDING ?  -1 : 1 );
  572.  
  573.    /*
  574.     * is the pivot line length less than beginning column?  if so, just
  575.     *  look at the length of the current line.  no need to compare keys.
  576.     */
  577.    } else if (sort.pivot_len < bc+1) {
  578.       if (len < bc+1)
  579.          return( 0 );
  580.       else
  581.          return( sort.direction == ASCENDING ?  1 : -1 );
  582.    } else {
  583.  
  584.       /*
  585.        * if lines are of equal length or greater than the ending column,
  586.        *  then lets consider them equal.
  587.        */
  588.       if (len == sort.pivot_len)
  589.          left_over = 0;
  590.       else if (len > sort.ec  &&  sort.pivot_len > sort.ec)
  591.          left_over = 0;
  592.       else {
  593.  
  594.          /*
  595.           * if one line does not extend thru the ending column, give
  596.           *  preference to the longest key.
  597.           */
  598.          if (sort.direction == ASCENDING)
  599.             left_over =  len > sort.pivot_len ? 1 : -1;
  600.          else
  601.             left_over =  len > sort.pivot_len ? -1 : 1;
  602.       }
  603.  
  604.       /*
  605.        * only need to compare up to length of the key in the pivot line.
  606.        */
  607.       if (len > sort.pivot_len)
  608.          len = sort.pivot_len;
  609.       len = len - bc;
  610.       if (len > sort.block_len)
  611.          len = sort.block_len;
  612.  
  613.       assert( len > 0 );
  614.  
  615.       if (sort.direction == ASCENDING)
  616.          rc = my_memcmp( node->line + bc, sort.pivot_ptr + bc, len );
  617.       else
  618.          rc = my_memcmp( sort.pivot_ptr + bc, node->line + bc, len );
  619.  
  620.       /*
  621.        * if keys are equal, let's see if one key is longer than the other.
  622.        */
  623.       if (rc == 0)
  624.          rc = left_over;
  625.       return( rc );
  626.    }
  627. }
  628.  
  629.  
  630. /*
  631.  * Name:    my_memcmp
  632.  * Purpose: compare strings using ignore or match case sort order
  633.  * Date:    October 31, 1992
  634.  * Passed:  s1:  pointer to string 1
  635.  *          s2:  pointer to string 2
  636.  *          len: number of characters to compare
  637.  * Notes:   let's do our own memcmp, so we can sort languages that use
  638.  *           extended characters as part of their alphabet.
  639.  */
  640. int  my_memcmp( text_ptr s1, text_ptr s2, int len )
  641. {
  642. unsigned char *p;
  643. register int c;
  644.  
  645.    assert( len >= 0 );
  646.    assert( len < MAX_LINE_LENGTH );
  647.    assert( s1 != NULL );
  648.    assert( s2 != NULL );
  649.  
  650.    if (len == 0)
  651.       return( 0 );
  652.  
  653.    p = sort.order_array;
  654.  
  655.    /*
  656.     * the C comparison function is equivalent to the assembly version;
  657.     *  however, once the assembly routine initializes, it is much faster
  658.     *  than the C version.
  659.     */
  660.    if (len < 10) {
  661.       for (;len > 0  &&  (c = (int)p[*s1] - (int)p[*s2]) == 0;
  662.                                               s1++, s2++, len--);
  663.       return( c );
  664.    } else {
  665.  
  666.       ASSEMBLE {
  667.  
  668.    /*
  669.    ; Register strategy:
  670.    ;   ax  == *s1
  671.    ;   dx  == *s2
  672.    ;   ds:[si]  == s1
  673.    ;   es:[bx]  == s2
  674.    ;   bp       == sort.order_array
  675.    ;   [bp+di]  == p[*s1]  or  p[*s2]
  676.    ;   cx       == len
  677.    ;
  678.    ;  CAVEAT:  sort.order_array is assumed to be located in the stack segment
  679.    */
  680.  
  681.         push    ds                      /* push required registers */
  682.         push    si
  683.         push    di
  684.         push    bp
  685.  
  686.         xor     ax, ax                  /* zero ax */
  687.         mov     cx, WORD PTR len        /* keep len in cx */
  688.         cmp     cx, 0                   /* len <= 0? */
  689.         jle     get_out                 /* yes, get out */
  690.  
  691.         mov     bx, WORD PTR s2         /* load our registers */
  692.         mov     ax, WORD PTR s2+2
  693.         mov     es, ax                  /* es:[bx] = s2 */
  694.         mov     si, WORD PTR s1
  695.         mov     ax, WORD PTR s1+2
  696.         mov     ds, ax                  /* ds:[si] = s1 */
  697.         mov     bp, p                   /* [bp] = p */
  698.         xor     ax, ax                  /* zero out ax */
  699.         xor     dx, dx                  /* zero out dx */
  700.       }
  701. top:
  702.  
  703.    ASSEMBLE {
  704.         mov     al, BYTE PTR ds:[si]    /* al == *s1 */
  705.         mov     di, ax
  706.         mov     al, BYTE PTR [bp+di]    /* al == p[*s1] */
  707.         mov     dl, BYTE PTR es:[bx]    /* dl == *s2 */
  708.         mov     di, dx
  709.         mov     dl, BYTE PTR [bp+di]    /* dl == p[*s2] */
  710.         sub     ax, dx                  /* ax == p[*s1] - p[*s2] */
  711.         jne     get_out
  712.         inc     bx
  713.         inc     si
  714.         dec     cx
  715.         cmp     cx, 0
  716.         jg      top                     /* ax keeps the return value */
  717.       }
  718. get_out:
  719.  
  720.    ASSEMBLE {
  721.         pop     bp                      /* pop the registers we pushed */
  722.         pop     di
  723.         pop     si
  724.         pop     ds                      /* ax keeps the return value */
  725.       }
  726.    }
  727. }
  728.