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

Commit5c06752

Browse files
committed
Add bms_prev_member function
This works very much like the existing bms_last_member function, only ittraverses through the Bitmapset in the opposite direction from the mostsignificant bit down to the least significant bit. A special prevbit value of-1 may be used to have the function determine the most significant bit. Thisis useful for starting a loop. When there are no members less than prevbit,the function returns -2 to indicate there are no more members.Author: David RowleyDiscussion:https://postgr.es/m/CAKJS1f-K=3d5MDASNYFJpUpc20xcBnAwNC1-AOeunhn0OtkWbQ@mail.gmail.com
1 parentf16241b commit5c06752

File tree

2 files changed

+96
-0
lines changed

2 files changed

+96
-0
lines changed

‎src/backend/nodes/bitmapset.c‎

Lines changed: 95 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -58,6 +58,9 @@
5858
* rightmost_one_pos[x] gives the bit number (0-7) of the rightmost one bit
5959
* in a nonzero byte value x. The entry for x=0 is never used.
6060
*
61+
* leftmost_one_pos[x] gives the bit number (0-7) of the leftmost one bit in a
62+
* nonzero byte value x. The entry for x=0 is never used.
63+
*
6164
* number_of_ones[x] gives the number of one-bits (0-8) in a byte value x.
6265
*
6366
* We could make these tables larger and reduce the number of iterations
@@ -84,6 +87,25 @@ static const uint8 rightmost_one_pos[256] = {
8487
4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
8588
};
8689

90+
staticconstuint8leftmost_one_pos[256]= {
91+
0,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,
92+
4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
93+
5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
94+
5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
95+
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
96+
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
97+
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
98+
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
99+
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
100+
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
101+
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
102+
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
103+
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
104+
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
105+
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
106+
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7
107+
};
108+
87109
staticconstuint8number_of_ones[256]= {
88110
0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
89111
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
@@ -1088,6 +1110,79 @@ bms_next_member(const Bitmapset *a, int prevbit)
10881110
return-2;
10891111
}
10901112

1113+
/*
1114+
* bms_prev_member - find prev member of a set
1115+
*
1116+
* Returns largest member less than "prevbit", or -2 if there is none.
1117+
* "prevbit" must NOT be more than one above the highest possible bit that can
1118+
* be set at the Bitmapset at its current size.
1119+
*
1120+
* To ease finding the highest set bit for the initial loop, the special
1121+
* prevbit value of -1 can be passed to have the function find the highest
1122+
* valued member in the set.
1123+
*
1124+
* This is intended as support for iterating through the members of a set in
1125+
* reverse. The typical pattern is
1126+
*
1127+
*x = -1;
1128+
*while ((x = bms_prev_member(inputset, x)) >= 0)
1129+
*process member x;
1130+
*
1131+
* Notice that when there are no more members, we return -2, not -1 as you
1132+
* might expect. The rationale for that is to allow distinguishing the
1133+
* loop-not-started state (x == -1) from the loop-completed state (x == -2).
1134+
* It makes no difference in simple loop usage, but complex iteration logic
1135+
* might need such an ability.
1136+
*/
1137+
1138+
int
1139+
bms_prev_member(constBitmapset*a,intprevbit)
1140+
{
1141+
intwordnum;
1142+
intushiftbits;
1143+
bitmapwordmask;
1144+
1145+
/*
1146+
* If set is NULL or if there are no more bits to the right then we've
1147+
* nothing to do.
1148+
*/
1149+
if (a==NULL||prevbit==0)
1150+
return-2;
1151+
1152+
/* transform -1 to the highest possible bit we could have set */
1153+
if (prevbit==-1)
1154+
prevbit=a->nwords*BITS_PER_BITMAPWORD-1;
1155+
else
1156+
prevbit--;
1157+
1158+
ushiftbits=BITS_PER_BITMAPWORD- (BITNUM(prevbit)+1);
1159+
mask= (~(bitmapword)0) >>ushiftbits;
1160+
for (wordnum=WORDNUM(prevbit);wordnum >=0;wordnum--)
1161+
{
1162+
bitmapwordw=a->words[wordnum];
1163+
1164+
/* mask out bits left of prevbit */
1165+
w &=mask;
1166+
1167+
if (w!=0)
1168+
{
1169+
intresult;
1170+
intshift=24;
1171+
result=wordnum*BITS_PER_BITMAPWORD;
1172+
1173+
while ((w >>shift)==0)
1174+
shift-=8;
1175+
1176+
result+=shift+leftmost_one_pos[(w >>shift)&255];
1177+
returnresult;
1178+
}
1179+
1180+
/* in subsequent words, consider all bits */
1181+
mask= (~(bitmapword)0);
1182+
}
1183+
return-2;
1184+
}
1185+
10911186
/*
10921187
* bms_hash_value - compute a hash key for a Bitmapset
10931188
*

‎src/include/nodes/bitmapset.h‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -99,6 +99,7 @@ extern Bitmapset *bms_join(Bitmapset *a, Bitmapset *b);
9999
/* support for iterating through the integer elements of a set: */
100100
externintbms_first_member(Bitmapset*a);
101101
externintbms_next_member(constBitmapset*a,intprevbit);
102+
externintbms_prev_member(constBitmapset*a,intprevbit);
102103

103104
/* support for hashtables using Bitmapsets as keys: */
104105
externuint32bms_hash_value(constBitmapset*a);

0 commit comments

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