8f913b6793186335504b952aa8add7af3f29b91dvboxsync/* $Id$ */
8f913b6793186335504b952aa8add7af3f29b91dvboxsync/** @file
8f913b6793186335504b952aa8add7af3f29b91dvboxsync * IPRT - RTSortIsSorted.
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/*******************************************************************************
8f913b6793186335504b952aa8add7af3f29b91dvboxsync* Header Files *
8f913b6793186335504b952aa8add7af3f29b91dvboxsync*******************************************************************************/
8f913b6793186335504b952aa8add7af3f29b91dvboxsync#include "internal/iprt.h"
8f913b6793186335504b952aa8add7af3f29b91dvboxsync#include <iprt/sort.h>
8f913b6793186335504b952aa8add7af3f29b91dvboxsync
8f913b6793186335504b952aa8add7af3f29b91dvboxsync
8f913b6793186335504b952aa8add7af3f29b91dvboxsync
8f913b6793186335504b952aa8add7af3f29b91dvboxsyncRTDECL(void) RTSortApvShell(void **papvArray, size_t cElements, PFNRTSORTCMP pfnCmp, void *pvUser)
8f913b6793186335504b952aa8add7af3f29b91dvboxsync{
8f913b6793186335504b952aa8add7af3f29b91dvboxsync /* Anything worth sorting? */
8f913b6793186335504b952aa8add7af3f29b91dvboxsync if (cElements < 2)
8f913b6793186335504b952aa8add7af3f29b91dvboxsync return;
8f913b6793186335504b952aa8add7af3f29b91dvboxsync
8f913b6793186335504b952aa8add7af3f29b91dvboxsync size_t cGap = (cElements + 1) / 2;
8f913b6793186335504b952aa8add7af3f29b91dvboxsync while (cGap > 0)
8f913b6793186335504b952aa8add7af3f29b91dvboxsync {
8f913b6793186335504b952aa8add7af3f29b91dvboxsync size_t i;
8f913b6793186335504b952aa8add7af3f29b91dvboxsync for (i = cGap; i < cElements; i++)
8f913b6793186335504b952aa8add7af3f29b91dvboxsync {
8f913b6793186335504b952aa8add7af3f29b91dvboxsync void *pvTmp = papvArray[i];
8f913b6793186335504b952aa8add7af3f29b91dvboxsync size_t j = i;
8f913b6793186335504b952aa8add7af3f29b91dvboxsync while ( j >= cGap
8f913b6793186335504b952aa8add7af3f29b91dvboxsync && pfnCmp(papvArray[j - cGap], pvTmp, pvUser) > 0)
8f913b6793186335504b952aa8add7af3f29b91dvboxsync {
8f913b6793186335504b952aa8add7af3f29b91dvboxsync papvArray[j] = papvArray[j - cGap];
8f913b6793186335504b952aa8add7af3f29b91dvboxsync j -= cGap;
8f913b6793186335504b952aa8add7af3f29b91dvboxsync }
8f913b6793186335504b952aa8add7af3f29b91dvboxsync papvArray[j] = pvTmp;
8f913b6793186335504b952aa8add7af3f29b91dvboxsync }
8f913b6793186335504b952aa8add7af3f29b91dvboxsync
8f913b6793186335504b952aa8add7af3f29b91dvboxsync /* This does not generate the most optimal gap sequence, but it has the
8f913b6793186335504b952aa8add7af3f29b91dvboxsync advantage of being simple and avoid floating point. */
8f913b6793186335504b952aa8add7af3f29b91dvboxsync cGap /= 2;
8f913b6793186335504b952aa8add7af3f29b91dvboxsync }
8f913b6793186335504b952aa8add7af3f29b91dvboxsync}
8f913b6793186335504b952aa8add7af3f29b91dvboxsync