1 // $Id: table.h,v 1.18 2004/03/25 13:32:29 ericb Exp $ -*- c++ -*- 2 // 3 // This software is subject to the terms of the IBM Jikes Compiler 4 // License Agreement available at the following URL: 5 // http://ibm.com/developerworks/opensource/jikes. 6 // Copyright (C) 1996, 2004 IBM Corporation and others. All Rights Reserved. 7 // You must accept the terms of that agreement to use this software. 8 // 9 10 #ifndef table_INCLUDED 11 #define table_INCLUDED 12 13 #include "platform.h" 14 #include "symbol.h" 15 16 #ifdef HAVE_JIKES_NAMESPACE 17 namespace Jikes { // Open namespace Jikes block 18 #endif 19 20 class VariableShadowSymbol 21 { 22 public: 23 VariableSymbol* variable_symbol; 24 VariableShadowSymbol(VariableSymbol * variable_symbol_)25 VariableShadowSymbol(VariableSymbol* variable_symbol_) 26 : variable_symbol(variable_symbol_), 27 conflict(NULL) 28 {} 29 ~VariableShadowSymbol()30 ~VariableShadowSymbol() 31 { 32 delete conflict; 33 } 34 Conflict(unsigned i)35 VariableSymbol* Conflict(unsigned i) const { return (*conflict)[i]; } 36 NumConflicts()37 inline unsigned NumConflicts() const 38 { 39 return conflict ? conflict -> Length() : 0; 40 } AddConflict(VariableSymbol * conflict_symbol)41 inline void AddConflict(VariableSymbol* conflict_symbol) 42 { 43 if (variable_symbol != conflict_symbol && ! Find(conflict_symbol)) 44 conflict -> Next() = conflict_symbol; 45 } CompressSpace()46 inline void CompressSpace() 47 { 48 if (conflict) 49 conflict -> Array(); 50 } 51 52 private: 53 friend class ExpandedFieldTable; 54 VariableShadowSymbol* next; 55 56 ConvertibleArray<VariableSymbol*>* conflict; 57 Find(const VariableSymbol * conflict_symbol)58 bool Find(const VariableSymbol* conflict_symbol) 59 { 60 if (! conflict) 61 conflict = new ConvertibleArray<VariableSymbol*>(4); 62 for (unsigned k = 0; k < conflict -> Length(); k++) 63 if ((*conflict)[k] == conflict_symbol) 64 return true; 65 return false; 66 } 67 }; 68 69 70 class MethodShadowSymbol 71 { 72 public: 73 MethodSymbol* method_symbol; 74 MethodShadowSymbol* next_method; 75 MethodShadowSymbol(MethodSymbol * method_symbol_)76 MethodShadowSymbol(MethodSymbol* method_symbol_) 77 : method_symbol(method_symbol_), 78 conflict(NULL) 79 {} 80 ~MethodShadowSymbol()81 ~MethodShadowSymbol() 82 { 83 delete conflict; 84 } 85 Conflict(unsigned i)86 MethodSymbol* Conflict(unsigned i) const { return (*conflict)[i]; } 87 NumConflicts()88 inline unsigned NumConflicts() const 89 { 90 return conflict ? conflict -> Length() : 0; 91 } AddConflict(MethodSymbol * conflict_symbol)92 inline void AddConflict(MethodSymbol* conflict_symbol) 93 { 94 if (method_symbol != conflict_symbol && ! Find(conflict_symbol)) 95 conflict -> Next() = conflict_symbol; 96 } 97 CompressSpace()98 inline void CompressSpace() 99 { 100 if (conflict) 101 conflict -> Array(); 102 } 103 104 private: 105 friend class ExpandedMethodTable; 106 MethodShadowSymbol* next; 107 108 ConvertibleArray<MethodSymbol*>* conflict; 109 Find(const MethodSymbol * conflict_symbol)110 bool Find(const MethodSymbol* conflict_symbol) 111 { 112 if (! conflict) 113 conflict = new ConvertibleArray<MethodSymbol*>(4); 114 for (unsigned k = 0; k < conflict -> Length(); k++) 115 if ((*conflict)[k] == conflict_symbol) 116 return true; 117 return false; 118 } 119 }; 120 121 122 class TypeShadowSymbol 123 { 124 public: 125 TypeSymbol* type_symbol; 126 TypeShadowSymbol(TypeSymbol * type_symbol_)127 TypeShadowSymbol(TypeSymbol* type_symbol_) 128 : type_symbol(type_symbol_), 129 conflict(NULL) 130 {} 131 ~TypeShadowSymbol()132 ~TypeShadowSymbol() 133 { 134 delete conflict; 135 } 136 Conflict(unsigned i)137 TypeSymbol* Conflict(unsigned i) const { return (*conflict)[i]; } 138 NumConflicts()139 inline unsigned NumConflicts() const 140 { 141 return conflict ? conflict -> Length() : 0; 142 } 143 AddConflict(TypeSymbol * conflict_symbol)144 inline void AddConflict(TypeSymbol* conflict_symbol) 145 { 146 if (type_symbol != conflict_symbol && ! Find(conflict_symbol)) 147 conflict -> Next() = conflict_symbol; 148 } 149 CompressSpace()150 inline void CompressSpace() 151 { 152 if (conflict) 153 conflict -> Array(); 154 } 155 156 private: 157 friend class ExpandedTypeTable; 158 TypeShadowSymbol* next; 159 160 ConvertibleArray<TypeSymbol*>* conflict; 161 Find(const TypeSymbol * conflict_symbol)162 bool Find(const TypeSymbol* conflict_symbol) 163 { 164 if (! conflict) 165 conflict = new ConvertibleArray<TypeSymbol*>(4); 166 for (unsigned k = 0; k < conflict -> Length(); k++) 167 if ((*conflict)[k] == conflict_symbol) 168 return true; 169 return false; 170 } 171 }; 172 173 174 class ExpandedTypeTable 175 { 176 public: 177 enum 178 { 179 DEFAULT_HASH_SIZE = 251, 180 MAX_HASH_SIZE = 509 181 }; 182 183 ConvertibleArray<TypeShadowSymbol*> symbol_pool; 184 CompressSpace()185 inline void CompressSpace() 186 { 187 hash_size = symbol_pool.Length(); 188 hash_size = hash_size <= 0 ? 1 : hash_size > MAX_HASH_SIZE 189 ? (unsigned) MAX_HASH_SIZE : hash_size; 190 delete [] base; 191 base = (TypeShadowSymbol**) 192 memset(new TypeShadowSymbol*[hash_size], 0, 193 hash_size * sizeof(TypeShadowSymbol*)); 194 195 TypeShadowSymbol** array = symbol_pool.Array(); 196 for (unsigned i = 0; i < symbol_pool.Length(); i++) 197 { 198 array[i] -> CompressSpace(); 199 200 unsigned k = 201 array[i] -> type_symbol -> name_symbol -> index % hash_size; 202 array[i] -> next = base[k]; 203 base[k] = array[i]; 204 } 205 } 206 207 ExpandedTypeTable(unsigned hash_size_ = DEFAULT_HASH_SIZE) 208 : symbol_pool(10, 4) 209 { 210 hash_size = hash_size_ <= 0 ? 1 : hash_size_ > MAX_HASH_SIZE 211 ? (unsigned) MAX_HASH_SIZE : hash_size_; 212 base = (TypeShadowSymbol**) 213 memset(new TypeShadowSymbol*[hash_size], 0, 214 hash_size * sizeof(TypeShadowSymbol*)); 215 } 216 ~ExpandedTypeTable()217 ~ExpandedTypeTable() 218 { 219 for (unsigned k = 0; k < symbol_pool.Length(); k++) 220 delete symbol_pool[k]; 221 delete [] base; 222 } 223 InsertTypeShadowSymbol(TypeSymbol * type_symbol)224 inline TypeShadowSymbol* InsertTypeShadowSymbol(TypeSymbol* type_symbol) 225 { 226 unsigned i = type_symbol -> name_symbol -> index % hash_size; 227 TypeShadowSymbol* p = new TypeShadowSymbol(type_symbol); 228 p -> next = base[i]; 229 base[i] = p; 230 symbol_pool.Next() = p; 231 232 return p; 233 } 234 FindTypeShadowSymbol(const NameSymbol * name_symbol)235 inline TypeShadowSymbol* FindTypeShadowSymbol(const NameSymbol* name_symbol) 236 { 237 TypeShadowSymbol* p; 238 for (p = base[name_symbol -> index % hash_size]; p; p = p -> next) 239 if (p -> type_symbol -> name_symbol == name_symbol) 240 break; 241 return p; 242 } 243 244 private: 245 TypeShadowSymbol** base; 246 unsigned hash_size; 247 }; 248 249 class ExpandedFieldTable 250 { 251 public: 252 enum 253 { 254 DEFAULT_HASH_SIZE = 251, 255 MAX_HASH_SIZE = 509 256 }; 257 258 ConvertibleArray<VariableShadowSymbol*> symbol_pool; 259 CompressSpace()260 inline void CompressSpace() 261 { 262 hash_size = symbol_pool.Length(); 263 hash_size = hash_size <= 0 ? 1 : hash_size > MAX_HASH_SIZE 264 ? (unsigned) MAX_HASH_SIZE : hash_size; 265 delete [] base; 266 base = (VariableShadowSymbol**) 267 memset(new VariableShadowSymbol*[hash_size], 0, 268 hash_size * sizeof(VariableShadowSymbol*)); 269 270 VariableShadowSymbol** array = symbol_pool.Array(); 271 for (unsigned i = 0; i < symbol_pool.Length(); i++) 272 { 273 array[i] -> CompressSpace(); 274 275 unsigned k = array[i] -> variable_symbol -> name_symbol -> index % 276 hash_size; 277 array[i] -> next = base[k]; 278 base[k] = array[i]; 279 } 280 } 281 282 ExpandedFieldTable(unsigned hash_size_ = DEFAULT_HASH_SIZE) 283 : symbol_pool(10, 4) 284 { 285 hash_size = hash_size_ <= 0 ? 1 : hash_size_ > MAX_HASH_SIZE 286 ? (unsigned) MAX_HASH_SIZE : hash_size_; 287 base = (VariableShadowSymbol**) 288 memset(new VariableShadowSymbol*[hash_size], 0, 289 hash_size * sizeof(VariableShadowSymbol*)); 290 } ~ExpandedFieldTable()291 ~ExpandedFieldTable() 292 { 293 for (unsigned i = 0; i < symbol_pool.Length(); i++) 294 delete symbol_pool[i]; 295 delete [] base; 296 } 297 InsertVariableShadowSymbol(VariableSymbol * variable_symbol)298 inline VariableShadowSymbol* InsertVariableShadowSymbol(VariableSymbol* variable_symbol) 299 { 300 unsigned i = variable_symbol -> name_symbol -> index % hash_size; 301 VariableShadowSymbol* p = new VariableShadowSymbol(variable_symbol); 302 p -> next = base[i]; 303 base[i] = p; 304 symbol_pool.Next() = p; 305 306 return p; 307 } 308 FindVariableShadowSymbol(const NameSymbol * name_symbol)309 inline VariableShadowSymbol* FindVariableShadowSymbol(const NameSymbol* name_symbol) 310 { 311 VariableShadowSymbol* p; 312 for (p = base[name_symbol -> index % hash_size]; p; p = p -> next) 313 if (p -> variable_symbol -> name_symbol == name_symbol) 314 break; 315 return p; 316 } 317 318 private: 319 VariableShadowSymbol** base; 320 unsigned hash_size; 321 }; 322 323 324 class ExpandedMethodTable 325 { 326 public: 327 enum 328 { 329 DEFAULT_HASH_SIZE = 251, 330 MAX_HASH_SIZE = 509 331 }; 332 333 ConvertibleArray<MethodShadowSymbol*> symbol_pool; 334 CompressSpace()335 inline void CompressSpace() 336 { 337 hash_size = symbol_pool.Length(); 338 hash_size = hash_size <= 0 ? 1 : hash_size > MAX_HASH_SIZE 339 ? (unsigned) MAX_HASH_SIZE : hash_size; 340 delete [] base; 341 base = (MethodShadowSymbol**) 342 memset(new MethodShadowSymbol*[hash_size], 0, 343 hash_size * sizeof(MethodShadowSymbol*)); 344 345 MethodShadowSymbol** array = symbol_pool.Array(); 346 for (unsigned i = 0; i < symbol_pool.Length(); i++) 347 { 348 array[i] -> CompressSpace(); 349 350 const NameSymbol* name_symbol = 351 array[i] -> method_symbol -> name_symbol; 352 MethodShadowSymbol* base_shadow = 353 FindMethodShadowSymbol(name_symbol); 354 if (! base_shadow) 355 { 356 unsigned k = name_symbol -> index % hash_size; 357 array[i] -> next = base[k]; 358 base[k] = array[i]; 359 array[i] -> next_method = NULL; 360 } 361 else 362 { 363 array[i] -> next_method = base_shadow -> next_method; 364 base_shadow -> next_method = array[i]; 365 } 366 } 367 } 368 369 ExpandedMethodTable(unsigned hash_size_ = DEFAULT_HASH_SIZE) 370 : symbol_pool(10, 4) 371 { 372 hash_size = hash_size_ <= 0 ? 1 : hash_size_ > MAX_HASH_SIZE 373 ? (unsigned) MAX_HASH_SIZE : hash_size_; 374 base = (MethodShadowSymbol**) 375 memset(new MethodShadowSymbol*[hash_size], 0, 376 hash_size * sizeof(MethodShadowSymbol*)); 377 } ~ExpandedMethodTable()378 ~ExpandedMethodTable() 379 { 380 for (unsigned i = 0; i < symbol_pool.Length(); i++) 381 delete symbol_pool[i]; 382 delete [] base; 383 } 384 FindMethodShadowSymbol(const NameSymbol * name_symbol)385 inline MethodShadowSymbol* FindMethodShadowSymbol(const NameSymbol* name_symbol) 386 { 387 MethodShadowSymbol* p; 388 for (p = base[name_symbol -> index % hash_size]; p; p = p -> next) 389 if (p -> method_symbol -> name_symbol == name_symbol) 390 break; 391 return p; 392 } 393 InsertMethodShadowSymbol(MethodSymbol * method_symbol)394 inline MethodShadowSymbol* InsertMethodShadowSymbol(MethodSymbol* method_symbol) 395 { 396 unsigned i = method_symbol -> name_symbol -> index % hash_size; 397 MethodShadowSymbol* p = new MethodShadowSymbol(method_symbol); 398 p -> next_method = NULL; 399 p -> next = base[i]; 400 base[i] = p; 401 symbol_pool.Next() = p; 402 403 return p; 404 } 405 Overload(MethodShadowSymbol * base_shadow,MethodSymbol * overload_method)406 inline void Overload(MethodShadowSymbol* base_shadow, 407 MethodSymbol* overload_method) 408 { 409 // 410 // Insert the new overload as the second list element, to preserve 411 // the existing base, while making Overload(MethodSymbol*) work. 412 // 413 MethodShadowSymbol* shadow = new MethodShadowSymbol(overload_method); 414 symbol_pool.Next() = shadow; 415 shadow -> next_method = base_shadow -> next_method; 416 base_shadow -> next_method = shadow; 417 } 418 Overload(MethodSymbol * overload_method)419 inline MethodShadowSymbol* Overload(MethodSymbol* overload_method) 420 { 421 MethodShadowSymbol* base_shadow = 422 FindMethodShadowSymbol(overload_method -> name_symbol); 423 if (! base_shadow) 424 return InsertMethodShadowSymbol(overload_method); 425 Overload(base_shadow, overload_method); 426 // 427 // Return the newly created overload; this relies on the current 428 // behavior of Overload(MethodSymbol*, MethodSymbol*). 429 // 430 return base_shadow -> next_method; 431 } 432 FindOverloadMethodShadow(MethodSymbol * overload_method,Semantic * sem,TokenIndex tok)433 MethodShadowSymbol* FindOverloadMethodShadow(MethodSymbol* overload_method, 434 Semantic* sem, TokenIndex tok) 435 { 436 if (! overload_method -> IsTyped()) 437 overload_method -> ProcessMethodSignature(sem, tok); 438 439 MethodShadowSymbol* method_shadow; 440 for (method_shadow = FindMethodShadowSymbol(overload_method -> 441 name_symbol); 442 method_shadow; 443 method_shadow = method_shadow -> next_method) 444 { 445 MethodSymbol* method = method_shadow -> method_symbol; 446 447 if (overload_method == method) 448 return method_shadow; 449 450 if (! method -> IsTyped()) 451 method -> ProcessMethodSignature(sem, tok); 452 453 if (overload_method -> NumFormalParameters() == 454 method -> NumFormalParameters()) 455 { 456 int i; 457 for (i = method -> NumFormalParameters() - 1; i >= 0; i--) 458 { 459 if (method -> FormalParameter(i) -> Type() != 460 overload_method -> FormalParameter(i) -> Type()) 461 { 462 break; 463 } 464 } 465 466 if (i < 0) 467 return method_shadow; 468 } 469 } 470 471 return method_shadow; 472 } 473 474 private: 475 MethodShadowSymbol** base; 476 unsigned hash_size; 477 }; 478 479 #ifdef HAVE_JIKES_NAMESPACE 480 } // Close namespace Jikes block 481 #endif 482 483 #endif // table_INCLUDED 484 485