radix-sort.h

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