drivers/event/dsw/dsw_sort.h

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  * Copyright(c) 2018 Ericsson AB
   3  */
   4
   5 #ifndef _DSW_SORT_
   6 #define _DSW_SORT_
   7
   8 #include <string.h>
   9
  10 #include <rte_common.h>
  11
  12 #define DSW_ARY_ELEM_PTR(_ary, _idx, _elem_size)        \
  13         RTE_PTR_ADD(_ary, (_idx) * (_elem_size))
  14
  15 #define DSW_ARY_ELEM_SWAP(_ary, _a_idx, _b_idx, _elem_size)             \
  16         do {                                                            \
  17                 char tmp[_elem_size];                                   \
  18                 void *_a_ptr = DSW_ARY_ELEM_PTR(_ary, _a_idx, _elem_size); \
  19                 void *_b_ptr = DSW_ARY_ELEM_PTR(_ary, _b_idx, _elem_size); \
  20                 memcpy(tmp, _a_ptr, _elem_size);                        \
  21                 memcpy(_a_ptr, _b_ptr, _elem_size);                     \
  22                 memcpy(_b_ptr, tmp, _elem_size);                        \
  23         } while (0)
  24
  25 static inline void
  26 dsw_insertion_sort(void *ary, uint16_t len, uint16_t elem_size,
  27                    int (*cmp_fn)(const void *, const void *))
  28 {
  29         uint16_t i;
  30
  31         for (i = 1; i < len; i++) {
  32                 uint16_t j;
  33                 for (j = i; j > 0 &&
  34                              cmp_fn(DSW_ARY_ELEM_PTR(ary, j-1, elem_size),
  35                                     DSW_ARY_ELEM_PTR(ary, j, elem_size)) > 0;
  36                      j--)
  37                         DSW_ARY_ELEM_SWAP(ary, j, j-1, elem_size);
  38         }
  39 }
  40
  41 static inline void
  42 dsw_stable_sort(void *ary, uint16_t len, uint16_t elem_size,
  43                 int (*cmp_fn)(const void *, const void *))
  44 {
  45         dsw_insertion_sort(ary, len, elem_size, cmp_fn);
  46 }
  47
  48 #endif