Quelle misc.c Sprache: C

/****************************************************************************
**
**  This file is part of GAP, a system for computational discrete algebra.
**
**  Copyright of GAP belongs to its developers, whose names are too numerous
**  to list here. Please refer to the COPYRIGHT file for details.
**
**  SPDX-License-Identifier: GPL-2.0-or-later
*/

#include "misc.h"

#include <stdlib.h>
#include <string.h>

/****************************************************************************
**
*V  ThreadUI  . . . . . . . . . . . . . . . . . . . .  support UI for threads
**
*/
UInt ThreadUI = 1;

/****************************************************************************
**
*V  DeadlockCheck  . . . . . . . . . . . . . . . . . .  check for deadlocks
**
*/
UInt DeadlockCheck = 1;

/****************************************************************************
**
*V  SyNumGCThreads  . . . . . . . . . . . . . . . number of GC worker threads
**
*/
UInt SyNumGCThreads = 0;

/****************************************************************************
**
*V  SingleThreadStartup . . . . . . . . .  start HPC-GAP with just one thread
**
*/
UInt SingleThreadStartup = 0;

/****************************************************************************
**
*F  MergeSort helpers
**
*/

static void Merge(char * to,
                  char * from1,
                  UInt   size1,
                  char * from2,
                  UInt   size2,
                  UInt   width,
                  int (*lessThan)(const void * a, const void * b))
{
    while (size1 && size2) {
        if (lessThan(from1, from2)) {
            memcpy(to, from1, width);
            from1 += width;
            size1--;
        }
        else {
            memcpy(to, from2, width);
            from2 += width;
            size2--;
        }
        to += width;
    }
    if (size1)
        memcpy(to, from1, size1 * width);
    else
        memcpy(to, from2, size2 * width);
}

static void MergeSortRecurse(char * data,
                             char * aux,
                             UInt   count,
                             UInt   width,
                             int (*lessThan)(const void * a, const void *))
{
    UInt nleft, nright;
    // assert(count > 1);
    if (count == 2) {
        if (!lessThan(data, data + width)) {
            memcpy(aux, data, width);
            memcpy(data, data + width, width);
            memcpy(data + width, aux, width);
        }
        return;
    }
    nleft = count / 2;
    nright = count - nleft;
    if (nleft > 1)
        MergeSortRecurse(data, aux, nleft, width, lessThan);
    if (nright > 1)
        MergeSortRecurse(data + nleft * width, aux + nleft * width, nright,
                         width, lessThan);
    memcpy(aux, data, count * width);
    Merge(data, aux, nleft, aux + nleft * width, nright, width, lessThan);
}

/****************************************************************************
**
*F  MergeSort() . . . . . . . . . . . . . . . sort an array using mergesort.
**
**  MergeSort() sorts an array of 'count' elements of individual size 'width'
**  with ordering determined by the parameter 'lessThan'. The 'lessThan'
**  function is to return a non-zero value if the first argument is less
**  than the second argument, zero otherwise.
*/

void MergeSort(void * data,
               UInt   count,
               UInt   width,
               int (*lessThan)(const void * a, const void *))
{
    char * aux = alloca(count * width);
    if (count > 1)
        MergeSortRecurse(data, aux, count, width, lessThan);
}

quality95%

¤ Dauer der Verarbeitung: 0.20 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.