1 /* 2 3 Copyright (C) 2008-2021 Michele Martone 4 5 This file is part of librsb. 6 7 librsb is free software; you can redistribute it and/or modify it 8 under the terms of the GNU Lesser General Public License as published 9 by the Free Software Foundation; either version 3 of the License, or 10 (at your option) any later version. 11 12 librsb is distributed in the hope that it will be useful, but WITHOUT 13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public 15 License for more details. 16 17 You should have received a copy of the GNU Lesser General Public 18 License along with librsb; see the file COPYING. 19 If not, see <http://www.gnu.org/licenses/>. 20 21 */ 22 /* @cond INNERDOC */ 23 /*! 24 * @file 25 * @author Michele Martone 26 * @brief 27 * This source file contains sorting functions. 28 * */ 29 30 #ifndef RSB_SRT_H_INCLUDED 31 #define RSB_SRT_H_INCLUDED 32 33 #include "rsb_internals.h" /* rsb_coo_matrix_t */ 34 35 rsb_err_t rsb__do_util_sortcoo( 36 void *VA, rsb_coo_idx_t * IA, rsb_coo_idx_t * JA, 37 rsb_coo_idx_t m, rsb_coo_idx_t k, 38 rsb_nnz_idx_t nnz, rsb_type_t typecode, 39 const struct rsb_mtx_partitioning_info_t * pinfop , rsb_flags_t flags, void * WA, size_t wb); 40 41 rsb_err_t rsb__do_index_based_bcsr_sort( 42 rsb_coo_idx_t * IA, rsb_coo_idx_t * JA, void * VA, 43 rsb_coo_idx_t * rIA, rsb_coo_idx_t * rJA, void * rVA, 44 rsb_coo_idx_t m, rsb_coo_idx_t k, 45 rsb_coo_idx_t br, rsb_coo_idx_t bc, 46 rsb_nnz_idx_t nnz, 47 rsb_type_t typecode, 48 rsb_flags_t flags 49 ,enum rsb_op_flags_t op_flags 50 , void * WA, size_t wb); 51 52 rsb_nnz_idx_t rsb__asymmetric_z_index( const rsb_coo_idx_t i, const rsb_coo_idx_t j, rsb_coo_idx_t m, rsb_coo_idx_t k , int ml, int kl); 53 void rsb__asymmetric_z_nnz_indices( const rsb_coo_idx_t i, const rsb_coo_idx_t j, rsb_coo_idx_t m, rsb_coo_idx_t k , int ml, int kl, rsb_nnz_idx_t * a , rsb_nnz_idx_t * b ); 54 55 rsb_err_t rsb__do_index_based_bcsr_msort( 56 rsb_coo_idx_t * IA, rsb_coo_idx_t * JA, void * VA, 57 rsb_coo_idx_t m, rsb_coo_idx_t k, 58 rsb_coo_idx_t br, rsb_coo_idx_t bc, 59 rsb_nnz_idx_t nnz, rsb_type_t typecode, rsb_flags_t flags 60 ,enum rsb_op_flags_t op_flags 61 ,void * WA, size_t wb 62 ); 63 64 rsb_err_t rsb__do_index_based_recursive_bcsr_sort( 65 const rsb_coo_idx_t * IA, const rsb_coo_idx_t * JA, const void * VA, 66 rsb_coo_idx_t * rIA, rsb_coo_idx_t * rJA, void * rVA, 67 rsb_coo_idx_t m, rsb_coo_idx_t k, 68 rsb_coo_idx_t br, rsb_coo_idx_t bc, 69 rsb_nnz_idx_t nnz, 70 rsb_type_t typecode, 71 rsb_flags_t flags 72 ,enum rsb_op_flags_t op_flags 73 ); 74 75 rsb_err_t rsb__do_nnz_index_based_sort_and_permute( 76 const rsb_coo_idx_t * IA, const rsb_coo_idx_t * JA, const void * VA, 77 rsb_coo_idx_t * rIA, rsb_coo_idx_t * rJA, void * rVA, 78 rsb_nnz_idx_t * K, rsb_nnz_idx_t nnz, rsb_type_t typecode, rsb_flags_t flags 79 ,enum rsb_op_flags_t op_flags 80 ); 81 82 void rsb__do_util_compact_permutation_nnz_idx_t_array(rsb_nnz_idx_t * K, rsb_nnz_idx_t nnz); 83 void rsb__do_util_compact_permutation_coo_idx_t_array(rsb_coo_idx_t * K, rsb_nnz_idx_t nnz); 84 rsb_err_t rsb__do_coo_index_sort_on_rows_array_make( 85 rsb_coo_idx_t * K, const rsb_coo_idx_t * IA, 86 const rsb_coo_idx_t m, const rsb_coo_idx_t br, 87 const rsb_nnz_idx_t nnz, const rsb_type_t typecode); 88 89 rsb_err_t rsb__do_nnz_index_based_bcsr_msort( 90 rsb_coo_idx_t * rIA, rsb_coo_idx_t * rJA, void * rVA, 91 rsb_coo_idx_t m, rsb_coo_idx_t k, 92 rsb_coo_idx_t br, rsb_coo_idx_t bc, 93 rsb_nnz_idx_t nnz, rsb_type_t typecode, rsb_flags_t flags 94 ,enum rsb_op_flags_t op_flags 95 ,void * WA, size_t wb); 96 97 rsb_err_t rsb__do_double_pass_nnz_index_based_bcsr_msort( 98 rsb_coo_idx_t * rIA, rsb_coo_idx_t * rJA, void * rVA, 99 rsb_coo_idx_t m, rsb_coo_idx_t k, 100 rsb_coo_idx_t br, rsb_coo_idx_t bc, 101 rsb_nnz_idx_t nnz, rsb_type_t typecode, rsb_flags_t flags);/* FIXME */ 102 103 rsb_err_t rsb__do_nnz_index_sort_array_make( 104 rsb_nnz_idx_t * K, const rsb_coo_idx_t * IA, const rsb_coo_idx_t * JA, 105 rsb_coo_idx_t m, rsb_coo_idx_t k, 106 rsb_coo_idx_t roffset, 107 rsb_coo_idx_t br, rsb_coo_idx_t bc, 108 rsb_nnz_idx_t nnz, 109 rsb_type_t typecode, 110 rsb_flags_t flags, 111 int want_recursive_sort 112 ,enum rsb_op_flags_t op_flags 113 /*, int want_rows_sort */); 114 115 rsb_err_t rsb__do_double_coo_index_sort_array_make( 116 rsb_coo_idx_t * K, const rsb_coo_idx_t * IA, const rsb_coo_idx_t * JA, 117 rsb_coo_idx_t m, rsb_coo_idx_t k, 118 rsb_coo_idx_t roffset, 119 rsb_coo_idx_t br, rsb_coo_idx_t bc, 120 rsb_nnz_idx_t nnz, 121 rsb_type_t typecode, 122 rsb_flags_t flags, 123 int want_recursive_sort 124 ,enum rsb_op_flags_t op_flags 125 /*, int want_rows_sort */); 126 127 rsb_nnz_idx_t rsb__nearest_power_of_two( const rsb_nnz_idx_t n ); 128 129 void rsb__asymmetric_z_indices_encode( const rsb_coo_idx_t i, const rsb_coo_idx_t j, rsb_coo_idx_t m, rsb_coo_idx_t k , int ml, int kl , rsb_coo_idx_t *h, rsb_coo_idx_t *l); 130 rsb_err_t rsb__do_index_based_z_morton_sort( 131 const rsb_coo_idx_t * IA, const rsb_coo_idx_t * JA, const void * VA, 132 rsb_coo_idx_t * rIA, rsb_coo_idx_t * rJA, void * rVA, 133 rsb_coo_idx_t m, rsb_coo_idx_t k, 134 rsb_nnz_idx_t nnz, 135 rsb_type_t typecode 136 ,enum rsb_op_flags_t op_flags 137 ); 138 139 #define RSB_DO_REQUIRE_BYTES_FOR_INDEX_BASED_SORT_ONE_PASS(NNZ,M,K,BR,BC) (((NNZ)+1) * sizeof(rsb_nnz_idx_t) * 2) 140 #define RSB_DO_REQUIRE_BYTES_FOR_INDEX_BASED_SORT_TWO_PASS(NNZ,M,K,BR,BC) \ 141 RSB_MAX((((NNZ)+1) * sizeof(rsb_coo_idx_t) * 2),(K)*(BR) * sizeof(rsb_nnz_idx_t) * 2) 142 143 144 #define RSB_DO_REQUIRE_BYTES_FOR_INDEX_BASED_SORT(NNZ,M,K,BR,BC) \ 145 RSB_MAX( \ 146 RSB_DO_REQUIRE_BYTES_FOR_INDEX_BASED_SORT_ONE_PASS(NNZ,M,K,BR,BC), \ 147 RSB_DO_REQUIRE_BYTES_FOR_INDEX_BASED_SORT_TWO_PASS(NNZ,M,K,BR,BC)) 148 #endif /* RSB_SRT_H_INCLUDED */ 149 /* @endcond */ 150