src/toolbox/hashtable.h

   1 /* src/toolbox/hashtable.h - functions for internal hashtables
   2
   3    Copyright (C) 1996-2005, 2006 R. Grafl, A. Krall, C. Kruegel,
   4    C. Oates, R. Obermaisser, M. Platter, M. Probst, S. Ring,
   5    E. Steiner, C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich,
   6    J. Wenninger, 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., 51 Franklin Street, Fifth Floor, Boston, MA
  23    02110-1301, USA.
  24
  25    Contact: cacao@cacaojvm.org
  26
  27    Authors: Reinhard Grafl
  28             Christian Thalinger
  29
  30    $Id: hashtable.h 8295 2007-08-11 17:57:24Z michi $
  31
  32 */
  33
  34
  35 #ifndef _HASHTABLE_H
  36 #define _HASHTABLE_H
  37
  38 /* forward typedefs ***********************************************************/
  39
  40 typedef struct hashtable hashtable;
  41
  42
  43 #include "config.h"
  44 #include "vm/types.h"
  45
  46 #include "vm/global.h"
  47 #include "vmcore/utf8.h"
  48
  49
  50 /* data structures for hashtables ********************************************
  51
  52    All utf-symbols, javastrings and classes are stored in global
  53    hashtables, so every symbol exists only once. Equal symbols have
  54    identical pointers.  The functions for adding hashtable elements
  55    search the table for the element with the specified name/text and
  56    return it on success. Otherwise a new hashtable element is created.
  57
  58    The hashtables use external linking for handling collisions. The
  59    hashtable structure contains a pointer <ptr> to the array of
  60    hashtable slots. The number of hashtable slots and therefore the
  61    size of this array is specified by the element <size> of hashtable
  62    structure. <entries> contains the number of all hashtable elements
  63    stored in the table, including those in the external chains.  The
  64    hashtable element structures (utf, literalstring, classinfo)
  65    contain both a pointer to the next hashtable element as a link for
  66    the external hash chain and the key of the element. The key is
  67    computed from the text of the string or the classname by using up
  68    to 8 characters.
  69
  70    If the number of entries in the hashtable exceeds twice the size of
  71    the hashtableslot-array it is supposed that the average length of
  72    the external chains has reached a value beyond 2. Therefore the
  73    functions for adding hashtable elements (utf_new, class_new,
  74    literalstring_new) double the hashtableslot-array. In this
  75    restructuring process all elements have to be inserted into the new
  76    hashtable and new external chains must be built.
  77
  78    Example for the layout of a hashtable:
  79
  80 hashtable.ptr-->+-------------------+
  81                 |                   |
  82                          ...
  83                 |                   |
  84                 +-------------------+   +-------------------+   +-------------------+
  85                 | hashtable element |-->| hashtable element |-->| hashtable element |-->NULL
  86                 +-------------------+   +-------------------+   +-------------------+
  87                 | hashtable element |
  88                 +-------------------+   +-------------------+
  89                 | hashtable element |-->| hashtable element |-->NULL
  90                 +-------------------+   +-------------------+
  91                 | hashtable element |-->NULL
  92                 +-------------------+
  93                 |                   |
  94                          ...
  95                 |                   |
  96                 +-------------------+
  97
  98 */
  99
 100
 101 /* hashtable ******************************************************************/
 102
 103 struct hashtable {
 104 #if defined(ENABLE_THREADS)
 105         java_object_t      *header;         /* required for locking               */
 106 #endif
 107         u4                  size;           /* current size of the hashtable      */
 108         u4                  entries;        /* number of entries in the table     */
 109         void              **ptr;            /* pointer to hashtable               */
 110 };
 111
 112
 113 /* function prototypes ********************************************************/
 114
 115 /* create hashtable */
 116 void hashtable_create(hashtable *hash, u4 size);
 117
 118 /* creates and resizes a hashtable */
 119 hashtable *hashtable_resize(hashtable *hash, u4 size);
 120
 121 /* frees a hashtable */
 122 void hashtable_free(hashtable *hash);
 123
 124 #endif /* _HASHTABLE_H */
 125
 126
 127 /*
 128  * These are local overrides for various environment variables in Emacs.
 129  * Please do not remove this and leave it at the end of the file, where
 130  * Emacs will automagically detect them.
 131  * ---------------------------------------------------------------------
 132  * Local variables:
 133  * mode: c
 134  * indent-tabs-mode: t
 135  * c-basic-offset: 4
 136  * tab-width: 4
 137  * End:
 138  */