granicus.if.org Git - postgresql/blob - src/include/nodes/bitmapset.h

   1 /*-------------------------------------------------------------------------
   2  *
   3  * bitmapset.h
   4  *        PostgreSQL generic bitmap set package
   5  *
   6  * A bitmap set can represent any set of nonnegative integers, although
   7  * it is mainly intended for sets where the maximum value is not large,
   8  * say at most a few hundred.  By convention, a NULL pointer is always
   9  * accepted by all operations to represent the empty set.  (But beware
  10  * that this is not the only representation of the empty set.  Use
  11  * bms_is_empty() in preference to testing for NULL.)
  12  *
  13  *
  14  * Copyright (c) 2003-2019, PostgreSQL Global Development Group
  15  *
  16  * src/include/nodes/bitmapset.h
  17  *
  18  *-------------------------------------------------------------------------
  19  */
  20 #ifndef BITMAPSET_H
  21 #define BITMAPSET_H
  22
  23 /*
  24  * Forward decl to save including pg_list.h
  25  */
  26 struct List;
  27
  28 /*
  29  * Data representation
  30  *
  31  * Larger bitmap word sizes generally give better performance, so long as
  32  * they're not wider than the processor can handle efficiently.  We use
  33  * 64-bit words if pointers are that large, else 32-bit words.
  34  */
  35 #if SIZEOF_VOID_P >= 8
  36
  37 #define BITS_PER_BITMAPWORD 64
  38 typedef uint64 bitmapword;              /* must be an unsigned type */
  39 typedef int64 signedbitmapword; /* must be the matching signed type */
  40
  41 #else
  42
  43 #define BITS_PER_BITMAPWORD 32
  44 typedef uint32 bitmapword;              /* must be an unsigned type */
  45 typedef int32 signedbitmapword; /* must be the matching signed type */
  46
  47 #endif
  48
  49 typedef struct Bitmapset
  50 {
  51         int                     nwords;                 /* number of words in array */
  52         bitmapword      words[FLEXIBLE_ARRAY_MEMBER];   /* really [nwords] */
  53 } Bitmapset;
  54
  55
  56 /* result of bms_subset_compare */
  57 typedef enum
  58 {
  59         BMS_EQUAL,                                      /* sets are equal */
  60         BMS_SUBSET1,                            /* first set is a subset of the second */
  61         BMS_SUBSET2,                            /* second set is a subset of the first */
  62         BMS_DIFFERENT                           /* neither set is a subset of the other */
  63 } BMS_Comparison;
  64
  65 /* result of bms_membership */
  66 typedef enum
  67 {
  68         BMS_EMPTY_SET,                          /* 0 members */
  69         BMS_SINGLETON,                          /* 1 member */
  70         BMS_MULTIPLE                            /* >1 member */
  71 } BMS_Membership;
  72
  73
  74 /*
  75  * function prototypes in nodes/bitmapset.c
  76  */
  77
  78 extern Bitmapset *bms_copy(const Bitmapset *a);
  79 extern bool bms_equal(const Bitmapset *a, const Bitmapset *b);
  80 extern int      bms_compare(const Bitmapset *a, const Bitmapset *b);
  81 extern Bitmapset *bms_make_singleton(int x);
  82 extern void bms_free(Bitmapset *a);
  83
  84 extern Bitmapset *bms_union(const Bitmapset *a, const Bitmapset *b);
  85 extern Bitmapset *bms_intersect(const Bitmapset *a, const Bitmapset *b);
  86 extern Bitmapset *bms_difference(const Bitmapset *a, const Bitmapset *b);
  87 extern bool bms_is_subset(const Bitmapset *a, const Bitmapset *b);
  88 extern BMS_Comparison bms_subset_compare(const Bitmapset *a, const Bitmapset *b);
  89 extern bool bms_is_member(int x, const Bitmapset *a);
  90 extern int      bms_member_index(Bitmapset *a, int x);
  91 extern bool bms_overlap(const Bitmapset *a, const Bitmapset *b);
  92 extern bool bms_overlap_list(const Bitmapset *a, const struct List *b);
  93 extern bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b);
  94 extern int      bms_singleton_member(const Bitmapset *a);
  95 extern bool bms_get_singleton_member(const Bitmapset *a, int *member);
  96 extern int      bms_num_members(const Bitmapset *a);
  97
  98 /* optimized tests when we don't need to know exact membership count: */
  99 extern BMS_Membership bms_membership(const Bitmapset *a);
 100 extern bool bms_is_empty(const Bitmapset *a);
 101
 102 /* these routines recycle (modify or free) their non-const inputs: */
 103
 104 extern Bitmapset *bms_add_member(Bitmapset *a, int x);
 105 extern Bitmapset *bms_del_member(Bitmapset *a, int x);
 106 extern Bitmapset *bms_add_members(Bitmapset *a, const Bitmapset *b);
 107 extern Bitmapset *bms_add_range(Bitmapset *a, int lower, int upper);
 108 extern Bitmapset *bms_int_members(Bitmapset *a, const Bitmapset *b);
 109 extern Bitmapset *bms_del_members(Bitmapset *a, const Bitmapset *b);
 110 extern Bitmapset *bms_join(Bitmapset *a, Bitmapset *b);
 111
 112 /* support for iterating through the integer elements of a set: */
 113 extern int      bms_first_member(Bitmapset *a);
 114 extern int      bms_next_member(const Bitmapset *a, int prevbit);
 115 extern int      bms_prev_member(const Bitmapset *a, int prevbit);
 116
 117 /* support for hashtables using Bitmapsets as keys: */
 118 extern uint32 bms_hash_value(const Bitmapset *a);
 119
 120 #endif                                                  /* BITMAPSET_H */