--- /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.