Skip to content

Commit f4e031c

Browse files
tglsfdctglsfdc
committed
Add bms_next_member(), and use it where appropriate.
This patch adds a way of iterating through the members of a bitmapset nondestructively, unlike the old way with bms_first_member(). While bms_next_member() is very slightly slower than bms_first_member() (at least for typical-size bitmapsets), eliminating the need to palloc and pfree a temporary copy of the target bitmapset is a significant win. So this method should be preferred in all cases where a temporary copy would be necessary. Tom Lane, with suggestions from Dean Rasheed and David Rowley
1 parent 96d66bc commit f4e031c

File tree

13 files changed

+114
-76
lines changed

13 files changed

+114
-76
lines changed

‎contrib/postgres_fdw/postgres_fdw.c

Lines changed: 8 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1198,15 +1198,17 @@ postgresPlanForeignModify(PlannerInfo *root,
11981198
}
11991199
else if (operation == CMD_UPDATE)
12001200
{
1201-
Bitmapset *tmpset = bms_copy(rte->modifiedCols);
1202-
AttrNumber col;
1201+
int col;
12031202

1204-
while ((col = bms_first_member(tmpset)) >= 0)
1203+
col = -1;
1204+
while ((col = bms_next_member(rte->modifiedCols, col)) >= 0)
12051205
{
1206-
col += FirstLowInvalidHeapAttributeNumber;
1207-
if (col <= InvalidAttrNumber) /* shouldn't happen */
1206+
/* bit numbers are offset by FirstLowInvalidHeapAttributeNumber */
1207+
AttrNumber attno = col + FirstLowInvalidHeapAttributeNumber;
1208+
1209+
if (attno <= InvalidAttrNumber) /* shouldn't happen */
12081210
elog(ERROR, "system-column update is not supported");
1209-
targetAttrs = lappend_int(targetAttrs, col);
1211+
targetAttrs = lappend_int(targetAttrs, attno);
12101212
}
12111213
}
12121214

‎contrib/sepgsql/dml.c

