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