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-2008, PostgreSQL Global Development Group
  15  *
  16  * $PostgreSQL$
  17  *
  18  *-------------------------------------------------------------------------
  19  */
  20 #ifndef BITMAPSET_H
  21 #define BITMAPSET_H
  22
  23 /*
  24  * Data representation
  25  */
  26
  27 /* The unit size can be adjusted by changing these three declarations: */
  28 #define BITS_PER_BITMAPWORD 32
  29 typedef uint32 bitmapword;              /* must be an unsigned type */
  30 typedef int32 signedbitmapword; /* must be the matching signed type */
  31
  32 typedef struct Bitmapset
  33 {
  34         int                     nwords;                 /* number of words in array */
  35         bitmapword      words[1];               /* really [nwords] */
  36 } Bitmapset;                                    /* VARIABLE LENGTH STRUCT */
  37
  38
  39 /* result of bms_membership */
  40 typedef enum
  41 {
  42         BMS_EMPTY_SET,                          /* 0 members */
  43         BMS_SINGLETON,                          /* 1 member */
  44         BMS_MULTIPLE                            /* >1 member */
  45 } BMS_Membership;
  46
  47
  48 /*
  49  * function prototypes in nodes/bitmapset.c
  50  */
  51
  52 extern Bitmapset *bms_copy(const Bitmapset *a);
  53 extern bool bms_equal(const Bitmapset *a, const Bitmapset *b);
  54 extern Bitmapset *bms_make_singleton(int x);
  55 extern void bms_free(Bitmapset *a);
  56
  57 extern Bitmapset *bms_union(const Bitmapset *a, const Bitmapset *b);
  58 extern Bitmapset *bms_intersect(const Bitmapset *a, const Bitmapset *b);
  59 extern Bitmapset *bms_difference(const Bitmapset *a, const Bitmapset *b);
  60 extern bool bms_is_subset(const Bitmapset *a, const Bitmapset *b);
  61 extern bool bms_is_member(int x, const Bitmapset *a);
  62 extern bool bms_overlap(const Bitmapset *a, const Bitmapset *b);
  63 extern bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b);
  64 extern int      bms_singleton_member(const Bitmapset *a);
  65 extern int      bms_num_members(const Bitmapset *a);
  66
  67 /* optimized tests when we don't need to know exact membership count: */
  68 extern BMS_Membership bms_membership(const Bitmapset *a);
  69 extern bool bms_is_empty(const Bitmapset *a);
  70
  71 /* these routines recycle (modify or free) their non-const inputs: */
  72
  73 extern Bitmapset *bms_add_member(Bitmapset *a, int x);
  74 extern Bitmapset *bms_del_member(Bitmapset *a, int x);
  75 extern Bitmapset *bms_add_members(Bitmapset *a, const Bitmapset *b);
  76 extern Bitmapset *bms_int_members(Bitmapset *a, const Bitmapset *b);
  77 extern Bitmapset *bms_del_members(Bitmapset *a, const Bitmapset *b);
  78 extern Bitmapset *bms_join(Bitmapset *a, Bitmapset *b);
  79
  80 /* support for iterating through the integer elements of a set: */
  81 extern int      bms_first_member(Bitmapset *a);
  82
  83 /* support for hashtables using Bitmapsets as keys: */
  84 extern uint32 bms_hash_value(const Bitmapset *a);
  85
  86 #endif   /* BITMAPSET_H */