Mercurial > jdk8-mips64-public > hotspot / file revision

 /*

  * Copyright (c) 1997, 2012, Oracle and/or its affiliates. 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

  * or visit www.oracle.com if you need additional information or have any

  * questions.

  *

  */

 #include "precompiled.hpp"

 #include "libadt/vectset.hpp"

 #include "memory/allocation.inline.hpp"

 // Vector Sets - An Abstract Data Type

 // %%%%% 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] = {

   0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,

   1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,

   1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,

   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

   1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,

   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,

   1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,

   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,

   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,

   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,

   4, 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 = ((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_size; 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----------------------------------------

 // Used by Set::print().

 class VSetI_ : public SetI_ {

   VectorSetI vsi;

 public:

   VSetI_( const VectorSet *vset, uint &elem ) : vsi(vset) { elem = vsi.elem; }

   uint next(void) { ++vsi; return vsi.elem; }

   int  test(void) { return vsi.test(); }

 };

 SetI_ *VectorSet::iterate(uint &elem) const {

   return new(ResourceObj::C_HEAP, mtInternal) VSetI_(this, elem);

 }

 //=============================================================================

 //------------------------------next-------------------------------------------

 // Find and return the next element of a vector set, or return garbage and

 // make "VectorSetI::test()" fail.

 uint VectorSetI::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

 }