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