/*-------------------------------------------------------------------- * Symbols referenced in this file: * - bms_copy * - bms_equal * - bms_free * - bms_next_member * - bms_num_members *-------------------------------------------------------------------- */ /*------------------------------------------------------------------------- * * 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 the * empty set by a NULL pointer. * * * Copyright (c) 2003-2023, 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)) /* Select appropriate bit-twiddling functions for bitmap word size */ #if BITS_PER_BITMAPWORD == 32 #define bmw_leftmost_one_pos(w) pg_leftmost_one_pos32(w) #define bmw_rightmost_one_pos(w) pg_rightmost_one_pos32(w) #define bmw_popcount(w) pg_popcount32(w) #elif BITS_PER_BITMAPWORD == 64 #define bmw_leftmost_one_pos(w) pg_leftmost_one_pos64(w) #define bmw_rightmost_one_pos(w) pg_rightmost_one_pos64(w) #define bmw_popcount(w) pg_popcount64(w) #else #error "invalid BITS_PER_BITMAPWORD" #endif static bool bms_is_empty_internal(const Bitmapset *a); /* * bms_copy - make a palloc'd copy of a bitmapset */ Bitmapset * bms_copy(const Bitmapset *a) { Bitmapset *result; size_t size; 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? * * This is logical not physical equality; in particular, a NULL pointer will * be reported as equal to a palloc'd value containing no members. */ bool bms_equal(const Bitmapset *a, const Bitmapset *b) { const Bitmapset *shorter; const Bitmapset *longer; int shortlen; int longlen; int i; /* Handle cases where either input is NULL */ if (a == NULL) { if (b == NULL) return true; return false; } else if (b == NULL) return false; /* Identify shorter and longer input */ if (a->nwords <= b->nwords) { shorter = a; longer = b; } else { shorter = b; longer = a; } /* And process */ shortlen = shorter->nwords; for (i = 0; i < shortlen; i++) { if (shorter->words[i] != longer->words[i]) return false; } longlen = longer->nwords; for (; i < longlen; i++) { if (longer->words[i] != 0) return false; } 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.) */ /* * bms_make_singleton - build a bitmapset containing a single member */ /* * bms_free - free a bitmapset * * Same as pfree except for allowing NULL input */ void bms_free(Bitmapset *a) { if (a) pfree(a); } /* * These operations all make a freshly palloc'd result, * leaving their inputs untouched */ /* * bms_union - set union */ /* * bms_intersect - set intersection */ /* * bms_difference - set difference (ie, A without members of B) */ /* * bms_is_subset - is A a subset of B? */ /* * bms_subset_compare - compare A and B for equality/subset relationships * * This is more efficient than testing bms_is_subset in both directions. */ /* * bms_is_member - is X a member of A? */ /* * bms_member_index * determine 0-based index of member x in the bitmap * * Returns (-1) when x is not a member. */ /* * bms_overlap - do sets overlap (ie, have a nonempty intersection)? */ /* * bms_overlap_list - does a set overlap an integer list? */ /* * bms_nonempty_difference - do sets have a nonempty difference? * * i.e., are any members set in 'a' that are not also set in 'b'. */ /* * bms_singleton_member - return the sole integer member of set * * Raises error if |a| is not 1. */ /* * 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. */ /* * bms_num_members - count members of set */ int bms_num_members(const Bitmapset *a) { int result = 0; int nwords; int wordnum; if (a == NULL) return 0; nwords = a->nwords; for (wordnum = 0; wordnum < nwords; wordnum++) { bitmapword w = a->words[wordnum]; /* No need to count the bits in a zero word */ if (w != 0) result += bmw_popcount(w); } return result; } /* * bms_membership - does a set have zero, one, or multiple members? * * This is faster than making an exact count with bms_num_members(). */ /* * bms_is_empty_internal - is a set empty? * * This is now used only locally, to detect cases where a function has * computed an empty set that we must now get rid of. Hence, we can * assume the input isn't NULL. */ /* * These operations all "recycle" their non-const inputs, ie, either * return the modified input or pfree it if it can't hold the result. * * These should generally be used in the style * * foo = bms_add_member(foo, x); */ /* * bms_add_member - add a specified member to set * * Input set is modified or recycled! */ /* * bms_del_member - remove a specified member from set * * No error if x is not currently a member of set * * Input set is modified in-place! */ /* * bms_add_members - like bms_union, but left input is recycled */ /* * 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. */ /* * bms_int_members - like bms_intersect, but left input is recycled */ /* * bms_del_members - like bms_difference, but left input is recycled */ /* * bms_join - like bms_union, but *both* inputs are recycled */ /* * 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; 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 at 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. */ /* * bms_hash_value - compute a hash key for a Bitmapset * * Note: we must ensure that any two bitmapsets that are bms_equal() will * hash to the same value; in practice this means that trailing all-zero * words must not affect the result. Hence we strip those before applying * hash_any(). */ /* * bitmap_hash - hash function for keys that are (pointers to) Bitmapsets * * Note: don't forget to specify bitmap_match as the match function! */ /* * bitmap_match - match function to use with bitmap_hash */