1# Copyright (c) 2022 Meta
2#
3# SPDX-License-Identifier: Apache-2.0
4
5menu "Hashmap (Hash Table) Support"
6
7config SYS_HASH_MAP
8	bool "Hashmap support"
9	help
10	  Support for Hashmaps (a.k.a. Hash Tables).
11
12	  Hashmaps are data structures that are used when insertion, removal, and
13	  lookup of key-value pairs must be done in O(1) time (on average).
14
15if SYS_HASH_MAP
16
17config SYS_HASH_MAP_SC
18	bool "Separate-Chaining Hashmap"
19	help
20	  Separate-Chaining Hashmaps implement each bucket as a linked-list.
21
22	  They are perhaps more useful on resource-constrained systems where
23	  large contiguous memory regions are scarce.
24
25	  The main disadvantage of Separate-Chaining Hashmaps are that their
26	  use tends to incur more cache-misses as nodes are spread throughout
27	  the heap.
28
29config SYS_HASH_MAP_OA_LP
30	bool "Open-Addressing / Linear Probe Hashmap"
31	help
32	  Open-Addressing Hashmaps do not chain entries together but instead
33	  store all entries in the table itself which is a contiguously allocated
34	  memory region.
35
36	  The main advantage of Open-Addressing Hashmaps are due to their
37	  contiguous allocation which improves performance on systems with
38	  memory caching.
39
40config SYS_HASH_MAP_CXX
41	bool "C++ Hashmap"
42	select CPP
43	select REQUIRES_FULL_LIBCPP
44	select CPP_EXCEPTIONS
45	help
46	  This enables a C wrapper around the C++ std::unordered_map.
47
48	  It is mainly used for benchmarking purposes.
49
50choice SYS_HASH_MAP_CHOICE
51	prompt "Default hashmap implementation"
52	default SYS_HASH_MAP_CHOICE_SC
53
54config SYS_HASH_MAP_CHOICE_SC
55	bool "Default hash is Separate-Chaining"
56	select SYS_HASH_MAP_SC
57
58config SYS_HASH_MAP_CHOICE_OA_LP
59	bool "Default hash is Open-Addressing / Linear Probe"
60	select SYS_HASH_MAP_OA_LP
61
62config SYS_HASH_MAP_CHOICE_CXX
63	bool "Default hash is C++"
64	select SYS_HASH_MAP_CXX
65
66endchoice # SYS_HASH_MAP_CHOICE
67
68endif
69
70endmenu
71