From f4e031c662a6b600b786c4849968a099c58fcce7 Mon Sep 17 00:00:00 2001 From: Tom Lane Date: Fri, 28 Nov 2014 13:37:25 -0500 Subject: [PATCH] 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 --- contrib/postgres_fdw/postgres_fdw.c | 14 +++--- contrib/sepgsql/dml.c | 16 +++---- src/backend/executor/execMain.c | 29 ++++++------ src/backend/nodes/bitmapset.c | 68 +++++++++++++++++++++++++-- src/backend/nodes/outfuncs.c | 6 +-- src/backend/optimizer/path/allpaths.c | 6 +-- src/backend/optimizer/path/indxpath.c | 6 +-- src/backend/optimizer/util/joininfo.c | 12 ++--- src/backend/optimizer/util/var.c | 6 +-- src/backend/rewrite/rewriteHandler.c | 8 ++-- src/backend/rewrite/rewriteManip.c | 6 +-- src/include/nodes/bitmapset.h | 1 + src/pl/plpgsql/src/pl_exec.c | 12 ++--- 13 files changed, 114 insertions(+), 76 deletions(-) diff --git a/contrib/postgres_fdw/postgres_fdw.c b/contrib/postgres_fdw/postgres_fdw.c index 76bda73935..c3039a6480 100644 --- a/contrib/postgres_fdw/postgres_fdw.c +++ b/contrib/postgres_fdw/postgres_fdw.c @@ -1198,15 +1198,17 @@ postgresPlanForeignModify(PlannerInfo *root, } else if (operation == CMD_UPDATE) { - Bitmapset *tmpset = bms_copy(rte->modifiedCols); - AttrNumber col; + int col; - while ((col = bms_first_member(tmpset)) >= 0) + col = -1; + while ((col = bms_next_member(rte->modifiedCols, col)) >= 0) { - col += FirstLowInvalidHeapAttributeNumber; - if (col <= InvalidAttrNumber) /* shouldn't happen */ + /* bit numbers are offset by FirstLowInvalidHeapAttributeNumber */ + AttrNumber attno = col + FirstLowInvalidHeapAttributeNumber; + + if (attno <= InvalidAttrNumber) /* shouldn't happen */ elog(ERROR, "system-column update is not supported"); - targetAttrs = lappend_int(targetAttrs, col); + targetAttrs = lappend_int(targetAttrs, attno); } } diff --git a/contrib/sepgsql/dml.c b/contrib/sepgsql/dml.c index bb82c0d6d2..9e9fa04746 100644 --- a/contrib/sepgsql/dml.c +++ b/contrib/sepgsql/dml.c @@ -93,10 +93,7 @@ fixup_whole_row_references(Oid relOid, Bitmapset *columns) static Bitmapset * fixup_inherited_columns(Oid parentId, Oid childId, Bitmapset *columns) { - AttrNumber attno; - Bitmapset *tmpset; Bitmapset *result = NULL; - char *attname; int index; /* @@ -105,10 +102,12 @@ fixup_inherited_columns(Oid parentId, Oid childId, Bitmapset *columns) if (parentId == childId) return columns; - tmpset = bms_copy(columns); - while ((index = bms_first_member(tmpset)) > 0) + index = -1; + while ((index = bms_next_member(columns, index)) >= 0) { - attno = index + FirstLowInvalidHeapAttributeNumber; + /* bit numbers are offset by FirstLowInvalidHeapAttributeNumber */ + AttrNumber attno = index + FirstLowInvalidHeapAttributeNumber; + char *attname; /* * whole-row-reference shall be fixed-up later @@ -128,12 +127,11 @@ fixup_inherited_columns(Oid parentId, Oid childId, Bitmapset *columns) elog(ERROR, "cache lookup failed for attribute %s of relation %u", attname, childId); - index = attno - FirstLowInvalidHeapAttributeNumber; - result = bms_add_member(result, index); + result = bms_add_member(result, + attno - FirstLowInvalidHeapAttributeNumber); pfree(attname); } - bms_free(tmpset); return result; } diff --git a/src/backend/executor/execMain.c b/src/backend/executor/execMain.c index c499486f01..8c799d3c21 100644 --- a/src/backend/executor/execMain.c +++ b/src/backend/executor/execMain.c @@ -547,7 +547,6 @@ ExecCheckRTEPerms(RangeTblEntry *rte) AclMode remainingPerms; Oid relOid; Oid userid; - Bitmapset *tmpset; int col; /* @@ -614,12 +613,13 @@ ExecCheckRTEPerms(RangeTblEntry *rte) return false; } - tmpset = bms_copy(rte->selectedCols); - while ((col = bms_first_member(tmpset)) >= 0) + col = -1; + while ((col = bms_next_member(rte->selectedCols, col)) >= 0) { - /* remove the column number offset */ - col += FirstLowInvalidHeapAttributeNumber; - if (col == InvalidAttrNumber) + /* bit #s are offset by FirstLowInvalidHeapAttributeNumber */ + AttrNumber attno = col + FirstLowInvalidHeapAttributeNumber; + + if (attno == InvalidAttrNumber) { /* Whole-row reference, must have priv on all cols */ if (pg_attribute_aclcheck_all(relOid, userid, ACL_SELECT, @@ -628,12 +628,11 @@ ExecCheckRTEPerms(RangeTblEntry *rte) } else { - if (pg_attribute_aclcheck(relOid, col, userid, + if (pg_attribute_aclcheck(relOid, attno, userid, ACL_SELECT) != ACLCHECK_OK) return false; } } - bms_free(tmpset); } /* @@ -656,24 +655,24 @@ ExecCheckRTEPerms(RangeTblEntry *rte) return false; } - tmpset = bms_copy(rte->modifiedCols); - while ((col = bms_first_member(tmpset)) >= 0) + col = -1; + while ((col = bms_next_member(rte->modifiedCols, col)) >= 0) { - /* remove the column number offset */ - col += FirstLowInvalidHeapAttributeNumber; - if (col == InvalidAttrNumber) + /* bit #s are offset by FirstLowInvalidHeapAttributeNumber */ + AttrNumber attno = col + FirstLowInvalidHeapAttributeNumber; + + if (attno == InvalidAttrNumber) { /* whole-row reference can't happen here */ elog(ERROR, "whole-row update is not implemented"); } else { - if (pg_attribute_aclcheck(relOid, col, userid, + if (pg_attribute_aclcheck(relOid, attno, userid, remainingPerms) != ACLCHECK_OK) return false; } } - bms_free(tmpset); } } return true; diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c index c927b7891f..26a0f872b3 100644 --- a/src/backend/nodes/bitmapset.c +++ b/src/backend/nodes/bitmapset.c @@ -793,7 +793,7 @@ bms_join(Bitmapset *a, Bitmapset *b) return result; } -/*---------- +/* * bms_first_member - find and remove first member of a set * * Returns -1 if set is empty. NB: set is destructively modified! @@ -801,11 +801,11 @@ bms_join(Bitmapset *a, Bitmapset *b) * This is intended as support for iterating through the members of a set. * The typical pattern is * - * tmpset = bms_copy(inputset); - * while ((x = bms_first_member(tmpset)) >= 0) + * while ((x = bms_first_member(inputset)) >= 0) * process member x; - * bms_free(tmpset); - *---------- + * + * CAUTION: this destroys the content of "inputset". If the set must + * not be modified, use bms_next_member instead. */ int bms_first_member(Bitmapset *a) @@ -840,6 +840,64 @@ bms_first_member(Bitmapset *a) return -1; } +/* + * bms_next_member - find next member of a set + * + * Returns smallest member greater than "prevbit", or -2 if there is none. + * "prevbit" must NOT be less than -1, or the behavior is unpredictable. + * + * This is intended as support for iterating through the members of a set. + * The typical pattern is + * + * x = -1; + * while ((x = bms_next_member(inputset, x)) >= 0) + * process member x; + * + * Notice that when there are no more members, we return -2, not -1 as you + * might expect. The rationale for that is to allow distinguishing the + * loop-not-started state (x == -1) from the loop-completed state (x == -2). + * It makes no difference in simple loop usage, but complex iteration logic + * might need such an ability. + */ +int +bms_next_member(const Bitmapset *a, int prevbit) +{ + int nwords; + int wordnum; + bitmapword mask; + + if (a == NULL) + return -2; + nwords = a->nwords; + prevbit++; + mask = (~(bitmapword) 0) << BITNUM(prevbit); + for (wordnum = WORDNUM(prevbit); wordnum < nwords; wordnum++) + { + bitmapword w = a->words[wordnum]; + + /* ignore bits before prevbit */ + w &= mask; + + if (w != 0) + { + int result; + + result = wordnum * BITS_PER_BITMAPWORD; + while ((w & 255) == 0) + { + w >>= 8; + result += 8; + } + result += rightmost_one_pos[w & 255]; + return result; + } + + /* in subsequent words, consider all bits */ + mask = (~(bitmapword) 0); + } + return -2; +} + /* * bms_hash_value - compute a hash key for a Bitmapset * diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c index ca9bd4f7c7..edbd09f942 100644 --- a/src/backend/nodes/outfuncs.c +++ b/src/backend/nodes/outfuncs.c @@ -184,15 +184,13 @@ _outList(StringInfo str, const List *node) static void _outBitmapset(StringInfo str, const Bitmapset *bms) { - Bitmapset *tmpset; int x; appendStringInfoChar(str, '('); appendStringInfoChar(str, 'b'); - tmpset = bms_copy(bms); - while ((x = bms_first_member(tmpset)) >= 0) + x = -1; + while ((x = bms_next_member(bms, x)) >= 0) appendStringInfo(str, " %d", x); - bms_free(tmpset); appendStringInfoChar(str, ')'); } diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c index 25f30676f0..449fdc3474 100644 --- a/src/backend/optimizer/path/allpaths.c +++ b/src/backend/optimizer/path/allpaths.c @@ -2272,19 +2272,17 @@ remove_unused_subquery_outputs(Query *subquery, RelOptInfo *rel) static void print_relids(Relids relids) { - Relids tmprelids; int x; bool first = true; - tmprelids = bms_copy(relids); - while ((x = bms_first_member(tmprelids)) >= 0) + x = -1; + while ((x = bms_next_member(relids, x)) >= 0) { if (!first) printf(" "); printf("%d", x); first = false; } - bms_free(tmprelids); } static void diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c index 1ee3b93b1e..7aab644e45 100644 --- a/src/backend/optimizer/path/indxpath.c +++ b/src/backend/optimizer/path/indxpath.c @@ -1875,9 +1875,8 @@ get_loop_count(PlannerInfo *root, Relids outer_relids) { int relid; - /* Need a working copy since bms_first_member is destructive */ - outer_relids = bms_copy(outer_relids); - while ((relid = bms_first_member(outer_relids)) >= 0) + relid = -1; + while ((relid = bms_next_member(outer_relids, relid)) >= 0) { RelOptInfo *outer_rel; @@ -1900,7 +1899,6 @@ get_loop_count(PlannerInfo *root, Relids outer_relids) if (result == 1.0 || result > outer_rel->rows) result = outer_rel->rows; } - bms_free(outer_relids); } return result; } diff --git a/src/backend/optimizer/util/joininfo.c b/src/backend/optimizer/util/joininfo.c index 0418946d71..40af38d7ad 100644 --- a/src/backend/optimizer/util/joininfo.c +++ b/src/backend/optimizer/util/joininfo.c @@ -96,17 +96,15 @@ add_join_clause_to_rels(PlannerInfo *root, RestrictInfo *restrictinfo, Relids join_relids) { - Relids tmprelids; int cur_relid; - tmprelids = bms_copy(join_relids); - while ((cur_relid = bms_first_member(tmprelids)) >= 0) + cur_relid = -1; + while ((cur_relid = bms_next_member(join_relids, cur_relid)) >= 0) { RelOptInfo *rel = find_base_rel(root, cur_relid); rel->joininfo = lappend(rel->joininfo, restrictinfo); } - bms_free(tmprelids); } /* @@ -125,11 +123,10 @@ remove_join_clause_from_rels(PlannerInfo *root, RestrictInfo *restrictinfo, Relids join_relids) { - Relids tmprelids; int cur_relid; - tmprelids = bms_copy(join_relids); - while ((cur_relid = bms_first_member(tmprelids)) >= 0) + cur_relid = -1; + while ((cur_relid = bms_next_member(join_relids, cur_relid)) >= 0) { RelOptInfo *rel = find_base_rel(root, cur_relid); @@ -140,5 +137,4 @@ remove_join_clause_from_rels(PlannerInfo *root, Assert(list_member_ptr(rel->joininfo, restrictinfo)); rel->joininfo = list_delete_ptr(rel->joininfo, restrictinfo); } - bms_free(tmprelids); } diff --git a/src/backend/optimizer/util/var.c b/src/backend/optimizer/util/var.c index d4f46b8d46..a64a8d7d5f 100644 --- a/src/backend/optimizer/util/var.c +++ b/src/backend/optimizer/util/var.c @@ -773,11 +773,10 @@ static Relids alias_relid_set(PlannerInfo *root, Relids relids) { Relids result = NULL; - Relids tmprelids; int rtindex; - tmprelids = bms_copy(relids); - while ((rtindex = bms_first_member(tmprelids)) >= 0) + rtindex = -1; + while ((rtindex = bms_next_member(relids, rtindex)) >= 0) { RangeTblEntry *rte = rt_fetch(rtindex, root->parse->rtable); @@ -786,6 +785,5 @@ alias_relid_set(PlannerInfo *root, Relids relids) else result = bms_add_member(result, rtindex); } - bms_free(tmprelids); return result; } diff --git a/src/backend/rewrite/rewriteHandler.c b/src/backend/rewrite/rewriteHandler.c index ad983c7158..2ed64279f0 100644 --- a/src/backend/rewrite/rewriteHandler.c +++ b/src/backend/rewrite/rewriteHandler.c @@ -2456,11 +2456,10 @@ static Bitmapset * adjust_view_column_set(Bitmapset *cols, List *targetlist) { Bitmapset *result = NULL; - Bitmapset *tmpcols; - AttrNumber col; + int col; - tmpcols = bms_copy(cols); - while ((col = bms_first_member(tmpcols)) >= 0) + col = -1; + while ((col = bms_next_member(cols, col)) >= 0) { /* bit numbers are offset by FirstLowInvalidHeapAttributeNumber */ AttrNumber attno = col + FirstLowInvalidHeapAttributeNumber; @@ -2510,7 +2509,6 @@ adjust_view_column_set(Bitmapset *cols, List *targetlist) attno); } } - bms_free(tmpcols); return result; } diff --git a/src/backend/rewrite/rewriteManip.c b/src/backend/rewrite/rewriteManip.c index fb203146b1..c9e4b68341 100644 --- a/src/backend/rewrite/rewriteManip.c +++ b/src/backend/rewrite/rewriteManip.c @@ -454,13 +454,11 @@ static Relids offset_relid_set(Relids relids, int offset) { Relids result = NULL; - Relids tmprelids; int rtindex; - tmprelids = bms_copy(relids); - while ((rtindex = bms_first_member(tmprelids)) >= 0) + rtindex = -1; + while ((rtindex = bms_next_member(relids, rtindex)) >= 0) result = bms_add_member(result, rtindex + offset); - bms_free(tmprelids); return result; } diff --git a/src/include/nodes/bitmapset.h b/src/include/nodes/bitmapset.h index f77060844f..a78ff4886d 100644 --- a/src/include/nodes/bitmapset.h +++ b/src/include/nodes/bitmapset.h @@ -89,6 +89,7 @@ extern Bitmapset *bms_join(Bitmapset *a, Bitmapset *b); /* support for iterating through the integer elements of a set: */ extern int bms_first_member(Bitmapset *a); +extern int bms_next_member(const Bitmapset *a, int prevbit); /* support for hashtables using Bitmapsets as keys: */ extern uint32 bms_hash_value(const Bitmapset *a); diff --git a/src/pl/plpgsql/src/pl_exec.c b/src/pl/plpgsql/src/pl_exec.c index 11cb47b522..d1feef78b7 100644 --- a/src/pl/plpgsql/src/pl_exec.c +++ b/src/pl/plpgsql/src/pl_exec.c @@ -5263,7 +5263,6 @@ setup_param_list(PLpgSQL_execstate *estate, PLpgSQL_expr *expr) */ if (!bms_is_empty(expr->paramnos)) { - Bitmapset *tmpset; int dno; paramLI = (ParamListInfo) @@ -5276,8 +5275,8 @@ setup_param_list(PLpgSQL_execstate *estate, PLpgSQL_expr *expr) paramLI->numParams = estate->ndatums; /* Instantiate values for "safe" parameters of the expression */ - tmpset = bms_copy(expr->paramnos); - while ((dno = bms_first_member(tmpset)) >= 0) + dno = -1; + while ((dno = bms_next_member(expr->paramnos, dno)) >= 0) { PLpgSQL_datum *datum = estate->datums[dno]; @@ -5292,7 +5291,6 @@ setup_param_list(PLpgSQL_execstate *estate, PLpgSQL_expr *expr) prm->ptype = var->datatype->typoid; } } - bms_free(tmpset); /* * Set up link to active expr where the hook functions can find it. @@ -6528,15 +6526,14 @@ format_expr_params(PLpgSQL_execstate *estate, int paramno; int dno; StringInfoData paramstr; - Bitmapset *tmpset; if (!expr->paramnos) return NULL; initStringInfo(¶mstr); - tmpset = bms_copy(expr->paramnos); paramno = 0; - while ((dno = bms_first_member(tmpset)) >= 0) + dno = -1; + while ((dno = bms_next_member(expr->paramnos, dno)) >= 0) { Datum paramdatum; Oid paramtypeid; @@ -6572,7 +6569,6 @@ format_expr_params(PLpgSQL_execstate *estate, paramno++; } - bms_free(tmpset); return paramstr.data; } -- 2.40.0