Robust/src/Benchmarks/SingleTM/Bayes/Sort.java

   1 /* =============================================================================
   2  *
   3  * sort.java
   4  *
   5  * =============================================================================
   6  *
   7  * Quick sort
   8  *
   9  * Copyright (C) 2002 Michael Ringgaard. All rights reserved.
  10  *
  11  * Redistribution and use in source and binary forms, with or without
  12  * modification, are permitted provided that the following conditions
  13  * are met:
  14  *
  15  * 1. Redistributions of source code must retain the above copyright
  16  *    notice, this list of conditions and the following disclaimer.
  17  * 2. Redistributions in binary form must reproduce the above copyright
  18  *    notice, this list of conditions and the following disclaimer in the
  19  *    documentation and/or other materials provided with the distribution.
  20  * 3. Neither the name of the project nor the names of its contributors
  21  *    may be used to endorse or promote products derived from this software
  22  *    without specific prior written permission.
  23  *
  24  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  25  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27  * ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
  28  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  29  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  30  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  31  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  32  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  33  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  34  * POSSIBILITY OF  SUCH DAMAGE
  35  *
  36  * =============================================================================
  37  *
  38  * Modifed October 2007 by Chi Cao Minh
  39  * -- Changed signature of comparison function
  40  *
  41  * =============================================================================
  42  *
  43  * For the license of bayes/sort.h and bayes/sort.c, please see the header
  44  * of the files.
  45  *
  46  * ------------------------------------------------------------------------
  47  *
  48  * Unless otherwise noted, the following license applies to STAMP files:
  49  *
  50  * Copyright (c) 2007, Stanford University
  51  * All rights reserved.
  52  *
  53  * Redistribution and use in source and binary forms, with or without
  54  * modification, are permitted provided that the following conditions are
  55  * met:
  56  *
  57  *     * Redistributions of source code must retain the above copyright
  58  *       notice, this list of conditions and the following disclaimer.
  59  *
  60  *     * Redistributions in binary form must reproduce the above copyright
  61  *       notice, this list of conditions and the following disclaimer in
  62  *       the documentation and/or other materials provided with the
  63  *       distribution.
  64  *
  65  *     * Neither the name of Stanford University nor the names of its
  66  *       contributors may be used to endorse or promote products derived
  67  *       from this software without specific prior written permission.
  68  *
  69  * THIS SOFTWARE IS PROVIDED BY STANFORD UNIVERSITY ``AS IS'' AND ANY
  70  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  71  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  72  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE
  73  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  74  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  75  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  76  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  77  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  78  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
  79  * THE POSSIBILITY OF SUCH DAMAGE.
  80  *
  81  * =============================================================================
  82  */
  83
  84 #define CUTOFF 8
  85
  86 public class Sort {
  87
  88   public Sort() {
  89
  90   }
  91
  92   /* =============================================================================
  93    * swap
  94    * =============================================================================
  95    */
  96   public static void
  97     swap (byte[] base, int a, int b, int width)
  98     {
  99       if (a != b ) {
 100         while (width--) {
 101           byte tmp = base[a];
 102           base[a++] = base[b];
 103           base[b++] = tmp;
 104         }
 105       }
 106     }
 107
 108
 109   /* =============================================================================
 110    * shortsort
 111    * =============================================================================
 112    */
 113
 114   public static void shortsort(byte[] base,
 115       int lo,
 116       int hi,
 117       int width,
 118       int n,
 119       int offset)
 120   {
 121     while(hi > lo) {
 122       int max = lo;
 123       for(int p = (lo + width); p <= hi; p += width) {
 124         if(cmp(base, p, max, n, offset) > 0) {
 125           max = p;
 126         }
 127       }
 128       swap(base, max, hi, width);
 129       hi -= width;
 130     }
 131   }
 132
 133   /* =============================================================================
 134    * sort
 135    * =============================================================================
 136    */
 137   public static void
 138     sort (byte[] base,
 139         int start,
 140         int num,
 141         int width,
 142         int n,
 143         int offset)
 144     {
 145       if (num < 2 || width == 0) {
 146         return;
 147       }
 148
 149       /**
 150        * Pointers that keep track of
 151        * where to start looking in
 152        * the base array
 153        **/
 154       int[] lostk= new int[30];
 155       int[] histk= new int[30];
 156
 157       int stkptr = 0;
 158
 159       int lo = start;
 160       int hi = start + (width * (num - 1));
 161
 162       int size = 0;
 163
 164       int pvlo = lo;
 165       int pvhi = hi;
 166       int pvwidth = width;
 167       int pvn = n;
 168       int pvmid;
 169       int pvloguy;
 170       int pvhiguy;
 171       int typeflag;
 172
 173       while(true) {
 174
 175         size = (pvhi - pvlo) / pvwidth + 1;
 176
 177         if (size <= CUTOFF) {
 178
 179           shortsort(base, pvlo, pvhi, pvwidth, pvn, offset);
 180
 181         } else {
 182
 183           pvmid = pvlo + (size / 2) * pvwidth;
 184           swap(base, pvmid, pvlo, pvwidth);
 185
 186           pvloguy = pvlo;
 187           pvhiguy = pvhi + pvwidth;
 188
 189           while(true) {
 190             do {
 191               pvloguy += pvwidth;
 192             } while (pvloguy <= pvhi && cmp(base, pvloguy, pvlo, pvn, offset) <= 0);
 193             do {
 194               pvhiguy -= pvwidth;
 195             } while (pvhiguy > pvlo && cmp(base, pvhiguy, pvlo, pvn, offset) >= 0);
 196             if (pvhiguy < pvloguy) {
 197               break;
 198             }
 199             swap(base, pvloguy, pvhiguy, pvwidth);
 200           }
 201
 202           swap(base, pvlo, pvhiguy, pvwidth);
 203
 204           if ((pvhiguy - 1 - pvlo) >= (pvhi - pvloguy)) {
 205             if (pvlo + pvwidth < pvhiguy) {
 206               lostk[stkptr] = pvlo;
 207               histk[stkptr] = pvhiguy - pvwidth;
 208               ++stkptr;
 209             }
 210
 211             if (pvloguy < pvhi) {
 212               pvlo = pvloguy;
 213               continue;
 214             }
 215           } else {
 216             if (pvloguy < pvhi) {
 217               lostk[stkptr] = pvloguy;
 218               histk[stkptr] = pvhi;
 219               ++stkptr;
 220             }
 221             if (pvlo + pvwidth < pvhiguy) {
 222               pvhi = pvhiguy - pvwidth;
 223               continue;
 224             }
 225           }
 226         }
 227
 228         --stkptr;
 229         if (stkptr >= 0) {
 230           pvlo = lostk[stkptr];
 231           pvhi = histk[stkptr];
 232           continue;
 233         }
 234         break;
 235       }
 236     }
 237
 238   /* =============================================================================
 239    * compareRecord
 240    * =============================================================================
 241    */
 242
 243   public static int
 244     cmp(byte[] base, int p1, int  p2, int n, int offset)
 245     {
 246       int i = n - offset;
 247       int s1 = p1 + offset;
 248       int s2 = p2 + offset;
 249
 250       while (i-- > 0) {
 251         byte u1 = base[s1];
 252         byte u2 = base[s2];
 253         if (u1 != u2) {
 254           return (u1 - u2);
 255         }
 256         s1++;
 257         s2++;
 258       }
 259       return 0;
 260     }
 261 }
 262
 263
 264 /* =============================================================================
 265  *
 266  * End of sort.java
 267  *
 268  * =============================================================================
 269  */