src

veil_bitmap.c File Reference

Detailed Description

Functions for manipulating Bitmaps, BitmapHashes and BitmapArrays. 

     Author:       Marc Munro
     Copyright (c) 2005, 2006 Marc Munro
     License:      BSD
 $Id: veil_bitmap.c,v 1.4 2007/07/31 22:18:27 bloodnok Exp $

Definition in file veil_bitmap.c.

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

Include dependency graph for veil_bitmap.c:

Go to the source code of this file.

Defines

#define BITZERO(x)   (x & 0xffffffe0)
#define BITMAX(x)   (x | 0x1f)
#define BITSET_ELEM(x)   (x >> 5)
#define BITSET_BIT(x)   (x & 0x1f)
#define ARRAYELEMS(min, max)   (((max - BITZERO(min)) >> 5) + 1)
#define MIN(a, b)   ((a < b)? a: b)

Functions

void vl_ClearBitmap (Bitmap *bitmap)
void vl_NewBitmap (Bitmap **p_bitmap, bool shared, int32 min, int32 max)
void vl_BitmapSetbit (Bitmap *bitmap, int32 bit)
void vl_BitmapClearbit (Bitmap *bitmap, int32 bit)
bool vl_BitmapTestbit (Bitmap *bitmap, int32 bit)
void vl_BitmapUnion (Bitmap *target, Bitmap *source)
void vl_BitmapIntersect (Bitmap *target, Bitmap *source)
int32 vl_BitmapNextBit (Bitmap *bitmap, int32 bit, bool *found)
Bitmap * vl_BitmapFromArray (BitmapArray *bmarray, int32 elem)
void vl_ClearBitmapArray (BitmapArray *bmarray)
void vl_NewBitmapArray (BitmapArray **p_bmarray, bool shared, int32 arrayzero, int32 arraymax, int32 bitzero, int32 bitmax)
static HTAB * new_hash (char *name)
VarEntry * vl_NextHashEntry (HTAB *hash, VarEntry *prev)
void vl_NewBitmapHash (BitmapHash **p_bmhash, char *name, int32 bitzero, int32 bitmax)
Bitmap * vl_BitmapFromHash (BitmapHash *bmhash, char *hashelem)
Bitmap * vl_AddBitmapToHash (BitmapHash *bmhash, char *hashelem)

Variables

static uint32 bitmasks []

Define Documentation

#define ARRAYELEMS ( min,
max   )     (((max - BITZERO(min)) >> 5) + 1)

Gives the number of array elements in a Bitmap that runs from element min to element max.

Parameters:
min 
max 
Returns:
The number of elements in the bitmap.

Definition at line 86 of file veil_bitmap.c.

Referenced by vl_ClearBitmap(), vl_ClearBitmapArray(), and vl_NewBitmap().

#define BITMAX ( x   )     (x | 0x1f)

Gives the bitmask index for the bitmax value of a bitmap. See BITZERO() for more information.

Parameters:
x The bitmax value of a bitmap
Returns:
The bitmask index representing x.

Definition at line 56 of file veil_bitmap.c.

#define BITSET_BIT ( x   )     (x & 0x1f)

Gives the index into bitmasks for the bit specified in x.

Parameters:
x The bit in question
Returns:
The bitmask index

Definition at line 75 of file veil_bitmap.c.

Referenced by vl_BitmapSetbit().

#define BITSET_ELEM ( x   )     (x >> 5)

Gives the index of a bit within the array of 32-bit words that comprise the bitmap.

Parameters:
x The bit in question
Returns:
The array index of the bit.

Definition at line 66 of file veil_bitmap.c.

Referenced by vl_BitmapSetbit().

#define BITZERO ( x   )     (x & 0xffffffe0)

Gives the bitmask index for the bitzero value of a Bitmap. This is part of the "normalisation" process for bitmap ranges. This process allows unlike bitmaps to be more easily compared by forcing bitmap indexes to be normalised around 32-bit word boundaries. Eg, 2 bitmaps with domains 1 to 50 and 3 to 55, will have identical bit patterns for bits 3 to 50.

