diff options
| -rw-r--r-- | libopkg/active_list.c | 33 | ||||
| -rw-r--r-- | libopkg/active_list.h | 2 | ||||
| -rw-r--r-- | libopkg/pkg.c | 4 | ||||
| -rw-r--r-- | libopkg/pkg.h | 2 | ||||
| -rw-r--r-- | libopkg/pkg_hash.c | 1 | ||||
| -rw-r--r-- | tests/opkg_active_list_test.c | 30 |
6 files changed, 65 insertions, 7 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; +} diff --git a/libopkg/active_list.h b/libopkg/active_list.h index 3bedc2f..70d2af8 100644 --- a/libopkg/active_list.h +++ b/libopkg/active_list.h @@ -35,6 +35,8 @@ void active_list_add_depend(struct active_list *node, struct active_list *depend void active_list_add(struct active_list *head, struct active_list *node); struct active_list *active_list_move_node(struct active_list *old_head, struct active_list *new_head, struct active_list *node); +struct active_list * active_list_sort(struct active_list *head, int (*compare_fcn_t)(const void *, const void *)); + struct active_list * active_list_next(struct active_list *head, struct active_list *ptr); struct active_list * active_list_prev(struct active_list *head, struct active_list *ptr); diff --git a/libopkg/pkg.c b/libopkg/pkg.c index 26bf484..dde3a19 100644 --- a/libopkg/pkg.c +++ b/libopkg/pkg.c @@ -113,6 +113,7 @@ int pkg_init(pkg_t *pkg) pkg->recommends_count = 0; active_list_init(&pkg->list); + active_list_init(&pkg->searched_node); /* Abhaya: added init for conflicts fields */ pkg->conflicts = NULL; @@ -446,14 +447,13 @@ abstract_pkg_t *abstract_pkg_new(void) int abstract_pkg_init(abstract_pkg_t *ab_pkg) { - memset(ab_pkg, 0, sizeof(abstract_pkg_t)); - ab_pkg->provided_by = abstract_pkg_vec_alloc(); if (ab_pkg->provided_by==NULL){ return -1; } ab_pkg->dependencies_checked = 0; ab_pkg->state_status = SS_NOT_INSTALLED; + active_list_init(&ab_pkg->searched_node); return 0; } diff --git a/libopkg/pkg.h b/libopkg/pkg.h index a7c98ec..3f7d6b6 100644 --- a/libopkg/pkg.h +++ b/libopkg/pkg.h @@ -88,6 +88,7 @@ struct abstract_pkg{ struct abstract_pkg ** depended_upon_by; /* @@@@ this should be abstract_pkg_vec_t -Jamey */ abstract_pkg_vec_t * provided_by; abstract_pkg_vec_t * replaced_by; + struct active_list searched_node; /* Used for hash search */ }; #include "pkg_depends.h" @@ -137,6 +138,7 @@ struct pkg char **suggests_str; int suggests_count; struct active_list list; /* Used for installing|upgrading */ + struct active_list searched_node; /* Used for searching */ compound_depend_t * depends; /* Abhaya: new conflicts */ diff --git a/libopkg/pkg_hash.c b/libopkg/pkg_hash.c index c63847b..d6a062d 100644 --- a/libopkg/pkg_hash.c +++ b/libopkg/pkg_hash.c @@ -47,7 +47,6 @@ static abstract_pkg_t * add_new_abstract_pkg_by_name(hash_table_t * hash, const */ - int pkg_hash_init(const char *name, hash_table_t *hash, int len) { return hash_table_init(name, hash, len); diff --git a/tests/opkg_active_list_test.c b/tests/opkg_active_list_test.c index 77819b0..4792eae 100644 --- a/tests/opkg_active_list_test.c +++ b/tests/opkg_active_list_test.c @@ -94,6 +94,23 @@ void make_list(struct active_list *head) { active_test_add_depend(L, N); } +int active_test_compare(const void *a, const void *b) { + struct active_list *first = (struct active_list *)a; + struct active_list *second = (struct active_list *)b; + return strcmp(list_entry(first, struct active_test, list), + list_entry(second, struct active_test, list)); +} + +void show_list(struct active_list *head) { + struct active_list *ptr; + struct active_test *test; + for(ptr = active_list_next(head, NULL); ptr ;ptr = active_list_next(head, ptr)) { + test = list_entry(ptr, struct active_test, list); + printf ("%s ",test->str); + } + printf("\n"); +} + int main (void) { struct active_list head; struct active_list *ptr; @@ -102,16 +119,21 @@ int main (void) { make_list(&head); printf("pos order: "); - for(ptr = active_list_next(&head, &head); ptr ;ptr = active_list_next(&head, ptr)) { + show_list(&head); +/* for(ptr = active_list_next(&head, &head); ptr ;ptr = active_list_next(&head, ptr)) { test = list_entry(ptr, struct active_test, list); printf ("%s ",test->str); - } - printf("\nneg order: "); + }*/ + printf("neg order: "); for(ptr = active_list_prev(&head, &head); ptr ;ptr = active_list_prev(&head, ptr)) { test = list_entry(ptr, struct active_test, list); printf ("%s ",test->str); } - printf("\nafter clear: "); + printf("\npos order after sort: "); + active_list_sort(&head, &active_test_compare); + show_list(&head); + + printf("after clear: "); active_list_clear(&head); for(ptr = active_list_next(&head, NULL); ptr ;ptr = active_list_next(&head, ptr)) { test = list_entry(ptr, struct active_test, list); |