00001 /* 00002 00003 Copyright (c) 2004, Cornell University 00004 All rights reserved. 00005 00006 Redistribution and use in source and binary forms, with or without 00007 modification, are permitted provided that the following conditions are met: 00008 00009 - Redistributions of source code must retain the above copyright notice, 00010 this list of conditions and the following disclaimer. 00011 - Redistributions in binary form must reproduce the above copyright 00012 notice, this list of conditions and the following disclaimer in the 00013 documentation and/or other materials provided with the distribution. 00014 - Neither the name of Cornell University nor the names of its 00015 contributors may be used to endorse or promote products derived from 00016 this software without specific prior written permission. 00017 00018 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 00019 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 00020 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 00021 ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 00022 LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 00023 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 00024 SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 00025 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 00026 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 00027 ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF 00028 THE POSSIBILITY OF SUCH DAMAGE. 00029 00030 */ 00031 00032 00033 ///////////////////////////////////////////////////////////////////// 00034 /// 00035 /// Bitmap64.h 00036 /// 00037 ///////////////////////////////////////////////////////////////////// 00038 #ifndef __Bitmap64_H__ 00039 #define __Bitmap64_H__ 00040 00041 #include <assert.h> 00042 #include <memory.h> 00043 #include "Tables.h" 00044 00045 ///////////////////////////////////////////////////////////////////// 00046 /// @addtogroup BitmapProcessingGroup Bitmap Processing 00047 /** @{ */ 00048 00049 ///////////////////////////////////////////////////////////////////// 00050 /// A vertical representation of the data. It handles both uncompressed 00051 /// and compressed data. 00052 /// <p> 00053 /// This bitmap can represent customers with up to 64 transactions since it 00054 /// allocates exactly 64 bits per customer 00055 ///////////////////////////////////////////////////////////////////// 00056 class Bitmap64 00057 { 00058 friend class SeqBitmap; 00059 00060 public: 00061 00062 static void Init(); 00063 static void Destroy(); 00064 00065 static int CalcSize (int numCust) 00066 { 00067 return 2 * numCust * SIZE_UINT; 00068 } 00069 00070 ///////////////////////////////////////////////////////////////////// 00071 /// Allocate the memory for Bitmap64 for this many customers 00072 /// 00073 /// @param numCustomers # of customers 00074 /// @param memory 00075 ///////////////////////////////////////////////////////////////////// 00076 Bitmap64(int numCustomers, unsigned int *&memory) 00077 { 00078 _numCust = numCustomers; 00079 _memSizeInt = 2 * _numCust; 00080 _memSizeShort = _memSizeInt * SHORT_PER_INT; 00081 //_memory = new unsigned int[_memSizeInt]; 00082 _memory = memory; 00083 memory += _memSizeInt * SIZE_UINT; 00084 memset(_memory, 0, _memSizeInt * SIZE_UINT); 00085 }; 00086 00087 ///////////////////////////////////////////////////////////////////// 00088 /// Copy constructor 00089 /// 00090 /// @param b Bitmap64 to copy 00091 /// @param memory 00092 ///////////////////////////////////////////////////////////////////// 00093 Bitmap64(Bitmap64 &b, unsigned int *&memory) 00094 { 00095 // copy information from the source bitmap 00096 _memSizeInt = b._memSizeInt; 00097 _memSizeShort = b._memSizeShort; 00098 _numCust = b._numCust; 00099 //_memory = new unsigned int [b._memSizeInt]; 00100 _memory = memory; 00101 memory += _memSizeInt * SIZE_UINT; 00102 memcpy(_memory, b._memory, _memSizeInt * SIZE_UINT); 00103 }; 00104 00105 ///////////////////////////////////////////////////////////////////// 00106 /// Destructor (does nothing) 00107 ///////////////////////////////////////////////////////////////////// 00108 ~Bitmap64() 00109 { 00110 //if (_memory) 00111 // delete [] _memory; 00112 }; 00113 00114 ///////////////////////////////////////////////////////////////////// 00115 /// Pop this bitmap's memory from the global stack (allocation is done in 00116 /// the constructor, but deallocation is not done in the destructor 00117 ///////////////////////////////////////////////////////////////////// 00118 void Deallocate(unsigned int *&memory) 00119 { 00120 memory -= (_memSizeInt * SIZE_UINT); 00121 }; 00122 00123 ///////////////////////////////////////////////////////////////////// 00124 /// Fill in a 1 in a certain position 00125 /// 00126 /// @param j bit position in Bitmap to be changed 00127 ///////////////////////////////////////////////////////////////////// 00128 void FillEmptyPosition(int j) 00129 { 00130 // Locate correct int in the Bitmap 00131 int i = j / BITS_PER_INT ; 00132 00133 // switch on correct bit 00134 _memory[i] = _memory[i] | Bit32Table[(j % BITS_PER_INT )]; 00135 }; 00136 00137 00138 // --- anding and oring two bitmap64s 00139 void Or(const Bitmap64 &b1, const Bitmap64 &b2); 00140 void And(const Bitmap64 &b1, const Bitmap64 &b2); 00141 00142 // count the number of customers 00143 int Count(); 00144 void CreateSBitmap(const Bitmap64 &iBitmap); 00145 void CreateCBitmap(const Bitmap64 &iBitmap); 00146 00147 // ----------------------- static variables ---------------------- 00148 // counters for performance measurements 00149 static int _countOr; 00150 static int _countAnd; 00151 static int _countCount; 00152 static int _countCreateSBitmap; 00153 static int _countCreateCBitmap; 00154 00155 /// lookup table for counting 00156 static const int _lookupTableSize; 00157 00158 /// lookup table for creating a s-bitmap from an i-bitmap 00159 static int* _sBitmapLookupTable; 00160 00161 /// lookup table for creating a c-bitmap for compression 00162 static int* _cBitmapLookupTable; 00163 00164 int getIntSize() const 00165 { 00166 return _memSizeInt; 00167 } 00168 00169 private: 00170 // --- private variables 00171 unsigned int* _memory; ///< where data is stored 00172 int _memSizeInt; ///< size of memory allocated in sizeof(int) 00173 int _memSizeShort; ///< size of memory allocated in sizeof(short) 00174 int _numCust; ///< number of customers 00175 00176 00177 } 00178 ; // class Bitmap64 00179 00180 /** @} */ 00181 #endif