1d38d8d6bc7c09e37c64dbbd02af2452f5ea2a42
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"
25 void active_list_init(struct active_list
*ptr
) {
26 INIT_LIST_HEAD(&ptr
->node
);
27 INIT_LIST_HEAD(&ptr
->depend
);
33 struct active_list
* active_list_next(struct active_list
*head
, struct active_list
*ptr
) {
34 struct active_list
*next
=NULL
;
36 fprintf(stderr
, "active_list_next head = %p, ptr = %p invalid value!!\n", head
, ptr
);
41 next
= list_entry(ptr
->node
.next
, struct active_list
, node
);
45 if ( ptr
->depended
&& &ptr
->depended
->depend
== ptr
->node
.next
) {
48 while ( next
->depend
.next
!= &next
->depend
) {
49 next
= list_entry(next
->depend
.next
, struct active_list
, node
);
55 struct active_list
* active_list_prev(struct active_list
*head
, struct active_list
*ptr
) {
56 struct active_list
*prev
=NULL
;
58 fprintf(stderr
, "active_list_prev head = %p, ptr = %p invalid value!!\n", head
, ptr
);
63 if ( ptr
->depend
.prev
!= &ptr
->depend
) {
64 prev
= list_entry(ptr
->depend
.prev
, struct active_list
, node
);
67 if ( ptr
->depended
&& ptr
->depended
!= head
&& &ptr
->depended
->depend
== ptr
->node
.prev
) {
68 prev
= list_entry(ptr
->depended
->node
.prev
, struct active_list
, node
);
70 prev
= list_entry(ptr
->node
.prev
, struct active_list
, node
);
77 struct active_list
*active_list_move_node(struct active_list
*old_head
, struct active_list
*new_head
, struct active_list
*node
) {
78 struct active_list
*prev
;
79 if (!old_head
|| !new_head
|| !node
)
81 if (old_head
== new_head
)
83 prev
= active_list_prev(old_head
, node
);
84 active_list_add(new_head
, node
);
88 static void list_head_clear (struct list_head
*head
) {
89 struct active_list
*next
;
90 struct list_head
*n
, *ptr
;
93 list_for_each_safe(ptr
, n
, head
) {
94 next
= list_entry(ptr
, struct active_list
, node
);
95 if (next
->depend
.next
!= &next
->depend
) {
96 list_head_clear(&next
->depend
);
98 active_list_init(next
);
101 void active_list_clear(struct active_list
*head
) {
102 list_head_clear(&head
->node
);
103 if (head
->depend
.next
!= &head
->depend
) {
104 list_head_clear(&head
->depend
);
106 active_list_init(head
);
109 void active_list_add_depend(struct active_list
*node
, struct active_list
*depend
) {
110 list_del_init(&depend
->node
);
111 list_add_tail(&depend
->node
, &node
->depend
);
112 depend
->depended
= node
;
115 void active_list_add(struct active_list
*head
, struct active_list
*node
) {
116 list_del_init(&node
->node
);
117 list_add_tail(&node
->node
, &head
->node
);
118 node
->depended
= head
;
121 struct active_list
* active_list_head_new() {
122 struct active_list
* head
= calloc(1, sizeof(struct active_list
));
123 active_list_init(head
);
127 void active_list_head_delete(struct active_list
*head
) {
128 active_list_clear(head
);
134 * Note. the list should not be large, or it will be very inefficient.
137 struct active_list
* active_list_sort(struct active_list
*head
, int (*compare
)(const void *, const void *)) {
138 struct active_list tmphead
;
139 struct active_list
*node
, *ptr
;
142 active_list_init(&tmphead
);
143 for (node
= active_list_next(head
, NULL
); node
; node
= active_list_next(head
, NULL
)) {
144 if (tmphead
.node
.next
== &tmphead
.node
) {
145 active_list_move_node(head
, &tmphead
, node
);
147 for (ptr
= active_list_next(&tmphead
, NULL
); ptr
; ptr
=active_list_next(&tmphead
, ptr
)) {
148 if (compare(ptr
, node
) <= 0) {
153 active_list_move_node(head
, &tmphead
, node
);
155 active_list_move_node(head
, ptr
, node
);
158 node
->depended
= &tmphead
;
160 for (ptr
= active_list_prev(&tmphead
, NULL
); ptr
; ptr
=active_list_prev(&tmphead
, NULL
)) {
161 active_list_move_node(&tmphead
, head
, ptr
);