1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/ossrv/genericopenlibs/cstdlib/LSTDLIB/QSORT.CPP Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,206 @@
1.4 +// Copyright (c) 1997-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 "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 +// Map ANSI bsearch and qsort onto EPOC32 functions
1.18 +//
1.19 +//
1.20 +
1.21 +#include <e32std.h>
1.22 +#include <stdlib.h>
1.23 +
1.24 +NONSHARABLE_CLASS(TAnsiKey) : public TKey
1.25 + {
1.26 +public:
1.27 + TAnsiKey(const TAny* key, const TAny* base, TInt length, TInt (*compar)(const TAny*, const TAny*))
1.28 + : iSearchKey(key), iCmp(compar)
1.29 + { SetPtr(base); iKeyLength=length; }
1.30 +
1.31 + virtual TInt Compare(TInt aLeft,TInt aRight) const;
1.32 + virtual TAny *At(TInt anIndex) const;
1.33 +private:
1.34 + const TAny* iSearchKey;
1.35 + TInt (*iCmp)(const TAny*, const TAny*);
1.36 + };
1.37 +
1.38 +TInt TAnsiKey::Compare (TInt aLeft,TInt aRight) const
1.39 + {
1.40 + if (aRight==KIndexPtr)
1.41 + return (*iCmp)(At(aLeft),iSearchKey);
1.42 + else
1.43 + return (*iCmp)(At(aLeft),At(aRight));
1.44 + }
1.45 +
1.46 +TAny* TAnsiKey::At (TInt aPos) const
1.47 + {
1.48 + return (TUint8*)iPtr+(aPos*iKeyLength);
1.49 + }
1.50 +
1.51 +NONSHARABLE_CLASS(TAnsiSwap) : public TSwap
1.52 + {
1.53 +public:
1.54 + TAnsiSwap(const TAny* base, TInt length) : iPtr(base), iLength(length) {}
1.55 +
1.56 + virtual void Swap(TInt aLeft,TInt aRight) const;
1.57 +private:
1.58 + TUint8* At(TInt aPos) const {return (TUint8*)iPtr+(aPos*iLength);}
1.59 +
1.60 + const TAny* iPtr;
1.61 + TInt iLength;
1.62 + };
1.63 +
1.64 +void TAnsiSwap::Swap(TInt aLeft,TInt aRight) const
1.65 + {
1.66 + TUint8* left=At(aLeft);
1.67 + TUint8* right=At(aRight);
1.68 + TUint8 tmp;
1.69 +
1.70 + for (TInt i=iLength; i>0; i--)
1.71 + {
1.72 + tmp=*left;
1.73 + *left++=*right;
1.74 + *right++=tmp;
1.75 + }
1.76 + }
1.77 +
1.78 +extern "C" {
1.79 +
1.80 +/*
1.81 +FUNCTION
1.82 +<<bsearch>>---binary search
1.83 +
1.84 +INDEX
1.85 + bsearch
1.86 +
1.87 +ANSI_SYNOPSIS
1.88 + #include <stdlib.h>
1.89 + void *bsearch(const void *<[key]>, const void *<[base]>,
1.90 + size_t <[nmemb]>, size_t <[size]>,
1.91 + int (*<[compar]>)(const void *, const void *));
1.92 +
1.93 +TRAD_SYNOPSIS
1.94 + #include <stdlib.h>
1.95 + char *bsearch(<[key]>, <[base]>, <[nmemb]>, <[size]>, <[compar]>)
1.96 + char *<[key]>;
1.97 + char *<[base]>;
1.98 + size_t <[nmemb]>, <[size]>;
1.99 + int (*<[compar]>)();
1.100 +
1.101 +DESCRIPTION
1.102 +<<bsearch>> searches an array beginning at <[base]> for any element
1.103 +that matches <[key]>, using binary search. <[nmemb]> is the element
1.104 +count of the array; <[size]> is the size of each element.
1.105 +
1.106 +The array must be sorted in ascending order with respect to the
1.107 +comparison function <[compar]> (which you supply as the last argument of
1.108 +<<bsearch>>).
1.109 +
1.110 +You must define the comparison function <<(*<[compar]>)>> to have two
1.111 +arguments; its result must be negative if the first argument is
1.112 +less than the second, zero if the two arguments match, and
1.113 +positive if the first argument is greater than the second (where
1.114 +``less than'' and ``greater than'' refer to whatever arbitrary
1.115 +ordering is appropriate).
1.116 +
1.117 +RETURNS
1.118 +Returns a pointer to an element of <[array]> that matches <[key]>. If
1.119 +more than one matching element is available, the result may point to
1.120 +any of them. Returns NULL if no matching element is found.
1.121 +
1.122 +PORTABILITY
1.123 +<<bsearch>> is ANSI.
1.124 +
1.125 +No supporting OS subroutines are required.
1.126 +*/
1.127 +
1.128 +/**
1.129 +searches an array beginning at <[base]> for any element
1.130 +that matches <[key]>, using binary search
1.131 +@return a pointer to an element of <[array]> that matches <[key]>. If
1.132 +more than one matching element is available, the result may point to
1.133 +any of them. Returns NULL if no matching element is found.
1.134 +@param key
1.135 +@param base
1.136 +@param nmemb
1.137 +@param size
1.138 +*/
1.139 +EXPORT_C void* bsearch (const void* key, const void* base, size_t nmemb, size_t size,
1.140 + int (*compar)(const void*, const void*))
1.141 + {
1.142 + TAnsiKey searchMe(key, base, size, compar);
1.143 + TInt result=KIndexPtr;
1.144 + TInt r=User::BinarySearch(nmemb, searchMe, result);
1.145 + if (r==0)
1.146 + return searchMe.At(result);
1.147 + else
1.148 + return NULL;
1.149 + }
1.150 +
1.151 +/*
1.152 +FUNCTION
1.153 +<<qsort>>---sort an array
1.154 +
1.155 +INDEX
1.156 + qsort
1.157 +
1.158 +ANSI_SYNOPSIS
1.159 + #include <stdlib.h>
1.160 + void qsort(void *<[base]>, size_t <[nmemb]>, size_t <[size]>,
1.161 + int (*<[compar]>)(const void *, const void *) );
1.162 +
1.163 +TRAD_SYNOPSIS
1.164 + #include <stdlib.h>
1.165 + qsort(<[base]>, <[nmemb]>, <[size]>, <[compar]> )
1.166 + char *<[base]>;
1.167 + size_t <[nmemb]>;
1.168 + size_t <[size]>;
1.169 + int (*<[compar]>)();
1.170 +
1.171 +DESCRIPTION
1.172 +<<qsort>> sorts an array (beginning at <[base]>) of <[nmemb]> objects.
1.173 +<[size]> describes the size of each element of the array.
1.174 +
1.175 +You must supply a pointer to a comparison function, using the argument
1.176 +shown as <[compar]>. (This permits sorting objects of unknown
1.177 +properties.) Define the comparison function to accept two arguments,
1.178 +each a pointer to an element of the array starting at <[base]>. The
1.179 +result of <<(*<[compar]>)>> must be negative if the first argument is
1.180 +less than the second, zero if the two arguments match, and positive if
1.181 +the first argument is greater than the second (where ``less than'' and
1.182 +``greater than'' refer to whatever arbitrary ordering is appropriate).
1.183 +
1.184 +The array is sorted in place; that is, when <<qsort>> returns, the
1.185 +array elements beginning at <[base]> have been reordered.
1.186 +
1.187 +RETURNS
1.188 +<<qsort>> does not return a result.
1.189 +
1.190 +PORTABILITY
1.191 +<<qsort>> is required by ANSI (without specifying the sorting algorithm).
1.192 +*/
1.193 +
1.194 +/**
1.195 +Sort an array.
1.196 +@param base
1.197 +@param nmemb
1.198 +@param size describes the size of each element of the array
1.199 +*/
1.200 +EXPORT_C void qsort (void* base, size_t nmemb, size_t size,
1.201 + int (*compar)(const void*, const void*))
1.202 + {
1.203 + TAnsiKey searchMe(NULL, base, size, compar);
1.204 + TAnsiSwap swapUs(base,size);
1.205 + User::QuickSort(nmemb, searchMe, swapUs);
1.206 + return;
1.207 + }
1.208 +
1.209 +} // extern "C"