Quelle test_stack.c Sprache: C

/*
* Copyright (c) 2005 Hewlett-Packard Development Company, L.P.
*
* This file may be redistributed and/or modified under the
* terms of the GNU General Public License as published by the Free Software
* Foundation; either version 2, or (at your option) any later version.
*
* It is distributed in the hope that it will be useful, but WITHOUT ANY
* WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
* FOR A PARTICULAR PURPOSE.  See the GNU General Public License in the
* file COPYING for more details.
*/

#if defined(HAVE_CONFIG_H)
# include "config.h"
#endif

#include <stdio.h>

#if defined(__vxworks)

  int main(void)
  {
    printf("test skipped\n");
    return 0;
  }

#else

#if ((defined(_WIN32) && !defined(__CYGWIN32__) && !defined(__CYGWIN__)) \
     || defined(_MSC_VER) || defined(_WIN32_WINCE)) \
    && !defined(AO_USE_WIN32_PTHREADS)
# define USE_WINTHREADS
#endif

#ifdef USE_WINTHREADS
# include <windows.h>
#else
# include <pthread.h>
#endif

#include <stdlib.h>

#include "atomic_ops_stack.h" /* includes atomic_ops.h as well */

#if (defined(_WIN32_WCE) || defined(__MINGW32CE__)) && !defined(AO_HAVE_abort)
# define abort() _exit(-1) /* there is no abort() in WinCE */
#endif

#ifndef MAX_NTHREADS
# define MAX_NTHREADS 100
#endif

#ifndef DEFAULT_NTHREADS
# define DEFAULT_NTHREADS 16 /* must be <= MAX_NTHREADS */
#endif

#ifdef NO_TIMES
# define get_msecs() 0
#elif (defined(USE_WINTHREADS) || defined(AO_USE_WIN32_PTHREADS)) \
      && !defined(CPPCHECK)
# include <sys/timeb.h>
  unsigned long get_msecs(void)
  {
    struct timeb tb;

    ftime(&tb);
    return (unsigned long)tb.time * 1000 + tb.millitm;
  }
#else /* Unix */
# include <time.h>
# include <sys/time.h>
  unsigned long get_msecs(void)
  {
    struct timeval tv;

    gettimeofday(&tv, 0);
    return (unsigned long)tv.tv_sec * 1000 + tv.tv_usec/1000;
  }
#endif /* !NO_TIMES */

typedef struct le {
  AO_t next;
  int data;
} list_element;

AO_stack_t the_list = AO_STACK_INITIALIZER;

void add_elements(int n)
{
  list_element * le;
  if (n == 0) return;
  add_elements(n-1);
  le = (list_element *)malloc(sizeof(list_element));
  if (le == 0)
    {
      fprintf(stderr, "Out of memory\n");
      exit(2);
    }
  le -> data = n;
  AO_stack_push(&the_list, (AO_t *)le);
}

#ifdef VERBOSE
void print_list(void)
{
  list_element *p;

  for (p = (list_element *)AO_REAL_HEAD_PTR(the_list);
       p != 0;
       p = (list_element *)AO_REAL_NEXT_PTR(p -> next))
    printf("%d\n", p -> data);
}
#endif /* VERBOSE */

static char marks[MAX_NTHREADS * (MAX_NTHREADS + 1) / 2 + 1];

void check_list(int n)
{
  list_element *p;
  int i;

  for (i = 1; i <= n; ++i) marks[i] = 0;

  for (p = (list_element *)AO_REAL_HEAD_PTR(the_list);
       p != 0;
       p = (list_element *)AO_REAL_NEXT_PTR(p -> next))
    {
      i = p -> data;
      if (i > n || i <= 0)
        {
          fprintf(stderr, "Found erroneous list element %d\n", i);
          abort();
        }
      if (marks[i] != 0)
        {
          fprintf(stderr, "Found duplicate list element %d\n", i);
          abort();
        }
      marks[i] = 1;
    }

  for (i = 1; i <= n; ++i)
    if (marks[i] != 1)
      {
        fprintf(stderr, "Missing list element %d\n", i);
        abort();
      }
}

volatile AO_t ops_performed = 0;

#ifndef LIMIT
        /* Total number of push/pop ops in all threads per test.    */
# ifdef AO_USE_PTHREAD_DEFS
#   define LIMIT 20000
# else
#   define LIMIT 1000000
# endif
#endif

#ifdef AO_HAVE_fetch_and_add
# define fetch_and_add(addr, val) AO_fetch_and_add(addr, val)
#else
  /* Fake it.  This is really quite unacceptable for timing */
  /* purposes.  But as a correctness test, it should be OK. */
  AO_INLINE AO_t fetch_and_add(volatile AO_t * addr, AO_t val)
  {
    AO_t result = AO_load(addr);
    AO_store(addr, result + val);
    return result;
  }
#endif

#ifdef USE_WINTHREADS
  DWORD WINAPI run_one_test(LPVOID arg)
#else
  void * run_one_test(void * arg)
