Horton

Re: [PATCH 04/16] Add embedded list interface (header only)

Andres Freund <andres@2ndquadrant.com>

View thread
From: Andres Freund <andres@2ndquadrant.com>
To: pgsql-hackers@postgresql.org
Cc: Marko Kreen <markokr@gmail.com>
Date: 2012-06-19T20:02:57Z
Lists: pgsql-hackers

Commits

Same data as JSON: GET /api/v1/messages/:b64id/commits the thread's linked commits as JSON, with link sources. API reference →

  1. Don't waste the last segment of each 4GB logical log file.

  2. Stamp HEAD as 9.3devel.

  3. Wake WALSender to reduce data loss at failover for async commit.

  4. Make the visibility map crash-safe.

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@2ndquadrant.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