From: | Marko Kreen <markokr(at)gmail(dot)com> |
---|---|
To: | Andres Freund <andres(at)2ndquadrant(dot)com> |
Cc: | pgsql-hackers(at)postgresql(dot)org |
Subject: | Re: [PATCH 04/16] Add embedded list interface (header only) |
Date: | 2012-06-19 20:19:02 |
Message-ID: | CACMqXCLb=cs7jthNesAx+V=fVpOJiAFCGsM9U8oK+hmrR=bJtg@mail.gmail.com |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-hackers |
On Tue, Jun 19, 2012 at 11:02 PM, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
> 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...
Oh, you have several list implementations there.
Sorry, I was just browsing and it caught my eye.
--
marko
From | Date | Subject | |
---|---|---|---|
Next Message | Andres Freund | 2012-06-19 20:22:19 | Re: [PATCH 04/16] Add embedded list interface (header only) |
Previous Message | Andres Freund | 2012-06-19 20:07:36 | Re: [PATCH 01/16] Overhaul walsender wakeup handling |