Hi, On Tuesday, June 19, 2012 09:59:48 PM Marko Kreen wrote: > On Wed, Jun 13, 2012 at 2:28 PM, Andres Freund <and...@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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers