File: gvcst_kill_sort.c

package info (click to toggle)
fis-gtm 6.3-007-1
  • links: PTS, VCS
  • area: main
  • in suites: buster
  • size: 36,284 kB
  • sloc: ansic: 328,861; asm: 5,182; csh: 5,102; sh: 1,918; awk: 291; makefile: 69; sed: 13
file content (90 lines) | stat: -rwxr-xr-x 1,653 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
/****************************************************************
 *								*
 *	Copyright 2001, 2007 Fidelity Information Services, Inc	*
 *								*
 *	This source code contains the intellectual property	*
 *	of its copyright holder(s), and is made available	*
 *	under a license.  If you do not know the terms of	*
 *	the license, please stop and do not read further.	*
 *								*
 ****************************************************************/

#include "mdef.h"
#include "gdsroot.h"
#include "gdskill.h"
#include "gvcst_kill_sort.h"

#define S_CUTOFF 15

void gvcst_kill_sort(kill_set *k)
{

	block_id_ptr_t	stack[50],*sp;
	block_id	v,t;
	block_id_ptr_t	l,r;
	block_id_ptr_t	ix,jx,kx;

	assert(k->used <= BLKS_IN_KILL_SET);
	sp = stack;
	l = (block_id_ptr_t)(k->blk);
	r = l + k->used-1;
	for (;;)
		if (r - l < S_CUTOFF)
		{
			for (ix  = l + 1 ; ix <= r ; ix++)
			{
				for (jx = ix , t = *ix; jx > l  && *(jx-1) > t; jx--)
					*jx = *(jx - 1);
				*jx = t;
			}
			if (sp <= stack)
				break;
			else
			{
				l = *--sp;
				r = *--sp;
			}
		}
		else
		{
			ix = l;
			jx = r;
			kx = l + ((int)(r - l) / 2);
			kx = (*ix > *jx) ?
				((*jx > *kx) ?
					jx:
					((*ix > *kx) ? kx : ix)):
				((*jx < *kx) ?
					jx:
					((*ix > *kx) ? ix : kx));
			t = *kx;
			*kx = *jx;
			*jx = t;
			ix--;
			do
			{
				do ix++; while (*ix < t);
				do jx--; while (*jx > t);
				v = *ix;
				*ix = *jx;
				*jx = v;
			} while (jx > ix);
			*jx = *ix;
			*ix = *r;
			*r = v;
			if (ix - l > r - ix)
			{
				*sp++ = ix - 1;
				*sp++ = l;
				l = ix + 1;
			}
			else
			{
				*sp++ = r;
				*sp++ = ix + 1;
				r = ix - 1;
			}
		}
	return;

}