OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-stable/] [gcc-4.5.1/] [libstdc++-v3/] [include/] [parallel/] [queue.h] - Blame information for rev 841

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 424 jeremybenn
// -*- C++ -*-
2
 
3
// Copyright (C) 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
4
//
5
// This file is part of the GNU ISO C++ Library.  This library is free
6
// software; you can redistribute it and/or modify it under the terms
7
// of the GNU General Public License as published by the Free Software
8
// Foundation; either version 3, or (at your option) any later
9
// version.
10
 
11
// This library is distributed in the hope that it will be useful, but
12
// WITHOUT ANY WARRANTY; without even the implied warranty of
13
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14
// General Public License for more details.
15
 
16
// Under Section 7 of GPL version 3, you are granted additional
17
// permissions described in the GCC Runtime Library Exception, version
18
// 3.1, as published by the Free Software Foundation.
19
 
20
// You should have received a copy of the GNU General Public License and
21
// a copy of the GCC Runtime Library Exception along with this program;
22
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23
// <http://www.gnu.org/licenses/>.
24
 
25
/** @file parallel/queue.h
26
 *  @brief Lock-free double-ended queue.
27
 *  This file is a GNU parallel extension to the Standard C++ Library.
28
 */
29
 
30
// Written by Johannes Singler.
31
 
32
#ifndef _GLIBCXX_PARALLEL_QUEUE_H
33
#define _GLIBCXX_PARALLEL_QUEUE_H 1
34
 
35
#include <parallel/types.h>
36
#include <parallel/base.h>
37
#include <parallel/compatibility.h>
38
 
39
/** @brief Decide whether to declare certain variable volatile in this file. */
40
#define _GLIBCXX_VOLATILE volatile
41
 
42
namespace __gnu_parallel
43
{
44
  /**@brief Double-ended queue of bounded size, allowing lock-free
45
   *  atomic access.  push_front() and pop_front() must not be called
46
   *  concurrently to each other, while pop_back() can be called
47
   *  concurrently at all times.
48
   *  @c empty(), @c size(), and @c top() are intentionally not provided.
49
   *  Calling them would not make sense in a concurrent setting.
50
   *  @param _Tp Contained element type. */
51
  template<typename _Tp>
52
    class _RestrictedBoundedConcurrentQueue
53
    {
54
    private:
55
      /** @brief Array of elements, seen as cyclic buffer. */
56
      _Tp* _M_base;
57
 
58
      /** @brief Maximal number of elements contained at the same time. */
59
      _SequenceIndex _M_max_size;
60
 
61
      /** @brief Cyclic __begin and __end pointers contained in one
62
          atomically changeable value. */
63
      _GLIBCXX_VOLATILE _CASable _M_borders;
64
 
65
    public:
66
      /** @brief Constructor. Not to be called concurrent, of course.
67
       *  @param _M_max_size Maximal number of elements to be contained. */
68
      _RestrictedBoundedConcurrentQueue(_SequenceIndex __max_size)
69
      {
70
        _M_max_size = __max_size;
71
        _M_base = new _Tp[__max_size];
72
        _M_borders = __encode2(0, 0);
73
#pragma omp flush
74
      }
75
 
76
      /** @brief Destructor. Not to be called concurrent, of course. */
77
      ~_RestrictedBoundedConcurrentQueue()
78
      { delete[] _M_base; }
79
 
80
      /** @brief Pushes one element into the queue at the front end.
81
       *  Must not be called concurrently with pop_front(). */
82
      void
83
      push_front(const _Tp& __t)
84
      {
85
        _CASable __former_borders = _M_borders;
86
        int __former_front, __former_back;
87
        __decode2(__former_borders, __former_front, __former_back);
88
        *(_M_base + __former_front % _M_max_size) = __t;
89
#if _GLIBCXX_ASSERTIONS
90
        // Otherwise: front - back > _M_max_size eventually.
91
        _GLIBCXX_PARALLEL_ASSERT(((__former_front + 1) - __former_back)
92
                                 <= _M_max_size);
93
#endif
94
        __fetch_and_add(&_M_borders, __encode2(1, 0));
95
      }
96
 
97
      /** @brief Pops one element from the queue at the front end.
98
       *  Must not be called concurrently with pop_front(). */
99
      bool
100
      pop_front(_Tp& __t)
101
      {
102
        int __former_front, __former_back;
103
#pragma omp flush
104
        __decode2(_M_borders, __former_front, __former_back);
105
        while (__former_front > __former_back)
106
          {
107
            // Chance.
108
            _CASable __former_borders = __encode2(__former_front,
109
                                                  __former_back);
110
            _CASable __new_borders = __encode2(__former_front - 1,
111
                                               __former_back);
112
            if (__compare_and_swap(&_M_borders, __former_borders,
113
                                   __new_borders))
114
              {
115
                __t = *(_M_base + (__former_front - 1) % _M_max_size);
116
                return true;
117
              }
118
#pragma omp flush
119
            __decode2(_M_borders, __former_front, __former_back);
120
          }
121
        return false;
122
      }
123
 
124
      /** @brief Pops one element from the queue at the front end.
125
       *  Must not be called concurrently with pop_front(). */
126
      bool
127
      pop_back(_Tp& __t)        //queue behavior
128
      {
129
        int __former_front, __former_back;
130
#pragma omp flush
131
        __decode2(_M_borders, __former_front, __former_back);
132
        while (__former_front > __former_back)
133
          {
134
            // Chance.
135
            _CASable __former_borders = __encode2(__former_front,
136
                                                  __former_back);
137
            _CASable __new_borders = __encode2(__former_front,
138
                                               __former_back + 1);
139
            if (__compare_and_swap(&_M_borders, __former_borders,
140
                                   __new_borders))
141
              {
142
                __t = *(_M_base + __former_back % _M_max_size);
143
                return true;
144
              }
145
#pragma omp flush
146
            __decode2(_M_borders, __former_front, __former_back);
147
          }
148
        return false;
149
      }
150
  };
151
}       //namespace __gnu_parallel
152
 
153
#undef _GLIBCXX_VOLATILE
154
 
155
#endif /* _GLIBCXX_PARALLEL_QUEUE_H */

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.