src/gromacs/gmxlib/gmx_sort.c

   1 /* -*- mode: c; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4; c-file-style: "stroustrup"; -*-
   2  *
   3  *
   4  * This file is part of Gromacs        Copyright (c) 1991-2010
   5  * David van der Spoel, Erik Lindahl, Berk Hess, University of Groningen.
   6  *
   7  * This program is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU General Public License
   9  * as published by the Free Software Foundation; either version 2
  10  * of the License, or (at your option) any later version.
  11  *
  12  * To help us fund GROMACS development, we humbly ask that you cite
  13  * the research papers on the package. Check out http://www.gromacs.org
  14  *
  15  * And Hey:
  16  * Gnomes, ROck Monsters And Chili Sauce
  17  */
  18
  19 #ifdef HAVE_CONFIG_H
  20 #include <config.h>
  21 #endif
  22
  23 #include <stdlib.h>
  24 #include "gmx_sort.h"
  25
  26
  27 static void
  28 qsort_swapfunc(void *        a,
  29                void *        b,
  30                size_t        n,
  31                int           swaptype)
  32 {
  33     int  *  ia;
  34     int  *  ib;
  35     int     itmp;
  36
  37     char *  ca;
  38     char *  cb;
  39     char    ctmp;
  40
  41     if (swaptype <= 1)
  42     {
  43         ia = (int *)a;
  44         ib = (int *)b;
  45         for (; n > 0; ia += 1, ib += 1, n -= sizeof(int))
  46         {
  47             itmp      = *ia;
  48             *ia       = *ib;
  49             *ib       = itmp;
  50         }
  51     }
  52     else
  53     {
  54         ca = (char *)a;
  55         cb = (char *)b;
  56         for (; n > 0; ca += 1, cb += 1, n -= 1)
  57         {
  58             ctmp       = *ca;
  59             *ca        = *cb;
  60             *cb        = ctmp;
  61         }
  62     }
  63 }
  64
  65
  66 static void *
  67 qsort_med3(void *        a,
  68            void *        b,
  69            void *        c,
  70            int          (*compar) (const void *a, const void *b))
  71 {
  72     if (compar(a, b) < 0)
  73     {
  74         if (compar(b, c) < 0)
  75         {
  76             return b;
  77         }
  78         else if (compar(a, c) < 0)
  79         {
  80             return c;
  81         }
  82         else
  83         {
  84             return a;
  85         }
  86     }
  87     else
  88     {
  89         if (compar(b, c) > 0)
  90         {
  91             return b;
  92         }
  93         else if (compar(a, c) > 0)
  94         {
  95             return c;
  96         }
  97         else
  98         {
  99             return a;
 100         }
 101     }
 102 }
 103
 104
 105 void
 106 gmx_qsort(void *           base,
 107           size_t           nmemb,
 108           size_t           size,
 109           int            (*compar)(const void *, const void *))
 110 {
 111 #define QSORT_EXCH(a, b, t) (t = a, a = b, b = t)
 112 #define QSORT_SWAP(a, b) swaptype != 0 ? qsort_swapfunc(a, b, size, swaptype) : \
 113     (void)QSORT_EXCH(*(int *)(a), *(int *)(b), t)
 114
 115     char  *pa, *pb, *pc, *pd, *pl, *pm, *pn, *pv, *cbase;
 116     int    r, swaptype;
 117     int    t, v;
 118     size_t s, st;
 119
 120     cbase = (char *)base;
 121
 122     swaptype = (size_t)(cbase - (char *)0) % sizeof(int) || size % sizeof(int) ? 2 : size == sizeof(int) ? 0 : 1;
 123
 124     if (nmemb < 7)
 125     {
 126         /* Insertion sort on smallest arrays */
 127         for (pm = cbase + size; pm < cbase + nmemb*size; pm += size)
 128         {
 129             for (pl = pm; (pl > cbase) && compar((void *)(pl-size), (void *) pl) > 0; pl -= size)
 130             {
 131                 QSORT_SWAP(pl, pl-size);
 132             }
 133         }
 134         return;
 135     }
 136
 137     /* Small arrays, middle element */
 138     pm = cbase + (nmemb/2)*size;
 139
 140     if (nmemb > 7)
 141     {
 142         pl = cbase;
 143         pn = cbase + (nmemb-1)*size;
 144         if (nmemb > 40)
 145         {
 146             /* Big arrays, pseudomedian of 9 */
 147             s  = (nmemb/8)*size;
 148             pl = (char *)qsort_med3((void *)pl, (void *)((size_t)pl+s), (void *)((size_t)pl+2*s), compar);
 149             pm = (char *)qsort_med3((void *)((size_t)pm-s), (void *)pm, (void *)((size_t)pm+s), compar);
 150             pn = (char *)qsort_med3((void *)((size_t)pn-2*s), (void *)((size_t)pn-s), (void *)pn, compar);
 151         }
 152         /* Mid-size, med of 3 */
 153         pm = (char *)qsort_med3((void *)pl, (void *)pm, (void *)pn, compar);
 154     }
 155
 156     /* pv points to partition value */
 157     if (swaptype != 0)
 158     {
 159         pv = cbase;
 160         QSORT_SWAP(pv, pm);
 161     }
 162     else
 163     {
 164         pv = (char*)(void*)&v;
 165         v  = *(int *)pm;
 166     }
 167
 168     pa = pb = cbase;
 169     pc = pd = cbase + (nmemb-1)*size;
 170
 171     for (;; )
 172     {
 173         while (pb <= pc && (r = compar((void *)pb, (void *) pv)) <= 0)
 174         {
 175             if (r == 0)
 176             {
 177                 QSORT_SWAP(pa, pb);
 178                 pa += size;
 179             }
 180             pb += size;
 181         }
 182         while (pc >= pb && (r = compar((void *)pc, (void *) pv)) >= 0)
 183         {
 184             if (r == 0)
 185             {
 186                 QSORT_SWAP(pc, pd);
 187                 pd -= size;
 188             }
 189             pc -= size;
 190         }
 191         if (pb > pc)
 192         {
 193             break;
 194         }
 195         QSORT_SWAP(pb, pc);
 196         pb += size;
 197         pc -= size;
 198     }
 199     pn = cbase + nmemb*size;
 200
 201     s  = pa-cbase;
 202     st = pb-pa;
 203     if (st < s)
 204     {
 205         s = st;
 206     }
 207
 208     if (s > 0)
 209     {
 210         qsort_swapfunc(cbase, pb-s, s, swaptype);
 211     }
 212
 213     s  = pd-pc;
 214     st = pn-pd-size;
 215     if (st < s)
 216     {
 217         s = st;
 218     }
 219
 220     if (s > 0)
 221     {
 222         qsort_swapfunc(pb, pn-s, s, swaptype);
 223     }
 224
 225     if ((s = pb-pa) > size)
 226     {
 227         gmx_qsort(cbase, s/size, size, compar);
 228     }
 229
 230     if ((s = pd-pc) > size)
 231     {
 232         gmx_qsort(pn-s, s/size, size, compar);
 233     }
 234
 235 #undef QSORT_EXCH
 236 #undef QSORT_SWAP
 237
 238     return;
 239 }