path: root/src/veil_bitmap.c

/**
 * @file   veil_bitmap.c
 * \code
 *     Author:       Marc Munro
 *     Copyright (c) 2005 - 2011 Marc Munro
 *     License:      BSD
 * 
 * \endcode
 * @brief  
 * Functions for manipulating Bitmaps, BitmapHashes and BitmapArrays
 * 
 */

#include <stdio.h>
#include "postgres.h"
#include "veil_datatypes.h"
#include "veil_funcs.h"


#ifdef USE_64_BIT
/**
 * Array of bit positions for int64, indexed by bitno.
 */
static
uint64 bitmasks[64] = {
	0x00000001, 0x00000002, 0x00000004, 0x00000008, 
	0x00000010, 0x00000020, 0x00000040, 0x00000080, 
	0x00000100, 0x00000200, 0x00000400, 0x00000800, 
	0x00001000, 0x00002000, 0x00004000, 0x00008000,
	0x00010000, 0x00020000, 0x00040000, 0x00080000,
	0x00100000, 0x00200000, 0x00400000, 0x00800000,
	0x01000000, 0x02000000, 0x04000000, 0x08000000,
	0x10000000, 0x20000000, 0x40000000, 0x80000000,
	0x0000000100000000, 0x0000000200000000, 
	    0x0000000400000000, 0x0000000800000000, 
	0x0000001000000000, 0x0000002000000000, 
	    0x0000004000000000, 0x0000008000000000, 
	0x0000010000000000, 0x0000020000000000, 
	    0x0000040000000000, 0x0000080000000000, 
	0x0000100000000000, 0x0000200000000000, 
	    0x0000400000000000, 0x0000800000000000,
	0x0001000000000000, 0x0002000000000000, 
	    0x0004000000000000, 0x0008000000000000,
	0x0010000000000000, 0x0020000000000000, 
	    0x0040000000000000, 0x0080000000000000,
	0x0100000000000000, 0x0200000000000000, 
	    0x0400000000000000, 0x0800000000000000,
	0x1000000000000000, 0x2000000000000000, 
	    0x4000000000000000, 0x8000000000000000};

#else
/**
 * Array of bit positions for int32, indexed by bitno.
 */
static
uint32 bitmasks[] = {0x00000001, 0x00000002, 0x00000004, 0x00000008, 
				  	 0x00000010, 0x00000020, 0x00000040, 0x00000080, 
				  	 0x00000100, 0x00000200, 0x00000400, 0x00000800, 
				  	 0x00001000, 0x00002000, 0x00004000, 0x00008000,
				  	 0x00010000, 0x00020000, 0x00040000, 0x00080000,
				  	 0x00100000, 0x00200000, 0x00400000, 0x00800000,
				  	 0x01000000, 0x02000000, 0x04000000, 0x08000000,
				  	 0x10000000, 0x20000000, 0x40000000, 0x80000000};

#endif

/** 
 * Clear all bits in a ::Bitmap.
 * 
 * @param bitmap The ::Bitmap in which all bits are to be cleared
 */
void
vl_ClearBitmap(Bitmap *bitmap)
{
	int elems = ARRAYELEMS(bitmap->bitzero, bitmap->bitmax);
	int i;
	
	for (i = 0; i < elems; i++) {
		bitmap->bitset[i] = 0;
	}
}

/** 
 * Return a newly initialised (empty) ::Bitmap.  The bitmap may already
 * exist in which case it will be re-used if possible.  The bitmap may
 * be created in either session or shared memory depending on the value
 * of shared.
 * 
 * @param p_bitmap Pointer to an existing bitmap if one exists
 * @param shared Whether to create the bitmap in shared memory
 * @param min The smallest bit to be stored in the bitmap
 * @param max The largest bit to be stored in the bitmap
 */
