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

Commit7c335b7

Browse files
committed
Add doubly linked count list implementation
We have various requirements when using a dlist_head to keep track of thenumber of items in the list. This, traditionally, has been done bymaintaining a counter variable in the calling code. Here we tidy this upby adding "dclist", which is very similar to dlist but also keeps track ofthe number of items stored in the list.Callers may use the new dclist_count() function when they need to know howmany items are stored. Obtaining the count is an O(1) operation.For simplicity reasons, dclist and dlist both use dlist_node as their nodetype and dlist_iter/dlist_mutable_iter as their iterator type. dclistshave all of the same functionality as dlists except there is no functionnamed dclist_delete(). To remove an item from a list dclist_delete_from()must be used. This requires knowing which dclist the given item is storedin.Additionally, here we also convert some dlists where additional codeexists to keep track of the number of items stored and to make these usedclists instead.Author: David RowleyReviewed-by: Bharath Rupireddy, Aleksander AlekseevDiscussion:https://postgr.es/m/CAApHDvrtVxr+FXEX0VbViCFKDGxA3tWDgw9oFewNXCJMmwLjLg@mail.gmail.com
1 parent451d116 commit7c335b7

File tree

11 files changed

+448
-109
lines changed

11 files changed

+448
-109
lines changed

‎src/backend/access/heap/rewriteheap.c

Lines changed: 11 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -196,8 +196,7 @@ typedef struct RewriteMappingFile
196196
TransactionIdxid;/* xid that might need to see the row */
197197
intvfd;/* fd of mappings file */
198198
off_toff;/* how far have we written yet */
199-
uint32num_mappings;/* number of in-memory mappings */
200-
dlist_headmappings;/* list of in-memory mappings */
199+
dclist_headmappings;/* list of in-memory mappings */
201200
charpath[MAXPGPATH];/* path, for error messages */
202201
}RewriteMappingFile;
203202

@@ -864,49 +863,49 @@ logical_heap_rewrite_flush_mappings(RewriteState state)
864863
Oiddboid;
865864
uint32len;
866865
intwritten;
866+
uint32num_mappings=dclist_count(&src->mappings);
867867

868868
/* this file hasn't got any new mappings */
869-
if (src->num_mappings==0)
869+
if (num_mappings==0)
870870
continue;
871871

872872
if (state->rs_old_rel->rd_rel->relisshared)
873873
dboid=InvalidOid;
874874
else
875875
dboid=MyDatabaseId;
876876

877-
xlrec.num_mappings=src->num_mappings;
877+
xlrec.num_mappings=num_mappings;
878878
xlrec.mapped_rel=RelationGetRelid(state->rs_old_rel);
879879
xlrec.mapped_xid=src->xid;
880880
xlrec.mapped_db=dboid;
881881
xlrec.offset=src->off;
882882
xlrec.start_lsn=state->rs_begin_lsn;
883883

884884
/* write all mappings consecutively */
885-
len=src->num_mappings*sizeof(LogicalRewriteMappingData);
885+
len=num_mappings*sizeof(LogicalRewriteMappingData);
886886
waldata_start=waldata=palloc(len);
887887

888888
/*
889889
* collect data we need to write out, but don't modify ondisk data yet
890890
*/
891-
dlist_foreach_modify(iter,&src->mappings)
891+
dclist_foreach_modify(iter,&src->mappings)
892892
{
893893
RewriteMappingDataEntry*pmap;
894894

895-
pmap=dlist_container(RewriteMappingDataEntry,node,iter.cur);
895+
pmap=dclist_container(RewriteMappingDataEntry,node,iter.cur);
896896

897897
memcpy(waldata,&pmap->map,sizeof(pmap->map));
898898
waldata+=sizeof(pmap->map);
899899

900900
/* remove from the list and free */
901-
dlist_delete(&pmap->node);
901+
dclist_delete_from(&src->mappings,&pmap->node);
902902
pfree(pmap);
903903

904904
/* update bookkeeping */
905905
state->rs_num_rewrite_mappings--;
906-
src->num_mappings--;
907906
}
908907

