tables.c

   1 /* tables.c -
   2
   3    Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003
   4    R. Grafl, A. Krall, C. Kruegel, C. Oates, R. Obermaisser,
   5    M. Probst, S. Ring, E. Steiner, C. Thalinger, D. Thuernbeck,
   6    P. Tomsich, J. Wenninger
   7
   8    This file is part of CACAO.
   9
  10    This program is free software; you can redistribute it and/or
  11    modify it under the terms of the GNU General Public License as
  12    published by the Free Software Foundation; either version 2, or (at
  13    your option) any later version.
  14
  15    This program is distributed in the hope that it will be useful, but
  16    WITHOUT ANY WARRANTY; without even the implied warranty of
  17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18    General Public License for more details.
  19
  20    You should have received a copy of the GNU General Public License
  21    along with this program; if not, write to the Free Software
  22    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  23    02111-1307, USA.
  24
  25    Contact: cacao@complang.tuwien.ac.at
  26
  27    Authors: Reinhard Grafl
  28
  29    Changes: Mark Probst
  30             Andreas Krall
  31
  32    Contains support functions for:
  33        - Reading of Java class files
  34        - Unicode symbols
  35        - the heap
  36        - additional support functions
  37
  38    $Id: tables.c 562 2003-11-03 00:34:34Z twisti $
  39
  40 */
  41
  42 #include <string.h>
  43 #include <assert.h>
  44 #include <sys/types.h>
  45 #include <sys/mman.h>
  46 #include <unistd.h>
  47 #include "types.h"
  48 #include "global.h"
  49 #include "tables.h"
  50 #include "asmpart.h"
  51 #include "threads/thread.h"
  52 #include "threads/locks.h"
  53 #include "toolbox/loging.h"
  54 #include "toolbox/memory.h"
  55
  56
  57 bool runverbose = false;
  58
  59 /* statistics */
  60 int count_utf_len = 0;         /* size of utf hash                  */
  61 int count_utf_new = 0;         /* calls of utf_new                  */
  62 int count_utf_new_found  = 0;  /* calls of utf_new with fast return */
  63
  64 hashtable utf_hash;     /* hashtable for utf8-symbols */
  65 hashtable string_hash;  /* hashtable for javastrings  */
  66 hashtable class_hash;   /* hashtable for classes      */
  67
  68 /******************************************************************************
  69  *********************** hashtable functions **********************************
  70  ******************************************************************************/
  71
  72 /* hashsize must be power of 2 */
  73
  74 #define UTF_HASHSTART   16384   /* initial size of utf-hash */
  75 #define HASHSTART        2048   /* initial size of javastring and class-hash */
  76
  77
  78 /******************** function: init_hashtable ******************************
  79
  80     Initializes a hashtable structure and allocates memory.
  81     The parameter size specifies the initial size of the hashtable.
  82
  83 *****************************************************************************/
  84
  85 void init_hashtable(hashtable *hash, u4 size)
  86 {
  87         u4 i;
  88
  89         hash->entries = 0;
  90         hash->size    = size;
  91         hash->ptr     = MNEW(void*, size);
  92
  93         /* clear table */
  94         for (i = 0; i < size; i++) hash->ptr[i] = NULL;
  95 }
  96
  97 /*********************** function: tables_init  *****************************
  98
  99     creates hashtables for symboltables
 100         (called once at startup)
 101
 102 *****************************************************************************/
 103
 104 void tables_init ()
 105 {
 106         init_hashtable(&utf_hash,    UTF_HASHSTART);  /* hashtable for utf8-symbols */
 107         init_hashtable(&string_hash, HASHSTART);      /* hashtable for javastrings */
 108         init_hashtable(&class_hash,  HASHSTART);      /* hashtable for classes */
 109
 110 #ifdef STATISTICS
 111         count_utf_len += sizeof(utf*) * utf_hash.size;
 112 #endif
 113
 114 }
 115
 116 /********************** function: tables_close ******************************
 117
 118         free memory for hashtables
 119
 120 *****************************************************************************/
 121
 122 void tables_close (stringdeleter del)
 123 {
 124         utf *u;
 125         literalstring *s;
 126         u4 i;
 127
 128         /* dispose utf symbols */
 129         for (i=0; i<utf_hash.size; i++) {
 130                 u = utf_hash.ptr[i];
 131                 while (u) {
 132                         /* process elements in external hash chain */
 133                         utf *nextu = u->hashlink;
 134                         MFREE (u->text, u1, u->blength);
 135                         FREE (u, utf);
 136                         u = nextu;
 137                 }
 138         }
 139
 140         /* dispose javastrings */
 141         for (i=0; i<string_hash.size; i++) {
 142                 s = string_hash.ptr[i];
 143                 while (u) {
 144                         /* process elements in external hash chain */
 145                         literalstring *nexts = s->hashlink;
 146                         del(s->string);
 147                         FREE(s, literalstring);
 148                         s = nexts;
 149                 }
 150         }
 151
 152         /* dispose hashtable structures */
 153         MFREE (utf_hash.ptr,    void*, utf_hash.size);
 154         MFREE (string_hash.ptr, void*, string_hash.size);
 155         MFREE (class_hash.ptr,  void*, class_hash.size);
 156 }
 157
 158 /********************* function: utf_display *********************************
 159
 160         write utf symbol to stdout (debugging purposes)
 161
 162 ******************************************************************************/
 163
 164 void utf_display (utf *u)
 165 {
 166     char *endpos  = utf_end(u);  /* points behind utf string       */
 167     char *utf_ptr = u->text;     /* current position in utf text   */
 168         if (u==NULL) return;
 169     while (utf_ptr<endpos) {
 170
 171                 /* read next unicode character */
 172                 u2 c = utf_nextu2(&utf_ptr);
 173                 if (c>=32 && c<=127) printf ("%c",c);
 174                 else printf ("?");
 175         }
 176
 177         fflush (stdout);
 178 }
 179
 180 /************************ function: utf_sprint *******************************
 181
 182     write utf symbol into c-string (debugging purposes)
 183
 184 ******************************************************************************/
 185
 186 void utf_sprint (char *buffer, utf *u)
 187 {
 188     char *endpos  = utf_end(u);  /* points behind utf string       */
 189     char *utf_ptr = u->text;     /* current position in utf text   */
 190     u2 pos = 0;                  /* position in c-string           */
 191
 192     while (utf_ptr<endpos)
 193                 /* copy next unicode character */
 194                 buffer[pos++] = utf_nextu2(&utf_ptr);
 195
 196     /* terminate string */
 197     buffer[pos] = '\0';
 198 }
 199
 200
 201 /********************* Funktion: utf_fprint **********************************
 202
 203     write utf symbol into file
 204
 205 ******************************************************************************/
 206
 207 void utf_fprint (FILE *file, utf *u)
 208 {
 209     char *endpos  = utf_end(u);  /* points behind utf string       */
 210     char *utf_ptr = u->text;     /* current position in utf text   */
 211     if (u==NULL) return;
 212     while (utf_ptr<endpos) {
 213                 /* read next unicode character */
 214                 u2 c = utf_nextu2(&utf_ptr);
 215
 216                 if (c>=32 && c<=127) fprintf (file,"%c",c);
 217                 else fprintf (file,"?");
 218         }
 219 }
 220
 221
 222 /****************** internal function: utf_hashkey ***************************
 223
 224         The hashkey is computed from the utf-text by using up to 8 characters.
 225         For utf-symbols longer than 15 characters 3 characters are taken from
 226         the beginning and the end, 2 characters are taken from the middle.
 227
 228 ******************************************************************************/
 229
 230 #define nbs(val) ((u4) *(++text) << val) /* get next byte, left shift by val  */
 231 #define fbs(val) ((u4) *(  text) << val) /* get first byte, left shift by val */
 232
 233 static u4 utf_hashkey (char *text, u4 length)
 234 {
 235         char *start_pos = text; /* pointer to utf text */
 236         u4 a;
 237
 238         switch (length) {
 239
 240         case 0: /* empty string */
 241                 return 0;
 242
 243         case 1: return fbs(0);
 244         case 2: return fbs(0) ^ nbs(3);
 245         case 3: return fbs(0) ^ nbs(3) ^ nbs(5);
 246         case 4: return fbs(0) ^ nbs(2) ^ nbs(4) ^ nbs(6);
 247         case 5: return fbs(0) ^ nbs(2) ^ nbs(3) ^ nbs(4) ^ nbs(6);
 248         case 6: return fbs(0) ^ nbs(1) ^ nbs(2) ^ nbs(3) ^ nbs(5) ^ nbs(6);
 249         case 7: return fbs(0) ^ nbs(1) ^ nbs(2) ^ nbs(3) ^ nbs(4) ^ nbs(5) ^ nbs(6);
 250         case 8: return fbs(0) ^ nbs(1) ^ nbs(2) ^ nbs(3) ^ nbs(4) ^ nbs(5) ^ nbs(6) ^ nbs(7);
 251
 252         case 9: a = fbs(0) ^ nbs(1) ^ nbs(2);
 253                 text++;
 254                 return a ^ nbs(4) ^ nbs(5) ^ nbs(6) ^ nbs(7) ^ nbs(8);
 255
 256         case 10: a = fbs(0);
 257                 text++;
 258                 a^= nbs(2) ^ nbs(3) ^ nbs(4);
 259                 text++;
 260                 return a ^ nbs(6) ^ nbs(7) ^ nbs(8) ^ nbs(9);
 261
 262         case 11: a = fbs(0);
 263                 text++;
 264                 a^= nbs(2) ^ nbs(3) ^ nbs(4);
 265                 text++;
 266                 return a ^ nbs(6) ^ nbs(7) ^ nbs(8) ^ nbs(9) ^ nbs(10);
 267
 268         case 12: a = fbs(0);
 269                 text+=2;
 270                 a^= nbs(2) ^ nbs(3);
 271                 text+=1;
 272                 a^= nbs(5) ^ nbs(6) ^ nbs(7);
 273                 text+=1;
 274                 return a ^ nbs(9) ^ nbs(10);
 275
 276         case 13: a = fbs(0) ^ nbs(1);
 277                 text+=1;
 278                 a^= nbs(3) ^ nbs(4);
 279                 text+=2;
 280                 a^= nbs(7) ^ nbs(8);
 281                 text+=2;
 282                 return a ^ nbs(9) ^ nbs(10);
 283
 284         case 14: a = fbs(0);
 285                 text+=2;
 286                 a^= nbs(3) ^ nbs(4);
 287                 text+=2;
 288                 a^= nbs(7) ^ nbs(8);
 289                 text+=2;
 290                 return a ^ nbs(9) ^ nbs(10) ^ nbs(11);
 291
 292         case 15: a = fbs(0);
 293                 text+=2;
 294                 a^= nbs(3) ^ nbs(4);
 295                 text+=2;
 296                 a^= nbs(7) ^ nbs(8);
 297                 text+=2;
 298                 return a ^ nbs(9) ^ nbs(10) ^ nbs(11);
 299
 300         default:  /* 3 characters from beginning */
 301                 a = fbs(0);
 302                 text+=2;
 303                 a^= nbs(3) ^ nbs(4);
 304
 305                 /* 2 characters from middle */
 306                 text = start_pos + (length / 2);
 307                 a^= fbs(5);
 308                 text+=2;
 309                 a^= nbs(6);
 310
 311                 /* 3 characters from end */
 312                 text = start_pos + length - 4;
 313
 314                 a^= fbs(7);
 315                 text+=1;
 316
 317                 return a ^ nbs(10) ^ nbs(11);
 318     }
 319 }
 320
 321
 322 /*************************** function: utf_hashkey ***************************
 323
 324     compute the hashkey of a unicode string
 325
 326 ******************************************************************************/
 327
 328 u4 unicode_hashkey (u2 *text, u2 len)
 329 {
 330         return utf_hashkey((char*) text, len);
 331 }
 332
 333 /************************ function: utf_new **********************************
 334
 335         Creates a new utf-symbol, the text of the symbol is passed as a
 336         u1-array. The function searches the utf-hashtable for a utf-symbol
 337         with this text. On success the element returned, otherwise a new
 338         hashtable element is created.
 339
 340         If the number of entries in the hashtable exceeds twice the size of the
 341         hashtable slots a reorganization of the hashtable is done and the utf
 342         symbols are copied to a new hashtable with doubled size.
 343
 344 ******************************************************************************/
 345
 346 utf *utf_new (char *text, u2 length)
 347 {
 348         u4 key;            /* hashkey computed from utf-text */
 349         u4 slot;           /* slot in hashtable */
 350         utf *u;            /* hashtable element */
 351         u2 i;
 352
 353 #ifdef STATISTICS
 354         count_utf_new++;
 355 #endif
 356
 357         key  = utf_hashkey (text, length);
 358         slot = key & (utf_hash.size-1);
 359         u    = utf_hash.ptr[slot];
 360
 361         /* search external hash chain for utf-symbol */
 362         while (u) {
 363                 if (u->blength == length) {
 364
 365                         /* compare text of hashtable elements */
 366                         for (i=0; i<length; i++)
 367                                 if (text[i] != u->text[i]) goto nomatch;
 368
 369 #ifdef STATISTICS
 370                         count_utf_new_found++;
 371 #endif
 372                         /* symbol found in hashtable */
 373                         return u;
 374                 }
 375         nomatch:
 376                 u = u->hashlink; /* next element in external chain */
 377         }
 378
 379 #ifdef STATISTICS
 380         count_utf_len += sizeof(utf) + length;
 381 #endif
 382
 383         /* location in hashtable found, create new utf element */
 384         u = NEW (utf);
 385         u->blength  = length;             /* length in bytes of utfstring */
 386         u->hashlink = utf_hash.ptr[slot]; /* link in external hashchain   */
 387         u->text     = mem_alloc(length);  /* allocate memory for utf-text */
 388         memcpy(u->text,text,length);      /* copy utf-text                */
 389         utf_hash.ptr[slot] = u;           /* insert symbol into table     */
 390
 391         utf_hash.entries++;               /* update number of entries     */
 392
 393         if ( utf_hash.entries > (utf_hash.size*2)) {
 394
 395         /* reorganization of hashtable, average length of
 396            the external chains is approx. 2                */
 397
 398                 u4 i;
 399                 utf *u;
 400                 hashtable newhash; /* the new hashtable */
 401
 402                 /* create new hashtable, double the size */
 403                 init_hashtable(&newhash, utf_hash.size*2);
 404                 newhash.entries=utf_hash.entries;
 405
 406 #ifdef STATISTICS
 407                 count_utf_len += sizeof(utf*) * utf_hash.size;
 408 #endif
 409
 410                 /* transfer elements to new hashtable */
 411                 for (i=0; i<utf_hash.size; i++) {
 412                         u = (utf*) utf_hash.ptr[i];
 413                         while (u) {
 414                                 utf *nextu = u -> hashlink;
 415                                 u4 slot = (utf_hashkey(u->text,u->blength)) & (newhash.size-1);
 416
 417                                 u->hashlink = (utf*) newhash.ptr[slot];
 418                                 newhash.ptr[slot] = u;
 419
 420                                 /* follow link in external hash chain */
 421                                 u = nextu;
 422                         }
 423                 }
 424
 425                 /* dispose old table */
 426                 MFREE (utf_hash.ptr, void*, utf_hash.size);
 427                 utf_hash = newhash;
 428         }
 429
 430         return u;
 431 }
 432
 433
 434 /********************* function: utf_new_char ********************************
 435
 436     creates a new utf symbol, the text for this symbol is passed
 437     as a c-string ( = char* )
 438
 439 ******************************************************************************/
 440
 441 utf *utf_new_char (char *text)
 442 {
 443         return utf_new(text, strlen(text));
 444 }
 445
 446 /************************** Funktion: utf_show ******************************
 447
 448     writes the utf symbols in the utfhash to stdout and
 449     displays the number of external hash chains grouped
 450     according to the chainlength
 451     (debugging purposes)
 452
 453 *****************************************************************************/
 454
 455 void utf_show ()
 456 {
 457
 458 #define CHAIN_LIMIT 20               /* limit for seperated enumeration */
 459
 460         u4 chain_count[CHAIN_LIMIT]; /* numbers of chains */
 461         u4 max_chainlength = 0;      /* maximum length of the chains */
 462         u4 sum_chainlength = 0;      /* sum of the chainlengths */
 463         u4 beyond_limit = 0;         /* number of utf-symbols in chains with length>=CHAIN_LIMIT-1 */
 464         u4 i;
 465
 466         printf ("UTF-HASH:\n");
 467
 468         /* show element of utf-hashtable */
 469         for (i=0; i<utf_hash.size; i++) {
 470                 utf *u = utf_hash.ptr[i];
 471                 if (u) {
 472                         printf ("SLOT %d: ", (int) i);
 473                         while (u) {
 474                                 printf ("'");
 475                                 utf_display (u);
 476                                 printf ("' ");
 477                                 u = u->hashlink;
 478                         }
 479                         printf ("\n");
 480                 }
 481
 482         }
 483
 484         printf ("UTF-HASH: %d slots for %d entries\n",
 485                         (int) utf_hash.size, (int) utf_hash.entries );
 486
 487
 488         if (utf_hash.entries == 0)
 489                 return;
 490
 491         printf("chains:\n  chainlength    number of chains    %% of utfstrings\n");
 492
 493         for (i=0;i<CHAIN_LIMIT;i++)
 494                 chain_count[i]=0;
 495
 496         /* count numbers of hashchains according to their length */
 497         for (i=0; i<utf_hash.size; i++) {
 498
 499                 utf *u = (utf*) utf_hash.ptr[i];
 500                 u4 chain_length = 0;
 501
 502                 /* determine chainlength */
 503                 while (u) {
 504                         u = u->hashlink;
 505                         chain_length++;
 506                 }
 507
 508                 /* update sum of all chainlengths */
 509                 sum_chainlength+=chain_length;
 510
 511                 /* determine the maximum length of the chains */
 512                 if (chain_length>max_chainlength)
 513                         max_chainlength = chain_length;
 514
 515                 /* update number of utf-symbols in chains with length>=CHAIN_LIMIT-1 */
 516                 if (chain_length>=CHAIN_LIMIT) {
 517                         beyond_limit+=chain_length;
 518                         chain_length=CHAIN_LIMIT-1;
 519                 }
 520
 521                 /* update number of hashchains of current length */
 522                 chain_count[chain_length]++;
 523         }
 524
 525         /* display results */
 526         for (i=1;i<CHAIN_LIMIT-1;i++)
 527                 printf("       %2d %17d %18.2f%%\n",i,chain_count[i],(((float) chain_count[i]*i*100)/utf_hash.entries));
 528
 529         printf("     >=%2d %17d %18.2f%%\n",CHAIN_LIMIT-1,chain_count[CHAIN_LIMIT-1],((float) beyond_limit*100)/utf_hash.entries);
 530
 531
 532         printf("max. chainlength:%5d\n",max_chainlength);
 533
 534         /* avg. chainlength = sum of chainlengths / number of chains */
 535         printf("avg. chainlength:%5.2f\n",(float) sum_chainlength / (utf_hash.size-chain_count[0]));
 536 }
 537
 538 /******************************************************************************
 539 *********************** Misc support functions ********************************
 540 ******************************************************************************/
 541
 542
 543 /******************** Function: desc_to_type **********************************
 544
 545         Determines the corresponding Java base data type for a given type
 546         descriptor.
 547
 548 ******************************************************************************/
 549
 550 u2 desc_to_type(utf *descriptor)
 551 {
 552         char *utf_ptr = descriptor->text;  /* current position in utf text */
 553
 554         if (descriptor->blength < 1) panic("Type-Descriptor is empty string");
 555
 556         switch (*utf_ptr++) {
 557         case 'B':
 558         case 'C':
 559         case 'I':
 560         case 'S':
 561         case 'Z':  return TYPE_INT;
 562         case 'D':  return TYPE_DOUBLE;
 563         case 'F':  return TYPE_FLOAT;
 564         case 'J':  return TYPE_LONG;
 565         case 'L':
 566         case '[':  return TYPE_ADDRESS;
 567         }
 568
 569         sprintf(logtext, "Invalid Type-Descriptor: ");
 570         utf_sprint(logtext+strlen(logtext), descriptor);
 571         error();
 572
 573         return 0;
 574 }
 575
 576
 577 /********************** Function: desc_typesize *******************************
 578
 579         Calculates the lenght in bytes needed for a data element of the type given
 580         by its type descriptor.
 581
 582 ******************************************************************************/
 583
 584 u2 desc_typesize (utf *descriptor)
 585 {
 586         switch (desc_to_type(descriptor)) {
 587         case TYPE_INT:     return 4;
 588         case TYPE_LONG:    return 8;
 589         case TYPE_FLOAT:   return 4;
 590         case TYPE_DOUBLE:  return 8;
 591         case TYPE_ADDRESS: return sizeof(voidptr);
 592         default:           return 0;
 593         }
 594 }
 595
 596
 597 /********************** function: utf_nextu2 *********************************
 598
 599     read the next unicode character from the utf string and
 600     increment the utf-string pointer accordingly
 601
 602 ******************************************************************************/
 603
 604 u2 utf_nextu2(char **utf_ptr)
 605 {
 606     /* uncompressed unicode character */
 607     u2 unicode_char;
 608     /* current position in utf text */
 609     unsigned char *utf = (unsigned char *) (*utf_ptr);
 610     /* bytes representing the unicode character */
 611     unsigned char ch1, ch2, ch3;
 612     /* number of bytes used to represent the unicode character */
 613     int len;
 614
 615     switch ((ch1 = utf[0]) >> 4) {
 616         default: /* 1 byte */
 617                 (*utf_ptr)++;
 618                 return ch1;
 619         case 0xC:
 620         case 0xD: /* 2 bytes */
 621                 if (((ch2 = utf[1]) & 0xC0) == 0x80) {
 622                         unsigned char high = ch1 & 0x1F;
 623                         unsigned char low  = ch2 & 0x3F;
 624                         unicode_char = (high << 6) + low;
 625                         len = 2;
 626                 }
 627                 break;
 628
 629         case 0xE: /* 2 or 3 bytes */
 630                 if (((ch2 = utf[1]) & 0xC0) == 0x80) {
 631                         if (((ch3 = utf[2]) & 0xC0) == 0x80) {
 632                                 unsigned char low  = ch3 & 0x3f;
 633                                 unsigned char mid  = ch2 & 0x3f;
 634                                 unsigned char high = ch1 & 0x0f;
 635                                 unicode_char = (((high << 6) + mid) << 6) + low;
 636                                 len = 3;
 637                         } else
 638                                 len = 2;
 639                 }
 640                 break;
 641     }
 642
 643     /* update position in utf-text */
 644     *utf_ptr = (char *) (utf + len);
 645     return unicode_char;
 646 }
 647
 648
 649 /******************** Function: class_new **************************************
 650
 651     searches for the class with the specified name in the classes hashtable,
 652     if there is no such class a new classinfo structure is created and inserted
 653     into the list of classes to be loaded
 654
 655 *******************************************************************************/
 656
 657 classinfo *class_new(utf *u)
 658 {
 659         classinfo *c;     /* hashtable element */
 660         u4 key;           /* hashkey computed from classname */
 661         u4 slot;          /* slot in hashtable */
 662         u2 i;
 663
 664         key  = utf_hashkey (u->text, u->blength);
 665         slot = key & (class_hash.size-1);
 666         c    = class_hash.ptr[slot];
 667
 668         /* search external hash chain for the class */
 669         while (c) {
 670                 if (c->name->blength == u->blength) {
 671                         for (i=0; i<u->blength; i++)
 672                                 if (u->text[i] != c->name->text[i]) goto nomatch;
 673
 674                         /* class found in hashtable */
 675                         return c;
 676                 }
 677
 678         nomatch:
 679                 c = c->hashlink; /* next element in external chain */
 680         }
 681
 682         /* location in hashtable found, create new classinfo structure */
 683
 684 #ifdef STATISTICS
 685         count_class_infos += sizeof(classinfo);
 686 #endif
 687
 688         c = NEW(classinfo);
 689         c->flags = 0;
 690         c->name = u;
 691         c->cpcount = 0;
 692         c->cptags = NULL;
 693         c->cpinfos = NULL;
 694         c->super = NULL;
 695         c->sub = NULL;
 696         c->nextsub = NULL;
 697         c->interfacescount = 0;
 698         c->interfaces = NULL;
 699         c->fieldscount = 0;
 700         c->fields = NULL;
 701         c->methodscount = 0;
 702         c->methods = NULL;
 703         c->linked = false;
 704         c->index = 0;
 705         c->instancesize = 0;
 706         c->header.vftbl = NULL;
 707         c->innerclasscount = 0;
 708         c->innerclass = NULL;
 709         c->vftbl = NULL;
 710         c->initialized = false;
 711         c->classvftbl = false;
 712
 713         /* prepare loading of the class */
 714         list_addlast(&unloadedclasses, c);
 715
 716         /* insert class into the hashtable */
 717         c->hashlink = class_hash.ptr[slot];
 718         class_hash.ptr[slot] = c;
 719
 720         /* update number of hashtable-entries */
 721         class_hash.entries++;
 722
 723         if (class_hash.entries > (class_hash.size*2)) {
 724
 725                 /* reorganization of hashtable, average length of
 726                    the external chains is approx. 2                */
 727
 728                 u4 i;
 729                 classinfo *c;
 730                 hashtable newhash;  /* the new hashtable */
 731
 732                 /* create new hashtable, double the size */
 733                 init_hashtable(&newhash, class_hash.size*2);
 734                 newhash.entries = class_hash.entries;
 735
 736                 /* transfer elements to new hashtable */
 737                 for (i = 0; i < class_hash.size; i++) {
 738                         c = (classinfo*) class_hash.ptr[i];
 739                         while (c) {
 740                                 classinfo *nextc = c->hashlink;
 741                                 u4 slot = (utf_hashkey(c->name->text, c->name->blength)) & (newhash.size - 1);
 742
 743                                 c->hashlink = newhash.ptr[slot];
 744                                 newhash.ptr[slot] = c;
 745
 746                                 c = nextc;
 747                         }
 748                 }
 749
 750                 /* dispose old table */
 751                 MFREE(class_hash.ptr, void*, class_hash.size);
 752                 class_hash = newhash;
 753         }
 754
 755         return c;
 756 }
 757
 758 /******************** Function: class_get **************************************
 759
 760     searches for the class with the specified name in the classes hashtable
 761     if there is no such class NULL is returned
 762
 763 *******************************************************************************/
 764
 765 classinfo *class_get(utf *u)
 766 {
 767         classinfo *c;  /* hashtable element */
 768         u4 key;        /* hashkey computed from classname */
 769         u4 slot;       /* slot in hashtable */
 770         u2 i;
 771
 772         key  = utf_hashkey (u->text, u->blength);
 773         slot = key & (class_hash.size-1);
 774         c    = class_hash.ptr[slot];
 775
 776         /* search external hash-chain */
 777         while (c) {
 778                 if (c->name->blength == u->blength) {
 779
 780                         /* compare classnames */
 781                         for (i=0; i<u->blength; i++)
 782                                 if (u->text[i] != c->name->text[i]) goto nomatch;
 783
 784                         /* class found in hashtable */
 785                         return c;
 786                 }
 787
 788         nomatch:
 789                 c = c->hashlink;
 790         }
 791
 792         /* class not found */
 793         return NULL;
 794 }
 795
 796
 797 /************************** function: utf_strlen ******************************
 798
 799     determine number of unicode characters in the utf string
 800
 801 *******************************************************************************/
 802
 803 u4 utf_strlen(utf *u)
 804 {
 805     char *endpos  = utf_end(u);  /* points behind utf string       */
 806     char *utf_ptr = u->text;     /* current position in utf text   */
 807     u4 len = 0;                  /* number of unicode characters   */
 808
 809     while (utf_ptr<endpos) {
 810                 len++;
 811                 /* next unicode character */
 812                 utf_nextu2(&utf_ptr);
 813     }
 814
 815     if (utf_ptr!=endpos)
 816         /* string ended abruptly */
 817                 panic("illegal utf string");
 818
 819     return len;
 820 }
 821
 822
 823 /*
 824  * These are local overrides for various environment variables in Emacs.
 825  * Please do not remove this and leave it at the end of the file, where
 826  * Emacs will automagically detect them.
 827  * ---------------------------------------------------------------------
 828  * Local variables:
 829  * mode: c
 830  * indent-tabs-mode: t
 831  * c-basic-offset: 4
 832  * tab-width: 4
 833  * End:
 834  */