File: sorts.c

package info (click to toggle)
msort 8.53-2.2
  • links: PTS
  • area: main
  • in suites: bullseye, buster, sid
  • size: 2,360 kB
  • sloc: sh: 10,138; ansic: 10,031; makefile: 51
file content (392 lines) | stat: -rw-r--r-- 9,938 bytes parent folder | download | duplicates (5)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
/*
 * Copyright (C) 1993-2007 William J. Poser.
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of version 3 of the GNU General Public License as
 * published by  the Free Software Foundation.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
 * or go to the web page:  http://www.gnu.org/licenses/gpl.txt.
 */


#include "config.h"
#include "compdefs.h"

#include <stdlib.h>
#ifdef HAVE_STDINT_H
#include <stdint.h>
#endif
#include <stdio.h>
#include <string.h>
#include <wchar.h>
#include <wctype.h>
#include <tre/regex.h>
#ifdef HAVE_UNINUM_UNICODE_H
#include <uninum/unicode.h>
#else
#include "unicode.h"
#endif
#include "comparisons.h"
#include "key.h"
#include "record.h"

#ifdef HAVE_LONG_LONG
typedef long long LongLong; 
#else
typedef long LongLong;
#endif

#ifdef HAVE_LONGDOUBLE
#define DOUBLE (long double)
#else
#define DOUBLE double
#endif

#define INSERTIONSORTTHRESHOLD 7L

#define TRUE 1
#define FALSE 0

/*
 *  This is the recursive routine in K&R with swap in-lined as a macro
 *  and use of a straight insertion sort for small sub-partitions.
 */	 


#define SWAP(a,b,c) temp = a[b];a[b] = a[c];a[c] = temp;

void
QuickSort(struct record **rlist, long left, long right)
{
  long i;
  long last;
  long j;
  long elts;
  struct record *temp;
	
  int Compare(struct record *,struct record *);

  elts = right - left + 1L;
  if(elts < 2L) return;
	
  if(elts < INSERTIONSORTTHRESHOLD){ /* Do a straight insertion sort */
    for(j=1L;j < elts;j++){
      temp = rlist[j+left];
      i = j -1L;
      while( (i >= 0) && (Compare(rlist[i+left],temp) > 0)){
	rlist[i+1L+left] = rlist[i+left];
	--i;
      }
      rlist[i+1L+left] = temp;
    }
    return;
  }
	
  /* If we get here it is worth continuing with quicksort. */
	
  j = (left + right)/2L;
  SWAP(rlist,left,j)
	
    last = left;
  for(i = left+1; i <= right; i++){
    if(Compare(rlist[i],rlist[left]) < 0){
      ++last;
      SWAP(rlist,last,i);
    }
  }
  SWAP(rlist,left,last);
  QuickSort(rlist,left,last-1L);
  QuickSort(rlist,last+1L,right);
}

void
ShellSort(struct record **rlist,long cnt)
{
  long gap;
  long i;
  long j;
   
  struct record *temp;
	
  int Compare(struct record *,struct record *);
   
  for(gap = cnt/2; gap > 0; gap /= 2){
    for(i = gap; i < cnt; i++){
      for(j = i-gap; j>= 0; j -= gap){
	if(Compare(rlist[j],rlist[j+gap]) <= 0) break;
	else{
	  temp = rlist[j];
	  rlist[j] = rlist[j+gap];
	  rlist[j+gap] = temp;
	}
      }
    }
  }
  return;
}

void
Merge(struct record **rlist, long start, long mid, long end) 
{
  long i;
  long j;
  long k;
  struct record **tmp;

  int Compare(struct record *,struct record *);

#ifdef ALLOCAOK
  tmp = (struct record **) alloca(sizeof(struct record *) * (end - start));
#else
  tmp = (struct record **) malloc(sizeof(struct record *) * (end - start));
#endif

  i = start;
  j = mid;
  k = 0;
  while ((i < mid) && (j < end)) {
    if (Compare(rlist[i],rlist[j]) <= 0)
	tmp[k++] = rlist[i++];
      else
	tmp[k++] = rlist[j++];
  }
  while (i < mid) {
    tmp[k++] = rlist[i++];
  }
  while (j < end) {
    tmp[k++] = rlist[j++];
  }
  for (i = 0L; i < (end-start); i++) {
    rlist[start+i] = tmp[i];
  }
#ifndef ALLOCAOK
  free((void *) tmp);
#endif
}

