[pacman-dev] [PATCH 0/4] Package list find performance improvements

[Dan McGee]

This series of patches makes finding a package in our linked list
implementation a whole lot faster, if that search is using the standard
_alpm_pkg_find, which nearly all are (after the first patch).

It does this by adding a hash function to util.c which is nothing too
complicated and named after a publicly available algorithm. When packages are
created, we fill in this hash value as soon as the pkgname is read. Finally,
the _alpm_pkg_find function is rewritten to take advantage of this field,
avoiding repeated strcmp() calls and only falling back to that if a hash is not
available and to verify the hash value was not some sort of collision.

Performance figures and numbers are available in the last patch. This actually
speeds up operations by nearly 33%, so this is not a total waste of time to
consider. :) Review and questions/comments/concerns welcome!

-Dan

Dan McGee (4):
  Use _alpm_pkg_find in deps search
  Add hash_sdbm function
  When setting package name, set hash value as well
  Used hashed package name in _alpm_pkg_find

 lib/libalpm/be_package.c |    1 +
 lib/libalpm/deps.c       |    4 ++--
 lib/libalpm/package.c    |   16 ++++++++++++++--
 lib/libalpm/package.h    |    1 +
 lib/libalpm/util.c       |   22 ++++++++++++++++++++++
 lib/libalpm/util.h       |    1 +
 6 files changed, 41 insertions(+), 4 deletions(-)

-- 
1.7.3.3