~drizzle-trunk/drizzle/development : contents of mysys/my

~drizzle-trunk/drizzle/development : (revision 1208)

/* Copyright (C) 2000 MySQL AB

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; version 2 of the License.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */

#ifndef MYSYS_MY_BITMAP_H
#define MYSYS_MY_BITMAP_H

#include <pthread.h>
#include <string.h>

static const uint32_t MY_BIT_NONE= UINT32_MAX;

typedef uint32_t my_bitmap_map;

/**
 * @class MyBitmap
 * @brief Represents a dynamically sized bitmap.
 *
 * Handling of unsigned char arrays as large bitmaps.
 * 
 * API limitations (or, rather asserted safety assumptions,
 * to encourage correct programming)
 *   - the internal size is a set of 32 bit words
 *   - the number of bits specified in creation can be any number
 *     greater than 0
 *
 * Original version created by Sergei Golubchik 2001 - 2004.
 * New version written and test program added and some changes to the 
 * interface was made by Mikael Ronström 2005, with assistance of Tomas 
 * Ulin and Mats Kindahl.
 */
class MyBitmap
{
public:
  MyBitmap()
    :
      bitmap(NULL),
      n_bits(0),
      last_word_mask(0),
      last_word_ptr(NULL)
  {}

  MyBitmap(const MyBitmap& rhs);

  ~MyBitmap()
  {
      /*
       * We are not de-allocating memory here correctly at the moment!!!!
       * Placing a delete [] statement here causes bad bad things to
       * happen......
       * Placing this comment here in the hope that someone can help me
       * resolve this issue....
       */
      bitmap= 0;
  }

  MyBitmap& operator=(const MyBitmap& rhs);

  bool init(my_bitmap_map *buf, uint32_t num_bits);

  /**
   * Compare the given bitmap with this bitmap.
   *
   * @param[in] map bitmap to perform a comparison against
   * @return true if bitmaps are equal; false otherwise
   */
  bool operator==(const MyBitmap *map)
  {
    *last_word_ptr|= last_word_mask;
    *(map)->last_word_ptr|= (map)->last_word_mask;
    return memcmp(bitmap, map->getBitmap(), 4*numOfWordsInMap())==0;
  }

  /**
   * Test whether the specified bit is set in the bitmap
   * already and set it if it was not already set.
   *
   * @param[in] bitPos position to test and set
   * @return false if the bit was not set; true otherwise
   */
  bool testAndSet(const uint32_t bitPos);

  /**
   * Test whether the specified bit is set in the bitmap
   * and clear it if it was set.
   *
   * @param[in] bitPos position to test and clear
   * @return false if the bit was not set; true otherwise
   */
  bool testAndClear(const uint32_t bitPos);

  /**
   * Set the next bit position that is not yet set starting
   * from the beginning of the bitmap.
   *
   * @return the bit position that was set
   */
  uint32_t setNext();

  uint32_t getFirst();

  /**
   * @return the position of the first bit set.
   */
  uint32_t getFirstSet();

  /**
   * @return the bits set in this bitmap.
   */
  uint32_t getBitsSet();

  /**
   * Set/clear all bits above a bit.
   * Only full bytes can be set/cleared.
   * The function is meant for the situation that you can copy
   * a smaller bitmap to a bigger bitmap. Bitmap lengths are
   * always a multiple of 8 (byte size). Using 'from_byte' saves
   * multiplication and division by 8 during parameter passing.
   *
   * @param[in] from_byte bitmap buffer byte offset to start with
   * @param[in] use_bit bit value (1/0) to use for all upper bits
   */
  void setAbove(const uint32_t from_byte, const uint32_t use_bit);


  /**
   * Test whether all the bits in the bitmap are clear or not.
   *
   * @return true if all bits in bitmap are cleared; false otherwise
   */
  bool isClearAll() const;

  bool isPrefix(const uint32_t prefix_size) const;

  void setPrefix(uint32_t prefix_size);

