1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/kernelhwsrv/kerneltest/e32test/buffer/bin_srch.cpp Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,293 @@
1.4 +// Copyright (c) 1994-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 +// e32test\buffer\bin_srch.cpp
1.18 +//
1.19 +//
1.20 +
1.21 +#include <e32test.h>
1.22 +#include <e32math.h>
1.23 +
1.24 +GLREF_D RTest test;
1.25 +
1.26 +#define KEEP_RUNNING 100
1.27 +
1.28 +struct TestMe
1.29 + {
1.30 + TBuf<0x10> name;
1.31 + TInt32 key1;
1.32 + TUint32 key2;
1.33 + };
1.34 +
1.35 +LOCAL_C void fillArray(RArray<TestMe>& arr, TInt size)
1.36 + {
1.37 + TInt32 seed = 1 + Math::Random() % size;
1.38 + TestMe testMe;
1.39 + for(TInt i=0;i<size;i++)
1.40 + {
1.41 + testMe.key1 = seed;
1.42 + arr.Append(testMe);
1.43 + seed += 2 + Math::Random() % (2 + size%5);
1.44 + }
1.45 +
1.46 + }
1.47 +
1.48 +LOCAL_C void fillArray(RArray<TInt32>& arr, TInt size)
1.49 + {
1.50 + TInt32 seed = 1 + Math::Random() % size;
1.51 + for(TInt i=0;i<size;i++)
1.52 + {
1.53 + arr.Append(seed);
1.54 + seed += 2 + Math::Random() % (2 + size%5);
1.55 + }
1.56 + }
1.57 +
1.58 +LOCAL_C void fillArray(RArray<TInt32>& arr, RPointerArray<TUint32>& parr, TInt size)
1.59 + {
1.60 + TInt32 seed = 1 + Math::Random() % size;
1.61 + TInt i;
1.62 + for(i=0;i<size;i++)
1.63 + {
1.64 + arr.Append(seed);
1.65 + seed += 2 + Math::Random() % (2 + size%5);
1.66 + }
1.67 + for(i=0;i<size;i++)
1.68 + {
1.69 + parr.Append((const TUint32*)&arr[i]);
1.70 + }
1.71 + }
1.72 +
1.73 +LOCAL_C void fillArray(RPointerArray<TUint32>& arr, TInt size)
1.74 + {
1.75 + TUint32 seed = 1 + Math::Random() % size;
1.76 + TUint32 dummy;
1.77 + for(TInt i=0;i<size;i++)
1.78 + {
1.79 + arr.Append((&dummy) + seed);
1.80 + seed += 2 + Math::Random() % (2 + size%5);
1.81 + }
1.82 + }
1.83 +
1.84 +LOCAL_C TInt simpleOrder(const TInt32& a1, const TInt32& a2)
1.85 + {
1.86 + return a1 - a2;
1.87 + }
1.88 +
1.89 +LOCAL_C TInt simpleOrder2(const TUint32& a1, const TUint32& a2)
1.90 + {
1.91 + return (a1==a2)?0:(a1>a2?1:-1);
1.92 + }
1.93 +
1.94 +GLDEF_C void DoRArrayTests()
1.95 + {
1.96 + {
1.97 + RArray<TInt32>* rArr1 = new RArray<TInt32>(0x10);
1.98 + test(rArr1!=NULL);
1.99 + RPointerArray<TUint32>* rpArr1 = new RPointerArray<TUint32>(0x10);
1.100 + test(rpArr1!=NULL);
1.101 + TInt i;
1.102 + TInt size = 25;
1.103 + test.Next(_L("Testing RArray::FindInOrder, RPointerArray::FindInOrder, RArrayBase::BinarySearch and RPointerArrayBase::BinarySearch with arrays of different sizes\r\n"));
1.104 + for(i=0;i<KEEP_RUNNING;i++)
1.105 + {
1.106 + test.Printf(_L("Testing with a random array of size %d \r\n"), size);
1.107 + fillArray(*rArr1,*rpArr1,size);
1.108 + test(rArr1->Count()==rpArr1->Count());
1.109 + TInt index;
1.110 + //test(KErrNotFound==rArr1->BinarySearch((TAny*)(rArr1->operator[](0)-1),index,(TGeneralLinearOrder)simpleOrder));
1.111 + test(KErrNotFound==rArr1->FindInOrder(rArr1->operator[](0)-1,index,TLinearOrder<TInt32>(simpleOrder)));
1.112 + test(index==0);
1.113 + TUint32 t = *rpArr1->operator[](0)-1;
1.114 + test(KErrNotFound==rpArr1->FindInOrder(&t,index,TLinearOrder<TUint32>(simpleOrder2)));
1.115 + test(index==0);
1.116 + for(TInt k=0;k<rArr1->Count();k++)
1.117 + {
1.118 + test(KErrNone==rArr1->FindInOrder(rArr1->operator[](k),index,TLinearOrder<TInt32>(simpleOrder)));
1.119 + test(index==k);
1.120 + test(KErrNone==rpArr1->FindInOrder(rpArr1->operator[](k),index,TLinearOrder<TUint32>(simpleOrder2)));
1.121 + test(index==k);
1.122 + if(k<rArr1->Count()-1)
1.123 + {
1.124 + test(KErrNotFound==rArr1->FindInOrder((rArr1->operator[](k)+rArr1->operator[](k+1))>>1,index,TLinearOrder<TInt32>(simpleOrder)));
1.125 + test(index==k+1);
1.126 + t = (*rpArr1->operator[](k)+*rpArr1->operator[](k+1))>>1;
1.127 + test(KErrNotFound==rpArr1->FindInOrder(&t,index,TLinearOrder<TUint32>(simpleOrder2)));
1.128 + test(index==k+1);
1.129 + }
1.130 + }
1.131 + test(KErrNotFound==rArr1->FindInOrder(rArr1->operator[](rArr1->Count()-1)+5,index,TLinearOrder<TInt32>(simpleOrder)));
1.132 + test(index==rArr1->Count());
1.133 + t = *rpArr1->operator[](rpArr1->Count()-1) + 5;
1.134 + test(KErrNotFound==rpArr1->FindInOrder(&t,index,TLinearOrder<TUint32>(simpleOrder2)));
1.135 + test(index==rpArr1->Count());
1.136 + size += 2 + Math::Random() % (2 + size%5);
1.137 + rArr1->Reset();
1.138 + rpArr1->Reset();
1.139 + }
1.140 + delete rpArr1;
1.141 +
1.142 + test.Next(_L("Testing RArray::FindInSignedKeyOrder and RArrayBase::BinarySignedSearch with arrays of different sizes\r\n"));
1.143 + for(i=0;i<KEEP_RUNNING;i++)
1.144 + {
1.145 + test.Printf(_L("Testing with a random array of size %d \r\n"), size);
1.146 + fillArray(*rArr1,size);
1.147 + TInt index;
1.148 + //test(KErrNotFound==rArr1->BinarySearch((TAny*)(rArr1->operator[](0)-1),index,(TGeneralLinearOrder)simpleOrder));
1.149 + test(KErrNotFound==rArr1->FindInSignedKeyOrder(rArr1->operator[](0)-1,index));
1.150 + test(index==0);
1.151 + for(TInt k=0;k<rArr1->Count();k++)
1.152 + {
1.153 + test(KErrNone==rArr1->FindInSignedKeyOrder(rArr1->operator[](k),index));
1.154 + test(index==k);
1.155 + if(k<rArr1->Count()-1)
1.156 + {
1.157 + test(KErrNotFound==rArr1->FindInSignedKeyOrder((rArr1->operator[](k)+rArr1->operator[](k+1))>>1,index));
1.158 + test(index==k+1);
1.159 + }
1.160 + }
1.161 + test(KErrNotFound==rArr1->FindInSignedKeyOrder(rArr1->operator[](rArr1->Count()-1)+5,index));
1.162 + test(index==rArr1->Count());
1.163 + size += 2 + Math::Random() % (2 + size%5);
1.164 + rArr1->Reset();
1.165 + }
1.166 +
1.167 + size=25;
1.168 + test.Next(_L("Testing RArray::FindInUnsignedKeyOrder and RArrayBase::BinaryUnsignedSearch with arrays of different sizes\r\n"));
1.169 + for(i=0;i<KEEP_RUNNING;i++)
1.170 + {
1.171 + test.Printf(_L("Testing with a random array of size %d \r\n"), size);
1.172 + fillArray(*rArr1,size);
1.173 + TInt index;
1.174 + //test(KErrNotFound==rArr1->BinarySearch((TAny*)(rArr1->operator[](0)-1),index,(TGeneralLinearOrder)simpleOrder));
1.175 + test(KErrNotFound==rArr1->FindInUnsignedKeyOrder(rArr1->operator[](0)-1,index));
1.176 + test(index==0);
1.177 + for(TInt k=0;k<rArr1->Count();k++)
1.178 + {
1.179 + test(KErrNone==rArr1->FindInUnsignedKeyOrder(rArr1->operator[](k),index));
1.180 + test(index==k);
1.181 + if(k<rArr1->Count()-1)
1.182 + {
1.183 + test(KErrNotFound==rArr1->FindInUnsignedKeyOrder((rArr1->operator[](k)+rArr1->operator[](k+1))>>1,index));
1.184 + test(index==k+1);
1.185 + }
1.186 + }
1.187 + test(KErrNotFound==rArr1->FindInUnsignedKeyOrder(rArr1->operator[](rArr1->Count()-1)+5,index));
1.188 + test(index==rArr1->Count());
1.189 + size += 2 + Math::Random() % (2 + size%5);
1.190 + rArr1->Reset();
1.191 + }
1.192 + delete rArr1;
1.193 + }
1.194 +
1.195 + {
1.196 + RArray<TestMe>* rArr1 = new RArray<TestMe>(0x10,_FOFF(TestMe,key1));
1.197 + test(rArr1!=NULL);
1.198 + TInt i;
1.199 + TInt size = 25;
1.200 + test.Next(_L("Testing RArray::FindInSignedOrder and RArrayBase::BinarySignedSearch with a structure + key\r\n"));
1.201 + TestMe testMe;
1.202 + for(i=0;i<KEEP_RUNNING;i++)
1.203 + {
1.204 + test.Printf(_L("Testing with a random array of size %d \r\n"), size);
1.205 + fillArray(*rArr1,size);
1.206 + TInt index;
1.207 + //test(KErrNotFound==rArr1->BinarySearch((TAny*)(rArr1->operator[](0)-1),index,(TGeneralLinearOrder)simpleOrder));
1.208 + testMe=rArr1->operator[](0);
1.209 + testMe.key1 = rArr1->operator[](0).key1-1;
1.210 + test(KErrNotFound==rArr1->FindInSignedKeyOrder(testMe,index));
1.211 + test(index==0);
1.212 + for(TInt k=0;k<rArr1->Count();k++)
1.213 + {
1.214 + testMe.key1 = rArr1->operator[](k).key1;
1.215 + test(KErrNone==rArr1->FindInSignedKeyOrder(testMe,index));
1.216 + test(index==k);
1.217 + if(k<rArr1->Count()-1)
1.218 + {
1.219 + testMe.key1 = (rArr1->operator[](k).key1+rArr1->operator[](k+1).key1)>>1;
1.220 + test(KErrNotFound==rArr1->FindInSignedKeyOrder(testMe,index));
1.221 + test(index==k+1);
1.222 + }
1.223 + }
1.224 + testMe.key1 = rArr1->operator[](rArr1->Count()-1).key1+5;
1.225 + test(KErrNotFound==rArr1->FindInSignedKeyOrder(testMe,index));
1.226 + test(index==rArr1->Count());
1.227 + size += 2 + Math::Random() % (2 + size%5);
1.228 + rArr1->Reset();
1.229 + }
1.230 +
1.231 + size=25;
1.232 + test.Next(_L("Testing RArray::FindInUnsignedKeyOrder and RArrayBase::BinaryUnsignedSearch with arrays of different sizes\r\n"));
1.233 + for(i=0;i<KEEP_RUNNING;i++)
1.234 + {
1.235 + test.Printf(_L("Testing with a random array of size %d \r\n"), size);
1.236 + fillArray(*rArr1,size);
1.237 + TInt index;
1.238 + //test(KErrNotFound==rArr1->BinarySearch((TAny*)(rArr1->operator[](0)-1),index,(TGeneralLinearOrder)simpleOrder));
1.239 + testMe.key1 = rArr1->operator[](0).key1-1;
1.240 + test(KErrNotFound==rArr1->FindInUnsignedKeyOrder(testMe,index));
1.241 + test(index==0);
1.242 + for(TInt k=0;k<rArr1->Count();k++)
1.243 + {
1.244 + testMe.key1 = rArr1->operator[](k).key1;
1.245 + test(KErrNone==rArr1->FindInUnsignedKeyOrder(testMe,index));
1.246 + test(index==k);
1.247 + if(k<rArr1->Count()-1)
1.248 + {
1.249 + testMe.key1 = (rArr1->operator[](k).key1+rArr1->operator[](k+1).key1)>>1;
1.250 + test(KErrNotFound==rArr1->FindInUnsignedKeyOrder(testMe,index));
1.251 + test(index==k+1);
1.252 + }
1.253 + }
1.254 + testMe.key1 = rArr1->operator[](rArr1->Count()-1).key1+5;
1.255 + test(KErrNotFound==rArr1->FindInUnsignedKeyOrder(testMe,index));
1.256 + test(index==rArr1->Count());
1.257 + size += 2 + Math::Random() % (2 + size%5);
1.258 + rArr1->Reset();
1.259 + }
1.260 + delete rArr1;
1.261 + }
1.262 +
1.263 + {
1.264 + RPointerArray<TUint32>* rArr1 = new RPointerArray<TUint32>(0x10);
1.265 + test(rArr1!=NULL);
1.266 + TInt i;
1.267 + TInt size = 25;
1.268 + test.Next(_L("Testing RPointerArray::FindInAddressOrder and RPointerArrayBase::BinaryUnsignedSearch with arrays of different sizes\r\n"));
1.269 + for(i=0;i<KEEP_RUNNING;i++)
1.270 + {
1.271 + test.Printf(_L("Testing with a random array of size %d \r\n"), size);
1.272 + fillArray(*rArr1,size);
1.273 + TInt index;
1.274 + //test(KErrNotFound==rArr1->BinarySearch((TAny*)(rArr1->operator[](0)-1),index,(TGeneralLinearOrder)simpleOrder));
1.275 + test(KErrNotFound==rArr1->FindInAddressOrder(rArr1->operator[](0)-1,index));
1.276 + test(index==0);
1.277 + for(TInt k=0;k<rArr1->Count();k++)
1.278 + {
1.279 + test(KErrNone==rArr1->FindInAddressOrder(rArr1->operator[](k),index));
1.280 + test(index==k);
1.281 + if(k<rArr1->Count()-1)
1.282 + {
1.283 + test(KErrNotFound==rArr1->FindInAddressOrder((const TUint32*)(((TUint32)rArr1->operator[](k))/2+((TUint32)rArr1->operator[](k+1))/2 + (((TUint32)rArr1->operator[](k))%2 + ((TUint32)rArr1->operator[](k+1))%2)/2),index));
1.284 + test(index==k+1);
1.285 + }
1.286 + }
1.287 + test(KErrNotFound==rArr1->FindInAddressOrder(rArr1->operator[](rArr1->Count()-1)+5,index));
1.288 + test(index==rArr1->Count());
1.289 + size += 2 + Math::Random() % (2 + size%5);
1.290 + rArr1->Reset();
1.291 + }
1.292 +
1.293 + delete rArr1;
1.294 + }
1.295 +
1.296 + }