909-
Assert(src->num_mappings==0);
908+
Assert(dclist_count(&src->mappings)==0);
910909
Assert(waldata==waldata_start+len);
911910

912911
/*
@@ -1002,8 +1001,7 @@ logical_rewrite_log_mapping(RewriteState state, TransactionId xid,
10021001
LSN_FORMAT_ARGS(state->rs_begin_lsn),
10031002
xid,GetCurrentTransactionId());
10041003

1005-
dlist_init(&src->mappings);
1006-
src->num_mappings=0;
1004+
dclist_init(&src->mappings);
10071005
src->off=0;
10081006
memcpy(src->path,path,sizeof(path));
10091007
src->vfd=PathNameOpenFile(path,
@@ -1017,8 +1015,7 @@ logical_rewrite_log_mapping(RewriteState state, TransactionId xid,
10171015
pmap=MemoryContextAlloc(state->rs_cxt,
10181016
sizeof(RewriteMappingDataEntry));
10191017
memcpy(&pmap->map,map,sizeof(LogicalRewriteMappingData));
1020-
dlist_push_tail(&src->mappings,&pmap->node);
1021-
src->num_mappings++;
1018+
dclist_push_tail(&src->mappings,&pmap->node);
10221019
state->rs_num_rewrite_mappings++;
10231020

10241021
/*

‎src/backend/access/transam/multixact.c

Lines changed: 16 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -319,8 +319,7 @@ typedef struct mXactCacheEnt
319319
}mXactCacheEnt;
320320

321321
#defineMAX_CACHE_ENTRIES256
322-
staticdlist_headMXactCache=DLIST_STATIC_INIT(MXactCache);
323-
staticintMXactCacheMembers=0;
322+
staticdclist_headMXactCache=DCLIST_STATIC_INIT(MXactCache);
324323
staticMemoryContextMXactContext=NULL;
325324

326325
#ifdefMULTIXACT_DEBUG
@@ -1504,9 +1503,10 @@ mXactCacheGetBySet(int nmembers, MultiXactMember *members)
15041503
/* sort the array so comparison is easy */
15051504
qsort(members,nmembers,sizeof(MultiXactMember),mxactMemberComparator);
15061505

1507-
dlist_foreach(iter,&MXactCache)
1506+
dclist_foreach(iter,&MXactCache)
15081507
{
1509-
mXactCacheEnt*entry=dlist_container(mXactCacheEnt,node,iter.cur);
1508+
mXactCacheEnt*entry=dclist_container(mXactCacheEnt,node,
1509+
iter.cur);
15101510

15111511
if (entry->nmembers!=nmembers)
15121512
continue;
@@ -1518,7 +1518,7 @@ mXactCacheGetBySet(int nmembers, MultiXactMember *members)
15181518
if (memcmp(members,entry->members,nmembers*sizeof(MultiXactMember))==0)
15191519
{
15201520
debug_elog3(DEBUG2,"CacheGet: found %u",entry->multi);
1521-
dlist_move_head(&MXactCache,iter.cur);
1521+
dclist_move_head(&MXactCache,iter.cur);
15221522
returnentry->multi;
15231523
}
15241524
}
@@ -1542,9 +1542,10 @@ mXactCacheGetById(MultiXactId multi, MultiXactMember **members)
15421542

15431543
debug_elog3(DEBUG2,"CacheGet: looking for %u",multi);
15441544

