From fa2fad3c06bfde03594ff38d53acdf9a60c56bb2 Mon Sep 17 00:00:00 2001 From: Tom Lane Date: Wed, 24 Jul 2013 17:41:55 -0400 Subject: Improve ilist.h's support for deletion of slist elements during iteration. Previously one had to use slist_delete(), implying an additional scan of the list, making this infrastructure considerably less efficient than traditional Lists when deletion of element(s) in a long list is needed. Modify the slist_foreach_modify() macro to support deleting the current element in O(1) time, by keeping a "prev" pointer in addition to "cur" and "next". Although this makes iteration with this macro a bit slower, no real harm is done, since in any scenario where you're not going to delete the current list element you might as well just use slist_foreach instead. Improve the comments about when to use each macro. Back-patch to 9.3 so that we'll have consistent semantics in all branches that provide ilist.h. Note this is an ABI break for callers of slist_foreach_modify(). Andres Freund and Tom Lane --- src/backend/lib/ilist.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/backend/lib/ilist.c') diff --git a/src/backend/lib/ilist.c b/src/backend/lib/ilist.c index 957a1181227..eb23fa1c687 100644 --- a/src/backend/lib/ilist.c +++ b/src/backend/lib/ilist.c @@ -28,7 +28,7 @@ * * It is not allowed to delete a 'node' which is is not in the list 'head' * - * Caution: this is O(n) + * Caution: this is O(n); consider using slist_delete_current() instead. */ void slist_delete(slist_head *head, slist_node *node) -- cgit v1.2.3