Header And Logo

PostgreSQL
| The world's most advanced open source database.

bitmapset.h

Go to the documentation of this file.
00001 /*-------------------------------------------------------------------------
00002  *
00003  * bitmapset.h
00004  *    PostgreSQL generic bitmap set package
00005  *
00006  * A bitmap set can represent any set of nonnegative integers, although
00007  * it is mainly intended for sets where the maximum value is not large,
00008  * say at most a few hundred.  By convention, a NULL pointer is always
00009  * accepted by all operations to represent the empty set.  (But beware
00010  * that this is not the only representation of the empty set.  Use
00011  * bms_is_empty() in preference to testing for NULL.)
00012  *
00013  *
00014  * Copyright (c) 2003-2013, PostgreSQL Global Development Group
00015  *
00016  * src/include/nodes/bitmapset.h
00017  *
00018  *-------------------------------------------------------------------------
00019  */
00020 #ifndef BITMAPSET_H
00021 #define BITMAPSET_H
00022 
00023 /*
00024  * Data representation
00025  */
00026 
00027 /* The unit size can be adjusted by changing these three declarations: */
00028 #define BITS_PER_BITMAPWORD 32
00029 typedef uint32 bitmapword;      /* must be an unsigned type */
00030 typedef int32 signedbitmapword; /* must be the matching signed type */
00031 
00032 typedef struct Bitmapset
00033 {
00034     int         nwords;         /* number of words in array */
00035     bitmapword  words[1];       /* really [nwords] */
00036 } Bitmapset;                    /* VARIABLE LENGTH STRUCT */
00037 
00038 
00039 /* result of bms_subset_compare */
00040 typedef enum
00041 {
00042     BMS_EQUAL,                  /* sets are equal */
00043     BMS_SUBSET1,                /* first set is a subset of the second */
00044     BMS_SUBSET2,                /* second set is a subset of the first */
00045     BMS_DIFFERENT               /* neither set is a subset of the other */
00046 } BMS_Comparison;
00047 
00048 /* result of bms_membership */
00049 typedef enum
00050 {
00051     BMS_EMPTY_SET,              /* 0 members */
00052     BMS_SINGLETON,              /* 1 member */
00053     BMS_MULTIPLE                /* >1 member */
00054 } BMS_Membership;
00055 
00056 
00057 /*
00058  * function prototypes in nodes/bitmapset.c
00059  */
00060 
00061 extern Bitmapset *bms_copy(const Bitmapset *a);
00062 extern bool bms_equal(const Bitmapset *a, const Bitmapset *b);
00063 extern Bitmapset *bms_make_singleton(int x);
00064 extern void bms_free(Bitmapset *a);
00065 
00066 extern Bitmapset *bms_union(const Bitmapset *a, const Bitmapset *b);
00067 extern Bitmapset *bms_intersect(const Bitmapset *a, const Bitmapset *b);
00068 extern Bitmapset *bms_difference(const Bitmapset *a, const Bitmapset *b);
00069 extern bool bms_is_subset(const Bitmapset *a, const Bitmapset *b);
00070 extern BMS_Comparison bms_subset_compare(const Bitmapset *a, const Bitmapset *b);
00071 extern bool bms_is_member(int x, const Bitmapset *a);
00072 extern bool bms_overlap(const Bitmapset *a, const Bitmapset *b);
00073 extern bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b);
00074 extern int  bms_singleton_member(const Bitmapset *a);
00075 extern int  bms_num_members(const Bitmapset *a);
00076 
00077 /* optimized tests when we don't need to know exact membership count: */
00078 extern BMS_Membership bms_membership(const Bitmapset *a);
00079 extern bool bms_is_empty(const Bitmapset *a);
00080 
00081 /* these routines recycle (modify or free) their non-const inputs: */
00082 
00083 extern Bitmapset *bms_add_member(Bitmapset *a, int x);
00084 extern Bitmapset *bms_del_member(Bitmapset *a, int x);
00085 extern Bitmapset *bms_add_members(Bitmapset *a, const Bitmapset *b);
00086 extern Bitmapset *bms_int_members(Bitmapset *a, const Bitmapset *b);
00087 extern Bitmapset *bms_del_members(Bitmapset *a, const Bitmapset *b);
00088 extern Bitmapset *bms_join(Bitmapset *a, Bitmapset *b);
00089 
00090 /* support for iterating through the integer elements of a set: */
00091 extern int  bms_first_member(Bitmapset *a);
00092 
00093 /* support for hashtables using Bitmapsets as keys: */
00094 extern uint32 bms_hash_value(const Bitmapset *a);
00095 
00096 #endif   /* BITMAPSET_H */