src/vm/tables.h

   1 /* src/vm/tables.h -
   2
   3    Copyright (C) 1996-2005 R. Grafl, A. Krall, C. Kruegel, C. Oates,
   4    R. Obermaisser, M. Platter, M. Probst, S. Ring, E. Steiner,
   5    C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich, J. Wenninger,
   6    Institut f. Computersprachen - TU Wien
   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: Christian Thalinger
  30
  31    $Id: tables.h 3678 2005-11-16 12:11:22Z twisti $
  32
  33 */
  34
  35
  36 #ifndef _TABLES_H
  37 #define _TABLES_H
  38
  39 #include <stdio.h>
  40
  41
  42 /* forward typedefs ***********************************************************/
  43
  44 typedef struct hashtable hashtable;
  45
  46 #include "config.h"
  47 #include "vm/types.h"
  48
  49 #include "vm/utf8.h"
  50
  51
  52 /* data structures for hashtables ********************************************
  53
  54    All utf-symbols, javastrings and classes are stored in global
  55    hashtables, so every symbol exists only once. Equal symbols have
  56    identical pointers.  The functions for adding hashtable elements
  57    search the table for the element with the specified name/text and
  58    return it on success. Otherwise a new hashtable element is created.
  59
  60    The hashtables use external linking for handling collisions. The
  61    hashtable structure contains a pointer <ptr> to the array of
  62    hashtable slots. The number of hashtable slots and therefore the
  63    size of this array is specified by the element <size> of hashtable
  64    structure. <entries> contains the number of all hashtable elements
  65    stored in the table, including those in the external chains.  The
  66    hashtable element structures (utf, literalstring, classinfo)
  67    contain both a pointer to the next hashtable element as a link for
  68    the external hash chain and the key of the element. The key is
  69    computed from the text of the string or the classname by using up
  70    to 8 characters.
  71
  72    If the number of entries in the hashtable exceeds twice the size of
  73    the hashtableslot-array it is supposed that the average length of
  74    the external chains has reached a value beyond 2. Therefore the
  75    functions for adding hashtable elements (utf_new, class_new,
  76    literalstring_new) double the hashtableslot-array. In this
  77    restructuring process all elements have to be inserted into the new
  78    hashtable and new external chains must be built.
  79
  80    Example for the layout of a hashtable:
  81
  82 hashtable.ptr-->+-------------------+
  83                 |                   |
  84                          ...
  85                 |                   |
  86                 +-------------------+   +-------------------+   +-------------------+
  87                 | hashtable element |-->| hashtable element |-->| hashtable element |-->NULL
  88                 +-------------------+   +-------------------+   +-------------------+
  89                 | hashtable element |
  90                 +-------------------+   +-------------------+
  91                 | hashtable element |-->| hashtable element |-->NULL
  92                 +-------------------+   +-------------------+
  93                 | hashtable element |-->NULL
  94                 +-------------------+
  95                 |                   |
  96                          ...
  97                 |                   |
  98                 +-------------------+
  99
 100 */
 101
 102
 103 /* hashtable ******************************************************************/
 104
 105 struct hashtable {
 106         u4     size;
 107         u4     entries;                     /* number of entries in the table     */
 108         void **ptr;                         /* pointer to hashtable               */
 109 };
 110
 111
 112 #define CLASS(name)     (unicode_getclasslink(unicode_new_char(name)))
 113
 114 extern hashtable utf_hash;     /* hashtable for utf8-symbols */
 115 extern hashtable string_hash;  /* hashtable for javastrings  */
 116
 117
 118 /* function prototypes ********************************************************/
 119
 120 /* creates hashtables for symboltables */
 121 bool tables_init(void);
 122
 123 /* free memory for hashtables */
 124 void tables_close(void);
 125
 126 /* get javatype according to a typedescriptor */
 127 u2 desc_to_type(utf *descriptor);
 128
 129 /* get length of a datatype */
 130 u2 desc_typesize(utf *descriptor);
 131
 132 /* create hashtable */
 133 void init_hashtable(hashtable *hash, u4 size);
 134
 135 #if defined(USE_THREADS) && defined(NATIVE_THREADS)
 136 void tables_lock(void);
 137 void tables_unlock(void);
 138 #endif
 139
 140 #endif /* _TABLES_H */
 141
 142
 143 /*
 144  * These are local overrides for various environment variables in Emacs.
 145  * Please do not remove this and leave it at the end of the file, where
 146  * Emacs will automagically detect them.
 147  * ---------------------------------------------------------------------
 148  * Local variables:
 149  * mode: c
 150  * indent-tabs-mode: t
 151  * c-basic-offset: 4
 152  * tab-width: 4
 153  * End:
 154  */