Home Libraries Author Links

dsettst.c

This example C program demonstrates the usage and tests the implementation of abstract set, multiset, map and multimap types modelling associative containers (see Dset: Associative Set and Map Containers).

/* ***** BEGIN LICENSE BLOCK *****
 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
 *
 * The contents of this file are subject to the Mozilla Public License Version
 * 1.1 (the "License"); you may not use this file except in compliance with
 * the License. You may obtain a copy of the License at
 * http://www.mozilla.org/MPL/
 *
 * Software distributed under the License is distributed on an "AS IS" basis,
 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
 * for the specific language governing rights and limitations under the
 * License.
 *
 * The Original Code is the SysToMath C Libraries package (LibStmC).
 *
 * The Initial Developer of the Original Code is
 * Tom Michaelis, SysToMath.
 * Portions created by the Initial Developer are Copyright (C) 2000-2006
 * the Initial Developer. All Rights Reserved.
 *
 * Contributor(s):
 *
 * Alternatively, the contents of this file may be used under the terms of
 * either the GNU General Public License Version 2 or later (the "GPL"), or
 * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
 * in which case the provisions of the GPL or the LGPL are applicable instead
 * of those above. If you wish to allow use of your version of this file only
 * under the terms of either the GPL or the LGPL, and not to allow others to
 * use your version of this file under the terms of the MPL, indicate your
 * decision by deleting the provisions above and replace them with the notice
 * and other provisions required by the GPL or the LGPL. If you do not delete
 * the provisions above, a recipient may use your version of this file under
 * the terms of any one of the MPL, the GPL or the LGPL.
 *
 * ***** END LICENSE BLOCK ***** */

/******************************************************************************
 *                       First Release 2000-07-15
 ******************************************************************************/


const char *Copyright = "(C) 2000-2006 Tom Michaelis, SysToMath";
const char *Version   = "1.12-r341";

static const char *man [] =
{
"NAME                                                                         ",
"       dsettst - sample for usage and test of abstract set and map types     ",
"                                                                             ",
"SYNOPSIS                                                                     ",
"       dsettst [--silent] [--append]                                         ",
"               [--output=<file>] [--count=<number>] [--tests=<number>]       ",
"       dsettst --help [<option-name>...]                                     ",
"       dsettst --version                                                     ",
"                                                                             ",
"DESCRIPTION                                                                  ",
"       The command creates an object of each of the abstract container types "
"       set, multiset, map and multimap, fills it with random values and      "
"       finally deletes some of these values in random order.                 ",
"       During the fill and delete operations some consistency checks for the "
"       container objects are performed.                                      ",
"                                                                             ",
"OPTIONS                                                                      ",
"       --help                                                                ",
"       -h     If no argument <option-name> follows, print the command man    "
"              page on standard output, else the description of the options   "
"              <option-name> and exit with exit code 2.  The arguments        "
"              <option-name> shall be stated without leading '-' or '--'.     ",
"                                                                             ",
"       --version                                                             ",
"       -V     Print version info on standard output and exit with exit code  "
"              2.                                                             ",
"                                                                             ",
"       --silent                                                              ",
"       -s     Suppress all messages on stdout.                               ",
"                                                                             ",
"       --append                                                              ",
"       -a     If output is redirected to a file (see option --output),       "
"              instead of deleting the file, if it exists already, append to  "
"              it.                                                            ",
"                                                                             ",
"       --output=<file>                                                       ",
"       -o <file>                                                             ",
"              Generate the output additionally to stdout in <file>.  By      "
"              default, no additional output is generated.                    ",
"                                                                             ",
"       --count=<number>                                                      ",
"       -c <number>                                                           ",
"              Fill the abstract container objects with 2*<number> values and "
"              then delete <number> values.  By default <number> is 1000.     ",
"                                                                             ",
"       --tests=<number>                                                      ",
"       -t <number>                                                           ",
"              Do the tests <number> times.  By default <number> is 1.        "
};


#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <time.h>
#include <limits.h>
#include <stm/basetype.h>
#include <stm/getopts.h>
#include <stm/dset.h>