void MergeSort(struct record **rlist, long begin, long end)
{
    long mid;
    if (end - begin <= 1L) return;
    mid = (begin + end) / 2L;
    MergeSort(rlist, begin, mid);
    MergeSort(rlist, mid, end);
    Merge(rlist, begin, mid, end);
}

 void InsertionSort(struct record **rlist, long items) {
   long i;
   long j;
   struct record *value;

  int Compare(struct record *,struct record *);

   for(i = 1L; i < items; i++) {
     value = rlist[i];
     for (j = i - 1L; (j >= 0L) && (Compare(rlist[j],value) > 0);j--) {
       rlist[j + 1] = rlist[j];
     }
     rlist[j + 1] = value;
   }
 }

inline int
sign(DOUBLE x)
{
  if(x > 0.0) return (1);
  else if (x < 0.0) return (-1);
  else return (0);
}

inline int
isign(long x)
{
  if(x > 0L) return (1);
  else if (x < 0L) return (-1);
  else return (0);
}

/* Compare two wide strings using a rank table, without reference to the locale.  */
int
wcscmpli (const wchar_t *rt, const wchar_t *a, const wchar_t *b) {
  while (rt[*a] == rt[*b++]) {
    if (*a++ =='\0') return(0);
  }
  return(rt[*a] - rt[*--b]);
}

/*
 * This is the subroutine that does the actual comparison of two records.
 *
 * It returns:
 *	 0 if a = b
 *	-1 if a < b 
 *	 1 if b > a
 *
 * It iterates over the keys, returning as soon as it finds a key on
 * which the two records compare differently. For each key it first
 * tests to see if the records have values for that key. If they do,
 * it does the actual comparison, the details depending on whether the
 * comparison is numeric (including dates, times, and sizes), or lexicographic.
 * If both records lack the key, it returns 0. If one record lacks the
 * key and the other does not, it returns a value depending on how
 * MissingKeyComparison is set for this key.
 *
 * Whether a key exists for a particular record is determined by
 * testing whether the pointer is null. It is therefore important
 * that key pointers be set to null during key extraction if a key is missing. 
 */


#define LOWBITONLYMASK 0x01
#define HIGHBITOFFMASK 0x7F
#define HIGHBITSHIFT      7
#define MIN(a,b) (a>b?b:a)

