From 5befdf4fce0a650193b32f618514de327543148e Mon Sep 17 00:00:00 2001 From: ticktock35 Date: Fri, 19 Dec 2008 10:43:55 +0000 Subject: [PATCH] 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 --- libopkg/opkg_install.c | 27 +++++++++++++-------------- 1 file 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); -- 2.30.2