src/toolbox/hashtable.h

   1 /* src/toolbox/hashtable.h - functions for internal hashtables
   2
   3    Copyright (C) 1996-2005, 2006, 2008
   4    CACAOVM - Verein zur Foerderung der freien virtuellen Maschine CACAO
   5
   6    This file is part of CACAO.
   7
   8    This program is free software; you can redistribute it and/or
   9    modify it under the terms of the GNU General Public License as
  10    published by the Free Software Foundation; either version 2, or (at
  11    your option) any later version.
  12
  13    This program is distributed in the hope that it will be useful, but
  14    WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16    General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with this program; if not, write to the Free Software
  20    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  21    02110-1301, USA.
  22
  23 */
  24
  25
  26 #ifndef _HASHTABLE_H
  27 #define _HASHTABLE_H
  28
  29 /* forward typedefs ***********************************************************/
  30
  31 typedef struct hashtable hashtable;
  32
  33
  34 #include "config.h"
  35 #include "vm/types.h"
  36
  37 #include "threads/mutex.hpp"
  38
  39 #include "vm/global.h"
  40 #include "vm/utf8.h"
  41
  42
  43 /* data structures for hashtables ********************************************
  44
  45    All utf-symbols, javastrings and classes are stored in global
  46    hashtables, so every symbol exists only once. Equal symbols have
  47    identical pointers.  The functions for adding hashtable elements
  48    search the table for the element with the specified name/text and
  49    return it on success. Otherwise a new hashtable element is created.
  50
  51    The hashtables use external linking for handling collisions. The
  52    hashtable structure contains a pointer <ptr> to the array of
  53    hashtable slots. The number of hashtable slots and therefore the
  54    size of this array is specified by the element <size> of hashtable
  55    structure. <entries> contains the number of all hashtable elements
  56    stored in the table, including those in the external chains.  The
  57    hashtable element structures (utf, literalstring, classinfo)
  58    contain both a pointer to the next hashtable element as a link for
  59    the external hash chain and the key of the element. The key is
  60    computed from the text of the string or the classname by using up
  61    to 8 characters.
  62
  63    If the number of entries in the hashtable exceeds twice the size of
  64    the hashtableslot-array it is supposed that the average length of
  65    the external chains has reached a value beyond 2. Therefore the
  66    functions for adding hashtable elements (utf_new, class_new,
  67    literalstring_new) double the hashtableslot-array. In this
  68    restructuring process all elements have to be inserted into the new
  69    hashtable and new external chains must be built.
  70
  71    Example for the layout of a hashtable:
  72
  73 hashtable.ptr-->+-------------------+
  74                 |                   |
  75                          ...
  76                 |                   |
  77                 +-------------------+   +-------------------+   +-------------------+
  78                 | hashtable element |-->| hashtable element |-->| hashtable element |-->NULL
  79                 +-------------------+   +-------------------+   +-------------------+
  80                 | hashtable element |
  81                 +-------------------+   +-------------------+
  82                 | hashtable element |-->| hashtable element |-->NULL
  83                 +-------------------+   +-------------------+
  84                 | hashtable element |-->NULL
  85                 +-------------------+
  86                 |                   |
  87                          ...
  88                 |                   |
  89                 +-------------------+
  90
  91 */
  92
  93
  94 /* hashtable ******************************************************************/
  95
  96 struct hashtable {
  97 #if defined(ENABLE_THREADS)
  98         Mutex              *mutex;          /* required for locking               */
  99 #endif
 100         u4                  size;           /* current size of the hashtable      */
 101         u4                  entries;        /* number of entries in the table     */
 102         void              **ptr;            /* pointer to hashtable               */
 103 };
 104
 105
 106 /* function prototypes ********************************************************/
 107
 108 #ifdef __cplusplus
 109 extern "C" {
 110 #endif
 111
 112 /* create hashtable */
 113 void hashtable_create(hashtable *hash, u4 size);
 114
 115 /* creates and resizes a hashtable */
 116 hashtable *hashtable_resize(hashtable *hash, u4 size);
 117
 118 /* frees a hashtable */
 119 void hashtable_free(hashtable *hash);
 120
 121 #ifdef __cplusplus
 122 }
 123 #endif
 124
 125 #endif /* _HASHTABLE_H */
 126
 127
 128 /*
 129  * These are local overrides for various environment variables in Emacs.
 130  * Please do not remove this and leave it at the end of the file, where
 131  * Emacs will automagically detect them.
 132  * ---------------------------------------------------------------------
 133  * Local variables:
 134  * mode: c
 135  * indent-tabs-mode: t
 136  * c-basic-offset: 4
 137  * tab-width: 4
 138  * End:
 139  */