az_sort.c

并行解法器,功能强大

  Parameter list:
  ===============

  a:               Set of merged lists to be sorted.
                   List 0 consists of a[0-->b[0]-1], list 1 consists of
                   a[b[0]-->b[0]+b[1]-1], list 2 consists of
                   a[b[0]+b[1]-->b[0]+b[1]+b[2]-1], etc.
                   On output, a[] is reordered such that all the even (or
                   all the odd if the_first == 1) come first as described above.

  indx:            indx[i] - indx[i-1] i > 0 (and indx[i] for i = 0)
                   gives the number of sublists comprising the ith merged list.

  start:           a[start] is the first element of the first list to be sorted.

  end:             a[end] is the last element of the last list to be sorted.

  b:               The length of the ith merged list in a[] is given by
                       if (b==0) && (i == 0) indx[0]
                       if (b==0) && (i >  0) indx[i] - indx[i-1]
                       if (b!=0) && (i == 0) b[0]
                       if (b!=0) && (i >  0) b[indx[i-1]]

  mid:             On output, a[mid] is the first element of the second
                   subsequence after sorting (i.e. the first element in the
                   first even merged list if 'the_first' == 0).

  real_lists:      Number of merged lists to be sorted.

  buffer:          A workspace array used to copy values during the sorting.

  buf_len:         The length of the workspace array 'buffer'.

  the_first:       Indicates whether we put the evens or the odd lists first.
                   That is, a[start ... end] contains a series of merged lists
                   to be sorted (l0 l1 l2 l3 l4 l5 l6 ... )
                   the_first = 0 on input, indicates that on output the list
                   will be sorted as (l0 l2 l4 l6 ... l1 l3 l5 ...)
                   the_first = 1 on input, indicates that on output the list
                   will be sorted as (l1 l3 l5 l7 ... l0 l2 l4 ...)

  ind_indices:       Index into  indx[] pointing to the first sublist within
                   the first merged list that will be sorted.

*******************************************************************************/

{

  /* local variables */

  int pre_mid, mid1, mid2, real1, real2;
  int count, rest, i;
  int first2;

  /**************************** execution begins ******************************/

  /* sort as many lists as we can directly using the buffer */

  AZ_direct_sort(b, indx, buffer, a, &start, buf_len, &ind_indices, &the_first,
                 &real_lists, &pre_mid);

  if (real_lists > 2 ) {

    /* split the rest of the list */

    real1 = real_lists >> 1;
    real2 = real_lists - real1;

    if ((real1%2) == 0) first2 = the_first;
    else                first2 = 1 - the_first;

    if (b == 0) {
      count = indx[ind_indices+real1-1];

      if (ind_indices != 0)
        count -= indx[ind_indices-1];
      count *= type_size;
    }
    else {
      count = 0;
      for (i = ind_indices; i < ind_indices+real1-1; i++)
        count += b[indx[i]];

      if (ind_indices == 0) count += b[0];
      else                count += b[indx[ind_indices-1]];
    }

    AZ_sort_dble(a, indx, start, start+count-1, b, &mid1, real1, buffer,
                 buf_len, the_first, ind_indices);

    AZ_sort_dble(a, indx, start+count, end, b, &mid2, real2, buffer, buf_len,
                 first2, ind_indices + real1);

    /* merge the lists */

    if (start+count-1-mid1 < 0 )
      *mid = mid2;
    else if (mid2-1-(start+count) < 0)
      *mid = mid1;
    else {
      move_dble((double *) &(a[mid1]), (double *) &(a[start+count]),
      (start+count-mid1) / sizeof(double),
      (mid2-(start+count)) / sizeof(double));

      *mid = mid1 + (mid2 - (start + count));
    }
  }

  else {
    *mid = start;
    if (real_lists == 2) {
      if (ind_indices ==0) {
        if (b == 0) count = type_size * indx[0];
        else        count = b[0];
      }
      else {
        if (b == 0) count = type_size * (indx[ind_indices] - indx[ind_indices-1]);
        else        count = b[indx[ind_indices-1]];
      }

      rest = end - (start + count) + 1;

      if (the_first == 0)
        *mid = start + count;
      else {
        *mid = start + rest;

        move_dble((double *) &(a[start]), (double *) &(a[start+count]),
        count / sizeof(double), rest / sizeof(double));
      }
    }
    else if (real_lists == 1) {
      if (the_first == 1) *mid = start;
      else                *mid = end + 1;
    }
  }

  if (start > pre_mid) {
    if (*mid == start) {
      *mid = pre_mid;
    }
    else {
      move_dble((double *) &(a[pre_mid]), (double *) &(a[start]),
      (start-pre_mid) / sizeof(double),
      (*mid-start) / sizeof(double));

      *mid = pre_mid + *mid - start;
    }
  }

} /* AZ_sort_dble */

/******************************************************************************/
/******************************************************************************/
/******************************************************************************/

