[pacman-dev] [GIT] The official pacman repository branch, master, updated. v3.0.0-531-gd0d5848
This is an automated email from the git hooks/post-receive script. It was generated because a ref change was pushed to the repository containing the project "The official pacman repository". The branch, master has been updated via d0d58489ff8b4458719e4bceb6a5d7290c99588a (commit) via 2ee90ddae23dd86c68223c0d6c49f0b92d62429d (commit) from bdab234d977dd2e9417a39f5191e495d5c460ee7 (commit) Those revisions listed above that are new to this repository have not appeared on any other notification email; so we list those revisions in full, below. - Log ----------------------------------------------------------------- commit d0d58489ff8b4458719e4bceb6a5d7290c99588a Author: Aaron Griffin <aaronmgriffin@gmail.com> Date: Tue Nov 6 22:50:21 2007 -0600 Add STRDUP macro to mirror MALLOC/CALLOC Signed-off-by: Aaron Griffin <aaronmgriffin@gmail.com> commit 2ee90ddae23dd86c68223c0d6c49f0b92d62429d Author: Aaron Griffin <aaronmgriffin@gmail.com> Date: Tue Nov 6 00:55:45 2007 -0600 Maintain list tail pointers in the head node 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> ----------------------------------------------------------------------- Summary of changes: lib/libalpm/alpm_list.c | 59 +++++++++++++++++++++++++++++++++++------------ lib/libalpm/remove.c | 3 +- lib/libalpm/util.h | 2 + 3 files changed, 48 insertions(+), 16 deletions(-) hooks/post-receive -- The official pacman repository
commit 2ee90ddae23dd86c68223c0d6c49f0b92d62429d Author: Aaron Griffin <aaronmgriffin@gmail.com> Date: Tue Nov 6 00:55:45 2007 -0600
Maintain list tail pointers in the head node
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>
----------------------------------------------------------------------- Hm. What about alpm_list_remove_node? Bye
---------------------------------------------------- SZTE Egyetemi Könyvtár - http://www.bibl.u-szeged.hu This mail sent through IMP: http://horde.org/imp/
On Nov 8, 2007 1:31 PM, Nagy Gabor <ngaba@bibl.u-szeged.hu> wrote:
commit 2ee90ddae23dd86c68223c0d6c49f0b92d62429d Author: Aaron Griffin <aaronmgriffin@gmail.com> Date: Tue Nov 6 00:55:45 2007 -0600
Maintain list tail pointers in the head node
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>
----------------------------------------------------------------------- Hm. What about alpm_list_remove_node?
I believe I snuck your thing in there too, assuming I understood it correctly: You stated that alpm_list_remove, when removing ALL items from a list only returned the last found data pointer. I adjusted the remove function to only remove the first item.
Hm. What about alpm_list_remove_node?
I believe I snuck your thing in there too, assuming I understood it correctly:
You stated that alpm_list_remove, when removing ALL items from a list only returned the last found data pointer. I adjusted the remove function to only remove the first item.
No. I meant that removing the first node with alpm_list_remove_node will create a "->next circle" now, because node->prev always != NULL. Other issue: If I assume, that alpm_list_reverse shouldn't free the input list (it doesn't free it now), then 1. /* break our reverse circular list */ will corrupt the input list without restoring 2. files = alpm_list_reverse(files) in your remove.c.diff is a memleak. Bye ---------------------------------------------------- SZTE Egyetemi Könyvtár - http://www.bibl.u-szeged.hu This mail sent through IMP: http://horde.org/imp/
On Nov 9, 2007 5:13 AM, Nagy Gabor <ngaba@bibl.u-szeged.hu> wrote:
Hm. What about alpm_list_remove_node?
I believe I snuck your thing in there too, assuming I understood it correctly:
You stated that alpm_list_remove, when removing ALL items from a list only returned the last found data pointer. I adjusted the remove function to only remove the first item.
No. I meant that removing the first node with alpm_list_remove_node will create a "->next circle" now, because node->prev always != NULL.
I don't know what you're talking about. That sentence makes no sense. At the very least please point to some code or something. Please stop doing this, it's annoying. At the very least give us freaking line numbers - I thought i talked to you about this?
On Nov 9, 2007 5:13 AM, Nagy Gabor <ngaba@bibl.u-szeged.hu> wrote:
Hm. What about alpm_list_remove_node?
I believe I snuck your thing in there too, assuming I understood it correctly:
You stated that alpm_list_remove, when removing ALL items from a list only returned the last found data pointer. I adjusted the remove function to only remove the first item.
No. I meant that removing the first node with alpm_list_remove_node will create a "->next circle" now, because node->prev always != NULL.
I don't know what you're talking about. That sentence makes no sense. At the very least please point to some code or something. Please stop doing this, it's annoying. At the very least give us freaking line numbers - I thought i talked to you about this? If you don't understand me, please try to simulate/think of _without any help_: what happens, if you want to remove the first node of a list with alpm_list_remove_node()... If you managed to do it, you will understand that sentence;-) (Hint: node->prev points to the tail in that case)
Some more issues: 1. You simply forgot about resetting the tail pointer when you remove the last element with alpm_list_remove. 2. As I see, alpm_list_remove_node is used nowhere in the code, and dangerous (when you remove the first or last node, "interesting" things can happen); so that should be removed. Bye
On Fri, Nov 09, 2007 at 08:54:52PM +0100, Nagy Gabor wrote:
Some more issues: 1. You simply forgot about resetting the tail pointer when you remove the last element with alpm_list_remove.
Yep, that's what explains the requiredby problem I noticed : http://www.archlinux.org/pipermail/pacman-dev/2007-November/009919.html Good catch :)
2. As I see, alpm_list_remove_node is used nowhere in the code, and dangerous (when you remove the first or last node, "interesting" things can happen); so that should be removed.
Oh right, I first thought the requiredby problem was caused by the issues you mentioned in remove_node (I thought remove used remove_node), but indeed, this function isn't used anywhere.
On Nov 9, 2007 2:55 PM, Xavier <shiningxc@gmail.com> wrote:
On Fri, Nov 09, 2007 at 08:54:52PM +0100, Nagy Gabor wrote:
Some more issues: 1. You simply forgot about resetting the tail pointer when you remove the last element with alpm_list_remove.
Yep, that's what explains the requiredby problem I noticed : http://www.archlinux.org/pipermail/pacman-dev/2007-November/009919.html Good catch :)
This should fix it. diff --git a/lib/libalpm/alpm_list.c b/lib/libalpm/alpm_list.c index 6f6ee8f..f2e57c0 100644 --- a/lib/libalpm/alpm_list.c +++ b/lib/libalpm/alpm_list.c @@ -311,6 +311,9 @@ alpm_list_t SYMEXPORT *alpm_list_remove(alpm_list_t *haystac k, const void *needl /* Normal case, non-head node */ if(i->next) { i->next->prev = i->prev; + } else { + /* We are on the tail node, need to upda te the back ref */ + haystack->prev = i->prev; } if(i->prev) { i->prev->next = i->next;
2. As I see, alpm_list_remove_node is used nowhere in the code, and dangerous (when you remove the first or last node, "interesting" things can happen); so that should be removed.
Oh right, I first thought the requiredby problem was caused by the issues you mentioned in remove_node (I thought remove used remove_node), but indeed, this function isn't used anywhere.
Killed locally too. I'll probably commit this, although I want to check where it was used originally before I kill it off. -Dan
On Nov 9, 2007 3:20 PM, Dan McGee <dpmcgee@gmail.com> wrote:
On Nov 9, 2007 2:55 PM, Xavier <shiningxc@gmail.com> wrote:
On Fri, Nov 09, 2007 at 08:54:52PM +0100, Nagy Gabor wrote:
Some more issues: 1. You simply forgot about resetting the tail pointer when you remove the last element with alpm_list_remove.
Yep, that's what explains the requiredby problem I noticed : http://www.archlinux.org/pipermail/pacman-dev/2007-November/009919.html Good catch :)
This should fix it.
diff --git a/lib/libalpm/alpm_list.c b/lib/libalpm/alpm_list.c index 6f6ee8f..f2e57c0 100644 --- a/lib/libalpm/alpm_list.c +++ b/lib/libalpm/alpm_list.c @@ -311,6 +311,9 @@ alpm_list_t SYMEXPORT *alpm_list_remove(alpm_list_t *haystac k, const void *needl /* Normal case, non-head node */ if(i->next) { i->next->prev = i->prev; + } else { + /* We are on the tail node, need to upda te the back ref */ + haystack->prev = i->prev; } if(i->prev) { i->prev->next = i->next;
Be careful here - the special cases or head nodes typically needed to be added after the "if next" and "if prev" stuff already there, as they never took the terminal nodes to be any different. By that, I mean if(next) { do stuff } if(prev) { do stuff } if(!next) { tail node } I'm sure it could be restructured, but I'll leave that for the CS students 8)
On Nov 9, 2007 3:25 PM, Aaron Griffin <aaronmgriffin@gmail.com> wrote:
On Nov 9, 2007 3:20 PM, Dan McGee <dpmcgee@gmail.com> wrote:
On Nov 9, 2007 2:55 PM, Xavier <shiningxc@gmail.com> wrote:
On Fri, Nov 09, 2007 at 08:54:52PM +0100, Nagy Gabor wrote:
Some more issues: 1. You simply forgot about resetting the tail pointer when you remove the last element with alpm_list_remove.
Yep, that's what explains the requiredby problem I noticed : http://www.archlinux.org/pipermail/pacman-dev/2007-November/009919.html Good catch :)
This should fix it.
diff --git a/lib/libalpm/alpm_list.c b/lib/libalpm/alpm_list.c index 6f6ee8f..f2e57c0 100644 --- a/lib/libalpm/alpm_list.c +++ b/lib/libalpm/alpm_list.c @@ -311,6 +311,9 @@ alpm_list_t SYMEXPORT *alpm_list_remove(alpm_list_t *haystac k, const void *needl /* Normal case, non-head node */ if(i->next) { i->next->prev = i->prev; + } else { + /* We are on the tail node, need to upda te the back ref */ + haystack->prev = i->prev; } if(i->prev) { i->prev->next = i->next;
Be careful here - the special cases or head nodes typically needed to be added after the "if next" and "if prev" stuff already there, as they never took the terminal nodes to be any different. By that, I mean
if(next) { do stuff } if(prev) { do stuff } if(!next) { tail node }
I'm sure it could be restructured, but I'll leave that for the CS students 8)
OK, try 2. :) diff --git a/lib/libalpm/alpm_list.c b/lib/libalpm/alpm_list.c index d3a7951..465c1a8 100644 --- a/lib/libalpm/alpm_list.c +++ b/lib/libalpm/alpm_list.c @@ -301,14 +301,22 @@ alpm_list_t SYMEXPORT *alpm_list_remove(alpm_list_t *haystack, const void *needl if(i == haystack) { /* Special case: removing the head node which has a back reference to * the tail node */ - /* The item found is the first in the chain */ haystack = i->next; if(haystack) { haystack->prev = i->prev; } i->prev = NULL; + } else if(i == haystack->prev) { + /* Special case: removing the tail node, so we need to fix the back + * reference on the head node. We also know tail != head. */ + if(i->prev) { + /* i->next should always be null */ + i->prev->next = i->next; + haystack->prev = i->prev; + i->prev = NULL; + } } else { - /* Normal case, non-head node */ + /* Normal case, non-head and non-tail node */ if(i->next) { i->next->prev = i->prev; }
I'm really confused by this email, so let me see if I understood this properly. What you mean to say is as follows: On Nov 9, 2007 5:13 AM, Nagy Gabor <ngaba@bibl.u-szeged.hu> wrote:
No. I meant that removing the first node with alpm_list_remove_node will create a "->next circle" now, because node->prev always != NULL.
A "->next circle" is what? A circular list in the forward/next direction? "removing the first node" meaning the first node in the list (head node)? the first node found? I'd like to fix this but I really have no idea what you mean - I'm not trying to be an ass, I just don't get it.
1. /* break our reverse circular list */ will corrupt the input list without restoring
To be clear, line 459 is what you mean? Is this what you intended to say: Setting the head node's ->prev point to NULL corrupts the passed in list ?
2. files = alpm_list_reverse(files) in your remove.c.diff is a memleak.
This one I understand. It has real code and a concise explanation of the problem. Thanks
I'm really confused by this email, so let me see if I understood this properly. What you mean to say is as follows:
On Nov 9, 2007 5:13 AM, Nagy Gabor <ngaba@bibl.u-szeged.hu> wrote:
No. I meant that removing the first node with alpm_list_remove_node will create a "->next circle" now, because node->prev always != NULL.
A "->next circle" is what? A circular list in the forward/next direction? "removing the first node" meaning the first node in the list (head node)? the first node found?
I'd like to fix this but I really have no idea what you mean - I'm not trying to be an ass, I just don't get it.
1. /* break our reverse circular list */ will corrupt the input list without restoring
To be clear, line 459 is what you mean? Is this what you intended to say: Setting the head node's ->prev point to NULL corrupts the passed in list ?
Yes, I mean line 349 <- I assume a typo here ;-) But I suggest simply remove that function, as Dan said. I explain why (this will be boring): I simply cannot understand how this function should be called: I imagine something like this: for (i=list; i; i=i->next) { if(foo(i)) alpm_list_remove_node(i); } But there are some problems here: 1. If you remove (detach) the first node, list will point to a corrupt 1-element (the old 1st element) list, and other nodes will be lost. So you have to keep this in mind in the _caller_ function. 2. After Aaron tail-patch, you must reset tail-pointer if you remove the last element (like in alpm_list_remove); which is not a nice game again, since alpm_list_remove_node doesn't know too much about the "whole" list. Bye, ngaba
On Nov 9, 2007 4:24 PM, Nagy Gabor <ngaba@bibl.u-szeged.hu> wrote:
Yes, I mean line 349 <- I assume a typo here ;-) But I suggest simply remove that function, as Dan said.
Yeah. It's unused. Lets kill it, it solves the issue - and probably explains why it was unnoticed.
participants (5)
-
Aaron Griffin
-
Aaron Griffin
-
Dan McGee
-
Nagy Gabor
-
Xavier