void
vl_NewBitmap(Bitmap **p_bitmap, bool shared,
			 int32 min, int32 max)
{
	Bitmap *bitmap = *p_bitmap;
	int     elems = ARRAYELEMS(min, max);

	if (bitmap) {
		int cur_elems = ARRAYELEMS(bitmap->bitzero, bitmap->bitmax);
		/* OK, there is an old bitmap in place.  If it is the same size
		 * or larger than we need we will re-use it, otherwise we will
		 * dispose of it and get a new one. */

		if (elems <= cur_elems) {
			vl_ClearBitmap(bitmap);
		}
		else {
			if (shared) {
				vl_free(bitmap);
			}
			else {
				pfree(bitmap);
			}
			bitmap = NULL;
		}
	}
	if (!bitmap) {
		/* We need a new bitmap */
		if (shared) {
			bitmap = vl_shmalloc(sizeof(Bitmap) + (sizeof(bm_int) * elems));
		}
		else {
			bitmap = vl_malloc(sizeof(Bitmap) + (sizeof(bm_int) * elems));
		}
	}

	DBG_SET_CANARY(*bitmap);
	DBG_SET_ELEMS(*bitmap, elems);
	DBG_SET_TRAILER(*bitmap, bitset);
	bitmap->type = OBJ_BITMAP;
	bitmap->bitzero = min;
	bitmap->bitmax = max;
	vl_ClearBitmap(bitmap);

	DBG_TEST_CANARY(*bitmap);
	DBG_TEST_TRAILER(*bitmap, bitset);
	*p_bitmap = bitmap;
}

/** 
 * Set a bit within a ::Bitmap.  If the bit is outside of the acceptable
 * range, raise an error.
 * 
 * @param bitmap The ::Bitmap within which the bit is to be set. 
 * @param bit The bit to be set.
 */
void
vl_BitmapSetbit(Bitmap *bitmap,
				int32 bit)
{
    int relative_bit = bit - BITZERO(bitmap->bitzero);
    int element = BITSET_ELEM(relative_bit);

	if ((bit > bitmap->bitmax) ||
		(bit < bitmap->bitzero)) 
	{
		ereport(ERROR,
				(errcode(ERRCODE_INTERNAL_ERROR),
				 errmsg("Bitmap range error"),
				 errdetail("Bit (%d) not in range %d..%d.  ", bit,
						   bitmap->bitzero, bitmap->bitmax)));
	}

	DBG_CHECK_INDEX(*bitmap, element);
    bitmap->bitset[element] |= bitmasks[BITSET_BIT(relative_bit)];
	DBG_TEST_CANARY(*bitmap);
	DBG_TEST_TRAILER(*bitmap, bitset);
}

/** 
 * Clear a bit within a ::Bitmap.  If the bit is outside of the acceptable
 * range, raise an error.
 * 
 * @param bitmap The ::Bitmap within which the bit is to be cleared. 
 * @param bit The bit to be cleared.
 */
void
vl_BitmapClearbit(Bitmap *bitmap,
				  int32 bit)
{
    int relative_bit = bit - BITZERO(bitmap->bitzero);
    int element = BITSET_ELEM(relative_bit);

	if ((bit > bitmap->bitmax) ||
		(bit < bitmap->bitzero)) 
	{
		ereport(ERROR,
				(errcode(ERRCODE_INTERNAL_ERROR),
				 errmsg("Bitmap range error"),
				 errdetail("Bit (%d) not in range %d..%d.  ", bit,
						   bitmap->bitzero, bitmap->bitmax)));
	}

    bitmap->bitset[element] &= ~(bitmasks[BITSET_BIT(relative_bit)]);
}

/** 
 * Test a bit within a ::Bitmap.  If the bit is outside of the acceptable
 * range return false.
 * 
 * @param bitmap The ::Bitmap within which the bit is to be set. 
 * @param bit The bit to be tested.
 * 
 * @return True if the bit is set, false otherwise.
 */
bool
vl_BitmapTestbit(Bitmap *bitmap,
				 int32 bit)
{
    int relative_bit = bit - BITZERO(bitmap->bitzero);
    int element = BITSET_ELEM(relative_bit);

	if ((bit > bitmap->bitmax) ||
		(bit < bitmap->bitzero)) 
	{
		return false;
	}

    return (bitmap->bitset[element] & bitmasks[BITSET_BIT(relative_bit)]) != 0;
}

/** 
 * Create the union of two bitmaps, updating the first with the result.
 * 
 * @param target The ::Bitmap into which the result will be placed.
 * @param source The ::Bitmap to be unioned into target.
 */
