drivers/md/dm-vdo/indexer/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
  17 struct radix_sorter;
  18
  19 int __must_check uds_make_radix_sorter(unsigned int count, struct radix_sorter **sorter);
  20
  21 void uds_free_radix_sorter(struct radix_sorter *sorter);
  22
  23 int __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 */