1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/share/vm/libadt/vectset.hpp Wed Apr 27 01:25:04 2016 +0800
1.3 @@ -0,0 +1,185 @@
1.4 +/*
1.5 + * Copyright (c) 1997, 2011, Oracle and/or its affiliates. All rights reserved.
1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 + *
1.8 + * This code is free software; you can redistribute it and/or modify it
1.9 + * under the terms of the GNU General Public License version 2 only, as
1.10 + * published by the Free Software Foundation.
1.11 + *
1.12 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.13 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.14 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.15 + * version 2 for more details (a copy is included in the LICENSE file that
1.16 + * accompanied this code).
1.17 + *
1.18 + * You should have received a copy of the GNU General Public License version
1.19 + * 2 along with this work; if not, write to the Free Software Foundation,
1.20 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.21 + *
1.22 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.23 + * or visit www.oracle.com if you need additional information or have any
1.24 + * questions.
1.25 + *
1.26 + */
1.27 +
1.28 +#ifndef SHARE_VM_LIBADT_VECTSET_HPP
1.29 +#define SHARE_VM_LIBADT_VECTSET_HPP
1.30 +
1.31 +#include "libadt/set.hpp"
1.32 +
1.33 +// Vector Sets - An Abstract Data Type
1.34 +//INTERFACE
1.35 +
1.36 +// These sets can grow or shrink, based on the initial size and the largest
1.37 +// element currently in them. Slow and bulky for sparse sets, these sets
1.38 +// are super for dense sets. They are fast and compact when dense.
1.39 +
1.40 +// TIME:
1.41 +// O(1) - Insert, Delete, Member, Sort
1.42 +// O(max_element) - Create, Clear, Size, Copy, Union, Intersect, Difference,
1.43 +// Equal, ChooseMember, Forall
1.44 +
1.45 +// SPACE: (max_element)/(8*sizeof(int))
1.46 +
1.47 +
1.48 +//------------------------------VectorSet--------------------------------------
1.49 +class VectorSet : public Set {
1.50 +friend class VectorSetI; // Friendly iterator class
1.51 +protected:
1.52 + uint size; // Size of data IN LONGWORDS (32bits)
1.53 + uint32 *data; // The data, bit packed
1.54 +
1.55 + void slamin( const VectorSet& s ); // Initialize one set with another
1.56 + int compare(const VectorSet &s) const; // Compare set contents
1.57 + void grow(uint newsize); // Grow vector to required bitsize
1.58 +
1.59 +public:
1.60 + VectorSet(Arena *arena); // Creates a new, empty set.
1.61 + VectorSet(const VectorSet &s) : Set(s._set_arena) {slamin(s);} // Set clone; deep-copy guts
1.62 + Set &operator =(const Set &s); // Set clone; deep-copy guts
1.63 + VectorSet &operator =(const VectorSet &s) // Set clone; deep-copy guts
1.64 + { if( &s != this ) { slamin(s); } return *this; }
1.65 + ~VectorSet() {}
1.66 + Set &clone(void) const { return *(new VectorSet(*this)); }
1.67 +
1.68 + Set &operator <<=(uint elem); // Add member to set
1.69 + VectorSet operator << (uint elem) // Add member to new set
1.70 + { VectorSet foo(*this); foo <<= elem; return foo; }
1.71 + Set &operator >>=(uint elem); // Delete member from set
1.72 + VectorSet operator >> (uint elem) // Delete member from new set
1.73 + { VectorSet foo(*this); foo >>= elem; return foo; }
1.74 +
1.75 + VectorSet &operator &=(const VectorSet &s); // Intersect sets into first set
1.76 + Set &operator &=(const Set &s); // Intersect sets into first set
1.77 + VectorSet operator & (const VectorSet &s) const
1.78 + { VectorSet foo(*this); foo &= s; return foo; }
1.79 +
1.80 + VectorSet &operator |=(const VectorSet &s); // Intersect sets into first set
1.81 + Set &operator |=(const Set &s); // Intersect sets into first set
1.82 + VectorSet operator | (const VectorSet &s) const
1.83 + { VectorSet foo(*this); foo |= s; return foo; }
1.84 +
1.85 + VectorSet &operator -=(const VectorSet &s); // Intersect sets into first set
1.86 + Set &operator -=(const Set &s); // Intersect sets into first set
1.87 + VectorSet operator - (const VectorSet &s) const
1.88 + { VectorSet foo(*this); foo -= s; return foo; }
1.89 +
1.90 + int operator ==(const VectorSet &s) const; // True if sets are equal
1.91 + int operator ==(const Set &s) const; // True if sets are equal
1.92 + int operator < (const VectorSet &s) const; // True if strict subset
1.93 + int operator < (const Set &s) const; // True if strict subset
1.94 + int operator <=(const VectorSet &s) const; // True if subset relation holds.
1.95 + int operator <=(const Set &s) const; // True if subset relation holds.
1.96 + int disjoint (const Set &s) const; // True if sets are disjoint
1.97 +
1.98 + int operator [](uint elem) const; // Test for membership
1.99 + uint getelem(void) const; // Return a random element
1.100 + void Clear(void); // Clear a set
1.101 + uint Size(void) const; // Number of elements in the Set.
1.102 + void Sort(void); // Sort before iterating
1.103 + int hash() const; // Hash function
1.104 + void Reset(void) { // Reset a set
1.105 + memset( data, 0, size*sizeof(uint32) );
1.106 + }
1.107 +
1.108 + /* Removed for MCC BUG
1.109 + operator const VectorSet* (void) const { return this; } */
1.110 + const VectorSet *asVectorSet() const { return this; }
1.111 +
1.112 + // Expose internals for speed-critical fast iterators
1.113 + uint word_size() const { return size; }
1.114 + uint32 *EXPOSE() const { return data; }
1.115 +
1.116 + // Fast inlined "test and set". Replaces the idiom:
1.117 + // if( visited[idx] ) return;
1.118 + // visited <<= idx;
1.119 + // With:
1.120 + // if( visited.test_set(idx) ) return;
1.121 + //
1.122 + int test_set( uint elem ) {
1.123 + uint word = elem >> 5; // Get the longword offset
1.124 + if( word >= size ) // Beyond the last?
1.125 + return test_set_grow(elem); // Then grow; set; return 0;
1.126 + uint32 mask = 1L << (elem & 31); // Get bit mask
1.127 + uint32 datum = data[word] & mask;// Get bit
1.128 + data[word] |= mask; // Set bit
1.129 + return datum; // Return bit
1.130 + }
1.131 + int test_set_grow( uint elem ) { // Insert & return 0;
1.132 + (*this) <<= elem; // Insert into set
1.133 + return 0; // Return 0!
1.134 + }
1.135 +
1.136 + // Fast inlined test
1.137 + int test( uint elem ) const {
1.138 + uint word = elem >> 5; // Get the longword offset
1.139 + if( word >= size ) return 0; // Beyond the last?
1.140 + uint32 mask = 1L << (elem & 31); // Get bit mask
1.141 + return data[word] & mask; // Get bit
1.142 + }
1.143 +
1.144 + // Fast inlined set
1.145 + void set( uint elem ) {
1.146 + uint word = elem >> 5; // Get the longword offset
1.147 + if( word >= size ) { // Beyond the last?
1.148 + test_set_grow(elem); // Then grow and set
1.149 + } else {
1.150 + uint32 mask = 1L << (elem & 31); // Get bit mask
1.151 + data[word] |= mask; // Set bit
1.152 + }
1.153 + }
1.154 +
1.155 +
1.156 +private:
1.157 + SetI_ *iterate(uint&) const;
1.158 +};
1.159 +
1.160 +//------------------------------Iteration--------------------------------------
1.161 +// Loop thru all elements of the set, setting "elem" to the element numbers
1.162 +// in random order. Inserted or deleted elements during this operation may
1.163 +// or may not be iterated over; untouched elements will be affected once.
1.164 +// Usage: for( VectorSetI i(s); i.test(); i++ ) { body = i.elem; }
1.165 +
1.166 +class VectorSetI : public StackObj {
1.167 + friend class VectorSet;
1.168 + const VectorSet *s;
1.169 + uint i, j;
1.170 + uint32 mask;
1.171 + uint next(void);
1.172 +
1.173 +public:
1.174 + uint elem; // The publically accessible element
1.175 +
1.176 + VectorSetI( const VectorSet *vset ) :
1.177 + s(vset),
1.178 + i((uint)-1L),
1.179 + j((uint)-1L),
1.180 + mask((unsigned)(1L<<31)) {
1.181 + elem = next();
1.182 + }
1.183 +
1.184 + void operator ++(void) { elem = next(); }
1.185 + int test(void) { return i < s->size; }
1.186 +};
1.187 +
1.188 +#endif // SHARE_VM_LIBADT_VECTSET_HPP
