aboutsummaryrefslogtreecommitdiff
path: root/mp/src/tier1/qsort_s.cpp
diff options
context:
space:
mode:
authorJørgen P. Tjernø <[email protected]>2013-12-02 19:31:46 -0800
committerJørgen P. Tjernø <[email protected]>2013-12-02 19:46:31 -0800
commitf56bb35301836e56582a575a75864392a0177875 (patch)
treede61ddd39de3e7df52759711950b4c288592f0dc /mp/src/tier1/qsort_s.cpp
parentMark some more files as text. (diff)
downloadsource-sdk-2013-f56bb35301836e56582a575a75864392a0177875.tar.xz
source-sdk-2013-f56bb35301836e56582a575a75864392a0177875.zip
Fix line endings. WHAMMY.
Diffstat (limited to 'mp/src/tier1/qsort_s.cpp')
-rw-r--r--mp/src/tier1/qsort_s.cpp224
1 files changed, 112 insertions, 112 deletions
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 <stddef.h> /* 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 <stddef.h> /* 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;
+ }
+ }
+}
+
+
generated by cgit v1.2.3 (git 2.25.1) at 2026-03-11 09:16:47 +0000