Mercurial > sdl-ios-xcode

comparison src/stdlib/SDL_qsort.c @ 1668:4da1ee79c9af SDL-1.3

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
more tweaking indent options
author Sam Lantinga <slouken@libsdl.org>
date Mon, 29 May 2006 04:04:35 +0000
parents 782fd950bd46
children
comparison
equal deleted inserted replaced
1667:1fddae038bc8 1668:4da1ee79c9af
264 register int t=*((int*)a); *((int*)a)=*((int*)b); *((int*)b)=t; } 264 register int t=*((int*)a); *((int*)a)=*((int*)b); *((int*)b)=t; }
265 265
266 /* ---------------------------------------------------------------------- */ 266 /* ---------------------------------------------------------------------- */
267 267
268 static char * 268 static char *
269 pivot_big (char *first, char *mid, char *last, size_t size, 269 pivot_big(char *first, char *mid, char *last, size_t size,
270 int compare (const void *, const void *)) 270 int compare(const void *, const void *))
271 { 271 {
272 size_t d = (((last - first) / size) >> 3) * size; 272 size_t d = (((last - first) / size) >> 3) * size;
273 char *m1, *m2, *m3; 273 char *m1, *m2, *m3;
274 { 274 {
275 char *a = first, *b = first + d, *c = first + 2 * d; 275 char *a = first, *b = first + d, *c = first + 2 * d;
276 #ifdef DEBUG_QSORT 276 #ifdef DEBUG_QSORT
277 fprintf (stderr, "< %d %d %d\n", *(int *) a, *(int *) b, *(int *) c); 277 fprintf(stderr, "< %d %d %d\n", *(int *) a, *(int *) b, *(int *) c);
278 #endif 278 #endif
279 m1 = compare (a, b) < 0 ? 279 m1 = compare(a, b) < 0 ?
280 (compare (b, c) < 0 ? b : (compare (a, c) < 0 ? c : a)) 280 (compare(b, c) < 0 ? b : (compare(a, c) < 0 ? c : a))
281 : (compare (a, c) < 0 ? a : (compare (b, c) < 0 ? c : b)); 281 : (compare(a, c) < 0 ? a : (compare(b, c) < 0 ? c : b));
282 } 282 }
283 { 283 {
284 char *a = mid - d, *b = mid, *c = mid + d; 284 char *a = mid - d, *b = mid, *c = mid + d;
285 #ifdef DEBUG_QSORT 285 #ifdef DEBUG_QSORT
286 fprintf (stderr, ". %d %d %d\n", *(int *) a, *(int *) b, *(int *) c); 286 fprintf(stderr, ". %d %d %d\n", *(int *) a, *(int *) b, *(int *) c);
287 #endif 287 #endif
288 m2 = compare (a, b) < 0 ? 288 m2 = compare(a, b) < 0 ?
289 (compare (b, c) < 0 ? b : (compare (a, c) < 0 ? c : a)) 289 (compare(b, c) < 0 ? b : (compare(a, c) < 0 ? c : a))
290 : (compare (a, c) < 0 ? a : (compare (b, c) < 0 ? c : b)); 290 : (compare(a, c) < 0 ? a : (compare(b, c) < 0 ? c : b));
291 } 291 }
292 { 292 {
293 char *a = last - 2 * d, *b = last - d, *c = last; 293 char *a = last - 2 * d, *b = last - d, *c = last;
294 #ifdef DEBUG_QSORT 294 #ifdef DEBUG_QSORT
295 fprintf (stderr, "> %d %d %d\n", *(int *) a, *(int *) b, *(int *) c); 295 fprintf(stderr, "> %d %d %d\n", *(int *) a, *(int *) b, *(int *) c);
296 #endif 296 #endif
297 m3 = compare (a, b) < 0 ? 297 m3 = compare(a, b) < 0 ?
298 (compare (b, c) < 0 ? b : (compare (a, c) < 0 ? c : a)) 298 (compare(b, c) < 0 ? b : (compare(a, c) < 0 ? c : a))
299 : (compare (a, c) < 0 ? a : (compare (b, c) < 0 ? c : b)); 299 : (compare(a, c) < 0 ? a : (compare(b, c) < 0 ? c : b));
300 } 300 }
301 #ifdef DEBUG_QSORT 301 #ifdef DEBUG_QSORT
302 fprintf (stderr, "-> %d %d %d\n", *(int *) m1, *(int *) m2, *(int *) m3); 302 fprintf(stderr, "-> %d %d %d\n", *(int *) m1, *(int *) m2, *(int *) m3);
303 #endif 303 #endif
304 return compare (m1, m2) < 0 ? 304 return compare(m1, m2) < 0 ?
305 (compare (m2, m3) < 0 ? m2 : (compare (m1, m3) < 0 ? m3 : m1)) 305 (compare(m2, m3) < 0 ? m2 : (compare(m1, m3) < 0 ? m3 : m1))
306 : (compare (m1, m3) < 0 ? m1 : (compare (m2, m3) < 0 ? m3 : m2)); 306 : (compare(m1, m3) < 0 ? m1 : (compare(m2, m3) < 0 ? m3 : m2));
307 } 307 }
308 308
309 /* ---------------------------------------------------------------------- */ 309 /* ---------------------------------------------------------------------- */
310 310
311 static void 311 static void
312 qsort_nonaligned (void *base, size_t nmemb, size_t size, 312 qsort_nonaligned(void *base, size_t nmemb, size_t size,
313 int (*compare) (const void *, const void *)) 313 int (*compare) (const void *, const void *))
314 { 314 {
315 315
316 stack_entry stack[STACK_SIZE]; 316 stack_entry stack[STACK_SIZE];
317 int stacktop = 0; 317 int stacktop = 0;
318 char *first, *last; 318 char *first, *last;
319 char *pivot = malloc (size); 319 char *pivot = malloc(size);
320 size_t trunc = TRUNC_nonaligned * size; 320 size_t trunc = TRUNC_nonaligned * size;
321 assert (pivot != 0); 321 assert(pivot != 0);
322 322
323 first = (char *) base; 323 first = (char *) base;
324 last = first + (nmemb - 1) * size; 324 last = first + (nmemb - 1) * size;
325 325
326 if ((size_t) (last - first) > trunc) { 326 if ((size_t) (last - first) > trunc) {
327 char *ffirst = first, *llast = last; 327 char *ffirst = first, *llast = last;
328 while (1) { 328 while (1) {
329 /* Select pivot */ 329 /* Select pivot */
330 { 330 {
331 char *mid = first + size * ((last - first) / size >> 1); 331 char *mid = first + size * ((last - first) / size >> 1);
332 Pivot (SWAP_nonaligned, size); 332 Pivot(SWAP_nonaligned, size);
333 memcpy (pivot, mid, size); 333 memcpy(pivot, mid, size);
334 } 334 }
335 /* Partition. */ 335 /* Partition. */
336 Partition (SWAP_nonaligned, size); 336 Partition(SWAP_nonaligned, size);
337 /* Prepare to recurse/iterate. */ 337 /* Prepare to recurse/iterate. */
338 Recurse (trunc)} 338 Recurse(trunc)}
339 } 339 }
340 PreInsertion (SWAP_nonaligned, TRUNC_nonaligned, size); 340 PreInsertion(SWAP_nonaligned, TRUNC_nonaligned, size);
341 Insertion (SWAP_nonaligned); 341 Insertion(SWAP_nonaligned);
342 free (pivot); 342 free(pivot);
343 } 343 }
344 344
345 static void 345 static void
346 qsort_aligned (void *base, size_t nmemb, size_t size, 346 qsort_aligned(void *base, size_t nmemb, size_t size,
347 int (*compare) (const void *, const void *)) 347 int (*compare) (const void *, const void *))
348 { 348 {
349 349
350 stack_entry stack[STACK_SIZE]; 350 stack_entry stack[STACK_SIZE];
351 int stacktop = 0; 351 int stacktop = 0;
352 char *first, *last; 352 char *first, *last;
353 char *pivot = malloc (size); 353 char *pivot = malloc(size);
354 size_t trunc = TRUNC_aligned * size; 354 size_t trunc = TRUNC_aligned * size;
355 assert (pivot != 0); 355 assert(pivot != 0);
356 356
357 first = (char *) base; 357 first = (char *) base;
358 last = first + (nmemb - 1) * size; 358 last = first + (nmemb - 1) * size;
359 359
360 if ((size_t) (last - first) > trunc) { 360 if ((size_t) (last - first) > trunc) {
361 char *ffirst = first, *llast = last; 361 char *ffirst = first, *llast = last;
362 while (1) { 362 while (1) {
363 /* Select pivot */ 363 /* Select pivot */
364 { 364 {
365 char *mid = first + size * ((last - first) / size >> 1); 365 char *mid = first + size * ((last - first) / size >> 1);
366 Pivot (SWAP_aligned, size); 366 Pivot(SWAP_aligned, size);
367 memcpy (pivot, mid, size); 367 memcpy(pivot, mid, size);
368 } 368 }
369 /* Partition. */ 369 /* Partition. */
370 Partition (SWAP_aligned, size); 370 Partition(SWAP_aligned, size);
371 /* Prepare to recurse/iterate. */ 371 /* Prepare to recurse/iterate. */
372 Recurse (trunc)} 372 Recurse(trunc)}
373 } 373 }
374 PreInsertion (SWAP_aligned, TRUNC_aligned, size); 374 PreInsertion(SWAP_aligned, TRUNC_aligned, size);
375 Insertion (SWAP_aligned); 375 Insertion(SWAP_aligned);
376 free (pivot); 376 free(pivot);
377 } 377 }
378 378
379 static void 379 static void
380 qsort_words (void *base, size_t nmemb, 380 qsort_words(void *base, size_t nmemb,
381 int (*compare) (const void *, const void *)) 381 int (*compare) (const void *, const void *))
382 { 382 {
383 383
384 stack_entry stack[STACK_SIZE]; 384 stack_entry stack[STACK_SIZE];
385 int stacktop = 0; 385 int stacktop = 0;
386 char *first, *last; 386 char *first, *last;
387 char *pivot = malloc (WORD_BYTES); 387 char *pivot = malloc(WORD_BYTES);
388 assert (pivot != 0); 388 assert(pivot != 0);
389 389
390 first = (char *) base; 390 first = (char *) base;
391 last = first + (nmemb - 1) * WORD_BYTES; 391 last = first + (nmemb - 1) * WORD_BYTES;
392 392
393 if (last - first > TRUNC_words) { 393 if (last - first > TRUNC_words) {
394 char *ffirst = first, *llast = last; 394 char *ffirst = first, *llast = last;
395 while (1) { 395 while (1) {
396 #ifdef DEBUG_QSORT 396 #ifdef DEBUG_QSORT
397 fprintf (stderr, "Doing %d:%d: ", 397 fprintf(stderr, "Doing %d:%d: ",
398 (first - (char *) base) / WORD_BYTES, 398 (first - (char *) base) / WORD_BYTES,
399 (last - (char *) base) / WORD_BYTES); 399 (last - (char *) base) / WORD_BYTES);
400 #endif 400 #endif
401 /* Select pivot */ 401 /* Select pivot */
402 { 402 {
403 char *mid = 403 char *mid =
404 first + WORD_BYTES * ((last - first) / (2 * WORD_BYTES)); 404 first + WORD_BYTES * ((last - first) / (2 * WORD_BYTES));
405 Pivot (SWAP_words, WORD_BYTES); 405 Pivot(SWAP_words, WORD_BYTES);
406 *(int *) pivot = *(int *) mid; 406 *(int *) pivot = *(int *) mid;
407 } 407 }
408 #ifdef DEBUG_QSORT 408 #ifdef DEBUG_QSORT
409 fprintf (stderr, "pivot=%d\n", *(int *) pivot); 409 fprintf(stderr, "pivot=%d\n", *(int *) pivot);
410 #endif 410 #endif
411 /* Partition. */ 411 /* Partition. */
412 Partition (SWAP_words, WORD_BYTES); 412 Partition(SWAP_words, WORD_BYTES);
413 /* Prepare to recurse/iterate. */ 413 /* Prepare to recurse/iterate. */
414 Recurse (TRUNC_words)} 414 Recurse(TRUNC_words)}
415 } 415 }
416 PreInsertion (SWAP_words, (TRUNC_words / WORD_BYTES), WORD_BYTES); 416 PreInsertion(SWAP_words, (TRUNC_words / WORD_BYTES), WORD_BYTES);
417 /* Now do insertion sort. */ 417 /* Now do insertion sort. */
418 last = ((char *) base) + nmemb * WORD_BYTES; 418 last = ((char *) base) + nmemb * WORD_BYTES;
419 for (first = ((char *) base) + WORD_BYTES; first != last; 419 for (first = ((char *) base) + WORD_BYTES; first != last;
420 first += WORD_BYTES) { 420 first += WORD_BYTES) {
421 /* Find the right place for |first|. My apologies for var reuse */ 421 /* Find the right place for |first|. My apologies for var reuse */
422 int *pl = (int *) (first - WORD_BYTES), *pr = (int *) first; 422 int *pl = (int *) (first - WORD_BYTES), *pr = (int *) first;
423 *(int *) pivot = *(int *) first; 423 *(int *) pivot = *(int *) first;
424 for (; compare (pl, pivot) > 0; pr = pl, --pl) { 424 for (; compare(pl, pivot) > 0; pr = pl, --pl) {
425 *pr = *pl; 425 *pr = *pl;
426 } 426 }
427 if (pr != (int *) first) 427 if (pr != (int *) first)
428 *pr = *(int *) pivot; 428 *pr = *(int *) pivot;
429 } 429 }
430 free (pivot); 430 free(pivot);
431 } 431 }
432 432
433 /* ---------------------------------------------------------------------- */ 433 /* ---------------------------------------------------------------------- */
434 434
435 void 435 void
436 qsort (void *base, size_t nmemb, size_t size, 436 qsort(void *base, size_t nmemb, size_t size,
437 int (*compare) (const void *, const void *)) 437 int (*compare) (const void *, const void *))
438 { 438 {
439 439
440 if (nmemb <= 1) 440 if (nmemb <= 1)
441 return; 441 return;
442 if (((uintptr_t) base | size) & (WORD_BYTES - 1)) 442 if (((uintptr_t) base | size) & (WORD_BYTES - 1))
443 qsort_nonaligned (base, nmemb, size, compare); 443 qsort_nonaligned(base, nmemb, size, compare);
444 else if (size != WORD_BYTES) 444 else if (size != WORD_BYTES)
445 qsort_aligned (base, nmemb, size, compare); 445 qsort_aligned(base, nmemb, size, compare);
446 else 446 else
447 qsort_words (base, nmemb, compare); 447 qsort_words(base, nmemb, compare);
448 } 448 }
449 449
450 #endif /* !HAVE_QSORT */ 450 #endif /* !HAVE_QSORT */
451 /* vi: set ts=4 sw=4 expandtab: */ 451 /* vi: set ts=4 sw=4 expandtab: */