From 8f942ca8a5259e8dac4745df1b15b80467346a0d Mon Sep 17 00:00:00 2001 From: Simon Marchi Date: Mon, 4 Nov 2024 13:27:35 -0500 Subject: gdbsupport: add unordered_dense.h 4.4.0 Add a copy of unordered_dense.h from [1]. This file implements an efficient hash map and hash set with a nice C++ interface (a near drop-in for std::unordered_map and std::unordered_set). This is expected to be used to replace uses of `htab_t`, for improved code readability and type safety. Performance-wise, it is preferred to the std types (std::unordered_map and std::unordered_set) due to it using open addressing vs closed addressing for the std types. I chose this particular implementation because it is simple to use, it's a standalone header and it typically performs well in benchmarks I have seen (e.g. [2]). The license being MIT, my understanding is that it's not a problem to use it and re-distribute it. Add two additional files, gdbsupport/unordered_map.h and gdbsupport/unordered_set.h, which make the map and set offered by gdbsupport/unordered_dense.h available as gdb::unordered_map and gdb::unordered_set. [1] https://github.com/martinus/unordered_dense [2] https://jacksonallan.github.io/c_cpp_hash_tables_benchmark/#conclusion-which-hash-table-to-choose Change-Id: I0c7469ccf9a14540465479e58b2a5140a2440a7d Approved-By: Tom Tromey --- gdbsupport/unordered_map.h | 37 +++++++++++++++++++++++++++++++++++++ 1 file changed, 37 insertions(+) create mode 100644 gdbsupport/unordered_map.h (limited to 'gdbsupport/unordered_map.h') diff --git a/gdbsupport/unordered_map.h b/gdbsupport/unordered_map.h new file mode 100644 index 0000000..96407b5 --- /dev/null +++ b/gdbsupport/unordered_map.h @@ -0,0 +1,37 @@ +/* Copyright (C) 2024 Free Software Foundation, Inc. + + This file is part of GDB. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see . */ + +#ifndef GDBSUPPORT_UNORDERED_MAP_H +#define GDBSUPPORT_UNORDERED_MAP_H + +#include "unordered_dense.h" + +namespace gdb +{ + +template, + typename KeyEqual = std::equal_to> +using unordered_map + = ankerl::unordered_dense::map + >, + ankerl::unordered_dense::bucket_type::standard>; + +} /* namespace gdb */ + +#endif /* GDBSUPPORT_UNORDERED_MAP_H */ -- cgit v1.1