Send patches - preferably formatted by git format-patch - to patches at archlinux32 dot org.
summaryrefslogtreecommitdiff
path: root/lib/libalpm/conflict.c
diff options
context:
space:
mode:
authorDan McGee <dan@archlinux.org>2011-07-19 04:47:29 -0500
committerDan McGee <dan@archlinux.org>2011-07-21 15:04:30 -0500
commitbb3dada8711fbb822513cd556167867b537f8986 (patch)
tree1230de6f94675777e9cdd4150779f4756995efa1 /lib/libalpm/conflict.c
parent058ee1737182c2d5e900e0feba57f0d6496e735e (diff)
Convert package filelists to an array instead of linked list
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>
Diffstat (limited to 'lib/libalpm/conflict.c')
-rw-r--r--lib/libalpm/conflict.c65
1 files changed, 36 insertions, 29 deletions
diff --git a/lib/libalpm/conflict.c b/lib/libalpm/conflict.c
index eda6ba10..538c4c73 100644
--- a/lib/libalpm/conflict.c
+++ b/lib/libalpm/conflict.c
@@ -229,22 +229,22 @@ static const int INTERSECT = 1;
* DIFFERENCE - a difference operation is performed. filesA - filesB.
* INTERSECT - an intersection operation is performed. filesA & filesB.
*/
-static alpm_list_t *filelist_operation(alpm_list_t *filesA, alpm_list_t *filesB,
- int operation)
+static alpm_list_t *filelist_operation(alpm_filelist_t *filesA,
+ alpm_filelist_t *filesB, int operation)
{
alpm_list_t *ret = NULL;
- alpm_list_t *pA = filesA, *pB = filesB;
+ size_t ctrA = 0, ctrB = 0;
- while(pA && pB) {
- alpm_file_t *fileA = pA->data;
- alpm_file_t *fileB = pB->data;
+ while(ctrA < filesA->count && ctrB < filesB->count) {
+ alpm_file_t *fileA = filesA->files + ctrA;
+ alpm_file_t *fileB = filesB->files + ctrB;
const char *strA = fileA->name;
const char *strB = fileB->name;
/* skip directories, we don't care about them */
if(strA[strlen(strA)-1] == '/') {
- pA = pA->next;
+ ctrA++;
} else if(strB[strlen(strB)-1] == '/') {
- pB = pB->next;
+ ctrB++;
} else {
int cmp = strcmp(strA, strB);
if(cmp < 0) {
@@ -252,29 +252,29 @@ static alpm_list_t *filelist_operation(alpm_list_t *filesA, alpm_list_t *filesB,
/* item only in filesA, qualifies as a difference */
ret = alpm_list_add(ret, fileA);
}
- pA = pA->next;
+ ctrA++;
} else if(cmp > 0) {
- pB = pB->next;
+ ctrB++;
} else {
if(operation == INTERSECT) {
/* item in both, qualifies as an intersect */
ret = alpm_list_add(ret, fileA);
}
- pA = pA->next;
- pB = pB->next;
+ ctrA++;
+ ctrB++;
}
}
}
/* if doing a difference, ensure we have completely emptied pA */
- while(operation == DIFFERENCE && pA) {
- alpm_file_t *fileA = pA->data;
+ while(operation == DIFFERENCE && ctrA < filesA->count) {
+ alpm_file_t *fileA = filesA->files + ctrA;
const char *strA = fileA->name;
/* skip directories */
if(strA[strlen(strA)-1] != '/') {
ret = alpm_list_add(ret, fileA);
}
- pA = pA->next;
+ ctrA++;
}
return ret;
@@ -319,16 +319,16 @@ void _alpm_fileconflict_free(alpm_fileconflict_t *conflict)
FREE(conflict);
}
-const alpm_file_t *_alpm_filelist_contains(const alpm_list_t *haystack,
- const char *needle)
+const alpm_file_t *_alpm_filelist_contains(alpm_filelist_t *filelist,
+ const char *name)
{
- const alpm_list_t *lp = haystack;
- while(lp) {
- const alpm_file_t *file = lp->data;
- if(strcmp(file->name, needle) == 0) {
+ size_t i;
+ const alpm_file_t *file = filelist->files;
+ for(i = 0; i < filelist->count; i++) {
+ if(strcmp(file->name, name) == 0) {
return file;
}
- lp = lp->next;
+ file++;
}
return NULL;
}
@@ -400,8 +400,10 @@ alpm_list_t *_alpm_db_find_fileconflicts(alpm_handle_t *handle,
* different cases. */
for(current = 0, i = upgrade; i; i = i->next, current++) {
alpm_pkg_t *p1 = i->data;
- alpm_list_t *j, *tmpfiles;
+ alpm_list_t *j;
+ alpm_filelist_t tmpfiles;
alpm_pkg_t *dbpkg;
+ size_t filenum;
int percent = (current * 100) / numtargs;
PROGRESS(trans, ALPM_TRANS_PROGRESS_CONFLICTS_START, "", percent,
@@ -444,16 +446,21 @@ alpm_list_t *_alpm_db_find_fileconflicts(alpm_handle_t *handle,
* that the former list needs to be freed while the latter list should NOT
* be freed. */
if(dbpkg) {
+ alpm_list_t *difference;
/* older ver of package currently installed */
- tmpfiles = filelist_operation(alpm_pkg_get_files(p1),
+ difference = filelist_operation(alpm_pkg_get_files(p1),
alpm_pkg_get_files(dbpkg), DIFFERENCE);
+ tmpfiles.count = alpm_list_count(difference);
+ tmpfiles.files = alpm_list_to_array(difference, tmpfiles.count,
+ sizeof(alpm_file_t));
+ alpm_list_free(difference);
} else {
/* no version of package currently installed */
- tmpfiles = alpm_pkg_get_files(p1);
+ tmpfiles = *alpm_pkg_get_files(p1);
}
- for(j = tmpfiles; j; j = j->next) {
- alpm_file_t *file = j->data;
+ for(filenum = 0; filenum < tmpfiles.count; filenum++) {
+ alpm_file_t *file = tmpfiles.files + filenum;
const char *filestr = file->name;
const char *relative_path;
alpm_list_t *k;
@@ -572,7 +579,7 @@ alpm_list_t *_alpm_db_find_fileconflicts(alpm_handle_t *handle,
FREELIST(conflicts);
if(dbpkg) {
/* only freed if it was generated from filelist_operation() */
- alpm_list_free(tmpfiles);
+ free(tmpfiles.files);
}
return NULL;
}
@@ -580,7 +587,7 @@ alpm_list_t *_alpm_db_find_fileconflicts(alpm_handle_t *handle,
}
if(dbpkg) {
/* only freed if it was generated from filelist_operation() */
- alpm_list_free(tmpfiles);
+ free(tmpfiles.files);
}
}
PROGRESS(trans, ALPM_TRANS_PROGRESS_CONFLICTS_START, "", 100,