Line data Source code
1 : /* src/toolbox/intern_table.hpp - Intern table header
2 :
3 : Copyright (C) 1996-2013
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 : #ifndef INTERN_TABLE_HPP_
26 : #define INTERN_TABLE_HPP_ 1
27 :
28 : #include "config.h"
29 :
30 : #include "threads/mutex.hpp"
31 :
32 : #include "toolbox/assert.hpp"
33 : #include "toolbox/hashtable.hpp"
34 : #include "toolbox/util.hpp"
35 :
36 : /***
37 : *
38 : * A specialized hash map that allows for parallel access by multiple threads.
39 : * This is achieved by splitting up the table into multiple segments. Each
40 : * segment is a separate hash table protected by its own lock.
41 : * We need no global lock for accessing segments because there is a
42 : * fixed number of segments.
43 : *
44 : * InternTable has the same requirements on elements you want to insert into
45 : * the table as HashTable.
46 : *
47 : * InternTable is meant to be used as a global, so its constructor and desctructor
48 : * do no real work. You have to call initialize() and destroy() manually.
49 : *
50 : * @tparam _Entry The type of element stored in the table.
51 : * Must fulfill the same requirements as a
52 : * HashTable entry.
53 : * @tparam concurrency_factor The maximum number of threads that can access
54 : * the table concurrently. Must be a power of two.
55 : *
56 : * @note
57 : * If we don't wan't any concurrency we can use an intern table with a
58 : * concurrency factor of 1. This means the table has exactly one global
59 : * lock without any overhead.
60 : */
61 : template<class _Entry, size_t concurrency_factor=4>
62 : struct InternTable {
63 : typedef _Entry Entry;
64 :
65 : static const size_t DEFAULT_INITIAL_CAPACITY = 256;
66 : static const size_t DEFAULT_LOAD_FACTOR = 85;
67 :
68 330 : InternTable() : segments(0) {}
69 :
70 326 : void initialize(size_t initial_capacity = DEFAULT_INITIAL_CAPACITY, size_t load_factor = DEFAULT_LOAD_FACTOR) {
71 326 : assert(!is_initialized());
72 326 : assert(load_factor > 0);
73 326 : assert(load_factor < 100);
74 326 : assert(initial_capacity > 0);
75 :
76 326 : segments = new Segment[concurrency_factor];
77 :
78 : // evenly divide capacity among segments
79 326 : size_t cap = divide_rounding_up(initial_capacity, concurrency_factor);
80 :
81 1630 : for (size_t i = 0; i < concurrency_factor; ++i) {
82 1304 : segments[i].initialize(cap, load_factor);
83 : }
84 326 : }
85 :
86 : void destroy() {
87 : delete [] segments;
88 : segments = 0;
89 : }
90 :
91 652 : bool is_initialized() const { return segments != 0; }
92 :
93 : template<typename Thunk>
94 6074479 : const Entry& intern(const Thunk& t) {
95 : EXPENSIVE_ASSERT(is_initialized());
96 :
97 6074479 : size_t hash = t.hash();
98 :
99 6074479 : return segments[hash % concurrency_factor].intern(t);
100 : }
101 : private:
102 : InternTable(const InternTable&); // non-copyable
103 : InternTable& operator=(const InternTable&); // non-assignable
104 :
105 1304 : struct Segment {
106 1304 : void initialize(size_t initial_capacity, size_t load_factor) {
107 1304 : ht.set_load_factor(load_factor);
108 1304 : ht.reserve(initial_capacity);
109 1304 : }
110 :
111 : void destroy() {
112 : ht.clear();
113 : }
114 :
115 : template<typename Thunk>
116 6074479 : const Entry& intern(const Thunk& thunk) {
117 6074479 : MutexLocker lock(mutex);
118 :
119 6074479 : return ht.insert(thunk);
120 : }
121 :
122 : HashTable<Entry> ht;
123 : Mutex mutex; // for locking this segment
124 : };
125 :
126 : Segment *segments; // the sub-hashtables
127 : };
128 :
129 : #endif // INTERN_TABLE_HPP_
130 :
131 : /*
132 : * These are local overrides for various environment variables in Emacs.
133 : * Please do not remove this and leave it at the end of the file, where
134 : * Emacs will automagically detect them.
135 : * ---------------------------------------------------------------------
136 : * Local variables:
137 : * mode: c++
138 : * indent-tabs-mode: t
139 : * c-basic-offset: 4
140 : * tab-width: 4
141 : * End:
142 : * vim:noexpandtab:sw=4:ts=4:
143 : */
|
