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

Commitfa2fad3

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 parent910d3a4 commitfa2fad3

File tree

6 files changed

+72
-20
lines changed

6 files changed

+72
-20
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/bgworker.c

Lines changed: 10 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -267,15 +267,20 @@ BackgroundWorkerStateChange(void)
267267
/*
268268
* Forget about a background worker that's no longer needed.
269269
*
270-
* At present, this only happens when a background worker marked
271-
* BGW_NEVER_RESTART exits. This function should only be invoked in
272-
* the postmaster.
270+
* The worker must be identified by passing an slist_mutable_iter that
271+
* points to it. This convention allows deletion of workers during
272+
* searches of the worker list, and saves having to search the list again.
273+
*
274+
* This function must be invoked only in the postmaster.
273275
*/
274276
void
275-
ForgetBackgroundWorker(RegisteredBgWorker*rw)
277+
ForgetBackgroundWorker(slist_mutable_iter*cur)
276278
{
279+
RegisteredBgWorker*rw;
277280
BackgroundWorkerSlot*slot;
278281

282+
rw=slist_container(RegisteredBgWorker,rw_lnode,cur->cur);
283+
279284
Assert(rw->rw_shmem_slot<max_worker_processes);
280285
slot=&BackgroundWorkerData->slot[rw->rw_shmem_slot];
281286
slot->in_use= false;
@@ -284,7 +289,7 @@ ForgetBackgroundWorker(RegisteredBgWorker *rw)
284289
(errmsg("unregistering background worker: %s",
285290
rw->rw_worker.bgw_name)));
286291

287-
slist_delete(&BackgroundWorkerList,&rw->rw_lnode);
292+
slist_delete_current(cur);
288293
free(rw);
289294
}
290295

‎src/backend/postmaster/pgstat.c

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -3602,6 +3602,13 @@ pgstat_write_statsfiles(bool permanent, bool allDbs)
36023602
{
36033603
slist_mutable_iteriter;
36043604

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

‎src/backend/postmaster/postmaster.c

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1452,7 +1452,7 @@ DetermineSleepTime(struct timeval * timeout)
14521452

14531453
if (rw->rw_worker.bgw_restart_time==BGW_NEVER_RESTART)
14541454
{
1455-
ForgetBackgroundWorker(rw);
1455+
ForgetBackgroundWorker(&siter);
14561456
continue;
14571457
}
14581458

@@ -5641,7 +5641,7 @@ StartOneBackgroundWorker(void)
56415641
{
56425642
if (rw->rw_worker.bgw_restart_time==BGW_NEVER_RESTART)
56435643
{
5644-
ForgetBackgroundWorker(rw);
5644+
ForgetBackgroundWorker(&iter);
56455645
continue;
56465646
}
56475647

‎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

‎src/include/postmaster/bgworker_internals.h

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -39,7 +39,7 @@ extern slist_head BackgroundWorkerList;
3939
externSizeBackgroundWorkerShmemSize(void);
4040
externvoidBackgroundWorkerShmemInit(void);
4141
externvoidBackgroundWorkerStateChange(void);
42-
externvoidForgetBackgroundWorker(RegisteredBgWorker*);
42+
externvoidForgetBackgroundWorker(slist_mutable_iter*cur);
4343

4444
#ifdefEXEC_BACKEND
4545
externBackgroundWorker*BackgroundWorkerEntry(intslotno);

0 commit comments

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