Tick Chen <tick@openmoko.com>
- Copyright (C) 2008 Openmoko Inc.
+ Copyright (C) 2008 Openmoko Inc.
This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License as
#include <string.h>
#include <stdlib.h>
+#include "libbb/libbb.h"
void active_list_init(struct active_list *ptr) {
INIT_LIST_HEAD(&ptr->node);
}
/**
- */
+ */
struct active_list * active_list_next(struct active_list *head, struct active_list *ptr) {
struct active_list *next=NULL;
if ( !head ) {
- fprintf(stderr, "active_list_next head = %p, ptr = %p invalid value!!\n", head, ptr);
+ opkg_msg(ERROR, "Internal error: head=%p, ptr=%p\n", head, ptr);
return NULL;
}
if ( !ptr )
return ptr->depended;
}
while ( next->depend.next != &next->depend ) {
- next = list_entry(next->depend.next, struct active_list, node);
+ next = list_entry(next->depend.next, struct active_list, node);
}
return next;
}
struct active_list * active_list_prev(struct active_list *head, struct active_list *ptr) {
struct active_list *prev=NULL;
if ( !head ) {
- fprintf(stderr, "active_list_prev head = %p, ptr = %p invalid value!!\n", head, ptr);
+ opkg_msg(ERROR, "Internal error: head=%p, ptr=%p\n", head, ptr);
return NULL;
}
if ( !ptr )
if ( ptr->depend.prev != &ptr->depend ) {
prev = list_entry(ptr->depend.prev, struct active_list, node);
return prev;
- }
+ }
if ( ptr->depended && ptr->depended != head && &ptr->depended->depend == ptr->node.prev ) {
prev = list_entry(ptr->depended->node.prev, struct active_list, node);
- } else
+ } else
prev = list_entry(ptr->node.prev, struct active_list, node);
if ( prev == head )
return NULL;
node->depended = head;
}
-struct active_list * active_list_head_new() {
- struct active_list * head = calloc(1, sizeof(struct active_list));
+struct active_list * active_list_head_new(void) {
+ struct active_list * head = xcalloc(1, sizeof(struct active_list));
active_list_init(head);
return head;
}
free(head);
}
+/*
+ * Using insert sort.
+ * Note. the list should not be large, or it will be very inefficient.
+ *
+ */
+struct active_list * active_list_sort(struct active_list *head, int (*compare)(const void *, const void *)) {
+ struct active_list tmphead;
+ struct active_list *node, *ptr;
+ if ( !head )
+ return NULL;
+ active_list_init(&tmphead);
+ for (node = active_list_next(head, NULL); node; node = active_list_next(head, NULL)) {
+ if (tmphead.node.next == &tmphead.node) {
+ active_list_move_node(head, &tmphead, node);
+ } else {
+ for (ptr = active_list_next(&tmphead, NULL); ptr; ptr=active_list_next(&tmphead, ptr)) {
+ if (compare(ptr, node) <= 0) {
+ break;
+ }
+ }
+ if (!ptr) {
+ active_list_move_node(head, &tmphead, node);
+ } else {
+ active_list_move_node(head, ptr, node);
+ }
+ }
+ node->depended = &tmphead;
+ }
+ for (ptr = active_list_prev(&tmphead, NULL); ptr; ptr=active_list_prev(&tmphead, NULL)) {
+ active_list_move_node(&tmphead, head, ptr);
+ }
+ return head;
+}