greenplumn bitmapset 源码

greenplumn bitmapset 代码

文件路径：/src/include/nodes/bitmapset.h

/*-------------------------------------------------------------------------
 *
 * bitmapset.h
 *	  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, a NULL pointer is always
 * accepted by all operations to represent the empty set.  (But beware
 * that this is not the only representation of the empty set.  Use
 * bms_is_empty() in preference to testing for NULL.)
 *
 *
 * Copyright (c) 2003-2019, PostgreSQL Global Development Group
 *
 * src/include/nodes/bitmapset.h
 *
 *-------------------------------------------------------------------------
 */
#ifndef BITMAPSET_H
#define BITMAPSET_H

/*
 * Forward decl to save including pg_list.h
 */
struct List;

/*
 * Data representation
 *
 * Larger bitmap word sizes generally give better performance, so long as
 * they're not wider than the processor can handle efficiently.  We use
 * 64-bit words if pointers are that large, else 32-bit words.
 */
/*
 * GPDB_12_MERGE_FIXME Disable 64-bit word size for bitmap sets.
 * Appenoptimized tables use bitmapset interface to encode tuple visibility.
 * These bitmap sets make their way to disk, inside aovisimap tuples.
 * Increasing word size will affect the ability to interpret existing
 * appendoptimized visibility data written with 32-bit word size.  Therefore,
 * we must continue to use 32-bit bitmap words or rewrite all existing
 * appendoptimized tables during upgrade (not viable).  The goal of this fixme
 * is to explore if the performance benefit of larger bitmapwords can still be
 * availed by distinguishing on-disk bitmap usage from strictly in-memory
 * bitmap usage.  E.g. define a new type bitmapword32 and use it in
 * appendoptimized code.  On a related note, tbm_bitmapword is Greenplum
 * specific 64-bit wide type used for TID bitmaps.  Can we start using
 * bitmapword for TID bitmaps, just like upastream, and eliminate
 * tbm_bitmapword?
 */
#if false && SIZEOF_VOID_P >= 8

#define BITS_PER_BITMAPWORD 64
typedef uint64 bitmapword;		/* must be an unsigned type */
typedef int64 signedbitmapword; /* must be the matching signed type */

#else

#define BITS_PER_BITMAPWORD 32
typedef uint32 bitmapword;		/* must be an unsigned type */
typedef int32 signedbitmapword; /* must be the matching signed type */

#endif

typedef struct Bitmapset
{
	int			nwords;			/* number of words in array */
	bitmapword	words[FLEXIBLE_ARRAY_MEMBER];	/* really [nwords] */
} Bitmapset;


/* result of bms_subset_compare */
typedef enum
{
	BMS_EQUAL,					/* sets are equal */
	BMS_SUBSET1,				/* first set is a subset of the second */
	BMS_SUBSET2,				/* second set is a subset of the first */
	BMS_DIFFERENT				/* neither set is a subset of the other */
} BMS_Comparison;

/* result of bms_membership */
typedef enum
{
	BMS_EMPTY_SET,				/* 0 members */
	BMS_SINGLETON,				/* 1 member */
	BMS_MULTIPLE				/* >1 member */
} BMS_Membership;


/*
 * function prototypes in nodes/bitmapset.c
 */

extern Bitmapset *bms_copy(const Bitmapset *a);
extern bool bms_equal(const Bitmapset *a, const Bitmapset *b);
extern int	bms_compare(const Bitmapset *a, const Bitmapset *b);
extern Bitmapset *bms_make_singleton(int x);
extern void bms_free(Bitmapset *a);

extern Bitmapset *bms_union(const Bitmapset *a, const Bitmapset *b);
extern Bitmapset *bms_intersect(const Bitmapset *a, const Bitmapset *b);
extern Bitmapset *bms_difference(const Bitmapset *a, const Bitmapset *b);
extern bool bms_is_subset(const Bitmapset *a, const Bitmapset *b);
extern BMS_Comparison bms_subset_compare(const Bitmapset *a, const Bitmapset *b);
extern bool bms_is_member(int x, const Bitmapset *a);
extern int	bms_member_index(Bitmapset *a, int x);
extern bool bms_overlap(const Bitmapset *a, const Bitmapset *b);
extern bool bms_overlap_list(const Bitmapset *a, const struct List *b);
extern bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b);
extern int	bms_singleton_member(const Bitmapset *a);
extern bool bms_get_singleton_member(const Bitmapset *a, int *member);
extern int	bms_num_members(const Bitmapset *a);

/* optimized tests when we don't need to know exact membership count: */
extern BMS_Membership bms_membership(const Bitmapset *a);
extern bool bms_is_empty(const Bitmapset *a);

/* these routines recycle (modify or free) their non-const inputs: */

extern Bitmapset *bms_add_member(Bitmapset *a, int x);
extern Bitmapset *bms_del_member(Bitmapset *a, int x);
extern Bitmapset *bms_add_members(Bitmapset *a, const Bitmapset *b);
extern Bitmapset *bms_add_range(Bitmapset *a, int lower, int upper);
extern Bitmapset *bms_int_members(Bitmapset *a, const Bitmapset *b);
extern Bitmapset *bms_del_members(Bitmapset *a, const Bitmapset *b);
extern Bitmapset *bms_join(Bitmapset *a, Bitmapset *b);

/* support for iterating through the integer elements of a set: */
extern int	bms_first_member(Bitmapset *a);
extern int	bms_next_member(const Bitmapset *a, int prevbit);
extern int	bms_prev_member(const Bitmapset *a, int prevbit);

/* support for hashtables using Bitmapsets as keys: */
extern uint32 bms_hash_value(const Bitmapset *a);
extern uint32 bitmap_hash(const void *key, Size keysize);
extern int	bitmap_match(const void *key1, const void *key2, Size keysize);

/* 
 * returns true iff the bitmap is sufficently large that
 * it stores the bit for member x
 */
extern bool bms_covers_member(const Bitmapset *a, int x);

/* 
 * Extend the bitmap a to have at least wc number of words.
 * If wc is smaller than the bitmap a, the bitmap a
 * is returned
 */
extern Bitmapset *bms_resize(Bitmapset *a, int wc);

#endif							/* BITMAPSET_H */

相关信息

greenplumn 源码目录

相关文章

greenplumn altertablenodes 源码

greenplumn execnodes 源码

greenplumn extensible 源码

greenplumn lockoptions 源码

greenplumn makefuncs 源码

greenplumn memnodes 源码

greenplumn nodeFuncs 源码

greenplumn nodes 源码

greenplumn params 源码

greenplumn parsenodes 源码