]>
Commit | Line | Data |
---|---|---|
9f95a23c TL |
1 | /* |
2 | * Copyright(c) 2012-2018 Intel Corporation | |
3 | * SPDX-License-Identifier: BSD-3-Clause-Clear | |
4 | */ | |
5 | ||
6 | #include "ocf/ocf.h" | |
7 | #include "utils_list.h" | |
8 | ||
9 | void ocf_lst_sort(struct ocf_lst *lst) | |
10 | { | |
11 | ocf_cache_line_t iter_idx; | |
12 | ocf_cache_line_t next_idx; | |
13 | struct ocf_lst_entry *iter; | |
14 | ||
15 | if (!lst->cmp) { | |
16 | /* No comparator, no needed to sort */ | |
17 | return; | |
18 | } | |
19 | ||
20 | if (ocf_lst_empty(lst)) { | |
21 | /* List is empty nothing to do */ | |
22 | return; | |
23 | } | |
24 | ||
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); | |
30 | ||
31 | /* Initialize list to initial empty state, it will be empty */ | |
32 | lst->head->next = lst->invalid; | |
33 | lst->head->prev = lst->invalid; | |
34 | ||
35 | while (iter_idx != lst->invalid) { | |
36 | ocf_lst_init_entry(lst, iter); | |
37 | ||
38 | if (ocf_lst_empty(lst)) { | |
39 | /* Put first at the the list */ | |
40 | ocf_lst_add(lst, iter_idx); | |
41 | } else { | |
42 | /* search for place where put element at the list */ | |
43 | struct ocf_lst_entry *pos; | |
44 | ocf_cache_line_t pos_idx; | |
45 | ||
46 | for_each_lst(lst, pos, pos_idx) | |
47 | if (lst->cmp(lst->cache, pos, iter) > 0) | |
48 | break; | |
49 | ||
50 | if (lst->invalid == pos_idx) { | |
51 | /* Put at the end of list */ | |
52 | ocf_lst_add_tail(lst, iter_idx); | |
53 | } else { | |
54 | /* Position is known, put it before */ | |
55 | ocf_lst_add_before(lst, pos_idx, iter_idx); | |
56 | } | |
57 | } | |
58 | ||
59 | /* Switch to next */ | |
60 | iter_idx = next_idx; | |
61 | iter = lst->getter(lst->cache, iter_idx); | |
62 | next_idx = iter->next; | |
63 | } | |
64 | } |