sort.c

一个开源著名的TDE编辑器源代码

      /*
       * 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  len;
int  type;

   /*
    * make sure we have more than 1 line to sort.
    */
   count = high - low + 1;
   if (count > 1) {

      pivot_node = first_node->next;
      for (pivot = 1; pivot < count; pivot++) {
         load_pivot( pivot_node );
         key  = pivot_node->line;
         len  = pivot_node->len;
         type = pivot_node->type;
         down_node = pivot_node;
         for (down = pivot; --down >= 0;) {
            /*
             * 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->type = down_node->prev->type;
            } else
               break;
            down_node = down_node->prev;
         }
         down_node->line = key;
         down_node->len  = len;
         down_node->type = type;
         pivot_node = pivot_node->next;
      }
   }
}

#else

/*
 * Name:    merge_sort_block
 * Purpose: sort lines according to text in marked BOX block
 * Author:  Jason Hood
 * Date:    November 25, 2005
 * Passed:  lines:  number of lines to sort
 *          first:  first line of block
 * Notes:   my own algorithm for a non-recursive stable merge sort taking
 *           advantage of natural sort order.
 */
void merge_sort_block( long lines, line_list_ptr first )
{
line_list_ptr h[32], p;         /* heads for each run */
long  n[32];                    /* lengths of each run */
int   i;                        /* current run index */

   if (lines <= 1)
      return;

   h[0] = first;
   for (i = 0;;) {
      /*
       * find out how much is already sorted.
       */
      p = run( h[i], &lines, &n[i] );
      if (lines == 0)
         break;
      /*
       * merge similar-sized runs.
       */
      while (i > 0 && n[i] * 3 / 2 >= n[i-1] /*|| i == 31*/) {
         --i;
         h[i]  = merge( h[i], n[i], h[i+1], n[i+1], p );
         n[i] += n[i+1];
      }
      h[++i] = p;
   }

   /*
    * merge all remaining runs.
    */
   while (i > 0) {
      --i;
      h[i]  = merge( h[i], n[i], h[i+1], n[i+1], p );
      n[i] += n[i+1];
   }
}


/*
 * Name:    run
 * Purpose: find sequence of already sorted lines
 * Author:  Jason Hood
 * Date:    November 26, 2005
 * Passed:  list:  start of the sequence
 *          len:   pointer to length of the list
 *          cnt:   pointer to receive length of the sequence
 * Returns: line to start next sequence
 * Notes:   updates len with remaining lines.
 */
line_list_ptr run( line_list_ptr list, long *len, long *cnt )
{
line_list_ptr p;
text_ptr line;
int  llen;
long type;
int  rc;

   p = list->next;
   list->type &= ~EQUAL;
   p->type &= ~EQUAL;
   *cnt = 1;
   if (--*len > 0) {
      load_pivot( list );
      rc = compare_pivot( p );
      if (rc < 0) {
         line = p->line;                /* the first two lines are out of */
         llen = p->len;                 /*  order, so swap them */
         type = p->type;
         p->line = list->line;
         p->len  = list->len;
         p->type = list->type;
         list->line = line;
         list->len  = llen;
         list->type = type;
         /*
         // relink - requires "line_list_ptr *list"
         // example: TOF b a EOF        // list = b, p = a
         (*list)->prev->next = p;       // TOF -> a
         p->prev = (*list)->prev;       //   a <- TOF
         (*list)->next = p->next;       //   b -> EOF
         p->next->prev = *list;         // EOF <- b
         p->next = *list;               //   a -> b
         (*list)->prev = p;             //   b <- a
         *list = p;                     // a
         p = p->next;                   // b
         */
      }
      /*
       * find remaining in-order lines.
       */
      do {
         if (rc == 0)
            p->type |= EQUAL;
         load_pivot( p );
         p = p->next;
         p->type &= ~EQUAL;
         ++*cnt;
      } while (--*len != 0 && (rc = compare_pivot( p )) >= 0);
   }

   return( p );
}


/*
 * Name:    merge
 * Purpose: merge two sorted lists
 * Author:  Jason Hood
 * Date:    November 26, 2005
 * Passed:  one:   start of first list
 *          len1:  length of first list
 *          two:   start of second list
 *          len2:  length of second list
 *          tail:  line after the end of two (ie: two + len2 == tail).
 * Returns: start of merged list
 * Notes:   two is assumed to follow after one (ie: one + len1 == two).
 *          both lengths are assumed to be one or more.
 */
line_list_ptr merge( line_list_ptr one, long len1,
                     line_list_ptr two, long len2, line_list_ptr tail )
{
line_list_ptr head, t1;
line_list_ptr p;
int  rc;

   p = head = one->prev;
   t1 = two->prev;                      /* the last line of one */
   t1->next = tail;                     /* make one finish at the tail */

   /*
    * can two just move before one?  this generally increases the number of
    * comparisons, but it *greatly* reduces it for reverse sorting.
    */
   load_pivot( one );
   if (compare_pivot( tail->prev ) < 0) {
      /*
       *    one   two    tail
       * TOF 4 5 6 1 2 3 EOF --> TOF 1 2 3 4 5 6 EOF
       */
      head->next = two;                 /* TOF -> 1   */
      two->prev = head;                 /*   1 <- TOF */
      tail->prev->next = one;           /*   3 -> 4   */
      one->prev = tail->prev;           /*   4 <- 3   */
      /*t1->next = tail;*/              /*   6 -> EOF */
      tail->prev = t1;                  /* EOF <- 6   */
      return( two );
   }

   for (;;) {
      rc = compare_pivot( two );
      if (rc >= 0) {                    /* add line(s) from one */
         if (rc == 0)
            two->type |= EQUAL;
         one->prev = p;
         p->next = one;
         do {
            one = one->next;
            --len1;
         } while (one->type & EQUAL);
         if (len1 == 0) {               /* add the rest of two */
            t1->next = two;
            two->prev = t1;
            break;
         }
         p = one->prev;
         load_pivot( one );
      }
      if (rc <= 0) {                    /* add line(s) from two */
         two->prev = p;
         p->next = two;
         do {
            two = two->next;
            --len2;
         } while (two->type & EQUAL);
         p = two->prev;
         if (len2 == 0) {               /* add the rest of one */
            p->next = one;
            one->prev = p;
            two->prev = t1;             /* make the tail point back */
            break;                      /*  to the end of one       */
         }
      }
   }

   return( head->next );
}

#endif


/*
 * Name:    load_pivot
 * Purpose: load pivot point for insertion sort
 * Date:    June 5, 1992
 * Passed:  node:  line that contains the pivot
 *
 * jmh 060827: use the line buffer to store the detabbed line.
 */
void load_pivot( line_list_ptr node )
{
text_ptr s;
int len;

   len = node->len;
   s = detab_a_line( node->line, &len, g_status.marked_file->inflate_tabs,
                                       g_status.marked_file->ptab_size );
   memcpy( g_status.line_buff, s, len );
   sort.pivot_ptr = g_status.line_buff;
   sort.pivot_len = 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.
 *
 * jmh 060827: detab the line.
 */
int  compare_pivot( line_list_ptr node )
{
int  len;
register int bc;
int  rc;
int  left_over;
int  dir;
text_ptr s;

#ifdef TEST
   ++*comps;
#endif

   len = node->len;
   bc  = sort.bc;
   dir =  sort.direction == ASCENDING ?  1 : -1;

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

   s = detab_a_line( node->line, &len, g_status.marked_file->inflate_tabs,
                                       g_status.marked_file->ptab_size );

   /*
    * 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( -dir );

   /*
    * 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( dir );
   } else {

      /*
       * if lines are of equal length or greater than the ending column,
       *  then lets consider them equal.
       */
      if (len == sort.pivot_len  ||
          (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.
          */
         left_over =  len > sort.pivot_len ? dir : -dir;
      }

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

      assert( len > 0 );

      if (sort.direction == ASCENDING)
         rc = my_memcmp( s + bc, sort.pivot_ptr + bc, len );
      else
         rc = my_memcmp( sort.pivot_ptr + bc, s + 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;
#if !defined( __DOS16__ )
register int c = 0;
#endif

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

   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.
    * jmh - had a look at djgpp's assembly output and it's pretty similar
    *       to the assembly version, anyway. Borland, OTOH, isn't as good,
    *       so why not use the assembly version all the time?
    */
#if !defined( __DOS16__ )
   if (len > 0)
      while ((c = (int)p[*s1++] - (int)p[*s2++]) == 0  &&  --len != 0) ;
   return( c );

#else
   ASSEMBLE {

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

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

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

        mov     dx, WORD ptr s1+2
        mov     cx, WORD ptr s1         /* dx:cx = s1 */
        les     di, s2                  /* es:di = s2 */
        xor     bx, bx                  /* zero out bx */
      }
top:

   ASSEMBLE {
        mov     ds, dx
        mov     si, cx                  /* ds:si = s1 */
        mov     bl, BYTE PTR ds:[si]    /* bl = *s1 */
        lds     si, p                   /* ds:si = sort order array */
        mov     al, BYTE PTR ds:[si+bx] /* al = p[*s1] */
        mov     bl, BYTE PTR es:[di]    /* bl = *s2 */
        mov     bl, BYTE PTR ds:[si+bx] /* bl = p[*s2] */
        sub     ax, bx                  /* ax = p[*s1] - p[*s2] */
        jne     get_out
        inc     cx                      /* s1++ */
        inc     di                      /* s2++ */
        dec     WORD PTR len            /* len-- */
        jnz     top
      }
get_out:

   ASSEMBLE {
        pop     di                      /* pop the registers we pushed */
        pop     si
        pop     ds                      /* ax keeps the return value */
      }
#if defined( __TURBOC__ )               /* jmh 980614: damn warning is  */
   return _AX;                          /*             driving me crazy */
#endif
#endif
}