int
Compare(struct record *a,struct record *b)
{
  int i, j, k, r;
  int rval;
  wchar_t *ap;
  wchar_t *bp;
  wchar_t *rt;
  unsigned short APresent;
  unsigned short BPresent;
  wchar_t **ATxt;
  wchar_t **BTxt;
  long *ANum;
  long *BNum;
  short ANumericFirstP;
  short BNumericFirstP;
  int AParts;
  int BParts;
  int lim;

#ifndef NOCOMPARISONCNT 
  extern LongLong ComparisonCnt;
#endif
  extern int KeyCount;
  extern struct keyinfo **KeyInfo;

  rval = 0;
#ifndef NOCOMPARISONCNT 
  ComparisonCnt++;
#endif

  for(i = 0; i < KeyCount; i++){

    if(KeyInfo[i]->CompType & CRANDOM) {
      return((random()%3)-1);
    }

    /* Set flags for presence of key in each record */
    APresent = BPresent = FALSE;
    if(KeyInfo[i]->CompType & CNUMERIC){
      if(a->klistptr[i].n != NULL) APresent=TRUE;
      if(b->klistptr[i].n != NULL) BPresent=TRUE;
    }
    else{
      ap = a->klistptr[i].t;
      if(ap != NULL) APresent=TRUE;
      bp = b->klistptr[i].t;
      if(bp != NULL) BPresent=TRUE;
    }

    if(APresent && BPresent){
      /* Straight numeric */
      if(KeyInfo[i]->CompType & CNUMERIC){
	if(KeyInfo[i]->CompType & CINVERSE){
	  rval = sign(*(b->klistptr[i].n) - *(a->klistptr[i].n));
	}
	else rval = sign(*(a->klistptr[i].n) - *(b->klistptr[i].n));
      }
      /* Numeric string */
      else if(KeyInfo[i]->CompType & CNUMSTR){
	if(a->klistptr[i].N.sign < b->klistptr[i].N.sign) rval = -1;
	else if(a->klistptr[i].N.sign > b->klistptr[i].N.sign) rval = 1;
	/* Signs are same */
	else if(a->klistptr[i].N.cnt < b->klistptr[i].N.cnt) rval = -1 * a->klistptr[i].N.sign;
	else if(b->klistptr[i].N.cnt < a->klistptr[i].N.cnt) rval = a->klistptr[i].N.sign;
	else rval = a->klistptr[i].N.sign * strcmp(a->klistptr[i].N.txt,b->klistptr[i].N.txt);
      }
      /* Non-numeric */
      else {
	rt = KeyInfo[i]->RankTable;
	rval = 1;		/* Use as flag to see if we reached end of string */
	if(KeyInfo[i]->CompType & CHYBRID) {
	    ANumericFirstP = (a->klistptr[i].H->cnt >> HIGHBITSHIFT) & LOWBITONLYMASK;
	    BNumericFirstP = (b->klistptr[i].H->cnt >> HIGHBITSHIFT) & LOWBITONLYMASK;
	    AParts = a->klistptr[i].H->cnt & HIGHBITOFFMASK;
	    BParts = b->klistptr[i].H->cnt & HIGHBITOFFMASK;
	    ATxt = a->klistptr[i].H->tlist;BTxt = b->klistptr[i].H->tlist;
	    ANum = a->klistptr[i].H->ilist;BNum = b->klistptr[i].H->ilist;
	    if(ANumericFirstP && !BNumericFirstP) return -1;
	    else if(BNumericFirstP && !ANumericFirstP) return 1;
	    else {
	      lim = MIN(AParts,BParts);
	      for(j=0; j < lim; j++) {
		k = j/2; r= j%2;
		if(r == ANumericFirstP) {
#ifdef LOCALE_SORT_ORDER
		  if(KeyInfo[i]->LocaleP) rval = wcscmp(ATxt[k],BTxt[k]);
		  else rval = wcscmpli(rt,ATxt[k],BTxt[k]);
#else
		  rval = wcscmpli(rt,ATxt[k],BTxt[k]);
#endif
		}
		else rval = isign(ANum[k]-BNum[k]);
		if(rval != 0) return rval;
	      }
	      if(BParts > AParts) rval = -1;
	      else if(AParts > BParts) rval = 1;
	      if(rval != 0) return(rval);
	      else continue;
	    }
	} /* End of hybrid section */
	else { /* Non-hybrid lexicographic comparison */
#ifdef LOCALE_SORT_ORDER
	  /* Locale-based */
	  if(KeyInfo[i]->LocaleP) {
	    rval = wcscmp(ap,bp);
	    if(rval!=0) return(rval);
	    else continue;
	  }
	  /* Locale-independent */
	  else {
#endif
	    for( ; rt[*ap] == rt[*bp]; ap++, bp++){
	      if(*ap == (wchar_t) '\0'){rval=0;break;} 
	    }
	    if(rval != 0){
	      if(KeyInfo[i]->CompType & CINVERSE) rval = rt[*bp] - rt[*ap];
	      else rval = rt[*ap] - rt[*bp];
	    }
#ifdef LOCALE_SORT_ORDER
	  }
#endif
	} /* End of non-hybrid lexicographic comparison */
      }	/* End of lexicographic comparison */
    } /* End of case where both keys are present */

    /* If we get here at least one record lacks this key */
    else{
      if (APresent && !BPresent) rval = 1 - KeyInfo[i]->MissingKeyComparison;
      else{
	if (!APresent && BPresent) rval = KeyInfo[i]->MissingKeyComparison - 1;
	else{
	  if (!APresent && !BPresent)rval = 0;
	}
      }
    }
    if(rval != 0) return(rval); /* If records are same on this key, go on to next key */
  } /* End of loop over keys */
  return(0);			/* If we get here, records tie on all keys */
}