Parameters:
x The bitzero value of a bitmap
Returns:
The bitmask index representing x.

Definition at line 46 of file veil_bitmap.c.

Referenced by vl_BitmapSetbit().

#define MIN ( a,
b   )     ((a < b)? a: b)

Return the smaller of a or b. Note that expressions a and b may be evaluated more than once.

Parameters:
a 
b 
Returns:
The smaller value of a or b.

Definition at line 98 of file veil_bitmap.c.

Function Documentation

static HTAB* new_hash ( char *  name  )  [static]

Create a new hash table. This is allocated from session memory as BitmapHashes may not be declared as shared variables.

Parameters:
name The name of the hash to be created. Note that we prefix this with "vl_" to prevent name collisions from other subsystems.
Returns:
Pointer to the newly created hash table.

Definition at line 500 of file veil_bitmap.c.

Bitmap* vl_AddBitmapToHash ( BitmapHash *  bmhash,
char *  hashelem 
)

Create a newly allocated empty Bitmap to a BitmapHash

Parameters:
bmhash The BitmapHash to which to add the new Bitmap.
hashelem The key for the new entry
Returns:
Pointer to the newly allocated empty Bitmap.

Definition at line 642 of file veil_bitmap.c.

void vl_BitmapClearbit ( Bitmap *  bitmap,
int32  bit 
)

Clear a bit within a Bitmap. If the bit is outside of the acceptable range, raise an error.

Parameters:
bitmap The Bitmap within which the bit is to be cleared.
bit The bit to be cleared.

Definition at line 221 of file veil_bitmap.c.

References Bitmap::bitmax, and Bitmap::bitzero.

Bitmap* vl_BitmapFromArray ( BitmapArray *  bmarray,
int32  elem 
)

Return a specified Bitmap from a BitmapArray.

Parameters:
bmarray The BitmapArray from which the result is to be returned.
elem The index of the Bitmap within the array.
Returns:
The bitmap corresponding to the parameters, or NULL if no such entry exists within the array.

Definition at line 364 of file veil_bitmap.c.

Referenced by veil_bitmap_array_bits().

Bitmap* vl_BitmapFromHash ( BitmapHash *  bmhash,
char *  hashelem 
)

Return a specified Bitmap from a BitmapHash. Raise an error if the returned object from the hash search is not a bitmap.

Parameters:
bmhash The BitmapHash from which the result is to be returned.
hashelem The key of the Bitmap within the hash.
Returns:
The bitmap corresponding to the parameters, or NULL if no such entry exists within the hash.

Definition at line 600 of file veil_bitmap.c.

References VarEntry::obj, and Object::type.

Referenced by veil_bitmap_hash_bits().

void vl_BitmapIntersect ( Bitmap *  target,
Bitmap *  source 
)

Create the intersection of two bitmaps, updating the first with the result.

Parameters:
target The Bitmap into which the result will be placed.
source The Bitmap to be intersected into target.

Definition at line 304 of file veil_bitmap.c.

References Bitmap::bitmax, and Bitmap::bitzero.

int32 vl_BitmapNextBit ( Bitmap *  bitmap,
int32  bit,
bool *  found 
)

Return the next set bit in the Bitmap.

Parameters:
bitmap The Bitmap being scanned.
bit The starting bit from which to scan the bitmap
found Boolean that will be set to true when a set bit has been found.
Returns:
The bit id of the found bit, or zero if no set bits were found.

Definition at line 338 of file veil_bitmap.c.

void vl_BitmapSetbit ( Bitmap *  bitmap,
int32  bit 
)

Set a bit within a Bitmap. If the bit is outside of the acceptable range, raise an error.

Parameters:
bitmap The Bitmap within which the bit is to be set.
bit The bit to be set.

Definition at line 187 of file veil_bitmap.c.

References bitmasks, Bitmap::bitmax, Bitmap::bitset, BITSET_BIT, BITSET_ELEM, Bitmap::bitzero, BITZERO, DBG_CHECK_INDEX, DBG_TEST_CANARY, and DBG_TEST_TRAILER.

bool vl_BitmapTestbit ( Bitmap *  bitmap,
int32  bit 
)

