sl@0: // Copyright (c) 1997-2009 Nokia Corporation and/or its subsidiary(-ies).
sl@0: // All rights reserved.
sl@0: // This component and the accompanying materials are made available
sl@0: // under the terms of "Eclipse Public License v1.0"
sl@0: // which accompanies this distribution, and is available
sl@0: // at the URL "http://www.eclipse.org/legal/epl-v10.html".
sl@0: //
sl@0: // Initial Contributors:
sl@0: // Nokia Corporation - initial contribution.
sl@0: //
sl@0: // Contributors:
sl@0: //
sl@0: // Description:
sl@0: // Map ANSI bsearch and qsort onto EPOC32 functions
sl@0: // 
sl@0: //
sl@0: 
sl@0: #include <e32std.h>
sl@0: #include <stdlib.h>
sl@0: 
sl@0: NONSHARABLE_CLASS(TAnsiKey) : public TKey
sl@0: 	{
sl@0: public:
sl@0: 	TAnsiKey(const TAny* key, const TAny* base, TInt length, TInt (*compar)(const TAny*, const TAny*))
sl@0: 		: iSearchKey(key), iCmp(compar)
sl@0: 		{ SetPtr(base); iKeyLength=length; }
sl@0: 
sl@0: 	virtual TInt Compare(TInt aLeft,TInt aRight) const;
sl@0: 	virtual TAny *At(TInt anIndex) const;
sl@0: private:
sl@0: 	const TAny* iSearchKey;
sl@0: 	TInt (*iCmp)(const TAny*, const TAny*);
sl@0: 	};
sl@0: 
sl@0: TInt TAnsiKey::Compare (TInt aLeft,TInt aRight) const
sl@0: 	{
sl@0: 	if (aRight==KIndexPtr)
sl@0: 		return (*iCmp)(At(aLeft),iSearchKey);
sl@0: 	else
sl@0: 		return (*iCmp)(At(aLeft),At(aRight));
sl@0: 	}
sl@0: 
sl@0: TAny* TAnsiKey::At (TInt aPos) const
sl@0: 	{
sl@0: 	return (TUint8*)iPtr+(aPos*iKeyLength);
sl@0: 	}
sl@0: 
sl@0: NONSHARABLE_CLASS(TAnsiSwap) : public TSwap
sl@0: 	{
sl@0: public:
sl@0: 	TAnsiSwap(const TAny* base, TInt length) : iPtr(base), iLength(length) {}
sl@0: 
sl@0: 	virtual void Swap(TInt aLeft,TInt aRight) const;
sl@0: private:
sl@0: 	TUint8* At(TInt aPos) const {return (TUint8*)iPtr+(aPos*iLength);}
sl@0: 
sl@0: 	const TAny* iPtr;
sl@0: 	TInt  iLength;
sl@0: 	};
sl@0: 
sl@0: void TAnsiSwap::Swap(TInt aLeft,TInt aRight) const
sl@0: 	{
sl@0: 	TUint8* left=At(aLeft);
sl@0: 	TUint8* right=At(aRight);
sl@0: 	TUint8 tmp;
sl@0: 
sl@0: 	for (TInt i=iLength; i>0; i--)
sl@0: 		{
sl@0: 		tmp=*left;
sl@0: 		*left++=*right;
sl@0: 		*right++=tmp;
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: extern "C" {
sl@0: 
sl@0: /*
sl@0: FUNCTION
sl@0: <<bsearch>>---binary search
sl@0: 
sl@0: INDEX
sl@0: 	bsearch
sl@0: 
sl@0: ANSI_SYNOPSIS
sl@0: 	#include <stdlib.h>
sl@0: 	void *bsearch(const void *<[key]>, const void *<[base]>,
sl@0: 		size_t <[nmemb]>, size_t <[size]>,
sl@0: 		int (*<[compar]>)(const void *, const void *));
sl@0: 
sl@0: TRAD_SYNOPSIS
sl@0: 	#include <stdlib.h>
sl@0: 	char *bsearch(<[key]>, <[base]>, <[nmemb]>, <[size]>, <[compar]>)
sl@0: 	char *<[key]>;
sl@0: 	char *<[base]>;
sl@0: 	size_t <[nmemb]>, <[size]>;
sl@0: 	int (*<[compar]>)();
sl@0: 
sl@0: DESCRIPTION
sl@0: <<bsearch>> searches an array beginning at <[base]> for any element
sl@0: that matches <[key]>, using binary search.  <[nmemb]> is the element
sl@0: count of the array; <[size]> is the size of each element.
sl@0: 
sl@0: The array must be sorted in ascending order with respect to the
sl@0: comparison function <[compar]> (which you supply as the last argument of
sl@0: <<bsearch>>).
sl@0: 
sl@0: You must define the comparison function <<(*<[compar]>)>> to have two
sl@0: arguments; its result must be negative if the first argument is
sl@0: less than the second, zero if the two arguments match, and
sl@0: positive if the first argument is greater than the second (where
sl@0: ``less than'' and ``greater than'' refer to whatever arbitrary
sl@0: ordering is appropriate).
sl@0: 
sl@0: RETURNS
sl@0: Returns a pointer to an element of <[array]> that matches <[key]>.  If
sl@0: more than one matching element is available, the result may point to
sl@0: any of them. Returns NULL if no matching element is found.
sl@0: 
sl@0: PORTABILITY
sl@0: <<bsearch>> is ANSI.
sl@0: 
sl@0: No supporting OS subroutines are required.
sl@0: */
sl@0: 
sl@0: /**
sl@0: searches an array beginning at <[base]> for any element
sl@0: that matches <[key]>, using binary search
sl@0: @return a pointer to an element of <[array]> that matches <[key]>.  If
sl@0: more than one matching element is available, the result may point to
sl@0: any of them. Returns NULL if no matching element is found.
sl@0: @param key
sl@0: @param base
sl@0: @param nmemb
sl@0: @param size
sl@0: */
sl@0: EXPORT_C void* bsearch (const void* key, const void* base, size_t nmemb, size_t size,
sl@0: 	int (*compar)(const void*, const void*))
sl@0: 	{
sl@0: 	TAnsiKey searchMe(key, base, size, compar);
sl@0: 	TInt result=KIndexPtr;
sl@0: 	TInt r=User::BinarySearch(nmemb, searchMe, result);
sl@0: 	if (r==0)
sl@0: 		return searchMe.At(result);
sl@0: 	else
sl@0: 		return NULL;
sl@0: 	}
sl@0: 
sl@0: /*
sl@0: FUNCTION
sl@0: <<qsort>>---sort an array
sl@0: 
sl@0: INDEX
sl@0: 	qsort
sl@0: 
sl@0: ANSI_SYNOPSIS
sl@0: 	#include <stdlib.h>
sl@0: 	void qsort(void *<[base]>, size_t <[nmemb]>, size_t <[size]>,
sl@0: 		   int (*<[compar]>)(const void *, const void *) );
sl@0: 
sl@0: TRAD_SYNOPSIS
sl@0: 	#include <stdlib.h>
sl@0: 	qsort(<[base]>, <[nmemb]>, <[size]>, <[compar]> )
sl@0: 	char *<[base]>;
sl@0: 	size_t <[nmemb]>;
sl@0: 	size_t <[size]>;
sl@0: 	int (*<[compar]>)();
sl@0: 
sl@0: DESCRIPTION
sl@0: <<qsort>> sorts an array (beginning at <[base]>) of <[nmemb]> objects.
sl@0: <[size]> describes the size of each element of the array.
sl@0: 
sl@0: You must supply a pointer to a comparison function, using the argument
sl@0: shown as <[compar]>.  (This permits sorting objects of unknown
sl@0: properties.)  Define the comparison function to accept two arguments,
sl@0: each a pointer to an element of the array starting at <[base]>.  The
sl@0: result of <<(*<[compar]>)>> must be negative if the first argument is
sl@0: less than the second, zero if the two arguments match, and positive if
sl@0: the first argument is greater than the second (where ``less than'' and
sl@0: ``greater than'' refer to whatever arbitrary ordering is appropriate).
sl@0: 
sl@0: The array is sorted in place; that is, when <<qsort>> returns, the
sl@0: array elements beginning at <[base]> have been reordered.
sl@0: 
sl@0: RETURNS
sl@0: <<qsort>> does not return a result.
sl@0: 
sl@0: PORTABILITY
sl@0: <<qsort>> is required by ANSI (without specifying the sorting algorithm).
sl@0: */
sl@0: 
sl@0: /**
sl@0: Sort an array.
sl@0: @param base 
sl@0: @param nmemb
sl@0: @param size describes the size of each element of the array
sl@0: */
sl@0: EXPORT_C void qsort (void* base, size_t nmemb, size_t size,
sl@0: 	int (*compar)(const void*, const void*))
sl@0: 	{
sl@0: 	TAnsiKey  searchMe(NULL, base, size, compar);
sl@0: 	TAnsiSwap swapUs(base,size);
sl@0: 	User::QuickSort(nmemb, searchMe, swapUs);
sl@0: 	return;
sl@0: 	}
sl@0: 
sl@0: } // extern "C"