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

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

/* 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)
  {
    ((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)
  {
    ((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)
  {
    ((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	{
174	((unsigned char *)bitmap)[bit / 8] \|= (1 << ((bit) & 7));
175	}
176
177	/**
178	* Flip the specified bit.
179	*
180	* @param[in] bit position of bit to flip in bitmap
181	*/
182	void flipBit(const uint32_t bit)
183	{
184	((unsigned char *)bitmap)[bit / 8] ^= (1 << ((bit) & 7));
185	}
186
187	/**
188	* Clear the specified bit.
189	*
190	* @param[in] bit position of bit to clear in bitmap
191	*/
192	void clearBit(const uint32_t bit)
193	{
194	((unsigned char *)bitmap)[bit / 8] &= ~ (1 << ((bit) & 7));
195	}
196
197	/**
198	* Clear all the bits in the bitmap i.e. set every
199	* bit to 0.
200	*/
201	void clearAll()
202	{
203	memset(bitmap, 0, 4*numOfWordsInMap());
204	}
205
206	/**
207	* Set all the bits in the bitmap i.e. set every
208	* bit to 1.
209	*/
210	void setAll()
211	{
212	memset(bitmap, 0xFF, 4*numOfWordsInMap());
213	}
214
215	/**
216	* @return the number of words in this bitmap.
217	*/
218	uint32_t numOfWordsInMap() const
219	{
220	return ((n_bits + 31)/32);
221	}
222
223	/**
224	* @return the number of bytes in this bitmap.
225	*/
226	uint32_t numOfBytesInMap() const
227	{
228	return ((n_bits + 7)/8);
229	}
230
231	/**
232	* Get the size of the bitmap in bits.
233	*
234	* @return the size of the bitmap in bits.
235	*/
236	uint32_t numOfBitsInMap() const
237	{
238	return n_bits;
239	}
240
241	/**
242	* @return the current bitmap
243	*/
244	my_bitmap_map *getBitmap() const
245	{
246	return bitmap;
247	}
248
249	/**
1103.6.2 by Padraig O'Sullivan Removing references to MY_BITMAP throughout the code base and updating calls	250	* Set the bitmap to the specified bitmap.
	251	*
	252	* @param[in] new_bitmap bitmap to use
	253	*/
	254	void setBitmap(my_bitmap_map *new_bitmap)
	255	{
	256	bitmap= new_bitmap;
	257	}
	258
	259	/**
1103.6.1 by Padraig O'Sullivan Converted MY_BITMAP from a struct to a class named MyBitmap. Added a copy	260	* Obtains the number of used bits (1..8) in the last
	261	* byte and creates a mask with the upper 'unused' bits
	262	* set and the lower 'used' bits clear.
	263	*/
	264	void createLastWordMask();
	265
	266	/**
	267	* @return the last word pointer for this bitmap
	268	*/
	269	my_bitmap_map *getLastWordPtr() const
	270	{
	271	return last_word_ptr;
	272	}
	273
	274	void addMaskToLastWord() const
	275	{
	276	*last_word_ptr\|= last_word_mask;
	277	}
	278
	279	/**
	280	* This resets the last bits in the bitmap to 0.
	281	*/
	282	void subtractMaskFromLastWord() const
	283	{
	284	*last_word_ptr&= ~last_word_mask;
	285	}
	286
	287	private:
	288
	289	/**
	290	* The bitmap is stored in this variable.
	291	*/
1005.2.1 by Monty Taylor Reverted a crap-ton of padraig's work.	292	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	293
	294	/**
	295	* Number of bits occupied by the bitmap.
	296	*/
	297	uint32_t n_bits;
	298
	299	/**
	300	* A mask used for the last word in the bitmap.
	301	*/
1005.2.1 by Monty Taylor Reverted a crap-ton of padraig's work.	302	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	303
	304	/**
	305	* A pointer to the last word in the bitmap.
	306	*/
1005.2.1 by Monty Taylor Reverted a crap-ton of padraig's work.	307	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	308
	309	};
	310
	311	bool bitmap_is_subset(const MyBitmap map1, const MyBitmap map2);
	312	bool bitmap_is_overlapping(const MyBitmap *map1,
	313	const MyBitmap *map2);
	314
	315	void bitmap_intersect(MyBitmap map, const MyBitmap map2);
	316	void bitmap_subtract(MyBitmap map, const MyBitmap map2);
	317	void bitmap_union(MyBitmap map, const MyBitmap map2);
	318	void bitmap_xor(MyBitmap map, const MyBitmap map2);
	319	void bitmap_invert(MyBitmap *map);
1005.2.15 by Monty Taylor More my_bitmap header cleanup.	320
1005.2.1 by Monty Taylor Reverted a crap-ton of padraig's work.	321	/* Fast, not thread safe, bitmap functions */
1005.2.15 by Monty Taylor More my_bitmap header cleanup.	322	/* This one is a define because it gets used in an array decl */
	323	#define bitmap_buffer_size(bits) ((bits+31)/32)*4
	324
	325	template <class T>
	326	inline T bytes_word_aligned(T bytes)
	327	{
	328	return (4*((bytes + 3)/4));
	329	}
1005.2.13 by Monty Taylor Turned macros in my_bitmap into honest inline methods.	330
1103.6.1 by Padraig O'Sullivan Converted MY_BITMAP from a struct to a class named MyBitmap. Added a copy	331	static inline bool bitmap_cmp(const MyBitmap map1, const MyBitmap map2)
	332	{
	333	map1->addMaskToLastWord();
	334	map2->addMaskToLastWord();
	335	return memcmp((map1)->getBitmap(),
	336	(map2)->getBitmap(),
	337	4*map1->numOfWordsInMap()) == 0;
1005.2.13 by Monty Taylor Turned macros in my_bitmap into honest inline methods.	338	}
1005.2.1 by Monty Taylor Reverted a crap-ton of padraig's work.	339
1005.2.15 by Monty Taylor More my_bitmap header cleanup.	340	#endif /* MYSYS_MY_BITMAP_H */