1545-
dlist_foreach(iter,&MXactCache)
1545+
dclist_foreach(iter,&MXactCache)
15461546
{
1547-
mXactCacheEnt*entry=dlist_container(mXactCacheEnt,node,iter.cur);
1547+
mXactCacheEnt*entry=dclist_container(mXactCacheEnt,node,
1548+
iter.cur);
15481549

15491550
if (entry->multi==multi)
15501551
{
@@ -1566,7 +1567,7 @@ mXactCacheGetById(MultiXactId multi, MultiXactMember **members)
15661567
* This is acceptable only because we exit the iteration
15671568
* immediately afterwards.
15681569
*/
1569-
dlist_move_head(&MXactCache,iter.cur);
1570+
dclist_move_head(&MXactCache,iter.cur);
15701571

15711572
*members=ptr;
15721573
returnentry->nmembers;
@@ -1610,16 +1611,15 @@ mXactCachePut(MultiXactId multi, int nmembers, MultiXactMember *members)
16101611
/* mXactCacheGetBySet assumes the entries are sorted, so sort them */
16111612
qsort(entry->members,nmembers,sizeof(MultiXactMember),mxactMemberComparator);
16121613

1613-
dlist_push_head(&MXactCache,&entry->node);
1614-
if (MXactCacheMembers++ >=MAX_CACHE_ENTRIES)
1614+
dclist_push_head(&MXactCache,&entry->node);
1615+
if (dclist_count(&MXactCache)>MAX_CACHE_ENTRIES)
16151616
{
16161617
dlist_node*node;
16171618

1618-
node=dlist_tail_node(&MXactCache);
1619-
dlist_delete(node);
1620-
MXactCacheMembers--;
1619+
node=dclist_tail_node(&MXactCache);
1620+
dclist_delete_from(&MXactCache,node);
16211621

1622-
entry=dlist_container(mXactCacheEnt,node,node);
1622+
entry=dclist_container(mXactCacheEnt,node,node);
16231623
debug_elog3(DEBUG2,"CachePut: pruning cached multi %u",
16241624
entry->multi);
16251625

@@ -1699,8 +1699,7 @@ AtEOXact_MultiXact(void)
16991699
* a child of TopTransactionContext, we needn't delete it explicitly.
17001700
*/
17011701
MXactContext=NULL;
1702-
dlist_init(&MXactCache);
1703-
MXactCacheMembers=0;
1702+
dclist_init(&MXactCache);
17041703
}
17051704

17061705
/*
@@ -1766,8 +1765,7 @@ PostPrepare_MultiXact(TransactionId xid)
17661765
* Discard the local MultiXactId cache like in AtEOXact_MultiXact.
17671766
*/
17681767
MXactContext=NULL;
1769-
dlist_init(&MXactCache);
1770-
MXactCacheMembers=0;
1768+
dclist_init(&MXactCache);
17711769
}
17721770

17731771
/*

‎src/backend/lib/ilist.c

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -52,6 +52,23 @@ slist_delete(slist_head *head, slist_node *node)
5252
}
5353

5454
#ifdefILIST_DEBUG
55+
/*
56+
* dlist_member_check
57+
*Validate that 'node' is a member of 'head'
58+
*/
59+
void
60+
dlist_member_check(dlist_head*head,dlist_node*node)
61+
{
62+
dlist_iteriter;
63+
64+
dlist_foreach(iter,head)
65+
{
66+
if (iter.cur==node)
67+
return;
68+
}
69+
elog(ERROR,"double linked list member check failure");
70+
}
71+
5572
/*
5673
* Verify integrity of a doubly linked list
5774
*/

‎src/backend/replication/logical/reorderbuffer.c

Lines changed: 12 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -349,8 +349,6 @@ ReorderBufferAllocate(void)
349349
buffer->by_txn_last_xid=InvalidTransactionId;
350350
buffer->by_txn_last_txn=NULL;
351351

352-
buffer->catchange_ntxns=0;
353-
354352
buffer->outbuf=NULL;
355353
buffer->outbufsize=0;
356354
buffer->size=0;
@@ -368,7 +366,7 @@ ReorderBufferAllocate(void)
368366

369367
dlist_init(&buffer->toplevel_by_lsn);
370368
dlist_init(&buffer->txns_by_base_snapshot_lsn);
371-
dlist_init(&buffer->catchange_txns);
369+
dclist_init(&buffer->catchange_txns);
372370

373371
/*
374372
* Ensure there's no stale data from prior uses of this slot, in case some
@@ -1553,12 +1551,7 @@ ReorderBufferCleanupTXN(ReorderBuffer *rb, ReorderBufferTXN *txn)
15531551
*/
15541552
dlist_delete(&txn->node);
15551553
if (rbtxn_has_catalog_changes(txn))
1556-
{
1557-
dlist_delete(&txn->catchange_node);
1558-
rb->catchange_ntxns--;
1559-
1560-
Assert(rb->catchange_ntxns >=0);
1561-
}
1554+
dclist_delete_from(&rb->catchange_txns,&txn->catchange_node);
15621555

15631556
/* now remove reference from buffer */
15641557
hash_search(rb->by_txn,
@@ -3309,8 +3302,7 @@ ReorderBufferXidSetCatalogChanges(ReorderBuffer *rb, TransactionId xid,
33093302
if (!rbtxn_has_catalog_changes(txn))
33103303
{
33113304
txn->txn_flags |=RBTXN_HAS_CATALOG_CHANGES;
3312-
dlist_push_tail(&rb->catchange_txns,&txn->catchange_node);
3313-
rb->catchange_ntxns++;
3305+
dclist_push_tail(&rb->catchange_txns,&txn->catchange_node);
33143306
}
33153307

33163308
/*
@@ -3323,8 +3315,7 @@ ReorderBufferXidSetCatalogChanges(ReorderBuffer *rb, TransactionId xid,
33233315
if (toptxn!=NULL&& !rbtxn_has_catalog_changes(toptxn))
33243316
{
33253317
toptxn->txn_flags |=RBTXN_HAS_CATALOG_CHANGES;
3326-
dlist_push_tail(&rb->catchange_txns,&toptxn->catchange_node);
3327-
rb->catchange_ntxns++;
3318+
dclist_push_tail(&rb->catchange_txns,&toptxn->catchange_node);
33283319
}
33293320
}
33303321

@@ -3342,19 +3333,17 @@ ReorderBufferGetCatalogChangesXacts(ReorderBuffer *rb)
33423333
size_txcnt=0;
33433334

33443335
/* Quick return if the list is empty */
3345-
if (rb->catchange_ntxns==0)
3346-
{
3347-
Assert(dlist_is_empty(&rb->catchange_txns));
3336+
if (dclist_count(&rb->catchange_txns)==0)
33483337
returnNULL;
3349-
}
33503338

33513339
/* Initialize XID array */
3352-
xids= (TransactionId*)palloc(sizeof(TransactionId)*rb->catchange_ntxns);
3353-
dlist_foreach(iter,&rb->catchange_txns)
3340+
xids= (TransactionId*)palloc(sizeof(TransactionId)*
3341+
dclist_count(&rb->catchange_txns));
3342+
dclist_foreach(iter,&rb->catchange_txns)
33543343
{
3355-
ReorderBufferTXN*txn=dlist_container(ReorderBufferTXN,
3356-
catchange_node,
3357-
iter.cur);
3344+
ReorderBufferTXN*txn=dclist_container(ReorderBufferTXN,
3345+
catchange_node,
3346+
iter.cur);
33583347

33593348
Assert(rbtxn_has_catalog_changes(txn));
33603349

@@ -3363,7 +3352,7 @@ ReorderBufferGetCatalogChangesXacts(ReorderBuffer *rb)
33633352

33643353
qsort(xids,xcnt,sizeof(TransactionId),xidComparator);
33653354

3366-
Assert(xcnt==rb->catchange_ntxns);
3355+
Assert(xcnt==dclist_count(&rb->catchange_txns));
33673356
returnxids;
33683357
}
33693358

‎src/backend/replication/logical/snapbuild.c

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1688,7 +1688,7 @@ SnapBuildSerialize(SnapBuild *builder, XLogRecPtr lsn)
16881688

16891689
/* Get the catalog modifying transactions that are yet not committed */
16901690
catchange_xip=ReorderBufferGetCatalogChangesXacts(builder->reorder);
1691-
catchange_xcnt=builder->reorder->catchange_ntxns;
1691+
catchange_xcnt=dclist_count(&builder->reorder->catchange_txns);
16921692

16931693
needed_length=sizeof(SnapBuildOnDisk)+
16941694
sizeof(TransactionId)* (builder->committed.xcnt+catchange_xcnt);

0 commit comments

Comments
 (0)

[8]ページ先頭

©2009-2025 Movatter.jp