hotspot/src/share/vm/libadt/set.hpp
changeset 1 489c9b5090e2
child 5547 f4b087cbb361
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/hotspot/src/share/vm/libadt/set.hpp	Sat Dec 01 00:00:00 2007 +0000
@@ -0,0 +1,251 @@
+/*
+ * Copyright 1997 Sun Microsystems, Inc.  All Rights Reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code 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
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
+ * CA 95054 USA or visit www.sun.com if you need additional information or
+ * have any questions.
+ *
+ */
+
+#ifndef _SET_
+#define _SET_
+// Sets - An Abstract Data Type
+
+// Should not manually include these in AVM framework. %%%%% - Ungar
+// #ifndef _PORT_
+// #include "port.hpp"
+// #endif // _PORT_
+//INTERFACE
+
+class SparseSet;
+class VectorSet;
+class ListSet;
+class CoSet;
+
+class ostream;
+class SetI_;
+
+// These sets can grow or shrink, based on the initial size and the largest
+// element currently in them.  Basically, they allow a bunch of bits to be
+// grouped together, tested, set & cleared, intersected, etc.  The basic
+// Set class is an abstract class, and cannot be constructed.  Instead,
+// one of VectorSet, SparseSet, or ListSet is created.  Each variation has
+// different asymptotic running times for different operations, and different
+// constants of proportionality as well.
+// {n = number of elements, N = largest element}
+
+//              VectorSet       SparseSet       ListSet
+// Create       O(N)            O(1)            O(1)
+// Clear        O(N)            O(1)            O(1)
+// Insert       O(1)            O(1)            O(log n)
+// Delete       O(1)            O(1)            O(log n)
+// Member       O(1)            O(1)            O(log n)
+// Size         O(N)            O(1)            O(1)
+// Copy         O(N)            O(n)            O(n)
+// Union        O(N)            O(n)            O(n log n)
+// Intersect    O(N)            O(n)            O(n log n)
+// Difference   O(N)            O(n)            O(n log n)
+// Equal        O(N)            O(n)            O(n log n)
+// ChooseMember O(N)            O(1)            O(1)
+// Sort         O(1)            O(n log n)      O(1)
+// Forall       O(N)            O(n)            O(n)
+// Complement   O(1)            O(1)            O(1)
+
+// TIME:        N/32            n               8*n     Accesses
+// SPACE:       N/8             4*N+4*n         8*n     Bytes
+
+// Create:      Make an empty set
+// Clear:       Remove all the elements of a Set
+// Insert:      Insert an element into a Set; duplicates are ignored
+// Delete:      Removes an element from a Set
+// Member:      Tests for membership in a Set
+// Size:        Returns the number of members of a Set
+// Copy:        Copy or assign one Set to another
+// Union:       Union 2 sets together
+// Intersect:   Intersect 2 sets together
+// Difference:  Compute A & !B; remove from set A those elements in set B
+// Equal:       Test for equality between 2 sets
+// ChooseMember Pick a random member
+// Sort:        If no other operation changes the set membership, a following
+//              Forall will iterate the members in ascending order.
+// Forall:      Iterate over the elements of a Set.  Operations that modify
+//              the set membership during iteration work, but the iterator may
+//              skip any member or duplicate any member.
+// Complement:  Only supported in the Co-Set variations.  It adds a small
+//              constant-time test to every Set operation.
+//
+// PERFORMANCE ISSUES:
+// If you "cast away" the specific set variation you are using, and then do
+// operations on the basic "Set" object you will pay a virtual function call
+// to get back the specific set variation.  On the other hand, using the
+// generic Set means you can change underlying implementations by just
+// changing the initial declaration.  Examples:
+//      void foo(VectorSet vs1, VectorSet vs2) { vs1 |= vs2; }
+// "foo" must be called with a VectorSet.  The vector set union operation
+// is called directly.
+//      void foo(Set vs1, Set vs2) { vs1 |= vs2; }
+// "foo" may be called with *any* kind of sets; suppose it is called with
+// VectorSets.  Two virtual function calls are used to figure out the that vs1
+// and vs2 are VectorSets.  In addition, if vs2 is not a VectorSet then a
+// temporary VectorSet copy of vs2 will be made before the union proceeds.
+//
+// VectorSets have a small constant.  Time and space are proportional to the
+//   largest element.  Fine for dense sets and largest element < 10,000.
+// SparseSets have a medium constant.  Time is proportional to the number of
+//   elements, space is proportional to the largest element.
+//   Fine (but big) with the largest element < 100,000.
+// ListSets have a big constant.  Time *and space* are proportional to the
+//   number of elements.  They work well for a few elements of *any* size
+//   (i.e. sets of pointers)!
+
+//------------------------------Set--------------------------------------------
+class Set : public ResourceObj {
+ public:
+
+  // Creates a new, empty set.
+  // DO NOT CONSTRUCT A Set.  THIS IS AN ABSTRACT CLASS, FOR INHERITENCE ONLY
+  Set(Arena *arena) : _set_arena(arena) {};
+
+  // Creates a new set from an existing set
+  // DO NOT CONSTRUCT A Set.  THIS IS AN ABSTRACT CLASS, FOR INHERITENCE ONLY
+  Set(const Set &) {};
+
+  // Set assignment; deep-copy guts
+  virtual Set &operator =(const Set &s)=0;
+  virtual Set &clone(void) const=0;
+
+  // Virtual destructor
+  virtual ~Set() {};
+
+  // Add member to set
+  virtual Set &operator <<=(uint elem)=0;
+  // virtual Set  operator << (uint elem);
+
+  // Delete member from set
+  virtual Set &operator >>=(uint elem)=0;
+  // virtual Set  operator >> (uint elem);
+
+  // Membership test.  Result is Zero (absent)/ Non-Zero (present)
+  virtual int operator [](uint elem) const=0;
+
+  // Intersect sets
+  virtual Set &operator &=(const Set &s)=0;
+  // virtual Set  operator & (const Set &s) const;
+
+  // Union sets
+  virtual Set &operator |=(const Set &s)=0;
+  // virtual Set  operator | (const Set &s) const;
+
+  // Difference sets
+  virtual Set &operator -=(const Set &s)=0;
+  // virtual Set  operator - (const Set &s) const;
+
+  // Tests for equality.  Result is Zero (false)/ Non-Zero (true)
+  virtual int operator ==(const Set &s) const=0;
+  int operator !=(const Set &s) const { return !(*this == s); }
+  virtual int disjoint(const Set &s) const=0;
+
+  // Tests for strict subset.  Result is Zero (false)/ Non-Zero (true)
+  virtual int operator < (const Set &s) const=0;
+  int operator > (const Set &s) const { return s < *this; }
+
+  // Tests for subset.  Result is Zero (false)/ Non-Zero (true)
+  virtual int operator <=(const Set &s) const=0;
+  int operator >=(const Set &s) const { return s <= *this; }
+
+  // Return any member of the Set.  Undefined if the Set is empty.
+  virtual uint getelem(void) const=0;
+
+  // Clear all the elements in the Set
+  virtual void Clear(void)=0;
+
+  // Return the number of members in the Set
+  virtual uint Size(void) const=0;
+
+  // If an iterator follows a "Sort()" without any Set-modifying operations
+  // inbetween then the iterator will visit the elements in ascending order.
+  virtual void Sort(void)=0;
+
+  // Convert a set to printable string in an allocated buffer.
+  // The caller must deallocate the string.
+  virtual char *setstr(void) const;
+
+  // Print the Set on "stdout".  Can be conveniently called in the debugger
+  void print() const;
+
+  // Parse text from the string into the Set.  Return length parsed.
+  virtual int parse(const char *s);
+
+  // Convert a generic Set to a specific Set
+  /* Removed for MCC BUG
+     virtual operator const SparseSet* (void) const;
+     virtual operator const VectorSet* (void) const;
+     virtual operator const ListSet  * (void) const;
+     virtual operator const CoSet    * (void) const; */
+  virtual const SparseSet *asSparseSet(void) const;
+  virtual const VectorSet *asVectorSet(void) const;
+  virtual const ListSet   *asListSet  (void) const;
+  virtual const CoSet     *asCoSet    (void) const;
+
+  // Hash the set.  Sets of different types but identical elements will NOT
+  // hash the same.  Same set type, same elements WILL hash the same.
+  virtual int hash() const = 0;
+
+protected:
+  friend class SetI;
+  friend class CoSet;
+  virtual class SetI_ *iterate(uint&) const=0;
+
+  // Need storeage for the set
+  Arena *_set_arena;
+};
+typedef Set&((*Set_Constructor)(Arena *arena));
+extern Set &ListSet_Construct(Arena *arena);
+extern Set &VectorSet_Construct(Arena *arena);
+extern Set &SparseSet_Construct(Arena *arena);
+
+//------------------------------Iteration--------------------------------------
+// Loop thru all elements of the set, setting "elem" to the element numbers
+// in random order.  Inserted or deleted elements during this operation may
+// or may not be iterated over; untouched elements will be affected once.
+
+// Usage:  for( SetI  i(s); i.test(); i++ ) { body = i.elem; }   ...OR...
+//         for( i.reset(s); i.test(); i++ ) { body = i.elem; }
+
+class SetI_ : public ResourceObj {
+protected:
+  friend class SetI;
+  virtual ~SetI_();
+  virtual uint next(void)=0;
+  virtual int test(void)=0;
+};
+
+class SetI {
+protected:
+  SetI_ *impl;
+public:
+  uint elem;                    // The publically accessible element
+
+  SetI( const Set *s ) { impl = s->iterate(elem); }
+  ~SetI() { delete impl; }
+  void reset( const Set *s ) { delete impl; impl = s->iterate(elem); }
+  void operator ++(void) { elem = impl->next(); }
+  int test(void) { return impl->test(); }
+};
+
+#endif // _SET_