summaryrefslogtreecommitdiffstats
path: root/libbb
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 /libbb
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 'libbb')
0 files changed, 0 insertions, 0 deletions