1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/kernelhwsrv/userlibandfileserver/fileserver/fs_utils/bit_vector.h Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,251 @@
1.4 +// Copyright (c) 1995-2009 Nokia Corporation and/or its subsidiary(-ies).
1.5 +// All rights reserved.
1.6 +// This component and the accompanying materials are made available
1.7 +// under the terms of the License "Eclipse Public License v1.0"
1.8 +// which accompanies this distribution, and is available
1.9 +// at the URL "http://www.eclipse.org/legal/epl-v10.html".
1.10 +//
1.11 +// Initial Contributors:
1.12 +// Nokia Corporation - initial contribution.
1.13 +//
1.14 +// Contributors:
1.15 +//
1.16 +// Description:
1.17 +//
1.18 +// Collection of common constants, utility functions, etc. for the file server and file systems.
1.19 +// Definitions here must be filesystem-agnostic, i.e. generic enougs to be used by every file system
1.20 +//
1.21 +// This is the internal file and must not be exported.
1.22 +
1.23 +/**
1.24 + @file
1.25 + @internalTechnology
1.26 +*/
1.27 +
1.28 +#if !defined(__FILESYSTEM_UTILS_BIT_VECTOR__)
1.29 +#define __FILESYSTEM_UTILS_BIT_VECTOR__
1.30 +
1.31 +#if !defined(__FILESYSTEM_UTILS_H__)
1.32 +#include "filesystem_utils.h"
1.33 +#endif
1.34 +
1.35 +
1.36 +//#######################################################################################################################################
1.37 +
1.38 +/**
1.39 + This class represents a bit vector i.e. an array of bits. Vector size can be from 1 to 2^32 bits.
1.40 + This class can be created on a stack (but needs to be placed into cleanup stack) or in a heap with the help of its factory methods Create/CreateL
1.41 +*/
1.42 +class RBitVector
1.43 + {
1.44 + public:
1.45 +
1.46 + RBitVector(); //-- Creates an empty vector. see Create() methods for memory allocation
1.47 + ~RBitVector();
1.48 +
1.49 + void Close();
1.50 +
1.51 + TInt Create(TUint32 aNumBits);
1.52 + void CreateL(TUint32 aNumBits);
1.53 +
1.54 + inline TUint32 Size() const;
1.55 +
1.56 + //-- single bit manipulation methods
1.57 + inline TBool operator[](TUint32 aIndex) const;
1.58 + inline void SetBit(TUint32 aIndex);
1.59 + inline void ResetBit(TUint32 aIndex);
1.60 + inline void InvertBit(TUint32 aIndex);
1.61 + inline void SetBitVal(TUint32 aIndex, TBool aVal);
1.62 +
1.63 + void Fill(TBool aVal);
1.64 + void Fill(TUint32 aIndexFrom, TUint32 aIndexTo, TBool aVal);
1.65 +
1.66 + void Invert();
1.67 +
1.68 + TBool operator==(const RBitVector& aRhs) const;
1.69 + TBool operator!=(const RBitVector& aRhs) const;
1.70 +
1.71 + //-- logical operations between 2 vectors.
1.72 + void And(const RBitVector& aRhs);
1.73 + void Or (const RBitVector& aRhs);
1.74 + void Xor(const RBitVector& aRhs);
1.75 +
1.76 + TBool Diff(const RBitVector& aRhs, TUint32& aDiffIndex) const;
1.77 +
1.78 + TUint32 Num1Bits() const;
1.79 + TUint32 Num1Bits(TUint32 aIndexFrom, TUint32 aIndexTo) const;
1.80 +
1.81 + TUint32 Num0Bits() const;
1.82 +
1.83 +
1.84 + /** Bit search specifiers */
1.85 + enum TFindDirection
1.86 + {
1.87 + ELeft, ///< Search from the given position to the left (towards lower index)
1.88 + ERight, ///< Search from the given position to the right (towards higher index)
1.89 + ENearestL, ///< Search in both directions starting from the given position; in the case of the equal distances return the position to the left
1.90 + ENearestR ///< Search in both directions starting from the given position; in the case of the equal distances return the position to the right
1.91 +
1.92 + //-- N.B the current position the search starts with isn't included to the search.
1.93 + };
1.94 +
1.95 + TBool Find(TUint32& aStartPos, TBool aBitVal, TFindDirection aDir) const;
1.96 +
1.97 + /** panic codes */
1.98 + enum TPanicCode
1.99 + {
1.100 + EIndexOutOfRange, ///< index out of range
1.101 + EWrondFindDirection, ///< a value doesn't belong to TFindDirection
1.102 + ESizeMismatch, ///< Size mismatch for binary operators
1.103 + ENotInitialised, ///< No memory allocated for the array
1.104 + ENotImplemented, ///< functionality isn't implemented
1.105 +
1.106 + EDataAlignment, ///< wrong data alignment when importing / exporting raw data
1.107 + };
1.108 +
1.109 + protected:
1.110 +
1.111 + //-- these are outlawed. Can't use them because memory allocator can leave and we don't have conthrol on it in these methods.
1.112 + RBitVector(const RBitVector& aRhs);
1.113 + RBitVector& operator=(const RBitVector& aRhs);
1.114 +
1.115 + void* operator new(TUint); //-- disable creating objects on heap.
1.116 + void* operator new(TUint, void*);
1.117 + //-------------------------------------
1.118 +
1.119 +
1.120 + void Panic(TPanicCode aPanicCode) const;
1.121 +
1.122 + inline TUint32 WordNum(TUint32 aBitPos) const;
1.123 + inline TUint32 BitInWord(TUint32 aBitPos) const;
1.124 +
1.125 + protected:
1.126 + //-- special interface to acecess raw internal data. It's protected. Derive appropriate class from this one if you wan to use it
1.127 + void DoImportData(TUint32 aStartBit, TUint32 aNumBits, const TAny* apData);
1.128 + void DoExportData(TUint32 aStartBit, TUint32 aNumBits, TDes8& aData) const;
1.129 +
1.130 +
1.131 + private:
1.132 + TBool FindToRight(TUint32& aStartPos, TBool aBitVal) const;
1.133 + TBool FindToLeft (TUint32& aStartPos, TBool aBitVal) const;
1.134 + TBool FindNearest(TUint32& aStartPos, TBool aBitVal, TBool aToLeft) const;
1.135 +
1.136 + inline TUint32 MaskLastWord(TUint32 aVal) const;
1.137 + inline TBool ItrLeft(TUint32& aIdx) const;
1.138 + inline TBool ItrRight(TUint32& aIdx) const;
1.139 +
1.140 +
1.141 + protected:
1.142 +
1.143 + TUint32 iNumBits; ///< number of bits in the vector
1.144 + TUint32* ipData; ///< pointer to the data
1.145 + TUint32 iNumWords;///< number of 32-bit words that store bits
1.146 + };
1.147 +
1.148 +
1.149 +//#######################################################################################################################################
1.150 +//# inline functions area
1.151 +//#######################################################################################################################################
1.152 +
1.153 +
1.154 +//---------------------------------------------------------------------------------------------------------------------------------
1.155 +//-- class RBitVector
1.156 +
1.157 +/** @return size of the vector (number of bits) */
1.158 +inline TUint32 RBitVector::Size() const
1.159 + {
1.160 + return iNumBits;
1.161 + }
1.162 +
1.163 +/**
1.164 + Get a bit by index
1.165 +
1.166 + @param aIndex index in a bit vector
1.167 + @return 0 if the bit at pos aIndex is 0, not zero otherwise
1.168 + @panic EIndexOutOfRange if aIndex is out of range
1.169 +*/
1.170 +inline TBool RBitVector::operator[](TUint32 aIndex) const
1.171 + {
1.172 + __ASSERT_ALWAYS(aIndex < iNumBits, Panic(EIndexOutOfRange));
1.173 + return (ipData[WordNum(aIndex)] & (1<<BitInWord(aIndex)));
1.174 + }
1.175 +
1.176 +/**
1.177 + Set a bit at pos aIndex to '1'
1.178 + @param aIndex index in a bit vector
1.179 + @panic EIndexOutOfRange if aIndex is out of range
1.180 +*/
1.181 +inline void RBitVector::SetBit(TUint32 aIndex)
1.182 + {
1.183 + __ASSERT_ALWAYS(aIndex < iNumBits, Panic(EIndexOutOfRange));
1.184 + ipData[WordNum(aIndex)] |= (1<<BitInWord(aIndex));
1.185 + }
1.186 +
1.187 +/**
1.188 + Set a bit at pos aIndex to '0'
1.189 + @param aIndex index in a bit vector
1.190 + @panic EIndexOutOfRange if aIndex is out of range
1.191 +*/
1.192 +inline void RBitVector::ResetBit(TUint32 aIndex)
1.193 + {
1.194 + __ASSERT_ALWAYS(aIndex < iNumBits, Panic(EIndexOutOfRange));
1.195 + ipData[WordNum(aIndex)] &= ~(1<<BitInWord(aIndex));
1.196 + }
1.197 +
1.198 +/**
1.199 + Invert a bit at pos aIndex
1.200 + @param aIndex index in a bit vector
1.201 + @panic EIndexOutOfRange if aIndex is out of range
1.202 +*/
1.203 +inline void RBitVector::InvertBit(TUint32 aIndex)
1.204 + {
1.205 + __ASSERT_ALWAYS(aIndex < iNumBits, Panic(EIndexOutOfRange));
1.206 + ipData[WordNum(aIndex)] ^= (1<<BitInWord(aIndex));
1.207 + }
1.208 +
1.209 +/**
1.210 + Set bit value at position aIndex
1.211 + @param aIndex index in a bit vector
1.212 + @panic EIndexOutOfRange if aIndex is out of range
1.213 +*/
1.214 +inline void RBitVector::SetBitVal(TUint32 aIndex, TBool aVal)
1.215 + {
1.216 + if(aVal)
1.217 + SetBit(aIndex);
1.218 + else
1.219 + ResetBit(aIndex);
1.220 + }
1.221 +
1.222 +
1.223 +inline TUint32 RBitVector::MaskLastWord(TUint32 aVal) const
1.224 + {
1.225 + const TUint32 shift = (32-(iNumBits & 0x1F)) & 0x1F;
1.226 + return (aVal << shift) >> shift; //-- mask unused high bits
1.227 + }
1.228 +
1.229 +inline TUint32 RBitVector::WordNum(TUint32 aBitPos) const
1.230 + {
1.231 + return aBitPos >> 5;
1.232 + }
1.233 +
1.234 +inline TUint32 RBitVector::BitInWord(TUint32 aBitPos) const
1.235 + {
1.236 + return aBitPos & 0x1F;
1.237 + }
1.238 +
1.239 +
1.240 +
1.241 +#endif //__FILESYSTEM_UTILS_BIT_VECTOR__
1.242 +
1.243 +
1.244 +
1.245 +
1.246 +
1.247 +
1.248 +
1.249 +
1.250 +
1.251 +
1.252 +
1.253 +
1.254 +