From 5befdf4fce0a650193b32f618514de327543148e Mon Sep 17 00:00:00 2001
From: ticktock35 <ticktock35@e8e0d7a0-c8d9-11dd-a880-a1081c7ac358>
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