diff options
Diffstat (limited to '')
| -rw-r--r-- | include/iprt/nocrt/algorithm | 164 |
1 files changed, 164 insertions, 0 deletions
diff --git a/include/iprt/nocrt/algorithm b/include/iprt/nocrt/algorithm new file mode 100644 index 00000000..bf6102f8 --- /dev/null +++ b/include/iprt/nocrt/algorithm @@ -0,0 +1,164 @@ +/** @file + * IPRT / No-CRT - Minimal C++ algorithm header. + */ + +/* + * Copyright (C) 2022 Oracle and/or its affiliates. + * + * This file is part of VirtualBox base platform packages, as + * available from https://www.virtualbox.org. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation, in version 3 of the + * License. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, see <https://www.gnu.org/licenses>. + * + * The contents of this file may alternatively be used under the terms + * of the Common Development and Distribution License Version 1.0 + * (CDDL), a copy of it is provided in the "COPYING.CDDL" file included + * in the VirtualBox distribution, in which case the provisions of the + * CDDL are applicable instead of those of the GPL. + * + * You may elect to license modified versions of this file under the + * terms and conditions of either the GPL or the CDDL or both. + * + * SPDX-License-Identifier: GPL-3.0-only OR CDDL-1.0 + */ + +#ifndef VBOX_INCLUDED_SRC_nocrt_algorithm +#define VBOX_INCLUDED_SRC_nocrt_algorithm +#ifndef RT_WITHOUT_PRAGMA_ONCE +# pragma once +#endif + +#ifdef _MSC_VER +# pragma warning(push) +# pragma warning(disable: 4643) /* warning C4643: Forward declaring 'ios_base' in namespace std is not permitted by the C++ Standard */ +#endif + +namespace std +{ + /** + * Swap the values pointed to by the two references. + */ + template<typename a_Type> + void swap(a_Type &a_rObj1, a_Type &a_rObj2) + { + a_Type Tmp(a_rObj1); + a_rObj1 = a_rObj2; + a_rObj2 = Tmp; + } + + /** + * Swap the values pointed to by two forward iterators. + */ + template<typename a_ForwardIt1, typename a_ForwardIt2> + void iter_swap(a_ForwardIt1 a_It1, a_ForwardIt2 a_It2) + { + swap(*a_It1, *a_It2); + } + + template<typename a_RandomIt> + void sort(a_RandomIt a_ItBegin, a_RandomIt a_ItEnd) + { + /* Note! Using shell sort here because it's tiny and we've got code for it. */ + /** @todo replace with faster code. */ + + /* Anything worth sorting? */ + std::size_t const cElements = a_ItEnd - a_ItBegin; + if (cElements >= 1) + { + /* Loop on decreasing gap, ending with 1: */ + std::size_t cGap = (cElements + 1) / 2; + while (cGap > 0) + { + /* Iterate from cGap till the end: */ + for (std::size_t i = cGap; i < cElements; i++) + { + /* Find the best suitable location for the item at 'i' comparing + backwards in steps of 'cGap', swapping the item at 'i' with the + one at '-cGap*j' if it's smaller, stopping if it's larger. + + Note! Original algorithm would make a copy of the item, this version + avoids extra copies of sorted items at the cost of extra copies + when dealing with unsorted ones a small cGaps values. */ + a_RandomIt ItCur = a_ItBegin + i; + size_t j = i; + do + { + j -= cGap; + a_RandomIt ItAtGap = a_ItBegin + j; + if (*ItAtGap < *ItCur) + break; + std::iter_swap(ItAtGap, ItCur); + ItCur = ItAtGap; + } while (j >= cGap); + } + + /* This does not generate the most optimal gap sequence, but it has the + advantage of being simple and avoid floating point. */ + cGap /= 2; + } + } + } + + template<typename a_RandomIt, typename a_FnCompareType> + void sort(a_RandomIt a_ItBegin, a_RandomIt a_ItEnd, a_FnCompareType a_fnComp) + { + /* Note! Using shell sort here because it's tiny and we've got code for it. */ + /** @todo replace with faster code. */ + + /* Anything worth sorting? */ + std::size_t const cElements = a_ItEnd - a_ItBegin; + if (cElements >= 1) + { + /* Loop on decreasing gap, ending with 1: */ + std::size_t cGap = (cElements + 1) / 2; + while (cGap > 0) + { + /* Iterate from cGap till the end: */ + for (std::size_t i = cGap; i < cElements; i++) + { + /* Find the best suitable location for the item at 'i' comparing + backwards in steps of 'cGap', swapping the item at 'i' with the + one at '-cGap*j' if it's smaller, stopping if it's larger. + + Note! Original algorithm would make a copy of the item, this version + avoids extra copies of sorted items at the cost of extra copies + when dealing with unsorted ones a small cGaps values. */ + a_RandomIt ItCur = a_ItBegin + i; + size_t j = i; + do + { + j -= cGap; + a_RandomIt ItAtGap = a_ItBegin + j; + if (a_fnComp(*ItAtGap, *ItCur)) + break; + std::iter_swap(ItAtGap, ItCur); + ItCur = ItAtGap; + } while (j >= cGap); + } + + /* This does not generate the most optimal gap sequence, but it has the + advantage of being simple and avoid floating point. */ + cGap /= 2; + } + } + } + +} + +#ifdef _MSC_VER +# pragma warning(pop) +#endif + +#endif /* !VBOX_INCLUDED_SRC_nocrt_algorithm */ + |