home *** CD-ROM | disk | FTP | other *** search
/ Tools / WinSN5.0Ver.iso / NETSCAP.50 / WIN1998.ZIP / ns / lib / xp / xp_qsort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-04-08  |  5.6 KB  |  196 lines
  1. /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
  2.  
  3. /*-
  4.  * Copyright (c) 1992, 1993
  5.  *    The Regents of the University of California.  All rights reserved.
  6.  *
  7.  * Redistribution and use in source and binary forms, with or without
  8.  * modification, are permitted provided that the following conditions
  9.  * are met:
  10.  * 1. Redistributions of source code must retain the above copyright
  11.  *    notice, this list of conditions and the following disclaimer.
  12.  * 2. Redistributions in binary form must reproduce the above copyright
  13.  *    notice, this list of conditions and the following disclaimer in the
  14.  *    documentation and/or other materials provided with the distribution.
  15.  * 3. All advertising materials mentioning features or use of this software
  16.  *    must display the following acknowledgement:
  17.  *    This product includes software developed by the University of
  18.  *    California, Berkeley and its contributors.
  19.  * 4. Neither the name of the University nor the names of its contributors
  20.  *    may be used to endorse or promote products derived from this software
  21.  *    without specific prior written permission.
  22.  *
  23.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  24.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  25.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  26.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  27.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  28.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  29.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  30.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  31.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  32.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  33.  * SUCH DAMAGE.
  34.  */
  35.  
  36. /* We need this because Solaris' version of qsort is broken and
  37.  * causes array bounds reads.
  38.  */
  39. #if defined(SOLARIS) || defined(XP_MAC)
  40.  
  41. #if defined(LIBC_SCCS) && !defined(lint)
  42. #if 0
  43. static char sccsid[] = "@(#)qsort.c    8.1 (Berkeley) 6/4/93";
  44. #endif
  45. static const char rcsid[] =
  46.     "$Id: xp_qsort.c,v 3.2 1998/04/07 23:30:24 slamm Exp $";
  47. #endif /* LIBC_SCCS and not lint */
  48.  
  49. #include <stdlib.h>
  50.  
  51. #if !defined(DEBUG) && (defined(__cplusplus) || defined(__gcc))
  52. # ifndef INLINE
  53. #  define INLINE inline
  54. # endif
  55. #else
  56. # define INLINE
  57. #endif
  58.  
  59. typedef int         cmp_t(const void *, const void *);
  60. static INLINE char    *med3(char *, char *, char *, cmp_t *);
  61. static INLINE void    swapfunc(char *, char *, int, int);
  62.  
  63. #define min(a, b)    (a) < (b) ? a : b
  64.  
  65. /*
  66.  * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
  67.  */
  68. #define swapcode(TYPE, parmi, parmj, n) {         \
  69.     long i = (n) / sizeof (TYPE);             \
  70.     register TYPE *pi = (TYPE *) (parmi);         \
  71.     register TYPE *pj = (TYPE *) (parmj);         \
  72.     do {                         \
  73.         register TYPE    t = *pi;        \
  74.         *pi++ = *pj;                \
  75.         *pj++ = t;                \
  76.         } while (--i > 0);                \
  77. }
  78.  
  79. #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
  80.     es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
  81.  
  82. static INLINE void
  83. swapfunc(a, b, n, swaptype)
  84.     char *a, *b;
  85.     int n, swaptype;
  86. {
  87.     if(swaptype <= 1)
  88.         swapcode(long, a, b, n)
  89.     else
  90.         swapcode(char, a, b, n)
  91. }
  92.  
  93. #define swap(a, b)                    \
  94.     if (swaptype == 0) {                \
  95.         long t = *(long *)(a);            \
  96.         *(long *)(a) = *(long *)(b);        \
  97.         *(long *)(b) = t;            \
  98.     } else                        \
  99.         swapfunc(a, b, es, swaptype)
  100.  
  101. #define vecswap(a, b, n)     if ((n) > 0) swapfunc(a, b, n, swaptype)
  102.  
  103. static INLINE char *
  104. med3(a, b, c, cmp)
  105.     char *a, *b, *c;
  106.     cmp_t *cmp;
  107. {
  108.     return cmp(a, b) < 0 ?
  109.            (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a ))
  110.               :(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c ));
  111. }
  112.  
  113. void XP_QSORT (
  114.     void *a,
  115.     unsigned n,
  116.     unsigned es,
  117.     cmp_t *cmp
  118.     )
  119. {
  120.     char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
  121.     int d, r, swaptype, swap_cnt;
  122.  
  123. loop:    SWAPINIT(a, es);
  124.     swap_cnt = 0;
  125.     if (n < 7) {
  126.         for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
  127.             for (pl = pm; pl > (char *)a && cmp(pl - es, pl) > 0;
  128.                  pl -= es)
  129.                 swap(pl, pl - es);
  130.         return;
  131.     }
  132.     pm = (char *)a + (n / 2) * es;
  133.     if (n > 7) {
  134.         pl = a;
  135.         pn = (char *)a + (n - 1) * es;
  136.         if (n > 40) {
  137.             d = (n / 8) * es;
  138.             pl = med3(pl, pl + d, pl + 2 * d, cmp);
  139.             pm = med3(pm - d, pm, pm + d, cmp);
  140.             pn = med3(pn - 2 * d, pn - d, pn, cmp);
  141.         }
  142.         pm = med3(pl, pm, pn, cmp);
  143.     }
  144.     swap(a, pm);
  145.     pa = pb = (char *)a + es;
  146.  
  147.     pc = pd = (char *)a + (n - 1) * es;
  148.     for (;;) {
  149.         while (pb <= pc && (r = cmp(pb, a)) <= 0) {
  150.             if (r == 0) {
  151.                 swap_cnt = 1;
  152.                 swap(pa, pb);
  153.                 pa += es;
  154.             }
  155.             pb += es;
  156.         }
  157.         while (pb <= pc && (r = cmp(pc, a)) >= 0) {
  158.             if (r == 0) {
  159.                 swap_cnt = 1;
  160.                 swap(pc, pd);
  161.                 pd -= es;
  162.             }
  163.             pc -= es;
  164.         }
  165.         if (pb > pc)
  166.             break;
  167.         swap(pb, pc);
  168.         swap_cnt = 1;
  169.         pb += es;
  170.         pc -= es;
  171.     }
  172.     if (swap_cnt == 0) {  /* Switch to insertion sort */
  173.         for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
  174.             for (pl = pm; pl > (char *)a && cmp(pl - es, pl) > 0;
  175.                  pl -= es)
  176.                 swap(pl, pl - es);
  177.         return;
  178.     }
  179.  
  180.     pn = (char *)a + n * es;
  181.     r = min(pa - (char *)a, pb - pa);
  182.     vecswap(a, pb - r, r);
  183.     r = min(pd - pc, pn - pd - es);
  184.     vecswap(pb, pn - r, r);
  185.     if ((r = pb - pa) > es)
  186.         XP_QSORT(a, r / es, es, cmp);
  187.     if ((r = pd - pc) > es) {
  188.         /* Iterate rather than recurse to save stack space */
  189.         a = pn - r;
  190.         n = r / es;
  191.         goto loop;
  192.     }
  193. /*        qsort(pn - r, r / es, es, cmp);*/
  194. }
  195. #endif /* SOLARIS or XP_MAC */
  196.