1 #include "history.h"
2
3
4 #define BIT8 0xff
5 #define BIT12 0xfff
6 #define BIT24 0xffffff
7
8 #define CNTSIZE ( 4096 + 4096 + 256 )
9 #define COUNT1 &countBuff[ 0 ]
10 #define COUNT2 &countBuff[ 4096 ]
11 #define COUNT3 &countBuff[ 4096 + 4096 ]
12 #define ENDCNT &countBuff[ CNTSIZE ]
13
14
15 static int *countBuff;
16 static phist *data_;
17 static phist *dataBuff;
18 static phist *dataBuff1;
19
20
21 /*
22 * Sort the edge array pointed to by 'lineBuff'. Return a pointer to a
23 * sorted array of pointers into the original data.
24 */
Sort(nlines,lineBuff,maxv)25 phist *Sort( nlines, lineBuff, maxv )
26 int nlines;
27 phist *lineBuff;
28 long maxv;
29 {
30 phist *tmp;
31
32 data_ = lineBuff;
33 dataBuff = tmp = (phist *) malloc( sizeof( phist ) * nlines );
34 countBuff = (int *) malloc( sizeof( int ) * CNTSIZE );
35 dataBuff1 = (phist *) malloc( sizeof( phist ) * nlines );
36 BucketSort( nlines, maxv );
37 if( dataBuff != tmp ) /* swapped by sort */
38 {
39 register phist *src, *dst, *end;
40
41 dataBuff1 = dataBuff;
42 dataBuff = tmp;
43 src = dataBuff1;
44 dst = dataBuff;
45 end = &dataBuff1[ nlines ];
46 do { *dst++ = *src++; } while( src < end );
47 }
48 return( dataBuff );
49 }
50
51
BucketSort(nlines,maxv)52 static BucketSort( nlines, maxv )
53 int nlines;
54 long maxv;
55 {
56 {
57 register int *cp, *end;
58
59 cp = COUNT1;
60 end = ENDCNT;
61 do { *cp++ = 0; } while( cp < end );
62 }
63
64 {
65 register phist *dat, *end;
66 register int *count1, *count2, *count3;
67
68 count1 = COUNT1;
69 count2 = COUNT2;
70 count3 = COUNT3;
71 dat = data_;
72 end = &data_[ nlines ];
73
74 if( maxv <= BIT12 )
75 {
76 do
77 {
78 count1[ (*dat)->time & BIT12 ]++;
79 dat++;
80 }
81 while( dat < end );
82 }
83 else if( maxv <= BIT24 )
84 {
85 do
86 {
87 count1[ (*dat)->time & BIT12 ]++;
88 count2[ ( (*dat)->time >> 12 ) & BIT12 ]++;
89 dat++;
90 }
91 while( dat < end );
92 }
93 else
94 {
95 do
96 {
97 count1[ (*dat)->time & BIT12 ]++;
98 count2[ ( (*dat)->time >> 12 ) & BIT12 ]++;
99 count3[ ( (*dat)->time >> 24 ) & BIT8 ]++;
100 dat++;
101 }
102 while( dat < end );
103 }
104 }
105
106 {
107 register int *cp, *cp_1;
108 register int *cp2, *cp2_1;
109 register int *end;
110 cp = COUNT1;
111 cp_1 = &cp[1];
112 cp2 = COUNT2;
113 cp2_1 = &cp2[1];
114 end = COUNT2;
115 do
116 {
117 *cp_1++ += *cp++;
118 *cp2_1++ += *cp2++;
119 }
120 while( cp_1 < end );
121
122 cp = COUNT3;
123 cp_1 = &cp[1];
124 end = ENDCNT;
125 do { *cp_1++ += *cp++; } while( cp_1 < end );
126 }
127
128 {
129 register int tmp;
130 register int *count;
131 register phist *dat;
132 register phist *datPtr, *end;
133
134 dat = &data_[ nlines-1 ];
135 count = COUNT1;
136 datPtr = dataBuff;
137 do
138 {
139 tmp = --count[ (*dat)->time & BIT12 ];
140 datPtr[ tmp ] = (*dat);
141 dat--;
142 }
143 while( dat >= data_ );
144
145 if( maxv <= BIT12 )
146 goto done;
147
148 datPtr = &dataBuff[ nlines-1 ];
149 end = dataBuff;
150 count = COUNT2;
151 do
152 {
153 tmp = -- count[ ((*datPtr)->time >> 12) & BIT12 ];
154 dataBuff1[ tmp ] = *datPtr;
155 datPtr--;
156 }
157 while( datPtr >= end );
158
159 if( maxv <= BIT24 )
160 {
161 datPtr = dataBuff1;
162 dataBuff1 = dataBuff;
163 dataBuff = datPtr;
164 goto done;
165 }
166
167 datPtr = &dataBuff1[ nlines-1 ];
168 end = dataBuff1;
169 count = COUNT3;
170 do
171 {
172 tmp = -- count[ ((*datPtr)->time >> 24) & BIT8 ];
173 dataBuff[ tmp ] = *datPtr;
174 datPtr--;
175 }
176 while( datPtr >= end );
177
178 }
179
180 done : ;
181 }
182