See file COPYRIGHT for information on usage and disclaimer of warranties
- Enth"alt Supportfunktionen f"ur:
- - Lesen von JavaClass-Files
- - unicode-Symbole
- - den Heap
- - zus"atzliche Support-Funktionen
+ Contains support functions for:
+ - Reading of Java class files
+ - Unicode symbols
+ - the heap
+ - additional support functions
Authors: Reinhard Grafl EMAIL: cacao@complang.tuwien.ac.at
Changes: Mark Probst EMAIL: cacao@complang.tuwien.ac.at
Andreas Krall EMAIL: cacao@complang.tuwien.ac.at
-
+
Last Change: 1998/03/24
*******************************************************************************/
#include "threads/thread.h" /* schani */
#include "threads/locks.h"
-
bool runverbose = false;
-int count_unicode_len = 0;
+/* statistics */
+int count_utf_len = 0; /* size of utf hash */
+int count_utf_new = 0; /* calls of utf_new */
+int count_utf_new_found = 0; /* calls of utf_new with fast return */
+hashtable utf_hash; /* hashtable for utf8-symbols */
+hashtable string_hash; /* hashtable for javastrings */
+hashtable class_hash; /* hashtable for classes */
/******************************************************************************
-************************* Der Dateien-Sauger **********************************
-*******************************************************************************
-
- dient zum Behandeln von Java-ClassFiles ("offnen, schlie"sen,
- einlesen von 8-, 16-, 32-, 64-bit Integers und 32-, 64- bit Floats)
-
-******************************************************************************/
-
-static FILE *classfile = NULL; /* File-handle der gerade gelesenen Datei */
-static char *classpath = ""; /* Suchpfad f"ur die ClassFiles */
-
-
-
-/************************** Funktion: suck_init ******************************
-
- Wird zu Programmstart einmal aufgerufen und setzt den Suchpfad f"ur
- Klassenfiles
-
-******************************************************************************/
-
-void suck_init (char *cpath)
-{
- classfile = NULL;
- classpath = cpath;
-}
-
-
-/************************** Funktion: suck_start ******************************
-
- "Offnet die Datei f"ur die Klasse des gegebenen Namens zum Lesen.
- Dabei werden alle im Suchpfad angegebenen Verzeichnisse durchsucht,
- bis eine entsprechende Datei ( <classname>.class) gefunden wird.
-
-******************************************************************************/
-
-bool suck_start (unicode *classname)
-{
-#define MAXFILENAME 1000 /* Maximale Langes des Dateinamens plus Pfad */
-
- char filename[MAXFILENAME+10]; /* Platz fuer '.class' */
- u2 filenamelen;
- char *pathpos;
- u2 i,c;
-
-
- pathpos = classpath;
-
- while (*pathpos) {
- while ( *pathpos == ':' ) pathpos++;
-
- filenamelen=0;
- while ( (*pathpos) && (*pathpos!=':') ) {
- PANICIF (filenamelen >= MAXFILENAME, "Filename too long") ;
-
- filename[filenamelen++] = *(pathpos++);
- }
-
- filename[filenamelen++] = '/';
-
- for (i=0; i < classname -> length; i++) {
- PANICIF (filenamelen >= MAXFILENAME, "Filename too long");
-
- c = classname -> text [i];
- if (c=='/') c = '/'; /* Slashes im Namen passen zu UNIX */
- else {
- if ( c<=' ' || c>'z') {
- c = '?';
- }
- }
-
- filename[filenamelen++] = c;
- }
-
- strcpy (filename+filenamelen, ".class");
-
- classfile = fopen(filename, "r");
- if (classfile) {
- return true;
- }
+ *********************** hashtable functions **********************************
+ ******************************************************************************/
-
- }
-
- sprintf (logtext,"Can not open class file '%s'", filename);
- error();
- return false;
-}
+/* hashsize must be power of 2 */
+#define UTF_HASHSTART 16384 /* initial size of utf-hash */
+#define HASHSTART 2048 /* initial size of javastring and class-hash */
-/************************** Funktion: suck_stop *******************************
- Schlie"st die offene Datei wieder.
-
-******************************************************************************/
+/******************** function: init_hashtable ******************************
-void suck_stop ()
-{
- u4 rest=0;
- u1 dummy;
+ Initializes a hashtable structure and allocates memory.
+ The parameter size specifies the initial size of the hashtable.
- while ( fread (&dummy, 1,1, classfile) > 0) rest++;
- if (rest) {
- sprintf (logtext,"There are %d access bytes at end of classfile",
- (int) rest);
- dolog();
- }
-
- fclose (classfile);
- classfile = NULL;
-}
-
-
-
-/************************** Lesefunktionen ***********************************
-
- Lesen von der Datei in verschieden grossen Paketen
- (8,16,32,64-bit Integer oder Float)
-
*****************************************************************************/
-void suck_nbytes (u1 *buffer, u4 len)
-{
- if ( fread (buffer, 1, len, classfile) != len) panic ("Unexpected EOF");
-}
-
-
-void skip_nbytes (u4 len)
+void init_hashtable(hashtable *hash, u4 size)
{
u4 i;
- for (i=0; i<len; i++) suck_u1 ();
-}
-
-
-u1 suck_u1 ()
-{
- u1 b;
- if ( fread (&b, 1,1, classfile) != 1) panic ("Unexpected EOF");
- return b;
-}
-
-s1 suck_s1 ()
-{
- s1 b;
- if ( fread (&b, 1,1, classfile) != 1) panic ("Unexpected EOF");
- return b;
-}
-
-
-u2 suck_u2 ()
-{
- u1 b[2];
- if ( fread (b, 1,2, classfile) != 2) panic ("Unexpected EOF");
- return (b[0]<<8) + b[1];
-}
-
-s2 suck_s2 ()
-{
- return suck_u2 ();
-}
-
-
-u4 suck_u4 ()
-{
- u1 b[4];
- u4 v;
- if ( fread (b, 1,4, classfile) != 4) panic ("Unexpected EOF");
- v = ( ((u4)b[0]) <<24) + ( ((u4)b[1])<<16) + ( ((u4)b[2])<<8) + ((u4)b[3]);
- return v;
-}
-
-s4 suck_s4 ()
-{
- s4 v = suck_u4 ();
- return v;
-}
-
-u8 suck_u8 ()
-{
-#if U8_AVAILABLE
- u8 lo,hi;
- hi = suck_u4();
- lo = suck_u4();
- return (hi<<32) + lo;
-#else
- u8 v;
- v.high = suck_u4();
- v.low = suck_u4();
- return v;
-#endif
-}
-
-s8 suck_s8 ()
-{
- return suck_u8 ();
-}
-
-
-float suck_float ()
-{
- float f;
-
-#if !WORDS_BIGENDIAN
- u1 buffer[4];
- u2 i;
- for (i=0; i<4; i++) buffer[3-i] = suck_u1 ();
- memcpy ( (u1*) (&f), buffer, 4);
-#else
- suck_nbytes ( (u1*) (&f), 4 );
-#endif
-
- PANICIF (sizeof(float) != 4, "Incompatible float-format");
-
- return f;
-}
-
-double suck_double ()
-{
- double d;
-
-#if !WORDS_BIGENDIAN
- u1 buffer[8];
- u2 i;
- for (i=0; i<8; i++) buffer[7-i] = suck_u1 ();
- memcpy ( (u1*) (&d), buffer, 8);
-#else
- suck_nbytes ( (u1*) (&d), 8 );
-#endif
+ hash->entries = 0;
+ hash->size = size;
+ hash->ptr = MNEW (void*, size);
- PANICIF (sizeof(double) != 8, "Incompatible double-format" );
-
- return d;
+ /* clear table */
+ for (i=0; i<size; i++) hash->ptr[i] = NULL;
}
+/*********************** function: tables_init *****************************
-
-
-/******************************************************************************
-******************** Der Unicode-Symbol-Verwalter *****************************
-*******************************************************************************
-
- legt eine Hashtabelle f"ur unicode-Symbole an und verwaltet
- das Eintragen neuer Symbole
-
-******************************************************************************/
-
-
-
-#define UNICODESTART 2187 /* Startgr"osse: moeglichst gross und prim */
-
-static u4 unicodeentries; /* Anzahl der Eintr"age in der Tabelle */
-static u4 unicodehashsize; /* Gr"osse der Tabelle */
-static unicode ** unicodehash; /* Zeiger auf die Tabelle selbst */
-
-
-/*********************** Funktion: unicode_init ******************************
-
- Initialisiert die unicode-Symboltabelle (muss zu Systemstart einmal
- aufgerufen werden)
+ creates hashtables for symboltables
+ (called once at startup)
*****************************************************************************/
-void unicode_init ()
+void tables_init ()
{
- u4 i;
+ init_hashtable(&utf_hash, UTF_HASHSTART); /* hashtable for utf8-symbols */
+ init_hashtable(&string_hash, HASHSTART); /* hashtable for javastrings */
+ init_hashtable(&class_hash, HASHSTART); /* hashtable for classes */
#ifdef STATISTICS
- count_unicode_len += sizeof(unicode*) * unicodehashsize;
+ count_utf_len += sizeof(utf*) * utf_hash.size;
#endif
- unicodeentries = 0;
- unicodehashsize = UNICODESTART;
- unicodehash = MNEW (unicode*, unicodehashsize);
- for (i=0; i<unicodehashsize; i++) unicodehash[i] = NULL;
}
+/********************** function: tables_close ******************************
-/*********************** Funktion: unicode_close *****************************
-
- Gibt allen Speicher der Symboltabellen frei.
- Parameter: Ein Zeiger auf eine Funktion, die dazu n"otig ist,
- Stringkonstanten (die mit 'unicode_setstringlink'
- Unicode-Symbole gebunden wurden) wieder freizugeben
+ free memory for hashtables
*****************************************************************************/
-void unicode_close (stringdeleter del)
+void tables_close (stringdeleter del)
{
- unicode *u;
+ utf *u;
+ literalstring *s;
u4 i;
- for (i=0; i<unicodehashsize; i++) {
- u = unicodehash[i];
+ /* dispose utf symbols */
+ for (i=0; i<utf_hash.size; i++) {
+ u = utf_hash.ptr[i];
while (u) {
- unicode *nextu = u->hashlink;
-
- if (u->string) del (u->string);
-
- MFREE (u->text, u2, u->length);
- FREE (u, unicode);
+ /* process elements in external hash chain */
+ utf *nextu = u->hashlink;
+ MFREE (u->text, u1, u->blength);
+ FREE (u, utf);
u = nextu;
}
}
- MFREE (unicodehash, unicode*, unicodehashsize);
+
+ /* dispose javastrings */
+ for (i=0; i<string_hash.size; i++) {
+ s = string_hash.ptr[i];
+ while (u) {
+ /* process elements in external hash chain */
+ literalstring *nexts = s->hashlink;
+ del(s->string);
+ FREE(s, literalstring);
+ s = nexts;
+ }
+ }
+
+ /* dispose hashtable structures */
+ MFREE (utf_hash.ptr, void*, utf_hash.size);
+ MFREE (string_hash.ptr, void*, string_hash.size);
+ MFREE (class_hash.ptr, void*, class_hash.size);
}
+/********************* function: utf_display *********************************
-/********************* Funktion: unicode_display ******************************
-
- Gibt ein unicode-Symbol auf stdout aus (zu Debugzwecken)
+ write utf symbol to stdout (debugging purposes)
******************************************************************************/
-void unicode_display (unicode *u)
+void utf_display (utf *u)
{
- u2 i,c;
- for (i=0; i < u->length; i++) {
- c = u->text[i];
+ char *endpos = utf_end(u); /* points behind utf string */
+ char *utf_ptr = u->text; /* current position in utf text */
+
+ while (utf_ptr<endpos) {
+
+ /* read next unicode character */
+ u2 c = utf_nextu2(&utf_ptr);
if (c>=32 && c<=127) printf ("%c",c);
else printf ("?");
- }
+ }
+
fflush (stdout);
}
-
-/********************* Funktion: unicode_sprint ******************************
+/************************ function: utf_sprint *******************************
- Schreibt ein unicode-Symbol in einen C-String
+ write utf symbol into c-string (debugging purposes)
******************************************************************************/
-void unicode_sprint (char *buffer, unicode *u)
+void utf_sprint (char *buffer, utf *u)
{
- u2 i;
- for (i=0; i < u->length; i++) buffer[i] = u->text[i];
- buffer[i] = '\0';
+ char *endpos = utf_end(u); /* points behind utf string */
+ char *utf_ptr = u->text; /* current position in utf text */
+ u2 pos = 0; /* position in c-string */
+
+ while (utf_ptr<endpos)
+ /* copy next unicode character */
+ buffer[pos++] = utf_nextu2(&utf_ptr);
+
+ /* terminate string */
+ buffer[pos] = '\0';
}
-/********************* Funktion: unicode_fprint ******************************
+/********************* Funktion: utf_fprint **********************************
- Schreibt ein unicode-Symbol auf eine Datei aus
+ write utf symbol into file
******************************************************************************/
-void unicode_fprint (FILE *file, unicode *u)
+void utf_fprint (FILE *file, utf *u)
{
- u2 i;
- for (i=0; i < u->length; i++) putc (u->text[i], file);
+ char *endpos = utf_end(u); /* points behind utf string */
+ char *utf_ptr = u->text; /* current position in utf text */
+
+ while (utf_ptr<endpos)
+ /* write next unicode character */
+ putc ( utf_nextu2(&utf_ptr), file );
}
-/****************** interne Funktion: u_hashkey ******************************/
+/****************** internal function: utf_hashkey ***************************
-static u4 u_hashkey (u2 *text, u2 length)
-{
- u4 k = 0;
- u2 i,sh=0;
-
- for (i=0; i<length; i++) {
- k ^= ( ((u4) (text[i])) << sh );
- if (sh<16) sh++;
- else sh=0;
- }
-
- return k;
-}
+ The hashkey is computed from the utf-text by using up to 8 characters.
+ For utf-symbols longer than 15 characters 3 characters are taken from
+ the beginning and the end, 2 characters are taken from the middle.
-/*************** interne Funktion: u_reorganizehash **************************/
+******************************************************************************/
-static void u_reorganizehash ()
-{
- u4 i;
- unicode *u;
+#define nbs(val) ((u4) *(++text) << val) /* get next byte, left shift by val */
+#define fbs(val) ((u4) *( text) << val) /* get first byte, left shift by val */
+
+static u4 utf_hashkey (char *text, u4 length)
+{
+ char *start_pos = text; /* pointer to utf text */
+ u4 a;
+
+ switch (length) {
+
+ case 0: /* empty string */
+ return 0;
+
+ case 1: return fbs(0);
+ case 2: return fbs(0) ^ nbs(3);
+ case 3: return fbs(0) ^ nbs(3) ^ nbs(5);
+ case 4: return fbs(0) ^ nbs(2) ^ nbs(4) ^ nbs(6);
+ case 5: return fbs(0) ^ nbs(2) ^ nbs(3) ^ nbs(4) ^ nbs(6);
+ case 6: return fbs(0) ^ nbs(1) ^ nbs(2) ^ nbs(3) ^ nbs(5) ^ nbs(6);
+ case 7: return fbs(0) ^ nbs(1) ^ nbs(2) ^ nbs(3) ^ nbs(4) ^ nbs(5) ^ nbs(6);
+ case 8: return fbs(0) ^ nbs(1) ^ nbs(2) ^ nbs(3) ^ nbs(4) ^ nbs(5) ^ nbs(6) ^ nbs(7);
+
+ case 9: a = fbs(0) ^ nbs(1) ^ nbs(2);
+ text++;
+ return a ^ nbs(4) ^ nbs(5) ^ nbs(6) ^ nbs(7) ^ nbs(8);
+
+ case 10: a = fbs(0);
+ text++;
+ a^= nbs(2) ^ nbs(3) ^ nbs(4);
+ text++;
+ return a ^ nbs(6) ^ nbs(7) ^ nbs(8) ^ nbs(9);
+
+ case 11: a = fbs(0);
+ text++;
+ a^= nbs(2) ^ nbs(3) ^ nbs(4);
+ text++;
+ return a ^ nbs(6) ^ nbs(7) ^ nbs(8) ^ nbs(9) ^ nbs(10);
+
+ case 12: a = fbs(0);
+ text+=2;
+ a^= nbs(2) ^ nbs(3);
+ text+=1;
+ a^= nbs(5) ^ nbs(6) ^ nbs(7);
+ text+=1;
+ return a ^ nbs(9) ^ nbs(10);
+
+ case 13: a = fbs(0) ^ nbs(1);
+ text+=1;
+ a^= nbs(3) ^ nbs(4);
+ text+=2;
+ a^= nbs(7) ^ nbs(8);
+ text+=2;
+ return a ^ nbs(9) ^ nbs(10);
+
+ case 14: a = fbs(0);
+ text+=2;
+ a^= nbs(3) ^ nbs(4);
+ text+=2;
+ a^= nbs(7) ^ nbs(8);
+ text+=2;
+ return a ^ nbs(9) ^ nbs(10) ^ nbs(11);
+
+ case 15: a = fbs(0);
+ text+=2;
+ a^= nbs(3) ^ nbs(4);
+ text+=2;
+ a^= nbs(7) ^ nbs(8);
+ text+=2;
+ return a ^ nbs(9) ^ nbs(10) ^ nbs(11);
+
+ default: /* 3 characters from beginning */
+ a = fbs(0);
+ text+=2;
+ a^= nbs(3) ^ nbs(4);
+
+ /* 2 characters from middle */
+ text = start_pos + (length / 2);
+ a^= fbs(5);
+ text+=2;
+ a^= nbs(6);
+
+ /* 3 characters from end */
+ text = start_pos + length - 4;
+
+ a^= fbs(7);
+ text+=1;
+
+ return a ^ nbs(10) ^ nbs(11);
+ }
+}
- u4 newhashsize = unicodehashsize*2;
- unicode **newhash = MNEW (unicode*, newhashsize);
-#ifdef STATISTICS
- count_unicode_len += sizeof(unicode*) * unicodehashsize;
-#endif
+/*************************** function: utf_hashkey ***************************
- for (i=0; i<newhashsize; i++) newhash[i] = NULL;
+ compute the hashkey of a unicode string
- for (i=0; i<unicodehashsize; i++) {
- u = unicodehash[i];
- while (u) {
- unicode *nextu = u -> hashlink;
- u4 slot = (u->key) % newhashsize;
-
- u->hashlink = newhash[slot];
- newhash[slot] = u;
+******************************************************************************/
- u = nextu;
- }
- }
-
- MFREE (unicodehash, unicode*, unicodehashsize);
- unicodehash = newhash;
- unicodehashsize = newhashsize;
+u4 unicode_hashkey (u2 *text, u2 len)
+{
+ return utf_hashkey((char*) text, len);
}
+/************************ function: utf_new **********************************
-/****************** Funktion: unicode_new_u2 **********************************
+ Creates a new utf-symbol, the text of the symbol is passed as a
+ u1-array. The function searches the utf-hashtable for a utf-symbol
+ with this text. On success the element returned, otherwise a new
+ hashtable element is created.
- Legt ein neues unicode-Symbol an. Der Text des Symbols wird dieser
- Funktion als u2-Array "ubergeben
+ If the number of entries in the hashtable exceeds twice the size of the
+ hashtable slots a reorganization of the hashtable is done and the utf
+ symbols are copied to a new hashtable with doubled size.
******************************************************************************/
-unicode *unicode_new_u2 (u2 *text, u2 length)
+utf *utf_new (char *text, u2 length)
{
- u4 key = u_hashkey (text, length);
- u4 slot = key % unicodehashsize;
- unicode *u = unicodehash[slot];
+ u4 key; /* hashkey computed from utf-text */
+ u4 slot; /* slot in hashtable */
+ utf *u; /* hashtable element */
u2 i;
-
- while (u) {
- if (u->key == key) {
- if (u->length == length) {
- for (i=0; i<length; i++) {
- if (text[i] != u->text[i]) goto nomatch;
- }
- return u;
- }
- }
- nomatch:
- u = u->hashlink;
- }
-
+
#ifdef STATISTICS
- count_unicode_len += sizeof(unicode) + 2 * length;
+ count_utf_new++;
#endif
- u = NEW (unicode);
- u->key = key;
- u->length = length;
- u->text = MNEW (u2, length);
- u->class = NULL;
- u->string = NULL;
- u->hashlink = unicodehash[slot];
- unicodehash[slot] = u;
- for (i=0; i<length; i++) u->text[i] = text[i];
-
- unicodeentries++;
-
- if ( unicodeentries > (unicodehashsize/2)) u_reorganizehash();
-
- return u;
-}
-
-
-/********************* Funktion: unicode_new_char *****************************
+ key = utf_hashkey (text, length);
+ slot = key & (utf_hash.size-1);
+ u = utf_hash.ptr[slot];
- Legt ein neues unicode-Symbol an. Der Text des Symbols wird dieser
- Funktion als C-String ( = char* ) "ubergeben
-
-******************************************************************************/
+ /* search external hash chain for utf-symbol */
+ while (u) {
+ if (u->blength == length) {
-unicode *unicode_new_char (char *text)
-{
-#define MAXNEWCHAR 500
- u2 buffer[MAXNEWCHAR];
- u2 length = 0;
- u1 c;
-
- while ( (c = *text) != '\0' ) {
- if (length>=MAXNEWCHAR) panic ("Text too long in unicode_new_char");
- buffer[length++] = c;
- text ++;
+ /* compare text of hashtable elements */
+ for (i=0; i<length; i++)
+ if (text[i] != u->text[i]) goto nomatch;
+
+#ifdef STATISTICS
+ count_utf_new_found++;
+#endif
+ /* symbol found in hashtable */
+ return u;
}
- return unicode_new_u2 (buffer, length);
-}
-
-
-/********************** Funktion: unicode_setclasslink ************************
-
- H"angt einen Verweis auf eine Klasse an ein unicode-Symbol an.
+ nomatch:
+ u = u->hashlink; /* next element in external chain */
+ }
-******************************************************************************/
+#ifdef STATISTICS
+ count_utf_len += sizeof(utf) + length;
+#endif
-void unicode_setclasslink (unicode *u, classinfo *class)
-{
- PANICIF (u->class, "Attempt to attach class to already attached symbol");
- u->class = class;
-}
+ /* location in hashtable found, create new utf element */
+ u = NEW (utf);
+ u->blength = length; /* length in bytes of utfstring */
+ u->hashlink = utf_hash.ptr[slot]; /* link in external hashchain */
+ u->text = mem_alloc(length); /* allocate memory for utf-text */
+ memcpy(u->text,text,length); /* copy utf-text */
+ utf_hash.ptr[slot] = u; /* insert symbol into table */
-/********************** Funktion: unicode_getclasslink ************************
+ utf_hash.entries++; /* update number of entries */
- Sucht den Verweis von einem unicode-Symbol auf eine Klasse.
- Wenn keine solche Klasse existiert, dann wird ein Fehler
- ausgegeben.
+ if ( utf_hash.entries > (utf_hash.size*2)) {
-******************************************************************************/
+ /* reorganization of hashtable, average length of
+ the external chains is approx. 2 */
-classinfo *unicode_getclasslink (unicode *u)
-{
- PANICIF (!u->class, "Attempt to get unknown class-reference");
- return u->class;
-}
+ u4 i;
+ utf *u;
+ hashtable newhash; /* the new hashtable */
+ /* create new hashtable, double the size */
+ init_hashtable(&newhash, utf_hash.size*2);
+ newhash.entries=utf_hash.entries;
+#ifdef STATISTICS
+ count_utf_len += sizeof(utf*) * utf_hash.size;
+#endif
-/********************* Funktion: unicode_unlinkclass *************************
+ /* transfer elements to new hashtable */
+ for (i=0; i<utf_hash.size; i++) {
+ u = (utf*) utf_hash.ptr[i];
+ while (u) {
+ utf *nextu = u -> hashlink;
+ u4 slot = (utf_hashkey(u->text,u->blength)) & (newhash.size-1);
+
+ u->hashlink = (utf*) newhash.ptr[slot];
+ newhash.ptr[slot] = u;
- Entfernt den Verweis auf eine Klasse wieder von einem Symbol
+ /* follow link in external hash chain */
+ u = nextu;
+ }
+ }
-******************************************************************************/
-
-void unicode_unlinkclass (unicode *u)
-{
- PANICIF (!u->class, "Attempt to unlink not yet linked symbol");
- u -> class = NULL;
-}
-
-
-
-/******************* Funktion> unicode_setstringlink *********************
-
- H"angt einen Verweis auf einen konstanten String an ein
- Unicode-Symbol
+ /* dispose old table */
+ MFREE (utf_hash.ptr, void*, utf_hash.size);
+ utf_hash = newhash;
+ }
-*************************************************************************/
-
-void unicode_setstringlink (unicode *u, java_objectheader *str)
-{
- PANICIF (u->string, "Attempt to attach string to already attached symbol");
- u->string = str;
+ return u;
}
-/********************* Funktion: unicode_unlinkstring *************************
+/********************* function: utf_new_char ********************************
+
+ creates a new utf symbol, the text for this symbol is passed
+ as a c-string ( = char* )
- Entfernt den Verweis auf einen String wieder von einem Symbol
-
******************************************************************************/
-void unicode_unlinkstring (unicode *u)
+utf *utf_new_char (char *text)
{
- PANICIF (!u->class, "Attempt to unlink not yet linked symbol");
- u -> string = NULL;
+ return utf_new(text, strlen(text));
}
+/************************** Funktion: utf_show ******************************
+ writes the utf symbols in the utfhash to stdout and
+ displays the number of external hash chains grouped
+ according to the chainlength
+ (debugging purposes)
-/*********************** Funktion: unicode_show ******************************
-
- gibt eine Aufstellung aller Symbol im unicode-hash auf stdout aus.
- (nur f"ur Debug-Zwecke)
-
*****************************************************************************/
-void unicode_show ()
+void utf_show ()
{
- unicode *u;
+
+#define CHAIN_LIMIT 20 /* limit for seperated enumeration */
+
+ u4 chain_count[CHAIN_LIMIT]; /* numbers of chains */
+ u4 max_chainlength = 0; /* maximum length of the chains */
+ u4 sum_chainlength = 0; /* sum of the chainlengths */
+ u4 beyond_limit = 0; /* number of utf-symbols in chains with length>=CHAIN_LIMIT-1 */
u4 i;
- printf ("UNICODE-HASH: %d slots for %d entries\n",
- (int) unicodehashsize, (int) unicodeentries );
-
- for (i=0; i<unicodehashsize; i++) {
- u = unicodehash[i];
+ printf ("UTF-HASH:\n");
+
+ /* show element of utf-hashtable */
+ for (i=0; i<utf_hash.size; i++) {
+ utf *u = utf_hash.ptr[i];
if (u) {
printf ("SLOT %d: ", (int) i);
while (u) {
printf ("'");
- unicode_display (u);
+ utf_display (u);
printf ("' ");
- if (u->string) printf ("(string) ");
u = u->hashlink;
}
printf ("\n");
}
}
-}
+ printf ("UTF-HASH: %d slots for %d entries\n",
+ (int) utf_hash.size, (int) utf_hash.entries );
+
+
+ if (utf_hash.entries == 0)
+ return;
+
+ printf("chains:\n chainlength number of chains %% of utfstrings\n");
+
+ for (i=0;i<CHAIN_LIMIT;i++)
+ chain_count[i]=0;
+
+ /* count numbers of hashchains according to their length */
+ for (i=0; i<utf_hash.size; i++) {
+
+ utf *u = (utf*) utf_hash.ptr[i];
+ u4 chain_length = 0;
+
+ /* determine chainlength */
+ while (u) {
+ u = u->hashlink;
+ chain_length++;
+ }
+
+ /* update sum of all chainlengths */
+ sum_chainlength+=chain_length;
+
+ /* determine the maximum length of the chains */
+ if (chain_length>max_chainlength)
+ max_chainlength = chain_length;
+
+ /* update number of utf-symbols in chains with length>=CHAIN_LIMIT-1 */
+ if (chain_length>=CHAIN_LIMIT) {
+ beyond_limit+=chain_length;
+ chain_length=CHAIN_LIMIT-1;
+ }
+
+ /* update number of hashchains of current length */
+ chain_count[chain_length]++;
+ }
+
+ /* display results */
+ for (i=1;i<CHAIN_LIMIT-1;i++)
+ printf(" %2d %17d %18.2f%%\n",i,chain_count[i],(((float) chain_count[i]*i*100)/utf_hash.entries));
+
+ printf(" >=%2d %17d %18.2f%%\n",CHAIN_LIMIT-1,chain_count[CHAIN_LIMIT-1],((float) beyond_limit*100)/utf_hash.entries);
+ printf("max. chainlength:%5d\n",max_chainlength);
+
+ /* avg. chainlength = sum of chainlengths / number of chains */
+ printf("avg. chainlength:%5.2f\n",(float) sum_chainlength / (utf_hash.size-chain_count[0]));
+}
+
/******************************************************************************
-*********************** Diverse Support-Funktionen ****************************
+*********************** Misc support functions ********************************
******************************************************************************/
-/******************** Funktion: desc_to_type **********************************
-
- Findet zu einem gegebenen Typdescriptor den entsprechenden
- Java-Grunddatentyp.
+/******************** Function: desc_to_type **********************************
+
+ Determines the corresponding Java base data type for a given type
+ descriptor.
******************************************************************************/
-u2 desc_to_type (unicode *descriptor)
+u2 desc_to_type (utf *descriptor)
{
- if (descriptor->length < 1) panic ("Type-Descriptor is empty string");
+ char *utf_ptr = descriptor->text; /* current position in utf text */
+
+ if (descriptor->blength < 1) panic ("Type-Descriptor is empty string");
- switch (descriptor->text[0]) {
+ switch (*utf_ptr++) {
case 'B':
case 'C':
case 'I':
}
sprintf (logtext, "Invalid Type-Descriptor: ");
- unicode_sprint (logtext+strlen(logtext), descriptor);
+ utf_sprint (logtext+strlen(logtext), descriptor);
error ();
return 0;
}
-/********************** Funktion: desc_typesize *******************************
+/********************** Function: desc_typesize *******************************
- Berechnet die L"ange (in Byte) eines Datenelements gegebenen Typs,
- der durch den Typdescriptor gegeben ist.
+ Calculates the lenght in bytes needed for a data element of the type given
+ by its type descriptor.
******************************************************************************/
-u2 desc_typesize (unicode *descriptor)
+u2 desc_typesize (utf *descriptor)
{
switch (desc_to_type(descriptor)) {
case TYPE_INT: return 4;
}
+/********************** function: utf_nextu2 *********************************
+
+ read the next unicode character from the utf string and
+ increment the utf-string pointer accordingly
+
+******************************************************************************/
+
+u2 utf_nextu2(char **utf_ptr)
+{
+ /* uncompressed unicode character */
+ u2 unicode_char;
+ /* current position in utf text */
+ unsigned char *utf = (unsigned char *) (*utf_ptr);
+ /* bytes representing the unicode character */
+ unsigned char ch1, ch2, ch3;
+ /* number of bytes used to represent the unicode character */
+ int len;
+
+ switch ((ch1 = utf[0]) >> 4) {
+ default: /* 1 byte */
+ (*utf_ptr)++;
+ return ch1;
+ case 0xC:
+ case 0xD: /* 2 bytes */
+ if (((ch2 = utf[1]) & 0xC0) == 0x80) {
+ unsigned char high = ch1 & 0x1F;
+ unsigned char low = ch2 & 0x3F;
+ unicode_char = (high << 6) + low;
+ len = 2;
+ }
+ break;
+
+ case 0xE: /* 2 or 3 bytes */
+ if (((ch2 = utf[1]) & 0xC0) == 0x80) {
+ if (((ch3 = utf[2]) & 0xC0) == 0x80) {
+ unsigned char low = ch3 & 0x3f;
+ unsigned char mid = ch2 & 0x3f;
+ unsigned char high = ch1 & 0x0f;
+ unicode_char = (((high << 6) + mid) << 6) + low;
+ len = 3;
+ } else
+ len = 2;
+ }
+ break;
+ }
+ /* update position in utf-text */
+ *utf_ptr = (char *) (utf + len);
+ return unicode_char;
+}
+
+/******************** Function: class_new **************************************
+ searches for the class with the specified name in the classes hashtable,
+ if there is no such class a new classinfo structure is created and inserted
+ into the list of classes to be loaded
-/******************************************************************************
-********************* Der garbage-collected Heap ******************************
-*******************************************************************************
-
- verwaltet einen Heap mit automatischer Speicherfreigabe.
-
- (eine ausf"uhrliche Dokumentation findet sich in der Datei:
- collect.doc)
-
-******************************************************************************/
+*******************************************************************************/
+classinfo *class_new (utf *u)
+{
+ classinfo *c; /* hashtable element */
+ u4 key; /* hashkey computed from classname */
+ u4 slot; /* slot in hashtable */
+ u2 i;
-bool collectverbose = false; /* soll Meldung beim GC ausgegeben werden? */
+ key = utf_hashkey (u->text, u->blength);
+ slot = key & (class_hash.size-1);
+ c = class_hash.ptr[slot];
+ /* search external hash chain for the class */
+ while (c) {
+ if (c->name->blength == u->blength) {
+ for (i=0; i<u->blength; i++)
+ if (u->text[i] != c->name->text[i]) goto nomatch;
+
+ /* class found in hashtable */
+ return c;
+ }
+
+ nomatch:
+ c = c->hashlink; /* next element in external chain */
+ }
-#define BLOCKSIZE 8 /* Gr"osse eines Speicherblockes */
-typedef u8 heapblock; /* Datentyp mit der Gr"osse eines Speicherblocks */
+ /* location in hashtable found, create new classinfo structure */
-#if U8_AVAILABLE && SUPPORT_LONG
-#define bitfieldtype u8
-#define BITFIELDBITS 64
-#else
-#define bitfieldtype u4
-#define BITFIELDBITS 32
+#ifdef STATISTICS
+ count_class_infos += sizeof(classinfo);
#endif
-u4 heapsize; /* Gr"osse des Heap in Blocks */
-u4 topofheap; /* Bisherige Obergrenze Heaps */
-heapblock *heap; /* Speicher f"ur den Heap selbst */
-
-bitfieldtype *startbits; /* Bitfeld f"ur Bereichsstartkennung */
-bitfieldtype *markbits; /* Bitfeld f"ur Markierung */
-bitfieldtype *referencebits; /* Bitfeld f"ur Folgereferenzenkennung */
-
-u4 heapfillgrade; /* Menge der Daten im Heap */
-u4 collectthreashold; /* Schwellwert f"ur n"achstes GC */
-
-void **bottom_of_stack; /* Zeiger auf Untergrenze des C-Stacks */
-chain *allglobalreferences; /* Liste f"ur alle globalen Zeiger */
+ c = NEW (classinfo);
+ c -> flags = 0;
+ c -> name = u;
+ c -> cpcount = 0;
+ c -> cptags = NULL;
+ c -> cpinfos = NULL;
+ c -> super = NULL;
+ c -> sub = NULL;
+ c -> nextsub = NULL;
+ c -> interfacescount = 0;
+ c -> interfaces = NULL;
+ c -> fieldscount = 0;
+ c -> fields = NULL;
+ c -> methodscount = 0;
+ c -> methods = NULL;
+ c -> linked = false;
+ c -> index = 0;
+ c -> instancesize = 0;
+ c -> header.vftbl = NULL;
+ c -> innerclasscount = 0;
+ c -> innerclass = NULL;
+ c -> vftbl = NULL;
+ c -> initialized = false;
+ c -> classvftbl = false;
+
+ /* prepare loading of the class */
+ list_addlast (&unloadedclasses, c);
+
+ /* insert class into the hashtable */
+ c->hashlink = class_hash.ptr[slot];
+ class_hash.ptr[slot] = c;
+
+ /* update number of hashtable-entries */
+ class_hash.entries++;
+
+ if ( class_hash.entries > (class_hash.size*2)) {
+
+ /* reorganization of hashtable, average length of
+ the external chains is approx. 2 */
+
+ u4 i;
+ classinfo *c;
+ hashtable newhash; /* the new hashtable */
+
+ /* create new hashtable, double the size */
+ init_hashtable(&newhash, class_hash.size*2);
+ newhash.entries = class_hash.entries;
+
+ /* transfer elements to new hashtable */
+ for (i=0; i<class_hash.size; i++) {
+ c = (classinfo*) class_hash.ptr[i];
+ while (c) {
+ classinfo *nextc = c -> hashlink;
+ u4 slot = (utf_hashkey(c->name->text,c->name->blength)) & (newhash.size-1);
+
+ c->hashlink = newhash.ptr[slot];
+ newhash.ptr[slot] = c;
-typedef struct finalizernode {
- struct finalizernode *next;
- u4 objstart;
- methodinfo *finalizer;
- } finalizernode;
+ c = nextc;
+ }
+ }
-finalizernode *livefinalizees;
-finalizernode *deadfinalizees;
+ /* dispose old table */
+ MFREE (class_hash.ptr, void*, class_hash.size);
+ class_hash = newhash;
+ }
+
+ return c;
+}
+/******************** Function: class_get **************************************
-typedef struct memarea { /* Datenstruktur f"ur einen Freispeicherbereich */
- struct memarea *next;
- } memarea;
+ searches for the class with the specified name in the classes hashtable
+ if there is no such class NULL is returned
-typedef struct bigmemarea { /* Datenstruktur f"ur einen */
- struct bigmemarea *next; /* Freispeicherbereich variabler L"ange */
- u4 size;
- } bigmemarea;
-
-#define DIFFERENTSIZES 128 /* Anzahl der 'kleinen' Freispeicherlisten */
-memarea *memlist[DIFFERENTSIZES]; /* Die 'kleinen' Freispeicherlisten */
-bitfieldtype memlistbits[DIFFERENTSIZES/BITFIELDBITS];
- /* Bitfeld, in dem jeweils ein Bit gesetzt */
- /* ist, wenn eine Liste noch etwas enth"alt */
-
-bigmemarea *bigmemlist; /* Liste der gr"osseren Freispeicherbereiche */
-
-
-
-
-/**************** Hilfsfunktion: lowest **************************************
-
-liefert als Ergebnis die Nummer des niederwertigsten Bits einer
-Zahl vom Typ bitfieldtype, das 1 ist.
-Wenn die ganze Zahl keine 1en enth"alt, dann ist egal, was f"ur einen
-Wert die Funktion l"iefert.
-z.B.: lowest(1) = 0, lowest(12) = 2, lowest(1024) = 10
-
-*****************************************************************************/
-
-static u1 lowesttable[256] = {
- 255, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
- 4, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
- 5, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
- 4, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
- 6, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
- 4, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
- 5, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
- 4, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
- 7, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
- 4, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
- 5, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
- 4, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
- 6, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
- 4, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
- 5, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
- 4, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0 };
-
-static int lowest(bitfieldtype i)
-{
-#if BITFIELDBITS==64
- u8 i1 = i<<32;
- if (i1) {
- u8 i11 = i1<<16;
- if (i11) {
- u8 i111 = i11<<8;
- if (i111) return lowesttable[i111>>56];
- else return 8+lowesttable[i11>>56];
- }
- else {
- u8 i112 = i1<<8;
- if (i112) return 16+lowesttable[i112>>56];
- else return 24+lowesttable[i1>>56];
- }
- }
- else {
- u8 i12 = i<<16;
- if (i12) {
- u8 i121 = i12<<8;
- if (i121) return 32+lowesttable[i121>>56];
- else return 40+lowesttable[i12>>56];
- }
- else {
- u8 i122 = i<<8;
- if (i122) return 48+lowesttable[i122>>56];
- else return 56+lowesttable[i>>56];
- }
- }
-#else
- u4 i1 = i<<16;
- if (i1) {
- u4 i11 = i1<<8;
- if (i11) return lowesttable[i11>>24];
- else return 8+lowesttable[i1>>24];
- }
- else {
- u4 i12 = i<<8;
- if (i12) return 16+lowesttable[i12>>24];
- else return 24+lowesttable[i>>24];
- }
-#endif
-}
-
-
-/******** Funktionen zum Setzen und L"oschen von Bits in Bitfeldern ***********/
-
-static void setbit(bitfieldtype *bitfield, u4 bitnumber)
-{
- bitfield[bitnumber/BITFIELDBITS] |=
- ((bitfieldtype) 1) << (bitnumber%BITFIELDBITS);
-}
-
-static void clearbit(bitfieldtype *bitfield, u4 bitnumber)
-{
- bitfield[bitnumber/BITFIELDBITS] &=
- ~((bitfieldtype) 1) << (bitnumber%BITFIELDBITS);
-}
-
-static bool isbitset(bitfieldtype *bitfield, u4 bitnumber)
-{
- return ( bitfield[bitnumber/BITFIELDBITS] &
- ( ((bitfieldtype) 1) << (bitnumber%BITFIELDBITS) ) ) != 0;
-}
-
-static bool isbitclear(bitfieldtype *bitfield, u4 bitnumber)
-{
- return ( bitfield[bitnumber/BITFIELDBITS] &
- ( ((bitfieldtype) 1) << (bitnumber%BITFIELDBITS) ) ) == 0;
-}
-
-
-/***************** Funktion: clearbitfield ************************************
-
- l"oscht ein ganzes Bitfeld
-
-******************************************************************************/
-
-static void clearbitfield(bitfieldtype *bitfield, u4 fieldsize)
-{
- u4 i,t;
- t = ALIGN(fieldsize, BITFIELDBITS) / BITFIELDBITS;
- for (i=0; i<t; i++) bitfield[i] = 0;
-}
-
-/************** Funktion: maskfieldwithfield **********************************
-
- Verkn"upft zwei Bitfelder bitweise mit UND, das erste Bitfeld
- wird mit dem Ergebnis "uberschrieben
-
-******************************************************************************/
-
-static void maskfieldwithfield (bitfieldtype* bitfield,
- bitfieldtype *maskfield, u4 fieldsize)
-{
- u4 i,t;
- t = ALIGN(fieldsize, BITFIELDBITS) / BITFIELDBITS;
- for (i=0; i<t; i++) bitfield[i] &= maskfield[i];
-}
-
-
-/************** Funktion: findnextsetbit **************************************
-
- Sucht in einem Bitfeld ab einer Stelle das n"achste gesetzte Bit
- und liefert die Nummer dieses Bits.
- Wenn kein Bit mehr zwischen 'bitnumber' und 'fieldsize' gesetzt
- ist, dann wird fieldsize zur"uckgeliefte.
-
-******************************************************************************/
-
-static u4 findnextsetbit(bitfieldtype* bitfield, u4 fieldsize, u4 bitnumber)
-{
- bitfieldtype pattern;
-
- for (;;) {
- if (bitnumber >= fieldsize) return fieldsize;
-
- pattern = bitfield[bitnumber/BITFIELDBITS];
- pattern >>= (bitnumber%BITFIELDBITS);
- if (pattern) return bitnumber + lowest(pattern);
-
- bitnumber = ((bitnumber + BITFIELDBITS) / BITFIELDBITS) * BITFIELDBITS;
- }
-}
-
-
-/************ Funktion: findnextcombination_set_unset *************************
-
- funktioniert wie findnextsetbit, allerdings sucht diese Funktion
- nach einer Stelle, an der gleichzeitig ein Bit im ersten
- Bitfeld gesetzt ist und im zweiten Bitfeld das entsprechende
- Bit nicht gesetzt ist.
-
-******************************************************************************/
-
-static u4 findnextcombination_set_unset
- (bitfieldtype *bitfield1, bitfieldtype* bitfield2, u4 fieldsize, u4 bitnumber)
-{
- bitfieldtype pattern;
-
- for (;;) {
- if (bitnumber >= fieldsize) return fieldsize;
-
- pattern = bitfield1[bitnumber/BITFIELDBITS]
- & (~bitfield2[bitnumber/BITFIELDBITS]);
- pattern >>= (bitnumber%BITFIELDBITS);
- if (pattern) return bitnumber + lowest(pattern);
-
- bitnumber = ((bitnumber + BITFIELDBITS) / BITFIELDBITS) * BITFIELDBITS;
- }
-}
-
-
-
-/************** Funktion: memlist_init ****************************************
-
- initialisiert die Freispeicherlisten (zum nachfolgenden Eintragen
- mit memlist_addrange).
-
-******************************************************************************/
-
-static void memlist_init ()
-{
- u4 i;
- for (i=0; i<DIFFERENTSIZES; i++) memlist[i] = NULL;
- clearbitfield (memlistbits, DIFFERENTSIZES);
- bigmemlist = NULL;
-}
-
-
-/************** Funktion: memlist_addrange ************************************
-
- f"ugt einen Bereich von Heap-Bl"ocken zur Freispeicherliste
- hinzu (in die freien Heap-Bl"ocke werden dabei verschiedene
- Verkettungszeiger hineingeschrieben).
-
-******************************************************************************/
+*******************************************************************************/
-static void memlist_addrange (u4 freestart, u4 freesize)
+classinfo *class_get (utf *u)
{
- if (freesize>=DIFFERENTSIZES) {
- bigmemarea *m = (bigmemarea*) (heap+freestart);
- m -> next = bigmemlist;
- m -> size = freesize;
- bigmemlist = m;
- }
- else {
- if (freesize*BLOCKSIZE>=sizeof(memarea)) {
- memarea *m = (memarea*) (heap+freestart);
- m -> next = memlist[freesize];
- memlist[freesize] = m;
- setbit (memlistbits, freesize);
- }
- }
-}
-
-
-/************** Funktion: memlist_getsuitable *********************************
-
- sucht in der Freispeicherliste einen Speicherbereich, der m"oglichst
- genau die gew"unschte L"ange hat.
- Der Bereich wird dabei auf jeden Fall aus der Liste ausgetragen.
- (Wenn der Bereich zu lang sein sollte, dann kann der Aufrufer den
- Rest wieder mit 'memlist_addrange' in die Liste einh"angen)
-
- Return (in Referenzparametern):
- *freestart: Anfang des freien Speichers
- *freelength: L"ange dieses Speicherbereiches
+ classinfo *c; /* hashtable element */
+ u4 key; /* hashkey computed from classname */
+ u4 slot; /* slot in hashtable */
+ u2 i;
- Wenn kein passender Speicherblock mehr gefunden werden kann, dann
- wird in '*freelength' 0 hineingeschrieben.
-
-******************************************************************************/
+ key = utf_hashkey (u->text, u->blength);
+ slot = key & (class_hash.size-1);
+ c = class_hash.ptr[slot];
-static void memlist_getsuitable (u4 *freestart, u4 *freelength, u4 length)
-{
- bigmemarea *m;
- bigmemarea *prevm = NULL;
-
- if (length<DIFFERENTSIZES) {
- u4 firstfreelength;
-
- if (memlist[length]) {
- firstfreelength = length;
- }
- else {
- firstfreelength = findnextsetbit
- (memlistbits, DIFFERENTSIZES, length+3);
- /* wenn kein passender Block da ist, dann gleich nach */
- /* einem etwas gr"osseren suchen, damit keine kleinen */
- /* St"uckchen "ubrigbleiben */
- }
+ /* search external hash-chain */
+ while (c) {
+ if (c->name->blength == u->blength) {
- if (firstfreelength<DIFFERENTSIZES) {
- memarea *m = memlist[firstfreelength];
- memlist[firstfreelength] = m->next;
- if (!m->next) clearbit (memlistbits, firstfreelength);
- *freestart = ((heapblock*) m) - heap;
- *freelength = firstfreelength;
- return;
- }
- }
+ /* compare classnames */
+ for (i=0; i<u->blength; i++)
+ if (u->text[i] != c->name->text[i]) goto nomatch;
- m = bigmemlist;
- while (m) {
- if (m->size >= length) {
- if (prevm) prevm->next = m->next;
- else bigmemlist = m->next;
-
- *freestart = ((heapblock*) m) - heap;
- *freelength = m->size;
- return ;
+ /* class found in hashtable */
+ return c;
}
-
- prevm = m;
- m = m->next;
- }
-
- *freelength=0;
-}
-
-
-
-
-
-/******************* Funktion: mark *******************************************
-
- Markiert ein m"oglicherweise g"ultiges Objekt.
- Sollte sich herausstellen, dass der Zeiger gar nicht auf ein Objekt
- am Heap zeigt, dann wird eben gar nichts markiert.
-
-******************************************************************************/
-
-static void markreferences (void **rstart, void **rend);
-
-static void mark (heapblock *obj)
-{
- u4 blocknum,objectend;
-
- if ((long) obj & (BLOCKSIZE-1)) return;
-
- if (obj<heap) return;
- if (obj>=(heap+topofheap) ) return;
-
- blocknum = obj-heap;
- if ( isbitclear(startbits, blocknum) ) return;
- if ( isbitset(markbits, blocknum) ) return;
-
- setbit (markbits, blocknum);
-
- if ( isbitclear(referencebits, blocknum) ) return;
-
- objectend = findnextsetbit (startbits, topofheap, blocknum+1);
- markreferences ((void**)obj, (void**) (heap+objectend) );
-}
-
-
-/******************** Funktion: markreferences ********************************
-
- Geht einen Speicherbereich durch, und markiert alle Objekte, auf
- die von diesem Bereich aus irgendeine Referenz existiert.
-
-******************************************************************************/
-
-static void markreferences (void **rstart, void **rend)
-{
- void **ptr;
-
- for (ptr=rstart; ptr<rend; ptr++) mark (*ptr);
-}
-
-
-/******************* Funktion: markstack **************************************
-
- Marks all objects that are referenced by the (C-)stacks of
- all live threads.
-
- (The stack-bottom is to be specified in the call to heap_init).
-
-******************************************************************************/
-
-static void markstack () /* schani */
-{
- void *dummy;
- void **top_of_stack = &dummy;
-
-#ifdef USE_THREADS
- thread *aThread;
-
- for (aThread = liveThreads; aThread != 0; aThread = CONTEXT(aThread).nextlive) {
- mark((heapblock*)aThread);
- if (aThread == currentThread) {
- if (top_of_stack > (void**)CONTEXT(aThread).stackEnd)
- markreferences ((void**)CONTEXT(aThread).stackEnd, top_of_stack);
- else
- markreferences (top_of_stack, (void**)CONTEXT(aThread).stackEnd);
- }
- else {
- if (CONTEXT(aThread).usedStackTop > CONTEXT(aThread).stackEnd)
- markreferences ((void**)CONTEXT(aThread).stackEnd,
- (void**)CONTEXT(aThread).usedStackTop + 16);
- else
- markreferences ((void**)CONTEXT(aThread).usedStackTop - 16,
- (void**)CONTEXT(aThread).stackEnd);
- }
- }
-
- markreferences((void**)&threadQhead[0], (void**)&threadQhead[MAX_THREAD_PRIO]);
-#else
- if (top_of_stack > bottom_of_stack)
- markreferences(bottom_of_stack, top_of_stack);
- else
- markreferences(top_of_stack, bottom_of_stack);
-#endif
-}
-
-
-
-/**************** Funktion: searchlivefinalizees *****************************
-
- geht die Liste aller Objekte durch, die noch finalisiert werden m"ussen
- (livefinalizees), und tr"agt alle nicht mehr markierten in die
- Liste deadfinalizess ein (allerdings werden sie vorher noch als
- erreicht markiert, damit sie nicht jetzt gleich gel"oscht werden).
-
-*****************************************************************************/
-
-static void searchlivefinalizees ()
-{
- finalizernode *fn = livefinalizees;
- finalizernode *lastlive = NULL;
-
- while (fn) {
-
- /* alle zu finalisierenden Objekte, die nicht mehr markiert sind: */
- if (isbitclear (markbits, fn->objstart)) {
- finalizernode *nextfn = fn->next;
-
- mark (heap + fn->objstart);
-
- if (lastlive) lastlive -> next = nextfn;
- else livefinalizees = nextfn;
-
- fn -> next = deadfinalizees;
- deadfinalizees = fn;
- fn = nextfn;
- }
- else {
- lastlive = fn;
- fn = fn->next;
- }
- }
-}
-
-
-
-/********************** Funktion: finalizedead *******************************
-
- ruft die 'finalize'-Methode aller Objekte in der 'deadfinalizees'-
- Liste auf.
- Achtung: Es kann hier eventuell zu neuerlichen Speicheranforderungen
- (mit potentiell notwendigem GC) kommen, deshalb m"ussen manche
- globalen Variablen in lokale Variblen kopiert werden
- (Reentrant-F"ahigkeit!!!)
-
-******************************************************************************/
-
-static void finalizedead()
-{
- finalizernode *fn = deadfinalizees;
- deadfinalizees = NULL;
-
- while (fn) {
- finalizernode *nextfn = fn->next;
-
- asm_calljavamethod (fn->finalizer, heap+fn->objstart, NULL,NULL,NULL);
- FREE (fn, finalizernode);
-
- fn = nextfn;
- }
-
-}
-
-
-
-/****************** Funktion: heap_docollect **********************************
-
- F"uhrt eine vollst"andige Garbage Collection durch
-
-******************************************************************************/
-
-static void heap_docollect ()
-{
- u4 freestart,freeend;
- void **p;
- bitfieldtype *dummy;
- u4 heapfreemem;
- u4 oldfillgrade;
-
-
- if (runverbose) {
- fprintf(stderr, "doing garbage collection\n");
- }
- /* alle Markierungsbits l"oschen */
- clearbitfield (markbits, topofheap);
-
- /* Alle vom Stack referenzierten Objekte markieren */
- asm_dumpregistersandcall (markstack);
-
- /* Alle von globalen Variablen erreichbaren Objekte markieren */
- p = chain_first (allglobalreferences);
- while (p) {
- mark (*p);
- p = chain_next (allglobalreferences);
- }
-
- /* alle Objekte durchsehen, die eine finalizer-Methode haben */
- searchlivefinalizees();
-
- /* alle Reference-Bits l"oschen, deren Objekte nicht */
- /* mehr erreichbar sind */
- maskfieldwithfield (referencebits, markbits, topofheap);
-
-
- /* Freispeicherliste initialisieren */
- memlist_init ();
-
-
- /* Heap schrittweise durchgehen, und alle freien Bl"ocke merken */
-
- heapfreemem = 0;
- freeend=0;
- for (;;) {
- /* Anfang des n"achsten freien Bereiches suchen */
- freestart = findnextcombination_set_unset
- (startbits, markbits, topofheap, freeend);
-
- /* Wenn es keinen freien Bereich mehr gibt -> fertig */
- if (freestart>=topofheap) goto freememfinished;
-
- /* Anfang des freien Bereiches markieren */
- setbit (markbits, freestart);
-
- /* Ende des freien Bereiches suchen */
- freeend = findnextsetbit (markbits, topofheap, freestart+1);
-
- /* Freien Bereich in Freispeicherliste einh"angen */
- memlist_addrange (freestart, freeend-freestart);
-
- /* Menge des freien Speichers mitnotieren */
- heapfreemem += (freeend-freestart);
- }
-
- freememfinished:
-
- /* Die Rollen von markbits und startbits vertauschen */
- dummy = markbits;
- markbits = startbits;
- startbits = dummy;
-
-
- /* Threashold-Wert f"ur n"achstes Collect */
- oldfillgrade = heapfillgrade;
- heapfillgrade = topofheap - heapfreemem;
- collectthreashold = heapfillgrade*3; /* eine nette Heuristik */
-
- /* Eventuell eine Meldung ausgeben */
- if (collectverbose) {
- sprintf (logtext, "Garbage Collection: previous/now = %d / %d ",
- (int) (oldfillgrade * BLOCKSIZE),
- (int) (heapfillgrade * BLOCKSIZE) );
- dolog ();
+ nomatch:
+ c = c->hashlink;
}
-
-
- /* alle gerade unerreichbar gewordenen Objekte mit
- finalize-Methoden jetzt finalisieren.
- Achtung: Diese Funktion kann zu neuerlichem GC f"uhren!! */
- finalizedead ();
-
+ /* class not found */
+ return NULL;
}
-/************************* Function: gc_init **********************************
-
- Initializes the garbage collection thread mechanism.
-
-******************************************************************************/
-
-#ifdef USE_THREADS
-iMux gcStartMutex;
-iMux gcThreadMutex;
-iCv gcConditionStart;
-iCv gcConditionDone;
-
-void
-gc_init (void)
-{
- gcStartMutex.holder = 0;
- gcStartMutex.count = 0;
- gcStartMutex.muxWaiters = 0;
-
- gcThreadMutex.holder = 0;
- gcThreadMutex.count = 0;
- gcThreadMutex.muxWaiters = 0;
-
- gcConditionStart.cvWaiters = 0;
- gcConditionStart.mux = 0;
-
- gcConditionDone.cvWaiters = 0;
- gcConditionDone.mux = 0;
-}
-#else
-void
-gc_init (void)
-{
-}
-#endif
-/************************* Function: gc_thread ********************************
+/************************** function: utf_strlen ******************************
- In an endless loop waits for a condition to be posted, then
- garbage collects the heap.
+ determine number of unicode characters in the utf string
-******************************************************************************/
+*******************************************************************************/
-#ifdef USE_THREADS
-void
-gc_thread (void)
+u4 utf_strlen(utf *u)
{
- intsRestore(); /* all threads start with interrupts disabled */
-
- assert(blockInts == 0);
-
- lock_mutex(&gcThreadMutex);
-
- for (;;)
- {
- wait_cond(&gcThreadMutex, &gcConditionStart, 0);
+ char *endpos = utf_end(u); /* points behind utf string */
+ char *utf_ptr = u->text; /* current position in utf text */
+ u4 len = 0; /* number of unicode characters */
- intsDisable();
- heap_docollect();
- intsRestore();
-
- signal_cond(&gcConditionDone);
+ while (utf_ptr<endpos) {
+ len++;
+ /* next unicode character */
+ utf_nextu2(&utf_ptr);
}
-}
-#endif
-
-void
-gc_call (void)
-{
-#ifdef USE_THREADS
- lock_mutex(&gcThreadMutex);
-
- signal_cond(&gcConditionStart);
- wait_cond(&gcThreadMutex, &gcConditionDone, 0);
-
- unlock_mutex(&gcThreadMutex);
-#else
- heap_docollect();
-#endif
-}
-
-
-/************************* Funktion: heap_init ********************************
-
- Initialisiert den Garbage Collector.
- Parameter:
- heapbytesize: Maximale Gr"osse des Heap (in Bytes)
- heapbytestartsize: Gr"osse des Heaps, bei dem zum ersten mal eine
- GC durchgef"uhrt werden soll.
- stackbottom: Ein Zeiger auf die Untergrenze des Stacks, im dem
- Referenzen auf Objekte stehen k"onnen.
-
-******************************************************************************/
-
-void heap_init (u4 heapbytesize, u4 heapbytestartsize, void **stackbottom)
-{
-
-#ifdef TRACECALLARGS
-
- heapsize = ALIGN (heapbytesize, getpagesize());
- heapsize = heapsize/BLOCKSIZE;
- heap = (void*) mmap ((void*) 0x10000000, (size_t) (heapsize * BLOCKSIZE),
- PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS | MAP_FIXED, -1, (off_t) 0);
- if (heap != (void *) 0x10000000) {
- perror("mmap");
- printf("address = %p\n", heap);
- panic("mmap failed\n");
- }
-
-#else
-
- heapsize = ALIGN (heapbytesize, 1024);
- heapsize = heapsize/BLOCKSIZE;
- heap = MNEW (heapblock, heapsize);
-
-#endif
-
- topofheap = 0;
- startbits = MNEW (bitfieldtype, heapsize/BITFIELDBITS);
- markbits = MNEW (bitfieldtype, heapsize/BITFIELDBITS);
- referencebits = MNEW (bitfieldtype, heapsize/BITFIELDBITS);
- clearbitfield (startbits, heapsize);
- clearbitfield (markbits, heapsize);
- clearbitfield (referencebits, heapsize);
-
- heapfillgrade = 0;
- collectthreashold = heapbytestartsize/BLOCKSIZE;
- allglobalreferences = chain_new ();
- bottom_of_stack = stackbottom;
-
- livefinalizees = NULL;
- deadfinalizees = NULL;
-}
-
-
-/****************** Funktion: heap_close **************************************
- Gibt allen ben"otigten Speicher frei
+ if (utf_ptr!=endpos)
+ /* string ended abruptly */
+ panic("illegal utf string");
-******************************************************************************/
-
-void heap_close ()
-{
-#ifndef TRACECALLARGS
- MFREE (heap, heapblock, heapsize); */
-#endif
- MFREE (startbits, bitfieldtype, heapsize/BITFIELDBITS);
- MFREE (markbits, bitfieldtype, heapsize/BITFIELDBITS);
- MFREE (referencebits, bitfieldtype, heapsize/BITFIELDBITS);
- chain_free (allglobalreferences);
-
- while (livefinalizees) {
- finalizernode *n = livefinalizees->next;
- FREE (livefinalizees, finalizernode);
- livefinalizees = n;
- }
+ return len;
}
-/***************** Funktion: heap_addreference ********************************
- Teilt dem GC eine Speicherstelle mit, an der eine globale Referenz
- auf Objekte gespeichert sein kann.
-******************************************************************************/
-void heap_addreference (void **reflocation)
-{
- intsDisable(); /* schani */
- chain_addlast (allglobalreferences, reflocation);
- intsRestore(); /* schani */
-}
+
+
-/***************** Funktion: heap_allocate ************************************
- Fordert einen Speicher vom Heap an, der eine gew"unschte Gr"osse
- (in Byte angegeben) haben muss.
- Wenn kein Speicher mehr vorhanden ist (auch nicht nach einem
- Garbage Collection-Durchlauf), dann wird NULL zur"uckgegeben.
- Zus"atzlich wird durch den Parameter 'references' angegeben, ob
- in das angelegte Objekt Referenzen auf andere Objekte eingetragen
- werden k"onnten.
- (Wichtig wegen Beschleunigung des Mark&Sweep-Durchlauf)
- Im Zweifelsfalle immer references=true verwenden.
-******************************************************************************/
-void *heap_allocate (u4 bytelength, bool references, methodinfo *finalizer)
-{
- u4 freestart,freelength;
- u4 length = ALIGN(bytelength, BLOCKSIZE) / BLOCKSIZE;
-
- intsDisable(); /* schani */
- memlist_getsuitable (&freestart, &freelength, length);
-onemoretry:
- if (!freelength) {
- if ( (topofheap+length > collectthreashold)
- || (topofheap+length > heapsize) ) {
- intsRestore();
- gc_call();
- intsDisable();
-
- memlist_getsuitable (&freestart, &freelength, length);
- if (freelength) goto onemoretry;
- }
-
- if (topofheap+length > heapsize) {
- sprintf (logtext, "Heap-Allocation failed for %d bytes",
- (int) bytelength);
- dolog();
- intsRestore(); /* schani */
- return NULL;
- }
-
- freestart = topofheap;
- freelength = length;
- setbit (startbits, topofheap);
- topofheap += length;
- }
- else {
- if (freelength>length) {
- setbit (startbits, freestart+length);
- memlist_addrange (freestart+length, freelength-length);
- }
- }
-
- if (references) setbit (referencebits, freestart);
- heapfillgrade += length;
- if (finalizer) {
- finalizernode *n = NEW(finalizernode);
- n -> next = livefinalizees;
- n -> objstart = freestart;
- n -> finalizer = finalizer;
- livefinalizees = n;
- }
-
- intsRestore(); /* schani */
- if (runverbose) {
- sprintf (logtext, "new returns: %lx", (long) (heap + freestart));
- dolog ();
- }
- return (void*) (heap + freestart);
-}