diff -r 000000000000 -r c8830336c852 eapol/eapol_framework/eapol_common/include/eap_sort.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/eapol/eapol_framework/eapol_common/include/eap_sort.h	Thu Dec 17 08:47:43 2009 +0200
@@ -0,0 +1,275 @@
+/*
+* Copyright (c) 2001-2006 Nokia Corporation and/or its subsidiary(-ies).
+* All rights reserved.
+* This component and the accompanying materials are made available
+* under the terms of the License "Eclipse Public License v1.0"
+* which accompanies this distribution, and is available
+* at the URL "http://www.eclipse.org/legal/epl-v10.html".
+*
+* Initial Contributors:
+* Nokia Corporation - initial contribution.
+*
+* Contributors:
+*
+* Description:  EAP and WLAN authentication protocols.
+*
+*/
+
+
+
+
+#if !defined(_EAP_SORT_H_)
+#define _EAP_SORT_H_
+
+#include "eap_am_memory.h"
+#include "eap_tools.h"
+#include "eap_am_tools.h"
+#include "eap_automatic_variable.h"
+
+/** @file */
+
+//--------------------------------------------------
+
+/**
+ * This template function copies array of objects from first to last
+ * to array of objects ending to result.
+ * Parameter first point to the first object of the source array.
+ * Parameter last points the next address after the last object of source array.
+ * Parameter result points the next address after the last object of the result array.
+ */
+template <class Type>
+void eap_sort_copy_backward(
+	const Type * const first,
+	const Type *last,
+	Type *result )
+{
+	while (first != last)
+	{
+		*--result = *--last;
+	}
+}
+
+//--------------------------------------------------
+
+/**
+ * 
+ */
+template <class Type>
+void eap_sort_unguarded_linear_insert(
+	Type *last,
+	const Type inserted_object,
+	bool (*compare_first_is_smaller)(
+		const Type * const first,
+		const Type * const second,
+		abs_eap_am_tools_c * const m_am_tools),
+	abs_eap_am_tools_c * const m_am_tools)
+{
+	Type *next = last;
+
+	--next;
+
+	while(compare_first_is_smaller(&inserted_object, next, m_am_tools) == true)
+	{
+		*last = *next;
+		last = next--;
+	}
+
+	*last = inserted_object;
+}
+
+//--------------------------------------------------
+
+template <class Type>
+void eap_sort_linear_insert(
+	Type * const first,
+	Type * const last,
+	bool (*compare_first_is_smaller)(
+		const Type * const first,
+		const Type * const second,
+		abs_eap_am_tools_c * const m_am_tools),
+	abs_eap_am_tools_c * const m_am_tools)
+{
+	const Type value = *last;
+
+	if(compare_first_is_smaller(&value, first, m_am_tools) == true)
+	{
+		eap_sort_copy_backward(first, last, last+1);
+		*first = value;
+	}
+	else
+	{
+		eap_sort_unguarded_linear_insert(last, value, compare_first_is_smaller, m_am_tools);
+	}
+}
+
+//--------------------------------------------------
+
+template <class Type>
+void eap_sort_insert_sort_area(
+	Type * const first,
+	const Type *last,
+	bool (*compare_first_is_smaller)(
+		const Type * const first,
+		const Type * const second,
+		abs_eap_am_tools_c * const m_am_tools),
+	abs_eap_am_tools_c * const m_am_tools)
+{
+	Type *tmp;
+
+	++last;
+
+	for( tmp = first+1; tmp < last; tmp++ )
+	{
+		eap_sort_linear_insert( first, tmp, compare_first_is_smaller, m_am_tools);
+	}
+}
+
+//------------------------------------------------------------
+
+
+template <class Type>
+Type *eap_sort_divide_area(
+	Type *start,
+	Type *finish,
+	bool (*compare_first_is_smaller)(
+		const Type * const first,
+		const Type * const second,
+		abs_eap_am_tools_c * const m_am_tools),
+	abs_eap_am_tools_c * const m_am_tools)
+{
+	// selects the boundary object.
+	const Type boundary = *(start+((finish - start)/2));
+	Type change;
+
+	start--;
+	finish++;
+
+	// Boundary is used as a middle object.
+	for(;;)
+	{
+		// Examine from begin to end is ++start smaller than boundary.
+		while(compare_first_is_smaller(++start, &boundary, m_am_tools) == true)
+		{
+			// Nothing to do.
+		}
+
+		// Examine from end to begin is --finish bigger than boundary.
+		while(compare_first_is_smaller(&boundary, --finish, m_am_tools) == true)
+		{
+			// Nothing to do.
+		}
+
+
+		if( start < finish )
+		{
+			// In case boundary isn't reached, it intent that two
+			// atom mutual side of boundary are in wrong order,
+			// so swap them.
+			change = *start;
+			*start = *finish;
+			*finish = change;
+		}
+		else
+		{
+			// Start and finish pointers are overlapping.
+			// Terminate loop and return pointer to finish.
+			return( finish );
+		}
+	} // for()
+
+}
+
+//--------------------------------------------------
+
+/**
+ * This function does quick-sort with non-recurvive alorithm.
+ * Parameter array is pointer to array including objects of type Type.
+ * Parameter object_count is count of objects in the array.
+ * Parameter compare_first_is_smaller is pointer to a function that compares objects of type Type.
+ */
+template <class Type>
+eap_status_e eap_sort_array(
+	Type * const array,
+	const u32_t object_count,
+	bool (*compare_first_is_smaller)(
+		const Type * const first,
+		const Type * const second,
+		abs_eap_am_tools_c * const m_am_tools),
+	abs_eap_am_tools_c * const m_am_tools)
+{
+	EAP_TRACE_BEGIN(m_am_tools, TRACE_FLAGS_DEFAULT);
+
+	eap_status_e status = eap_status_ok; // Note original_array may be empty or it includes only one object, then sort will not be run. 
+
+	if (object_count < 2ul)
+	{
+		EAP_TRACE_END(m_am_tools, TRACE_FLAGS_DEFAULT);
+		return EAP_STATUS_RETURN(m_am_tools, status);
+	}
+
+	const u32_t quicksort_finish = 10ul;
+
+	// When there are atoms in the array fewer than quicksort_finish,
+	// then the array is sorted directly by eap_sort_insert_sort_area() function.
+	if (object_count >= quicksort_finish)
+	{
+		Type ** const sort_array = new Type *[object_count+1];
+		eap_automatic_array_variable_c<Type *> automatic_sort_array(m_am_tools, sort_array);
+		if (sort_array == 0)
+		{
+			EAP_TRACE_END(m_am_tools, TRACE_FLAGS_DEFAULT);
+			return EAP_STATUS_RETURN(m_am_tools, eap_status_allocation_error);
+		}
+
+		// first atom
+		Type *start = array;
+		// last point to the first address after the last atom.
+		Type *last = array+object_count;
+		Type *finish = last - 1;
+		sort_array[finish-array] = finish;
+
+		// We continue until start come real array's end.
+		while (last != start)
+		{
+			if (static_cast<u32_t>(finish - start) > quicksort_finish)
+			{
+				Type *upper = eap_sort_divide_area(start, finish , compare_first_is_smaller, m_am_tools);
+
+				// When is at least two unit in beginning.
+				// Divide sorting area under upper address.
+				// Upper areas end points are saved to sort_array.
+				sort_array[upper+1-array] = finish;
+
+				// New sorting area.
+				// New start address is the same as start pointer of previous sort area.
+				// New finish address is preceding address of upper address.
+				finish = upper;
+			}
+			else
+			{
+				eap_sort_insert_sort_area(start, finish , compare_first_is_smaller, m_am_tools);
+
+				start = ++finish;
+				finish = sort_array[start-array];
+			}
+		} // while ( last != start )
+	}
+	else
+	{
+		eap_sort_insert_sort_area(array, array+(object_count-1), compare_first_is_smaller, m_am_tools);
+	}
+
+	EAP_TRACE_END(m_am_tools, TRACE_FLAGS_DEFAULT);
+	return EAP_STATUS_RETURN(m_am_tools, status);
+}
+
+//--------------------------------------------------
+
+#endif //#if !defined(_EAP_SORT_H_)
+
+
+//--------------------------------------------------
+
+
+
+// End.