opkg: apply "2-pkg-vec--Optimize-gross-inefficiency.patch" from OpenEmbedded
authorticktock35 <ticktock35@e8e0d7a0-c8d9-11dd-a880-a1081c7ac358>
Mon, 15 Dec 2008 04:19:43 +0000 (04:19 +0000)
committerticktock35 <ticktock35@e8e0d7a0-c8d9-11dd-a880-a1081c7ac358>
Mon, 15 Dec 2008 04:19:43 +0000 (04:19 +0000)
  pkg_vec: Optimize gross inefficiency.

  This module tries to implement *unique* vector (without duplicating objects),
  and does this by iterating thru all already existing elements.  Thus,
  complexity of adding N elements was O(N^2). However, there're no grave reasons
  to do uniqueness at all:

  1. First of all, if feeds are correct, there won't be duplicates.
  2. Then, even if there will be, there won't be serious problems like
     segfaults.
  3. Finally, for quite a few operations vectors is constructed from a
     hashtable, thus uniqueness is guaranteed (which reduces possible cases of
     non-uniqueness to values of Depends: and friends).

  All an all, remove dup check, and make ipkg work order of magnitude faster on
  a feed with few thousands of packages.

git-svn-id: http://opkg.googlecode.com/svn/trunk@18 e8e0d7a0-c8d9-11dd-a880-a1081c7ac358

pkg_vec.c

index 0fc47f884315e158282cfd821fe89302a7acb3b9..2d22d912ec6a7c1fc818402ad254edc4dfbdfcb5 100644 (file)
--- a/pkg_vec.c
+++ b/pkg_vec.c
@@ -104,6 +104,7 @@ void pkg_vec_insert(pkg_vec_t *vec, const pkg_t *pkg)
      int i;
      int found = 0;
 
+#if 0
      /* look for a duplicate pkg by name, version, and architecture */
      for (i = 0; i < vec->len; i++)
          if ((strcmp(pkg->name, vec->pkgs[i]->name) == 0)
@@ -112,6 +113,7 @@ void pkg_vec_insert(pkg_vec_t *vec, const pkg_t *pkg)
               found = 1;
               break;
          }
+#endif
 
      /* we didn't find one, add it */
      if(!found){   
@@ -191,6 +193,7 @@ void abstract_pkg_vec_insert(abstract_pkg_vec_t *vec, abstract_pkg_t *pkg)
 {
     int i;
 
+#if 0
     /* look for a duplicate pkg by name */
     for(i = 0; i < vec->len; i++)
        if (strcmp(pkg->name, vec->pkgs[i]->name) == 0)
@@ -198,12 +201,15 @@ void abstract_pkg_vec_insert(abstract_pkg_vec_t *vec, abstract_pkg_t *pkg)
 
     /* we didn't find one, add it */
     if(i == vec->len){   
+#endif
        vec->pkgs = 
          (abstract_pkg_t **)
            realloc(vec->pkgs, (vec->len + 1) * sizeof(abstract_pkg_t *));
        vec->pkgs[vec->len] = pkg;
        vec->len++;
+#if 0
     }
+#endif
 }
 
 abstract_pkg_t * abstract_pkg_vec_get(abstract_pkg_vec_t *vec, int i)