Test a bit within a Bitmap. If the bit is outside of the acceptable range return false.

Parameters:
bitmap The Bitmap within which the bit is to be set.
bit The bit to be tested.
Returns:
True if the bit is set, false otherwise.

Definition at line 251 of file veil_bitmap.c.

void vl_BitmapUnion ( Bitmap *  target,
Bitmap *  source 
)

Create the union of two bitmaps, updating the first with the result.

Parameters:
target The Bitmap into which the result will be placed.
source The Bitmap to be unioned into target.

Definition at line 273 of file veil_bitmap.c.

References Bitmap::bitmax, and Bitmap::bitzero.

void vl_ClearBitmap ( Bitmap *  bitmap  ) 

Clear all bits in a Bitmap.

Parameters:
bitmap The Bitmap in which all bits are to be cleared

Definition at line 107 of file veil_bitmap.c.

References ARRAYELEMS, Bitmap::bitmax, Bitmap::bitset, and Bitmap::bitzero.

Referenced by vl_NewBitmap().

void vl_ClearBitmapArray ( BitmapArray *  bmarray  ) 

Clear all bitmaps in the given BitmapArray

Parameters:
bmarray The BitmapArray to be cleared

Definition at line 387 of file veil_bitmap.c.

References ARRAYELEMS, BitmapArray::arraymax, BitmapArray::arrayzero, BitmapArray::bitmax, BitmapArray::bitzero, and DBG_TEST_CANARY.

void vl_NewBitmap ( Bitmap **  p_bitmap,
bool  shared,
int32  min,
int32  max 
)

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.

Parameters:
p_bitmap Pointer to an existing bitmap if one exists.
shared Whether to create the bitmap in shared memory
min The smallest bit to be stored in the bitmap
max The largest bit to be stored in the bitmap

Definition at line 129 of file veil_bitmap.c.

References ARRAYELEMS, Bitmap::bitmax, Bitmap::bitzero, DBG_SET_CANARY, DBG_SET_ELEMS, DBG_SET_TRAILER, DBG_TEST_CANARY, DBG_TEST_TRAILER, Bitmap::type, vl_ClearBitmap(), vl_free(), vl_malloc(), and vl_shmalloc().

Here is the call graph for this function:

void vl_NewBitmapArray ( BitmapArray **  p_bmarray,
bool  shared,
int32  arrayzero,
int32  arraymax,
int32  bitzero,
int32  bitmax 
)

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.

Parameters:
p_bmarray Pointer to an existing bitmap if one exists.
shared Whether to create the bitmap in shared memory
arrayzero The lowest array index
arraymax The highest array index
bitzero The smallest bit to be stored in the bitmap
bitmax The largest bit to be stored in the bitmap

Definition at line 417 of file veil_bitmap.c.

void vl_NewBitmapHash ( BitmapHash **  p_bmhash,
char *  name,
int32  bitzero,
int32  bitmax 
)

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.

Parameters:
p_bmhash Pointer to an existing bitmap if one exists.
name The name to be used for the hash table
bitzero The smallest bit to be stored in the bitmap
bitmax The largest bit to be stored in the bitmap

Definition at line 550 of file veil_bitmap.c.

VarEntry* vl_NextHashEntry ( HTAB *  hash,
VarEntry *  prev 
)

Utility function for scanning the hash table of a BitmapHash.

Parameters:
hash The hash table being scanned
prev The entry from which to scan, starting with NULL.
Returns:
The next element in the hash table (a VarEntry) or NULL when the last element has already been scanned.

Definition at line 525 of file veil_bitmap.c.

References BitmapHash::hash, VarEntry::obj, Object::type, and vl_NextHashEntry().

Referenced by vl_NextHashEntry().

Here is the call graph for this function:

Variable Documentation

uint32 bitmasks[] [static]

Initial value:

 {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}
Array of bit positions for int32, indexed by bitno.

Definition at line 25 of file veil_bitmap.c.

Referenced by vl_BitmapSetbit().

Generated on Tue Mar 11 10:08:37 2008 for Veil by  doxygen 1.5.4