#define dsetAssert(cond)                                                       \
if (! (cond))                                                                  \
{                                                                              \
    if (!silent) printf ("line %d: '" #cond "' failed\n", __LINE__);           \
    exit (__LINE__);                                                           \
}                                                                              \


static void dsetPrintf (const char *format, ...);


static void dsetShowf (const char *format, ...);


static int randomInt (int minval, int maxval);


int main (int argc, char **argv);


static StmBool silent = StmFalse;


static FILE *os = NULL;


stm_static_inline int elemCmp (const int *pEl1, const int *pEl2);


stm_static_inline int keyCmp (int key1, int key2);


StmSetTypeDefine (int, elemCmp)  /* SampleSet */



StmMultiSetTypeDefine (int, elemCmp)  /* SampleMultiSet */


StmMapTypeDefine (Nr, int, int, keyCmp)  /* SampleMap */


StmMultiMapTypeDefine (MultiNr, int, int, keyCmp)  /* SampleMultiMap */


int main (int argc, char **argv)
{
    /* Evaluate command line options. */
    int t, tests = 1, count = 1000;
    StmBool appendFlag = StmFalse;
    StmDword optId;
    StmCmdOptSpec optSpec [] =
    {
        {StmId (h), "h\0help\0", StmCmdOptSpecOnlyOption},
        {StmId (V), "V\0version\0", StmCmdOptSpecOnlyOption},
        {StmId (s), "s\0silent\0"},
        {StmId (a), "a\0append\0"},
        {StmId (o), "o\0output\0", StmCmdOptSpecRequiresArg},
        {StmId (c), "c\0count\0", StmCmdOptSpecRequiresArg},
        {StmId (t), "t\0tests\0", StmCmdOptSpecRequiresArg},
        {0, NULL}
    };
    StmCmdLine cmdLine = stmCmdLineCreate (argc, (const char **) argv, optSpec);
    const char *prog = stmCmdLineGetProg (cmdLine);
    const char *helpMode = NULL;
    StmBool printVersion = StmFalse;
    stmCmdLineSetErrfp (cmdLine, stderr);
    for (optId = stmCmdLineGetFirstOptionId (cmdLine);
         optId;
         optId = stmCmdLineGetNextOptionId (cmdLine))
    {
        if (optId == StmId (h))
        {
            helpMode = stmCmdLineGetCurrentOptionName (cmdLine);
            continue;
        }
        if (optId == StmId (V))
        {
            printVersion = StmTrue;
            continue;
        }
        if (optId == StmId (s))
        {
            silent = StmTrue;
            continue;
        }
        if (optId == StmId (a))
        {
            appendFlag = StmTrue;
            continue;
        }
        if (optId == StmId (o))
        {
            const char *optarg = stmCmdLineGetCurrentOptionArg (cmdLine);
            assert (optarg);
            if (! (os = fopen (optarg, appendFlag ? "a" : "w")))
            {
                fprintf (stderr,
                         "%s: option %s: cannot open output file %s\n",
                         prog,
                         stmCmdLineGetCurrentOptionName (cmdLine),
                         optarg);
                stmCmdLineSetError (cmdLine, StmCmdLineOptionArgError);
            }
            continue;
        }
        if (optId == StmId (c))
        {
            const char *optarg = stmCmdLineGetCurrentOptionArg (cmdLine);
            char *end;
            long ll;
            assert (optarg);
            ll = strtol (optarg, &end, 10);
            if (*end || ll < 1 || ll > INT_MAX)
            {
                fprintf (stderr,
                         "%s: option %s: illegal option argument: %s\n",
                         prog,
                         stmCmdLineGetCurrentOptionName (cmdLine),
                         optarg);
                stmCmdLineSetError (cmdLine, StmCmdLineOptionArgError);
            }
            count = (int) ll;
            continue;
        }
        if (optId == StmId (t))
        {
            const char *optarg = stmCmdLineGetCurrentOptionArg (cmdLine);
            char *end;
            long ll;
            assert (optarg);
            ll = strtol (optarg, &end, 10);
            if (*end || ll < 1 || ll > INT_MAX)
            {
                fprintf (stderr,
                         "%s: option %s: illegal option argument: %s\n",
                         prog,
                         stmCmdLineGetCurrentOptionName (cmdLine),
                         optarg);
                stmCmdLineSetError (cmdLine, StmCmdLineOptionArgError);
            }
            tests = (int) ll;
            continue;
        }
    }

    /* Exit on option error. */
    if (stmCmdLineGetError (cmdLine))
    {
        stmPrintSynopsis (stderr, 79, StmElements (man), man);
        return 1;
    }

    /* Handle help mode. */
    if (helpMode)
    {
        int ret = 2;
        FILE *pp;
        if (! (pp = popen ("more", "w")))
        {
            fprintf (stderr, "popen failed: aborted\n");
            exit (1);
        }
        if (stmCmdLineGetCurrentArgIndex (cmdLine) ==
            stmCmdLineGetArgCount (cmdLine))
        {
            ret = 
                stmPrintManual (pp, 79,
                                Version, Copyright, StmElements (man), man) < 0 ?
                    1 :  /* Error.   */
                    2;   /* Success. */
        }
        else
        {
            if ((ret = stmPrintManualHeader (pp, 79, Version, StmElements (man), man)) >= 0 &&
                (ret = stmPrintSynopsis (pp, 79, StmElements (man), man)) >= 0)
            {
                StmBool first = StmTrue;
                size_t i;
                for (i = stmCmdLineGetCurrentArgIndex (cmdLine);
                     i < stmCmdLineGetArgCount (cmdLine);
                     ++ i)
                {
                    fprintf (pp, "\n");
                    if (first)
                    {
                        fprintf (pp, "OPTIONS HELP\n");
                        first = StmFalse;
                    }
                    if ((ret = stmPrintOptionHelp (pp, 79,
                                                   stmCmdLineGetArg (cmdLine, i),
                                                   StmElements (man), man)) < 0)
                    {
                        break;
                    }
                }
            }
            ret =
                ret < 0 || (ret = stmPrintManualFooter (pp, 79, ret, Copyright)) < 0 ?
                    1 :  /* Error.   */
                    2;   /* Success. */
        }
        if (pclose (pp))
        {
            fprintf (stderr, "pclose failed: aborted\n");
            exit (1);
        }
        return ret;
    }

    /* Handle print version */
    if (printVersion)
    {
        fprintf (stdout, "%s\n", Version);
        exit (2);
    }

    /* Exit on argument error. */
    if (stmCmdLineGetArgCount (cmdLine) != stmCmdLineGetCurrentArgIndex (cmdLine))
    {
        fprintf (stderr,
                 "%s: ambigous arguments\n",
                 prog);
        stmPrintSynopsis (stderr, 79, StmElements (man), man);
        exit (1);
    }

    /* Do command operation. */
    srand ((unsigned int) clock () ^
           (unsigned int) (time (NULL) % (rand () + 1)));
    for (t = 0; t < tests; ++ t)
    {
        int c, cc = 2 * count;
        intStmSetIterator setIt;
        intStmMultiSetIterator multiSetIt;
        NrStmMapIterator mapIt;
        MultiNrStmMultiMapIterator multiMapIt;
        intStmSet set = intStmSetCreate ();
        intStmMultiSet multiSet = intStmMultiSetCreate ();
        NrStmMap map = NrStmMapCreate ();
        MultiNrStmMultiMap multiMap = MultiNrStmMultiMapCreate ();
        Nr *nrVec = (Nr *) malloc (cc * sizeof (Nr));
        Nr *nrMultiVec = (Nr *) malloc (cc * sizeof (Nr));
        dsetPrintf ("test %d of %d:\n", t + 1, tests);
        dsetAssert (set && multiSet && map && multiMap && nrVec && nrMultiVec);
        dsetPrintf ("  inserting 2 * %d = %d random elements: ", count, cc);
        for (c = 0; c < cc; ++ c)
        {
            StmBool inserted = StmFalse;
            Nr nr;
            int key = randomInt (-cc, cc);
            nr.key = key;
            nr.val = c;
            intStmMultiSetInsert (multiSet, &key);
            MultiNrStmMultiMapInsert (multiMap, (MultiNr *) &nr);
            nrMultiVec [c] = nr;
            while (!inserted)
            {
                key = nr.key = randomInt (-cc, cc);
                intStmSetInsert (set, &key, NULL);
                NrStmMapInsert (map, &nr, &inserted);
            }
            nrVec [c] = nr;
            if ((c + 1) % 10 == 0) dsetShowf ("%d", c + 1);
        }
        dsetShowf ("                        ");
        dsetPrintf ("OK\n");
        dsetAssert (intStmSetSize (set) == cc);
        dsetAssert (intStmMultiSetSize (multiSet) == cc);
        dsetAssert (NrStmMapSize (map) == cc);
        dsetAssert (MultiNrStmMultiMapSize (multiMap) == cc);
        dsetPrintf ("  sorting %d elements of test vector: ", cc);
        dsetShowf ("nrVec");
        qsort (nrVec, cc, sizeof (Nr), NrStmMapCmp_);
        dsetShowf ("nrMultiVec");
        qsort (nrMultiVec, cc, sizeof (Nr), NrStmMapCmp_);
        dsetShowf ("              ");
        dsetPrintf ("OK\n");
        dsetPrintf ("  testing %d elements: ", cc);
        dsetShowf ("intStmSet");
        for (c = 0, setIt = intStmSetBegin (set);
             c < cc && setIt != intStmSetEnd (set);
             ++ c, setIt = intStmSetIteratorNext (setIt))
        {
            dsetAssert (*intStmSetIteratorElem (setIt) == nrVec [c].key);
        }
        dsetAssert (c == cc);
        dsetShowf ("NrStmMap ");
        for (c = 0, mapIt = NrStmMapBegin (map);
             c < cc && mapIt != NrStmMapEnd (map);
             ++ c, mapIt = NrStmMapIteratorNext (mapIt))
        {
            dsetAssert (NrStmMapIteratorKey (mapIt) == nrVec [c].key);
        }
        dsetAssert (c == cc);
        dsetShowf ("intStmMultiSet");
        for (c = 0, multiSetIt = intStmMultiSetBegin (multiSet);
             c < cc && multiSetIt != intStmMultiSetEnd (multiSet);
             ++ c, multiSetIt = intStmMultiSetIteratorNext (multiSetIt))
        {
            dsetAssert
                (*intStmMultiSetIteratorElem (multiSetIt) == nrMultiVec [c].key);
        }
        dsetAssert (c == cc);
        dsetShowf ("MultiNrStmMultiMap ");
        for (c = 0, multiMapIt = MultiNrStmMultiMapBegin (multiMap);
             c < cc && multiMapIt != MultiNrStmMultiMapEnd (multiMap);
             ++ c, multiMapIt = MultiNrStmMultiMapIteratorNext (multiMapIt))
        {
            dsetAssert
                (MultiNrStmMultiMapIteratorKey (multiMapIt) == nrMultiVec [c].key);
        }
        dsetAssert (c == cc);
        dsetShowf ("                   ");
        dsetPrintf ("OK\n");
        dsetPrintf ("  deleting %d random elements: ", count);
        for (c = 0; c < count; ++ c)
        {
            int i;
            for (i = randomInt (0, cc - 1);
                 nrVec [i].val == -1;
                 i = randomInt (0, cc - 1));
            nrVec [i].val = -1;
            dsetAssert (intStmSetEraseKey (set, nrVec [i].key) == 1);
            dsetAssert (NrStmMapEraseKey (map, nrVec [i].key) == 1);
            for (i = randomInt (0, cc - 1);
                 nrMultiVec [i].val == -1;
                 i = randomInt (0, cc - 1));
            nrMultiVec [i].val = -1;
            multiSetIt = intStmMultiSetFind (multiSet, &nrMultiVec [i].key);
            dsetAssert (multiSetIt != intStmMultiSetEnd (multiSet));
            dsetAssert (intStmMultiSetErase (multiSet, multiSetIt) == 1);
            multiMapIt = MultiNrStmMultiMapFindKey (multiMap, nrMultiVec [i].key);
            dsetAssert (multiMapIt != MultiNrStmMultiMapEnd (multiMap));
            dsetAssert (MultiNrStmMultiMapErase (multiMap, multiMapIt) == 1);
            if ((c + 1) % 10 == 0) dsetShowf ("%d", c + 1);
        }
        dsetShowf ("                      ");
        dsetPrintf ("OK\n");
        dsetAssert (intStmSetSize (set) == count);
        dsetAssert (intStmMultiSetSize (multiSet) == count);
        dsetAssert (NrStmMapSize (map) == count);
        dsetAssert (MultiNrStmMultiMapSize (multiMap) == count);
        dsetPrintf ("  testing %d elements: ", count);
        dsetShowf ("intStmSet");
        for (c = 0, setIt = intStmSetBegin (set);
             c < cc && setIt != intStmSetEnd (set);
             ++ c, setIt = intStmSetIteratorNext (setIt))
        {
            while (nrVec [c].val == -1) ++ c;
            dsetAssert (*intStmSetIteratorElem (setIt) == nrVec [c].key);
        }
        dsetAssert (setIt == intStmSetEnd (set));
        dsetShowf ("NrStmMap ");
        for (c = 0, mapIt = NrStmMapBegin (map);
             c < cc && mapIt != NrStmMapEnd (map);
             ++ c, mapIt = NrStmMapIteratorNext (mapIt))
        {
            while (nrVec [c].val == -1) ++ c;
            dsetAssert (NrStmMapIteratorKey (mapIt) == nrVec [c].key);
        }
        dsetAssert (mapIt == NrStmMapEnd (map));
        dsetShowf ("intStmMultiSet");
        for (c = 0, multiSetIt = intStmMultiSetBegin (multiSet);
             c < cc && multiSetIt != intStmMultiSetEnd (multiSet);
             ++ c, multiSetIt = intStmMultiSetIteratorNext (multiSetIt))
        {
            while (nrMultiVec [c].val == -1) ++ c;
            dsetAssert
                (*intStmMultiSetIteratorElem (multiSetIt) == nrMultiVec [c].key);
        }
        dsetAssert (multiSetIt == intStmMultiSetEnd (multiSet));
        dsetShowf ("MultiNrStmMultiMap ");
        for (c = 0, multiMapIt = MultiNrStmMultiMapBegin (multiMap);
             c < cc && multiMapIt != MultiNrStmMultiMapEnd (multiMap);
             ++ c, multiMapIt = MultiNrStmMultiMapIteratorNext (multiMapIt))
        {
            while (nrMultiVec [c].val == -1) ++ c;
            dsetAssert
                (MultiNrStmMultiMapIteratorKey (multiMapIt) == nrMultiVec [c].key);
        }
        dsetAssert (multiMapIt == MultiNrStmMultiMapEnd (multiMap));
        dsetShowf ("                   ");
        dsetPrintf ("OK\n");
        intStmSetClear (set);
        intStmMultiSetClear (multiSet);
        NrStmMapClear (map);
        MultiNrStmMultiMapClear (multiMap);
        dsetAssert (intStmSetSize (set) == 0);
        dsetAssert (intStmMultiSetSize (multiSet) == 0);
        dsetAssert (NrStmMapSize (map) == 0);
        dsetAssert (MultiNrStmMultiMapSize (multiMap) == 0);
        intStmSetDestroy (set);
        intStmMultiSetDestroy (multiSet);
        NrStmMapDestroy (map);
        MultiNrStmMultiMapDestroy (multiMap);
        free (nrVec);
        free (nrMultiVec);
    }
    stmCmdLineDestroy (cmdLine);
    return 0;
}


stm_static_inline int elemCmp (const int *pEl1, const int *pEl2)
{
    return keyCmp (*pEl1, *pEl2);
}


stm_static_inline int keyCmp (int key1, int key2)
{
    return key1 < key2 ? -1 : key1 > key2 ? 1 : 0;
}


static void dsetPrintf (const char *format, ...)
{
    va_list list;
    va_start (list, format);
    if (!silent) vfprintf (stdout, format, list);
    va_start (list, format);
    if (os) vfprintf (os, format, list);
    va_end (list);
    return;
}


static void dsetShowf (const char *format, ...)
{
    if (!silent)
    {
        int i, cnt;
        va_list list;
        va_start (list, format);
        cnt = vfprintf (stdout, format, list);
        va_end (list);
        for (i = 0; i < cnt; ++ i) printf ("\b");
        fflush (stdout);
    }
    return;
}


static int randomInt (int minval, int maxval)
{
    unsigned int ret = 0;
    unsigned int range = -minval + maxval + 1;
    int i;
    dsetAssert (minval <= maxval);
    for (i = 0; i < sizeof (int); ++ i)
    {
        int rv = rand ();
        rv *= rv;
        rv >>= 7;
        ret = (ret << StmByteBits) + (StmByte) rv;
    }
    if (range) ret %= range;
    return (int) ret + minval;
}

© Copyright Tom Michaelis 2002-2007

Distributed under the SysToMath Software License (See the accompanying file license.txt or a copy at www.SysToMath.com).