summaryrefslogtreecommitdiffstats
path: root/libopkg
diff options
context:
space:
mode:
authorticktock35 <ticktock35@e8e0d7a0-c8d9-11dd-a880-a1081c7ac358>2008-12-19 05:43:55 (EST)
committer ticktock35 <ticktock35@e8e0d7a0-c8d9-11dd-a880-a1081c7ac358>2008-12-19 05:43:55 (EST)
commit5befdf4fce0a650193b32f618514de327543148e (patch)
treeda21381bf794fdb9d3a1e9740a5865b49119c13b /libopkg
parent5f550c85c4d2308a15f49f4d2d975b0614867412 (diff)
using hash_table reduce an O(n^2) algorithm to O(n)
in strcmp analysis from gcov: Before: 507: 1386: old_files = pkg_get_installed_files(old_pkg); 507: 1387: new_files = pkg_get_installed_files(pkg); -: 1388: 5466: 1389: for (of = str_list_first(old_files); of; of = str_list_next -: 1390: pkg_t *owner; -: 1391: char *old, *new; 4959: 1392: old = (char *)of->data; 2963021: 1393: for (nf = str_list_first(new_files); nf; nf = str_list 2961464: 1394: new = nf->data; 2961464: 1395: if (strcmp(old, new) == 0) { 3402: 1396: niter = &nf; 3402: 1397: nf=str_list_next(new_files, nf); 3402: 1398: str_list_remove(new_files, niter); 3402: 1399: free(new); 3402: 1400: goto NOT_OBSOLETE; -: 1401: } After: 507: 1393: new_files_table.entries = NULL; 507: 1394: hash_table_init("new_files" , &new_files_table, 20); 8897: 1395: for (nf = str_list_first(new_files); nf; nf = str_list_next 8390: 1396: if (nf && nf->data) 8390: 1397: hash_table_insert(&new_files_table, nf->data, nf->da -: 1398: } -: 1399: 5466: 1400: for (of = str_list_first(old_files); of; of = str_list_next -: 1401: pkg_t *owner; -: 1402: char *old, *new; 4959: 1403: old = (char *)of->data; 4959: 1404: new = (char *) hash_table_get (&new_files_table, old); 4959: 1405: if (new) 4894: 1406: continue; git-svn-id: http://opkg.googlecode.com/svn/trunk@186 e8e0d7a0-c8d9-11dd-a880-a1081c7ac358
Diffstat (limited to 'libopkg')
-rw-r--r--libopkg/opkg_install.c27
1 files changed, 13 insertions, 14 deletions
diff --git a/libopkg/opkg_install.c b/libopkg/opkg_install.c
index 8625f62..5f154a5 100644
--- a/libopkg/opkg_install.c
+++ b/libopkg/opkg_install.c
@@ -1377,7 +1377,7 @@ static int remove_obsolesced_files(opkg_conf_t *conf, pkg_t *pkg, pkg_t *old_pkg
str_list_elt_t *of;
str_list_t *new_files;
str_list_elt_t *nf;
- str_list_elt_t **niter;
+ hash_table_t new_files_table;
if (old_pkg == NULL) {
return 0;
@@ -1386,20 +1386,21 @@ static int remove_obsolesced_files(opkg_conf_t *conf, pkg_t *pkg, pkg_t *old_pkg
old_files = pkg_get_installed_files(old_pkg);
new_files = pkg_get_installed_files(pkg);
+ new_files_table.entries = NULL;
+ hash_table_init("new_files" , &new_files_table, 20);
+ for (nf = str_list_first(new_files); nf; nf = str_list_next(new_files, nf)) {
+ if (nf && nf->data)
+ hash_table_insert(&new_files_table, nf->data, nf->data);
+ }
+
for (of = str_list_first(old_files); of; of = str_list_next(old_files, of)) {
pkg_t *owner;
char *old, *new;
old = (char *)of->data;
- for (nf = str_list_first(new_files); nf; nf = str_list_next(new_files, nf)) {
- new = nf->data;
- if (strcmp(old, new) == 0) {
- niter = &nf;
- nf=str_list_next(new_files, nf);
- str_list_remove(new_files, niter);
- free(new);
- goto NOT_OBSOLETE;
- }
- }
+ new = (char *) hash_table_get (&new_files_table, old);
+ if (new)
+ continue;
+
if (file_is_dir(old)) {
continue;
}
@@ -1419,11 +1420,9 @@ static int remove_obsolesced_files(opkg_conf_t *conf, pkg_t *pkg, pkg_t *old_pkg
strerror(errno));
}
}
-
- NOT_OBSOLETE:
- ;
}
+ hash_table_deinit(&new_files_table);
pkg_free_installed_files(old_pkg);
pkg_free_installed_files(pkg);