Lines changed: 7 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -93,10 +93,7 @@ fixup_whole_row_references(Oid relOid, Bitmapset *columns)
9393
static Bitmapset *
9494
fixup_inherited_columns(Oid parentId, Oid childId, Bitmapset *columns)
9595
{
96-
AttrNumber attno;
97-
Bitmapset *tmpset;
9896
Bitmapset *result = NULL;
99-
char *attname;
10097
int index;
10198

10299
/*
@@ -105,10 +102,12 @@ fixup_inherited_columns(Oid parentId, Oid childId, Bitmapset *columns)
105102
if (parentId == childId)
106103
return columns;
107104

108-
tmpset = bms_copy(columns);
109-
while ((index = bms_first_member(tmpset)) > 0)
105+
index = -1;
106+
while ((index = bms_next_member(columns, index)) >= 0)
110107
{
111-
attno = index + FirstLowInvalidHeapAttributeNumber;
108+
/* bit numbers are offset by FirstLowInvalidHeapAttributeNumber */
109+
AttrNumber attno = index + FirstLowInvalidHeapAttributeNumber;
110+
char *attname;
112111

113112
/*
114113
* whole-row-reference shall be fixed-up later
@@ -128,12 +127,11 @@ fixup_inherited_columns(Oid parentId, Oid childId, Bitmapset *columns)
128127
elog(ERROR, "cache lookup failed for attribute %s of relation %u",
129128
attname, childId);
130129

131-
index = attno - FirstLowInvalidHeapAttributeNumber;
132-
result = bms_add_member(result, index);
130+
result = bms_add_member(result,
131+
attno - FirstLowInvalidHeapAttributeNumber);
133132

134133
pfree(attname);
135134
}
136-
bms_free(tmpset);
137135

138136
return result;
139137
}

‎src/backend/executor/execMain.c

Lines changed: 14 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -547,7 +547,6 @@ ExecCheckRTEPerms(RangeTblEntry *rte)
547547
AclMode remainingPerms;
548548
Oid relOid;
549549
Oid userid;
550-
Bitmapset *tmpset;
551550
int col;
552551

553552
/*
@@ -614,12 +613,13 @@ ExecCheckRTEPerms(RangeTblEntry *rte)
614613
return false;
615614
}
616615

617-
tmpset = bms_copy(rte->selectedCols);
618-
while ((col = bms_first_member(tmpset)) >= 0)
616+
col = -1;
617+
while ((col = bms_next_member(rte->selectedCols, col)) >= 0)
619618
{
620-
/* remove the column number offset */
621-
col += FirstLowInvalidHeapAttributeNumber;
622-
if (col == InvalidAttrNumber)
619+
/* bit #s are offset by FirstLowInvalidHeapAttributeNumber */
620+
AttrNumber attno = col + FirstLowInvalidHeapAttributeNumber;
621+
622+
if (attno == InvalidAttrNumber)
623623
{
624624
/* Whole-row reference, must have priv on all cols */
625625
if (pg_attribute_aclcheck_all(relOid, userid, ACL_SELECT,
@@ -628,12 +628,11 @@ ExecCheckRTEPerms(RangeTblEntry *rte)
628628
}
629629
else
630630
{
631-
if (pg_attribute_aclcheck(relOid, col, userid,
631+
if (pg_attribute_aclcheck(relOid, attno, userid,
632632
ACL_SELECT) != ACLCHECK_OK)
633633
return false;
634634
}
635635
}
636-
bms_free(tmpset);
637636
}
638637

639638
/*
@@ -656,24 +655,24 @@ ExecCheckRTEPerms(RangeTblEntry *rte)
656655
return false;
657656
}
658657

659-
tmpset = bms_copy(rte->modifiedCols);
660-
while ((col = bms_first_member(tmpset)) >= 0)
658+
col = -1;
659+
while ((col = bms_next_member(rte->modifiedCols, col)) >= 0)
661660
{
662-
/* remove the column number offset */
663-
col += FirstLowInvalidHeapAttributeNumber;
664-
if (col == InvalidAttrNumber)
661+
/* bit #s are offset by FirstLowInvalidHeapAttributeNumber */
662+
AttrNumber attno = col + FirstLowInvalidHeapAttributeNumber;
663+
664+
if (attno == InvalidAttrNumber)
665665
{
666666
/* whole-row reference can't happen here */
667667
elog(ERROR, "whole-row update is not implemented");
668668
}
669669
else
670670
{
671-
if (pg_attribute_aclcheck(relOid, col, userid,
671+
if (pg_attribute_aclcheck(relOid, attno, userid,
672672
remainingPerms) != ACLCHECK_OK)
673673
return false;
674674
}
675675
}
676-
bms_free(tmpset);
677676
}
678677
}
679678
return true;

‎src/backend/nodes/bitmapset.c

Lines changed: 63 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -793,19 +793,19 @@ bms_join(Bitmapset *a, Bitmapset *b)
793793
return result;
794794
}
795795

796-
/*----------
796+
/*
797797
* bms_first_member - find and remove first member of a set
798798
*
799799
* Returns -1 if set is empty. NB: set is destructively modified!
800800
*
801801
* This is intended as support for iterating through the members of a set.
802802
* The typical pattern is
803803
*
804-
* tmpset = bms_copy(inputset);
805-
* while ((x = bms_first_member(tmpset)) >= 0)
804+
* while ((x = bms_first_member(inputset)) >= 0)
806805
* process member x;
807-
* bms_free(tmpset);
808-
*----------
806+
*
807+
* CAUTION: this destroys the content of "inputset". If the set must
808+
* not be modified, use bms_next_member instead.
809809
*/
810810
int
811811
bms_first_member(Bitmapset *a)
@@ -840,6 +840,64 @@ bms_first_member(Bitmapset *a)
840840
return -1;
841841
}
842842

