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

diff --git a/libopkg/opkg_install.c b/libopkg/opkg_install.c
index 8625f6214dffecab9afb5fddf4caad408b6a4c84..5f154a5128f0179edf0dfc39090dce097618222a 100644 (file)
--- 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);