void
vl_BitmapUnion(Bitmap *target,
			   Bitmap *source)
{
	int i;
	int elems = ARRAYELEMS(target->bitzero, target->bitmax);

	/* TODO: Make this tolerant of range mismatches. */
	if ((target->bitzero != source->bitzero) ||
		(target->bitmax != source->bitmax))
	{
		ereport(ERROR,
				(errcode(ERRCODE_INTERNAL_ERROR),
				 errmsg("Incompatible bitmaps"),
				 errdetail("Target range is %d..%d.  Source range %d..%d.",
						   target->bitzero, target->bitmax,
						   source->bitzero, source->bitmax)));
	}
	for (i = 0; i < elems; i++) {
		target->bitset[i] |= source->bitset[i];
	}
}

/** 
 * Create the intersection of two bitmaps, updating the first with the
 * result.
 * 
 * @param target The ::Bitmap into which the result will be placed.
 * @param source The ::Bitmap to be intersected into target.
 */
void
vl_BitmapIntersect(Bitmap *target,
				   Bitmap *source)
{
	int i;
	int elems = ARRAYELEMS(target->bitzero, target->bitmax);

	/* TODO: Make this tolerant of range mismatches. */
	if ((target->bitzero != source->bitzero) ||
		(target->bitmax != source->bitmax))
	{
		ereport(ERROR,
				(errcode(ERRCODE_INTERNAL_ERROR),
				 errmsg("Incompatible bitmaps"),
				 errdetail("Target range is %d..%d.  Source range %d..%d.",
						   target->bitzero, target->bitmax,
						   source->bitzero, source->bitmax)));
	}
	for (i = 0; i < elems; i++) {
		target->bitset[i] &= source->bitset[i];
	}
}

/** 
 * Return the next set bit in the ::Bitmap.
 * 
 * @param bitmap The ::Bitmap being scanned.
 * @param bit The starting bit from which to scan the bitmap
 * @param found Boolean that will be set to true when a set bit has been
 * found.
 * 
 * @return The bit id of the found bit, or zero if no set bits were found. 
 */
int32
vl_BitmapNextBit(Bitmap *bitmap,
				 int32 bit,
				 bool *found)
{
	while (bit <= bitmap->bitmax) {
		if (vl_BitmapTestbit(bitmap, bit)) {
			*found = true;
			return bit;
		}
		bit++;
	}
	*found = false;
	return 0;
}

/** 
 * Return a specified ::Bitmap from a ::BitmapArray.
 * 
 * @param bmarray The ::BitmapArray from which the result is to be
 * returned.
 * @param elem The index of the ::Bitmap within the array. 
 * 
 * @return The bitmap corresponding to the parameters, or NULL if no
 *such entry exists within the array.
 */
Bitmap *
vl_BitmapFromArray(BitmapArray *bmarray,
				   int32 elem)
{
	DBG_TEST_CANARY(*bmarray);
	DBG_TEST_TRAILER(*bmarray, bitmap);
	if ((elem < bmarray->arrayzero) || (elem > bmarray->arraymax)) {
		return NULL;
	}
	else {
		DBG_CHECK_INDEX(*bmarray, elem - bmarray->arrayzero);
		return bmarray->bitmap[elem - bmarray->arrayzero];
	}
}

/** 
 * Clear all bitmaps in the given ::BitmapArray
 * 
 * @param bmarray The ::BitmapArray to be cleared
 */
void
vl_ClearBitmapArray(BitmapArray *bmarray)
{
	int bitmaps = bmarray->arraymax + 1 - bmarray->arrayzero;
	int i;

	DBG_TEST_CANARY(*bmarray);
	DBG_TEST_TRAILER(*bmarray, bitmap);
	for (i = 0; i < bitmaps; i++) {
		DBG_CHECK_INDEX(*bmarray, i);
		vl_ClearBitmap(bmarray->bitmap[i]);
	}
}

/** 
 * Return a newly initialised (empty) ::BitmapArray.  It may already
 * exist in which case it will be re-used if possible.  It may
 * be created in either session or shared memory depending on the value
 * of shared.
 * 
 * @param p_bmarray Pointer to an existing bitmap if one exists.
 * @param shared Whether to create the bitmap in shared memory
 * @param arrayzero The lowest array index
 * @param arraymax The highest array index
 * @param bitzero The smallest bit to be stored in the bitmap
 * @param bitmax The largest bit to be stored in the bitmap
 */
