From: | Andres Freund <andres(at)2ndquadrant(dot)com> |
---|---|
To: | pgsql-hackers(at)postgresql(dot)org |
Cc: | Marko Kreen <markokr(at)gmail(dot)com> |
Subject: | Re: [PATCH 04/16] Add embedded list interface (header only) |
Date: | 2012-06-19 20:02:57 |
Message-ID: | 201206192202.58151.andres@2ndquadrant.com |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-hackers |
Hi,
On Tuesday, June 19, 2012 09:59:48 PM Marko Kreen wrote:
> On Wed, Jun 13, 2012 at 2:28 PM, Andres Freund <andres(at)2ndquadrant(dot)com>
wrote:
> > +/*
> > + * removes a node from a list
> > + * Attention: O(n)
> > + */
> > +static inline void ilist_s_remove(ilist_s_head *head,
> > + ilist_s_node *node)
> > +{
> > + ilist_s_node *last = &head->head;
> > + ilist_s_node *cur;
> > +#ifndef NDEBUG
> > + bool found = false;
> > +#endif
> > + while ((cur = last->next))
> > + {
> > + if (cur == node)
> > + {
> > + last->next = cur->next;
> > +#ifndef NDEBUG
> > + found = true;
> > +#endif
> > + break;
> > + }
> > + last = cur;
> > + }
> > + assert(found);
> > +}
>
> This looks weird.
>
> In cyclic list removal is:
>
> node->prev->next = node->next;
> node->next->prev = node->prev;
>
> And thats it.
Thats the single linked list, not the double linked one. Thats why it has a
O(n) warning tacked on...
The double linked one is just as you said:
/*
* removes a node from a list
*/
static inline void ilist_d_remove(unused_attr ilist_d_head *head, ilist_d_node
*node)
{
ilist_d_check(head);
node->prev->next = node->next;
node->next->prev = node->prev;
ilist_d_check(head);
}
Greetings,
Andres
--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services
From | Date | Subject | |
---|---|---|---|
Next Message | Andres Freund | 2012-06-19 20:07:36 | Re: [PATCH 01/16] Overhaul walsender wakeup handling |
Previous Message | Marko Kreen | 2012-06-19 19:59:48 | Re: [PATCH 04/16] Add embedded list interface (header only) |