sort.c

C语言实战105例源码

         /*
          * now, lets look at the low list and the high list.  save the node
          *  pointers and counters of the longest sublist on the stack.
          *  then, quicksort the shortest sublist.
          */
         if (low_count > high_count) {

            /*
             * if fewer than 25 nodes in the high count, don't bother to
             *  push the stack -- sort the low list.
             */
            if (high_count > 25) {
               low_rline_stack[stack_pointer]  = low;
               high_rline_stack[stack_pointer] = low + low_count - 1;
               low_node_stack[stack_pointer]   = low_head;
               high_node_stack[stack_pointer]  = low_tail;
               ++stack_pointer;
               low       = high - high_count + 1;
               high      = high;
               low_node  = high_head;
               high_node = high_tail;
            } else {
               low       = low;
               high      = low + low_count - 1;
               low_node  = low_head;
               high_node = low_tail;
            }
         } else {

            /*
             * if fewer than 25 nodes in the low count, don't bother to
             *  push the stack -- sort the high list.
             */
            if (low_count > 25) {
               low_rline_stack[stack_pointer]  = high - high_count + 1;
               high_rline_stack[stack_pointer] = high;
               low_node_stack[stack_pointer]   = high_head;
               high_node_stack[stack_pointer]  = high_tail;
               ++stack_pointer;
               low       = low;
               high      = low + low_count - 1;
               low_node  = low_head;
               high_node = low_tail;
            } else {
               low       = high - high_count + 1;
               high      = high;
               low_node  = high_head;
               high_node = high_tail;
            }
         }

         assert( stack_pointer < 24 );
      }

      /*
       * now that we have sorted the smallest sublist, we need to pop
       *  the long sublist(s) that were pushed on the stack.
       */
      --stack_pointer;
      if (stack_pointer < 0)
         break;
      low       = low_rline_stack[stack_pointer];
      high      = high_rline_stack[stack_pointer];
      low_node  = low_node_stack[stack_pointer];
      high_node = high_node_stack[stack_pointer];
   }
}


/*
 * Name:    insertion_sort_block
 * Purpose: sort small partitions passed in by qsort
 * Date:    January 10, 1993
 * Passed:  low:          starting line in box block
 *          high:         ending line in a box block
 *          first_node:   first linked list node to sort
 * Notes:   Insertion sort the lines in the BOX buff according to stuff in
 *           a box block.
 */
void insertion_sort_block( long low, long high, line_list_ptr first_node )
{
long down;                      /* relative line number for insertion sort */
long pivot;                     /* relative line number of pivot in block */
long count;
line_list_ptr pivot_node;       /* pointer to actual text in block */
line_list_ptr down_node;        /* pointer used to compare text */
text_ptr key;
int  dirty_flag;
int  len;

   /*
    * make sure we have more than 1 line to sort.
    */
   if (low < high) {

      count = (int)(high - low) + 1;
      pivot_node = first_node->next;
      for (pivot=1; pivot < count; pivot++) {
         load_pivot( pivot_node );
         key = pivot_node->line;
         len = pivot_node->len;
         dirty_flag = pivot_node->dirty;
         down_node = pivot_node;
         for (down=pivot-1; down >= 0; down--) {
            /*
             * lets keep comparing the keys until we find the hole for
             *  pivot.
             */
            if (compare_pivot( down_node->prev ) > 0) {
               down_node->line = down_node->prev->line;
               down_node->len = down_node->prev->len;
               down_node->dirty = down_node->prev->dirty;
            } else
               break;
            down_node = down_node->prev;
         }
         down_node->line = key;
         down_node->len  = len;
         down_node->dirty = (char)dirty_flag;
         pivot_node = pivot_node->next;
      }
   }
}


/*
 * Name:    load_pivot
 * Purpose: load pivot point for insertion sort
 * Date:    June 5, 1992
 * Passed:  text:  line that contains the pivot
 */
void load_pivot( line_list_ptr node )
{
   sort.pivot_ptr = node->line;
   sort.pivot_len = node->len;
}


/*
 * Name:    compare_pivot
 * Purpose: compare pivot string with text string
 * Date:    June 5, 1992
 * Passed:  text:  pointer to current line
 * Notes:   the sort structure keeps track of the pointer to the pivot line
 *           and the pivot line length.
 */