#endif
{
  list_element * t[MAX_NTHREADS + 1];
  unsigned index = (unsigned)(size_t)arg;
  unsigned i;
# ifdef VERBOSE
    unsigned j = 0;

    printf("starting thread %u\n", index);
# endif
  while (fetch_and_add(&ops_performed, index + 1) + index + 1 < LIMIT)
    {
      for (i = 0; i <= index; ++i)
        {
          t[i] = (list_element *)AO_stack_pop(&the_list);
          if (0 == t[i])
            {
              fprintf(stderr, "FAILED\n");
              abort();
            }
        }
      for (i = 0; i <= index; ++i)
        {
          AO_stack_push(&the_list, (AO_t *)t[i]);
        }
#     ifdef VERBOSE
        j += index + 1;
#     endif
    }
# ifdef VERBOSE
    printf("finished thread %u: %u total ops\n", index, j);
# endif
  return 0;
}

#ifndef N_EXPERIMENTS
# define N_EXPERIMENTS 1
#endif

unsigned long times[MAX_NTHREADS + 1][N_EXPERIMENTS];

int main(int argc, char **argv)
{
  int nthreads;
  int max_nthreads;
  int exper_n;

  if (1 == argc)
    {
      max_nthreads = DEFAULT_NTHREADS;
    }
  else if (2 == argc)
    {
      max_nthreads = atoi(argv[1]);
      if (max_nthreads < 1 || max_nthreads > MAX_NTHREADS)
        {
          fprintf(stderr, "Invalid max # of threads argument\n");
          exit(1);
        }
    }
  else
    {
      fprintf(stderr, "Usage: %s [max # of threads]\n", argv[0]);
      exit(1);
    }
  for (exper_n = 0; exper_n < N_EXPERIMENTS; ++ exper_n)
    for (nthreads = 1; nthreads <= max_nthreads; ++nthreads)
      {
        unsigned i;
#       ifdef USE_WINTHREADS
          DWORD thread_id;
          HANDLE thread[MAX_NTHREADS];
#       else
          pthread_t thread[MAX_NTHREADS];
#       endif
        int list_length = nthreads*(nthreads+1)/2;
        unsigned long start_time;
        list_element * le;

#       ifdef VERBOSE
          printf("Before add_elements: exper_n=%d, nthreads=%d,"
                 " max_nthreads=%d, list_length=%d\n",
                 exper_n, nthreads, max_nthreads, list_length);
#       endif
        add_elements(list_length);
#       ifdef VERBOSE
          printf("Initial list (nthreads = %d):\n", nthreads);
          print_list();
#       endif
        ops_performed = 0;
        start_time = get_msecs();
        for (i = 1; (int)i < nthreads; ++i) {
          int code;

#         ifdef USE_WINTHREADS
            thread[i] = CreateThread(NULL, 0, run_one_test, (LPVOID)(size_t)i,
                                     0, &thread_id);
            code = thread[i] != NULL ? 0 : (int)GetLastError();
#         else
            code = pthread_create(&thread[i], 0, run_one_test,
                                  (void *)(size_t)i);
#         endif
          if (code != 0) {
            fprintf(stderr, "Thread creation failed %u\n", (unsigned)code);
            exit(3);
          }
        }
        /* We use the main thread to run one test.  This allows gprof   */
        /* profiling to work, for example.                              */
        run_one_test(0);
        for (i = 1; (int)i < nthreads; ++i) {
          int code;

#         ifdef USE_WINTHREADS
            code = WaitForSingleObject(thread[i], INFINITE) == WAIT_OBJECT_0 ?
                        0 : (int)GetLastError();
#         else
            code = pthread_join(thread[i], 0);
#         endif
          if (code != 0) {
            fprintf(stderr, "Thread join failed %u\n", (unsigned)code);
            abort();
          }
        }
        times[nthreads][exper_n] = get_msecs() - start_time;
#       ifdef VERBOSE
          printf("nthreads=%d, time_ms=%lu\n",
                 nthreads, times[nthreads][exper_n]);
          printf("final list (should be reordered initial list):\n");
          print_list();
#       endif
        check_list(list_length);
        while ((le = (list_element *)AO_stack_pop(&the_list)) != 0)
          free(le);
      }

  for (nthreads = 1; nthreads <= max_nthreads; ++nthreads)
      {
#       ifndef NO_TIMES
          unsigned long sum = 0;
#       endif

        printf("About %d pushes + %d pops in %d threads:",
               LIMIT, LIMIT, nthreads);
#       ifndef NO_TIMES
          for (exper_n = 0; exper_n < N_EXPERIMENTS; ++exper_n) {
#           ifdef VERBOSE
              printf(" [%lums]", times[nthreads][exper_n]);
#           endif
            sum += times[nthreads][exper_n];
          }
          printf(" %lu msecs\n", (sum + N_EXPERIMENTS/2)/N_EXPERIMENTS);
#       else
          printf(" completed\n");
#       endif
      }
  return 0;
}

#endif

quality96%

¤ Dauer der Verarbeitung: 0.12 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.