1 /* This file is part of Conauto.
2
3 Conauto is free software: you can redistribute it and/or modify
4 it under the terms of the GNU General Public License as published by
5 the Free Software Foundation, either version 3 of the License, or
6 (at your option) any later version.
7
8 Conauto is distributed in the hope that it will be useful,
9 but WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 GNU General Public License for more details.
12
13 You should have received a copy of the GNU General Public License
14 along with Conauto. If not, see <http://www.gnu.org/licenses/>.
15 */
16
17 /* sort function which uses qsort */
18
19 #include <stdlib.h>
20 #include <string.h>
21
22 #include "sort.h"
23
24 #define EXCHANGE( A, B )\
25 { register void* C; C = A; A = B; B = C;\
26 }
27
28 #define MERGE( OLD, NEW, I1, S1, I2, S2 )\
29 {\
30 uint16_t k, l, m;\
31 k = I1;\
32 l = I2;\
33 m = I1;\
34 while ( ( k <= S1 ) && ( l <= S2 ) )\
35 if ( attributes[OLD[k]] >= attributes[OLD[l]] )\
36 NEW[m++] = OLD[k++];\
37 else\
38 NEW[m++] = OLD[l++];\
39 while ( k <= S1 )\
40 NEW[m++] = OLD[k++];\
41 while ( l <= S2 )\
42 NEW[m++] = OLD[l++];\
43 }
44
45 #define COPY( OLD, NEW, DOWN_LIM, UP_LIM )\
46 {\
47 uint32_t k;\
48 for ( k = DOWN_LIM; k <= UP_LIM; k++ )\
49 NEW[k] = OLD[k];\
50 }
51
sort_cell(uint16_t nmemb,uint16_t * base,uint64_t * attributes)52 void sort_cell ( uint16_t nmemb, uint16_t *base, uint64_t *attributes )
53 {
54 uint16_t i1, s1;
55 uint16_t i2, s2;
56 uint16_t size;
57 uint16_t temp[nmemb];
58 uint16_t *new, *old;
59 uint16_t up_to;
60
61 old = base;
62 new = temp;
63 up_to = (uint16_t) (nmemb-1);
64 for ( size = 1; size < nmemb; size = (uint16_t) (size << 1 ) )
65 {
66 i1 = 0;
67 i2 = (uint16_t) ( i1 + size );
68 s1 = (uint16_t) ( i2 - 1 );
69 s2 = (uint16_t) ( s1 + size );
70 while ( s2 < nmemb )
71 {
72 MERGE ( old, new, i1, s1, i2, s2 );
73 i1 = (uint16_t) ( s2 + 1 );
74 i2 = (uint16_t) ( i1 + size );
75 s1 = (uint16_t) ( i2 - 1 );
76 s2 = (uint16_t) ( s1 + size );
77 }
78 if ( s1 < up_to )
79 MERGE ( old, new, i1, s1, i2, up_to )
80 else
81 COPY ( old, new, i1, up_to )
82 EXCHANGE ( old, new );
83 }
84 if ( old != base )
85 memcpy ( base, old, nmemb * sizeof ( uint16_t ) );
86 }
87
88 #define MERGE_UINT16( OLD, NEW, I1, S1, I2, S2 )\
89 {\
90 uint16_t k, l, m;\
91 k = I1;\
92 l = I2;\
93 m = I1;\
94 while ( ( k <= S1 ) && ( l <= S2 ) )\
95 if ( OLD[k] >= OLD[l] )\
96 NEW[m++] = OLD[k++];\
97 else\
98 NEW[m++] = OLD[l++];\
99 while ( k <= S1 )\
100 NEW[m++] = OLD[k++];\
101 while ( l <= S2 )\
102 NEW[m++] = OLD[l++];\
103 }
104
sort_uint16(uint16_t nmemb,uint16_t * base)105 void sort_uint16 ( uint16_t nmemb, uint16_t *base )
106 {
107 uint16_t i1, s1;
108 uint16_t i2, s2;
109 uint16_t size;
110 uint16_t temp[nmemb];
111 uint16_t *new, *old;
112 uint16_t up_to;
113
114 old = base;
115 new = temp;
116 up_to = (uint16_t) (nmemb-1);
117 for ( size = 1; size < nmemb; size = (uint16_t) (size << 1 ) )
118 {
119 i1 = 0;
120 i2 = (uint16_t) ( i1 + size );
121 s1 = (uint16_t) ( i2 - 1 );
122 s2 = (uint16_t) ( s1 + size );
123 while ( s2 < nmemb )
124 {
125 MERGE_UINT16 ( old, new, i1, s1, i2, s2 );
126 i1 = (uint16_t) ( s2 + 1 );
127 i2 = (uint16_t) ( i1 + size );
128 s1 = (uint16_t) ( i2 - 1 );
129 s2 = (uint16_t) ( s1 + size );
130 }
131 if ( s1 < up_to )
132 MERGE_UINT16 ( old, new, i1, s1, i2, up_to )
133 else
134 COPY ( old, new, i1, up_to )
135 EXCHANGE ( old, new );
136 }
137 if ( old != base )
138 memcpy ( base, old, nmemb * sizeof ( uint16_t ) );
139 }
140
141 #define MERGE_VALID_ORBITS( OLD, NEW, I1, S1, I2, S2 )\
142 {\
143 uint16_t k, l, m;\
144 k = I1;\
145 l = I2;\
146 m = I1;\
147 while ( ( k <= S1 ) && ( l <= S2 ) )\
148 if ( go->orbits[go->vertices[OLD[k]].belongs_to].size >= go->orbits[go->vertices[OLD[l]].belongs_to].size )\
149 NEW[m++] = OLD[k++];\
150 else\
151 NEW[m++] = OLD[l++];\
152 while ( k <= S1 )\
153 NEW[m++] = OLD[k++];\
154 while ( l <= S2 )\
155 NEW[m++] = OLD[l++];\
156 }
157
sort_valid_orbits(uint16_t nmemb,uint16_t * base,Graph_Orbits * go)158 void sort_valid_orbits ( uint16_t nmemb, uint16_t *base, Graph_Orbits *go )
159 {
160 uint16_t i1, s1;
161 uint16_t i2, s2;
162 uint16_t size;
163 uint16_t temp[nmemb];
164 uint16_t *new, *old;
165 uint16_t up_to;
166
167 old = base;
168 new = temp;
169 up_to = (uint16_t) (nmemb-1);
170 for ( size = 1; size < nmemb; size = (uint16_t) (size << 1 ) )
171 {
172 i1 = 0;
173 i2 = (uint16_t) ( i1 + size );
174 s1 = (uint16_t) ( i2 - 1 );
175 s2 = (uint16_t) ( s1 + size );
176 while ( s2 < nmemb )
177 {
178 MERGE_VALID_ORBITS ( old, new, i1, s1, i2, s2 );
179 i1 = (uint16_t) ( s2 + 1 );
180 i2 = (uint16_t) ( i1 + size );
181 s1 = (uint16_t) ( i2 - 1 );
182 s2 = (uint16_t) ( s1 + size );
183 }
184 if ( s1 < up_to )
185 MERGE_VALID_ORBITS ( old, new, i1, s1, i2, up_to )
186 else
187 COPY ( old, new, i1, up_to )
188 EXCHANGE ( old, new );
189 }
190 if ( old != base )
191 memcpy ( base, old, nmemb * sizeof ( uint16_t ) );
192 }
193
194 #define ROL32(x, n) (((x) << (n)) | ((x) >> (32-(n))))
195 #define ROL16(x, n) (((x) << (n)) | ((x) >> (16-(n))))
196
hash_Meiyan32(const void * key,size_t len)197 uint32_t hash_Meiyan32 ( const void *key, size_t len )
198 {
199 const uint32_t PRIME = 709607;
200 uint32_t hash32;
201 const uint32_t *p;
202
203 for ( hash32 = 2166136261, p = key; --len; p++ )
204 {
205 hash32 = ( hash32 ^ ( ROL32(*p,5) ^ *(p+1) ) ) * PRIME;
206 }
207 return hash32 ^ ( hash32 >> 16 );
208 }
209
hash_Meiyan16(const void * key,size_t len)210 uint16_t hash_Meiyan16 ( const void *key, size_t len )
211 {
212 const uint16_t PRIME = 9173;
213 uint16_t hash16;
214 const uint16_t *p;
215
216 /* for ( hash16 = 40387, p = key; --len; p++ ) */
217 for ( hash16 = 43387, p = key; --len; p++ )
218 {
219 if ( hash16 == ( ROL16(*p,5) ^ *(p+1) ) )
220 hash16++;
221 hash16 = (uint16_t)(( hash16 ^ ( ROL16(*p,5) ^ *(p+1) ) ) * PRIME);
222 }
223 return hash16 ^ ( hash16 >> 8 );
224 }
225