Sun, 23 Nov 2025 13:15:19 +0100
optimize sorted insertion by using the infimum instead of the supremum
The reason is that the supremum returns the equal element with the smallest index, and we want the largest.
Therefore, we use the infimum, which already gives us the largest index when there are equal elements, and increase the index by one. The infimum is also guaranteed to exist in that case.
<?xml version="1.0" encoding="utf-8"?> <Project DefaultTargets="Build" xmlns="http://schemas.microsoft.com/developer/msbuild/2003"> <ItemGroup Label="ProjectConfigurations"> <ProjectConfiguration Include="Debug|Win32"> <Configuration>Debug</Configuration> <Platform>Win32</Platform> </ProjectConfiguration> <ProjectConfiguration Include="Release|Win32"> <Configuration>Release</Configuration> <Platform>Win32</Platform> </ProjectConfiguration> <ProjectConfiguration Include="Debug|x64"> <Configuration>Debug</Configuration> <Platform>x64</Platform> </ProjectConfiguration> <ProjectConfiguration Include="Release|x64"> <Configuration>Release</Configuration> <Platform>x64</Platform> </ProjectConfiguration> </ItemGroup> <ItemGroup> <ClCompile Include="..\..\tests\test_allocator.c" /> <ClCompile Include="..\..\tests\test_buffer.c" /> <ClCompile Include="..\..\tests\test_compare.c" /> <ClCompile Include="..\..\tests\test_hash_key.c" /> <ClCompile Include="..\..\tests\test_hash_map.c" /> <ClCompile Include="..\..\tests\test_iterator.c" /> <ClCompile Include="..\..\tests\test_json.c" /> <ClCompile Include="..\..\tests\test_list.c" /> <ClCompile Include="..\..\tests\test_kv_list.c" /> <ClCompile Include="..\..\tests\test_mempool.c" /> <ClCompile Include="..\..\tests\test_printf.c" /> <ClCompile Include="..\..\tests\test_properties.c" /> <ClCompile Include="..\..\tests\test_string.c" /> <ClCompile Include="..\..\tests\test_szmul.c" /> <ClCompile Include="..\..\tests\test_tree.c" /> <ClCompile Include="..\..\tests\test_streams.c" /> <ClCompile Include="..\..\tests\ucxtest.c" /> <ClCompile Include="..\..\tests\util_allocator.c" /> </ItemGroup> <ItemGroup> <ClInclude Include="..\..\tests\util_allocator.h" /> </ItemGroup> <ItemGroup> <ProjectReference Include="..\libucx\libucx.vcxproj"> <Project>{a7ee56a3-0bad-4cab-9354-7fae2a65e276}</Project> </ProjectReference> </ItemGroup> <PropertyGroup Label="Globals"> <VCProjectVersion>17.0</VCProjectVersion> <Keyword>Win32Proj</Keyword> <ProjectGuid>{56337f37-5298-49c4-b4d4-b43c1b2900f0}</ProjectGuid> <RootNamespace>ucxtest</RootNamespace> <WindowsTargetPlatformVersion>10.0</WindowsTargetPlatformVersion> </PropertyGroup> <Import Project="$(VCTargetsPath)\Microsoft.Cpp.Default.props" /> <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Debug|Win32'" Label="Configuration"> <ConfigurationType>Application</ConfigurationType> <UseDebugLibraries>true</UseDebugLibraries> <PlatformToolset>v143</PlatformToolset> <CharacterSet>Unicode</CharacterSet> </PropertyGroup> <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Release|Win32'" Label="Configuration"> <ConfigurationType>Application</ConfigurationType> <UseDebugLibraries>false</UseDebugLibraries> <PlatformToolset>v143</PlatformToolset> <WholeProgramOptimization>true</WholeProgramOptimization> <CharacterSet>Unicode</CharacterSet> </PropertyGroup> <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Debug|x64'" Label="Configuration"> <ConfigurationType>Application</ConfigurationType> <UseDebugLibraries>true</UseDebugLibraries> <PlatformToolset>v143</PlatformToolset> <CharacterSet>Unicode</CharacterSet> </PropertyGroup> <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Release|x64'" Label="Configuration"> <ConfigurationType>Application</ConfigurationType> <UseDebugLibraries>false</UseDebugLibraries> <PlatformToolset>v143</PlatformToolset> <WholeProgramOptimization>true</WholeProgramOptimization> <CharacterSet>Unicode</CharacterSet> </PropertyGroup> <Import Project="$(VCTargetsPath)\Microsoft.Cpp.props" /> <ImportGroup Label="ExtensionSettings"> </ImportGroup> <ImportGroup Label="Shared"> </ImportGroup> <ImportGroup Label="PropertySheets" Condition="'$(Configuration)|$(Platform)'=='Debug|Win32'"> <Import Project="$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props" Condition="exists('$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props')" Label="LocalAppDataPlatform" /> </ImportGroup> <ImportGroup Label="PropertySheets" Condition="'$(Configuration)|$(Platform)'=='Release|Win32'"> <Import Project="$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props" Condition="exists('$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props')" Label="LocalAppDataPlatform" /> </ImportGroup> <ImportGroup Label="PropertySheets" Condition="'$(Configuration)|$(Platform)'=='Debug|x64'"> <Import Project="$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props" Condition="exists('$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props')" Label="LocalAppDataPlatform" /> </ImportGroup> <ImportGroup Label="PropertySheets" Condition="'$(Configuration)|$(Platform)'=='Release|x64'"> <Import Project="$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props" Condition="exists('$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props')" Label="LocalAppDataPlatform" /> </ImportGroup> <PropertyGroup Label="UserMacros" /> <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Debug|Win32'"> <OutDir>$(SolutionDir)..\build\msvc\$(Platform)\$(Configuration)\</OutDir> <IntDir>build\$(Platform)\$(Configuration)\</IntDir> </PropertyGroup> <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Release|Win32'"> <OutDir>$(SolutionDir)..\build\msvc\$(Platform)\$(Configuration)\</OutDir> <IntDir>build\$(Platform)\$(Configuration)\</IntDir> </PropertyGroup> <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Debug|x64'"> <OutDir>$(SolutionDir)..\build\msvc\$(Platform)\$(Configuration)\</OutDir> <IntDir>build\$(Platform)\$(Configuration)\</IntDir> </PropertyGroup> <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Release|x64'"> <OutDir>$(SolutionDir)..\build\msvc\$(Platform)\$(Configuration)\</OutDir> <IntDir>build\$(Platform)\$(Configuration)\</IntDir> </PropertyGroup> <ItemDefinitionGroup Condition="'$(Configuration)|$(Platform)'=='Debug|Win32'"> <ClCompile> <WarningLevel>Level3</WarningLevel> <SDLCheck>true</SDLCheck> <PreprocessorDefinitions>WIN32;_DEBUG;_CONSOLE;_CRT_SECURE_NO_WARNINGS;%(PreprocessorDefinitions)</PreprocessorDefinitions> <ConformanceMode>true</ConformanceMode> <LanguageStandard_C>stdc17</LanguageStandard_C> <AdditionalIncludeDirectories>$(SolutionDir)..\src\</AdditionalIncludeDirectories> <CompileAs>CompileAsC</CompileAs> </ClCompile> <Link> <SubSystem>Console</SubSystem> <GenerateDebugInformation>true</GenerateDebugInformation> <AdditionalLibraryDirectories>$(OutputPath)</AdditionalLibraryDirectories> <AdditionalDependencies>libucx.lib;$(CoreLibraryDependencies);%(AdditionalDependencies)</AdditionalDependencies> </Link> </ItemDefinitionGroup> <ItemDefinitionGroup Condition="'$(Configuration)|$(Platform)'=='Release|Win32'"> <ClCompile> <WarningLevel>Level3</WarningLevel> <FunctionLevelLinking>true</FunctionLevelLinking> <IntrinsicFunctions>true</IntrinsicFunctions> <SDLCheck>true</SDLCheck> <PreprocessorDefinitions>WIN32;NDEBUG;_CONSOLE;_CRT_SECURE_NO_WARNINGS;%(PreprocessorDefinitions)</PreprocessorDefinitions> <ConformanceMode>true</ConformanceMode> <LanguageStandard_C>stdc17</LanguageStandard_C> <AdditionalIncludeDirectories>$(SolutionDir)..\src\</AdditionalIncludeDirectories> <CompileAs>CompileAsC</CompileAs> </ClCompile> <Link> <SubSystem>Console</SubSystem> <EnableCOMDATFolding>true</EnableCOMDATFolding> <OptimizeReferences>true</OptimizeReferences> <GenerateDebugInformation>true</GenerateDebugInformation> <AdditionalLibraryDirectories>$(OutputPath)</AdditionalLibraryDirectories> <AdditionalDependencies>libucx.lib;$(CoreLibraryDependencies);%(AdditionalDependencies)</AdditionalDependencies> </Link> </ItemDefinitionGroup> <ItemDefinitionGroup Condition="'$(Configuration)|$(Platform)'=='Debug|x64'"> <ClCompile> <WarningLevel>Level3</WarningLevel> <SDLCheck>true</SDLCheck> <PreprocessorDefinitions>_DEBUG;_CONSOLE;_CRT_SECURE_NO_WARNINGS;%(PreprocessorDefinitions)</PreprocessorDefinitions> <ConformanceMode>true</ConformanceMode> <LanguageStandard_C>stdc17</LanguageStandard_C> <AdditionalIncludeDirectories>$(SolutionDir)..\src\</AdditionalIncludeDirectories> <CompileAs>CompileAsC</CompileAs> </ClCompile> <Link> <SubSystem>Console</SubSystem> <GenerateDebugInformation>true</GenerateDebugInformation> <AdditionalLibraryDirectories>$(OutputPath)</AdditionalLibraryDirectories> <AdditionalDependencies>libucx.lib;$(CoreLibraryDependencies);%(AdditionalDependencies)</AdditionalDependencies> </Link> </ItemDefinitionGroup> <ItemDefinitionGroup Condition="'$(Configuration)|$(Platform)'=='Release|x64'"> <ClCompile> <WarningLevel>Level3</WarningLevel> <FunctionLevelLinking>true</FunctionLevelLinking> <IntrinsicFunctions>true</IntrinsicFunctions> <SDLCheck>true</SDLCheck> <PreprocessorDefinitions>NDEBUG;_CONSOLE;_CRT_SECURE_NO_WARNINGS;%(PreprocessorDefinitions)</PreprocessorDefinitions> <ConformanceMode>true</ConformanceMode> <LanguageStandard_C>stdc17</LanguageStandard_C> <AdditionalIncludeDirectories>$(SolutionDir)..\src\</AdditionalIncludeDirectories> <CompileAs>CompileAsC</CompileAs> </ClCompile> <Link> <SubSystem>Console</SubSystem> <EnableCOMDATFolding>true</EnableCOMDATFolding> <OptimizeReferences>true</OptimizeReferences> <GenerateDebugInformation>true</GenerateDebugInformation> <AdditionalLibraryDirectories>$(OutputPath)</AdditionalLibraryDirectories> <AdditionalDependencies>libucx.lib;$(CoreLibraryDependencies);%(AdditionalDependencies)</AdditionalDependencies> </Link> </ItemDefinitionGroup> <Import Project="$(VCTargetsPath)\Microsoft.Cpp.targets" /> <ImportGroup Label="ExtensionTargets"> </ImportGroup> </Project>