Line data    Source code

       1             : //------------------------------------------------------------------------------
       2             : // LG_qsort_2: sort a 2-by-n list of integers, using A[0:1][ ] as the key
       3             : //------------------------------------------------------------------------------
       4             : 
       5             : // LAGraph, (c) 2019-2022 by The LAGraph Contributors, All Rights Reserved.
       6             : // SPDX-License-Identifier: BSD-2-Clause
       7             : //
       8             : // For additional details (including references to third party source code and
       9             : // other files) see the LICENSE file or contact permission@sei.cmu.edu. See
      10             : // Contributors.txt for a full list of contributors. Created, in part, with
      11             : // funding and support from the U.S. Government (see Acknowledgments.txt file).
      12             : // DM22-0790
      13             : 
      14             : // Contributed by Timothy A. Davis, Texas A&M University
      15             : 
      16             : //------------------------------------------------------------------------------
      17             : 
      18             : #include "LG_internal.h"
      19             : 
      20             : // returns true if A [a] < B [b]
      21             : #define LG_lt(A,a,B,b)                  \
      22             :     LG_lt_2 (A ## _0, A ## _1, a, B ## _0, B ## _1, b)
      23             : 
      24             : // argument list for calling a function
      25             : #define LG_arg(A)                       \
      26             :     A ## _0, A ## _1
      27             : 
      28             : // argument list for calling a function, with offset
      29             : #define LG_arg_offset(A,x)              \
      30             :     A ## _0 + (x), A ## _1 + (x)
      31             : 
      32             : // argument list for defining a function
      33             : #define LG_args(A)                      \
      34             :     int64_t *LG_RESTRICT A ## _0,       \
      35             :     int64_t *LG_RESTRICT A ## _1
      36             : 
      37             : // each entry has a 2-integer key
      38             : #define LG_K 2
      39             : 
      40             : // swap A [a] and A [b]
      41             : #define LG_swap(A,a,b)                                                        \
      42             : {                                                                             \
      43             :     int64_t t0 = A ## _0 [a] ; A ## _0 [a] = A ## _0 [b] ; A ## _0 [b] = t0 ; \
      44             :     int64_t t1 = A ## _1 [a] ; A ## _1 [a] = A ## _1 [b] ; A ## _1 [b] = t1 ; \
      45             : }
      46             : 
      47             : #define LG_partition LG_partition_2
      48             : #define LG_quicksort LG_quicksort_2
      49             : 
      50             : #include "LG_qsort_template.h"
      51             : 
      52        1721 : void LG_qsort_2     // sort array A of size 2-by-n, using 2 keys (A [0:1][])
      53             : (
      54             :     int64_t *LG_RESTRICT A_0,       // size n array
      55             :     int64_t *LG_RESTRICT A_1,       // size n array
      56             :     const int64_t n
      57             : )
      58             : {
      59        1721 :     uint64_t seed = n ;
      60        1721 :     LG_quicksort (LG_arg (A), n, &seed, NULL) ;
      61        1721 : }