Mercurial > jdk8-mips64-public > hotspot / annotate
src/share/vm/libadt/set.cpp@f90c822e73f8 (annotated)
src/share/vm/libadt/set.cpp
Wed, 27 Apr 2016 01:25:04 +0800
- author
- aoqi
- date
- Wed, 27 Apr 2016 01:25:04 +0800
- changeset 0
- f90c822e73f8
- child 6876
- 710a3c8b516e
- permissions
- -rw-r--r--
Initial load
http://hg.openjdk.java.net/jdk8u/jdk8u/hotspot/
changeset: 6782:28b50d07f6f8
tag: jdk8u25-b17
| aoqi@0 | 1 | /* |
| aoqi@0 | 2 | * Copyright (c) 1997, 2014, Oracle and/or its affiliates. All rights reserved. |
| aoqi@0 | 3 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| aoqi@0 | 4 | * |
| aoqi@0 | 5 | * This code is free software; you can redistribute it and/or modify it |
| aoqi@0 | 6 | * under the terms of the GNU General Public License version 2 only, as |
| aoqi@0 | 7 | * published by the Free Software Foundation. |
| aoqi@0 | 8 | * |
| aoqi@0 | 9 | * This code is distributed in the hope that it will be useful, but WITHOUT |
| aoqi@0 | 10 | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| aoqi@0 | 11 | * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| aoqi@0 | 12 | * version 2 for more details (a copy is included in the LICENSE file that |
| aoqi@0 | 13 | * accompanied this code). |
| aoqi@0 | 14 | * |
| aoqi@0 | 15 | * You should have received a copy of the GNU General Public License version |
| aoqi@0 | 16 | * 2 along with this work; if not, write to the Free Software Foundation, |
| aoqi@0 | 17 | * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
| aoqi@0 | 18 | * |
| aoqi@0 | 19 | * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
| aoqi@0 | 20 | * or visit www.oracle.com if you need additional information or have any |
| aoqi@0 | 21 | * questions. |
| aoqi@0 | 22 | * |
| aoqi@0 | 23 | */ |
| aoqi@0 | 24 | |
| aoqi@0 | 25 | #include "precompiled.hpp" |
| aoqi@0 | 26 | #include "libadt/set.hpp" |
| aoqi@0 | 27 | #include "memory/allocation.inline.hpp" |
| aoqi@0 | 28 | |
| aoqi@0 | 29 | // Sets - An Abstract Data Type |
| aoqi@0 | 30 | |
| aoqi@0 | 31 | // %%%%% includes not needed with AVM framework - Ungar |
| aoqi@0 | 32 | // #include "port.hpp" |
| aoqi@0 | 33 | //IMPLEMENTATION |
| aoqi@0 | 34 | // #include "set.hpp" |
| aoqi@0 | 35 | |
| aoqi@0 | 36 | #include <stdio.h> |
| aoqi@0 | 37 | #include <assert.h> |
| aoqi@0 | 38 | #include <string.h> |
| aoqi@0 | 39 | #include <stdlib.h> |
| aoqi@0 | 40 | |
| aoqi@0 | 41 | // Not needed and it causes terouble for gcc. |
| aoqi@0 | 42 | // |
| aoqi@0 | 43 | // #include <iostream.h> |
| aoqi@0 | 44 | |
| aoqi@0 | 45 | //-------------------------Virtual Functions----------------------------------- |
| aoqi@0 | 46 | // These functions MUST be implemented by the inheriting class. |
| aoqi@0 | 47 | class SparseSet; |
| aoqi@0 | 48 | /* Removed for MCC BUG |
| aoqi@0 | 49 | Set::operator const SparseSet*() const { assert(0); return NULL; } */ |
| aoqi@0 | 50 | const SparseSet *Set::asSparseSet() const { assert(0); return NULL; } |
| aoqi@0 | 51 | class VectorSet; |
| aoqi@0 | 52 | /* Removed for MCC BUG |
| aoqi@0 | 53 | Set::operator const VectorSet*() const { assert(0); return NULL; } */ |
| aoqi@0 | 54 | const VectorSet *Set::asVectorSet() const { assert(0); return NULL; } |
| aoqi@0 | 55 | class ListSet; |
| aoqi@0 | 56 | /* Removed for MCC BUG |
| aoqi@0 | 57 | Set::operator const ListSet*() const { assert(0); return NULL; } */ |
| aoqi@0 | 58 | const ListSet *Set::asListSet() const { assert(0); return NULL; } |
| aoqi@0 | 59 | class CoSet; |
| aoqi@0 | 60 | /* Removed for MCC BUG |
| aoqi@0 | 61 | Set::operator const CoSet*() const { assert(0); return NULL; } */ |
| aoqi@0 | 62 | const CoSet *Set::asCoSet() const { assert(0); return NULL; } |
| aoqi@0 | 63 | |
| aoqi@0 | 64 | //------------------------------setstr----------------------------------------- |
| aoqi@0 | 65 | // Create a string with a printable representation of a set. |
| aoqi@0 | 66 | // The caller must deallocate the string. |
| aoqi@0 | 67 | char *Set::setstr() const |
| aoqi@0 | 68 | { |
| aoqi@0 | 69 | if( !this ) return os::strdup("{no set}"); |
| aoqi@0 | 70 | Set &set = clone(); // Virtually copy the basic set. |
| aoqi@0 | 71 | set.Sort(); // Sort elements for in-order retrieval |
| aoqi@0 | 72 | |
| aoqi@0 | 73 | uint len = 128; // Total string space |
| aoqi@0 | 74 | char *buf = NEW_C_HEAP_ARRAY(char,len, mtCompiler);// Some initial string space |
| aoqi@0 | 75 | |
| aoqi@0 | 76 | register char *s = buf; // Current working string pointer |
| aoqi@0 | 77 | *s++ = '{'; |
| aoqi@0 | 78 | *s = '\0'; |
| aoqi@0 | 79 | |
| aoqi@0 | 80 | // For all elements of the Set |
| aoqi@0 | 81 | uint hi = (uint)-2, lo = (uint)-2; |
| aoqi@0 | 82 | for( SetI i(&set); i.test(); ++i ) { |
| aoqi@0 | 83 | if( hi+1 == i.elem ) { // Moving sequentially thru range? |
| aoqi@0 | 84 | hi = i.elem; // Yes, just update hi end of range |
| aoqi@0 | 85 | } else { // Else range ended |
| aoqi@0 | 86 | if( buf+len-s < 25 ) { // Generous trailing space for upcoming numbers |
| aoqi@0 | 87 | int offset = (int)(s-buf);// Not enuf space; compute offset into buffer |
| aoqi@0 | 88 | len <<= 1; // Double string size |
| aoqi@0 | 89 | buf = REALLOC_C_HEAP_ARRAY(char,buf,len, mtCompiler); // Reallocate doubled size |
| aoqi@0 | 90 | s = buf+offset; // Get working pointer into new bigger buffer |
| aoqi@0 | 91 | } |
| aoqi@0 | 92 | if( lo != (uint)-2 ) { // Startup? No! Then print previous range. |
| aoqi@0 | 93 | if( lo != hi ) sprintf(s,"%d-%d,",lo,hi); |
| aoqi@0 | 94 | else sprintf(s,"%d,",lo); |
| aoqi@0 | 95 | s += strlen(s); // Advance working string |
| aoqi@0 | 96 | } |
| aoqi@0 | 97 | hi = lo = i.elem; |
| aoqi@0 | 98 | } |
| aoqi@0 | 99 | } |
| aoqi@0 | 100 | if( lo != (uint)-2 ) { |
| aoqi@0 | 101 | if( buf+len-s < 25 ) { // Generous trailing space for upcoming numbers |
| aoqi@0 | 102 | int offset = (int)(s-buf);// Not enuf space; compute offset into buffer |
| aoqi@0 | 103 | len <<= 1; // Double string size |
| aoqi@0 | 104 | buf = (char*)ReallocateHeap(buf,len, mtCompiler); // Reallocate doubled size |
| aoqi@0 | 105 | s = buf+offset; // Get working pointer into new bigger buffer |
| aoqi@0 | 106 | } |
| aoqi@0 | 107 | if( lo != hi ) sprintf(s,"%d-%d}",lo,hi); |
| aoqi@0 | 108 | else sprintf(s,"%d}",lo); |
| aoqi@0 | 109 | } else strcat(s,"}"); |
| aoqi@0 | 110 | // Don't delete the clone 'set' since it is allocated on Arena. |
| aoqi@0 | 111 | return buf; |
| aoqi@0 | 112 | } |
| aoqi@0 | 113 | |
| aoqi@0 | 114 | //------------------------------print------------------------------------------ |
| aoqi@0 | 115 | // Handier print routine |
| aoqi@0 | 116 | void Set::print() const |
| aoqi@0 | 117 | { |
| aoqi@0 | 118 | char *printable_set = setstr(); |
| aoqi@0 | 119 | tty->print_cr("%s", printable_set); |
| aoqi@0 | 120 | FreeHeap(printable_set); |
| aoqi@0 | 121 | } |
| aoqi@0 | 122 | |
| aoqi@0 | 123 | //------------------------------parse------------------------------------------ |
| aoqi@0 | 124 | // Convert a textual representation of a Set, to a Set and union into "this" |
| aoqi@0 | 125 | // Set. Return the amount of text parsed in "len", or zero in "len". |
| aoqi@0 | 126 | int Set::parse(const char *s) |
| aoqi@0 | 127 | { |
| aoqi@0 | 128 | register char c; // Parse character |
| aoqi@0 | 129 | register const char *t = s; // Save the starting position of s. |
| aoqi@0 | 130 | do c = *s++; // Skip characters |
| aoqi@0 | 131 | while( c && (c <= ' ') ); // Till no more whitespace or EOS |
| aoqi@0 | 132 | if( c != '{' ) return 0; // Oops, not a Set openner |
| aoqi@0 | 133 | if( *s == '}' ) return 2; // The empty Set |
| aoqi@0 | 134 | |
| aoqi@0 | 135 | // Sets are filled with values of the form "xx," or "xx-yy," with the comma |
| aoqi@0 | 136 | // a "}" at the very end. |
| aoqi@0 | 137 | while( 1 ) { // While have elements in the Set |
| aoqi@0 | 138 | char *u; // Pointer to character ending parse |
| aoqi@0 | 139 | uint hi, i; // Needed for range handling below |
| aoqi@0 | 140 | uint elem = (uint)strtoul(s,&u,10);// Get element |
| aoqi@0 | 141 | if( u == s ) return 0; // Bogus crude |
| aoqi@0 | 142 | s = u; // Skip over the number |
| aoqi@0 | 143 | c = *s++; // Get the number seperator |
| aoqi@0 | 144 | switch ( c ) { // Different seperators |
| aoqi@0 | 145 | case '}': // Last simple element |
| aoqi@0 | 146 | case ',': // Simple element |
| aoqi@0 | 147 | (*this) <<= elem; // Insert the simple element into the Set |
| aoqi@0 | 148 | break; // Go get next element |
| aoqi@0 | 149 | case '-': // Range |
| aoqi@0 | 150 | hi = (uint)strtoul(s,&u,10); // Get element |
| aoqi@0 | 151 | if( u == s ) return 0; // Bogus crude |
| aoqi@0 | 152 | for( i=elem; i<=hi; i++ ) |
| aoqi@0 | 153 | (*this) <<= i; // Insert the entire range into the Set |
| aoqi@0 | 154 | s = u; // Skip over the number |
| aoqi@0 | 155 | c = *s++; // Get the number seperator |
| aoqi@0 | 156 | break; |
| aoqi@0 | 157 | } |
| aoqi@0 | 158 | if( c == '}' ) break; // End of the Set |
| aoqi@0 | 159 | if( c != ',' ) return 0; // Bogus garbage |
| aoqi@0 | 160 | } |
| aoqi@0 | 161 | return (int)(s-t); // Return length parsed |
| aoqi@0 | 162 | } |
| aoqi@0 | 163 | |
| aoqi@0 | 164 | //------------------------------Iterator--------------------------------------- |
| aoqi@0 | 165 | SetI_::~SetI_() |
| aoqi@0 | 166 | { |
| aoqi@0 | 167 | } |
