summaryrefslogtreecommitdiffstats
path: root/lib/libalpm/alpm_list.c
AgeCommit message (Collapse)AuthorFilesLines
2012-02-06Merge branch 'maint'Dan McGee1-1/+4
Conflicts: lib/libalpm/alpm_list.c
2012-01-31Fix rare segfault on package removalAllan McRae1-1/+4
Very rarely a segfault would occur when removing a number of packages due to a corrupted list for the local database (FS#27805, FS#28195). This was caused by the alpm_list_msort function not correctly dealing with the two new head node's prev values. Signed-off-by: Allan McRae <allan@archlinux.org> Signed-off-by: Dan McGee <dan@archlinux.org>
2012-01-02alpm_list_msort: inline alpm_list_nth() callDan McGee1-7/+14
This reduces the number of functions we call by log(n) in this function, and the inlined version is trivial and barely increases the size of the function. Signed-off-by: Dan McGee <dan@archlinux.org>
2011-10-12Remove alpm_list_getdata wrapper functionDan McGee1-13/+0
This one is pretty darn useless. Just derefence the ->data attribute since the type is public anyway and save yourself the function call. Signed-off-by: Dan McGee <dan@archlinux.org>
2011-09-27alpm_list: use malloc instead of callocDan McGee1-4/+4
In every case we were calling calloc, the struct we allocated (or the memory to be used) is fully specified later in the method. For alpm_list_t allocations, we always set all of data, next, and prev. For list copying and transforming to an array, we always copy the entire data element, so no need to zero it first. Signed-off-by: Dan McGee <dan@archlinux.org>
2011-09-22Update Doxyfile and fix some documentation errors caught by DoxygenDan McGee1-1/+0
A few parameters were outdated or wrongly named, and a few things were explicitly linked that Doxygen wasn't able to resolve. Signed-off-by: Dan McGee <dan@archlinux.org>
2011-08-24Improved alpm_list_mmerge() performance (fixed coding style)Diogo Sousa1-10/+15
Improved alpm_list_mmerge() performance by removing an extra pass to obtain the tail node. This was actually suggested by a TODO comment. Signed-off-by: Diogo Sousa <diogogsousa@gmail.com> Signed-off-by: Dan McGee <dan@archlinux.org>
2011-07-21Convert package filelists to an array instead of linked listDan McGee1-0/+32
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>
2011-07-05Simplify alpm_list_previousAllan McRae1-4/+3
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>
2011-07-05Remove alpm_list_firstAllan McRae1-16/+0
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>
2011-07-03Add alpm_list_previous methodAllan McRae1-0/+18
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>
2011-06-01Merge branch 'maint'Dan McGee1-1/+1
2011-05-24alpm_list: fix typo in doxygen commentPang Yan Han1-1/+1
Signed-off-by: Pang Yan Han <pangyanhan@gmail.com> Signed-off-by: Dan McGee <dan@archlinux.org>
2011-04-20Header inclusion cleanupDan McGee1-1/+0
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>
2011-04-20syntax: if/while statements should have no trailing spaceDan McGee1-13/+13
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>
2011-03-20Style change: return(x) --> return xDan McGee1-43/+44
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>
2011-03-16alpm_list: fix typo in doxygen commentDave Reisner1-1/+1
Signed-off-by: Dave Reisner <d@falconindy.com> Signed-off-by: Dan McGee <dan@archlinux.org>
2011-02-04Add new alpm_list_remove_item() functionDan McGee1-33/+53
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>
2011-01-07Use size_t for alpm_list sizesAllan McRae1-4/+4
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>
2011-01-07Update copyright years for 2011Allan McRae1-1/+1
Signed-off-by: Allan McRae <allan@archlinux.org> Signed-off-by: Dan McGee <dan@archlinux.org>
2010-03-25alpm_list_diff_sorted - make some arguments constAllan McRae1-4/+4
Signed-off-by: Allan McRae <allan@archlinux.org> Signed-off-by: Dan McGee <dan@archlinux.org>
2010-03-14Bump copyright dates to 2010Dan McGee1-1/+1
Signed-off-by: Dan McGee <dan@archlinux.org>
2009-10-24Fix a small typo in alpm_list.cLaszlo Papp1-1/+1
Signed-off-by: Laszlo Papp <djszapi@archlinux.us> Signed-off-by: Dan McGee <dan@archlinux.org>
2009-10-11alpm_list : add new alpm_list_diff_sorted functionXavier Chantry1-17/+68
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>
2009-10-11alpm_list : fix a bug in alpm_list_removeXavier Chantry1-0/+1
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>
2009-07-01Update copyright headers and messagesDan McGee1-1/+2
Signed-off-by: Dan McGee <dan@archlinux.org>
2008-07-17alpm_list_remove treat NULL needle as "nothing"Nagy Gabor1-0/+4
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>
2008-05-13Cleanup usages of alpm_list_find and alpm_list_remove.Chantry Xavier1-5/+23
* 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>
2008-02-24More cleanup to alpm_listDan McGee1-20/+7
* 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>
2008-02-25alpm_list.c clean-upNagy Gabor1-58/+63
* 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>
2007-12-10Update GNU GPL boilerplate and copyright datesDan McGee1-4/+2
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>
2007-12-02alpm_list : change the alpm_list_find* to return the matching item.Chantry Xavier1-9/+9
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>
2007-11-20New alpm_list_join functionNagy Gabor1-0/+33
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>
2007-11-17Generalized alpm_list_find.Nagy Gabor1-15/+28
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>
2007-11-16War on whitespaceDan McGee1-9/+9
Run the kernel's cleanfile script on all of our source files. Signed-off-by: Dan McGee <dan@archlinux.org>
2007-11-14Fix alpm_list_copy_dataDan McGee1-5/+7
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>
2007-11-14alpm_list_add == alpm_list_add_lastNagy Gabor1-1/+1
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>
2007-11-11Ensure list tail pointer is updated when we remove tail nodeDan McGee1-2/+10
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>
2007-11-11Remove unused and broken alpm_list_remove_node functionDan McGee1-29/+0
Signed-off-by: Dan McGee <dan@archlinux.org>
2007-11-06Maintain list tail pointers in the head nodeAaron Griffin1-15/+44
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>
2007-11-04Add a little const correctness fix to alpm_listDan McGee1-3/+4
Signed-off-by: Dan McGee <dan@archlinux.org>
2007-10-29Make general list copy functionDan McGee1-2/+24
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>
2007-10-19Add pmdelta_t structure and functions to libalpm.Nathan Jones1-0/+18
Signed-off-by: Nathan Jones <nathanj@insightbb.com> Signed-off-by: Dan McGee <dan@archlinux.org>
2007-07-20libalpm/alpm_list.c : add SYMEXPORT to all alpm_list_ functions.Chantry Xavier1-11/+11
Signed-off-by: Chantry Xavier <shiningxc@gmail.com>
2007-06-05Const correctness!Dan McGee1-19/+23
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>
2007-05-14Remove unnecessary casts on malloc and elsewhereDan McGee1-1/+1
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>
2007-04-27Remove FREESERVER macro and correctly type _alpm_server_freeDan McGee1-1/+1
Signed-off-by: Dan McGee <dan@archlinux.org>
2007-03-29Doxygen fixups for libalpmDan McGee1-81/+158
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>
2007-03-11* Fix group comparison issue and associated compilation warnings by usingDan McGee1-2/+2
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.
2007-03-05This commit looks much more monumental than it is. Almost all just #includeDan McGee1-1/+2
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.
generated by cgit v1.2.3-70-g09d2 (git 2.47.0) at 2024-12-04 14:09:45 +0000