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
dsw_insertion_sort(void * ary,uint16_t len,uint16_t elem_size,int (* cmp_fn)(const void *,const 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
dsw_stable_sort(void * ary,uint16_t len,uint16_t elem_size,int (* cmp_fn)(const void *,const 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
49