void
vl_NewBitmapArray(BitmapArray **p_bmarray, bool shared,
				  int32 arrayzero, int32 arraymax,
				  int32 bitzero, int32 bitmax)
{
	BitmapArray *bmarray = *p_bmarray;
	int bitsetelems = ARRAYELEMS(bitzero, bitmax);
	int bitmaps = arraymax + 1 - arrayzero;
	int i;

	if (bmarray) {
		/* We already have a bitmap array.  If possible, we re-use it. */
		int cur_elems = ARRAYELEMS(bmarray->bitzero, bmarray->bitmax);
		int cur_maps = bmarray->arraymax + 1 - bmarray->arrayzero;

		DBG_TEST_CANARY(*bmarray);
		DBG_TEST_TRAILER(*bmarray, bitmap);
		if ((cur_elems >= bitsetelems) && (cur_maps >= bitmaps)) {
			vl_ClearBitmapArray(bmarray);
		}
		else {
			if (shared) {
				for (i = 0; i < cur_maps; i++) {
					vl_free(bmarray->bitmap[i]);
				}
				vl_free(bmarray);
			}
			else {
				for (i = 0; i < cur_maps; i++) {
					pfree(bmarray->bitmap[i]);
				}
				pfree(bmarray);
			}
			bmarray = NULL;
		}
	}

	if (!bmarray) {
		if (shared) {
			bmarray = vl_shmalloc(sizeof(BitmapArray) + 
								 (sizeof(Bitmap *) * bitmaps));

		}
		else {
			bmarray = vl_malloc(sizeof(BitmapArray) + 
								(sizeof(Bitmap *) * bitmaps));
		}

		for (i = 0; i < bitmaps; i++) {
			bmarray->bitmap[i] = NULL;
			vl_NewBitmap(&(bmarray->bitmap[i]), shared, bitzero, bitmax);
		}

		bmarray->type = OBJ_BITMAP_ARRAY;
		DBG_SET_CANARY(*bmarray);
		DBG_SET_ELEMS(*bmarray, bitmaps);
		DBG_SET_TRAILERP(*bmarray, bitmap);
	}
	bmarray->bitzero = bitzero;
	bmarray->bitmax = bitmax;
	bmarray->arrayzero = arrayzero;
	bmarray->arraymax = arraymax;

	for (i = 0; i < bitmaps; i++) {
		bmarray->bitmap[i]->type = OBJ_BITMAP;
		bmarray->bitmap[i]->bitzero = bitzero;
		bmarray->bitmap[i]->bitmax = bitmax;
	}

	*p_bmarray = bmarray;
}

/** 
 * Create a new hash table.  This is allocated from session memory as
 * BitmapHashes may not be declared as shared variables.
 * 
 * @param name The name of the hash to be created.  Note that we prefix
 * this with "vl_" to prevent name collisions from other subsystems.
 * 
 * @return Pointer to the newly created hash table.
 */
static HTAB *
new_hash(char *name)
{
	char     vl_name[HASH_KEYLEN];
	HTAB    *hash;
	HASHCTL  hashctl;

	(void) snprintf(vl_name, HASH_KEYLEN - 1, "vl_%s", name);

	hashctl.keysize = HASH_KEYLEN;
	hashctl.entrysize = sizeof(VarEntry);

	hash = hash_create(vl_name, 200, &hashctl, HASH_ELEM);
    return hash;
}

/** 
 * Utility function for scanning the hash table of a BitmapHash.
 * 
 * @param hash The hash table being scanned
 * @param prev The entry from which to scan, starting with NULL.
 * 
 * @return The next element in the hash table (a VarEntry) or NULL when
 * the last element has already been scanned.
 */
VarEntry *
vl_NextHashEntry(HTAB *hash,
				 VarEntry *prev)
{
	VarEntry *next;
	static HASH_SEQ_STATUS status;
	if (!prev) {
		/* Initialise the hash search */
		
		hash_seq_init(&status, hash);
	}
	next = (VarEntry *) hash_seq_search(&status);
	return (next);
}

/** 
 * Return a newly initialised (empty) ::BitmapHash.  It may already
 * exist in which case it will be re-used if possible.  BitmapHash
 * variables may only be created as session (not shared) variables.
 * 
 * @param p_bmhash Pointer to an existing bitmap if one exists.
 * @param name The name to be used for the hash table
 * @param bitzero The smallest bit to be stored in the bitmap
 * @param bitmax The largest bit to be stored in the bitmap
 */
