1 /* src/toolbox/hashtable.h - functions for internal hashtables
3 Copyright (C) 1996-2005, 2006, 2008
4 CACAOVM - Verein zur Foerderung der freien virtuellen Maschine CACAO
6 This file is part of CACAO.
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.
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.
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
29 /* forward typedefs ***********************************************************/
31 typedef struct hashtable hashtable;
37 #include "threads/mutex.hpp"
39 #include "vm/global.h"
43 /* data structures for hashtables ********************************************
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.
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
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.
71 Example for the layout of a hashtable:
73 hashtable.ptr-->+-------------------+
77 +-------------------+ +-------------------+ +-------------------+
78 | hashtable element |-->| hashtable element |-->| hashtable element |-->NULL
79 +-------------------+ +-------------------+ +-------------------+
81 +-------------------+ +-------------------+
82 | hashtable element |-->| hashtable element |-->NULL
83 +-------------------+ +-------------------+
84 | hashtable element |-->NULL
94 /* hashtable ******************************************************************/
97 #if defined(ENABLE_THREADS)
98 Mutex *mutex; /* required for locking */
100 u4 size; /* current size of the hashtable */
101 u4 entries; /* number of entries in the table */
102 void **ptr; /* pointer to hashtable */
106 /* function prototypes ********************************************************/
112 /* create hashtable */
113 void hashtable_create(hashtable *hash, u4 size);
115 /* creates and resizes a hashtable */
116 hashtable *hashtable_resize(hashtable *hash, u4 size);
118 /* frees a hashtable */
119 void hashtable_free(hashtable *hash);
125 #endif /* _HASHTABLE_H */
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 * ---------------------------------------------------------------------
135 * indent-tabs-mode: t