vppinfra/vppinfra/qsort.c

   1 /*
   2  * Copyright (c) 2015 Cisco and/or its affiliates.
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14  */
  15 /*
  16  * Imported into CLIB by Eliot Dresselhaus from:
  17  *
  18  *  This file is part of
  19  *      MakeIndex - A formatter and format independent index processor
  20  *
  21  *  This file is public domain software donated by
  22  *  Nelson Beebe (beebe@science.utah.edu).
  23  *
  24  *  modifications copyright (c) 2003 Cisco Systems, Inc.
  25  */
  26
  27 #include <vppinfra/clib.h>
  28
  29 /*
  30  * qsort.c: Our own version of the system qsort routine which is faster by an
  31  * average of 25%, with lows and highs of 10% and 50%. The THRESHold below is
  32  * the insertion sort threshold, and has been adjusted for records of size 48
  33  * bytes. The MTHREShold is where we stop finding a better median.
  34  */
  35
  36 #define THRESH  4                      /* threshold for insertion */
  37 #define MTHRESH 6                      /* threshold for median */
  38
  39 typedef struct {
  40   word qsz;                     /* size of each record */
  41   word thresh;                  /* THRESHold in chars */
  42   word mthresh;                 /* MTHRESHold in chars */
  43   int (*qcmp) (const void *, const void *); /* the comparison routine */
  44 } qst_t;
  45
  46 static void qst (qst_t * q, char * base, char *max);
  47
  48 /*
  49  * qqsort: First, set up some global parameters for qst to share.
  50  * Then, quicksort with qst(), and then a cleanup insertion sort ourselves.
  51  * Sound simple?  It's not...
  52  */
  53
  54 void
  55 qsort (void * base, uword n, uword size,
  56        int (*compar) (const void *, const void *))
  57 {
  58   char *i;
  59   char *j;
  60   char *lo;
  61   char *hi;
  62   char *min;
  63   char c;
  64   char *max;
  65   qst_t _q, * q = &_q;
  66
  67   if (n <= 1)
  68     return;
  69
  70   q->qsz = size;
  71   q->qcmp = compar;
  72   q->thresh = q->qsz * THRESH;
  73   q->mthresh = q->qsz * MTHRESH;
  74   max = base + n * q->qsz;
  75   if (n >= THRESH) {
  76     qst(q, base, max);
  77     hi = base + q->thresh;
  78   } else {
  79     hi = max;
  80   }
  81   /*
  82    * First put smallest element, which must be in the first THRESH, in the
  83    * first position as a sentinel.  This is done just by searching the
  84    * first THRESH elements (or the first n if n < THRESH), finding the min,
  85    * and swapping it into the first position.
  86    */
  87   for (j = lo = base; (lo += q->qsz) < hi;) {
  88     if ((*compar) (j, lo) > 0)
  89       j = lo;
  90   }
  91   if (j != base) {                     /* swap j into place */
  92     for (i = base, hi = base + q->qsz; i < hi;) {
  93       c = *j;
  94       *j++ = *i;
  95       *i++ = c;
  96     }
  97   }
  98   /*
  99    * With our sentinel in place, we now run the following hyper-fast
 100    * insertion sort. For each remaining element, min, from [1] to [n-1],
 101    * set hi to the index of the element AFTER which this one goes. Then, do
 102    * the standard insertion sort shift on a character at a time basis for
 103    * each element in the frob.
 104    */
 105   for (min = base; (hi = min += q->qsz) < max;) {
 106     while ((*q->qcmp) (hi -= q->qsz, min) > 0);
 107     if ((hi += q->qsz) != min) {
 108       for (lo = min + q->qsz; --lo >= min;) {
 109         c = *lo;
 110         for (i = j = lo; (j -= q->qsz) >= hi; i = j)
 111           *i = *j;
 112         *i = c;
 113       }
 114     }
 115   }
 116 }
 117
 118
 119
 120 /*
 121  * qst: Do a quicksort.  First, find the median element, and put that one in
 122  * the first place as the discriminator.  (This "median" is just the median
 123  * of the first, last and middle elements).  (Using this median instead of
 124  * the first element is a big win). Then, the usual partitioning/swapping,
 125  * followed by moving the discriminator into the right place.  Then, figure
 126  * out the sizes of the two partions, do the smaller one recursively and the
 127  * larger one via a repeat of this code.  Stopping when there are less than
 128  * THRESH elements in a partition and cleaning up with an insertion sort (in
 129  * our caller) is a huge win. All data swaps are done in-line, which is
 130  * space-losing but time-saving. (And there are only three places where this
 131  * is done).
 132  */
 133
 134 static void
 135 qst(qst_t *q, char *base, char *max)
 136 {
 137   char *i;
 138   char *j;
 139   char *jj;
 140   char *mid;
 141   int ii;
 142   char c;
 143   char   *tmp;
 144   int     lo;
 145   int     hi;
 146   int qsz = q->qsz;
 147
 148   lo = (int)(max - base);               /* number of elements as chars */
 149   do {
 150     /*
 151      * At the top here, lo is the number of characters of elements in the
 152      * current partition.  (Which should be max - base). Find the median
 153      * of the first, last, and middle element and make that the middle
 154      * element.  Set j to largest of first and middle.  If max is larger
 155      * than that guy, then it's that guy, else compare max with loser of
 156      * first and take larger.  Things are set up to prefer the middle,
 157      * then the first in case of ties.
 158      */
 159     mid = i = base + qsz * ((unsigned) (lo / qsz) >> 1);
 160     if (lo >= q->mthresh) {
 161       j = ((*q->qcmp) ((jj = base), i) > 0 ? jj : i);
 162       if ((*q->qcmp) (j, (tmp = max - qsz)) > 0) {
 163         /* switch to first loser */
 164         j = (j == jj ? i : jj);
 165         if ((*q->qcmp) (j, tmp) < 0)
 166           j = tmp;
 167       }
 168       if (j != i) {
 169         ii = qsz;
 170         do {
 171           c = *i;
 172           *i++ = *j;
 173           *j++ = c;
 174         } while (--ii);
 175       }
 176     }
 177     /* Semi-standard quicksort partitioning/swapping */
 178     for (i = base, j = max - qsz;;) {
 179       while (i < mid && (*q->qcmp) (i, mid) <= 0)
 180         i += qsz;
 181       while (j > mid) {
 182         if ((*q->qcmp) (mid, j) <= 0) {
 183           j -= qsz;
 184           continue;
 185         }
 186         tmp = i + qsz;  /* value of i after swap */
 187         if (i == mid) {        /* j <-> mid, new mid is j */
 188           mid = jj = j;
 189         } else {               /* i <-> j */
 190           jj = j;
 191           j -= qsz;
 192         }
 193         goto swap;
 194       }
 195       if (i == mid) {
 196         break;
 197       } else {                 /* i <-> mid, new mid is i */
 198         jj = mid;
 199         tmp = mid = i;         /* value of i after swap */
 200         j -= qsz;
 201       }
 202     swap:
 203       ii = qsz;
 204       do {
 205         c = *i;
 206         *i++ = *jj;
 207         *jj++ = c;
 208       } while (--ii);
 209       i = tmp;
 210     }
 211     /*
 212      * Look at sizes of the two partitions, do the smaller one first by
 213      * recursion, then do the larger one by making sure lo is its size,
 214      * base and max are update correctly, and branching back. But only
 215      * repeat (recursively or by branching) if the partition is of at
 216      * least size THRESH.
 217      */
 218     i = (j = mid) + qsz;
 219     if ((lo = (int)(j - base)) <= (hi = (int)(max - i))) {
 220       if (lo >= q->thresh)
 221         qst(q, base, j);
 222       base = i;
 223       lo = hi;
 224     } else {
 225       if (hi >= q->thresh)
 226         qst(q, i, max);
 227       max = j;
 228     }
 229   } while (lo >= q->thresh);
 230 }