int  compare_pivot( line_list_ptr node )
{
register int len;
register int bc;
int  rc;
int  left_over;

   len = node->len;
   bc  = sort.bc;

   assert( bc >= 0 );
   assert( len >= 0 );

   /*
    * is the current line length less than beginning column?  if so, just
    *  look at the length of the pivot line.  no need to compare keys.
    */
   if (len < bc+1) {
      if (sort.pivot_len < bc+1)
         return( 0 );
      else
         return( sort.direction == ASCENDING ?  -1 : 1 );

   /*
    * is the pivot line length less than beginning column?  if so, just
    *  look at the length of the current line.  no need to compare keys.
    */
   } else if (sort.pivot_len < bc+1) {
      if (len < bc+1)
         return( 0 );
      else
         return( sort.direction == ASCENDING ?  1 : -1 );
   } else {

      /*
       * if lines are of equal length or greater than the ending column,
       *  then lets consider them equal.
       */
      if (len == sort.pivot_len)
         left_over = 0;
      else if (len > sort.ec  &&  sort.pivot_len > sort.ec)
         left_over = 0;
      else {

         /*
          * if one line does not extend thru the ending column, give
          *  preference to the longest key.
          */
         if (sort.direction == ASCENDING)
            left_over =  len > sort.pivot_len ? 1 : -1;
         else
            left_over =  len > sort.pivot_len ? -1 : 1;
      }

      /*
       * only need to compare up to length of the key in the pivot line.
       */
      if (len > sort.pivot_len)
         len = sort.pivot_len;
      len = len - bc;
      if (len > sort.block_len)
         len = sort.block_len;

      assert( len > 0 );

      if (sort.direction == ASCENDING)
         rc = my_memcmp( node->line + bc, sort.pivot_ptr + bc, len );
      else
         rc = my_memcmp( sort.pivot_ptr + bc, node->line + bc, len );

      /*
       * if keys are equal, let's see if one key is longer than the other.
       */
      if (rc == 0)
         rc = left_over;
      return( rc );
   }
}


/*
 * Name:    my_memcmp
 * Purpose: compare strings using ignore or match case sort order
 * Date:    October 31, 1992
 * Passed:  s1:  pointer to string 1
 *          s2:  pointer to string 2
 *          len: number of characters to compare
 * Notes:   let's do our own memcmp, so we can sort languages that use
 *           extended characters as part of their alphabet.
 */
int  my_memcmp( text_ptr s1, text_ptr s2, int len )
{
unsigned char *p;
register int c;

   assert( len >= 0 );
   assert( len < MAX_LINE_LENGTH );
   assert( s1 != NULL );
   assert( s2 != NULL );

   if (len == 0)
      return( 0 );

   p = sort.order_array;

   /*
    * the C comparison function is equivalent to the assembly version;
    *  however, once the assembly routine initializes, it is much faster
    *  than the C version.
    */
   if (len < 10) {
      for (;len > 0  &&  (c = (int)p[*s1] - (int)p[*s2]) == 0;
                                              s1++, s2++, len--);
      return( c );
   } else {

      ASSEMBLE {

   /*
   ; Register strategy:
   ;   ax  == *s1
   ;   dx  == *s2
   ;   ds:[si]  == s1
   ;   es:[bx]  == s2
   ;   bp       == sort.order_array
   ;   [bp+di]  == p[*s1]  or  p[*s2]
   ;   cx       == len
   ;
   ;  CAVEAT:  sort.order_array is assumed to be located in the stack segment
   */

        push    ds                      /* push required registers */
        push    si
        push    di
        push    bp

        xor     ax, ax                  /* zero ax */
        mov     cx, WORD PTR len        /* keep len in cx */
        cmp     cx, 0                   /* len <= 0? */
        jle     get_out                 /* yes, get out */

        mov     bx, WORD PTR s2         /* load our registers */
        mov     ax, WORD PTR s2+2
        mov     es, ax                  /* es:[bx] = s2 */
        mov     si, WORD PTR s1
        mov     ax, WORD PTR s1+2
        mov     ds, ax                  /* ds:[si] = s1 */
        mov     bp, p                   /* [bp] = p */
        xor     ax, ax                  /* zero out ax */
        xor     dx, dx                  /* zero out dx */
      }
top:

   ASSEMBLE {
        mov     al, BYTE PTR ds:[si]    /* al == *s1 */
        mov     di, ax
        mov     al, BYTE PTR [bp+di]    /* al == p[*s1] */
        mov     dl, BYTE PTR es:[bx]    /* dl == *s2 */
        mov     di, dx
        mov     dl, BYTE PTR [bp+di]    /* dl == p[*s2] */
        sub     ax, dx                  /* ax == p[*s1] - p[*s2] */
        jne     get_out
        inc     bx
        inc     si
        dec     cx
        cmp     cx, 0
        jg      top                     /* ax keeps the return value */
      }
get_out:

   ASSEMBLE {
        pop     bp                      /* pop the registers we pushed */
        pop     di
        pop     si
        pop     ds                      /* ax keeps the return value */
      }
   }
}