/
balmaster
/
postgres
Обзор
Документация
Войти
/
balmaster
/
postgres
Код
Запросы
0
Задачи
Вики
Пакеты
0
Релизы
0
Аналитика
Безопасность
master
src/backend/nodes/bitmapset.c
1 439 строк
30 KB
David Rowley
Fix unlikely overflow bug in bms_next_member()
13 апр 2026, 02:39
13 апр 2026, 02:39
e3e26d0
Код
Авторство
О чём код?
/*------------------------------------------------------------------------- * * bitmapset.c * PostgreSQL generic bitmap set package * * A bitmap set can represent any set of nonnegative integers, although * it is mainly intended for sets where the maximum value is not large, * say at most a few hundred. By convention, we always represent a set with * the minimum possible number of words, i.e, there are never any trailing * zero words. Enforcing this requires that an empty set is represented as * NULL. Because an empty Bitmapset is represented as NULL, a non-NULL * Bitmapset always has at least 1 Bitmapword. We can exploit this fact to * speed up various loops over the Bitmapset's words array by using "do while" * loops instead of "for" loops. This means the code does not waste time * checking the loop condition before the first iteration. For Bitmapsets * containing only a single word (likely the majority of them) this halves the * number of loop condition checks. * * Callers must ensure that the set returned by functions in this file which * adjust the members of an existing set is assigned to all pointers pointing * to that existing set. No guarantees are made that we'll ever modify the * existing set in-place and return it. * * To help find bugs caused by callers failing to record the return value of * the function which manipulates an existing set, we support building with * REALLOCATE_BITMAPSETS. This results in the set being reallocated each time * the set is altered and the existing being pfreed. This is useful as if any * references still exist to the old set, we're more likely to notice as * any users of the old set will be accessing pfree'd memory. This option is * only intended to be used for debugging. * * Copyright (c) 2003-2026, PostgreSQL Global Development Group * * IDENTIFICATION * src/backend/nodes/bitmapset.c * *------------------------------------------------------------------------- */ #include "postgres.h" #include "common/hashfn.h" #include "nodes/bitmapset.h" #include "nodes/pg_list.h" #include "port/pg_bitutils.h" #define WORDNUM(x) ((x) / BITS_PER_BITMAPWORD) #define BITNUM(x) ((x) % BITS_PER_BITMAPWORD) #define BITMAPSET_SIZE(nwords) \ (offsetof(Bitmapset, words) + (nwords) * sizeof(bitmapword)) /*---------- * This is a well-known cute trick for isolating the rightmost one-bit * in a word. It assumes two's complement arithmetic. Consider any * nonzero value, and focus attention on the rightmost one. The value is * then something like * xxxxxx10000 * where x's are unspecified bits. The two's complement negative is formed * by inverting all the bits and adding one. Inversion gives * yyyyyy01111 * where each y is the inverse of the corresponding x. Incrementing gives * yyyyyy10000 * and then ANDing with the original value gives * 00000010000 * This works for all cases except original value = zero, where of course * we get zero. *---------- */ #define RIGHTMOST_ONE(x) ((signedbitmapword) (x) & -((signedbitmapword) (x))) #define HAS_MULTIPLE_ONES(x) ((bitmapword) RIGHTMOST_ONE(x) != (x)) #ifdef USE_ASSERT_CHECKING /* * bms_is_valid_set - for cassert builds to check for valid sets */ static bool bms_is_valid_set(const Bitmapset *a) { /* NULL is the correct representation of an empty set */ if (a == NULL) return true; /* check the node tag is set correctly. pfree'd pointer, maybe? */ if (!IsA(a, Bitmapset)) return false; /* trailing zero words are not allowed */ if (a->words[a->nwords - 1] == 0) return false; return true; } #endif #ifdef REALLOCATE_BITMAPSETS /* * bms_copy_and_free * Only required in REALLOCATE_BITMAPSETS builds. Provide a simple way * to return a freshly allocated set and pfree the original. * * Note: callers which accept multiple sets must be careful when calling this * function to clone one parameter as other parameters may point to the same * set. A good option is to call this just before returning the resulting * set. */ static Bitmapset * bms_copy_and_free(Bitmapset *a) { Bitmapset *c = bms_copy(a); bms_free(a); return c; } #endif /* * bms_copy - make a palloc'd copy of a bitmapset */ Bitmapset * bms_copy(const Bitmapset *a) { Bitmapset *result; size_t size; Assert(bms_is_valid_set(a)); if (a == NULL) return NULL; size = BITMAPSET_SIZE(a->nwords); result = (Bitmapset *) palloc(size); memcpy(result, a, size); return result; } /* * bms_equal - are two bitmapsets equal? or both NULL? */ bool bms_equal(const Bitmapset *a, const Bitmapset *b) { int i; Assert(bms_is_valid_set(a)); Assert(bms_is_valid_set(b)); /* Handle cases where either input is NULL */ if (a == NULL) { if (b == NULL) return true; return false; } else if (b == NULL) return false; /* can't be equal if the word counts don't match */ if (a->nwords != b->nwords) return false; /* check each word matches */ i = 0; do { if (a->words[i] != b->words[i]) return false; } while (++i < a->nwords); return true; } /* * bms_compare - qsort-style comparator for bitmapsets * * This guarantees to report values as equal iff bms_equal would say they are * equal. Otherwise, the highest-numbered bit that is set in one value but * not the other determines the result. (This rule means that, for example, * {6} is greater than {5}, which seems plausible.) */ int bms_compare(const Bitmapset *a, const Bitmapset *b) { int i; Assert(bms_is_valid_set(a)); Assert(bms_is_valid_set(b)); /* Handle cases where either input is NULL */ if (a == NULL) return (b == NULL) ? 0 : -1; else if (b == NULL) return +1; /* the set with the most words must be greater */ if (a->nwords != b->nwords) return (a->nwords > b->nwords) ? +1 : -1; i = a->nwords - 1; do { bitmapword aw = a->words[i]; bitmapword bw = b->words[i]; if (aw != bw) return (aw > bw) ? +1 : -1; } while (--i >= 0); return 0; } /* * bms_make_singleton - build a bitmapset containing a single member */ Bitmapset * bms_make_singleton(int x) { Bitmapset *result; int wordnum, bitnum; if (x < 0) elog(ERROR, "negative bitmapset member not allowed"); wordnum = WORDNUM(x); bitnum = BITNUM(x); result = (Bitmapset *) palloc0(BITMAPSET_SIZE(wordnum + 1)); result->type = T_Bitmapset; result->nwords = wordnum + 1; result->words[wordnum] = ((bitmapword) 1 << bitnum); return result; } /* * bms_free - free a bitmapset * * Same as pfree except for allowing NULL input */ void bms_free(Bitmapset *a) { if (a) pfree(a); } /* * bms_union - create and return a new set containing all members from both * input sets. Both inputs are left unmodified. */ Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b) { Bitmapset *result; const Bitmapset *other; int otherlen; int i; Assert(bms_is_valid_set(a)); Assert(bms_is_valid_set(b)); /* Handle cases where either input is NULL */ if (a == NULL) return bms_copy(b); if (b == NULL) return bms_copy(a); /* Identify shorter and longer input; copy the longer one */ if (a->nwords <= b->nwords) { result = bms_copy(b); other = a; } else { result = bms_copy(a); other = b; } /* And union the shorter input into the result */ otherlen = other->nwords; i = 0; do { result->words[i] |= other->words[i]; } while (++i < otherlen); return result; } /* * bms_intersect - create and return a new set containing members which both * input sets have in common. Both inputs are left unmodified. */ Bitmapset * bms_intersect(const Bitmapset *a, const Bitmapset *b) { Bitmapset *result; const Bitmapset *other; int lastnonzero; int resultlen; int i; Assert(bms_is_valid_set(a)); Assert(bms_is_valid_set(b)); /* Handle cases where either input is NULL */ if (a == NULL || b == NULL) return NULL; /* Identify shorter and longer input; copy the shorter one */ if (a->nwords <= b->nwords) { result = bms_copy(a); other = b; } else { result = bms_copy(b); other = a; } /* And intersect the longer input with the result */ resultlen = result->nwords; lastnonzero = -1; i = 0; do { result->words[i] &= other->words[i]; if (result->words[i] != 0) lastnonzero = i; } while (++i < resultlen); /* If we computed an empty result, we must return NULL */ if (lastnonzero == -1) { pfree(result); return NULL; } /* get rid of trailing zero words */ result->nwords = lastnonzero + 1; return result; } /* * bms_difference - create and return a new set containing all the members of * 'a' without the members of 'b'. */ Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b) { Bitmapset *result; int i; Assert(bms_is_valid_set(a)); Assert(bms_is_valid_set(b)); /* Handle cases where either input is NULL */ if (a == NULL) return NULL; if (b == NULL) return bms_copy(a); /* * In Postgres' usage, an empty result is a very common case, so it's * worth optimizing for that by testing bms_nonempty_difference(). This * saves us a palloc/pfree cycle compared to checking after-the-fact. */ if (!bms_nonempty_difference(a, b)) return NULL; /* Copy the left input */ result = bms_copy(a); /* And remove b's bits from result */ if (result->nwords > b->nwords) { /* * We'll never need to remove trailing zero words when 'a' has more * words than 'b' as the additional words must be non-zero. */ i = 0; do { result->words[i] &= ~b->words[i]; } while (++i < b->nwords); } else { int lastnonzero = -1; /* we may need to remove trailing zero words from the result. */ i = 0; do { result->words[i] &= ~b->words[i]; /* remember the last non-zero word */ if (result->words[i] != 0) lastnonzero = i; } while (++i < result->nwords); /* trim off trailing zero words */ result->nwords = lastnonzero + 1; } Assert(result->nwords != 0); /* Need not check for empty result, since we handled that case above */ return result; } /* * bms_is_subset - is A a subset of B? */ bool bms_is_subset(const Bitmapset *a, const Bitmapset *b) { int i; Assert(bms_is_valid_set(a)); Assert(bms_is_valid_set(b)); /* Handle cases where either input is NULL */ if (a == NULL) return true; /* empty set is a subset of anything */ if (b == NULL) return false; /* 'a' can't be a subset of 'b' if it contains more words */ if (a->nwords > b->nwords) return false; /* Check all 'a' members are set in 'b' */ i = 0; do { if ((a->words[i] & ~b->words[i]) != 0) return false; } while (++i < a->nwords); return true; } /* * bms_subset_compare - compare A and B for equality/subset relationships * * This is more efficient than testing bms_is_subset in both directions. */ BMS_Comparison bms_subset_compare(const Bitmapset *a, const Bitmapset *b) { BMS_Comparison result; int shortlen; int i; Assert(bms_is_valid_set(a)); Assert(bms_is_valid_set(b)); /* Handle cases where either input is NULL */ if (a == NULL) { if (b == NULL) return BMS_EQUAL; return BMS_SUBSET1; } if (b == NULL) return BMS_SUBSET2; /* Check common words */ result = BMS_EQUAL; /* status so far */ shortlen = Min(a->nwords, b->nwords); i = 0; do { bitmapword aword = a->words[i]; bitmapword bword = b->words[i]; if ((aword & ~bword) != 0) { /* a is not a subset of b */ if (result == BMS_SUBSET1) return BMS_DIFFERENT; result = BMS_SUBSET2; } if ((bword & ~aword) != 0) { /* b is not a subset of a */ if (result == BMS_SUBSET2) return BMS_DIFFERENT; result = BMS_SUBSET1; } } while (++i < shortlen); /* Check extra words */ if (a->nwords > b->nwords) { /* if a has more words then a is not a subset of b */ if (result == BMS_SUBSET1) return BMS_DIFFERENT; return BMS_SUBSET2; } else if (a->nwords < b->nwords) { /* if b has more words then b is not a subset of a */ if (result == BMS_SUBSET2) return BMS_DIFFERENT; return BMS_SUBSET1; } return result; } /* * bms_is_member - is X a member of A? */ bool bms_is_member(int x, const Bitmapset *a) { int wordnum, bitnum; Assert(bms_is_valid_set(a)); /* XXX better to just return false for x<0 ? */ if (x < 0) elog(ERROR, "negative bitmapset member not allowed"); if (a == NULL) return false; wordnum = WORDNUM(x); bitnum = BITNUM(x); if (wordnum >= a->nwords) return false; if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0) return true; return false; } /* * bms_member_index * determine 0-based index of member x in the bitmap * * Returns (-1) when x is not a member. */ int bms_member_index(Bitmapset *a, int x) { int bitnum; int wordnum; int result = 0; bitmapword mask; Assert(bms_is_valid_set(a)); /* return -1 if not a member of the bitmap */ if (!bms_is_member(x, a)) return -1; wordnum = WORDNUM(x); bitnum = BITNUM(x); /* count bits in preceding words */ result += pg_popcount((const char *) a->words, wordnum * sizeof(bitmapword)); /* * Now add bits of the last word, but only those before the item. We can * do that by applying a mask and then using popcount again. To get * 0-based index, we want to count only preceding bits, not the item * itself, so we subtract 1. */ mask = ((bitmapword) 1 << bitnum) - 1; result += bmw_popcount(a->words[wordnum] & mask); return result; } /* * bms_overlap - do sets overlap (ie, have a nonempty intersection)? */ bool bms_overlap(const Bitmapset *a, const Bitmapset *b) { int shortlen; int i; Assert(bms_is_valid_set(a)); Assert(bms_is_valid_set(b)); /* Handle cases where either input is NULL */ if (a == NULL || b == NULL) return false; /* Check words in common */ shortlen = Min(a->nwords, b->nwords); i = 0; do { if ((a->words[i] & b->words[i]) != 0) return true; } while (++i < shortlen); return false; } /* * bms_overlap_list - does a set overlap an integer list? */ bool bms_overlap_list(const Bitmapset *a, const List *b) { ListCell *lc; int wordnum, bitnum; Assert(bms_is_valid_set(a)); if (a == NULL || b == NIL) return false; foreach(lc, b) { int x = lfirst_int(lc); if (x < 0) elog(ERROR, "negative bitmapset member not allowed"); wordnum = WORDNUM(x); bitnum = BITNUM(x); if (wordnum < a->nwords) if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0) return true; } return false; } /* * bms_nonempty_difference - do sets have a nonempty difference? * * i.e., are any members set in 'a' that are not also set in 'b'. */ bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b) { int i; Assert(bms_is_valid_set(a)); Assert(bms_is_valid_set(b)); /* Handle cases where either input is NULL */ if (a == NULL) return false; if (b == NULL) return true; /* if 'a' has more words then it must contain additional members */ if (a->nwords > b->nwords) return true; /* Check all 'a' members are set in 'b' */ i = 0; do { if ((a->words[i] & ~b->words[i]) != 0) return true; } while (++i < a->nwords); return false; } /* * bms_singleton_member - return the sole integer member of set * * Raises error if |a| is not 1. */ int bms_singleton_member(const Bitmapset *a) { int result = -1; int nwords; int wordnum; Assert(bms_is_valid_set(a)); if (a == NULL) elog(ERROR, "bitmapset is empty"); nwords = a->nwords; wordnum = 0; do { bitmapword w = a->words[wordnum]; if (w != 0) { if (result >= 0 || HAS_MULTIPLE_ONES(w)) elog(ERROR, "bitmapset has multiple members"); result = wordnum * BITS_PER_BITMAPWORD; result += bmw_rightmost_one_pos(w); } } while (++wordnum < nwords); /* we don't expect non-NULL sets to be empty */ Assert(result >= 0); return result; } /* * bms_get_singleton_member * * Test whether the given set is a singleton. * If so, set *member to the value of its sole member, and return true. * If not, return false, without changing *member. * * This is more convenient and faster than calling bms_membership() and then * bms_singleton_member(), if we don't care about distinguishing empty sets * from multiple-member sets. */ bool bms_get_singleton_member(const Bitmapset *a, int *member) { int result = -1; int nwords; int wordnum; Assert(bms_is_valid_set(a)); if (a == NULL) return false; nwords = a->nwords; wordnum = 0; do { bitmapword w = a->words[wordnum]; if (w != 0) { if (result >= 0 || HAS_MULTIPLE_ONES(w)) return false; result = wordnum * BITS_PER_BITMAPWORD; result += bmw_rightmost_one_pos(w); } } while (++wordnum < nwords); /* we don't expect non-NULL sets to be empty */ Assert(result >= 0); *member = result; return true; } /* * bms_num_members - count members of set */ int bms_num_members(const Bitmapset *a) { Assert(bms_is_valid_set(a)); if (a == NULL) return 0; /* fast-path for common case */ if (a->nwords == 1) return bmw_popcount(a->words[0]); return pg_popcount((const char *) a->words, a->nwords * sizeof(bitmapword)); } /* * bms_membership - does a set have zero, one, or multiple members? * * This is faster than making an exact count with bms_num_members(). */ BMS_Membership bms_membership(const Bitmapset *a) { BMS_Membership result = BMS_EMPTY_SET; int nwords; int wordnum; Assert(bms_is_valid_set(a)); if (a == NULL) return BMS_EMPTY_SET; nwords = a->nwords; wordnum = 0; do { bitmapword w = a->words[wordnum]; if (w != 0) { if (result != BMS_EMPTY_SET || HAS_MULTIPLE_ONES(w)) return BMS_MULTIPLE; result = BMS_SINGLETON; } } while (++wordnum < nwords); return result; } /* * bms_add_member - add a specified member to set * * 'a' is recycled when possible. */ Bitmapset * bms_add_member(Bitmapset *a, int x) { int wordnum, bitnum; Assert(bms_is_valid_set(a)); if (x < 0) elog(ERROR, "negative bitmapset member not allowed"); if (a == NULL) return bms_make_singleton(x); wordnum = WORDNUM(x); bitnum = BITNUM(x); /* enlarge the set if necessary */ if (wordnum >= a->nwords) { int oldnwords = a->nwords; int i; a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(wordnum + 1)); a->nwords = wordnum + 1; /* zero out the enlarged portion */ i = oldnwords; do { a->words[i] = 0; } while (++i < a->nwords); } a->words[wordnum] |= ((bitmapword) 1 << bitnum); #ifdef REALLOCATE_BITMAPSETS /* * There's no guarantee that the repalloc returned a new pointer, so copy * and free unconditionally here. */ a = bms_copy_and_free(a); #endif return a; } /* * bms_del_member - remove a specified member from set * * No error if x is not currently a member of set * * 'a' is recycled when possible. */ Bitmapset * bms_del_member(Bitmapset *a, int x) { int wordnum, bitnum; Assert(bms_is_valid_set(a)); if (x < 0) elog(ERROR, "negative bitmapset member not allowed"); if (a == NULL) return NULL; wordnum = WORDNUM(x); bitnum = BITNUM(x); #ifdef REALLOCATE_BITMAPSETS a = bms_copy_and_free(a); #endif /* member can't exist. Return 'a' unmodified */ if (unlikely(wordnum >= a->nwords)) return a; a->words[wordnum] &= ~((bitmapword) 1 << bitnum); /* when last word becomes empty, trim off all trailing empty words */ if (a->words[wordnum] == 0 && wordnum == a->nwords - 1) { /* find the last non-empty word and make that the new final word */ for (int i = wordnum - 1; i >= 0; i--) { if (a->words[i] != 0) { a->nwords = i + 1; return a; } } /* the set is now empty */ pfree(a); return NULL; } return a; } /* * bms_add_members - like bms_union, but left input is recycled when possible */ Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b) { Bitmapset *result; const Bitmapset *other; int otherlen; int i; Assert(bms_is_valid_set(a)); Assert(bms_is_valid_set(b)); /* Handle cases where either input is NULL */ if (a == NULL) return bms_copy(b); if (b == NULL) { #ifdef REALLOCATE_BITMAPSETS a = bms_copy_and_free(a); #endif return a; } /* Identify shorter and longer input; copy the longer one if needed */ if (a->nwords < b->nwords) { result = bms_copy(b); other = a; } else { result = a; other = b; } /* And union the shorter input into the result */ otherlen = other->nwords; i = 0; do { result->words[i] |= other->words[i]; } while (++i < otherlen); if (result != a) pfree(a); #ifdef REALLOCATE_BITMAPSETS else result = bms_copy_and_free(result); #endif return result; } /* * bms_replace_members * Remove all existing members from 'a' and repopulate the set with members * from 'b', recycling 'a', when possible. */ Bitmapset * bms_replace_members(Bitmapset *a, const Bitmapset *b) { int i; Assert(bms_is_valid_set(a)); Assert(bms_is_valid_set(b)); if (a == NULL) return bms_copy(b); if (b == NULL) { pfree(a); return NULL; } if (a->nwords < b->nwords) a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(b->nwords)); i = 0; do { a->words[i] = b->words[i]; } while (++i < b->nwords); a->nwords = b->nwords; #ifdef REALLOCATE_BITMAPSETS /* * There's no guarantee that the repalloc returned a new pointer, so copy * and free unconditionally here. */ a = bms_copy_and_free(a); #endif return a; } /* * bms_add_range * Add members in the range of 'lower' to 'upper' to the set. * * Note this could also be done by calling bms_add_member in a loop, however, * using this function will be faster when the range is large as we work at * the bitmapword level rather than at bit level. */ Bitmapset * bms_add_range(Bitmapset *a, int lower, int upper) { int lwordnum, lbitnum, uwordnum, ushiftbits, wordnum; Assert(bms_is_valid_set(a)); /* do nothing if nothing is called for, without further checking */ if (upper < lower) { #ifdef REALLOCATE_BITMAPSETS a = bms_copy_and_free(a); #endif return a; } if (lower < 0) elog(ERROR, "negative bitmapset member not allowed"); uwordnum = WORDNUM(upper); if (a == NULL) { a = (Bitmapset *) palloc0(BITMAPSET_SIZE(uwordnum + 1)); a->type = T_Bitmapset; a->nwords = uwordnum + 1; } else if (uwordnum >= a->nwords) { int oldnwords = a->nwords; int i; /* ensure we have enough words to store the upper bit */ a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(uwordnum + 1)); a->nwords = uwordnum + 1; /* zero out the enlarged portion */ i = oldnwords; do { a->words[i] = 0; } while (++i < a->nwords); } wordnum = lwordnum = WORDNUM(lower); lbitnum = BITNUM(lower); ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(upper) + 1); /* * Special case when lwordnum is the same as uwordnum we must perform the * upper and lower masking on the word. */ if (lwordnum == uwordnum) { a->words[lwordnum] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1) & (~(bitmapword) 0) >> ushiftbits; } else { /* turn on lbitnum and all bits left of it */ a->words[wordnum++] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1); /* turn on all bits for any intermediate words */ while (wordnum < uwordnum) a->words[wordnum++] = ~(bitmapword) 0; /* turn on upper's bit and all bits right of it. */ a->words[uwordnum] |= (~(bitmapword) 0) >> ushiftbits; } #ifdef REALLOCATE_BITMAPSETS /* * There's no guarantee that the repalloc returned a new pointer, so copy * and free unconditionally here. */ a = bms_copy_and_free(a); #endif return a; } /* * bms_int_members - like bms_intersect, but left input is recycled when * possible */ Bitmapset * bms_int_members(Bitmapset *a, const Bitmapset *b) { int lastnonzero; int shortlen; int i; Assert(bms_is_valid_set(a)); Assert(bms_is_valid_set(b)); /* Handle cases where either input is NULL */ if (a == NULL) return NULL; if (b == NULL) { pfree(a); return NULL; } /* Intersect b into a; we need never copy */ shortlen = Min(a->nwords, b->nwords); lastnonzero = -1; i = 0; do { a->words[i] &= b->words[i]; if (a->words[i] != 0) lastnonzero = i; } while (++i < shortlen); /* If we computed an empty result, we must return NULL */ if (lastnonzero == -1) { pfree(a); return NULL; } /* get rid of trailing zero words */ a->nwords = lastnonzero + 1; #ifdef REALLOCATE_BITMAPSETS a = bms_copy_and_free(a); #endif return a; } /* * bms_del_members - delete members in 'a' that are set in 'b'. 'a' is * recycled when possible. */ Bitmapset * bms_del_members(Bitmapset *a, const Bitmapset *b) { int i; Assert(bms_is_valid_set(a)); Assert(bms_is_valid_set(b)); /* Handle cases where either input is NULL */ if (a == NULL) return NULL; if (b == NULL) { #ifdef REALLOCATE_BITMAPSETS a = bms_copy_and_free(a); #endif return a; } /* Remove b's bits from a; we need never copy */ if (a->nwords > b->nwords) { /* * We'll never need to remove trailing zero words when 'a' has more * words than 'b'. */ i = 0; do { a->words[i] &= ~b->words[i]; } while (++i < b->nwords); } else { int lastnonzero = -1; /* we may need to remove trailing zero words from the result. */ i = 0; do { a->words[i] &= ~b->words[i]; /* remember the last non-zero word */ if (a->words[i] != 0) lastnonzero = i; } while (++i < a->nwords); /* check if 'a' has become empty */ if (lastnonzero == -1) { pfree(a); return NULL; } /* trim off any trailing zero words */ a->nwords = lastnonzero + 1; } #ifdef REALLOCATE_BITMAPSETS a = bms_copy_and_free(a); #endif return a; } /* * bms_join - like bms_union, but *either* input *may* be recycled */ Bitmapset * bms_join(Bitmapset *a, Bitmapset *b) { Bitmapset *result; Bitmapset *other; int otherlen; int i; Assert(bms_is_valid_set(a)); Assert(bms_is_valid_set(b)); /* Handle cases where either input is NULL */ if (a == NULL) { #ifdef REALLOCATE_BITMAPSETS b = bms_copy_and_free(b); #endif return b; } if (b == NULL) { #ifdef REALLOCATE_BITMAPSETS a = bms_copy_and_free(a); #endif return a; } /* Identify shorter and longer input; use longer one as result */ if (a->nwords < b->nwords) { result = b; other = a; } else { result = a; other = b; } /* And union the shorter input into the result */ otherlen = other->nwords; i = 0; do { result->words[i] |= other->words[i]; } while (++i < otherlen); if (other != result) /* pure paranoia */ pfree(other); #ifdef REALLOCATE_BITMAPSETS result = bms_copy_and_free(result); #endif return result; } /* * 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) { unsigned int currbit = prevbit; int nwords; bitmapword mask; Assert(bms_is_valid_set(a)); if (a == NULL) return -2; nwords = a->nwords; /* use an unsigned int to avoid the risk that int overflows */ currbit++; mask = (~(bitmapword) 0) << BITNUM(currbit); for (int wordnum = WORDNUM(currbit); wordnum < nwords; wordnum++) { bitmapword w = a->words[wordnum]; /* ignore bits before currbit */ w &= mask; if (w != 0) { int result; result = wordnum * BITS_PER_BITMAPWORD; result += bmw_rightmost_one_pos(w); return result; } /* in subsequent words, consider all bits */ mask = (~(bitmapword) 0); } return -2; } /* * bms_prev_member - find prev member of a set * * Returns largest member less than "prevbit", or -2 if there is none. * "prevbit" must NOT be more than one above the highest possible bit that can * be set in the Bitmapset at its current size. * * To ease finding the highest set bit for the initial loop, the special * prevbit value of -1 can be passed to have the function find the highest * valued member in the set. * * This is intended as support for iterating through the members of a set in * reverse. The typical pattern is * * x = -1; * while ((x = bms_prev_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_prev_member(const Bitmapset *a, int prevbit) { unsigned int currbit; int ushiftbits; bitmapword mask; Assert(bms_is_valid_set(a)); /* * If set is NULL or if there are no more bits to the right then we've * nothing to do. */ if (a == NULL || prevbit == 0) return -2; /* Validate callers didn't give us something out of range */ Assert(prevbit < 0 || prevbit <= (unsigned int) (a->nwords * BITS_PER_BITMAPWORD)); /* * Transform -1 (or any negative number) to the highest possible bit we * could have set. We do this in unsigned math to avoid the risk of * overflowing a signed int. */ if (prevbit < 0) currbit = (unsigned int) a->nwords * BITS_PER_BITMAPWORD - 1; else currbit = prevbit - 1; ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(currbit) + 1); mask = (~(bitmapword) 0) >> ushiftbits; for (int wordnum = WORDNUM(currbit); wordnum >= 0; wordnum--) { bitmapword w = a->words[wordnum]; /* mask out bits left of currbit */ w &= mask; if (w != 0) { int result; result = wordnum * BITS_PER_BITMAPWORD; result += bmw_leftmost_one_pos(w); return result; } /* in subsequent words, consider all bits */ mask = (~(bitmapword) 0); } return -2; } /* * bms_hash_value - compute a hash key for a Bitmapset */ uint32 bms_hash_value(const Bitmapset *a) { Assert(bms_is_valid_set(a)); if (a == NULL) return 0; /* All empty sets hash to 0 */ return DatumGetUInt32(hash_any((const unsigned char *) a->words, a->nwords * sizeof(bitmapword))); } /* * bitmap_hash - hash function for keys that are (pointers to) Bitmapsets * * Note: don't forget to specify bitmap_match as the match function! */ uint32 bitmap_hash(const void *key, Size keysize) { Assert(keysize == sizeof(Bitmapset *)); return bms_hash_value(*((const Bitmapset *const *) key)); } /* * bitmap_match - match function to use with bitmap_hash */ int bitmap_match(const void *key1, const void *key2, Size keysize) { Assert(keysize == sizeof(Bitmapset *)); return !bms_equal(*((const Bitmapset *const *) key1), *((const Bitmapset *const *) key2)); }