release/src-rt-6.x.4708/cfe/cfe/lib/lib_qsort.c

   1 #include "lib_types.h"
   2 #include "lib_string.h"
   3
   4 #define CHAR_BIT 8
   5 #define MAXSTACK (sizeof(int) * CHAR_BIT)
   6
   7 static void qsexchange(void *a, void *b, size_t size)
   8 {
   9     size_t i;
  10
  11     /******************
  12      *  exchange a,b  *
  13      ******************/
  14
  15     for (i = sizeof(int); i <= size; i += sizeof(int)) {
  16         int t = *((int *)a);
  17         *((int *)a++) = *((int *)b);
  18         *((int *)b++) = t;
  19         }
  20     for (i = i - sizeof(int) + 1; i <= size; i++) {
  21         char t = *((char *)a);
  22         *((char *)a++) = *((char *)b);
  23         *((char *)b++) = t;
  24         }
  25 }
  26
  27 void qsort(void *base, size_t nmemb, size_t size,
  28            int (*compar)(const void *, const void *))
  29 {
  30     void *lbStack[MAXSTACK], *ubStack[MAXSTACK];
  31     int sp;
  32     unsigned int offset;
  33
  34     /********************
  35      *  ANSI-C qsort()  *
  36      ********************/
  37
  38     lbStack[0] = (char *)base;
  39     ubStack[0] = (char *)base + (nmemb-1)*size;
  40     for (sp = 0; sp >= 0; sp--) {
  41         char *lb, *ub, *m;
  42         char *P, *i, *j;
  43
  44         lb = lbStack[sp];
  45         ub = ubStack[sp];
  46
  47         while (lb < ub) {
  48
  49             /* select pivot and exchange with 1st element */
  50             offset = (ub - lb) >> 1;
  51             P = lb + offset - offset % size;
  52             qsexchange (lb, P, size);
  53
  54             /* partition into two segments */
  55             i = lb + size;
  56             j = ub;
  57             while (1) {
  58                 while (i < j && compar(lb, i) > 0) i += size;
  59                 while (j >= i && compar(j, lb) > 0) j -= size;
  60                 if (i >= j) break;
  61                 qsexchange (i, j, size);
  62                 j -= size;
  63                 i += size;
  64                 }
  65
  66             /* pivot belongs in A[j] */
  67             qsexchange (lb, j, size);
  68             m = j;
  69
  70             /* keep processing smallest segment, and stack largest */
  71             if (m - lb <= ub - m) {
  72                 if (m + size < ub) {
  73                     lbStack[sp] = m + size;
  74                     ubStack[sp++] = ub;
  75                     }
  76                 ub = m - size;
  77                 }
  78             else {
  79                 if (m - size > lb) {
  80                     lbStack[sp] = lb;
  81                     ubStack[sp++] = m - size;
  82                     }
  83                 lb = m + size;
  84                 }
  85             }
  86         }
  87 }