void
vl_NewBitmapHash(BitmapHash **p_bmhash, char *name,
				 int32 bitzero, int32 bitmax)
{
	BitmapHash *bmhash = *p_bmhash;

	if (bmhash) {
		VarEntry *entry = NULL;
		HTAB *hash = bmhash->hash;
		bool found;

		while ((entry = vl_NextHashEntry(hash, entry))) {
			if (entry->obj) {
				if (entry->obj->type != OBJ_BITMAP) {
					ereport(ERROR,
							(errcode(ERRCODE_INTERNAL_ERROR),
							 errmsg("Bitmap hash contains invalid object %d",
									entry->obj->type),
							 errdetail("Object type is %d, expected is %d.",
									   entry->obj->type, OBJ_BITMAP)));
				}
				pfree(entry->obj);  /* Free the bitmap */
			}
			/* Now remove the entry from the hash */
			(void) hash_search(hash, entry->key, HASH_REMOVE, &found);
		}
	}
	else {
		bmhash = vl_malloc(sizeof(BitmapHash));
		bmhash->type = OBJ_BITMAP_HASH;
		bmhash->hash = new_hash(name);
	}
	bmhash->bitzero = bitzero;
	bmhash->bitmax = bitmax;

	*p_bmhash = bmhash;
}

/** 
 * Return a specified ::Bitmap from a ::BitmapHash.  Raise an error if
 * the returned object from the hash search is not a bitmap.
 * 
 * @param bmhash The ::BitmapHash from which the result is to be
 * returned.
 * @param hashelem The key of the ::Bitmap within the hash. 
 * 
 * @return The bitmap corresponding to the parameters, or NULL if no
 *such entry exists within the hash.
 */
Bitmap *
vl_BitmapFromHash(BitmapHash *bmhash,
				  char *hashelem)
{
	VarEntry *var;
	Bitmap   *bitmap;
	bool      found;

	var = hash_search(bmhash->hash, hashelem, HASH_FIND, &found);
	if (!found) {
		return NULL;
	}
	
	if (!var->obj) {
		ereport(ERROR,
				(errcode(ERRCODE_INTERNAL_ERROR),
				 errmsg("BitmapFromHash - empty VarEntry")));
	}

	if (var->obj->type != OBJ_BITMAP) {
		ereport(ERROR,
				(errcode(ERRCODE_INTERNAL_ERROR),
				 errmsg("Bitmap hash contains invalid object %d",
						var->obj->type),
				 errdetail("Object type is %d, expected is %d.",
						   var->obj->type, OBJ_BITMAP)));
	}

	bitmap = (Bitmap *) var->obj;
	return bitmap;
}

/** 
 * Create a newly allocated empty ::Bitmap to a ::BitmapHash
 * 
 * @param bmhash The ::BitmapHash to which to add the new ::Bitmap.
 * @param hashelem The key for the new entry
 * 
 * @return Pointer to the newly allocated empty ::Bitmap.
 */
Bitmap *
vl_AddBitmapToHash(BitmapHash *bmhash,
				   char *hashelem)
{
	VarEntry *var;
	Bitmap   *bitmap = NULL;
	bool      found;

	var = hash_search(bmhash->hash, hashelem, HASH_ENTER, &found);
	if (found) {
		if (!var->obj) {
			ereport(ERROR,
					(errcode(ERRCODE_INTERNAL_ERROR),
					 errmsg("AddBitmapToHash - empty VarEntry")));
		}
		if (var->obj->type != OBJ_BITMAP) {
			ereport(ERROR,
					(errcode(ERRCODE_INTERNAL_ERROR),
					 errmsg("AddBitmapToHash - type mismatch %d",
							var->obj->type),
					 errdetail("Object type is %d, expected is %d.",
							   var->obj->type, OBJ_BITMAP)));
		}
		return (Bitmap *) var->obj;
	}

	/* We've created a new entry.  Now create the bitmap for it. */

	vl_NewBitmap(&bitmap, FALSE, bmhash->bitzero, bmhash->bitmax);
	var->obj = (Object *) bitmap;
	return bitmap;
}

/** 
 * Determine whether the supplied key exists in the ::BitmapHash.
 * 
 * @param bmhash The ::BitmapHash to be tested
 * @param hashelem The key to be tested
 * 
 * @return True if the key already exists in the hash.
 */
bool
vl_BitmapHashHasKey(BitmapHash *bmhash,
				    char *hashelem)
{
	bool found;

	(void) hash_search(bmhash->hash, hashelem, HASH_FIND, &found);
	return found;
}