  /**
   * Test whether all the bits in the bitmap are set or not.
   *
   * @return true if all bits in bitmap are set; false otherwise
   */
  bool isSetAll() const;


  /**
   * Test if the specified bit is set or not.
   *
   * @param[in] bit position of bit to test
   * @return true if the bit is set; false otherwise
   */
  bool isBitSet(const uint32_t bit) const
  {
    return (bool)(((unsigned char *)bitmap)[bit / 8] &  (1 << ((bit) & 7)));
  }

  /**
   * Set the specified bit.
   *
   * @param[in] bit position of bit to set in bitmap
   */
  void setBit(const uint32_t bit)
  {
    reinterpret_cast<unsigned char *>(bitmap)[bit / 8]= 
      static_cast<unsigned char>(
      (reinterpret_cast<unsigned char *>(bitmap))[bit / 8] | 
      (1 << ((bit) & 7)));
  }

  /**
   * Flip the specified bit.
   *
   * @param[in] bit position of bit to flip in bitmap
   */
  void flipBit(const uint32_t bit)
  {
    reinterpret_cast<unsigned char *>(bitmap)[bit / 8]= 
      static_cast<unsigned char>(
      (reinterpret_cast<unsigned char *>(bitmap))[bit / 8] ^ 
      (1 << ((bit) & 7)));
  }

  /**
   * Clear the specified bit.
   *
   * @param[in] bit position of bit to clear in bitmap
   */
  void clearBit(const uint32_t bit)
  {
    reinterpret_cast<unsigned char *>(bitmap)[bit / 8]= 
      static_cast<unsigned char>(
      (reinterpret_cast<unsigned char *>(bitmap))[bit / 8] & 
      ~ (1 << ((bit) & 7)));
  }

  /**
   * Clear all the bits in the bitmap i.e. set every
   * bit to 0.
   */
  void clearAll()
  {
     memset(bitmap, 0, 4*numOfWordsInMap());
  }

  /**
   * Set all the bits in the bitmap i.e. set every
   * bit to 1.
   */
  void setAll()
  {
     memset(bitmap, 0xFF, 4*numOfWordsInMap());
  }

  /**
   * @return the number of words in this bitmap.
   */
  uint32_t numOfWordsInMap() const
  {
    return ((n_bits + 31)/32);
  }

  /**
   * @return the number of bytes in this bitmap.
   */
  uint32_t numOfBytesInMap() const
  {
    return ((n_bits + 7)/8);
  }

  /**
   * Get the size of the bitmap in bits.
   *
   * @return the size of the bitmap in bits.
   */
  uint32_t numOfBitsInMap() const
  {
    return n_bits;
  }

  /**
   * @return the current bitmap
   */
  my_bitmap_map *getBitmap() const
  {
    return bitmap;
  }

  /**
   * Set the bitmap to the specified bitmap.
   *
   * @param[in] new_bitmap bitmap to use
   */
  void setBitmap(my_bitmap_map *new_bitmap)
  {
    bitmap= new_bitmap;
  }

  /**
   * Obtains the number of used bits (1..8) in the last
   * byte and creates a mask with the upper 'unused' bits
   * set and the lower 'used' bits clear. 
   */
  void createLastWordMask();

  /**
   * @return the last word pointer for this bitmap
   */
  my_bitmap_map *getLastWordPtr() const
  {
    return last_word_ptr;
  }

  void addMaskToLastWord() const
  {
    *last_word_ptr|= last_word_mask;
  }

  /**
   * This resets the last bits in the bitmap to 0.
   */
  void subtractMaskFromLastWord() const
  {
    *last_word_ptr&= ~last_word_mask;
  }

private:

  /**
   * The bitmap is stored in this variable.
   */
  my_bitmap_map *bitmap;

  /**
   * Number of bits occupied by the bitmap.
   */
  uint32_t n_bits;

  /**
   * A mask used for the last word in the bitmap.
   */
  my_bitmap_map last_word_mask;

