From f56bb35301836e56582a575a75864392a0177875 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?J=C3=B8rgen=20P=2E=20Tjern=C3=B8?= Date: Mon, 2 Dec 2013 19:31:46 -0800 Subject: Fix line endings. WHAMMY. --- mp/src/tier1/qsort_s.cpp | 224 +++++++++++++++++++++++------------------------ 1 file changed, 112 insertions(+), 112 deletions(-) (limited to 'mp/src/tier1/qsort_s.cpp') diff --git a/mp/src/tier1/qsort_s.cpp b/mp/src/tier1/qsort_s.cpp index 6c5b2a95..8222b32b 100644 --- a/mp/src/tier1/qsort_s.cpp +++ b/mp/src/tier1/qsort_s.cpp @@ -1,112 +1,112 @@ -//========= Copyright Valve Corporation, All rights reserved. ============// -/******************************************************************/ -/* qsort.c -- Non-Recursive ANSI Quicksort function */ -/* */ -/* Public domain by Raymond Gardner, Englewood CO February 1991 */ -/* */ -/* Usage: */ -/* qsort(base, nbr_elements, width_bytes, compare_function); */ -/* void *base; */ -/* size_t nbr_elements, width_bytes; */ -/* int (*compare_function)(const void *, const void *); */ -/* */ -/* Sorts an array starting at base, of length nbr_elements, each */ -/* element of size width_bytes, ordered via compare_function, */ -/* which is called as (*compare_function)(ptr_to_element1, */ -/* ptr_to_element2) and returns < 0 if element1 < element2, */ -/* 0 if element1 = element2, > 0 if element1 > element2. */ -/* Most refinements are due to R. Sedgewick. See "Implementing */ -/* Quicksort Programs", Comm. ACM, Oct. 1978, and Corrigendum, */ -/* Comm. ACM, June 1979. */ -/******************************************************************/ - -// modified to take (and use) a context object, ala Microsoft's qsort_s -// "extension" to the stdlib - -#include /* for size_t definition */ - -/* -** swap nbytes between a and b -*/ - -static void swap_bytes(char *a, char *b, size_t nbytes) -{ - char tmp; - do { - tmp = *a; *a++ = *b; *b++ = tmp; - } while ( --nbytes ); -} - -#define SWAP(a, b) (swap_bytes((char *)(a), (char *)(b), size)) - -#define COMP(ctx, a, b) ((*comp)((void *)ctx, (void *)(a), (void *)(b))) - -#define T 7 /* subfiles of T or fewer elements will */ - /* be sorted by a simple insertion sort */ - /* Note! T must be at least 3 */ - -extern "C" void qsort_s(void *basep, size_t nelems, size_t size, - int (*comp)(void *, const void *, const void *), - void *ctx) -{ - char *stack[40], **sp; /* stack and stack pointer */ - char *i, *j, *limit; /* scan and limit pointers */ - size_t thresh; /* size of T elements in bytes */ - char *base; /* base pointer as char * */ - - base = (char *)basep; /* set up char * base pointer */ - thresh = T * size; /* init threshold */ - sp = stack; /* init stack pointer */ - limit = base + nelems * size;/* pointer past end of array */ - for ( ;; ) { /* repeat until break... */ - if ( limit - base > thresh ) { /* if more than T elements */ - /* swap base with middle */ - SWAP((((limit-base)/size)/2)*size+base, base); - i = base + size; /* i scans left to right */ - j = limit - size; /* j scans right to left */ - if ( COMP(ctx, i, j) > 0 ) /* Sedgewick's */ - SWAP(i, j); /* three-element sort */ - if ( COMP(ctx, base, j) > 0 )/* sets things up */ - SWAP(base, j); /* so that */ - if ( COMP(ctx, i, base) > 0 )/* *i <= *base <= *j */ - SWAP(i, base); /* *base is pivot element */ - for ( ;; ) { /* loop until break */ - do /* move i right */ - i += size; /* until *i >= pivot */ - while ( COMP(ctx, i, base) < 0 ); - do /* move j left */ - j -= size; /* until *j <= pivot */ - while ( COMP(ctx, j, base) > 0 ); - if ( i > j ) /* if pointers crossed */ - break; /* break loop */ - SWAP(i, j); /* else swap elements, keep scanning*/ - } - SWAP(base, j); /* move pivot into correct place */ - if ( j - base > limit - i ) { /* if left subfile larger */ - sp[0] = base; /* stack left subfile base */ - sp[1] = j; /* and limit */ - base = i; /* sort the right subfile */ - } else { /* else right subfile larger*/ - sp[0] = i; /* stack right subfile base */ - sp[1] = limit; /* and limit */ - limit = j; /* sort the left subfile */ - } - sp += 2; /* increment stack pointer */ - } else { /* else subfile is small, use insertion sort */ - for ( j = base, i = j+size; i < limit; j = i, i += size ) - for ( ; COMP(ctx, j, j+size) > 0; j -= size ) { - SWAP(j, j+size); - if ( j == base ) - break; - } - if ( sp != stack ) { /* if any entries on stack */ - sp -= 2; /* pop the base and limit */ - base = sp[0]; - limit = sp[1]; - } else /* else stack empty, done */ - break; - } - } -} - - +//========= Copyright Valve Corporation, All rights reserved. ============// +/******************************************************************/ +/* qsort.c -- Non-Recursive ANSI Quicksort function */ +/* */ +/* Public domain by Raymond Gardner, Englewood CO February 1991 */ +/* */ +/* Usage: */ +/* qsort(base, nbr_elements, width_bytes, compare_function); */ +/* void *base; */ +/* size_t nbr_elements, width_bytes; */ +/* int (*compare_function)(const void *, const void *); */ +/* */ +/* Sorts an array starting at base, of length nbr_elements, each */ +/* element of size width_bytes, ordered via compare_function, */ +/* which is called as (*compare_function)(ptr_to_element1, */ +/* ptr_to_element2) and returns < 0 if element1 < element2, */ +/* 0 if element1 = element2, > 0 if element1 > element2. */ +/* Most refinements are due to R. Sedgewick. See "Implementing */ +/* Quicksort Programs", Comm. ACM, Oct. 1978, and Corrigendum, */ +/* Comm. ACM, June 1979. */ +/******************************************************************/ + +// modified to take (and use) a context object, ala Microsoft's qsort_s +// "extension" to the stdlib + +#include /* for size_t definition */ + +/* +** swap nbytes between a and b +*/ + +static void swap_bytes(char *a, char *b, size_t nbytes) +{ + char tmp; + do { + tmp = *a; *a++ = *b; *b++ = tmp; + } while ( --nbytes ); +} + +#define SWAP(a, b) (swap_bytes((char *)(a), (char *)(b), size)) + +#define COMP(ctx, a, b) ((*comp)((void *)ctx, (void *)(a), (void *)(b))) + +#define T 7 /* subfiles of T or fewer elements will */ + /* be sorted by a simple insertion sort */ + /* Note! T must be at least 3 */ + +extern "C" void qsort_s(void *basep, size_t nelems, size_t size, + int (*comp)(void *, const void *, const void *), + void *ctx) +{ + char *stack[40], **sp; /* stack and stack pointer */ + char *i, *j, *limit; /* scan and limit pointers */ + size_t thresh; /* size of T elements in bytes */ + char *base; /* base pointer as char * */ + + base = (char *)basep; /* set up char * base pointer */ + thresh = T * size; /* init threshold */ + sp = stack; /* init stack pointer */ + limit = base + nelems * size;/* pointer past end of array */ + for ( ;; ) { /* repeat until break... */ + if ( limit - base > thresh ) { /* if more than T elements */ + /* swap base with middle */ + SWAP((((limit-base)/size)/2)*size+base, base); + i = base + size; /* i scans left to right */ + j = limit - size; /* j scans right to left */ + if ( COMP(ctx, i, j) > 0 ) /* Sedgewick's */ + SWAP(i, j); /* three-element sort */ + if ( COMP(ctx, base, j) > 0 )/* sets things up */ + SWAP(base, j); /* so that */ + if ( COMP(ctx, i, base) > 0 )/* *i <= *base <= *j */ + SWAP(i, base); /* *base is pivot element */ + for ( ;; ) { /* loop until break */ + do /* move i right */ + i += size; /* until *i >= pivot */ + while ( COMP(ctx, i, base) < 0 ); + do /* move j left */ + j -= size; /* until *j <= pivot */ + while ( COMP(ctx, j, base) > 0 ); + if ( i > j ) /* if pointers crossed */ + break; /* break loop */ + SWAP(i, j); /* else swap elements, keep scanning*/ + } + SWAP(base, j); /* move pivot into correct place */ + if ( j - base > limit - i ) { /* if left subfile larger */ + sp[0] = base; /* stack left subfile base */ + sp[1] = j; /* and limit */ + base = i; /* sort the right subfile */ + } else { /* else right subfile larger*/ + sp[0] = i; /* stack right subfile base */ + sp[1] = limit; /* and limit */ + limit = j; /* sort the left subfile */ + } + sp += 2; /* increment stack pointer */ + } else { /* else subfile is small, use insertion sort */ + for ( j = base, i = j+size; i < limit; j = i, i += size ) + for ( ; COMP(ctx, j, j+size) > 0; j -= size ) { + SWAP(j, j+size); + if ( j == base ) + break; + } + if ( sp != stack ) { /* if any entries on stack */ + sp -= 2; /* pop the base and limit */ + base = sp[0]; + limit = sp[1]; + } else /* else stack empty, done */ + break; + } + } +} + + -- cgit v1.2.3