From 5befdf4fce0a650193b32f618514de327543148e Mon Sep 17 00:00:00 2001 From: ticktock35 Date: Fri, 19 Dec 2008 05:43:55 -0500 Subject: 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 --- (limited to 'COPYING') -- cgit v0.9.1