| Age | Commit message (Collapse) | Author |
|---|
|
This accomplishes quite a few things with one rather invasive change.
1. Iteration is much more performant, due to a reduction in pointer
chasing and linear item access.
2. Data structures are smaller- we no longer have the overhead of the
linked list as the file struts are now laid out consecutively in
memory.
3. Memory allocation has been massively reworked. Before, we would
allocate three different pieces of memory per file item- the list
struct, the file struct, and the copied filename. What this resulted
in was massive fragmentation of memory when loading filelists since
the memory allocator had to leave holes all over the place. The new
situation here now removes the need for any list item allocation;
allocates the file structs in contiguous memory (and reallocs as
necessary), leaving only the strings as individually allocated. Tests
using valgrind (massif) show some pretty significant memory
reductions on the worst case `pacman -Ql > /dev/null` (366387 files
on my machine):
Before:
Peak heap: 54,416,024 B
Useful heap: 36,840,692 B
Extra heap: 17,575,332 B
After:
Peak heap: 38,004,352 B
Useful heap: 28,101,347 B
Extra heap: 9,903,005 B
Several small helper methods have been introduced, including a list to
array conversion helper as well as a filelist merge sort that works
directly on arrays.
Signed-off-by: Dan McGee <dan@archlinux.org>
|
|
We can readily detect the first node in a list by checking if
node->prev->next is NULL. So there is no need to pass the head
of the list to this function and its prototype now looks like
all the other item accessors.
Signed-off-by: Allan McRae <allan@archlinux.org>
Signed-off-by: Dan McGee <dan@archlinux.org>
|
|
The only thing this accessor did was remove the const qualifier
given our entire list implementation requires passing around the
head anyway.
Signed-off-by: Allan McRae <allan@archlinux.org>
Signed-off-by: Dan McGee <dan@archlinux.org>
|
|
Helper function to get the previous item in a list
Signed-off-by: Allan McRae <allan@archlinux.org>
Signed-off-by: Dan McGee <dan@archlinux.org>
|
|
|
|
Signed-off-by: Pang Yan Han <pangyanhan@gmail.com>
Signed-off-by: Dan McGee <dan@archlinux.org>
|
|
This does touch a lot of things, and hopefully doesn't break things on
other platforms, but allows us to also clean up a bunch of crud that no
longer needs to be there.
Signed-off-by: Dan McGee <dan@archlinux.org>
|
|
This is the standard, and we have had a few of these introduced lately
that should not be here.
Done with:
find -name '*.c' | xargs sed -i -e 's#if (#if(#g'
find -name '*.c' | xargs sed -i -e 's#while (#while(#g'
Signed-off-by: Dan McGee <dan@archlinux.org>
|
|
This was discussed and more or less agreed upon on the mailing list. A
huge checkin, but if we just do it and let people adjust the pain will
end soon enough. Rebasing should be relatively straighforward for anyone
that sees conflicts; just be sure you use the new return style if
possible.
The following semantic patch was used to do the change, along with some
hand-massaging in order to preserve parenthesis where appropriate:
The semantic match that finds this problem is as follows, although some
hand-massaging was done in order to keep parenthesis where appropriate:
(http://coccinelle.lip6.fr/)
// <smpl>
@@
expression a;
@@
- return(a);
+ return a;
// </smpl>
A macros_file was also provided with the following content:
Additional steps taken, mainly for ASSERT() macros:
$ sed -i -e 's#return(NULL)#return NULL#' lib/libalpm/*.c
$ sed -i -e 's#return(-1)#return -1#' lib/libalpm/*.c
Signed-off-by: Dan McGee <dan@archlinux.org>
|
|
Signed-off-by: Dave Reisner <d@falconindy.com>
Signed-off-by: Dan McGee <dan@archlinux.org>
|
|
This takes in the list and a list item, and does the pointer dance necessary
to remove it from the list regardless of whether it is first, last, or
somewhere in the middle. It is useful for callers that already know what
item needs to be removed and have a pointer to it rather than doing a search
by data that the plain alpm_list_remove() does.
Refactor alpm_list_remove() to use this function as well.
Signed-off-by: Dan McGee <dan@archlinux.org>
|
|
There is a lot of swtiching between size_t and int for alpm_list sizes
in the codebase. Start converting these to all be size_t by adjusting
the return type of alpm_list_count and fixing all additional warnings
given by -Wconversion that are generated by this change.
Dan: a few more small changes to ensure things compile, adjusting some
printf format string characters to accommodate the larger size on x86_64.
Signed-off-by: Allan McRae <allan@archlinux.org>
Signed-off-by: Dan McGee <dan@archlinux.org>
|
|
Signed-off-by: Allan McRae <allan@archlinux.org>
Signed-off-by: Dan McGee <dan@archlinux.org>
|
|
Signed-off-by: Allan McRae <allan@archlinux.org>
Signed-off-by: Dan McGee <dan@archlinux.org>
|
|
Signed-off-by: Dan McGee <dan@archlinux.org>
|
|
Signed-off-by: Laszlo Papp <djszapi@archlinux.us>
Signed-off-by: Dan McGee <dan@archlinux.org>
|
|
This is more efficient than alpm_list_diff since it assumes the two lists
are sorted. And also we get the two sides of the diff.
Even sorting should more efficient than the current list_diff. Sorting the
two lists should be O(n*log(n)+m*log(m)) while the current list_diff is
O(n*m). So I also reimplemented list_diff using list_diff_sorted.
Signed-off-by: Xavier Chantry <shiningxc@gmail.com>
Signed-off-by: Dan McGee <dan@archlinux.org>
|
|
A NULL list element triggered an infinite loop. Not cool :)
Signed-off-by: Xavier Chantry <shiningxc@gmail.com>
Signed-off-by: Dan McGee <dan@archlinux.org>
|
|
Signed-off-by: Dan McGee <dan@archlinux.org>
|
|
So if you want to remove NULL needle from a list, alpm_list_remove will
return with "not found".
Signed-off-by: Nagy Gabor <ngaba@bibl.u-szeged.hu>
Signed-off-by: Dan McGee <dan@archlinux.org>
|
|
* remove obsolete and unused *_cmp helper functions like deppkg_cmp and
_alpm_grp_cmp
* new alpm_list_remove_str function, used 6 times in handle.c
* remove _alpm_prov_cmp / _alpm_db_whatprovides and replace them by
a more general alpm_find_pkg_satisfiers with a cleaner implementation.
before: alpm_db_whatprovides(db, targ)
after: alpm_find_pkg_satisfiers(alpm_db_getpkgcache(db), targ)
* remove satisfycmp and replace alpm_list_find + satisfycmp usage by
_alpm_find_dep_satisfiers.
before : alpm_list_find(_alpm_db_get_pkgcache(db), dep, satisfycmp)
after : _alpm_find_dep_satisfiers(_alpm_db_get_pkgcache(db), dep)
* remove _alpm_pkgname_pkg_cmp, which was used with alpm_list_remove, and
use _alpm_pkg_find + alpm_list_remove with _alpm_pkg_cmp instead.
This commit actually get rids of all complicated and asymmetric _cmp
functions. I first thought these functions were worth it, be caused it
allowed us to reuse list_find and list_remove. But this was at the detriment
of the clarity and also the ease of use of these functions, dangerous
because of their asymmetricity.
Signed-off-by: Chantry Xavier <shiningxc@gmail.com>
Signed-off-by: Dan McGee <dan@archlinux.org>
|
|
* Remove some #include statements that are not strictly necessary
* Remove node_new function that is really just a one-liner
Signed-off-by: Dan McGee <dan@archlinux.org>
|
|
* Introduces 'list == NULL' convention for empty list. That means
alpm_list_new isn't needed anymore, so kill it
* Small straightforward fixes in alpm_list.c
Signed-off-by: Nagy Gabor <ngaba@bibl.u-szeged.hu>
Signed-off-by: Chantry Xavier <shiningxc@gmail.com>
|
|
Update the GPL boilerplate to direct people to the GNU website for a copy of
the license, as well as bump all of Judd's copyrights to 2007.
Signed-off-by: Dan McGee <dan@archlinux.org>
|
|
alpm_list_find and alpm_list_find_ptr will now return a void *, and
alpm_list_find_str will return a char *, instead of an int.
Signed-off-by: Chantry Xavier <shiningxc@gmail.com>
Signed-off-by: Dan McGee <dan@archlinux.org>
|
|
This O(1) function joins 2 lists.
Signed-off-by: Nagy Gabor <ngaba@bibl.u-szeged.hu>
Signed-off-by: Dan McGee <dan@archlinux.org>
|
|
The old alpm_list_find was renamed to alpm_list_find_ptr, and a new
alpm_list_find was introduced, which uses the fn comparison-function
parameter in its decision.
Now both alpm_list_find_ptr (a new ptrcmp helper function was also
added) and alpm_list_find_str are just an alpm_list_find call.
Signed-off-by: Nagy Gabor <ngaba@bibl.u-szeged.hu>
Signed-off-by: Chantry Xavier <shiningxc@gmail.com>
[Dan: made ptrcmp a static function]
Signed-off-by: Dan McGee <dan@archlinux.org>
|
|
Run the kernel's cleanfile script on all of our source files.
Signed-off-by: Dan McGee <dan@archlinux.org>
|
|
So I spent a good 4 hours tracking a bug down tonight due to
alpm_list_copy_data not actually doing what I expected to do. We can't find
the size of an object we don't know the type of, so rewrite it so we pass
in the size explicitly. This was making _alpm_pkg_dup fail and causing all
sorts of other issues.
Signed-off-by: Dan McGee <dan@archlinux.org>
|
|
It's time to define that alpm_list_add(list, foo) adds 'foo' to the end of
'list' and returns with 'list', because:
1. list is a list, not a set.
2. sortbydeps _needs_ an alpm_list_add definition to work properly.
As a first step, I used this definition in recursedeps.
Signed-off-by: Nagy Gabor <ngaba@bibl.u-szeged.hu>
[Dan: punctuation cleanup in commit message and code comments, added comment
to alpm_list_add]
Signed-off-by: Dan McGee <dan@archlinux.org>
|
|
Commit 2ee90ddae23dd86c68223c0d6c49f0b92d62429d did a special check to see
if we were removing the head node, but not the tail node. Add a special case
for the tail node to ensure all relevant pointers get updated.
Signed-off-by: Dan McGee <dan@archlinux.org>
|
|
Signed-off-by: Dan McGee <dan@archlinux.org>
|
|
List head nodes contain null 'prev' pointer, which we can (ab)use to maintain a
back reference to the tail pointer of the list.
While list additions are not _significantly_ improved, they are still sped up.
Original
$ time pacman -Qo /usr/bin/wtpt
/usr/bin/wtpt is owned by lcms 1.17-2
real 0m3.623s
user 0m1.883s
sys 0m1.473s
New
$ time pacman -Qo /usr/bin/wtpt
/usr/bin/wtpt is owned by lcms 1.17-2
real 0m2.006s
user 0m0.263s
sys 0m1.627s
Signed-off-by: Aaron Griffin <aaronmgriffin@gmail.com>
|
|
Signed-off-by: Dan McGee <dan@archlinux.org>
|
|
Package dup needs to copy all members. Nathan had his implementation, but
I generalized it to this new alpm_list function (and will use it in the
next commit).
CC: Nathan Jones <nathanj@insightbb.com>
Signed-off-by: Dan McGee <dan@archlinux.org>
|
|
Signed-off-by: Nathan Jones <nathanj@insightbb.com>
Signed-off-by: Dan McGee <dan@archlinux.org>
|
|
Signed-off-by: Chantry Xavier <shiningxc@gmail.com>
|
|
Add some 'const' keywords all over the code to make it a bit more strict on
what you can and can't do with data. This is especially important when we
return pointers to the pacman frontend- ideally this would always be
untouchable data.
Signed-off-by: Dan McGee <dan@archlinux.org>
|
|
We had many unnecessary casts, most of them dealing with malloc and
other memory allocations. The variable type should take care of it;
no need to do it explicitly. In addition, I caught a const error while
removing the casts.
Signed-off-by: Dan McGee <dan@archlinux.org>
|
|
Signed-off-by: Dan McGee <dan@archlinux.org>
|
|
We haven't done a whole lot with Doxygen so far, so this updates some of the
things that have changed a lot- namely, the now public exposure of alpm_list.
All functions in this file have now been Doxygen commented, and a few other
things in alpm.c were fixed as well. In addition, the Doxygen config file
was updated.
Signed-off-by: Dan McGee <dan@archlinux.org>
|
|
the alpm strcmp operation which takes void* references.
* We had this great visibility patch, but never actually took advantage of
it. Added the right compile flag to make it work and added some more
SYMEXPORTs where necessary to have a successful compile.
|
|
reordering and adding ones that were forgotten (noticed when trying to
compile after reordering).
* Updated the HACKING file to include information on #include usage.
* print -> vprint in "making dir" function in pactest.
|
|
* Moved entirely to alpm_pkg_get_* accessors, to read data on demand
* Mostly removed the INFRQ_ parameters from outside the be_files backend (making
the backend more extensible in the long run)
* packages created from _alpm_db_scan now have the db and origin set (making
accessors actually work for these packages)
* removed _alpm_db_ensure_pkgcache
* totally revamped the _alpm_checkconflicts function, making it cleaner and
easier to read (and thus fix in the long run) - maintainable code ftw
NOTE: feel free to rename the functions... I couldn't think of anything better
* removed an extra loop in sync.c:find_replacements - no sense in looping over
an entire DB while strcmp'ing the name, when we have get_pkgfromcache
Other:
* package struct "license" -> "licenses"
* Created _alpm_sync_find (duplicate code in some places, find_pkginsync
* Minor const correctness changes along the way
* fixed a couple extra '/' pathing issues (non-issues really)
* removed a duplicate pkg_cmp function
|
|
allows for the same bit operators to be used across the board on pkg_get
operations.
* Changed name of INFRQ_NONE -> INFRQ_BASE to more clearly reflect what it
does (loads pkg name and version).
* Added a few missing things on package functions, such as SYMEXPORT and
ALPM_LOG_FUNC.
* Slight updates to pmenv to print 'pass' and 'fail' instead of 'passed' and
'failed'. Keeps output a bit more concise.
* Fixed a doxygen comment spelling error. :P
|
|
* Added some provision switching hackery. This could probably use some
refactoring,.. it solves the following case:
pkg1 and pkg2 provide 'foo' and are both installed
pkg3 depends on 'foo' and so lists 'pkg1' in the REQUIREDBY db section
pkg1 is upgraded and no longer provides 'foo'
** This code ensures that the REQUIREDBY of pkg3 is updated to require pkg2
now instead of pkg1
|
|
* gcc visiblity changes
Also modified _alpm_versioncmp -> alpm_versioncmp (public function) as per K.
Piche's suggestions
|
|
* alpm_list_is_in --> alpm_list_find
* alpm_list_is_strin --> alpm_list_find_str
* Flip parameters of both functions to be inline with rest of alpm_list.
First commit, woohoo.
|
|
* Added alpm_list_remove_node for single list node removal
* Proper error checking/output for failed db_read/db_write (missing files)
* Invalid packages (missing files) are now removed from the package cache
* -Qs and -Ss output now look the same
* config.rpath causes errors on one machine I had, so I added it to CVS
* Fixed a "clobbered memory" issue when installing groups - only the outer list
should be free'd, not the contained data
|
|
* Fixed -Ss output so as not to call alpm_list_getdata with a NULl list
* Added a NULL check in alpm_list_getdata
* Fixed alpm_list_add_sorted to properly handle a new / beginning insertions
|