vppinfra: finish deprecating qsort.c

Minor change to vec_sort_with_function(...): don't depend on the qsort
implementation to deal with null, zero-long, or 1-long vectors

Type: fix

Signed-off-by: Dave Barach <dave@barachs.net>
Change-Id: I7bd7b0421673d2a025363089562aa7c6266fba66
(cherry picked from commit f593b5792031b3797cdcdfd3fbb33ac4de8c9a5d)

2 files changed, 7 insertions, 272 deletions

diff --git a/src/vppinfra/qsort.c b/src/vppinfra/qsort.c
deleted file mode 100644
index 145ae40fe91..00000000000
--- a/src/vppinfra/qsort.c
+++ /dev/null
@@ -1,269 +0,0 @@
-/*
- * Copyright (c) 2015 Cisco and/or its affiliates.
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at:
- *
- *     http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-/*
- * Imported into CLIB by Eliot Dresselhaus from:
- *
- *  This file is part of
- *	MakeIndex - A formatter and format independent index processor
- *
- *  This file is public domain software donated by
- *  Nelson Beebe (beebe@science.utah.edu).
- *
- *  modifications copyright (c) 2003 Cisco Systems, Inc.
- */
-
-#include <vppinfra/clib.h>
-
-/*
- * qsort.c: Our own version of the system qsort routine which is faster by an
- * average of 25%, with lows and highs of 10% and 50%. The THRESHold below is
- * the insertion sort threshold, and has been adjusted for records of size 48
- * bytes. The MTHREShold is where we stop finding a better median.
- */
-
-#define THRESH  4		/* threshold for insertion */
-#define MTHRESH 6		/* threshold for median */
-
-typedef struct
-{
-  word qsz;			/* size of each record */
-  word thresh;			/* THRESHold in chars */
-  word mthresh;			/* MTHRESHold in chars */
-  int (*qcmp) (const void *, const void *);	/* the comparison routine */
-} qst_t;
-
-static void qst (qst_t * q, char *base, char *max);
-
-/*
- * qqsort: First, set up some global parameters for qst to share.
- * Then, quicksort with qst(), and then a cleanup insertion sort ourselves.
- * Sound simple?  It's not...
- */
-
-void
-qsort (void *base, uword n, uword size,
-       int (*compar) (const void *, const void *))
-{
-  char *i;
-  char *j;
-  char *lo;
-  char *hi;
-  char *min;
-  char c;
-  char *max;
-  qst_t _q, *q = &_q;
-
-  if (n <= 1)
-    return;
-
-  q->qsz = size;
-  q->qcmp = compar;
-  q->thresh = q->qsz * THRESH;
-  q->mthresh = q->qsz * MTHRESH;
-  max = base + n * q->qsz;
-  if (n >= THRESH)
-    {
-      qst (q, base, max);
-      hi = base + q->thresh;
-    }
-  else
-    {
-      hi = max;
-    }
-  /*
-   * First put smallest element, which must be in the first THRESH, in the
-   * first position as a sentinel.  This is done just by searching the
-   * first THRESH elements (or the first n if n < THRESH), finding the min,
-   * and swapping it into the first position.
-   */
-  for (j = lo = base; (lo += q->qsz) < hi;)
-    {
-      if ((*compar) (j, lo) > 0)
-	j = lo;
-    }
-  if (j != base)
-    {				/* swap j into place */
-      for (i = base, hi = base + q->qsz; i < hi;)
-	{
-	  c = *j;
-	  *j++ = *i;
-	  *i++ = c;
-	}
-    }
-  /*
-   * With our sentinel in place, we now run the following hyper-fast
-   * insertion sort. For each remaining element, min, from [1] to [n-1],
-   * set hi to the index of the element AFTER which this one goes. Then, do
-   * the standard insertion sort shift on a character at a time basis for
-   * each element in the frob.
-   */
-  for (min = base; (hi = min += q->qsz) < max;)
-    {
-      while ((*q->qcmp) (hi -= q->qsz, min) > 0);
-      if ((hi += q->qsz) != min)
-	{
-	  for (lo = min + q->qsz; --lo >= min;)
-	    {
-	      c = *lo;
-	      for (i = j = lo; (j -= q->qsz) >= hi; i = j)
-		*i = *j;
-	      *i = c;
-	    }
-	}
-    }
-}
-
-
-
-/*
- * qst: Do a quicksort.  First, find the median element, and put that one in
- * the first place as the discriminator.  (This "median" is just the median
- * of the first, last and middle elements).  (Using this median instead of
- * the first element is a big win). Then, the usual partitioning/swapping,
- * followed by moving the discriminator into the right place.  Then, figure
- * out the sizes of the two partitions, do the smaller one recursively and the
- * larger one via a repeat of this code.  Stopping when there are less than
- * THRESH elements in a partition and cleaning up with an insertion sort (in
- * our caller) is a huge win. All data swaps are done in-line, which is
- * space-losing but time-saving. (And there are only three places where this
- * is done).
- */
-
-static void
-qst (qst_t * q, char *base, char *max)
-{
-  char *i;
-  char *j;
-  char *jj;
-  char *mid;
-  int ii;
-  char c;
-  char *tmp;
-  int lo;
-  int hi;
-  int qsz = q->qsz;
-
-  lo = (int) (max - base);	/* number of elements as chars */
-  do
-    {
-      /*
-       * At the top here, lo is the number of characters of elements in the
-       * current partition.  (Which should be max - base). Find the median
-       * of the first, last, and middle element and make that the middle
-       * element.  Set j to largest of first and middle.  If max is larger
-       * than that guy, then it's that guy, else compare max with loser of
-       * first and take larger.  Things are set up to prefer the middle,
-       * then the first in case of ties.
-       */
-      mid = i = base + qsz * ((unsigned) (lo / qsz) >> 1);
-      if (lo >= q->mthresh)
-	{
-	  j = ((*q->qcmp) ((jj = base), i) > 0 ? jj : i);
-	  if ((*q->qcmp) (j, (tmp = max - qsz)) > 0)
-	    {
-	      /* switch to first loser */
-	      j = (j == jj ? i : jj);
-	      if ((*q->qcmp) (j, tmp) < 0)
-		j = tmp;
-	    }
-	  if (j != i)
-	    {
-	      ii = qsz;
-	      do
-		{
-		  c = *i;
-		  *i++ = *j;
-		  *j++ = c;
-		}
-	      while (--ii);
-	    }
-	}
-      /* Semi-standard quicksort partitioning/swapping */
-      for (i = base, j = max - qsz;;)
-	{
-	  while (i < mid && (*q->qcmp) (i, mid) <= 0)
-	    i += qsz;
-	  while (j > mid)
-	    {
-	      if ((*q->qcmp) (mid, j) <= 0)
-		{
-		  j -= qsz;
-		  continue;
-		}
-	      tmp = i + qsz;	/* value of i after swap */
-	      if (i == mid)
-		{		/* j <-> mid, new mid is j */
-		  mid = jj = j;
-		}
-	      else
-		{		/* i <-> j */
-		  jj = j;
-		  j -= qsz;
-		}
-	      goto swap;
-	    }
-	  if (i == mid)
-	    {
-	      break;
-	    }
-	  else
-	    {			/* i <-> mid, new mid is i */
-	      jj = mid;
-	      tmp = mid = i;	/* value of i after swap */
-	      j -= qsz;
-	    }
-	swap:
-	  ii = qsz;
-	  do
-	    {
-	      c = *i;
-	      *i++ = *jj;
-	      *jj++ = c;
-	    }
-	  while (--ii);
-	  i = tmp;
-	}
-      /*
-       * Look at sizes of the two partitions, do the smaller one first by
-       * recursion, then do the larger one by making sure lo is its size,
-       * base and max are update correctly, and branching back. But only
-       * repeat (recursively or by branching) if the partition is of at
-       * least size THRESH.
-       */
-      i = (j = mid) + qsz;
-      if ((lo = (int) (j - base)) <= (hi = (int) (max - i)))
-	{
-	  if (lo >= q->thresh)
-	    qst (q, base, j);
-	  base = i;
-	  lo = hi;
-	}
-      else
-	{
-	  if (hi >= q->thresh)
-	    qst (q, i, max);
-	  max = j;
-	}
-    }
-  while (lo >= q->thresh);
-}
-
-/*
- * fd.io coding-style-patch-verification: ON
- *
- * Local Variables:
- * eval: (c-set-style "gnu")
- * End:
- */
diff --git a/src/vppinfra/vec.h b/src/vppinfra/vec.h
index 461c0de3347..da7d0896109 100644
--- a/src/vppinfra/vec.h
+++ b/src/vppinfra/vec.h
@@ -974,12 +974,16 @@ do {						\
 
 /** \brief Sort a vector using the supplied element comparison function
 
+    Does not depend on the underlying implementation to deal correctly
+    with null, zero-long, or 1-long vectors
+
     @param vec vector to sort
     @param f comparison function
 */
-#define vec_sort_with_function(vec,f)				\
-do {								\
-  qsort (vec, vec_len (vec), sizeof (vec[0]), (void *) (f));	\
+#define vec_sort_with_function(vec,f)                           \
+do {                                                            \
+  if (vec_len (vec) > 1)                                        \
+    qsort (vec, vec_len (vec), sizeof (vec[0]), (void *) (f));  \
 } while (0)
 
 /** \brief Make a vector containing a NULL terminated c-string.