Logo Search packages:      
Sourcecode: yasm version File versions  Download package

int yasm__mergesort ( void *  base,
size_t  nmemb,
size_t  size,
int(*)(const void *, const void *)  compar 
)

Sort an array using merge sort algorithm.

For internal use only.

Parameters:
base base of array
nmemb number of elements in array
size size of each array element
compar element comparison function

Definition at line 106 of file mergesort.c.

References yasm__mergesort(), yasm_xfree, and yasm_xmalloc.

Referenced by yasm__mergesort().

{
#ifdef HAVE_MERGESORT
    return mergesort(base, nmemb, size, cmp);
#else
      size_t i;
      int sense;
      int big, iflag;
      unsigned char *f1, *f2, *t, *b, *tp2, *q, *l1, *l2;
      unsigned char *list2, *list1, *p2, *p, *last, **p1;

      if (size < PSIZE / 2) {       /* Pointers must fit into 2 * size. */
#ifdef EINVAL
            errno = EINVAL;
#endif
            return (-1);
      }

      if (nmemb == 0)
            return (0);

      /*
       * XXX
       * Stupid subtraction for the Cray.
       */
      iflag = 0;
      if (!(size % ISIZE) && !(((char *)base - (char *)0) % ISIZE))
            iflag = 1;

      if ((list2 = yasm_xmalloc(nmemb * size + PSIZE)) == NULL)
            return (-1);

      list1 = base;
      setup(list1, list2, nmemb, size, cmp);
      last = list2 + nmemb * size;
      i = 0;
      big = 0;
      while (*EVAL(list2) != last) {
          l2 = list1;
          p1 = EVAL(list1);
          for (tp2 = p2 = list2; p2 != last; p1 = EVAL(l2)) {
            p2 = *EVAL(p2);
            f1 = l2;
            f2 = l1 = list1 + (p2 - list2);
            if (p2 != last)
                  p2 = *EVAL(p2);
            l2 = list1 + (p2 - list2);
            while (f1 < l1 && f2 < l2) {
                  if ((*cmp)(f1, f2) <= 0) {
                        q = f2;
                        b = f1, t = l1;
                        sense = -1;
                  } else {
                        q = f1;
                        b = f2, t = l2;
                        sense = 0;
                  }
                  if (!big) { /* here i = 0 */
                        while ((b += size) < t && cmp(q, b) >sense)
                              if (++i == 6) {
                                    big = 1;
                                    goto EXPONENTIAL;
                              }
                  } else {
EXPONENTIAL:                  for (i = size; ; i <<= 1)
                              if ((p = (b + i)) >= t) {
                                    if ((p = t - size) > b &&
                                        (*cmp)(q, p) <= sense)
                                          t = p;
                                    else
                                          b = p;
                                    break;
                              } else if ((*cmp)(q, p) <= sense) {
                                    t = p;
                                    if (i == size)
                                          big = 0;
                                    goto FASTCASE;
                              } else
                                    b = p;
                        while (t > b+size) {
                              i = (((t - b) / size) >> 1) * size;
                              if ((*cmp)(q, p = b + i) <= sense)
                                    t = p;
                              else
                                    b = p;
                        }
                        goto COPY;
FASTCASE:               while (i > size)
                              if ((*cmp)(q,
                                    p = b + (i >>= 1)) <= sense)
                                    t = p;
                              else
                                    b = p;
COPY:                   b = t;
                  }
                  i = size;
                  if (q == f1) {
                        if (iflag) {
                              ICOPY_LIST(f2, tp2, b);
                              ICOPY_ELT(f1, tp2, i);
                        } else {
                              CCOPY_LIST(f2, tp2, b);
                              CCOPY_ELT(f1, tp2, i);
                        }
                  } else {
                        if (iflag) {
                              ICOPY_LIST(f1, tp2, b);
                              ICOPY_ELT(f2, tp2, i);
                        } else {
                              CCOPY_LIST(f1, tp2, b);
                              CCOPY_ELT(f2, tp2, i);
                        }
                  }
            }
            if (f2 < l2) {
                  if (iflag)
                        ICOPY_LIST(f2, tp2, l2);
                  else
                        CCOPY_LIST(f2, tp2, l2);
            } else if (f1 < l1) {
                  if (iflag)
                        ICOPY_LIST(f1, tp2, l1);
                  else
                        CCOPY_LIST(f1, tp2, l1);
            }
            *p1 = l2;
          }
          tp2 = list1;  /* swap list1, list2 */
          list1 = list2;
          list2 = tp2;
          last = list2 + nmemb*size;
      }
      if (base == list2) {
            memmove(list2, list1, nmemb*size);
            list2 = list1;
      }
      yasm_xfree(list2);
      return (0);
#endif      /*HAVE_MERGESORT*/
}


Generated by  Doxygen 1.6.0   Back to index