diff options
author | ticktock35 <ticktock35@e8e0d7a0-c8d9-11dd-a880-a1081c7ac358> | 2008-12-16 19:26:32 (EST) |
---|---|---|
committer | ticktock35 <ticktock35@e8e0d7a0-c8d9-11dd-a880-a1081c7ac358> | 2008-12-16 19:26:32 (EST) |
commit | 4a5627af1ecf0061c99409f4a3b4e84de5e58f30 (patch) | |
tree | 6d45577650af682ccd329fc228e2076fe4b6d6dc /libopkg/active_list.c | |
parent | da40af11f7cdf54b484c8aae73d6201694e6c234 (diff) |
introduce the active_list for searching.
introduce the active_list_sort
git-svn-id: http://opkg.googlecode.com/svn/trunk@181 e8e0d7a0-c8d9-11dd-a880-a1081c7ac358
Diffstat (limited to 'libopkg/active_list.c')
-rw-r--r-- | libopkg/active_list.c | 33 |
1 files changed, 33 insertions, 0 deletions
diff --git a/libopkg/active_list.c b/libopkg/active_list.c index 861454e..1d38d8d 100644 --- a/libopkg/active_list.c +++ b/libopkg/active_list.c @@ -129,3 +129,36 @@ void active_list_head_delete(struct active_list *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; +} |