/*
 * Copyright (c) 2020 Red Hat, Inc.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
 * 02110-1301, USA. 
 *
 * $Id: //eng/uds-releases/jasper/src/uds/util/radixSort.h#1 $
 */

#ifndef RADIX_SORT_H
#define RADIX_SORT_H

/*
 * The implementation uses one large object allocated on the heap.  This
 * large object can be reused as many times as desired.  There is no
 * further heap usage by the sorting.
 */
typedef struct radixSorter RadixSorter;

/**
 * Reserve the heap storage needed by the radixSort routine.  The amount of
 * heap space is logarithmically proportional to the number of keys.
 *
 * @param count   The maximum number of keys to be sorted
 * @param sorter  The RadixSorter object is returned here
 *
 * @return UDS_SUCCESS or an error code
 **/
int makeRadixSorter(unsigned int count, RadixSorter **sorter)
  __attribute__((warn_unused_result));

/**
 * Free the heap storage needed by the radixSort routine.
 *
 * @param sorter  The RadixSorter object to free
 **/
void freeRadixSorter(RadixSorter *sorter);

/**
 * Sort pointers to fixed-length keys (arrays of bytes) using a radix sort.
 *
 * The sort implementation is unstable--relative ordering of equal keys is not
 * preserved. The implementation does not use any heap allocation.
 *
 * @param [in] sorter  the heap storage used by the sorting
 * @param      keys    the array of key pointers to sort (modified in place)
 * @param [in] count   the number of keys
 * @param [in] length  the length of every key, in bytes
 *
 * @return UDS_SUCCESS or an error code
 **/
int radixSort(RadixSorter         *sorter,
              const unsigned char *keys[],
              unsigned int         count,
              unsigned short       length)
  __attribute__((warn_unused_result));

#endif /* RADIX_SORT_H */