1*17b1a73fSMike Snitzer /* SPDX-License-Identifier: GPL-2.0-only */ 2*17b1a73fSMike Snitzer /* 3*17b1a73fSMike Snitzer * Copyright 2023 Red Hat 4*17b1a73fSMike Snitzer */ 5*17b1a73fSMike Snitzer 6*17b1a73fSMike Snitzer #ifndef UDS_RADIX_SORT_H 7*17b1a73fSMike Snitzer #define UDS_RADIX_SORT_H 8*17b1a73fSMike Snitzer 9*17b1a73fSMike Snitzer /* 10*17b1a73fSMike Snitzer * Radix sort is implemented using an American Flag sort, an unstable, in-place 8-bit radix 11*17b1a73fSMike Snitzer * exchange sort. This is adapted from the algorithm in the paper by Peter M. McIlroy, Keith 12*17b1a73fSMike Snitzer * Bostic, and M. Douglas McIlroy, "Engineering Radix Sort". 13*17b1a73fSMike Snitzer * 14*17b1a73fSMike Snitzer * http://www.usenix.org/publications/compsystems/1993/win_mcilroy.pdf 15*17b1a73fSMike Snitzer */ 16*17b1a73fSMike Snitzer 17*17b1a73fSMike Snitzer struct radix_sorter; 18*17b1a73fSMike Snitzer 19*17b1a73fSMike Snitzer int __must_check uds_make_radix_sorter(unsigned int count, struct radix_sorter **sorter); 20*17b1a73fSMike Snitzer 21*17b1a73fSMike Snitzer void uds_free_radix_sorter(struct radix_sorter *sorter); 22*17b1a73fSMike Snitzer 23*17b1a73fSMike Snitzer int __must_check uds_radix_sort(struct radix_sorter *sorter, const unsigned char *keys[], 24*17b1a73fSMike Snitzer unsigned int count, unsigned short length); 25*17b1a73fSMike Snitzer 26*17b1a73fSMike Snitzer #endif /* UDS_RADIX_SORT_H */ 27