void AZ_sort_ints(char a[], int indx[], int start, int end, int b[], int *mid,
                  int real_lists, char buffer[], int buf_len, int the_first,
                  int ind_indices)

/*******************************************************************************

  Sort the set of merged lists in a[]. In particular a[] contains a sequence of
  'real_lists' merged lists of the form
        list 0   list 1  list 2   list 3
  Each merged list is in fact comprised of a bunch of sublists which consist of
  integer numbers.  On output, AZ_sort_dble will put all the even lists first
  followed by all the odd lists (e.g. list 0, list 2, list4, ...  list1, list3,
  list 5, ...) if 'the_first' == 0. Otherwise, the odd lists are first followed
  by the even lists.

  The algorithm proceeds as follows:
      1) sort as many merged lists as we can using a buffer (of size buf_len)
         and simply copy what does not belong in the first subsequence
         (either even or odd depending on 'the_first') into the buffer.
      2) split the remaining merged lists into 2 sublists.
      3) use AZ_sort_dble() recursively for each of the 2 sublists.
      4) merge the results of the 2 recursive calls so that the entire
         list is sorted.

  Author:          Ray S. Tuminaro, SNL, 1422
  =======

  Return code:     void
  ============

  Parameter list:
  ===============

  a:               Set of merged lists to be sorted.
                   List 0 consists of a[0-->b[0]-1], list 1 consists of
                   a[b[0]-->b[0]+b[1]-1], list 2 consists of
                   a[b[0]+b[1]-->b[0]+b[1]+b[2]-1], etc.
                   On output, a[] is reordered such that all the even (or
                   all the odd if the_first == 1) come first as described above.

  indx:            indx[i] - indx[i-1] i > 0 (and indx[i] for i = 0)
                   gives the number of sublists comprising the ith merged list.

  start:           a[start] is the first element of the first list to be sorted.

  end:             a[end] is the last element of the last list to be sorted.

  b:               The length of the ith merged list in a[] is given by
                       if (b==0) && (i == 0) indx[0]
                       if (b==0) && (i >  0) indx[i] - indx[i-1]
                       if (b!=0) && (i == 0) b[0]
                       if (b!=0) && (i >  0) b[indx[i-1]]

  mid:             On output, a[mid] is the first element of the second
                   subsequence after sorting (i.e. the first element in the
                   first even merged list if 'the_first' == 0).

  real_lists:      Number of merged lists to be sorted.

  buffer:          A workspace array used to copy values during the sorting.

  buf_len:         The length of the workspace array 'buffer'.

  the_first:       Indicates whether we put the evens or the odd lists first.
                   That is, a[start ... end] contains a series of merged lists
                   to be sorted (l0 l1 l2 l3 l4 l5 l6 ... )
                   the_first = 0 on input, indicates that on output the list
                   will be sorted as (l0 l2 l4 l6 ... l1 l3 l5 ...)
                   the_first = 1 on input, indicates that on output the list
                   will be sorted as (l1 l3 l5 l7 ... l0 l2 l4 ...)

  ind_indices:       Index into  indx[] pointing to the first sublist within
                   the first merged list that will be sorted.

*******************************************************************************/

{

  /* local variables */

  int pre_mid, mid1, mid2, real1, real2;
  int count, rest, i;
  int first2;

  /**************************** execution begins ******************************/

  /* sort as many lists as we can directly using the buffer */

  AZ_direct_sort(b, indx, buffer, a, &start, buf_len, &ind_indices, &the_first,
                 &real_lists, &pre_mid);

  if (real_lists > 2 ) {

    /* split the rest of the list */

    real1 = real_lists >> 1;
    real2 = real_lists - real1;

    if ( (real1%2) == 0) first2 = the_first;
    else                 first2 = 1 - the_first;

    if (b == 0) {
      count = indx[ind_indices+real1-1];

      if (ind_indices != 0)
        count -= indx[ind_indices-1];

      count *= type_size;
    }
    else {
      count = 0;
      for (i = ind_indices; i < ind_indices+real1-1; i++)
        count += b[indx[i]];

      if (ind_indices == 0) count += b[0];
      else                count += b[indx[ind_indices-1]];
    }

    AZ_sort_ints(a, indx, start, start+count-1, b, &mid1, real1, buffer,
                 buf_len, the_first, ind_indices);

    AZ_sort_ints(a, indx, start+count, end, b, &mid2, real2, buffer, buf_len,
                 first2, ind_indices+real1);

    /* merge the lists */

    if(start+count-1-mid1 < 0 )
      *mid = mid2;
    else if (mid2-1-(start+count) < 0)
      *mid = mid1;
    else {
      move_ints((int *) &(a[mid1]), (int *) &(a[start+count]),
      (start+count-mid1) / sizeof(int),
      (mid2-(start+count)) / sizeof(int));

      *mid = mid1 + (mid2 - (start + count));
    }
  }
  else {
    *mid = start;
    if (real_lists == 2) {
      if (ind_indices == 0) {
        if (b == 0) count = type_size * indx[0];
        else        count = b[0];
      }
      else {
        if (b == 0) count =type_size * (indx[ind_indices] - indx[ind_indices-1]);
        else        count = b[indx[ind_indices-1]];
      }

      rest = end - (start + count) + 1;

      if (the_first == 0)
        *mid = start+count;
      else {
        *mid = start + rest;
        move_ints((int *) &(a[start]), (int *) &(a[start+count]),
        count / sizeof(int), rest / sizeof(int));
      }
    }

    else if (real_lists == 1) {
      if (the_first == 1) *mid = start;
      else                *mid = end + 1;
    }
  }

  if (start > pre_mid) {
    if (*mid == start) {
      *mid = pre_mid;
    }
    else {
      move_ints((int *) &(a[pre_mid]), (int *) &(a[start]),
      (start-pre_mid) / sizeof(int), (*mid-start) / sizeof(int));
      *mid = pre_mid + *mid - start;
    }
  }

} /* AZ_sort_ints */

