embox

1
/**
2
 * @file
3
 * @brief 2-tier priority-sorted list.
4
 *
5
 * @date 04.12.13
6
 * @author Eldar Abusalimov
7
 */
8

9
#include <assert.h>
10
#include <stddef.h>
11

12
#include <lib/libds/priolist.h>
13

14
void priolist_add(struct priolist_link *link, struct priolist *list) {
15
	struct dlist_head *next_node_link = &list->node_list;
16

17
	assert(link && list);
18
	assert(dlist_empty(&link->node_link));
19
	assert(dlist_empty(&link->prio_link));
20

21
	if (!priolist_empty(list)) {
22
		struct priolist_link *first = priolist_first(list);
23
		struct priolist_link *iter = first, *last = NULL;
24

25
		do {
26
			if (iter->prio > link->prio) {
27
				next_node_link = &iter->node_link;
28
				break;
29
			}
30

31
			last = iter;
32
			iter = mcast_out(iter->prio_link.next,
33
					struct priolist_link, prio_link);
34
		} while (iter != first);
35

36
		if (!last || last->prio != link->prio)
37
			/* new prio, new element in a prio tier */
38
			dlist_add_prev(&link->prio_link, &iter->prio_link);
39
	}
40

41
	dlist_add_prev(&link->node_link, next_node_link);
42
}
43

44
void priolist_del(struct priolist_link *link, struct priolist *list) {
45
	assert(link && list);
46
	assert(!dlist_empty(&link->node_link));
47
	assert(!dlist_empty(&list->node_list));
48

49
	if (!dlist_empty(&link->prio_link)) {
50
		struct dlist_head *next_node_link = link->node_link.next;
51

52
		if (next_node_link != &list->node_list) {
53
			struct priolist_link *next =
54
				mcast_out(next_node_link,
55
						struct priolist_link,
56
						node_link);
57

58
			if (dlist_empty(&next->prio_link))
59
				dlist_add_next(&next->prio_link, &link->prio_link);
60
		}
61

62
		dlist_del_init(&link->prio_link);
63
	}
64

65
	dlist_del_init(&link->node_link);
66
}
67

68