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   int[] lostk;
  88   int[] histk;
  89
  90
  91   public Sort() {
  92     lostk= new int[30];
  93     histk= new int[30];
  94   }
  95
  96   /* =============================================================================
  97    * swap
  98    * =============================================================================
  99    */
 100   public static void swap (byte[] base, int a, int b, int width) {
 101     if (a != b ) {
 102       while(width--) {
 103         byte tmp = base[a];
 104         base[a++] = base[b];
 105         base[b++] = tmp;
 106       }
 107     }
 108   }
 109
 110
 111   /* =============================================================================
 112    * shortsort
 113    * =============================================================================
 114    */
 115
 116   public static void shortsort(byte[] base,
 117       int lo,
 118       int hi,
 119       int width,
 120       int n,
 121       int offset)
 122   {
 123     while(hi > lo) {
 124       int max = lo;
 125       for(int p = (lo + width); p <= hi; p += width) {
 126         if(cmp(base, p, max, n, offset) > 0) {
 127           max = p;
 128         }
 129       }
 130       swap(base, max, hi, width);
 131       hi -= width;
 132     }
 133   }
 134
 135   /* =============================================================================
 136    * sort
 137    * =============================================================================
 138    */
 139   public void sort (byte[] base,
 140                     int start,
 141                     int num,
 142                     int width,
 143                     int n,
 144                     int offset) {
 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=this.lostk;
 155     int[] histk=this.histk;
 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  */