  /**
   * A pointer to the last word in the bitmap.
   */
  my_bitmap_map *last_word_ptr;

};

bool bitmap_is_subset(const MyBitmap *map1, const MyBitmap *map2);
bool bitmap_is_overlapping(const MyBitmap *map1,
                           const MyBitmap *map2);

void bitmap_intersect(MyBitmap *map, const MyBitmap *map2);
void bitmap_subtract(MyBitmap *map, const MyBitmap *map2);
void bitmap_union(MyBitmap *map, const MyBitmap *map2);
void bitmap_xor(MyBitmap *map, const MyBitmap *map2);
void bitmap_invert(MyBitmap *map);

/* Fast, not thread safe, bitmap functions */
/* This one is a define because it gets used in an array decl */
#define bitmap_buffer_size(bits) ((bits+31)/32)*4

template <class T>
inline T bytes_word_aligned(T bytes)
{
  return (4*((bytes + 3)/4));
}

static inline bool bitmap_cmp(const MyBitmap *map1, const MyBitmap *map2)
{
  map1->addMaskToLastWord();
  map2->addMaskToLastWord();
  return memcmp((map1)->getBitmap(), 
                (map2)->getBitmap(),
                4*map1->numOfWordsInMap()) == 0;
}

#endif /* MYSYS_MY_BITMAP_H */

1005.2.1 by Monty Taylor Reverted a crap-ton of padraig's work.	1	/* Copyright (C) 2000 MySQL AB
	2
	3	This program is free software; you can redistribute it and/or modify
	4	it under the terms of the GNU General Public License as published by
	5	the Free Software Foundation; version 2 of the License.
	6
	7	This program is distributed in the hope that it will be useful,
	8	but WITHOUT ANY WARRANTY; without even the implied warranty of
	9	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	10	GNU General Public License for more details.
	11
	12	You should have received a copy of the GNU General Public License
	13	along with this program; if not, write to the Free Software
	14	Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
	15
1005.2.15 by Monty Taylor More my_bitmap header cleanup.	16	#ifndef MYSYS_MY_BITMAP_H
	17	#define MYSYS_MY_BITMAP_H
	18
	19	#include <pthread.h>
	20	#include <string.h>
	21
	22	static const uint32_t MY_BIT_NONE= UINT32_MAX;
1005.2.1 by Monty Taylor Reverted a crap-ton of padraig's work.	23
	24	typedef uint32_t my_bitmap_map;
	25
1103.6.1 by Padraig O'Sullivan Converted MY_BITMAP from a struct to a class named MyBitmap. Added a copy	26	/**
	27	* @class MyBitmap
	28	* @brief Represents a dynamically sized bitmap.
	29	*
	30	* Handling of unsigned char arrays as large bitmaps.
	31	*
	32	* API limitations (or, rather asserted safety assumptions,
	33	* to encourage correct programming)
	34	* - the internal size is a set of 32 bit words
	35	* - the number of bits specified in creation can be any number
	36	* greater than 0
	37	*
	38	* Original version created by Sergei Golubchik 2001 - 2004.
	39	* New version written and test program added and some changes to the
	40	* interface was made by Mikael Ronström 2005, with assistance of Tomas
	41	* Ulin and Mats Kindahl.
	42	*/
	43	class MyBitmap
1005.2.1 by Monty Taylor Reverted a crap-ton of padraig's work.	44	{
1103.6.1 by Padraig O'Sullivan Converted MY_BITMAP from a struct to a class named MyBitmap. Added a copy	45	public:
	46	MyBitmap()
	47	:
	48	bitmap(NULL),
	49	n_bits(0),
	50	last_word_mask(0),
