Line data Source code
1 : /* src/toolbox/hashtable.hpp - functions for internal hashtables
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 :
26 : #ifndef HASHTABLE_HPP_
27 : #define HASHTABLE_HPP_ 1
28 :
29 : #include "config.h"
30 :
31 : #include <cassert> // for assert
32 : #include <cstddef> // for size_t
33 : #include <new> // for operator new
34 :
35 : #include "mm/memory.hpp" // for MemoryAllocator
36 :
37 : #include "toolbox/util.hpp" // for is_power_of_two, etc
38 :
39 : #include "vm/types.hpp" // for u4
40 : #include "vm/utf8.hpp" // for Utf8String
41 :
42 : class Mutex;
43 :
44 :
45 : /***
46 : * An instrusive hash table using open addressing.
47 : *
48 : * Entries stored in the table must conform to the following interface:
49 : * @code
50 : * struct Entry {
51 : * Entry();
52 : * Entry(const Entry&);
53 : *
54 : * // An Entry constructed with it's default constructor
55 : * // must return true for is_empty().
56 : * bool is_empty() const;
57 : * bool is_occupied() const;
58 : *
59 : * // make this an inline function that always
60 : * // returns false for an insert only table
61 : * bool is_deleted() const;
62 : *
63 : * void set_empty();
64 : * void set_occupied(const T&);
65 : *
66 : * // only required if you want to remove elements from the table,
67 : * // an insert-only table will work without it.
68 : * void set_deleted();
69 : *
70 : * // there must be an overload for any T that you want to insert
71 : * // into the table
72 : * void set_occupied(const T&);
73 : *
74 : * // these are only ever called on occupied entries
75 : * bool operator==(const T&);
76 : * size_t hash() const;
77 : * };
78 : * @endcode
79 : *
80 : * An entry can be in one of three states: empty, occupied and deleted.
81 : *
82 : * Each table entry must have an unique key that identifies it.
83 : * The key must be stored in the entry itself, it is not stored separately in
84 : * the table.
85 : *
86 : * After inserting an element its key and the key's hash code may never
87 : * change.
88 : *
89 : * Calling find(), insert() or remove() on the table invalidates pointers
90 : * to elements in the table, EntryRefs and Iterators.
91 : *
92 : * This hash table is not thread safe.
93 : *
94 : * If you want an insert only hash table Entry should not have a set_deleted()
95 : * method. If the is_deleted() method is inline and always returns false
96 : * it can be inlined away, and there should be no overhead.
97 : *
98 : * @tparam Entry The type of element stored in the table.
99 : * Must conform to the interface mentioned above
100 : * Should be small, a pointer is optimal.
101 : * @tparam Allocator STL style allocator for Entries.
102 : *
103 : * @note
104 : * The design of the hash table is taken from CPython
105 : * as presented in the book `Beautiful Code',
106 : * and Google's sparsehash (https://code.google.com/p/sparsehash)
107 : *
108 : * @Cpp11 Use C++11 move semantics to move entries on resize instead of copying them
109 : */
110 : template<typename _Entry,
111 : typename _Allocator = MemoryAllocator<_Entry> >
112 : struct HashTable {
113 : typedef _Entry Entry;
114 : typedef _Allocator Allocator;
115 :
116 : static const size_t DEFAULT_INITIAL_CAPACITY = 256;
117 : static const size_t DEFAULT_LOAD_FACTOR = 85;
118 :
119 : /***
120 : * Creates an empty hash table.
121 : *
122 : * @Cpp11 Make this a constexpr
123 : */
124 1304 : HashTable() : entries(0),
125 : capacity(0),
126 : count(0),
127 : deleted(0),
128 : threshold(0),
129 1304 : load_factor(DEFAULT_LOAD_FACTOR) {}
130 :
131 72070 : HashTable(size_t initial_capacity, size_t load_factor = DEFAULT_LOAD_FACTOR) {
132 72070 : assert(initial_capacity > 0);
133 :
134 72070 : this->capacity = initial_capacity;
135 72070 : this->count = 0;
136 72070 : this->load_factor = load_factor;
137 :
138 72070 : allocate_table();
139 72070 : };
140 :
141 71906 : ~HashTable() { destroy(entries, capacity); }
142 :
143 : /***
144 : * A reference to an entry in the table.
145 : *
146 : * Can be obtained via find(), and used with insert() and remove()
147 : * for insertion and deletion with a single hash lookup.
148 : */
149 : class EntryRef {
150 : public:
151 : /***
152 : * Check if entry pointed to by ref is valid.
153 : *
154 : * Accessing an invalid entry leads to undefined behaviour.
155 : */
156 11232017 : operator bool() const { return occupied; }
157 :
158 : /***
159 : * Access to refs entry.
160 : * Only use this if operator bool() returns true
161 : *
162 : * You MUST NOT alter the key of entry
163 : */
164 9329295 : Entry *operator->() { return entry; }
165 7828488 : Entry &operator*() { return *entry; }
166 : private:
167 10732785 : EntryRef(Entry *e, bool occupied) : entry(e), occupied(occupied) {}
168 :
169 : Entry *entry;
170 : bool occupied;
171 :
172 : friend struct HashTable;
173 : };
174 :
175 : /***
176 : * An STL style iterator that can be used to traverse all
177 : * elements stored in the table
178 : */
179 : class Iterator {
180 : public:
181 : bool operator==(Iterator it) const { return pos == it.pos; }
182 456626 : bool operator!=(Iterator it) const { return pos != it.pos; }
183 :
184 420673 : Iterator& operator++() {
185 420673 : pos = next_occupied(pos, end);
186 :
187 420673 : return *this;
188 : }
189 : Iterator operator++(int) {
190 : Iterator it(*this);
191 : ++(*this);
192 : return it;
193 : }
194 :
195 0 : Entry& operator*() { return *pos; }
196 841346 : Entry* operator->() { return pos; }
197 : private:
198 71906 : Iterator(Entry *pos, Entry *end) : pos(pos), end(end) {}
199 :
200 : Entry *pos, *end;
201 :
202 : friend struct HashTable;
203 : };
204 :
205 : /***
206 : * Find entry for key.
207 : * Iff no such entry exists converting the returned ref to bool yields false.
208 : * The returned EntryRef can be used to insert or remove items.
209 : *
210 : * T must have a member function:
211 : * size_t hash() const;
212 : * T must be equality comparable to an Entry
213 : */
214 : template<typename T>
215 10732785 : EntryRef find(const T& t) {
216 : // make sure table has at least one unoccupied entry
217 10732785 : if ((count + deleted) >= threshold)
218 680 : grow_table(capacity + 1);
219 :
220 : EXPENSIVE_ASSERT(has_empty_entries());
221 :
222 10732785 : size_t hash = t.hash();
223 10732785 : size_t index = hash;
224 10732785 : size_t perturb = hash;
225 :
226 10732785 : Entry *insert_pos = NULL;
227 10732785 : bool occupied = false;
228 :
229 11331364 : while (1) {
230 22064149 : Entry *e = entries + fast_modulo(index, capacity);
231 :
232 22064149 : if (e->is_empty()) {
233 3715719 : if (insert_pos) {
234 : // No entry for key found, could be inserted at insert_pos
235 0 : break;
236 : } else {
237 : // No entry for key found, could be inserted at e
238 3715719 : insert_pos = e;
239 3715719 : break;
240 : }
241 18348430 : } else if (e->is_deleted() && !insert_pos) {
242 : // Not the entry we're looking for, but we could insert here
243 0 : insert_pos = e;
244 18348430 : } else if (*e == t) {
245 : // Found entry
246 7017066 : insert_pos = e;
247 7017066 : occupied = true;
248 7017066 : break;
249 : }
250 :
251 : // e does not contain the entry we are looking for
252 : // or a deleted entry, keep searching
253 11331364 : index = (5 * index) + 1 + perturb;
254 11331364 : perturb >>= 5;
255 : }
256 :
257 : // single point of return for RVO
258 10732785 : return EntryRef(insert_pos, occupied);
259 : }
260 :
261 : /***
262 : * Insert element into table.
263 : * Does nothing if it is already present.
264 : *
265 : * Returns the newly inserted or already present element.
266 : *
267 : * T must have a member function:
268 : * size_t hash() const;
269 : * T must be equality comparable to an Entry
270 : * T must be assignable to an Entry
271 : */
272 : template<typename T>
273 7329256 : Entry& insert(const T& t) {
274 7329256 : return insert(find(t), t);
275 : }
276 :
277 : /***
278 : * Insert into entry pointed to by ref.
279 : * Does nothing if it is already present.
280 : *
281 : * Returns the newly inserted or already present element.
282 : *
283 : * `e' MUST have the same key as was used to obtain `ref'.
284 : *
285 : * T must have a member function:
286 : * size_t hash() const;
287 : * T must be equality comparable to an Entry
288 : * T must be assignable to an Entry
289 : */
290 : template<typename T>
291 7828488 : Entry& insert(EntryRef ref, const T& t) {
292 7828488 : if (ref) {
293 4113540 : return *ref;
294 : } else {
295 3714948 : return update(ref, t);
296 : }
297 : }
298 :
299 : /***
300 : * Insert or update element in table.
301 : *
302 : * Returns the newly inserted element.
303 : *
304 : * T must have a member function:
305 : * size_t hash() const;
306 : * T must be equality comparable to an Entry
307 : * T must be assignable to an Entry
308 : */
309 : template<typename T>
310 : Entry& update(const T& t) {
311 : return update(find(t), t);
312 : }
313 :
314 : /***
315 : * Insert or update element in table.
316 : *
317 : * Returns the newly inserted element.
318 : *
319 : * `e' MUST have the same key as was used to obtain `ref'.
320 : *
321 : * T must have a member function:
322 : * size_t hash() const;
323 : * T must be equality comparable to an Entry
324 : * T must be assignable to an Entry
325 : */
326 : template<typename T>
327 3714948 : Entry& update(EntryRef ref, const T& t) {
328 3714948 : if (ref->is_empty()) {
329 : // insert into empty entry
330 3714948 : count++;
331 0 : } else if (ref->is_deleted()) {
332 : // overwrite deleted entry
333 0 : count++;
334 0 : deleted--;
335 : }
336 :
337 3714948 : ref->set_occupied(t);
338 :
339 3714948 : return *ref;
340 : }
341 :
342 : /**
343 : * Utility function for hashtables that store key value pairs
344 : */
345 : template<typename Key, typename Val>
346 : Entry& insert(const Key& k, const Val& v) {
347 : return insert(find(k), Entry(k, v));
348 : }
349 :
350 : /**
351 : * Utility function for hashtables that store key value pairs
352 : */
353 : template<typename Key, typename Val>
354 499232 : Entry& insert(EntryRef ref, const Key& k, const Val& v) {
355 499232 : return insert(ref, Entry(k, v));
356 : }
357 :
358 : /**
359 : * Utility function for hashtables that store key value pairs
360 : */
361 : template<typename Key, typename Val>
362 : Entry& update(const Key& k, const Val& v) {
363 : return update(find(k), Entry(k, v));
364 : }
365 :
366 : /**
367 : * Utility function for hashtables that store key value pairs
368 : */
369 : template<typename Key, typename Val>
370 : Entry& update(EntryRef ref, const Key& k, const Val& v) {
371 : return update(ref, Entry(k, v));
372 : }
373 :
374 : /***
375 : * Remove entry pointed to by ref.
376 : *
377 : * `e' MUST have the same key as was used to obtain `ref'.
378 : *
379 : * T must have a member function:
380 : * size_t hash() const;
381 : * T must be equality comparable to an Entry
382 : */
383 : void remove(EntryRef ref) {
384 : if (ref) {
385 : ref->set_deleted();
386 :
387 : count--;
388 : deleted++;
389 : }
390 : }
391 :
392 : /***
393 : * Remove element from table.
394 : *
395 : * T must have a member function:
396 : * size_t hash() const;
397 : * T must be equality comparable to an Entry
398 : */
399 : template<typename T>
400 : void remove(const T& t) {
401 : remove(find(t));
402 : }
403 :
404 : /***
405 : * Remove all entries from the table.
406 : */
407 : void clear() {
408 : count = 0;
409 : deleted = 0;
410 :
411 : for (Entry *e = entries, *end = entries + capacity; e != end; ++e) {
412 : e->set_empty();
413 : }
414 : }
415 :
416 : /***
417 : * Makes sure the table has enough space for at least n entries
418 : */
419 1304 : void reserve(size_t n) {
420 1304 : if (n <= capacity)
421 0 : return;
422 :
423 1304 : grow_table(n);
424 : }
425 :
426 : /***
427 : * Change the tables load factor.
428 : * This never triggers a resizing, a resize may be triggered by the next
429 : * call to find, insert, update or erase.
430 : */
431 1304 : void set_load_factor(size_t load_factor) {
432 1304 : assert(load_factor > 0);
433 1304 : assert(load_factor < 100);
434 :
435 1304 : this->load_factor = load_factor;
436 1304 : update_threshold();
437 1304 : }
438 :
439 : /***
440 : * Access to all occupied entries in table.
441 : */
442 35953 : Iterator begin() {
443 35953 : Entry *begin = entries;
444 35953 : Entry *end = entries + capacity;
445 :
446 : // skip to first entry that is occupied
447 35953 : if (begin != end && !begin->is_occupied())
448 34666 : begin = next_occupied(begin, end);
449 :
450 35953 : return Iterator(begin, end);
451 : }
452 :
453 35953 : Iterator end() {
454 35953 : return Iterator(entries + capacity, entries + capacity);
455 : }
456 :
457 456626 : size_t size() { return count; }
458 : bool empty() { return count == 0; }
459 : private:
460 : HashTable(const HashTable&); // non-copyable
461 : HashTable& operator=(const HashTable&); // non-assignable
462 :
463 : bool has_empty_entries() {
464 : return capacity > (count + deleted);
465 : }
466 :
467 : /**
468 : * Increase capacity, re-allocate table and copy over all old entries
469 : */
470 1984 : void grow_table(size_t new_capacity) {
471 1984 : Entry *old_entries = entries;
472 1984 : size_t old_capacity = capacity;
473 :
474 1984 : capacity = next_power_of_two(new_capacity);
475 :
476 1984 : assert(capacity > 0);
477 1984 : assert(capacity > old_capacity);
478 1984 : allocate_table();
479 :
480 : // re-insert all entries
481 2620352 : for (Entry *it = old_entries, *end = old_entries + old_capacity; it != end; ++it) {
482 2618368 : if (it->is_occupied()) {
483 : // We use an optimized version of the hash lookup here.
484 : // We can omit some checks since we know that,
485 : // a) the table contains no deleted entries,
486 : // b) every entry we insert has a unique key
487 :
488 2225270 : size_t hash = it->hash();
489 2225270 : size_t index = hash;
490 2225270 : size_t perturb = hash;
491 :
492 807820 : while (1) {
493 3033090 : Entry& e = entries[fast_modulo(index, capacity)];
494 :
495 3033090 : if (e.is_empty()) {
496 2225270 : e.set_occupied(*it);
497 2225270 : break;
498 : }
499 :
500 : // e does not contain the entry we are looking for
501 : // or a deleted entry, keep searching
502 807820 : index = (5 * index) + 1 + perturb;
503 807820 : perturb >>= 5;
504 : }
505 : }
506 : }
507 :
508 : // free old table
509 1984 : destroy(old_entries, old_capacity);
510 1984 : }
511 :
512 : /***
513 : * Allocate table with given capacity.
514 : * Also recomputes resize threshold
515 : */
516 74054 : void allocate_table() {
517 74054 : assert(is_power_of_two(capacity));
518 :
519 74054 : deleted = 0;
520 74054 : update_threshold();
521 :
522 : // allocate new table
523 74054 : entries = allocator.allocate(capacity);
524 74054 : assert(capacity == 0 || entries != NULL);
525 :
526 : // initialize table entries
527 74054 : new (entries) Entry[capacity]();
528 74054 : }
529 :
530 73890 : void destroy(Entry *es, size_t sz) {
531 21100194 : for (Entry *it = es, *end = it + sz; it != end; ++it) {
532 21026304 : it->~Entry();
533 : }
534 :
535 73890 : allocator.deallocate(es, sz);
536 73890 : }
537 :
538 75358 : void update_threshold() {
539 75358 : threshold = (capacity * load_factor) / 100;
540 75358 : }
541 :
542 455339 : static Entry *next_occupied(Entry *current, Entry *end) {
543 455339 : if (current == end) return current;
544 :
545 9203968 : do {
546 9203968 : ++current;
547 : } while (current != end && !current->is_occupied());
548 :
549 455339 : return current;
550 : }
551 :
552 : Entry *entries; // the table of entries
553 : size_t capacity; // number of elements the table can hold
554 : size_t count; // number of elements stored in the table
555 : size_t deleted; // number of deleted elements in the table
556 : size_t threshold; // table will be resized when `count' gets
557 : // greater than `threshold'
558 : size_t load_factor; // used to compute threshold
559 : Allocator allocator; // used to allocate table
560 : };
561 :
562 :
563 : /***
564 : * A HashTable entry that uses Utf8Strings as key.
565 : * Useful for using a HashTable as a hash map.
566 : *
567 : * @code
568 : * typedef HashTable<NameValueEntry<int> > HashMap;
569 : *
570 : * HashMap map;
571 : * Utf8String key = ...;
572 : *
573 : * map.insert(key, 5);
574 : *
575 : * int i = *map.find(key);
576 : * @endcode
577 : *
578 : * The NULL string is forbidden as key
579 : *
580 : * @Cpp11 Add a templated typedef of HashTable that makes using it as a hash map easier.
581 : */
582 : template<typename Value>
583 : struct NameValuePair {
584 : NameValuePair() {}
585 : NameValuePair(Utf8String name, Value v) : _name(name), _value(v) {}
586 :
587 : Utf8String name() const { return _name; }
588 : Value& value() { return _value; }
589 : const Value& value() const { return _value; }
590 : private:
591 : Utf8String _name;
592 : Value _value;
593 :
594 : /// Interface to HashTable
595 :
596 : size_t hash() const { return _name.hash(); }
597 :
598 : bool is_empty() const { return _name == (utf*) 0; }
599 : bool is_deleted() const { return _name == (utf*) 1; }
600 : bool is_occupied() const { return _name > (utf*) 1; }
601 :
602 : void set_empty() { _name = (utf*) 0; }
603 : void set_deleted() { _name = (utf*) 1; }
604 : void set_occupied(const NameValuePair& n) { (*this) = n; }
605 :
606 : bool operator==(Utf8String u) const { return _name == u; }
607 : bool operator==(const NameValuePair& n) const { return _name == n._name; }
608 :
609 : template<typename T, typename A>
610 : friend struct HashTable;
611 : };
612 :
613 : /***
614 : * Same as NameValuePair, but for insert only hash tables.
615 : */
616 : template<typename Value>
617 18407936 : struct InsertOnlyNameValuePair {
618 18407936 : InsertOnlyNameValuePair() {}
619 499232 : InsertOnlyNameValuePair(Utf8String name, Value v) : _name(name), _value(v) {}
620 :
621 420673 : Utf8String key() const { return _name; }
622 2254626 : Value& value() { return _value; }
623 : const Value& value() const { return _value; }
624 :
625 : Value *operator->() { return _value; }
626 : Value &operator*() { return *_value; }
627 : private:
628 : Utf8String _name;
629 : Value _value;
630 :
631 : /// Interface to HashTable
632 :
633 0 : size_t hash() const { return _name.hash(); }
634 :
635 3967205 : bool is_empty() const { return _name == (utf*) 0; }
636 2968741 : bool is_deleted() const { return _name == (utf*) 1; }
637 9203968 : bool is_occupied() const { return _name > (utf*) 1; }
638 :
639 : void set_empty() { _name = (utf*) 0; }
640 : void set_deleted() { _name = (utf*) 1; }
641 499232 : void set_occupied(const InsertOnlyNameValuePair& n) { (*this) = n; }
642 :
643 2968741 : bool operator==(Utf8String u) const { return _name == u; }
644 : bool operator==(const InsertOnlyNameValuePair& n) const { return _name == n._name; }
645 :
646 : template<typename T, typename A>
647 : friend struct HashTable;
648 : };
649 :
650 :
651 : /***
652 : * A HashTable entry that uses a Utf8String as key.
653 : * Useful for using a HashTable as an intrusive hash map.
654 : *
655 : * The key is not stored separately in the entry, Value must store
656 : * and provide access to the key.
657 : *
658 : * The type Value must have members for accessing the key:
659 : * @code
660 : * Utf8String key() const;
661 : * void set_key(Utf8String);
662 : * @endcode
663 : *
664 : * The NULL string is forbidden as key
665 : */
666 : template<typename Value>
667 : struct NamedEntry : Value {
668 : NamedEntry() {}
669 : NamedEntry(const Value& v) : Value(v) {}
670 : private:
671 : using Value::key;
672 : using Value::set_key;
673 :
674 : /// Interface to HashTable
675 :
676 : size_t hash() const { return key().hash(); }
677 :
678 : bool is_empty() const { return key() == (utf*) 0; }
679 : bool is_deleted() const { return key() == (utf*) 1; }
680 : bool is_occupied() const { return key() > (utf*) 1; }
681 :
682 : void set_empty() { set_key((utf*) 0); }
683 : void set_deleted() { set_key((utf*) 1); }
684 : void set_occupied(const NamedEntry& e) { (*this) = e; }
685 :
686 : bool operator==(Utf8String u) const { return key() == u; }
687 : bool operator==(const Value& v) const { return key() == v.key(); }
688 :
689 : template<typename T, typename A>
690 : friend struct HashTable;
691 : };
692 :
693 :
694 : /***
695 : * Same as NamedEntry, but for insert only hash tables.
696 : */
697 : template<typename Value>
698 2503680 : struct InsertOnlyNamedEntry : Value {
699 5175296 : InsertOnlyNamedEntry() {}
700 3381763 : InsertOnlyNamedEntry(const Value& v) : Value(v) {}
701 : // InsertOnlyNamedEntry(Utf8String key, const Value& v) : Value(v) { set_key(key); }
702 : private:
703 : using Value::key;
704 : using Value::set_key;
705 :
706 : /// Interface to HashTable
707 :
708 2127802 : size_t hash() const { return key().hash(); }
709 :
710 8077887 : bool is_empty() const { return key() == (utf*) 0; }
711 2737395 : bool is_deleted() const { return false; }
712 2503680 : bool is_occupied() const { return key() != (utf*) 0; }
713 :
714 : void set_empty() { set_key((utf*) 0); }
715 3381763 : void set_occupied(const Value& v) { (*this) = v; }
716 :
717 46917 : bool operator==(Utf8String u) const { return key() == u; }
718 2690478 : bool operator==(const Value& v) const { return key() == v.key(); }
719 :
720 : template<typename T, typename A>
721 : friend struct HashTable;
722 : };
723 :
724 :
725 : /* data structures for hashtables ********************************************
726 :
727 : All utf-symbols, javastrings and classes are stored in global
728 : hashtables, so every symbol exists only once. Equal symbols have
729 : identical pointers. The functions for adding hashtable elements
730 : search the table for the element with the specified name/text and
731 : return it on success. Otherwise a new hashtable element is created.
732 :
733 : The hashtables use external linking for handling collisions. The
734 : hashtable structure contains a pointer <ptr> to the array of
735 : hashtable slots. The number of hashtable slots and therefore the
736 : size of this array is specified by the element <size> of hashtable
737 : structure. <entries> contains the number of all hashtable elements
738 : stored in the table, including those in the external chains. The
739 : hashtable element structures (utf, literalstring, classinfo)
740 : contain both a pointer to the next hashtable element as a link for
741 : the external hash chain and the key of the element. The key is
742 : computed from the text of the string or the classname by using up
743 : to 8 characters.
744 :
745 : If the number of entries in the hashtable exceeds twice the size of
746 : the hashtableslot-array it is supposed that the average length of
747 : the external chains has reached a value beyond 2. Therefore the
748 : functions for adding hashtable elements (utf_new, class_new,
749 : literalstring_new) double the hashtableslot-array. In this
750 : restructuring process all elements have to be inserted into the new
751 : hashtable and new external chains must be built.
752 :
753 : Example for the layout of a hashtable:
754 :
755 : hashtable.ptr-->+-------------------+
756 : | |
757 : ...
758 : | |
759 : +-------------------+ +-------------------+ +-------------------+
760 : | hashtable element |-->| hashtable element |-->| hashtable element |-->NULL
761 : +-------------------+ +-------------------+ +-------------------+
762 : | hashtable element |
763 : +-------------------+ +-------------------+
764 : | hashtable element |-->| hashtable element |-->NULL
765 : +-------------------+ +-------------------+
766 : | hashtable element |-->NULL
767 : +-------------------+
768 : | |
769 : ...
770 : | |
771 : +-------------------+
772 :
773 : */
774 :
775 : /* hashtable ******************************************************************/
776 :
777 : struct hashtable {
778 : Mutex *mutex; /* required for locking */
779 : u4 size; /* current size of the hashtable */
780 : u4 entries; /* number of entries in the table */
781 : void **ptr; /* pointer to hashtable */
782 : };
783 :
784 :
785 : /* function prototypes ********************************************************/
786 :
787 : /* create hashtable */
788 : void hashtable_create(hashtable *hash, u4 size);
789 :
790 : /* creates and resizes a hashtable */
791 : hashtable *hashtable_resize(hashtable *hash, u4 size);
792 :
793 : /* frees a hashtable */
794 : void hashtable_free(hashtable *hash);
795 :
796 : #endif // HASHTABLE_HPP_
797 :
798 :
799 : /*
800 : * These are local overrides for various environment variables in Emacs.
801 : * Please do not remove this and leave it at the end of the file, where
802 : * Emacs will automagically detect them.
803 : * ---------------------------------------------------------------------
804 : * Local variables:
805 : * mode: c++
806 : * indent-tabs-mode: t
807 : * c-basic-offset: 4
808 : * tab-width: 4
809 : * End:
810 : * vim:noexpandtab:sw=4:ts=4:
811 : */
|