843+
/*
844+
* bms_next_member - find next member of a set
845+
*
846+
* Returns smallest member greater than "prevbit", or -2 if there is none.
847+
* "prevbit" must NOT be less than -1, or the behavior is unpredictable.
848+
*
849+
* This is intended as support for iterating through the members of a set.
850+
* The typical pattern is
851+
*
852+
* x = -1;
853+
* while ((x = bms_next_member(inputset, x)) >= 0)
854+
* process member x;
855+
*
856+
* Notice that when there are no more members, we return -2, not -1 as you
857+
* might expect. The rationale for that is to allow distinguishing the
858+
* loop-not-started state (x == -1) from the loop-completed state (x == -2).
859+
* It makes no difference in simple loop usage, but complex iteration logic
860+
* might need such an ability.
861+
*/
862+
int
863+
bms_next_member(const Bitmapset *a, int prevbit)
864+
{
865+
int nwords;
866+
int wordnum;
867+
bitmapword mask;
868+
869+
if (a == NULL)
870+
return -2;
871+
nwords = a->nwords;
872+
prevbit++;
873+
mask = (~(bitmapword) 0) << BITNUM(prevbit);
874+
for (wordnum = WORDNUM(prevbit); wordnum < nwords; wordnum++)
875+
{
876+
bitmapword w = a->words[wordnum];
877+
878+
/* ignore bits before prevbit */
879+
w &= mask;
880+
881+
if (w != 0)
882+
{
883+
int result;
884+
885+
result = wordnum * BITS_PER_BITMAPWORD;
886+
while ((w & 255) == 0)
887+
{
888+
w >>= 8;
889+
result += 8;
890+
}
891+
result += rightmost_one_pos[w & 255];
892+
return result;
893+
}
894+
895+
/* in subsequent words, consider all bits */
896+
mask = (~(bitmapword) 0);
897+
}
898+
return -2;
899+
}
900+
843901
/*
844902
* bms_hash_value - compute a hash key for a Bitmapset
845903
*

‎src/backend/nodes/outfuncs.c

Lines changed: 2 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -184,15 +184,13 @@ _outList(StringInfo str, const List *node)
184184
static void
185185
_outBitmapset(StringInfo str, const Bitmapset *bms)
186186
{
187-
Bitmapset *tmpset;
188187
int x;
189188

190189
appendStringInfoChar(str, '(');
191190
appendStringInfoChar(str, 'b');
192-
tmpset = bms_copy(bms);
193-
while ((x = bms_first_member(tmpset)) >= 0)
191+
x = -1;
192+
while ((x = bms_next_member(bms, x)) >= 0)
194193
appendStringInfo(str, " %d", x);
195-
bms_free(tmpset);
196194
appendStringInfoChar(str, ')');
197195
}
198196

‎src/backend/optimizer/path/allpaths.c

Lines changed: 2 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -2272,19 +2272,17 @@ remove_unused_subquery_outputs(Query *subquery, RelOptInfo *rel)
22722272
static void
22732273
print_relids(Relids relids)
22742274
{
2275-
Relids tmprelids;
22762275
int x;
22772276
bool first = true;
22782277

2279-
tmprelids = bms_copy(relids);
2280-
while ((x = bms_first_member(tmprelids)) >= 0)
2278+
x = -1;
2279+
while ((x = bms_next_member(relids, x)) >= 0)
22812280
{
22822281
if (!first)
22832282
printf(" ");
22842283
printf("%d", x);
22852284
first = false;
22862285
}
2287-
bms_free(tmprelids);
22882286
}
22892287

22902288
static void

‎src/backend/optimizer/path/indxpath.c

Lines changed: 2 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1875,9 +1875,8 @@ get_loop_count(PlannerInfo *root, Relids outer_relids)
18751875
{
18761876
int relid;
18771877

1878-
/* Need a working copy since bms_first_member is destructive */
1879-
outer_relids = bms_copy(outer_relids);
1880-
while ((relid = bms_first_member(outer_relids)) >= 0)
1878+
relid = -1;
1879+
while ((relid = bms_next_member(outer_relids, relid)) >= 0)
18811880
{
18821881
RelOptInfo *outer_rel;
18831882

@@ -1900,7 +1899,6 @@ get_loop_count(PlannerInfo *root, Relids outer_relids)
19001899
if (result == 1.0 || result > outer_rel->rows)
19011900
result = outer_rel->rows;
19021901
}
1903-
bms_free(outer_relids);
19041902
}
19051903
return result;
19061904
}

‎src/backend/optimizer/util/joininfo.c

Lines changed: 4 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -96,17 +96,15 @@ add_join_clause_to_rels(PlannerInfo *root,
9696
RestrictInfo *restrictinfo,
9797
Relids join_relids)
9898
{
99-
Relids tmprelids;
10099
int cur_relid;
101100

102-
tmprelids = bms_copy(join_relids);
103-
while ((cur_relid = bms_first_member(tmprelids)) >= 0)
101+
cur_relid = -1;
102+
while ((cur_relid = bms_next_member(join_relids, cur_relid)) >= 0)
104103
{
105104
RelOptInfo *rel = find_base_rel(root, cur_relid);
106105

107106
rel->joininfo = lappend(rel->joininfo, restrictinfo);
108107
}
109-
bms_free(tmprelids);
110108
}
111109

