2 * Copyright(c) 2012-2018 Intel Corporation
3 * SPDX-License-Identifier: BSD-3-Clause-Clear
7 #include "utils_list.h"
9 void ocf_lst_sort(struct ocf_lst
*lst
)
11 ocf_cache_line_t iter_idx
;
12 ocf_cache_line_t next_idx
;
13 struct ocf_lst_entry
*iter
;
16 /* No comparator, no needed to sort */
20 if (ocf_lst_empty(lst
)) {
21 /* List is empty nothing to do */
25 /* Get iterator - first element on the list, and one after */
26 iter_idx
= lst
->head
->next
;
27 iter
= lst
->getter(lst
->cache
, iter_idx
);
28 next_idx
= iter
->next
;
29 lst
->getter(lst
->cache
, iter
->next
);
31 /* Initialize list to initial empty state, it will be empty */
32 lst
->head
->next
= lst
->invalid
;
33 lst
->head
->prev
= lst
->invalid
;
35 while (iter_idx
!= lst
->invalid
) {
36 ocf_lst_init_entry(lst
, iter
);
38 if (ocf_lst_empty(lst
)) {
39 /* Put first at the the list */
40 ocf_lst_add(lst
, iter_idx
);
42 /* search for place where put element at the list */
43 struct ocf_lst_entry
*pos
;
44 ocf_cache_line_t pos_idx
;
46 for_each_lst(lst
, pos
, pos_idx
)
47 if (lst
->cmp(lst
->cache
, pos
, iter
) > 0)
50 if (lst
->invalid
== pos_idx
) {
51 /* Put at the end of list */
52 ocf_lst_add_tail(lst
, iter_idx
);
54 /* Position is known, put it before */
55 ocf_lst_add_before(lst
, pos_idx
, iter_idx
);
61 iter
= lst
->getter(lst
->cache
, iter_idx
);
62 next_idx
= iter
->next
;