8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25 #ifndef SHARE_UTILITIES_CONCURRENT_HASH_TABLE_HPP
26 #define SHARE_UTILITIES_CONCURRENT_HASH_TABLE_HPP
27
28 // A mostly concurrent-hash-table where the read-side is wait-free, inserts are
29 // CAS and deletes mutual exclude each other on per bucket-basis. VALUE is the
30 // type kept inside each Node and CONFIG contains hash and allocation methods.
31 // A CALLBACK_FUNC and LOOKUP_FUNC needs to be provided for get and insert.
32
33 class Thread;
34
35 template <typename VALUE, typename CONFIG, MEMFLAGS F>
36 class ConcurrentHashTable : public CHeapObj<F> {
37 private:
38 // This is the internal node structure.
39 // Only constructed with placement new from memory allocated with MEMFLAGS of
40 // the InternalTable or user-defined memory.
41 class Node {
42 private:
43 Node * volatile _next;
44 VALUE _value;
45 public:
46 Node(const VALUE& value, Node* next = NULL)
47 : _next(next), _value(value) {
356 };
357
358 // Check for dead items in this table with range. During shrink/grow we cannot
359 // guarantee that we only visit nodes once. To keep it simple caller will
360 // have locked _resize_lock.
361 template <typename EVALUATE_FUNC, typename DELETE_FUNC>
362 void do_bulk_delete_locked_for(Thread* thread, size_t start_idx,
363 size_t stop_idx, EVALUATE_FUNC& eval_f,
364 DELETE_FUNC& del_f, bool is_mt = false);
365
366 // Method to delete one items.
367 template <typename LOOKUP_FUNC>
368 void delete_in_bucket(Thread* thread, Bucket* bucket, LOOKUP_FUNC& lookup_f);
369
370 public:
371 ConcurrentHashTable(size_t log2size = DEFAULT_START_SIZE_LOG2,
372 size_t log2size_limit = DEFAULT_MAX_SIZE_LOG2,
373 size_t grow_hint = DEFAULT_GROW_HINT);
374
375 ~ConcurrentHashTable();
376
377 size_t get_size_log2(Thread* thread);
378 size_t get_node_size() const { return sizeof(Node); }
379 bool is_max_size_reached() { return _size_limit_reached; }
380
381 // This means no paused bucket resize operation is going to resume
382 // on this table.
383 bool is_safepoint_safe() { return _resize_lock_owner == NULL; }
384
385 // Re-size operations.
386 bool shrink(Thread* thread, size_t size_limit_log2 = 0);
387 bool grow(Thread* thread, size_t size_limit_log2 = 0);
388
389 // All callbacks for get are under critical sections. Other callbacks may be
390 // under critical section or may have locked parts of table. Calling any
391 // methods on the table during a callback is not supported.Only MultiGetHandle
392 // supports multiple gets.
393
394 // LOOKUP_FUNC is matching methods, VALUE_FUNC creates value to be inserted
395 // and CALLBACK_FUNC is called with new or old value. Returns true if the
460
461 // Visit all items with SCAN_FUNC if no concurrent resize. Takes the resize
462 // lock to avoid concurrent resizes. Else returns false.
463 template <typename SCAN_FUNC>
464 bool try_scan(Thread* thread, SCAN_FUNC& scan_f);
465
466 // Visit all items with SCAN_FUNC when the resize lock is obtained.
467 template <typename SCAN_FUNC>
468 void do_scan(Thread* thread, SCAN_FUNC& scan_f);
469
470 // Destroying items matching EVALUATE_FUNC, before destroying items
471 // DELETE_FUNC is called, if resize lock is obtained. Else returns false.
472 template <typename EVALUATE_FUNC, typename DELETE_FUNC>
473 bool try_bulk_delete(Thread* thread, EVALUATE_FUNC& eval_f,
474 DELETE_FUNC& del_f);
475
476 // Destroying items matching EVALUATE_FUNC, before destroying items
477 // DELETE_FUNC is called, when the resize lock is successfully obtained.
478 template <typename EVALUATE_FUNC, typename DELETE_FUNC>
479 void bulk_delete(Thread* thread, EVALUATE_FUNC& eval_f, DELETE_FUNC& del_f);
480
481 // Writes statistics to the outputStream. Item sizes are calculated with
482 // VALUE_SIZE_FUNC.
483 template <typename VALUE_SIZE_FUNC>
484 void statistics_to(Thread* thread, VALUE_SIZE_FUNC& vs_f, outputStream* st,
485 const char* table_name);
486
487 // Moves all nodes from this table to to_cht
488 bool try_move_nodes_to(Thread* thread, ConcurrentHashTable<VALUE, CONFIG, F>* to_cht);
489
490 // This is a Curiously Recurring Template Pattern (CRPT) interface for the
491 // specialization.
492 struct BaseConfig {
493 public:
494 // Called when the hash table needs the hash for a VALUE.
495 static uintx get_hash(const VALUE& value, bool* dead) {
496 return CONFIG::get_hash(value, dead);
497 }
498 // On get_copy if no value is found then this value is returned.
499 static const VALUE& notfound() {
|
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25 #ifndef SHARE_UTILITIES_CONCURRENT_HASH_TABLE_HPP
26 #define SHARE_UTILITIES_CONCURRENT_HASH_TABLE_HPP
27
28 #include "utilities/tableStatistics.hpp"
29
30 // A mostly concurrent-hash-table where the read-side is wait-free, inserts are
31 // CAS and deletes mutual exclude each other on per bucket-basis. VALUE is the
32 // type kept inside each Node and CONFIG contains hash and allocation methods.
33 // A CALLBACK_FUNC and LOOKUP_FUNC needs to be provided for get and insert.
34
35 class Thread;
36
37 template <typename VALUE, typename CONFIG, MEMFLAGS F>
38 class ConcurrentHashTable : public CHeapObj<F> {
39 private:
40 // This is the internal node structure.
41 // Only constructed with placement new from memory allocated with MEMFLAGS of
42 // the InternalTable or user-defined memory.
43 class Node {
44 private:
45 Node * volatile _next;
46 VALUE _value;
47 public:
48 Node(const VALUE& value, Node* next = NULL)
49 : _next(next), _value(value) {
358 };
359
360 // Check for dead items in this table with range. During shrink/grow we cannot
361 // guarantee that we only visit nodes once. To keep it simple caller will
362 // have locked _resize_lock.
363 template <typename EVALUATE_FUNC, typename DELETE_FUNC>
364 void do_bulk_delete_locked_for(Thread* thread, size_t start_idx,
365 size_t stop_idx, EVALUATE_FUNC& eval_f,
366 DELETE_FUNC& del_f, bool is_mt = false);
367
368 // Method to delete one items.
369 template <typename LOOKUP_FUNC>
370 void delete_in_bucket(Thread* thread, Bucket* bucket, LOOKUP_FUNC& lookup_f);
371
372 public:
373 ConcurrentHashTable(size_t log2size = DEFAULT_START_SIZE_LOG2,
374 size_t log2size_limit = DEFAULT_MAX_SIZE_LOG2,
375 size_t grow_hint = DEFAULT_GROW_HINT);
376
377 ~ConcurrentHashTable();
378 TableRateStatistics _stats_rate;
379
380 size_t get_size_log2(Thread* thread);
381 size_t get_node_size() const { return sizeof(Node); }
382 bool is_max_size_reached() { return _size_limit_reached; }
383
384 // This means no paused bucket resize operation is going to resume
385 // on this table.
386 bool is_safepoint_safe() { return _resize_lock_owner == NULL; }
387
388 // Re-size operations.
389 bool shrink(Thread* thread, size_t size_limit_log2 = 0);
390 bool grow(Thread* thread, size_t size_limit_log2 = 0);
391
392 // All callbacks for get are under critical sections. Other callbacks may be
393 // under critical section or may have locked parts of table. Calling any
394 // methods on the table during a callback is not supported.Only MultiGetHandle
395 // supports multiple gets.
396
397 // LOOKUP_FUNC is matching methods, VALUE_FUNC creates value to be inserted
398 // and CALLBACK_FUNC is called with new or old value. Returns true if the
463
464 // Visit all items with SCAN_FUNC if no concurrent resize. Takes the resize
465 // lock to avoid concurrent resizes. Else returns false.
466 template <typename SCAN_FUNC>
467 bool try_scan(Thread* thread, SCAN_FUNC& scan_f);
468
469 // Visit all items with SCAN_FUNC when the resize lock is obtained.
470 template <typename SCAN_FUNC>
471 void do_scan(Thread* thread, SCAN_FUNC& scan_f);
472
473 // Destroying items matching EVALUATE_FUNC, before destroying items
474 // DELETE_FUNC is called, if resize lock is obtained. Else returns false.
475 template <typename EVALUATE_FUNC, typename DELETE_FUNC>
476 bool try_bulk_delete(Thread* thread, EVALUATE_FUNC& eval_f,
477 DELETE_FUNC& del_f);
478
479 // Destroying items matching EVALUATE_FUNC, before destroying items
480 // DELETE_FUNC is called, when the resize lock is successfully obtained.
481 template <typename EVALUATE_FUNC, typename DELETE_FUNC>
482 void bulk_delete(Thread* thread, EVALUATE_FUNC& eval_f, DELETE_FUNC& del_f);
483
484 // Calcuate statistics. Item sizes are calculated with VALUE_SIZE_FUNC.
485 template <typename VALUE_SIZE_FUNC>
486 TableStatistics statistics_calculate(Thread* thread, VALUE_SIZE_FUNC& vs_f);
487
488 // Gets statistics if available, if not return old one. Item sizes are calculated with
489 // VALUE_SIZE_FUNC.
490 template <typename VALUE_SIZE_FUNC>
491 TableStatistics statistics_get(Thread* thread, VALUE_SIZE_FUNC& vs_f, TableStatistics old);
492
493 // Writes statistics to the outputStream. Item sizes are calculated with
494 // VALUE_SIZE_FUNC.
495 template <typename VALUE_SIZE_FUNC>
496 void statistics_to(Thread* thread, VALUE_SIZE_FUNC& vs_f, outputStream* st,
497 const char* table_name);
498
499 // Moves all nodes from this table to to_cht
500 bool try_move_nodes_to(Thread* thread, ConcurrentHashTable<VALUE, CONFIG, F>* to_cht);
501
502 // This is a Curiously Recurring Template Pattern (CRPT) interface for the
503 // specialization.
504 struct BaseConfig {
505 public:
506 // Called when the hash table needs the hash for a VALUE.
507 static uintx get_hash(const VALUE& value, bool* dead) {
508 return CONFIG::get_hash(value, dead);
509 }
510 // On get_copy if no value is found then this value is returned.
511 static const VALUE& notfound() {
|