1103.6.2 by Padraig O'Sullivan Removing references to MY_BITMAP throughout the code base and updating calls	51	last_word_ptr(NULL)
1103.6.1 by Padraig O'Sullivan Converted MY_BITMAP from a struct to a class named MyBitmap. Added a copy	52	{}
	53
	54	MyBitmap(const MyBitmap& rhs);
	55
	56	~MyBitmap()
	57	{
1103.6.6 by Padraig O'Sullivan Updating desctructor in MyBitmap class to work for now (although not	58	/*
	59	* We are not de-allocating memory here correctly at the moment!!!!
	60	* Placing a delete [] statement here causes bad bad things to
	61	* happen......
	62	* Placing this comment here in the hope that someone can help me
	63	* resolve this issue....
	64	*/
	65	bitmap= 0;
1103.6.1 by Padraig O'Sullivan Converted MY_BITMAP from a struct to a class named MyBitmap. Added a copy	66	}
	67
	68	MyBitmap& operator=(const MyBitmap& rhs);
	69
	70	bool init(my_bitmap_map *buf, uint32_t num_bits);
	71
	72	/**
	73	* Compare the given bitmap with this bitmap.
	74	*
	75	* @param[in] map bitmap to perform a comparison against
	76	* @return true if bitmaps are equal; false otherwise
	77	*/
	78	bool operator==(const MyBitmap *map)
	79	{
	80	*last_word_ptr\|= last_word_mask;
	81	*(map)->last_word_ptr\|= (map)->last_word_mask;
	82	return memcmp(bitmap, map->getBitmap(), 4*numOfWordsInMap())==0;
	83	}
	84
	85	/**
	86	* Test whether the specified bit is set in the bitmap
	87	* already and set it if it was not already set.
	88	*
	89	* @param[in] bitPos position to test and set
	90	* @return false if the bit was not set; true otherwise
	91	*/
	92	bool testAndSet(const uint32_t bitPos);
	93
	94	/**
	95	* Test whether the specified bit is set in the bitmap
	96	* and clear it if it was set.
	97	*
	98	* @param[in] bitPos position to test and clear
	99	* @return false if the bit was not set; true otherwise
	100	*/
	101	bool testAndClear(const uint32_t bitPos);
	102
	103	/**
	104	* Set the next bit position that is not yet set starting
	105	* from the beginning of the bitmap.
	106	*
	107	* @return the bit position that was set
	108	*/
	109	uint32_t setNext();
	110
	111	uint32_t getFirst();
	112
	113	/**
	114	* @return the position of the first bit set.
	115	*/
	116	uint32_t getFirstSet();
	117
	118	/**
	119	* @return the bits set in this bitmap.
	120	*/
	121	uint32_t getBitsSet();
	122
	123	/**
	124	* Set/clear all bits above a bit.
	125	* Only full bytes can be set/cleared.
	126	* The function is meant for the situation that you can copy
	127	* a smaller bitmap to a bigger bitmap. Bitmap lengths are
	128	* always a multiple of 8 (byte size). Using 'from_byte' saves
	129	* multiplication and division by 8 during parameter passing.
130	*
131	* @param[in] from_byte bitmap buffer byte offset to start with
132	* @param[in] use_bit bit value (1/0) to use for all upper bits
133	*/
134	void setAbove(const uint32_t from_byte, const uint32_t use_bit);
135
136
137	/**
138	* Test whether all the bits in the bitmap are clear or not.
139	*
140	* @return true if all bits in bitmap are cleared; false otherwise
141	*/
142	bool isClearAll() const;
143
144	bool isPrefix(const uint32_t prefix_size) const;
145
146	void setPrefix(uint32_t prefix_size);
147
148	/**
149	* Test whether all the bits in the bitmap are set or not.
150	*
151	* @return true if all bits in bitmap are set; false otherwise
152	*/
153	bool isSetAll() const;
154
155
156	/**
157	* Test if the specified bit is set or not.
158	*
159	* @param[in] bit position of bit to test
160	* @return true if the bit is set; false otherwise
161	*/
162	bool isBitSet(const uint32_t bit) const
163	{
164	return (bool)(((unsigned char *)bitmap)[bit / 8] & (1 << ((bit) & 7)));
165	}
166
167	/**
168	* Set the specified bit.
169	*
170	* @param[in] bit position of bit to set in bitmap
171	*/
172	void setBit(const uint32_t bit)
173	{
1126.8.1 by Joe Daly changes to allow -Wconversion flag to be turned on	174	reinterpret_cast<unsigned char *>(bitmap)[bit / 8]=
	175	static_cast<unsigned char>(
	176	(reinterpret_cast<unsigned char *>(bitmap))[bit / 8] \|
	177	(1 << ((bit) & 7)));
1103.6.1 by Padraig O'Sullivan Converted MY_BITMAP from a struct to a class named MyBitmap. Added a copy	178	}
	179
	180	/**
	181	* Flip the specified bit.
	182	*
	183	* @param[in] bit position of bit to flip in bitmap
	184	*/
	185	void flipBit(const uint32_t bit)
	186	{
1126.8.1 by Joe Daly changes to allow -Wconversion flag to be turned on	187	reinterpret_cast<unsigned char *>(bitmap)[bit / 8]=
	188	static_cast<unsigned char>(
	189	(reinterpret_cast<unsigned char *>(bitmap))[bit / 8] ^
	190	(1 << ((bit) & 7)));
1103.6.1 by Padraig O'Sullivan Converted MY_BITMAP from a struct to a class named MyBitmap. Added a copy	191	}
	192
	193	/**
	194	* Clear the specified bit.
	195	*
	196	* @param[in] bit position of bit to clear in bitmap
	197	*/
	198	void clearBit(const uint32_t bit)
	199	{
1126.8.1 by Joe Daly changes to allow -Wconversion flag to be turned on	200	reinterpret_cast<unsigned char *>(bitmap)[bit / 8]=
	201	static_cast<unsigned char>(
	202	(reinterpret_cast<unsigned char *>(bitmap))[bit / 8] &
	203	~ (1 << ((bit) & 7)));
1103.6.1 by Padraig O'Sullivan Converted MY_BITMAP from a struct to a class named MyBitmap. Added a copy	204	}
	205
	206	/**
	207	* Clear all the bits in the bitmap i.e. set every
	208	* bit to 0.
	209	*/
	210	void clearAll()
	211	{
	212	memset(bitmap, 0, 4*numOfWordsInMap());
	213	}
	214
	215	/**
	216	* Set all the bits in the bitmap i.e. set every
	217	* bit to 1.
	218	*/
	219	void setAll()
	220	{
	221	memset(bitmap, 0xFF, 4*numOfWordsInMap());
	222	}
	223
	224	/**
	225	* @return the number of words in this bitmap.
	226	*/
	227	uint32_t numOfWordsInMap() const
	228	{
	229	return ((n_bits + 31)/32);
	230	}
	231
	232	/**
	233	* @return the number of bytes in this bitmap.
	234	*/
	235	uint32_t numOfBytesInMap() const
	236	{
	237	return ((n_bits + 7)/8);
	238	}
	239
	240	/**
	241	* Get the size of the bitmap in bits.
	242	*
	243	* @return the size of the bitmap in bits.
	244	*/
	245	uint32_t numOfBitsInMap() const
	246	{
	247	return n_bits;
	248	}
	249
	250	/**
	251	* @return the current bitmap
	252	*/
	253	my_bitmap_map *getBitmap() const
	254	{
	255	return bitmap;
	256	}
	257
	258	/**
1103.6.2 by Padraig O'Sullivan Removing references to MY_BITMAP throughout the code base and updating calls	259	* Set the bitmap to the specified bitmap.
	260	*
	261	* @param[in] new_bitmap bitmap to use
	262	*/
	263	void setBitmap(my_bitmap_map *new_bitmap)
	264	{
	265	bitmap= new_bitmap;
	266	}
	267
	268	/**
1103.6.1 by Padraig O'Sullivan Converted MY_BITMAP from a struct to a class named MyBitmap. Added a copy	269	* Obtains the number of used bits (1..8) in the last
	270	* byte and creates a mask with the upper 'unused' bits
	271	* set and the lower 'used' bits clear.
	272	*/
	273	void createLastWordMask();
	274
	275	/**
	276	* @return the last word pointer for this bitmap
	277	*/
	278	my_bitmap_map *getLastWordPtr() const
	279	{
	280	return last_word_ptr;
	281	}
	282
	283	void addMaskToLastWord() const
	284	{
	285	*last_word_ptr\|= last_word_mask;
	286	}
	287
	288	/**
	289	* This resets the last bits in the bitmap to 0.
	290	*/
	291	void subtractMaskFromLastWord() const
	292	{
	293	*last_word_ptr&= ~last_word_mask;
	294	}
	295
	296	private:
	297
	298	/**
	299	* The bitmap is stored in this variable.
	300	*/
1005.2.1 by Monty Taylor Reverted a crap-ton of padraig's work.	301	my_bitmap_map *bitmap;
1103.6.1 by Padraig O'Sullivan Converted MY_BITMAP from a struct to a class named MyBitmap. Added a copy	302
	303	/**
	304	* Number of bits occupied by the bitmap.
	305	*/
	306	uint32_t n_bits;
	307
	308	/**
	309	* A mask used for the last word in the bitmap.
	310	*/
1005.2.1 by Monty Taylor Reverted a crap-ton of padraig's work.	311	my_bitmap_map last_word_mask;
1103.6.1 by Padraig O'Sullivan Converted MY_BITMAP from a struct to a class named MyBitmap. Added a copy	312
	313	/**
	314	* A pointer to the last word in the bitmap.
	315	*/
1005.2.1 by Monty Taylor Reverted a crap-ton of padraig's work.	316	my_bitmap_map *last_word_ptr;
1103.6.1 by Padraig O'Sullivan Converted MY_BITMAP from a struct to a class named MyBitmap. Added a copy	317
	318	};
	319
	320	bool bitmap_is_subset(const MyBitmap map1, const MyBitmap map2);
	321	bool bitmap_is_overlapping(const MyBitmap *map1,
	322	const MyBitmap *map2);
	323
	324	void bitmap_intersect(MyBitmap map, const MyBitmap map2);
	325	void bitmap_subtract(MyBitmap map, const MyBitmap map2);
	326	void bitmap_union(MyBitmap map, const MyBitmap map2);
	327	void bitmap_xor(MyBitmap map, const MyBitmap map2);
	328	void bitmap_invert(MyBitmap *map);
1005.2.15 by Monty Taylor More my_bitmap header cleanup.	329
1005.2.1 by Monty Taylor Reverted a crap-ton of padraig's work.	330	/* Fast, not thread safe, bitmap functions */
1005.2.15 by Monty Taylor More my_bitmap header cleanup.	331	/* This one is a define because it gets used in an array decl */
	332	#define bitmap_buffer_size(bits) ((bits+31)/32)*4
	333
	334	template <class T>
	335	inline T bytes_word_aligned(T bytes)
	336	{
	337	return (4*((bytes + 3)/4));
	338	}
1005.2.13 by Monty Taylor Turned macros in my_bitmap into honest inline methods.	339
1103.6.1 by Padraig O'Sullivan Converted MY_BITMAP from a struct to a class named MyBitmap. Added a copy	340	static inline bool bitmap_cmp(const MyBitmap map1, const MyBitmap map2)
	341	{
	342	map1->addMaskToLastWord();
	343	map2->addMaskToLastWord();
	344	return memcmp((map1)->getBitmap(),
	345	(map2)->getBitmap(),
	346	4*map1->numOfWordsInMap()) == 0;
1005.2.13 by Monty Taylor Turned macros in my_bitmap into honest inline methods.	347	}
1005.2.1 by Monty Taylor Reverted a crap-ton of padraig's work.	348
1005.2.15 by Monty Taylor More my_bitmap header cleanup.	349	#endif /* MYSYS_MY_BITMAP_H */