19 /**

    20     Removes trailing dots from aName.

    21     @return new string descriptor that may have its length adjusted

    22 */

    23 TPtrC RemoveTrailingDots(const TDesC& aName)

    24 {

    25     TInt len = aName.Length();

    26     

    27     while(len > 0)

    28     {

    29         if(aName[len-1] == '.')

    30             len--;

    31         else

    32             break;

    33     }

    34 

    35     TPtrC ptrNoDots(aName.Ptr(), len);

    36     return ptrNoDots;

    37 }

    38 

    39 

    40 TUint32 Log2(TUint32 aVal)

    41 {

    42     return Log2_inline(aVal);

    43 }

    44 

   198 //-----------------------------------------------------------------------------

   199 

   200 const TUint32 K_FFFF = 0xFFFFFFFF; //-- all one bits, beware rigth shifts of signed integers!

   201 

   202 

   203 RBitVector::RBitVector()

   204           :iNumBits(0), ipData(NULL), iNumWords(0)

   205     {

   206     }

   207 

   208 

   209 RBitVector::~RBitVector()

   210     {

   211     Close();

   212     }

   213 

   214 /**

   215     Panics.

   216     @param aPanicCode   a panic code

   217 */

   218 void RBitVector::Panic(TPanicCode aPanicCode) const

   219     {

   220     _LIT(KPanicCat,"RBitVector");

   221     User::Panic(KPanicCat, aPanicCode);

   222     }

   223 

   224 /** explicitly closes the object and deallocates memory */

   225 void RBitVector::Close()

   226     {

   227     iNumBits = 0;

   228     iNumWords =0;

   229     User::Free(ipData);

   230     ipData = NULL;

   231     }

   232 

   233 //-----------------------------------------------------------------------------

   234 

   235 /**

   236     Comparison perator.

   237     @param  aRhs a vector to compate with.

   238     @panic ESizeMismatch in the case of different vector sizes

   239 */

   240 TBool RBitVector::operator==(const RBitVector& aRhs) const

   241     {

   242     __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));

   243     __ASSERT_ALWAYS(iNumBits == aRhs.iNumBits, Panic(ESizeMismatch));

   244 

   245 

   246     if(!iNumBits)

   247         return ETrue; //-- comparing 0-lenght arrays

   248 

   249     if(this == &aRhs)

   250         return ETrue; //-- comparing with itself

   251 

   252     if(iNumWords >= 1)

   253         {

   254         const TUint32 cntBytes = (iNumBits >> 5) << 2; //-- bytes to compare

   255         if(memcompare((const TUint8*)ipData, cntBytes, (const TUint8*)aRhs.ipData, cntBytes))

   256             return EFalse;

   257         }

   258 

   259     const TUint32 bitsRest  = iNumBits & 0x1F;

   260     if(bitsRest)

   261         {

   262         const TUint32 mask = K_FFFF >> (32-bitsRest);

   263         return ( (ipData[iNumWords-1] & mask) == (aRhs.ipData[iNumWords-1] & mask) );

   264         }

   265     

   266     return ETrue;

   267     }

   268 

   269 TBool RBitVector::operator!=(const RBitVector& aRhs) const  

   270     {

   271     return ! ((*this) == aRhs);

   272     } 

   273 

   274 //-----------------------------------------------------------------------------

   275 

   276 /** The same as Create(), but leaves on error */

   277 void RBitVector::CreateL(TUint32 aNumBits)

   278     {

   279     User::LeaveIfError(Create(aNumBits));

   280     }

   281 

   282 

   283 /**

   284     Create the vector with the size of aNumBits bits.

   285     @return system-wide error codes:

   286         KErrNoMemory    unable to allocate sufficient amount of memory for the array

   287         KErrInUse       an attempt to call Create() for non-empty vector. Close it first.

   288         KErrArgument    invalid aNumBits value == 0

   289 */

   290 TInt RBitVector::Create(TUint32 aNumBits)

   291     {

   292 

   293     if(ipData)

   294         return KErrInUse; //-- array is already in use. Close it first.

   295 

   296     if(!aNumBits)

   297         return KErrArgument;

   298 

   299     //-- memory is allocated by word (32 bit) quiantities

   300     const TUint32 numWords = (aNumBits >> 5) + ((aNumBits & 0x1F) > 0 ? 1:0);

   301     ipData = (TUint32*)User::AllocZ(numWords << 2);

   302 

   303     if(!ipData)

   304         return KErrNoMemory;

   305 

   306     iNumBits  = aNumBits;

   307     iNumWords = numWords;

   308 

   309     return KErrNone;

   310     }

   311 

   312 

   313 /**

   314     Fill a bit vector with a given bit value

   315     @param aVal a bit value

   316 */

   317 void RBitVector::Fill(TBool aVal)

   318     {

   319     __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));

   320     memset(ipData, (aVal ? 0xFF : 0x00), iNumWords << 2);

   321     }

   322 

   323 /** Invert all bits in a bit vector */

   324 void RBitVector::Invert()

   325 {

   326     __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));

   327     for(TUint32 i=0; i<iNumWords; ++i)

   328         ipData[i] ^= K_FFFF;

   329 }

   330 

   331 

   332 /**

   333     Perform "And" operation between 2 vectors. They shall be the same size.

   334     @param  aRhs a vector from the right hand side

   335     @panic ESizeMismatch in the case of different vector sizes

   336 */

   337 void RBitVector::And(const RBitVector& aRhs)

   338     {

   339     __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));

   340     __ASSERT_ALWAYS(iNumBits == aRhs.iNumBits, Panic(ESizeMismatch));

   341     for(TUint32 i=0; i<iNumWords; ++i)

   342         {

   343         ipData[i] &= aRhs.ipData[i];

   344         }

   345     }

   346 

   347 /**

   348     Perform "Or" operation between 2 vectors. They shall be the same size.    

   349     @param  aRhs a vector from the right hand side

   350     @panic ESizeMismatch in the case of different vector sizes

   351 */

   352 void RBitVector::Or(const RBitVector& aRhs)

   353     {

   354     __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));

   355     __ASSERT_ALWAYS(iNumBits == aRhs.iNumBits, Panic(ESizeMismatch));

   356     for(TUint32 i=0; i<iNumWords; ++i)

   357         {

   358         ipData[i] |= aRhs.ipData[i];

   359         }

   360     }

   361 

   362 /**

   363     Perform "Xor" operation between 2 vectors. They shall be the same size.    

   364     @param  aRhs a vector from the right hand side

   365     @panic ESizeMismatch in the case of different vector sizes

   366 */

   367 void RBitVector::Xor(const RBitVector& aRhs)

   368     {

   369     __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));

   370     __ASSERT_ALWAYS(iNumBits == aRhs.iNumBits, Panic(ESizeMismatch));

   371     for(TUint32 i=0; i<iNumWords; ++i)

   372         {

   373         ipData[i] ^= aRhs.ipData[i];

   374         }

   375     }

   376 

   377 //-----------------------------------------------------------------------------

   378 /**

   379     Fill a range from bit number "aIndexFrom" to "aIndexTo" inclusively with the value of aVal

   380     

   381     @param  aIndexFrom  start bit number (inclusive)

   382     @param  aIndexTo    end bit number (inclusive)

   383     @param  aVal        the value to be used to fill the range (0s or 1s)

   384 */

   385 void RBitVector::Fill(TUint32 aIndexFrom, TUint32 aIndexTo, TBool aVal)

   386     {

   387     __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));

   388 

   389     //-- swap indexes if they are not in order

   390     if(aIndexFrom > aIndexTo)

   391         {

   392         const TUint32 tmp = aIndexFrom;

   393         aIndexFrom = aIndexTo;

   394         aIndexTo = tmp;

   395         }

   396 

   397     __ASSERT_ALWAYS((aIndexFrom < iNumBits) && (aIndexTo < iNumBits), Panic(EIndexOutOfRange));

   398 

   399     const TUint32 wordStart = WordNum(aIndexFrom);

   400     const TUint32 wordTo    = WordNum(aIndexTo);

   401 

   402     if(aVal)

   403         {//-- filling a range with '1'

   404         

   405         TUint32 shift = BitInWord(aIndexFrom);

   406         const TUint32 mask1 = (K_FFFF >> shift) << shift;

   407 

   408         TUint32 mask2 = K_FFFF;

   409         shift = 1+BitInWord(aIndexTo);

   410         if(shift < 32)

   411             {

   412             mask2 = ~((mask2 >> shift) << shift);

   413             }

   414 

   415         if(wordTo == wordStart)

   416             {//-- a special case, filling is in the same word

   417             ipData[wordStart] |= (mask1 & mask2);

   418             }

   419         else

   420             {

   421             ipData[wordStart] |= mask1; 

   422             ipData[wordTo]    |= mask2;

   423             

   424             const TUint32 wholeWordsBetween = wordTo - wordStart - 1; //-- whole words that can be bulk filled

   425 

   426             if(wholeWordsBetween)

   427                 memset(ipData+wordStart+1, 0xFF, wholeWordsBetween << 2);

   428                             

   429             }

   430         }

   431     else

   432         {//-- filling a range with '0'

   433         

   434         //-- if you need this functionality, remove the panic and uncomment the code below.

   435 

   436         Panic(ENotImplemented);

   437         

   438         /*

   439         TUint32 shift = BitInWord(aIndexFrom);

   440         const TUint32 mask1 = ~((K_FFFF >> shift) << shift);

   441 

   442         TUint32 mask2 = 0;

   443         shift = 1+BitInWord(aIndexTo);

   444         if(shift < 32)

   445             {

   446             mask2 = ((K_FFFF >> shift) << shift);

   447             }

   448 

   449         if(wordTo == wordStart)

   450             {//-- a special case, filling is in the same word

   451             ipData[wordStart] &= (mask1 | mask2);

   452             }

   453         else

   454             {

   455             ipData[wordStart] &= mask1; 

   456             ipData[wordTo]    &= mask2;

   457             

   458             const TUint32 wholeWordsBetween = wordTo - wordStart - 1; //-- whole words that can be bulk filled

   459 

   460             if(wholeWordsBetween)

   461                 memset(ipData+wordStart+1, 0x00, wholeWordsBetween << 2);

   462                             

   463             }

   464         */

   465         }

   466 

   467     }

   468 

   469 //-----------------------------------------------------------------------------

   470 

   471 /**

   472     Search for a specified bit value ('0' or '1') in the vector from the given position.

   473     @param  aStartPos   zero-based index; from this position the search will start. This position isn't included to the search.

   474                         On return may contain a new position if the specified bit is found in specified direction.

   475     @param  aBitVal     zero or non-zero bit to search.

   476     @param  aDir        Specifies the search direction

   477 

   478     @return ETrue if the specified bit value is found; aStartPos gets updated.

   479             EFalse otherwise.

   480 

   481 */

   482 TBool RBitVector::Find(TUint32& aStartPos, TBool aBitVal, TFindDirection aDir) const

   483     {

   484     __ASSERT_ALWAYS(aStartPos < iNumBits, Panic(EIndexOutOfRange));

   485     ASSERT(iNumWords && ipData);

   486 

   487     switch(aDir)

   488         {

   489         case ERight:    //-- Search from the given position to the right

   490             return FindToRight(aStartPos, aBitVal);

   491 

   492         case ELeft:     //-- Search from the given position to the left (towards lower index)

   493             return FindToLeft(aStartPos, aBitVal);

   494 

   495         case ENearestL: //-- Search for the nearest value in both directions starting from left

   496             return FindNearest(aStartPos, aBitVal, ETrue);

   497 

   498         case ENearestR: //-- Search for the nearest value in both directions starting from right

   499             return FindNearest(aStartPos, aBitVal, EFalse);

   500 

   501         default:

   502             Panic(EWrondFindDirection);

   503             return EFalse;

   504 

   505         };

   506     

   507     }

   508 

   509 //-----------------------------------------------------------------------------

   510 /**

   511     Internal method to look for a given bit value in the right direction.

   512     see TBool RBitVector::Find(...)

   513 */

   514 TBool RBitVector::FindToRight(TUint32& aStartPos, TBool aBitVal) const

   515     {

   516     if(aStartPos >= iNumBits-1)

   517         return EFalse; //-- no way to the right

   518 

   519     const TUint32 startPos = aStartPos+1;

   520     const TUint32 fInvert = aBitVal ? 0 : K_FFFF; //-- invert everything if we are looking for '0' bit

   521 

   522     TUint32 wordNum = WordNum(startPos);

   523     TUint32 val = ipData[wordNum] ^ fInvert;

   524 

   525     if(wordNum == iNumWords-1)

   526         {//-- process the last word in the array, some higher bits might not belong to the bit vector

   527         val = MaskLastWord(val);

   528         }

   529 

   530     const TUint32 shift = BitInWord(startPos);

   531     val = (val >> shift) << shift; //-- mask unused low bits

   532 

   533     if(val)

   534         {//-- there are '1' bits in the current word

   535         goto found;

   536         }

   537     else

   538         {//-- search in higher words

   539         wordNum++;

   540 

   541         while(iNumWords-wordNum > 1)

   542             {

   543             val = ipData[wordNum] ^ fInvert;

   544             if(val)

   545                 goto found;

   546 

   547             wordNum++;

   548             }

   549 

   550         if(wordNum == iNumWords-1)

   551             {//-- process the last word in the array, some higher bith might not belong to the bit vector

   552             val = ipData[wordNum] ^ fInvert;

   553             val = MaskLastWord(val);

   554 

   555             if(val)

   556                 goto found;

   557             }

   558         }

   559 

   560     return EFalse; //-- haven't found anything

   561 

   562   found:

   563 

   564     val &= (~val+1); //-- select rightmost bit

   565     aStartPos = (wordNum << 5)+Log2(val);

   566     return ETrue;

   567     }

   568 

   569 

   570 //-----------------------------------------------------------------------------

   571 

   572 /**

   573     Internal method to look for a given bit value in the left direction.

   574     see TBool RBitVector::Find(...)

   575 */

   576 TBool RBitVector::FindToLeft(TUint32& aStartPos, TBool aBitVal) const

   577 {

   578     if(!aStartPos)

   579         return EFalse; //-- no way to the left

   580     

   581     const TUint32 startPos=aStartPos-1;

   582     const TUint32 fInvert = aBitVal ? 0 : K_FFFF; //-- invert everything if we are looking for '0' bit

   583 

   584     TUint32 wordNum = WordNum(startPos);

   585     TUint32 val = ipData[wordNum] ^ fInvert;

   586 

   587     const TUint32 shift = 31-(BitInWord(startPos));

   588     val = (val << shift) >> shift; //-- mask unused high bits

   589 

   590     if(val)

   591     {//-- there are '1' bits in the current word

   592         goto found;

   593     }

   594     else

   595     {//-- search in the lower words

   596         while(wordNum)

   597         {

   598             wordNum--;

   599             val=ipData[wordNum] ^ fInvert;

   600             if(val)

   601                 goto found;

   602         }

   603     }

   604 

   605     return EFalse; //-- nothing found

   606 

   607  found:

   608     aStartPos = (wordNum << 5)+Log2(val);

   609     return ETrue;

   610 }

   611 

   612 //-----------------------------------------------------------------------------

   613 

   614 /**

   615     Internal method to look for a given bit value in the both directions.

   616     see TBool RBitVector::Find(...)

   617 */

   618 TBool RBitVector::FindNearest(TUint32& aStartPos, TBool aBitVal, TBool aToLeft) const

   619 {

   620     if(iNumBits < 2)

   621         return EFalse;

   622 

   623     if(aStartPos == 0)

   624         return FindToRight(aStartPos, aBitVal);

   625 

   626     if(aStartPos == iNumBits-1)

   627         return FindToLeft(aStartPos, aBitVal);

   628 

   629     

   630     const TUint32 fInvert = aBitVal ? 0 : K_FFFF; //-- invert everything if we are looking for '0' bit

   631     

   632     TUint32 wordNum = WordNum(aStartPos);

   633     TUint32 l_Idx; //-- index of the word to the left

   634     TUint32 r_Idx; //-- index of the word to the right

   635     

   636     l_Idx = r_Idx = wordNum;

   637 

   638     TBool   noWayLeft  = (wordNum == 0);            //-- if we are in the first word

   639     TBool   noWayRight = (wordNum == iNumWords-1);  //-- if we are in the last word

   640 

   641     //-- look in the current word first

   642     TUint32 val = ipData[wordNum] ^ fInvert;

   643     

   644     if(noWayRight)

   645     {   //-- this is the last word in the array, mask unused high bits in the last word

   646         val = MaskLastWord(val);

   647     }

   648 

   649     const TUint32 bitPos = aStartPos & 0x1F;

   650     val &= ~(1<<bitPos); //-- mask the bit at current position

   651     

   652     if(val == 0)

   653     {//-- no '1' bits in the current word

   654         noWayLeft  = ItrLeft(l_Idx);

   655         noWayRight = ItrRight(r_Idx);

   656     }

   657     else if(bitPos == 0)

   658     {

   659         noWayLeft = ItrLeft(l_Idx); //-- move to the previous word

   660     }

   661     else if(bitPos == 31)

   662     {

   663         noWayRight = ItrRight(r_Idx); //-- move to the next word

   664     }

   665     else

   666     {//-- look in the current word, in both halves to the left and right from the start position

   667         

   668         const TUint32 shift1 = 32-bitPos;

   669         const TUint32 partLo = (val << shift1) >> shift1; //-- towards lower bits

   670 

   671         const TUint32 shift2 = bitPos+1;

   672         const TUint32 partHi = (val >> shift2) << shift2; //-- towards higher bits 

   673         

   674 

   675         if(partLo && !partHi) //-- only lower part has '1' bits   

   676         {

   677             aStartPos = (wordNum << 5)+Log2(partLo);

   678             return ETrue;

   679         }

   680         else if(!partLo && partHi) //-- only higher part has '1' bits

   681         {

   682             aStartPos = (wordNum << 5)+Log2( (partHi & (~partHi+1)) );

   683             return ETrue;

   684         }

   685         else if(partLo && partHi) //-- both parts contain '1' bits, select the nearest one

   686         {

   687             const TUint32 posL = (wordNum << 5)+Log2(partLo);

   688             const TUint32 posR = (wordNum << 5)+Log2( (partHi & (~partHi+1)) );

   689         

   690             ASSERT(aStartPos > posL);

   691             ASSERT(posR > aStartPos);

   692             const TUint32 distL = aStartPos-posL;

   693             const TUint32 distR = posR-aStartPos;

   694 

   695             if(distL < distR)

   696             {

   697                 aStartPos = posL;

   698                 return ETrue;

   699             }

   700             else if(distL > distR)

   701             {

   702                 aStartPos = posR;

   703                 return ETrue;

   704             }

   705             else

   706             {//-- distL == distR, take into account search priority

   707                 aStartPos = aToLeft ? posL : posR;

   708                 return ETrue;

   709             }

   710         }

   711         else //-- (!partLo && !partHi), nothing in the current word

   712         {

   713             ASSERT(0);

   714         }

   715 

   716     }// if(bitPos > 0 && bitPos < 31)

   717 

   718     //-- now we are processing separate words from both sides of the search position

   719     for(;;)

   720     { 

   721         TUint32 wL = ipData[l_Idx] ^ fInvert;

   722         TUint32 wR = ipData[r_Idx] ^ fInvert;

   723         if(r_Idx == iNumWords-1)

   724         {   //-- this is the last word in the array, mask unused high bits in the last word

   725             wR = MaskLastWord(wR);

   726         }

   727 

   728         if(wL && !wR)

   729         {

   730             aStartPos = (l_Idx << 5)+Log2(wL);

   731             return ETrue;

   732         }

   733         else if(!wL && wR)

   734         {

   735             aStartPos = (r_Idx << 5)+Log2( (wR & (~wR+1)) );

   736             return ETrue;

   737         }

   738         else if(wL && wR)

   739         {

   740             const TUint32 posL = (l_Idx << 5)+Log2(wL);

   741             const TUint32 posR = (r_Idx << 5)+Log2( (wR & (~wR+1)) );

   742         

   743             ASSERT(aStartPos > posL);

   744             ASSERT(posR > aStartPos);

   745             const TUint32 distL = aStartPos-posL;

   746             const TUint32 distR = posR-aStartPos;

   747 

   748             if(distL < distR)

   749             {

   750                 aStartPos = posL;

   751                 return ETrue;

   752             }

   753             else if(distL > distR)

   754             {

   755                 aStartPos = posR;

   756                 return ETrue;

   757             }

   758             else

   759             {//-- distL == distR, take into account search priority

   760                 aStartPos = aToLeft ? posL : posR;

   761                 return ETrue;

   762             }

   763 

   764         }//else if(wL && wR)

   765 

   766 

   767         if(noWayLeft)

   768         {

   769             aStartPos = r_Idx << 5;

   770             return FindToRight(aStartPos, aBitVal);

   771         }

   772         else

   773         {

   774             noWayLeft  = ItrLeft(l_Idx);

   775         }

   776 

   777         if(noWayRight)

   778         {

   779             aStartPos = l_Idx << 5;

   780             return FindToLeft(aStartPos, aBitVal);

   781         }

   782         else

   783         {    

   784             noWayRight = ItrRight(r_Idx);

   785         }

   786 

   787    }//for(;;)

   788 

   789     //return EFalse;

   790 }

   791 

   792 //-----------------------------------------------------------------------------

   793 /**

   794     Find out if two vectors are different.

   795 

   796     @param  aRhs        vector to compare with

   797     @param  aDiffIndex  if there is a differene, here will be the number of the first different bit

   798     @return ETrue if vectors differ, EFalse, if they are identical.

   799 */

   800 TBool RBitVector::Diff(const RBitVector& aRhs, TUint32& aDiffIndex) const

   801 {

   802     __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));

   803     __ASSERT_ALWAYS(iNumBits == aRhs.iNumBits, Panic(ESizeMismatch));

   804     ASSERT(iNumWords > 0);

   805 

   806     TUint32 diffWord=0;

   807     TUint32 wordNum=0;

   808 

   809     //-- compare all but the last word in the array

   810     for(wordNum=0; wordNum < iNumWords-1; ++wordNum)

   811     {

   812         diffWord = ipData[wordNum] ^ aRhs.ipData[wordNum];

   813         if(diffWord)

   814             break;  //-- found difference

   815     }

   816 

   817     //-- process the last word in the array

   818     if(!diffWord)

   819     {

   820         diffWord = MaskLastWord(ipData[wordNum]) ^ MaskLastWord(aRhs.ipData[wordNum]);

   821     }

   822 

   823     if(!diffWord)

   824         return EFalse; //-- vectors are the same

   825 

   826     //-- calculate the position of the bit that different.

   827     diffWord &= (~diffWord+1); //-- select rightmost bit

   828     aDiffIndex = (wordNum << 5)+Log2(diffWord);

   829     

   830     return ETrue;

   831 }

   832 //-----------------------------------------------------------------------------

   833 

   834 /**

   835     Iterate to the left (towards lower index) in the array of words ipData

   836 

   837     @param  aIdx index within ipData array to be decremented; if it's possible to move left, it will be decreased

   838     @return ETrue if there is no way left i.e. aIdx is 0. EFalse otherwise and aIdx decreased.

   839 */

   840 TBool RBitVector::ItrLeft(TUint32& aIdx) const

   841 {

   842     if(aIdx == 0)

   843         return ETrue;

   844     else

   845     {

   846         aIdx--;

   847         return EFalse;

   848     }

   849 }

   850 

   851 

   852 /**

   853     Iterate to the right (towards higher index) in the array of words ipData

   854 

   855     @param  aIdx index within ipData array to be incremented; if it's possible to move right, it will be increased

   856     @return ETrue if there is no way right i.e. aIdx corresponds to the last word. EFalse otherwise and aIdx increased.

   857 */

   858 TBool RBitVector::ItrRight(TUint32& aIdx) const

   859 {

   860     if(aIdx < iNumWords-1)

   861     {

   862         aIdx++;

   863         return EFalse;

   864     }

   865     else

   866         return ETrue;

   867 }

   873 

   874 

   875