projects / apple / libc.git / blame
| Commit | Line | Data |
|---|---|---|
| b061a43b A |
1 | /*- |
| 2 | * Copyright (C) 2004 Maxim Sobolev <sobomax@FreeBSD.org> | |
| 3 | * All rights reserved. | |
| 4 | * | |
| 5 | * Redistribution and use in source and binary forms, with or without | |
| 6 | * modification, are permitted provided that the following conditions | |
| 7 | * are met: | |
| 8 | * 1. Redistributions of source code must retain the above copyright | |
| 9 | * notice, this list of conditions and the following disclaimer. | |
| 10 | * 2. Redistributions in binary form must reproduce the above copyright | |
| 11 | * notice, this list of conditions and the following disclaimer in the | |
| 12 | * documentation and/or other materials provided with the distribution. | |
| 13 | * | |
| 14 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND | |
| 15 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
| 16 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | |
| 17 | * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE | |
| 18 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | |
| 19 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | |
| 20 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
| 21 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | |
| 22 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | |
| 23 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | |
| 24 | * SUCH DAMAGE. | |
| 25 | * | |
| 26 | * $FreeBSD$ | |
| 27 | */ | |
| 28 | ||
| 29 | #ifndef _TEST_SORT_H | |
| 30 | #define _TEST_SORT_H | |
| 31 | ||
| 32 | #include <sys/param.h> | |
| 33 | ||
| 34 | #define nitems(x) (sizeof((x)) / sizeof((x)[0])) | |
| 35 | ||
| 36 | static int | |
| 37 | sorthelp(const void *a, const void *b) | |
| 38 | { | |
| 39 | const int *oa, *ob; | |
| 40 | ||
| 41 | oa = a; | |
| 42 | ob = b; | |
| 43 | /* Don't use "return *oa - *ob" since it's easy to cause overflow! */ | |
| 44 | if (*oa > *ob) | |
| 45 | return (1); | |
| 46 | if (*oa < *ob) | |
| 47 | return (-1); | |
| 48 | return (0); | |
| 49 | } | |
| 50 | ||
| 51 | static int | |
| 52 | szsorthelp(void *sz, const void *a, const void *b) | |
| 53 | { | |
| 54 | size_t elmsz = (size_t)sz; | |
| 55 | return memcmp(a, b, elmsz); | |
| 56 | } | |
| 57 | ||
| 58 | static int (^sorthelp_b)(const void *a, const void *b) = | |
| 59 | ^(const void *a, const void *b){ | |
| 60 | const int *oa, *ob; | |
| 61 | ||
| 62 | oa = a; | |
| 63 | ob = b; | |
| 64 | /* Don't use "return *oa - *ob" since it's easy to cause overflow! */ | |
| 65 | if (*oa > *ob) | |
| 66 | return (1); | |
| 67 | if (*oa < *ob) | |
| 68 | return (-1); | |
| 69 | return (0); | |
| 70 | }; | |
| 71 | ||
| 72 | /* Reference sorting routine (slooow!) */ | |
| 73 | static void | |
| 74 | ssort(int v[], int nmemb) | |
| 75 | { | |
| 76 | int i, j, k; | |
| 77 | ||
| 78 | for (i = 0; i < nmemb; i++) { | |
| 79 | for (j = i + 1; j < nmemb; j++) { | |
| 80 | if (v[j] < v[i]) { | |
| 81 | k = v[i]; | |
| 82 | v[i] = v[j]; | |
| 83 | v[j] = k; | |
| 84 | } | |
| 85 | } | |
| 86 | } | |
| 87 | } | |
| 88 | ||
| 89 | /* with element size */ | |
| 90 | static void | |
| 91 | szsort(char v[], size_t nmemb, size_t sz) | |
| 92 | { | |
| 93 | size_t i, j; | |
| 94 | char temp[sz]; | |
| 95 | ||
| 96 | for (i = 0; i < nmemb; i++) { | |
| 97 | for (j = i + 1; j < nmemb; j++) { | |
| 98 | if (memcmp(v + (j * sz), v + (i * sz), sz) < 0) { | |
| 99 | memcpy(temp, v + (i * sz), sz); | |
| 100 | memcpy(v + (i * sz), v + (j * sz), sz); | |
| 101 | memcpy(v + (j * sz), temp, sz); | |
| 102 | } | |
| 103 | } | |
| 104 | } | |
| 105 | } | |
| 106 | ||
| 107 | /* Some random data */ | |
| 108 | static int initvector[1024] = { | |
| 109 | 599853225, 371951333, -428880425, 1450668530, 85530178, -460170550, | |
| 110 | -270680269, 717137591, 106244401, -1138072905, -113532586, | |
| 111 | 599690958, 464993720, 107690177, 24249019, -1151018550, 794225588, | |
| 112 | 1494905642, -62951716, -734531757, 1197251494, 1020063925, | |
| 113 | -634536734, -216634704, 617366508, -18840190, 481010395, | |
| 114 | -1555785724, 128221950, -1747743676, 1119012320, -252160437, | |
| 115 | 617137855, 1159833073, -106647920, -1570719046, -769400990, | |
| 116 | -130308848, 1186546396, 215253591, 445832488, 160263176, 777264170, | |
| 117 | -274636650, -696134447, 1057957088, -626175254, 188632134, | |
| 118 | -98941793, -1602334908, -373717125, 885013862, 571258221, | |
| 119 | -399572192, 407761463, -733249776, 12094800, -367046815, 178974501, | |
| 120 | -452638559, -516580143, -94282073, 1411115180, -1151792797, | |
| 121 | 1442815268, 1106583674, 515269284, -74019972, 598818901, 696848474, | |
| 122 | -657910766, -287309335, 1538095746, 143543003, 851444033, | |
| 123 | -947573348, 296222973, 1339592140, -947505360, 872027891, | |
| 124 | -418844714, -583075597, -324758197, -964531573, 1016795914, | |
| 125 | -866842580, -304084402, -286930819, 338975583, 803597943, | |
| 126 | -452483372, 1525283506, -1185830826, -596405894, 905191340, | |
| 127 | -1638026278, 106749913, 582771197, -730713796, 56052422, | |
| 128 | 1498040174, 644967266, 182541575, 280483468, -1932835017, | |
| 129 | -435546874, 940106007, 1753388509, -340355019, -231577358, | |
| 130 | -714879035, 1051182949, 204261785, 1321346243, -895289878, | |
| 131 | -240369893, 566608506, -350777580, -1384849829, -876816409, | |
| 132 | 1013787299, -1408035937, -222626650, 1708168486, -645148461, | |
| 133 | 1854654, -393012507, 179327030, -1607975548, -715202732, 730588290, | |
| 134 | 246968517, -550975254, -101136772, -174103176, 1188941016, | |
| 135 | 2004650834, -1501389866, -2021225998, 1219042515, -464113898, | |
| 136 | 268565342, 126451123, -1045877126, -198918003, 310177444, | |
| 137 | 1578314812, 1828867082, 453336898, -908485523, 749777130, | |
| 138 | -1028565802, 61360571, 241484853, -175693399, 1816211059, | |
| 139 | 533940889, -1496933703, 385185125, -821132413, -8923391, | |
| 140 | -1429546239, 46190992, 449247332, -20432494, 778761611, -178782699, | |
| 141 | -811194695, -632276211, 70196094, 890817525, -1447776908, | |
| 142 | -323783741, -62333222, 954929503, 247668507, -1394420605, | |
| 143 | 367913886, 1364926759, 1298781924, 357923028, -73644747, | |
| 144 | -319744305, 61718202, -1454549286, 387493522, 2018321449, | |
| 145 | 861026653, 289973298, 1755939093, -84772204, 43425266, -1325753781, | |
| 146 | -679938775, 1228500370, -763816405, 548903035, 1765563727, | |
| 147 | 425183052, 1424621863, -188287424, 554385654, 751831998, | |
| 148 | 1377088085, 66622090, 139224450, -1305816167, 650140724, 593988868, | |
| 149 | -444913321, 589045097, 1261428989, 101292769, -780376786, | |
| 150 | 559307348, 1644593236, -1838606833, 53570301, -680576100, | |
| 151 | -44969538, 268718267, -632104125, 276904628, 626299449, -11761453, | |
| 152 | 545899086, -1027343598, -432251872, 539353494, -399575006, | |
| 153 | -568383580, -677802882, 1296513472, 801202048, 806425805, 1983363, | |
| 154 | 850487421, 38046173, 1535399484, 1998285544, -1301751898, | |
| 155 | -46561973, 56545408, -1107662676, 456041145, -452923904, | |
| 156 | -262219453, -371849200, 392524281, 1650231392, 1185585356, | |
| 157 | 126610511, -1125389657, 1015981177, -1318481342, -213835789, | |
| 158 | 1263484054, -654361441, 1408272041, -231555284, -1121778152, | |
| 159 | -395512897, 332277674, -349703586, 1809474399, -223731607, | |
| 160 | -1342224737, 736165236, 67535587, 89879082, 471445838, 423788300, | |
| 161 | -384354470, 907475706, 154886390, -1406736539, -8558766, | |
| 162 | -203405718, -422127884, 1048520863, 747418501, 87438975, 727668160, | |
| 163 | -914936981, 428266976, -455742009, -949014605, 487159058, | |
| 164 | -262526850, -309451504, -76928461, 1072951428, -1370953830, | |
| 165 | 238231681, -1831047244, -405735199, -35941848, 469048670, | |
| 166 | 505307987, -660553590, 876537439, -314195871, 999234339, | |
| 167 | -1405846240, -579885695, 629067031, 863481510, -742301385, | |
| 168 | -1723403128, -153070386, 782682839, -343111818, -877101810, | |
| 169 | 1438467302, -319951459, -1585702508, -338381888, 484108815, | |
| 170 | -1726935191, -749923706, 1657932127, -816151395, -566321865, | |
| 171 | -133542331, 84961164, 598275578, 1302065347, -533098653, | |
| 172 | -1766383037, 53169714, -464201288, 617735133, 862536123, | |
| 173 | -141730724, -1967377125, -1023736305, -1012511106, 64484992, | |
| 174 | -1250856831, 426409332, -355670055, -298251663, -867634978, | |
| 175 | -776124819, 74018333, -425385214, -108004251, -1192766130, | |
| 176 | 1294193867, -109867195, -78667637, 1164855393, -826007552, | |
| 177 | -522528066, 1160283046, -1095276403, -1218917472, -396475366, | |
| 178 | -77394733, -425603169, 251928357, -393559355, 1488845184, | |
| 179 | 898455978, -773338691, -37627855, -345014717, 204298578, 209084274, | |
| 180 | 1047080643, -414348222, 26496664, 705759824, 575149152, 604904761, | |
| 181 | 624988690, 1446041250, 1000757225, -1354896151, 1422958189, | |
| 182 | -1607165311, -832757521, 365074225, 1171764999, 1200795217, | |
| 183 | -203957828, 23166236, -846818698, -547439867, -790192498, | |
| 184 | -122123561, 914298013, 66225525, -36163174, -480698856, | |
| 185 | -1269421818, 624641703, 254923102, 1564329013, -583609221, | |
| 186 | -649433551, -743396069, 1182455435, 102658744, 285599336, | |
| 187 | 692480463, -852737563, -660090184, 1374350065, 72300985, 690541659, | |
| 188 | -1194212957, -1151816525, 157415641, 487398246, 1030153072, | |
| 189 | 933723020, 1359181027, -1303457764, -1543773272, 774306017, | |
| 190 | -854382652, 755485667, -864943584, -63242545, -1271480354, | |
| 191 | 157720215, -205001173, 889984130, -581583822, -473779111, | |
| 192 | -932136577, 735326252, 428638717, 1888884222, 561493709, | |
| 193 | -1966427364, -1710208603, 340121869, 918894036, 927172509, | |
| 194 | 904178436, 1476687667, 90796414, 651591731, -550913123, -42218158, | |
| 195 | 637756529, 1091478400, 124976584, -48739309, -798898083, 393581349, | |
| 196 | -1078624722, -789291577, 1010582542, -512317005, 1222773656, | |
| 197 | 466454593, 1183558811, 822782663, -851624703, -850404012, | |
| 198 | 1473672600, 852527073, 1073953362, 137635828, 936104739, -86567759, | |
| 199 | -882563252, 1845232980, -737978404, -104703380, 149802989, | |
| 200 | -349118325, 1479797538, 1966007488, 1254228842, 414304661, | |
| 201 | -790805785, 31583329, -76864151, 558202855, -1447047313, 716720607, | |
| 202 | -404224238, -54107627, 1747385914, -657407390, 202940208, | |
| 203 | 1083067056, -532861378, 163426933, -130289277, 1301785258, | |
| 204 | -302920320, -637947485, -644895903, -1668027530, 391890467, | |
| 205 | -126586485, -536836984, -1154536413, -339505118, -1187229462, | |
| 206 | -670985870, -601310813, -1350055158, -482479784, 139847714, | |
| 207 | -253955849, 5190414, -542857077, 1175835684, -584165057, | |
| 208 | 1132775766, -592091269, -891445655, -340995936, 736395810, | |
| 209 | 779967964, 515095845, -1138437307, -259226729, -167820100, | |
| 210 | -801611617, -282451622, -1313679283, -1436126694, 1258773990, | |
| 211 | -717601098, -583559645, -1307478759, 1238647247, 1589011223, | |
| 212 | -1029216445, -107030650, 400152690, -1349079913, 1428582247, | |
| 213 | 21546946, 208807686, -169450574, -1086213374, -1242715198, | |
| 214 | 669098277, 416626722, -1122525014, -1389466669, -391843085, | |
| 215 | -56318357, 421040094, 212303518, 738666684, -1185364904, | |
| 216 | -506192760, 646735912, -1424722633, 745226976, 1019191717, | |
| 217 | -190891744, -310320868, -373655022, -665117060, 830760000, | |
| 218 | 583906512, -330536027, 611092636, -321344259, -1255008904, | |
| 219 | -777959046, -523043472, 88896910, 346062204, -163734816, 336635665, | |
| 220 | 906060268, -128891583, 740952564, 916767203, 296514859, 198670559, | |
| 221 | 358136672, -152253676, 12038867, -1469916749, -1020980597, | |
| 222 | -897143313, 354240970, -97959800, 814172811, 1983363241, 264990663, | |
| 223 | 105154676, 1060463014, 430172143, 375111946, -824526943, | |
| 224 | -708877751, -1377442616, -236559551, 684724584, 1602131358, | |
| 225 | -42140186, -763499840, -605167, 98575879, -376577598, 1689746083, | |
| 226 | -777973879, -1396984691, -187780326, 281040966, 1858859521, | |
| 227 | 158395760, 1022807978, -218458812, 811779708, 1495113833, | |
| 228 | 1192561226, 629539535, -1365196683, -1120253162, 1091681956, | |
| 229 | 134286445, 1172218369, -34093658, -137087343, -27869226, | |
| 230 | -180889478, 55705436, 52362743, -1745516232, -926564477, | |
| 231 | -513701675, -1666272054, 1457952810, 843953275, -478275722, | |
| 232 | -1240291080, 101859661, -1606687523, 916365333, 314713310, | |
| 233 | -22002688, 1019022641, -1171741314, -129050627, -211955813, | |
| 234 | -1020176299, 1357865293, -609819628, 724533854, -1141449545, | |
| 235 | 22285231, -97731145, -302329687, 191910894, -1300709885, | |
| 236 | -644951895, 640448036, -1289009824, 1445456129, 846416471, | |
| 237 | 1821291740, -1639640821, -712724532, -447475807, 132156847, | |
| 238 | 258067455, 324301319, 278586969, -1544082357, 636007277, 977122066, | |
| 239 | 127462480, 365126129, 1086276825, -432124148, 896598926, | |
| 240 | -388550179, 273357331, -845018695, -1089465389, 384439820, | |
| 241 | -558419772, 1476422025, 730712769, 190665059, -764968927, | |
| 242 | -789708218, 637873581, 348429858, 1386000168, -638123594, | |
| 243 | -842010345, -607926448, 19535163, -742771490, -18323344, 246155488, | |
| 244 | 350409468, 1290907730, -492566468, 300358636, 501876267, 252441807, | |
| 245 | 1233551975, -1431067042, 517177374, -1540299707, -948380761, | |
| 246 | 1253997663, 693795998, 148707823, 152894502, 98729538, -30042824, | |
| 247 | -563057441, 723726409, 367338961, 1395435261, 217868876, | |
| 248 | 1220652431, 953572083, -1134905155, -734486813, -587470130, | |
| 249 | -864647866, 1030737023, 781798521, -321076732, -460548153, | |
| 250 | 122681678, -873728847, -1286304399, -75472885, 113390881, | |
| 251 | -1556849198, -1070802176, 924389470, 957478910, 5974049, 709413506, | |
| 252 | 476334647, 572869787, 776298405, -8822420, -99326499, -707855342, | |
| 253 | -1187216303, 668038414, 262454769, -1120293198, -32011040, | |
| 254 | 249812104, -101835410, 1082281087, -570183855, -954535179, | |
| 255 | 1384361473, -983199686, 2017611313, 328926483, -878162849, | |
| 256 | -1202254181, -225604951, 966898955, 247213529, -1257544612, | |
| 257 | -197005970, -1039902730, -1947925142, 1752780907, -313410699, | |
| 258 | -464474556, 416580338, -1063356643, -292212702, 57509168, | |
| 259 | 1034124629, 1059212593, 468522867, 845369497, 1872717306, | |
| 260 | -1216544764, -1419907623, 1376869956, -66585488, -1590974467, | |
| 261 | -367070705, -1456529060, 791844031, 336217635, -1106832215, | |
| 262 | 1476739427, -751018210, -1411671555, -1880387375, -1714242595, | |
| 263 | 1169006474, -479442380, -892267555, -1471250266, -267888858, | |
| 264 | 808634418, 1324777189, -585449929, 1127186951, 468768901, | |
| 265 | -2002989138, -52352849, 186493053, 1258464606, 117157186, | |
| 266 | 445919258, 908401949, -1112221136, 863904453, -942718649, | |
| 267 | 796754809, -38943966, -781978872, -56814078, 1273857459, | |
| 268 | -1781920832, 209979504, 811828269, -1150814437, 850061883, | |
| 269 | -532968763, 252506408, -885025629, 391567580, -1295702482, | |
| 270 | 574894420, 1462248349, 1622584325, -88443443, -1122006092, | |
| 271 | -169758578, 456282338, -443233309, 436693483, -956563815, | |
| 272 | -480221349, 435252860, -1114099391, 1060053979, -470893945, | |
| 273 | -1273682879, -734596176, 639950927, -1278648701, 306274747, | |
| 274 | -410562146, 1137869228, -1970746553, 1313830798, 1248071822, | |
| 275 | -247297704, 1015218053, -1607348116, -261817613, -821413148, | |
| 276 | -782942639, -628711083, 240953091, -629550668, -1584736319, | |
| 277 | 856616893, -186759752, 197905373, 541638393, 603407919, -278480495, | |
| 278 | 410077039, 544065371, -1509627427, 402918436, -450463799, | |
| 279 | -131169308, 249920630, 1079548609, -927911828, 1444577689, | |
| 280 | -353002528, -224292462, 1247795279, -790844631, -40427503, | |
| 281 | 59829765, -332587567, 1319862109, -1261340753, 121711726, | |
| 282 | 1342756342, -643495787, 100326201, -934436714, -69134888, | |
| 283 | -898880561, -379524737, -577234570, -805827092, -1575493557, | |
| 284 | -289920678, -476605057, 1235714994, -317239591, 418553949, | |
| 285 | 410053338, -204985448, 1206503615, 202610372, -932244873, | |
| 286 | 782207875, -288661931, -806814809, 1270953679, 2060991595, | |
| 287 | -311412846, 327279979, 1148562672, 55239149, -610114433, | |
| 288 | -1511688434, 87619740, -433503545, 326150519, -581293393, | |
| 289 | -97417688, -289736140, -1543886029, -1251976119, 1585774446, | |
| 290 | 1570011421, 432602745, 486343696, -834680922, 265004849, | |
| 291 | -1132107706, 502627197, -815873818, 249635389, 1985714127, | |
| 292 | -1095817653, -130743522, -645266828, -334621094, 199921747, | |
| 293 | 1059256177, 378031303, 1519740920, 925540689, 1405957844, | |
| 294 | 1387748290, -56138046, -770637828, -187984510, -1361735163, | |
| 295 | 1294823206, -608941238, 451860688, -510549867, 1143516283, | |
| 296 | -779090703, 1459305047, -600335915, -1684168049, 1516622316, | |
| 297 | -631733335, -4360068, 499778796, 587600402, -1296000335, -37959743, | |
| 298 | -1084203927, 1162902556, 246374600, -515103645, 341724568, | |
| 299 | -702303954, 452229900, 485108287, 1170048553, -1510148355, | |
| 300 | 611133912, 1997927484, -142022671, -724776653, -336090522, | |
| 301 | 708283514, -1409637378, -2052637687, 376055110, 226628105, | |
| 302 | -1714452033, -1776158002, 369167930, 1800807012, 710680889, | |
| 303 | -69951947, -1223849766, -1862239787, 218536127, -656411794, | |
| 304 | -1202269188, 609634805, -224425858, 519797951, 284223080, | |
| 305 | 869408930, 270750206, -544967439, 2097168510, 31650971, -600985417, | |
| 306 | -165303097, -257809088, -1043223971, 1827891621, -156827355, | |
| 307 | 499719603 | |
| 308 | }; | |
| 309 | ||
| 310 | #define IVEC_LEN (nitems(initvector)) | |
| 311 | ||
| 312 | #endif |