112110
/*
@@ -125,11 +123,10 @@ remove_join_clause_from_rels(PlannerInfo *root,
125123
RestrictInfo *restrictinfo,
126124
Relids join_relids)
127125
{
128-
Relids tmprelids;
129126
int cur_relid;
130127

131-
tmprelids = bms_copy(join_relids);
132-
while ((cur_relid = bms_first_member(tmprelids)) >= 0)
128+
cur_relid = -1;
129+
while ((cur_relid = bms_next_member(join_relids, cur_relid)) >= 0)
133130
{
134131
RelOptInfo *rel = find_base_rel(root, cur_relid);
135132

@@ -140,5 +137,4 @@ remove_join_clause_from_rels(PlannerInfo *root,
140137
Assert(list_member_ptr(rel->joininfo, restrictinfo));
141138
rel->joininfo = list_delete_ptr(rel->joininfo, restrictinfo);
142139
}
143-
bms_free(tmprelids);
144140
}

‎src/backend/optimizer/util/var.c

Lines changed: 2 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -773,11 +773,10 @@ static Relids
773773
alias_relid_set(PlannerInfo *root, Relids relids)
774774
{
775775
Relids result = NULL;
776-
Relids tmprelids;
777776
int rtindex;
778777

779-
tmprelids = bms_copy(relids);
780-
while ((rtindex = bms_first_member(tmprelids)) >= 0)
778+
rtindex = -1;
779+
while ((rtindex = bms_next_member(relids, rtindex)) >= 0)
781780
{
782781
RangeTblEntry *rte = rt_fetch(rtindex, root->parse->rtable);
783782

@@ -786,6 +785,5 @@ alias_relid_set(PlannerInfo *root, Relids relids)
786785
else
787786
result = bms_add_member(result, rtindex);
788787
}
789-
bms_free(tmprelids);
790788
return result;
791789
}

‎src/backend/rewrite/rewriteHandler.c

Lines changed: 3 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -2456,11 +2456,10 @@ static Bitmapset *
24562456
adjust_view_column_set(Bitmapset *cols, List *targetlist)
24572457
{
24582458
Bitmapset *result = NULL;
2459-
Bitmapset *tmpcols;
2460-
AttrNumber col;
2459+
int col;
24612460

2462-
tmpcols = bms_copy(cols);
2463-
while ((col = bms_first_member(tmpcols)) >= 0)
2461+
col = -1;
2462+
while ((col = bms_next_member(cols, col)) >= 0)
24642463
{
24652464
/* bit numbers are offset by FirstLowInvalidHeapAttributeNumber */
24662465
AttrNumber attno = col + FirstLowInvalidHeapAttributeNumber;
@@ -2510,7 +2509,6 @@ adjust_view_column_set(Bitmapset *cols, List *targetlist)
25102509
attno);
25112510
}
25122511
}
2513-
bms_free(tmpcols);
25142512

25152513
return result;
25162514
}

‎src/backend/rewrite/rewriteManip.c

Lines changed: 2 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -454,13 +454,11 @@ static Relids
454454
offset_relid_set(Relids relids, int offset)
455455
{
456456
Relids result = NULL;
457-
Relids tmprelids;
458457
int rtindex;
459458

460-
tmprelids = bms_copy(relids);
461-
while ((rtindex = bms_first_member(tmprelids)) >= 0)
459+
rtindex = -1;
460+
while ((rtindex = bms_next_member(relids, rtindex)) >= 0)
462461
result = bms_add_member(result, rtindex + offset);
463-
bms_free(tmprelids);
464462
return result;
465463
}
466464

‎src/include/nodes/bitmapset.h

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -89,6 +89,7 @@ extern Bitmapset *bms_join(Bitmapset *a, Bitmapset *b);
8989

9090
/* support for iterating through the integer elements of a set: */
9191
extern int bms_first_member(Bitmapset *a);
92+
extern int bms_next_member(const Bitmapset *a, int prevbit);
9293

9394
/* support for hashtables using Bitmapsets as keys: */
9495
extern uint32 bms_hash_value(const Bitmapset *a);

0 commit comments

Comments
 (0)