[pacman-dev] Problems with alpm_list_remove(_node)

[Dan McGee]

On Nov 9, 2007 3:25 PM, Aaron Griffin <aaronmgriffin at gmail.com> wrote:
>
> On Nov 9, 2007 3:20 PM, Dan McGee <dpmcgee at gmail.com> wrote:
> > On Nov 9, 2007 2:55 PM, Xavier <shiningxc at 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;
                                }