/******************************************************************************/
/******************************************************************************/
/******************************************************************************/

void AZ_direct_sort(int b[], int indx[], char buffer[], char a[], int *start,
                    int buf_len, int *ind_indices, int *the_first,
                    int *real_lists, int *firstmid)

/*******************************************************************************

  Sort as many lists as we can using the buffer. In particular, we go through
  the lists (starting with indx[0]). If a list belongs to the first subsequence
  then we move it to its proper location. If a list belongs to the second
  subsequence we copy it to the buffer. We continue doing this until there is
  not enough room in the buffer. At this point, we copy the buffer contents back
  to the data array starting immediately after the last element put in its
  proper location of the first subsequence.

  Author:          Ray S. Tuminaro, SNL, 1422
  =======

  Return code:     void
  ============

  Parameter list:
  ===============

  b:               Contains lengths of merged lists (see AZ_change_it()).

  indx:            Indicates the number of sublists in this merged list.
                   indx[i] - indx[i-1]    i > 0
                   indx[i]                i = 0

  buffer:          Workspace array.

  a:               Data array containing lists to be sorted.

  start:           On input, starting location in a[] of information to be
                   sorted. On output, start indicates the location of the first
                   list in a[] which was not sorted or copied into the buffer.

  buf_len:         Length of workspace array (buffer[]).

  ind_indices:       Index of the first merged list not to be sorted.
                   On input, first list to be sorted with buffer.
                   On output, first list that was not sorted with buffer.

  the_first:       On input, the_first = 0   ==> first merged list belongs
                                                 to first subsequence
                             the_first = 1   ==> first merged list belongs
                                                 to second subsequence

  real_lists:      On input, number of merged lists to be sorted.
                   On output, number of merged lists remaining to be sorted.

  firstmid:        On output, pointer to first element in a[] that was stored
                   in the buffer (hence belongs to the second subsequence).

*******************************************************************************/

{

  /* local variables */

  int   buffer_full = 0, cur, i, si, flag;
  char *ptr1, *ptr2;
  unsigned int buf_end = 0, thelength;

  /**************************** execution begins ******************************/

  cur = *start;
  i   = *ind_indices;
  si  = *start;

  if (*the_first == 0) flag = 0;
  else                 flag = 1;

  while (buffer_full == 0) {
    if (flag == 1) {

      /* must move this to the buffer */

      if (i ==0) {
        if (b == 0) thelength = type_size * indx[0];
        else        thelength = b[0];
      }
      else {
        if (b == 0) thelength = type_size * (indx[i] - indx[i-1]);
        else        thelength = b[indx[i-1]];
      }

      if  ( (int) (buf_end+thelength) > buf_len )
        buffer_full = 1;
      else {
        ptr1 = (char *) &(buffer[buf_end]);
        ptr2 = (char *) &(a[si]);

        memcpy(ptr1, ptr2, thelength);
        buf_end += thelength;
        si      += thelength;
      }
      flag = 0;
    }
    else {

      /* move this stuff to the front */

      if (i ==0) {
        if (b == 0) thelength = type_size * indx[0];
        else        thelength = b[0];
      }
      else {
        if (b == 0) thelength = type_size * (indx[i] - indx[i-1]);
        else        thelength = b[indx[i-1]];
      }

      ptr1 = (char *) &(a[cur]);
      ptr2 = (char *) &(a[si]);
      memcpy(ptr1, ptr2, thelength);

      cur += thelength;
      si  += thelength;

      flag = 1;
    }

    i++;
    if (buffer_full == 0) {
      if ((i- (*ind_indices)) == (*real_lists) ) {
        buffer_full = 1;
        i++;
      }
    }
  }

  i--;

  /* empty the buffer back into the list */

  *firstmid = cur;
  ptr1      = (char *) &(a[cur]);
  memcpy(ptr1, buffer, buf_end);
  cur += buf_end;

  *real_lists = *real_lists - (i - *ind_indices);
  *start      = cur;
  *the_first  = 1;
  *ind_indices  = i;

} /* AZ_direct_sort */