Mercurial > hg > truffle
annotate src/share/vm/libadt/set.hpp @ 14649:f6301b007a16
6498581: ThreadInterruptTest3 produces wrong output on Windows
Summary: There is race condition between os::interrupt and os::is_interrupted on Windows. In JVM_Sleep(Thread.sleep), check if thread gets interrupted, it may see interrupted but not really interrupted so cause spurious waking up (early return from sleep). Fix by checking if interrupt event really gets set thus prevent false return. For intrinsic of _isInterrupted, on Windows, go fastpath only on bit not set.
Reviewed-by: acorn, kvn
Contributed-by: david.holmes@oracle.com, yumin.qi@oracle.com
| author | minqi |
|---|---|
| date | Wed, 26 Feb 2014 15:20:41 -0800 |
| parents | f95d63e2154a |
| children |
| rev | line source |
|---|---|
| 0 | 1 /* |
| 1972 | 2 * Copyright (c) 1997, 2010, Oracle and/or its affiliates. All rights reserved. |
| 0 | 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| 4 * | |
| 5 * This code is free software; you can redistribute it and/or modify it | |
| 6 * under the terms of the GNU General Public License version 2 only, as | |
| 7 * published by the Free Software Foundation. | |
| 8 * | |
| 9 * This code is distributed in the hope that it will be useful, but WITHOUT | |
| 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
| 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
| 12 * version 2 for more details (a copy is included in the LICENSE file that | |
| 13 * accompanied this code). | |
| 14 * | |
| 15 * You should have received a copy of the GNU General Public License version | |
| 16 * 2 along with this work; if not, write to the Free Software Foundation, | |
| 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. | |
| 18 * | |
|
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
0
diff
changeset
|
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
|
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
0
diff
changeset
|
20 * or visit www.oracle.com if you need additional information or have any |
|
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
0
diff
changeset
|
21 * questions. |
| 0 | 22 * |
| 23 */ | |
| 24 | |
| 1972 | 25 #ifndef SHARE_VM_LIBADT_SET_HPP |
| 26 #define SHARE_VM_LIBADT_SET_HPP | |
| 27 | |
| 28 #include "libadt/port.hpp" | |
| 29 #include "memory/allocation.hpp" | |
| 30 | |
| 0 | 31 // Sets - An Abstract Data Type |
| 32 | |
| 33 //INTERFACE | |
| 34 | |
| 35 class SparseSet; | |
| 36 class VectorSet; | |
| 37 class ListSet; | |
| 38 class CoSet; | |
| 39 | |
| 40 class ostream; | |
| 41 class SetI_; | |
| 42 | |
| 43 // These sets can grow or shrink, based on the initial size and the largest | |
| 44 // element currently in them. Basically, they allow a bunch of bits to be | |
| 45 // grouped together, tested, set & cleared, intersected, etc. The basic | |
| 46 // Set class is an abstract class, and cannot be constructed. Instead, | |
| 47 // one of VectorSet, SparseSet, or ListSet is created. Each variation has | |
| 48 // different asymptotic running times for different operations, and different | |
| 49 // constants of proportionality as well. | |
| 50 // {n = number of elements, N = largest element} | |
| 51 | |
| 52 // VectorSet SparseSet ListSet | |
| 53 // Create O(N) O(1) O(1) | |
| 54 // Clear O(N) O(1) O(1) | |
| 55 // Insert O(1) O(1) O(log n) | |
| 56 // Delete O(1) O(1) O(log n) | |
| 57 // Member O(1) O(1) O(log n) | |
| 58 // Size O(N) O(1) O(1) | |
| 59 // Copy O(N) O(n) O(n) | |
| 60 // Union O(N) O(n) O(n log n) | |
| 61 // Intersect O(N) O(n) O(n log n) | |
| 62 // Difference O(N) O(n) O(n log n) | |
| 63 // Equal O(N) O(n) O(n log n) | |
| 64 // ChooseMember O(N) O(1) O(1) | |
| 65 // Sort O(1) O(n log n) O(1) | |
| 66 // Forall O(N) O(n) O(n) | |
| 67 // Complement O(1) O(1) O(1) | |
| 68 | |
| 69 // TIME: N/32 n 8*n Accesses | |
| 70 // SPACE: N/8 4*N+4*n 8*n Bytes | |
| 71 | |
| 72 // Create: Make an empty set | |
| 73 // Clear: Remove all the elements of a Set | |
| 74 // Insert: Insert an element into a Set; duplicates are ignored | |
| 75 // Delete: Removes an element from a Set | |
| 76 // Member: Tests for membership in a Set | |
| 77 // Size: Returns the number of members of a Set | |
| 78 // Copy: Copy or assign one Set to another | |
| 79 // Union: Union 2 sets together | |
| 80 // Intersect: Intersect 2 sets together | |
| 81 // Difference: Compute A & !B; remove from set A those elements in set B | |
| 82 // Equal: Test for equality between 2 sets | |
| 83 // ChooseMember Pick a random member | |
| 84 // Sort: If no other operation changes the set membership, a following | |
| 85 // Forall will iterate the members in ascending order. | |
| 86 // Forall: Iterate over the elements of a Set. Operations that modify | |
| 87 // the set membership during iteration work, but the iterator may | |
| 88 // skip any member or duplicate any member. | |
| 89 // Complement: Only supported in the Co-Set variations. It adds a small | |
| 90 // constant-time test to every Set operation. | |
| 91 // | |
| 92 // PERFORMANCE ISSUES: | |
| 93 // If you "cast away" the specific set variation you are using, and then do | |
| 94 // operations on the basic "Set" object you will pay a virtual function call | |
| 95 // to get back the specific set variation. On the other hand, using the | |
| 96 // generic Set means you can change underlying implementations by just | |
| 97 // changing the initial declaration. Examples: | |
| 98 // void foo(VectorSet vs1, VectorSet vs2) { vs1 |= vs2; } | |
| 99 // "foo" must be called with a VectorSet. The vector set union operation | |
| 100 // is called directly. | |
| 101 // void foo(Set vs1, Set vs2) { vs1 |= vs2; } | |
| 102 // "foo" may be called with *any* kind of sets; suppose it is called with | |
| 103 // VectorSets. Two virtual function calls are used to figure out the that vs1 | |
| 104 // and vs2 are VectorSets. In addition, if vs2 is not a VectorSet then a | |
| 105 // temporary VectorSet copy of vs2 will be made before the union proceeds. | |
| 106 // | |
| 107 // VectorSets have a small constant. Time and space are proportional to the | |
| 108 // largest element. Fine for dense sets and largest element < 10,000. | |
| 109 // SparseSets have a medium constant. Time is proportional to the number of | |
| 110 // elements, space is proportional to the largest element. | |
| 111 // Fine (but big) with the largest element < 100,000. | |
| 112 // ListSets have a big constant. Time *and space* are proportional to the | |
| 113 // number of elements. They work well for a few elements of *any* size | |
| 114 // (i.e. sets of pointers)! | |
| 115 | |
| 116 //------------------------------Set-------------------------------------------- | |
| 117 class Set : public ResourceObj { | |
| 118 public: | |
| 119 | |
| 120 // Creates a new, empty set. | |
| 121 // DO NOT CONSTRUCT A Set. THIS IS AN ABSTRACT CLASS, FOR INHERITENCE ONLY | |
| 122 Set(Arena *arena) : _set_arena(arena) {}; | |
| 123 | |
| 124 // Creates a new set from an existing set | |
| 125 // DO NOT CONSTRUCT A Set. THIS IS AN ABSTRACT CLASS, FOR INHERITENCE ONLY | |
| 126 Set(const Set &) {}; | |
| 127 | |
| 128 // Set assignment; deep-copy guts | |
| 129 virtual Set &operator =(const Set &s)=0; | |
| 130 virtual Set &clone(void) const=0; | |
| 131 | |
| 132 // Virtual destructor | |
| 133 virtual ~Set() {}; | |
| 134 | |
| 135 // Add member to set | |
| 136 virtual Set &operator <<=(uint elem)=0; | |
| 137 // virtual Set operator << (uint elem); | |
| 138 | |
| 139 // Delete member from set | |
| 140 virtual Set &operator >>=(uint elem)=0; | |
| 141 // virtual Set operator >> (uint elem); | |
| 142 | |
| 143 // Membership test. Result is Zero (absent)/ Non-Zero (present) | |
| 144 virtual int operator [](uint elem) const=0; | |
| 145 | |
| 146 // Intersect sets | |
| 147 virtual Set &operator &=(const Set &s)=0; | |
| 148 // virtual Set operator & (const Set &s) const; | |
| 149 | |
| 150 // Union sets | |
| 151 virtual Set &operator |=(const Set &s)=0; | |
| 152 // virtual Set operator | (const Set &s) const; | |
| 153 | |
| 154 // Difference sets | |
| 155 virtual Set &operator -=(const Set &s)=0; | |
| 156 // virtual Set operator - (const Set &s) const; | |
| 157 | |
| 158 // Tests for equality. Result is Zero (false)/ Non-Zero (true) | |
| 159 virtual int operator ==(const Set &s) const=0; | |
| 160 int operator !=(const Set &s) const { return !(*this == s); } | |
| 161 virtual int disjoint(const Set &s) const=0; | |
| 162 | |
| 163 // Tests for strict subset. Result is Zero (false)/ Non-Zero (true) | |
| 164 virtual int operator < (const Set &s) const=0; | |
| 165 int operator > (const Set &s) const { return s < *this; } | |
| 166 | |
| 167 // Tests for subset. Result is Zero (false)/ Non-Zero (true) | |
| 168 virtual int operator <=(const Set &s) const=0; | |
| 169 int operator >=(const Set &s) const { return s <= *this; } | |
| 170 | |
| 171 // Return any member of the Set. Undefined if the Set is empty. | |
| 172 virtual uint getelem(void) const=0; | |
| 173 | |
| 174 // Clear all the elements in the Set | |
| 175 virtual void Clear(void)=0; | |
| 176 | |
| 177 // Return the number of members in the Set | |
| 178 virtual uint Size(void) const=0; | |
| 179 | |
| 180 // If an iterator follows a "Sort()" without any Set-modifying operations | |
| 181 // inbetween then the iterator will visit the elements in ascending order. | |
| 182 virtual void Sort(void)=0; | |
| 183 | |
| 184 // Convert a set to printable string in an allocated buffer. | |
| 185 // The caller must deallocate the string. | |
| 186 virtual char *setstr(void) const; | |
| 187 | |
| 188 // Print the Set on "stdout". Can be conveniently called in the debugger | |
| 189 void print() const; | |
| 190 | |
| 191 // Parse text from the string into the Set. Return length parsed. | |
| 192 virtual int parse(const char *s); | |
| 193 | |
| 194 // Convert a generic Set to a specific Set | |
| 195 /* Removed for MCC BUG | |
| 196 virtual operator const SparseSet* (void) const; | |
| 197 virtual operator const VectorSet* (void) const; | |
| 198 virtual operator const ListSet * (void) const; | |
| 199 virtual operator const CoSet * (void) const; */ | |
| 200 virtual const SparseSet *asSparseSet(void) const; | |
| 201 virtual const VectorSet *asVectorSet(void) const; | |
| 202 virtual const ListSet *asListSet (void) const; | |
| 203 virtual const CoSet *asCoSet (void) const; | |
| 204 | |
| 205 // Hash the set. Sets of different types but identical elements will NOT | |
| 206 // hash the same. Same set type, same elements WILL hash the same. | |
| 207 virtual int hash() const = 0; | |
| 208 | |
| 209 protected: | |
| 210 friend class SetI; | |
| 211 friend class CoSet; | |
| 212 virtual class SetI_ *iterate(uint&) const=0; | |
| 213 | |
| 214 // Need storeage for the set | |
| 215 Arena *_set_arena; | |
| 216 }; | |
| 217 typedef Set&((*Set_Constructor)(Arena *arena)); | |
| 218 extern Set &ListSet_Construct(Arena *arena); | |
| 219 extern Set &VectorSet_Construct(Arena *arena); | |
| 220 extern Set &SparseSet_Construct(Arena *arena); | |
| 221 | |
| 222 //------------------------------Iteration-------------------------------------- | |
| 223 // Loop thru all elements of the set, setting "elem" to the element numbers | |
| 224 // in random order. Inserted or deleted elements during this operation may | |
| 225 // or may not be iterated over; untouched elements will be affected once. | |
| 226 | |
| 227 // Usage: for( SetI i(s); i.test(); i++ ) { body = i.elem; } ...OR... | |
| 228 // for( i.reset(s); i.test(); i++ ) { body = i.elem; } | |
| 229 | |
| 230 class SetI_ : public ResourceObj { | |
| 231 protected: | |
| 232 friend class SetI; | |
| 233 virtual ~SetI_(); | |
| 234 virtual uint next(void)=0; | |
| 235 virtual int test(void)=0; | |
| 236 }; | |
| 237 | |
| 238 class SetI { | |
| 239 protected: | |
| 240 SetI_ *impl; | |
| 241 public: | |
| 242 uint elem; // The publically accessible element | |
| 243 | |
| 244 SetI( const Set *s ) { impl = s->iterate(elem); } | |
| 245 ~SetI() { delete impl; } | |
| 246 void reset( const Set *s ) { delete impl; impl = s->iterate(elem); } | |
| 247 void operator ++(void) { elem = impl->next(); } | |
| 248 int test(void) { return impl->test(); } | |
| 249 }; | |
| 250 | |
| 1972 | 251 #endif // SHARE_VM_LIBADT_SET_HPP |