VirtualBox

source: vbox/trunk/include/iprt/nocrt/algorithm@ 96361

最後變更 在這個檔案從96361是 96361,由 vboxsync 提交於 3 年 前

iprt/nocrt/algorithm: Just use shell sort for the std::sort implementation for now. bugref:10261

  • 屬性 svn:eol-style 設為 native
  • 屬性 svn:keywords 設為 Author Date Id Revision
檔案大小: 5.6 KB
 
1/** @file
2 * IPRT / No-CRT - Minimal C++ algorithm header.
3 */
4
5/*
6 * Copyright (C) 2022 Oracle Corporation
7 *
8 * This file is part of VirtualBox Open Source Edition (OSE), as
9 * available from http://www.alldomusa.eu.org. This file is free software;
10 * you can redistribute it and/or modify it under the terms of the GNU
11 * General Public License (GPL) as published by the Free Software
12 * Foundation, in version 2 as it comes in the "COPYING" file of the
13 * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
14 * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
15 *
16 * The contents of this file may alternatively be used under the terms
17 * of the Common Development and Distribution License Version 1.0
18 * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
19 * VirtualBox OSE distribution, in which case the provisions of the
20 * CDDL are applicable instead of those of the GPL.
21 *
22 * You may elect to license modified versions of this file under the
23 * terms and conditions of either the GPL or the CDDL or both.
24 */
25
26#ifndef IPRT_INCLUDED_nocrt_algorithm
27#define IPRT_INCLUDED_nocrt_algorithm
28#ifndef RT_WITHOUT_PRAGMA_ONCE
29# pragma once
30#endif
31
32#ifdef _MSC_VER
33# pragma warning(push)
34# pragma warning(disable: 4643) /* warning C4643: Forward declaring 'ios_base' in namespace std is not permitted by the C++ Standard */
35#endif
36
37namespace std
38{
39 /**
40 * Swap the values pointed to by the two references.
41 */
42 template<typename a_Type>
43 void swap(a_Type &a_rObj1, a_Type &a_rObj2)
44 {
45 a_Type Tmp(a_rObj1);
46 a_rObj1 = a_rObj2;
47 a_rObj2 = Tmp;
48 }
49
50 /**
51 * Swap the values pointed to by two forward iterators.
52 */
53 template<typename a_ForwardIt1, typename a_ForwardIt2>
54 void iter_swap(a_ForwardIt1 a_It1, a_ForwardIt2 a_It2)
55 {
56 swap(*a_It1, *a_It2);
57 }
58
59 template<typename a_RandomIt>
60 void sort(a_RandomIt a_ItBegin, a_RandomIt a_ItEnd)
61 {
62 /* Note! Using shell sort here because it's tiny and we've got code for it. */
63 /** @todo replace with faster code. */
64
65 /* Anything worth sorting? */
66 std::size_t const cElements = a_ItEnd - a_ItBegin;
67 if (cElements >= 1)
68 {
69 /* Loop on decreasing gap, ending with 1: */
70 std::size_t cGap = (cElements + 1) / 2;
71 while (cGap > 0)
72 {
73 /* Iterate from cGap till the end: */
74 for (std::size_t i = cGap; i < cElements; i++)
75 {
76 /* Find the best suitable location for the item at 'i' comparing
77 backwards in steps of 'cGap', swapping the item at 'i' with the
78 one at '-cGap*j' if it's smaller, stopping if it's larger.
79
80 Note! Original algorithm would make a copy of the item, this version
81 avoids extra copies of sorted items at the cost of extra copies
82 when dealing with unsorted ones a small cGaps values. */
83 a_RandomIt ItCur = a_ItBegin + i;
84 size_t j = i;
85 do
86 {
87 j -= cGap;
88 a_RandomIt ItAtGap = a_ItBegin + j;
89 if (*ItAtGap < *ItCur)
90 break;
91 std::iter_swap(ItAtGap, ItCur);
92 ItCur = ItAtGap;
93 } while (j >= cGap);
94 }
95
96 /* This does not generate the most optimal gap sequence, but it has the
97 advantage of being simple and avoid floating point. */
98 cGap /= 2;
99 }
100 }
101 }
102
103 template<typename a_RandomIt, typename a_FnCompareType>
104 void sort(a_RandomIt a_ItBegin, a_RandomIt a_ItEnd, a_FnCompareType a_fnComp)
105 {
106 /* Note! Using shell sort here because it's tiny and we've got code for it. */
107 /** @todo replace with faster code. */
108
109 /* Anything worth sorting? */
110 std::size_t const cElements = a_ItEnd - a_ItBegin;
111 if (cElements >= 1)
112 {
113 /* Loop on decreasing gap, ending with 1: */
114 std::size_t cGap = (cElements + 1) / 2;
115 while (cGap > 0)
116 {
117 /* Iterate from cGap till the end: */
118 for (std::size_t i = cGap; i < cElements; i++)
119 {
120 /* Find the best suitable location for the item at 'i' comparing
121 backwards in steps of 'cGap', swapping the item at 'i' with the
122 one at '-cGap*j' if it's smaller, stopping if it's larger.
123
124 Note! Original algorithm would make a copy of the item, this version
125 avoids extra copies of sorted items at the cost of extra copies
126 when dealing with unsorted ones a small cGaps values. */
127 a_RandomIt ItCur = a_ItBegin + i;
128 size_t j = i;
129 do
130 {
131 j -= cGap;
132 a_RandomIt ItAtGap = a_ItBegin + j;
133 if (a_fnComp(*ItAtGap, *ItCur))
134 break;
135 std::iter_swap(ItAtGap, ItCur);
136 ItCur = ItAtGap;
137 } while (j >= cGap);
138 }
139
140 /* This does not generate the most optimal gap sequence, but it has the
141 advantage of being simple and avoid floating point. */
142 cGap /= 2;
143 }
144 }
145 }
146
147}
148
149#ifdef _MSC_VER
150# pragma warning(pop)
151#endif
152
153#endif /* !IPRT_INCLUDED_nocrt_algorithm */
154
155
注意: 瀏覽 TracBrowser 來幫助您使用儲存庫瀏覽器

© 2025 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette