Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitcf707aa

Browse files
committed
Improve ilist.h's support for deletion of slist elements during iteration.
Previously one had to use slist_delete(), implying an additional scan ofthe list, making this infrastructure considerably less efficient thantraditional Lists when deletion of element(s) in a long list is needed.Modify the slist_foreach_modify() macro to support deleting the currentelement 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 todelete the current list element you might as well just use slist_foreachinstead. Improve the comments about when to use each macro.Back-patch to 9.3 so that we'll have consistent semantics in all branchesthat provide ilist.h. Note this is an ABI break for callers ofslist_foreach_modify().Andres Freund and Tom Lane
1 parent4a67a9a commitcf707aa

File tree

3 files changed

+59
-12
lines changed

3 files changed

+59
-12
lines changed

‎src/backend/lib/ilist.c

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -28,7 +28,7 @@
2828
*
2929
* It is not allowed to delete a 'node' which is is not in the list 'head'
3030
*
31-
* Caution: this is O(n)
31+
* Caution: this is O(n); consider using slist_delete_current() instead.
3232
*/
3333
void
3434
slist_delete(slist_head*head,slist_node*node)

‎src/backend/postmaster/pgstat.c

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -3598,6 +3598,13 @@ pgstat_write_statsfiles(bool permanent, bool allDbs)
35983598
{
35993599
slist_mutable_iteriter;
36003600

3601+
/*
3602+
* Strictly speaking we should do slist_delete_current() before
3603+
* freeing each request struct. We skip that and instead
3604+
* re-initialize the list header at the end. Nonetheless, we must use
3605+
* slist_foreach_modify, not just slist_foreach, since we will free
3606+
* the node's storage before advancing.
3607+
*/
36013608
slist_foreach_modify(iter,&last_statrequests)
36023609
{
36033610
DBWriteRequest*req;

‎src/include/lib/ilist.h

Lines changed: 51 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -211,9 +211,14 @@ typedef struct slist_head
211211
* Used as state in slist_foreach(). To get the current element of the
212212
* iteration use the 'cur' member.
213213
*
214-
* Do *not* manipulate the list while iterating!
215-
*
216-
* NB: this wouldn't really need to be an extra struct, we could use a
214+
* It's allowed to modify the list while iterating, with the exception of
215+
* deleting the iterator's current node; deletion of that node requires
216+
* care if the iteration is to be continued afterward.(Doing so and also
217+
* deleting or inserting adjacent list elements might misbehave; also, if
218+
* the user frees the current node's storage, continuing the iteration is
219+
* not safe.)
220+
*
221+
* NB: this wouldn't really need to be an extra struct, we could use an
217222
* slist_node * directly. We prefer a separate type for consistency.
218223
*/
219224
typedefstructslist_iter
@@ -224,15 +229,18 @@ typedef struct slist_iter
224229
/*
225230
* Singly linked list iterator allowing some modifications while iterating.
226231
*
227-
* Used as state in slist_foreach_modify().
232+
* Used as state in slist_foreach_modify(). To get the current element of the
233+
* iteration use the 'cur' member.
228234
*
229-
* Iterations using this are allowed to remove the current node and to add
230-
* more nodes ahead of the current node.
235+
* The only list modification allowed while iterating is to remove the current
236+
* node via slist_delete_current() (*not* slist_delete()).Insertion or
237+
* deletion of nodes adjacent to the current node would misbehave.
231238
*/
232239
typedefstructslist_mutable_iter
233240
{
234241
slist_node*cur;/* current element */
235242
slist_node*next;/* next node we'll iterate to */
243+
slist_node*prev;/* prev node, for deletions */
236244
}slist_mutable_iter;
237245

238246

@@ -243,7 +251,7 @@ typedef struct slist_mutable_iter
243251

244252
/* Prototypes for functions too big to be inline */
245253

246-
/* Caution: this is O(n) */
254+
/* Caution: this is O(n); consider using slist_delete_current() instead */
247255
externvoidslist_delete(slist_head*head,slist_node*node);
248256

249257
#ifdefILIST_DEBUG
@@ -578,6 +586,7 @@ extern slist_node *slist_pop_head_node(slist_head *head);
578586
externboolslist_has_next(slist_head*head,slist_node*node);
579587
externslist_node*slist_next_node(slist_head*head,slist_node*node);
580588
externslist_node*slist_head_node(slist_head*head);
589+
externvoidslist_delete_current(slist_mutable_iter*iter);
581590

582591
/* slist macro support function */
583592
externvoid*slist_head_element_off(slist_head*head,size_toff);
@@ -679,6 +688,29 @@ slist_head_node(slist_head *head)
679688
{
680689
return (slist_node*)slist_head_element_off(head,0);
681690
}
691+
692+
/*
693+
* Delete the list element the iterator currently points to.
694+
*
695+
* Caution: this modifies iter->cur, so don't use that again in the current
696+
* loop iteration.
697+
*/
698+
STATIC_IF_INLINEvoid
699+
slist_delete_current(slist_mutable_iter*iter)
700+
{
701+
/*
702+
* Update previous element's forward link. If the iteration is at the
703+
* first list element, iter->prev will point to the list header's "head"
704+
* field, so we don't need a special case for that.
705+
*/
706+
iter->prev->next=iter->next;
707+
708+
/*
709+
* Reset cur to prev, so that prev will continue to point to the prior
710+
* valid list element after slist_foreach_modify() advances to the next.
711+
*/
712+
iter->cur=iter->prev;
713+
}
682714
#endif/* PG_USE_INLINE || ILIST_INCLUDE_DEFINITIONS */
683715

684716
/*
@@ -706,7 +738,12 @@ slist_head_node(slist_head *head)
706738
*
707739
* Access the current element with iter.cur.
708740
*
709-
* It is *not* allowed to manipulate the list during iteration.
741+
* It's allowed to modify the list while iterating, with the exception of
742+
* deleting the iterator's current node; deletion of that node requires
743+
* care if the iteration is to be continued afterward.(Doing so and also
744+
* deleting or inserting adjacent list elements might misbehave; also, if
745+
* the user frees the current node's storage, continuing the iteration is
746+
* not safe.)
710747
*/
711748
#defineslist_foreach(iter,lhead)\
712749
for (AssertVariableIsOfTypeMacro(iter, slist_iter),\
@@ -720,15 +757,18 @@ slist_head_node(slist_head *head)
720757
*
721758
* Access the current element with iter.cur.
722759
*
723-
* Iterations using this are allowed to remove the current node and to add
724-
* more nodes ahead of the current node.
760+
* The only list modification allowed while iterating is to remove the current
761+
* node via slist_delete_current() (*not* slist_delete()).Insertion or
762+
* deletion of nodes adjacent to the current node would misbehave.
725763
*/
726764
#defineslist_foreach_modify(iter,lhead)\
727765
for (AssertVariableIsOfTypeMacro(iter, slist_mutable_iter),\
728766
AssertVariableIsOfTypeMacro(lhead, slist_head *),\
729-
(iter).cur = (lhead)->head.next,\
767+
(iter).prev = &(lhead)->head,\
768+
(iter).cur = (iter).prev->next,\
730769
(iter).next = (iter).cur ? (iter).cur->next : NULL;\
731770
(iter).cur != NULL;\
771+
(iter).prev = (iter).cur,\
732772
(iter).cur = (iter).next,\
733773
(iter).next = (iter).next ? (iter).next->next : NULL)
734774

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp