1 /* active_list.h - the opkg package management system
3 Tick Chen <tick@openmoko.com>
5 Copyright (C) 2008 Openmoko Inc.
7 This program is free software; you can redistribute it and/or
8 modify it under the terms of the GNU General Public License as
9 published by the Free Software Foundation; either version 2, or (at
10 your option) any later version.
12 This program is distributed in the hope that it will be useful, but
13 WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 General Public License for more details.
19 #include "active_list.h"
24 #include "libbb/libbb.h"
26 void active_list_init(struct active_list
*ptr
) {
27 INIT_LIST_HEAD(&ptr
->node
);
28 INIT_LIST_HEAD(&ptr
->depend
);
34 struct active_list
* active_list_next(struct active_list
*head
, struct active_list
*ptr
) {
35 struct active_list
*next
=NULL
;
37 fprintf(stderr
, "active_list_next head = %p, ptr = %p invalid value!!\n", head
, ptr
);
42 next
= list_entry(ptr
->node
.next
, struct active_list
, node
);
46 if ( ptr
->depended
&& &ptr
->depended
->depend
== ptr
->node
.next
) {
49 while ( next
->depend
.next
!= &next
->depend
) {
50 next
= list_entry(next
->depend
.next
, struct active_list
, node
);
56 struct active_list
* active_list_prev(struct active_list
*head
, struct active_list
*ptr
) {
57 struct active_list
*prev
=NULL
;
59 fprintf(stderr
, "active_list_prev head = %p, ptr = %p invalid value!!\n", head
, ptr
);
64 if ( ptr
->depend
.prev
!= &ptr
->depend
) {
65 prev
= list_entry(ptr
->depend
.prev
, struct active_list
, node
);
68 if ( ptr
->depended
&& ptr
->depended
!= head
&& &ptr
->depended
->depend
== ptr
->node
.prev
) {
69 prev
= list_entry(ptr
->depended
->node
.prev
, struct active_list
, node
);
71 prev
= list_entry(ptr
->node
.prev
, struct active_list
, node
);
78 struct active_list
*active_list_move_node(struct active_list
*old_head
, struct active_list
*new_head
, struct active_list
*node
) {
79 struct active_list
*prev
;
80 if (!old_head
|| !new_head
|| !node
)
82 if (old_head
== new_head
)
84 prev
= active_list_prev(old_head
, node
);
85 active_list_add(new_head
, node
);
89 static void list_head_clear (struct list_head
*head
) {
90 struct active_list
*next
;
91 struct list_head
*n
, *ptr
;
94 list_for_each_safe(ptr
, n
, head
) {
95 next
= list_entry(ptr
, struct active_list
, node
);
96 if (next
->depend
.next
!= &next
->depend
) {
97 list_head_clear(&next
->depend
);
99 active_list_init(next
);
102 void active_list_clear(struct active_list
*head
) {
103 list_head_clear(&head
->node
);
104 if (head
->depend
.next
!= &head
->depend
) {
105 list_head_clear(&head
->depend
);
107 active_list_init(head
);
110 void active_list_add_depend(struct active_list
*node
, struct active_list
*depend
) {
111 list_del_init(&depend
->node
);
112 list_add_tail(&depend
->node
, &node
->depend
);
113 depend
->depended
= node
;
116 void active_list_add(struct active_list
*head
, struct active_list
*node
) {
117 list_del_init(&node
->node
);
118 list_add_tail(&node
->node
, &head
->node
);
119 node
->depended
= head
;
122 struct active_list
* active_list_head_new() {
123 struct active_list
* head
= xcalloc(1, sizeof(struct active_list
));
124 active_list_init(head
);
128 void active_list_head_delete(struct active_list
*head
) {
129 active_list_clear(head
);
135 * Note. the list should not be large, or it will be very inefficient.
138 struct active_list
* active_list_sort(struct active_list
*head
, int (*compare
)(const void *, const void *)) {
139 struct active_list tmphead
;
140 struct active_list
*node
, *ptr
;
143 active_list_init(&tmphead
);
144 for (node
= active_list_next(head
, NULL
); node
; node
= active_list_next(head
, NULL
)) {
145 if (tmphead
.node
.next
== &tmphead
.node
) {
146 active_list_move_node(head
, &tmphead
, node
);
148 for (ptr
= active_list_next(&tmphead
, NULL
); ptr
; ptr
=active_list_next(&tmphead
, ptr
)) {
149 if (compare(ptr
, node
) <= 0) {
154 active_list_move_node(head
, &tmphead
, node
);
156 active_list_move_node(head
, ptr
, node
);
159 node
->depended
= &tmphead
;
161 for (ptr
= active_list_prev(&tmphead
, NULL
); ptr
; ptr
=active_list_prev(&tmphead
, NULL
)) {
162 active_list_move_node(&tmphead
, head
, ptr
);