1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/share/vm/libadt/set.cpp Sat Dec 01 00:00:00 2007 +0000
1.3 @@ -0,0 +1,166 @@
1.4 +/*
1.5 + * Copyright 1997-2006 Sun Microsystems, Inc. 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
1.23 + * CA 95054 USA or visit www.sun.com if you need additional information or
1.24 + * have any questions.
1.25 + *
1.26 + */
1.27 +
1.28 +// Sets - An Abstract Data Type
1.29 +
1.30 +#include "incls/_precompiled.incl"
1.31 +#include "incls/_set.cpp.incl"
1.32 +
1.33 +// %%%%% includes not needed with AVM framework - Ungar
1.34 +// #include "port.hpp"
1.35 +//IMPLEMENTATION
1.36 +// #include "set.hpp"
1.37 +
1.38 +#include <stdio.h>
1.39 +#include <assert.h>
1.40 +#include <string.h>
1.41 +#include <stdlib.h>
1.42 +
1.43 +// Not needed and it causes terouble for gcc.
1.44 +//
1.45 +// #include <iostream.h>
1.46 +
1.47 +//-------------------------Virtual Functions-----------------------------------
1.48 +// These functions MUST be implemented by the inheriting class.
1.49 +class SparseSet;
1.50 +/* Removed for MCC BUG
1.51 + Set::operator const SparseSet*() const { assert(0); return NULL; } */
1.52 +const SparseSet *Set::asSparseSet() const { assert(0); return NULL; }
1.53 +class VectorSet;
1.54 +/* Removed for MCC BUG
1.55 + Set::operator const VectorSet*() const { assert(0); return NULL; } */
1.56 +const VectorSet *Set::asVectorSet() const { assert(0); return NULL; }
1.57 +class ListSet;
1.58 +/* Removed for MCC BUG
1.59 + Set::operator const ListSet*() const { assert(0); return NULL; } */
1.60 +const ListSet *Set::asListSet() const { assert(0); return NULL; }
1.61 +class CoSet;
1.62 +/* Removed for MCC BUG
1.63 + Set::operator const CoSet*() const { assert(0); return NULL; } */
1.64 +const CoSet *Set::asCoSet() const { assert(0); return NULL; }
1.65 +
1.66 +//------------------------------setstr-----------------------------------------
1.67 +// Create a string with a printable representation of a set.
1.68 +// The caller must deallocate the string.
1.69 +char *Set::setstr() const
1.70 +{
1.71 + if( !this ) return os::strdup("{no set}");
1.72 + Set &set = clone(); // Virtually copy the basic set.
1.73 + set.Sort(); // Sort elements for in-order retrieval
1.74 +
1.75 + uint len = 128; // Total string space
1.76 + char *buf = NEW_C_HEAP_ARRAY(char,len);// Some initial string space
1.77 +
1.78 + register char *s = buf; // Current working string pointer
1.79 + *s++ = '{';
1.80 + *s = '\0';
1.81 +
1.82 + // For all elements of the Set
1.83 + uint hi = (uint)-2, lo = (uint)-2;
1.84 + for( SetI i(&set); i.test(); ++i ) {
1.85 + if( hi+1 == i.elem ) { // Moving sequentially thru range?
1.86 + hi = i.elem; // Yes, just update hi end of range
1.87 + } else { // Else range ended
1.88 + if( buf+len-s < 25 ) { // Generous trailing space for upcoming numbers
1.89 + int offset = (int)(s-buf);// Not enuf space; compute offset into buffer
1.90 + len <<= 1; // Double string size
1.91 + buf = REALLOC_C_HEAP_ARRAY(char,buf,len); // Reallocate doubled size
1.92 + s = buf+offset; // Get working pointer into new bigger buffer
1.93 + }
1.94 + if( lo != (uint)-2 ) { // Startup? No! Then print previous range.
1.95 + if( lo != hi ) sprintf(s,"%d-%d,",lo,hi);
1.96 + else sprintf(s,"%d,",lo);
1.97 + s += strlen(s); // Advance working string
1.98 + }
1.99 + hi = lo = i.elem;
1.100 + }
1.101 + }
1.102 + if( lo != (uint)-2 ) {
1.103 + if( buf+len-s < 25 ) { // Generous trailing space for upcoming numbers
1.104 + int offset = (int)(s-buf);// Not enuf space; compute offset into buffer
1.105 + len <<= 1; // Double string size
1.106 + buf = (char*)ReallocateHeap(buf,len); // Reallocate doubled size
1.107 + s = buf+offset; // Get working pointer into new bigger buffer
1.108 + }
1.109 + if( lo != hi ) sprintf(s,"%d-%d}",lo,hi);
1.110 + else sprintf(s,"%d}",lo);
1.111 + } else strcat(s,"}");
1.112 + // Don't delete the clone 'set' since it is allocated on Arena.
1.113 + return buf;
1.114 +}
1.115 +
1.116 +//------------------------------print------------------------------------------
1.117 +// Handier print routine
1.118 +void Set::print() const
1.119 +{
1.120 + char *printable_set = setstr();
1.121 + tty->print_cr(printable_set);
1.122 + FreeHeap(printable_set);
1.123 +}
1.124 +
1.125 +//------------------------------parse------------------------------------------
1.126 +// Convert a textual representation of a Set, to a Set and union into "this"
1.127 +// Set. Return the amount of text parsed in "len", or zero in "len".
1.128 +int Set::parse(const char *s)
1.129 +{
1.130 + register char c; // Parse character
1.131 + register const char *t = s; // Save the starting position of s.
1.132 + do c = *s++; // Skip characters
1.133 + while( c && (c <= ' ') ); // Till no more whitespace or EOS
1.134 + if( c != '{' ) return 0; // Oops, not a Set openner
1.135 + if( *s == '}' ) return 2; // The empty Set
1.136 +
1.137 + // Sets are filled with values of the form "xx," or "xx-yy," with the comma
1.138 + // a "}" at the very end.
1.139 + while( 1 ) { // While have elements in the Set
1.140 + char *u; // Pointer to character ending parse
1.141 + uint hi, i; // Needed for range handling below
1.142 + uint elem = (uint)strtoul(s,&u,10);// Get element
1.143 + if( u == s ) return 0; // Bogus crude
1.144 + s = u; // Skip over the number
1.145 + c = *s++; // Get the number seperator
1.146 + switch ( c ) { // Different seperators
1.147 + case '}': // Last simple element
1.148 + case ',': // Simple element
1.149 + (*this) <<= elem; // Insert the simple element into the Set
1.150 + break; // Go get next element
1.151 + case '-': // Range
1.152 + hi = (uint)strtoul(s,&u,10); // Get element
1.153 + if( u == s ) return 0; // Bogus crude
1.154 + for( i=elem; i<=hi; i++ )
1.155 + (*this) <<= i; // Insert the entire range into the Set
1.156 + s = u; // Skip over the number
1.157 + c = *s++; // Get the number seperator
1.158 + break;
1.159 + }
1.160 + if( c == '}' ) break; // End of the Set
1.161 + if( c != ',' ) return 0; // Bogus garbage
1.162 + }
1.163 + return (int)(s-t); // Return length parsed
1.164 +}
1.165 +
1.166 +//------------------------------Iterator---------------------------------------
1.167 +SetI_::~SetI_()
1.168 +{
1.169 +}
