jdk8-mips64-public/hotspot: src/share/vm/libadt/vectset.cpp@a61af66fc99e (annotated)

src/share/vm/libadt/vectset.cpp@a61af66fc99e (annotated)

src/share/vm/libadt/vectset.cpp

Sat, 01 Dec 2007 00:00:00 +0000

author: duke
date: Sat, 01 Dec 2007 00:00:00 +0000
changeset 435: a61af66fc99e
child 1907: c18cbe5936b8
permissions: -rw-r--r--

Initial load

 /*
  * Copyright 1997-2005 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.
  *
  */
 // Vector Sets - An Abstract Data Type
 #include "incls/_precompiled.incl"
 #include "incls/_vectset.cpp.incl"
 // %%%%% includes not needed with AVM framework - Ungar
 // #include "port.hpp"
 //IMPLEMENTATION
 // #include "vectset.hpp"
 // BitsInByte is a lookup table which tells the number of bits that
 // are in the looked-up number.  It is very useful in VectorSet_Size.
 uint8 bitsInByte[256] = {
 , 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
 , 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
 , 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
 , 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 , 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
 , 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 , 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 , 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
 , 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
 , 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 , 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 , 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
 , 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 , 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
 , 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
 , 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
 };
 //------------------------------VectorSet--------------------------------------
 // Create a new, empty Set.
 VectorSet::VectorSet(Arena *arena) : Set(arena) {
   size = 2;                     // Small initial size
   data = (uint32 *)_set_arena->Amalloc(size*sizeof(uint32));
   data[0] = 0;                  // No elements
   data[1] = 0;
 }
 //------------------------------Construct--------------------------------------
 Set &VectorSet_Construct(Arena *arena)
 {
   return *(new VectorSet(arena));
 }
 //------------------------------operator=--------------------------------------
 Set &VectorSet::operator = (const Set &set)
 {
   if( &set == this ) return *this;
   FREE_FAST(data);
   // The cast is a virtual function that checks that "set" is a VectorSet.
   slamin(*(set.asVectorSet()));
   return *this;
 }
 //------------------------------slamin-----------------------------------------
 // Initialize one set with another.  No regard is made to the existing Set.
 void VectorSet::slamin(const VectorSet& s)
 {
   size = s.size;                // Use new size
   data = (uint32*)s._set_arena->Amalloc(size*sizeof(uint32)); // Make array of required size
   memcpy( data, s.data, size*sizeof(uint32) ); // Fill the array
 }
 //------------------------------grow-------------------------------------------
 // Expand the existing set to a bigger size
 void VectorSet::grow( uint newsize )
 {
   newsize = (newsize+31) >> 5;  // Convert to longwords
   uint x = size;
   while( x < newsize ) x <<= 1;
   data = (uint32 *)_set_arena->Arealloc(data, size*sizeof(uint32), x*sizeof(uint32));
   memset((char *)(data + size), 0, (x - size)*sizeof(uint32));
   size = x;
 }
 //------------------------------operator<<=------------------------------------
 // Insert a member into an existing Set.
 Set &VectorSet::operator <<= (uint elem)
 {
   register uint word = elem >> 5;            // Get the longword offset
   register uint32 mask = 1L << (elem & 31);  // Get bit mask
   if( word >= size )            // Need to grow set?
     grow(elem+1);               // Then grow it
   data[word] |= mask;           // Set new bit
   return *this;
 }
 //------------------------------operator>>=------------------------------------
 // Delete a member from an existing Set.
 Set &VectorSet::operator >>= (uint elem)
 {
   register uint word = elem >> 5; // Get the longword offset
   if( word >= size )              // Beyond the last?
     return *this;                 // Then it's clear & return clear
   register uint32 mask = 1L << (elem & 31);     // Get bit mask
   data[word] &= ~mask;            // Clear bit
   return *this;
 }
 //------------------------------operator&=-------------------------------------
 // Intersect one set into another.
 VectorSet &VectorSet::operator &= (const VectorSet &s)
 {
   // NOTE: The intersection is never any larger than the smallest set.
   if( s.size < size ) size = s.size; // Get smaller size
   register uint32 *u1 = data;   // Pointer to the destination data
   register uint32 *u2 = s.data; // Pointer to the source data
   for( uint i=0; i<size; i++)   // For data in set
     *u1++ &= *u2++;             // Copy and AND longwords
   return *this;                 // Return set
 }
 //------------------------------operator&=-------------------------------------
 Set &VectorSet::operator &= (const Set &set)
 {
   // The cast is a virtual function that checks that "set" is a VectorSet.
   return (*this) &= *(set.asVectorSet());
 }
 //------------------------------operator|=-------------------------------------
 // Union one set into another.
 VectorSet &VectorSet::operator |= (const VectorSet &s)
 {
   // This many words must be unioned
   register uint cnt = ((size<s.size)?size:s.size);
   register uint32 *u1 = data;   // Pointer to the destination data
   register uint32 *u2 = s.data; // Pointer to the source data
   for( uint i=0; i<cnt; i++)    // Copy and OR the two sets
     *u1++ |= *u2++;
   if( size < s.size ) {         // Is set 2 larger than set 1?
     // Extend result by larger set
     grow(s.size*sizeof(uint32)*8);
     memcpy(&data[cnt], u2, (s.size - cnt)*sizeof(uint32));
   }
   return *this;                 // Return result set
 }
 //------------------------------operator|=-------------------------------------
 Set &VectorSet::operator |= (const Set &set)
 {
   // The cast is a virtual function that checks that "set" is a VectorSet.
   return (*this) |= *(set.asVectorSet());
 }
 //------------------------------operator-=-------------------------------------
 // Difference one set from another.
 VectorSet &VectorSet::operator -= (const VectorSet &s)
 {
   // This many words must be unioned
   register uint cnt = ((size<s.size)?size:s.size);
   register uint32 *u1 = data;   // Pointer to the destination data
   register uint32 *u2 = s.data; // Pointer to the source data
   for( uint i=0; i<cnt; i++ )   // For data in set
     *u1++ &= ~(*u2++);          // A <-- A & ~B  with longwords
   return *this;                 // Return new set
 }
 //------------------------------operator-=-------------------------------------
 Set &VectorSet::operator -= (const Set &set)
 {
   // The cast is a virtual function that checks that "set" is a VectorSet.
   return (*this) -= *(set.asVectorSet());
 }
 //------------------------------compare----------------------------------------
 // Compute 2 booleans: bits in A not B, bits in B not A.
 // Return X0 --  A is not a subset of B
 //        X1 --  A is a subset of B
 //        0X --  B is not a subset of A
 //        1X --  B is a subset of A
 int VectorSet::compare (const VectorSet &s) const
 {
   register uint32 *u1 = data;   // Pointer to the destination data
   register uint32 *u2 = s.data; // Pointer to the source data
   register uint32 AnotB = 0, BnotA = 0;
   // This many words must be unioned
   register uint cnt = ((size<s.size)?size:s.size);
   // Get bits for both sets
   uint i;                       // Exit value of loop
   for( i=0; i<cnt; i++ ) {      // For data in BOTH sets
     register uint32 A = *u1++;  // Data from one guy
     register uint32 B = *u2++;  // Data from other guy
     AnotB |= (A & ~B);          // Compute bits in A not B
     BnotA |= (B & ~A);          // Compute bits in B not A
   }
   // Get bits from bigger set
   if( size < s.size ) {
     for( ; i<s.size; i++ )      // For data in larger set
       BnotA |= *u2++;           // These bits are in B not A
   } else {
     for( ; i<size; i++ )        // For data in larger set
       AnotB |= *u1++;           // These bits are in A not B
   }
   // Set & return boolean flags
   return ((!BnotA)<<1) + (!AnotB);
 }
 //------------------------------operator==-------------------------------------
 // Test for set equality
 int VectorSet::operator == (const VectorSet &s) const
 {
   return compare(s) == 3;       // TRUE if A and B are mutual subsets
 }
 //------------------------------operator==-------------------------------------
 int VectorSet::operator == (const Set &set) const
 {
   // The cast is a virtual function that checks that "set" is a VectorSet.
   return (*this) == *(set.asVectorSet());
 }
 //------------------------------disjoint---------------------------------------
 // Check for sets being disjoint.
 int VectorSet::disjoint(const Set &set) const
 {
   // The cast is a virtual function that checks that "set" is a VectorSet.
   const VectorSet &s = *(set.asVectorSet());
   // NOTE: The intersection is never any larger than the smallest set.
   register uint small = ((size<s.size)?size:s.size);
   register uint32 *u1 = data;   // Pointer to the destination data
   register uint32 *u2 = s.data; // Pointer to the source data
   for( uint i=0; i<small; i++)  // For data in set
     if( *u1++ & *u2++ )         // If any elements in common
       return 0;                 // Then not disjoint
   return 1;                     // Else disjoint
 }
 //------------------------------operator<--------------------------------------
 // Test for strict subset
 int VectorSet::operator < (const VectorSet &s) const
 {
   return compare(s) == 1;       // A subset B, B not subset A
 }
 //------------------------------operator<--------------------------------------
 int VectorSet::operator < (const Set &set) const
 {
   // The cast is a virtual function that checks that "set" is a VectorSet.
   return (*this) < *(set.asVectorSet());
 }
 //------------------------------operator<=-------------------------------------
 // Test for subset
 int VectorSet::operator <= (const VectorSet &s) const
 {
   return compare(s) & 1;        // A subset B
 }
 //------------------------------operator<=-------------------------------------
 int VectorSet::operator <= (const Set &set) const
 {
   // The cast is a virtual function that checks that "set" is a VectorSet.
   return (*this) <= *(set.asVectorSet());
 }
 //------------------------------operator[]-------------------------------------
 // Test for membership.  A Zero/Non-Zero value is returned!
 int VectorSet::operator[](uint elem) const
 {
   register uint word = elem >> 5; // Get the longword offset
   if( word >= size )              // Beyond the last?
     return 0;                     // Then it's clear
   register uint32 mask = 1L << (elem & 31);  // Get bit mask
   return ((data[word] & mask))!=0;           // Return the sense of the bit
 }
 //------------------------------getelem----------------------------------------
 // Get any element from the set.
 uint VectorSet::getelem(void) const
 {
   uint i;                       // Exit value of loop
   for( i=0; i<size; i++ )
     if( data[i] )
       break;
   uint32 word = data[i];
   int j;                        // Exit value of loop
   for( j= -1; word; j++, word>>=1 );
   return (i<<5)+j;
 }
 //------------------------------Clear------------------------------------------
 // Clear a set
 void VectorSet::Clear(void)
 {
   if( size > 100 ) {            // Reclaim storage only if huge
     FREE_RESOURCE_ARRAY(uint32,data,size);
     size = 2;                   // Small initial size
     data = NEW_RESOURCE_ARRAY(uint32,size);
   }
   memset( data, 0, size*sizeof(uint32) );
 }
 //------------------------------Size-------------------------------------------
 // Return number of elements in a Set
 uint VectorSet::Size(void) const
 {
   uint sum = 0;                 // Cumulative size so far.
   uint8 *currByte = (uint8*)data;
   for( uint32 i = 0; i < (size<<2); i++) // While have bytes to process
     sum += bitsInByte[*currByte++];      // Add bits in current byte to size.
   return sum;
 }
 //------------------------------Sort-------------------------------------------
 // Sort the elements for the next forall statement
 void VectorSet::Sort(void)
 {
 }
 //------------------------------hash-------------------------------------------
 int VectorSet::hash() const
 {
   uint32 _xor = 0;
   uint lim = ((size<4)?size:4);
   for( uint i = 0; i < lim; i++ )
     _xor ^= data[i];
   return (int)_xor;
 }
 //------------------------------iterate----------------------------------------
 SetI_ *VectorSet::iterate(uint &elem) const
 {
   VSetI_ *foo = (new(ResourceObj::C_HEAP) VSetI_(this));
   elem = foo->next();
   return foo;
 }
 //=============================================================================
 //------------------------------VSetI_-----------------------------------------
 // Initialize the innards of a VectorSet iterator
 VSetI_::VSetI_( const VectorSet *vset ) : s(vset)
 {
   i = (uint)-1L;
   j = (uint)-1L;
   mask = (unsigned)(1L<<31);
 }
 //------------------------------next-------------------------------------------
 // Find and return the next element of a vector set, or return garbage and
 // make "VSetI_::test()" fail.
 uint VSetI_::next(void)
 {
   j++;                          // Next element in word
   mask = (mask & max_jint) << 1;// Next bit in word
   do {                          // Do While still have words
     while( mask ) {             // While have bits in word
       if( s->data[i] & mask ) { // If found a bit
         return (i<<5)+j;        // Return the bit address
       }
       j++;                      // Skip to next bit
       mask = (mask & max_jint) << 1;
     }
     j = 0;                      // No more bits in word; setup for next word
     mask = 1;
     for( i++; (i<s->size) && (!s->data[i]); i++ ); // Skip to non-zero word
   } while( i<s->size );
   return max_juint;             // No element, iterated them all
 }

Mercurial > jdk8-mips64-public > hotspot / annotate

src/share/vm/libadt/vectset.cpp@a61af66fc99e (annotated)

src/share/vm/libadt/vectset.cpp