From f8fe689a81f906d1b91bb3220acde2a4ecb14c5b Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Mon, 6 May 2024 05:01:46 +0200 Subject: Adding upstream version 6.0.4-dfsg. Signed-off-by: Daniel Baumann --- src/VBox/Runtime/common/sort/Makefile.kup | 0 src/VBox/Runtime/common/sort/RTSortApvIsSorted.cpp | 48 ++++++++++ src/VBox/Runtime/common/sort/RTSortIsSorted.cpp | 50 ++++++++++ src/VBox/Runtime/common/sort/shellsort.cpp | 102 +++++++++++++++++++++ 4 files changed, 200 insertions(+) create mode 100644 src/VBox/Runtime/common/sort/Makefile.kup create mode 100644 src/VBox/Runtime/common/sort/RTSortApvIsSorted.cpp create mode 100644 src/VBox/Runtime/common/sort/RTSortIsSorted.cpp create mode 100644 src/VBox/Runtime/common/sort/shellsort.cpp (limited to 'src/VBox/Runtime/common/sort') diff --git a/src/VBox/Runtime/common/sort/Makefile.kup b/src/VBox/Runtime/common/sort/Makefile.kup new file mode 100644 index 00000000..e69de29b diff --git a/src/VBox/Runtime/common/sort/RTSortApvIsSorted.cpp b/src/VBox/Runtime/common/sort/RTSortApvIsSorted.cpp new file mode 100644 index 00000000..35fdb960 --- /dev/null +++ b/src/VBox/Runtime/common/sort/RTSortApvIsSorted.cpp @@ -0,0 +1,48 @@ +/* $Id: RTSortApvIsSorted.cpp $ */ +/** @file + * IPRT - RTSortApvIsSorted. + */ + +/* + * Copyright (C) 2010-2019 Oracle Corporation + * + * This file is part of VirtualBox Open Source Edition (OSE), as + * available from http://www.virtualbox.org. This file is free software; + * you can redistribute it and/or modify it under the terms of the GNU + * General Public License (GPL) as published by the Free Software + * Foundation, in version 2 as it comes in the "COPYING" file of the + * VirtualBox OSE distribution. VirtualBox OSE is distributed in the + * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind. + * + * The contents of this file may alternatively be used under the terms + * of the Common Development and Distribution License Version 1.0 + * (CDDL) only, as it comes in the "COPYING.CDDL" file of the + * VirtualBox OSE 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. + */ + + +/********************************************************************************************************************************* +* Header Files * +*********************************************************************************************************************************/ +#include +#include "internal/iprt.h" + + +RTDECL(bool) RTSortApvIsSorted(void const * const *papvArray, size_t cElements, PFNRTSORTCMP pfnCmp, void *pvUser) +{ + if (cElements >= 2) + { + for (size_t i = 0; i < cElements - 1; i++) + { + if (pfnCmp(papvArray[i], papvArray[i + 1], pvUser) > 0) + return false; + } + } + return true; +} +RT_EXPORT_SYMBOL(RTSortIsSorted); + diff --git a/src/VBox/Runtime/common/sort/RTSortIsSorted.cpp b/src/VBox/Runtime/common/sort/RTSortIsSorted.cpp new file mode 100644 index 00000000..99f8aad9 --- /dev/null +++ b/src/VBox/Runtime/common/sort/RTSortIsSorted.cpp @@ -0,0 +1,50 @@ +/* $Id: RTSortIsSorted.cpp $ */ +/** @file + * IPRT - RTSortIsSorted. + */ + +/* + * Copyright (C) 2010-2019 Oracle Corporation + * + * This file is part of VirtualBox Open Source Edition (OSE), as + * available from http://www.virtualbox.org. This file is free software; + * you can redistribute it and/or modify it under the terms of the GNU + * General Public License (GPL) as published by the Free Software + * Foundation, in version 2 as it comes in the "COPYING" file of the + * VirtualBox OSE distribution. VirtualBox OSE is distributed in the + * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind. + * + * The contents of this file may alternatively be used under the terms + * of the Common Development and Distribution License Version 1.0 + * (CDDL) only, as it comes in the "COPYING.CDDL" file of the + * VirtualBox OSE 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. + */ + + +/********************************************************************************************************************************* +* Header Files * +*********************************************************************************************************************************/ +#include +#include "internal/iprt.h" + + +RTDECL(bool) RTSortIsSorted(void const *pvArray, size_t cElements, size_t cbElement, PFNRTSORTCMP pfnCmp, void *pvUser) +{ + if (cElements >= 2) + { + const char *pbArray = (const char *)pvArray; + for (size_t i = 0; i < cElements - 1; i++) + { + const char *pbElement1 = pbArray + i * cbElement; + if (pfnCmp(pbElement1, pbElement1 + cbElement, pvUser) > 0) + return false; + } + } + return true; +} +RT_EXPORT_SYMBOL(RTSortIsSorted); + diff --git a/src/VBox/Runtime/common/sort/shellsort.cpp b/src/VBox/Runtime/common/sort/shellsort.cpp new file mode 100644 index 00000000..ebc28236 --- /dev/null +++ b/src/VBox/Runtime/common/sort/shellsort.cpp @@ -0,0 +1,102 @@ +/* $Id: shellsort.cpp $ */ +/** @file + * IPRT - RTSortIsSorted. + */ + +/* + * Copyright (C) 2010-2019 Oracle Corporation + * + * This file is part of VirtualBox Open Source Edition (OSE), as + * available from http://www.virtualbox.org. This file is free software; + * you can redistribute it and/or modify it under the terms of the GNU + * General Public License (GPL) as published by the Free Software + * Foundation, in version 2 as it comes in the "COPYING" file of the + * VirtualBox OSE distribution. VirtualBox OSE is distributed in the + * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind. + * + * The contents of this file may alternatively be used under the terms + * of the Common Development and Distribution License Version 1.0 + * (CDDL) only, as it comes in the "COPYING.CDDL" file of the + * VirtualBox OSE 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. + */ + + +/********************************************************************************************************************************* +* Header Files * +*********************************************************************************************************************************/ +#include "internal/iprt.h" +#include + +#include +#include +#include + + + +RTDECL(void) RTSortShell(void *pvArray, size_t cElements, size_t cbElement, PFNRTSORTCMP pfnCmp, void *pvUser) +{ + Assert(cbElement <= 32); + + /* Anything worth sorting? */ + if (cElements < 2) + return; + + uint8_t *pbArray = (uint8_t *)pvArray; + void *pvTmp = alloca(cbElement); + size_t cGap = (cElements + 1) / 2; + while (cGap > 0) + { + size_t i; + for (i = cGap; i < cElements; i++) + { + memcpy(pvTmp, &pbArray[i * cbElement], cbElement); + size_t j = i; + while ( j >= cGap + && pfnCmp(&pbArray[(j - cGap) * cbElement], pvTmp, pvUser) > 0) + { + memmove(&pbArray[j * cbElement], &pbArray[(j - cGap) * cbElement], cbElement); + j -= cGap; + } + memcpy(&pbArray[j * cbElement], pvTmp, cbElement); + } + + /* This does not generate the most optimal gap sequence, but it has the + advantage of being simple and avoid floating point. */ + cGap /= 2; + } +} + + +RTDECL(void) RTSortApvShell(void **papvArray, size_t cElements, PFNRTSORTCMP pfnCmp, void *pvUser) +{ + /* Anything worth sorting? */ + if (cElements < 2) + return; + + size_t cGap = (cElements + 1) / 2; + while (cGap > 0) + { + size_t i; + for (i = cGap; i < cElements; i++) + { + void *pvTmp = papvArray[i]; + size_t j = i; + while ( j >= cGap + && pfnCmp(papvArray[j - cGap], pvTmp, pvUser) > 0) + { + papvArray[j] = papvArray[j - cGap]; + j -= cGap; + } + papvArray[j] = pvTmp; + } + + /* This does not generate the most optimal gap sequence, but it has the + advantage of being simple and avoid floating point. */ + cGap /= 2; + } +} + -- cgit v1.2.3