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