Ads

  1 /******************************************************************************
  2 *
  3 * Copyright (C) 2006, The Gentee Group. All rights reserved. 
  4 * This file is part of the Gentee open source project <http://www.gentee.com>. 
  5 * 
  6 * THIS FILE IS PROVIDED UNDER THE TERMS OF THE GENTEE LICENSE ("AGREEMENT"). 
  7 * ANY USE, REPRODUCTION OR DISTRIBUTION OF THIS FILE CONSTITUTES RECIPIENTS 
  8 * ACCEPTANCE OF THE AGREEMENT.
  9 *
 10 * qsort 20.04.2007 0.0.A.
 11 *
 12 * Author:  
 13 *
 14 ******************************************************************************/
 15 
 16 #include "../common/memory.h"
 17 #include "../vm/vmrun.h"
 18 #include "qsort.h"
 19 
 20 //typedef  void ( STDCALL* swapfunc)( pvoid, pvoid, uint );
 21 
 22 //--------------------------------------------------------------------------
 23 
 24 void  STDCALL quicksort( pvoid base, uint count,
 25                                uint width, cmpfunc func, uint param )
 26 {
 27    pubyte low;
 28    pubyte high;
 29    pubyte middle;
 30    pubyte lowguy;
 31    pubyte highguy;
 32    int   size;
 33    pubyte lowstk[30];
 34    pubyte highstk[30];
 35    int       stkptr;
 36 //   swapfunc  swap = ( swapfunc )( width & 3 ? mem_swap : mem_swapdw );
 37 
 38    if ( count < 2 || width == 0 )
 39       return;
 40 
 41    stkptr = 0;
 42 
 43    low = base;
 44    high = ( pubyte )base + width * ( count-1 );
 45 
 46 recurse:
 47 
 48    size = ( high - low ) / width + 1; 
 49 
 50    middle = low + ( size / 2 ) * width;
 51    mem_swap( middle, low, width);
 52 
 53    lowguy = low;
 54    highguy = high + width;
 55 
 56    for (;;) 
 57    {
 58       do  {
 59          lowguy += width;
 60       } while (lowguy <= high && func(lowguy, low, param) < 0);
 61 
 62       do  {
 63          highguy -= width;
 64       } while (highguy > low && func(highguy, low, param) > 0);
 65 
 66       if ( highguy < lowguy )
 67          break;
 68 
 69       mem_swap( lowguy, highguy, width );
 70    }
 71 
 72    mem_swap( low, highguy, width );
 73 
 74    if ( highguy - 1 - low >= high - lowguy ) 
 75    {
 76       if (low + width < highguy) 
 77       {
 78          lowstk[stkptr] = low;
 79          highstk[stkptr] = highguy - width;
 80          ++stkptr;
 81       }
 82 
 83       if (lowguy < high) 
 84       {
 85          low = lowguy;
 86          goto recurse;
 87       }
 88    }
 89    else 
 90    {
 91       if (lowguy < high) {
 92          lowstk[stkptr] = lowguy;
 93          highstk[stkptr] = high;
 94          ++stkptr;
 95       }
 96 
 97       if (low + width < highguy) {
 98          high = highguy - width;
 99          goto recurse;
100       }
101    }
102 
103    --stkptr;
104    if ( stkptr >= 0 )
105    {
106       low = lowstk[stkptr];
107       high = highstk[stkptr];
108       goto recurse;
109    }
110    else
111       return;
112 }
113 
114 //--------------------------------------------------------------------------
115 
116 int   STDCALL  cmpvm( pvoid left, pvoid right, uint idfunc )
117 {
118    return vm_runtwo( idfunc, ( uint )left, ( uint )right );
119 }
120 
121 //--------------------------------------------------------------------------
122 
123 void  STDCALL sort( pvoid base, uint count, uint size, uint idfunc )
124 {
125    quicksort( base, count, size, cmpvm, idfunc );
126 //   quicksort( base, count, size, cmpstr, 0 );
127 //   qsort( base, count, 16, cmpstrc );
128 
129 }
130 
131 //--------------------------------------------------------------------------
132 
133 int   CALLBACK  cmpsortstr( pvoid left, pvoid right, uint idfunc )
134 {
135    return os_strcmp( ( pvoid )*( puint )left, ( pvoid )*( puint )right );
136 }
137 
138 //--------------------------------------------------------------------------
139 
140 int   CALLBACK  cmpsortstri( pvoid left, pvoid right, uint idfunc )
141 {
142    return os_strcmpign( ( pvoid )*( puint )left, ( pvoid )*( puint )right );
143 }
144 
145 //--------------------------------------------------------------------------
146 
147 int   CALLBACK  cmpsortustr( pvoid left, pvoid right, uint idfunc )
148 {
149    return os_ustrcmp( ( pvoid )*( puint )left, ( pvoid )*( puint )right );
150 }
151 
152 //--------------------------------------------------------------------------
153 
154 int   CALLBACK  cmpsortustri( pvoid left, pvoid right, uint idfunc )
155 {
156    return os_ustrcmpign( ( pvoid )*( puint )left, ( pvoid )*( puint )right );
157 }
158 //--------------------------------------------------------------------------
159 
160 int   CALLBACK  cmpsortuint( pvoid left, pvoid right, uint idfunc )
161 {
162    uint  lval = *( puint )left;
163    uint  rval = *( puint )right;
164 
165    return lval < rval ? -1 : ( lval > rval ? 1 : 0 );
166 }
167 
168 //--------------------------------------------------------------------------
169 
170 void  STDCALL  fastsort( pvoid base, uint count, uint size, uint mode )
171 {
172    cmpfunc  func;
173 
174    switch ( mode ) {
175       case FS_STR: 
176          func = cmpsortstr;
177          break;
178       case FS_STRIGNORE: 
179          func = cmpsortstri;
180          break;
181       case FS_UINT: 
182          func = cmpsortuint;
183          break;
184       case FS_USTR: 
185          func = cmpsortustr;
186          break;
187       case FS_USTRIGNORE: 
188          func = cmpsortustri;
189          break;
190    }
191    quicksort( base, count, size, func, 0 );
192 }
193 
194 //--------------------------------------------------------------------------