1 : /*
2 : * Copyright (c) 2011 The Native Client Authors. All rights reserved.
3 : * Use of this source code is governed by a BSD-style license that can be
4 : * found in the LICENSE file.
5 : */
6 :
7 :
8 : // ConditionVariableEvents provides a doubly-link-list of events for use
9 : // exclusively by the ConditionVariable class.
10 :
11 : // This custom container was crafted because no simple combination of STL
12 : // classes appeared to support the functionality required. The specific
13 : // unusual requirement for a linked-list-class is support for the Extract()
14 : // method, which can remove an element from a list, potentially for insertion
15 : // into a second list. Most critically, the Extract() method is idempotent,
16 : // turning the indicated element into an extracted singleton whether it was
17 : // contained in a list or not. This functionality allows one (or more) of
18 : // threads to do the extraction. The iterator that identifies this extractable
19 : // element (in this case, a pointer to the list element) can be used after
20 : // arbitrary manipulation of the (possibly) enclosing list container. In
21 : // general, STL containers do not provide iterators that can be used across
22 : // modifications (insertions/extractions) of the enclosing containers, and
23 : // certainly don't provide iterators that can be used if the identified
24 : // element is *deleted* (removed) from the container.
25 :
26 : // It is possible to use multiple redundant containers, such as an STL list,
27 : // and an STL map, to achieve similar container semantics. This container has
28 : // only O(1) methods, while the corresponding (multiple) STL container approach
29 : // would have more complex O(log(N)) methods (yeah... N isn't that large).
30 : // Multiple containers also makes correctness more difficult to assert, as
31 : // data is redundantly stored and maintained, which is generally evil.
32 :
33 : #ifndef NATIVE_CLIENT_SRC_TRUSTED_PLATFORM_WIN_CONDITION_VARIABLE_EVENTS_H_
34 : #define NATIVE_CLIENT_SRC_TRUSTED_PLATFORM_WIN_CONDITION_VARIABLE_EVENTS_H_
35 :
36 : #include "native_client/src/shared/platform/win/time.h"
37 : #include "native_client/src/shared/platform/win/lock.h"
38 : #include "native_client/src/shared/platform/nacl_log.h"
39 : #include "native_client/src/shared/platform/nacl_check.h"
40 :
41 : namespace NaCl {
42 :
43 : class ConditionVariable;
44 :
45 : // Define elements that are used in a circular linked list.
46 : // The list container is an element with zero as handle_ value.
47 : // The actual list elements will have a non-zero HANDLE as their handle_.
48 : // All access to methods MUST be done under protection of a lock so that links
49 : // can be validated (and not asynchronously changing) during the method calls.
50 : class ConditionVariableEvent {
51 : private:
52 : friend class ConditionVariable;
53 :
54 : HANDLE handle_;
55 : ConditionVariableEvent* next_; // Doubly linked list.
56 : ConditionVariableEvent* prev_;
57 :
58 : // Default constructor with no arguments creates a list container.
59 2 : explicit ConditionVariableEvent(bool is_list_element = false) {
60 2 : if (is_list_element) {
61 2 : handle_ = CreateEvent(NULL, false, false, NULL);
62 : // DCHECK(0 != handle_); // InitCheck will validate in production.
63 2 : } else {
64 2 : handle_ = 0;
65 : }
66 2 : next_ = prev_ = this; // Self referencing circular.
67 2 : }
68 :
69 2 : ~ConditionVariableEvent() {
70 : // DCHECK(IsSingleton());
71 2 : if (0 != handle_) {
72 2 : if (0 == CloseHandle(handle_)) {
73 : NaClLog(LOG_ERROR, "CloseHandle returned 0"
74 0 : "in ~ConditionVariableEvent()");
75 : }
76 : }
77 2 : }
78 :
79 : // Methods for use on lists.
80 2 : bool IsEmpty() {
81 : // DCHECK(ValidateAsList());
82 2 : return IsSingleton();
83 2 : }
84 :
85 2 : void PushBack(ConditionVariableEvent* other) {
86 : // DCHECK(ValidateAsList());
87 : // DCHECK(other->ValidateAsItem());
88 : // DCHECK(other->IsSingleton());
89 : // Prepare other for insertion.
90 2 : other->prev_ = prev_;
91 2 : other->next_ = this;
92 : // Cut into list.
93 2 : prev_->next_ = other;
94 2 : prev_ = other;
95 : // DCHECK(ValidateAsDistinct(other));
96 2 : }
97 :
98 2 : ConditionVariableEvent* PopFront() {
99 : // DCHECK(ValidateAsList());
100 : // DCHECK(!IsSingleton());
101 2 : return next_->Extract();
102 2 : }
103 :
104 2 : ConditionVariableEvent* PopBack() {
105 : // DCHECK(ValidateAsList());
106 : // DCHECK(!IsSingleton());
107 2 : return prev_->Extract();
108 2 : }
109 :
110 : // Methods for use on list elements.
111 : // Accessor method.
112 2 : HANDLE handle() {
113 : // DCHECK(ValidateAsItem());
114 2 : return handle_;
115 2 : }
116 :
117 : // Pull an element from a list (if it's in one).
118 2 : ConditionVariableEvent* Extract() {
119 : // DCHECK(ValidateAsItem());
120 2 : if (!IsSingleton()) {
121 : // Stitch neighbors together.
122 2 : next_->prev_ = prev_;
123 2 : prev_->next_ = next_;
124 : // Make extractee into a singleton.
125 2 : prev_ = next_ = this;
126 : }
127 : // DCHECK(IsSingleton());
128 2 : return this;
129 2 : }
130 :
131 : // Method for use on a list element or on a list.
132 2 : bool IsSingleton() {
133 : // DCHECK(ValidateLinks());
134 2 : return next_ == this;
135 2 : }
136 :
137 : // Provide pre/post conditions to validate correct manipulations.
138 : bool ValidateAsDistinct(ConditionVariableEvent* other) {
139 : return ValidateLinks() && other->ValidateLinks() && (this != other);
140 : }
141 :
142 : bool ValidateAsItem() {
143 : return (0 != handle_) && ValidateLinks();
144 : }
145 :
146 : bool ValidateAsList() {
147 : return (0 == handle_) && ValidateLinks();
148 : }
149 :
150 : bool ValidateLinks() {
151 : // Make sure our neighbor's link to us.
152 : return (next_->prev_ == this) && (prev_->next_ == this);
153 : }
154 :
155 : NACL_DISALLOW_COPY_AND_ASSIGN(ConditionVariableEvent);
156 : };
157 :
158 : } // namespace NaCl
159 :
160 : #endif // NATIVE_CLIENT_SRC_TRUSTED_PLATFORM_WIN_CONDITION_VARIABLE_EVENTS_H_
|
