8f913b6793186335504b952aa8add7af3f29b91dvboxsync/* $Id$ */
8f913b6793186335504b952aa8add7af3f29b91dvboxsync/** @file
8f913b6793186335504b952aa8add7af3f29b91dvboxsync * IPRT Testcase - Sorting.
8f913b6793186335504b952aa8add7af3f29b91dvboxsync */
8f913b6793186335504b952aa8add7af3f29b91dvboxsync
8f913b6793186335504b952aa8add7af3f29b91dvboxsync/*
e64031e20c39650a7bc902a3e1aba613b9415deevboxsync * Copyright (C) 2010 Oracle Corporation
8f913b6793186335504b952aa8add7af3f29b91dvboxsync *
8f913b6793186335504b952aa8add7af3f29b91dvboxsync * This file is part of VirtualBox Open Source Edition (OSE), as
8f913b6793186335504b952aa8add7af3f29b91dvboxsync * available from http://www.virtualbox.org. This file is free software;
8f913b6793186335504b952aa8add7af3f29b91dvboxsync * you can redistribute it and/or modify it under the terms of the GNU
8f913b6793186335504b952aa8add7af3f29b91dvboxsync * General Public License (GPL) as published by the Free Software
8f913b6793186335504b952aa8add7af3f29b91dvboxsync * Foundation, in version 2 as it comes in the "COPYING" file of the
8f913b6793186335504b952aa8add7af3f29b91dvboxsync * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
8f913b6793186335504b952aa8add7af3f29b91dvboxsync * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
8f913b6793186335504b952aa8add7af3f29b91dvboxsync *
8f913b6793186335504b952aa8add7af3f29b91dvboxsync * The contents of this file may alternatively be used under the terms
8f913b6793186335504b952aa8add7af3f29b91dvboxsync * of the Common Development and Distribution License Version 1.0
8f913b6793186335504b952aa8add7af3f29b91dvboxsync * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
8f913b6793186335504b952aa8add7af3f29b91dvboxsync * VirtualBox OSE distribution, in which case the provisions of the
8f913b6793186335504b952aa8add7af3f29b91dvboxsync * CDDL are applicable instead of those of the GPL.
8f913b6793186335504b952aa8add7af3f29b91dvboxsync *
8f913b6793186335504b952aa8add7af3f29b91dvboxsync * You may elect to license modified versions of this file under the
8f913b6793186335504b952aa8add7af3f29b91dvboxsync * terms and conditions of either the GPL or the CDDL or both.
8f913b6793186335504b952aa8add7af3f29b91dvboxsync */
8f913b6793186335504b952aa8add7af3f29b91dvboxsync
8f913b6793186335504b952aa8add7af3f29b91dvboxsync/*******************************************************************************
8f913b6793186335504b952aa8add7af3f29b91dvboxsync* Header Files *
8f913b6793186335504b952aa8add7af3f29b91dvboxsync*******************************************************************************/
8f913b6793186335504b952aa8add7af3f29b91dvboxsync#include <iprt/sort.h>
8f913b6793186335504b952aa8add7af3f29b91dvboxsync
8f913b6793186335504b952aa8add7af3f29b91dvboxsync#include <iprt/err.h>
8f913b6793186335504b952aa8add7af3f29b91dvboxsync#include <iprt/rand.h>
8f913b6793186335504b952aa8add7af3f29b91dvboxsync#include <iprt/string.h>
8f913b6793186335504b952aa8add7af3f29b91dvboxsync#include <iprt/test.h>
8f913b6793186335504b952aa8add7af3f29b91dvboxsync
8f913b6793186335504b952aa8add7af3f29b91dvboxsync
8f913b6793186335504b952aa8add7af3f29b91dvboxsync/*******************************************************************************
8f913b6793186335504b952aa8add7af3f29b91dvboxsync* Structures and Typedefs *
8f913b6793186335504b952aa8add7af3f29b91dvboxsync*******************************************************************************/
8f913b6793186335504b952aa8add7af3f29b91dvboxsynctypedef struct TSTRTSORTAPV
8f913b6793186335504b952aa8add7af3f29b91dvboxsync{
8f913b6793186335504b952aa8add7af3f29b91dvboxsync uint32_t aValues[8192];
8f913b6793186335504b952aa8add7af3f29b91dvboxsync void *apv[8192];
8f913b6793186335504b952aa8add7af3f29b91dvboxsync size_t cElements;
8f913b6793186335504b952aa8add7af3f29b91dvboxsync} TSTRTSORTAPV;
8f913b6793186335504b952aa8add7af3f29b91dvboxsync
8f913b6793186335504b952aa8add7af3f29b91dvboxsync
8f913b6793186335504b952aa8add7af3f29b91dvboxsyncstatic DECLCALLBACK(int) testApvCompare(void const *pvElement1, void const *pvElement2, void *pvUser)
8f913b6793186335504b952aa8add7af3f29b91dvboxsync{
8f913b6793186335504b952aa8add7af3f29b91dvboxsync TSTRTSORTAPV *pData = (TSTRTSORTAPV *)pvUser;
8f913b6793186335504b952aa8add7af3f29b91dvboxsync uint32_t const *pu32Element1 = (uint32_t const *)pvElement1;
8f913b6793186335504b952aa8add7af3f29b91dvboxsync uint32_t const *pu32Element2 = (uint32_t const *)pvElement2;
8f913b6793186335504b952aa8add7af3f29b91dvboxsync RTTESTI_CHECK(VALID_PTR(pData) && pData->cElements <= RT_ELEMENTS(pData->aValues));
8f913b6793186335504b952aa8add7af3f29b91dvboxsync RTTESTI_CHECK((uintptr_t)(pu32Element1 - &pData->aValues[0]) < pData->cElements);
8f913b6793186335504b952aa8add7af3f29b91dvboxsync RTTESTI_CHECK((uintptr_t)(pu32Element2 - &pData->aValues[0]) < pData->cElements);
8f913b6793186335504b952aa8add7af3f29b91dvboxsync
8f913b6793186335504b952aa8add7af3f29b91dvboxsync if (*pu32Element1 < *pu32Element2)
8f913b6793186335504b952aa8add7af3f29b91dvboxsync return -1;
8f913b6793186335504b952aa8add7af3f29b91dvboxsync if (*pu32Element1 > *pu32Element2)
8f913b6793186335504b952aa8add7af3f29b91dvboxsync return 1;
8f913b6793186335504b952aa8add7af3f29b91dvboxsync return 0;
8f913b6793186335504b952aa8add7af3f29b91dvboxsync}
8f913b6793186335504b952aa8add7af3f29b91dvboxsync
8f913b6793186335504b952aa8add7af3f29b91dvboxsyncstatic void testApvSorter(FNRTSORTAPV pfnSorter, const char *pszName)
8f913b6793186335504b952aa8add7af3f29b91dvboxsync{
8f913b6793186335504b952aa8add7af3f29b91dvboxsync RTTestISub(pszName);
8f913b6793186335504b952aa8add7af3f29b91dvboxsync
8f913b6793186335504b952aa8add7af3f29b91dvboxsync RTRAND hRand;
8f913b6793186335504b952aa8add7af3f29b91dvboxsync RTTESTI_CHECK_RC_OK_RETV(RTRandAdvCreateParkMiller(&hRand));
8f913b6793186335504b952aa8add7af3f29b91dvboxsync
8f913b6793186335504b952aa8add7af3f29b91dvboxsync TSTRTSORTAPV Data;
8f913b6793186335504b952aa8add7af3f29b91dvboxsync for (size_t cElements = 0; cElements < RT_ELEMENTS(Data.apv); cElements++)
8f913b6793186335504b952aa8add7af3f29b91dvboxsync {
8f913b6793186335504b952aa8add7af3f29b91dvboxsync RT_ZERO(Data);
8f913b6793186335504b952aa8add7af3f29b91dvboxsync Data.cElements = cElements;
8f913b6793186335504b952aa8add7af3f29b91dvboxsync
8f913b6793186335504b952aa8add7af3f29b91dvboxsync /* popuplate the array */
8f913b6793186335504b952aa8add7af3f29b91dvboxsync for (size_t i = 0; i < cElements; i++)
8f913b6793186335504b952aa8add7af3f29b91dvboxsync {
8f913b6793186335504b952aa8add7af3f29b91dvboxsync Data.aValues[i] = RTRandAdvU32(hRand);
8f913b6793186335504b952aa8add7af3f29b91dvboxsync Data.apv[i] = &Data.aValues[i];
8f913b6793186335504b952aa8add7af3f29b91dvboxsync }
8f913b6793186335504b952aa8add7af3f29b91dvboxsync
8f913b6793186335504b952aa8add7af3f29b91dvboxsync /* sort it */
8f913b6793186335504b952aa8add7af3f29b91dvboxsync pfnSorter(&Data.apv[0], cElements, testApvCompare, &Data);
8f913b6793186335504b952aa8add7af3f29b91dvboxsync
8f913b6793186335504b952aa8add7af3f29b91dvboxsync /* verify it */
8f913b6793186335504b952aa8add7af3f29b91dvboxsync if (!RTSortApvIsSorted(&Data.apv[0], cElements, testApvCompare, &Data))
8f913b6793186335504b952aa8add7af3f29b91dvboxsync RTTestIFailed("failed sorting %u elements", cElements);
8f913b6793186335504b952aa8add7af3f29b91dvboxsync }
8f913b6793186335504b952aa8add7af3f29b91dvboxsync}
8f913b6793186335504b952aa8add7af3f29b91dvboxsync
8f913b6793186335504b952aa8add7af3f29b91dvboxsync
8f913b6793186335504b952aa8add7af3f29b91dvboxsyncint main()
8f913b6793186335504b952aa8add7af3f29b91dvboxsync{
8f913b6793186335504b952aa8add7af3f29b91dvboxsync RTTEST hTest;
8f913b6793186335504b952aa8add7af3f29b91dvboxsync int rc = RTTestInitAndCreate("tstRTTemp", &hTest);
8f913b6793186335504b952aa8add7af3f29b91dvboxsync if (rc)
8f913b6793186335504b952aa8add7af3f29b91dvboxsync return rc;
8f913b6793186335504b952aa8add7af3f29b91dvboxsync RTTestBanner(hTest);
8f913b6793186335504b952aa8add7af3f29b91dvboxsync
8f913b6793186335504b952aa8add7af3f29b91dvboxsync /*
8f913b6793186335504b952aa8add7af3f29b91dvboxsync * Test the different algorithms.
8f913b6793186335504b952aa8add7af3f29b91dvboxsync */
8f913b6793186335504b952aa8add7af3f29b91dvboxsync testApvSorter(RTSortApvShell, "RTSortApvShell - shell sort, pointer array");
8f913b6793186335504b952aa8add7af3f29b91dvboxsync
8f913b6793186335504b952aa8add7af3f29b91dvboxsync /*
8f913b6793186335504b952aa8add7af3f29b91dvboxsync * Summary.
8f913b6793186335504b952aa8add7af3f29b91dvboxsync */
8f913b6793186335504b952aa8add7af3f29b91dvboxsync return RTTestSummaryAndDestroy(hTest);
8f913b6793186335504b952aa8add7af3f29b91dvboxsync}
8f913b6793186335504b952aa8add7af3f29b91dvboxsync