Skip to content

Instantly share code, notes, and snippets.

@llllllllll

llllllllll/constexpr_dict.h

Last active April 15, 2024 13:53
Show Gist options
  • Save llllllllll/54bc5ce2fdc078f1c4158508297ec50a to your computer and use it in GitHub Desktop.
Save llllllllll/54bc5ce2fdc078f1c4158508297ec50a to your computer and use it in GitHub Desktop.
Download ZIP
compile-time hashtable for C++17 which supports mixed dtype keys and values
Raw
constexpr_dict.h
#include <array>
#include <tuple>
#include <type_traits>
#include <utility>
namespace cdict {
template<char... cs>
using string = std::integer_sequence<char, cs...>;
template<typename C, C... cs>
constexpr auto operator""_s() {
return string<cs...>{};
}
namespace detail {
template<char... cs>
constexpr int atoi() {
int result = 0;
for (char c : {cs...}) {
result *= 10;
result += c - '0';
}
return result;
}
} // detail
template<char... cs>
constexpr std::integral_constant<int, detail::atoi<cs...>()> operator""_i() {
return {};
}
namespace detail {
template<typename K, auto v>
struct entry {};
template<typename... Es>
struct bucket {};
template<typename B, typename C>
struct bucket_merge;
template<typename... B, typename... C>
struct bucket_merge<bucket<B...>, bucket<C...>> {
using type = bucket<B..., C...>;
};
template<typename B>
struct bucket_length;
template<typename... Es>
struct bucket_length<bucket<Es...>> {
constexpr static std::size_t value = sizeof...(Es);
};
template<typename K, typename B>
struct bucket_lookup;
template<typename K,
typename BK,
typename... Ks,
auto head,
auto... tail>
struct bucket_lookup<K, bucket<entry<BK, head>, entry<Ks, tail>...>> {
private:
static constexpr auto get_value() {
if constexpr (std::is_same_v<K, BK>) {
return head;
}
else {
return bucket_lookup<K, bucket<entry<Ks, tail>...>>::value;
}
}
public:
constexpr static auto value = get_value();
};
template<typename K, auto v, typename B>
struct bucket_insert;
template<typename K, auto v>
struct bucket_insert<K, v, bucket<>> {
using type = bucket<entry<K, v>>;
};
template<typename K,
auto v,
typename BK,
typename... Ks,
auto head,
auto... tail>
struct bucket_insert<K, v, bucket<entry<BK, head>, entry<Ks, tail>...>> {
private:
using btail = bucket<entry<Ks, tail>...>;
public:
using type = std::conditional_t<
std::is_same_v<K, BK>,
typename bucket_merge<bucket<entry<K, v>>, btail>::type,
typename bucket_merge<bucket<entry<BK, head>>,
typename bucket_insert<K, v, btail>::type>::type>;
};
template<char... cs>
constexpr std::size_t hash(string<cs...>) {
constexpr std::int32_t mod = 65521;
std::array<char, sizeof...(cs)>{cs...};
std::uint32_t a = 1;
std::uint32_t b = 0;
for (char signed_char : {cs...}) {
unsigned char c = signed_char;
a = (a + c) % mod;
b = (b + a) % mod;
}
return (b << 16) | a;
}
template<auto v>
constexpr std::size_t hash(std::integral_constant<decltype(v), v>) {
return v;
}
template<typename D, std::size_t ix, typename B>
struct bucket_replace;
template<typename D>
struct increment_size;
template<std::size_t size, typename... Bs>
struct dict {
private:
template<typename K>
static constexpr auto get_index_and_bucket(K key) {
constexpr std::size_t hash_value = hash(key);
constexpr std::size_t ix = hash_value % sizeof...(Bs);
using as_tuple = std::tuple<Bs...>;
using bucket =
std::remove_reference_t<decltype(std::get<ix>(std::declval<as_tuple>()))>;
return std::make_tuple(ix, bucket{});
}
public:
constexpr dict() {}
template<typename K, typename V, V value>
constexpr auto emplace(K key,
std::integral_constant<V, value>) {
constexpr auto t = get_index_and_bucket(key);
constexpr auto ix = std::get<0>(t);
using bucket = std::remove_cv_t<std::remove_reference_t<decltype(std::get<1>(t))>>;
using new_bucket = typename bucket_insert<K,
value,
bucket>::type;
using inserted = typename bucket_replace<dict<size, Bs...>,
ix,
new_bucket>::type;
return typename increment_size<inserted>::type{};
}
template<typename K, char... cs>
auto emplace(K key, string<cs...>) {
static constexpr char value[sizeof...(cs) + 1] = {cs..., '\0'};
constexpr auto t = get_index_and_bucket(key);
constexpr auto ix = std::get<0>(t);
using bucket = std::remove_cv_t<std::remove_reference_t<decltype(std::get<1>(t))>>;
using new_bucket = typename bucket_insert<K,
value,
bucket>::type;
using inserted = typename bucket_replace<dict<size, Bs...>,
ix,
new_bucket>::type;
return typename increment_size<inserted>::type{};
}
template<typename K>
constexpr inline auto get(K key) {
auto [ix, bucket] = get_index_and_bucket(key);
return bucket_lookup<K, decltype(bucket)>::value;
}
};
template<std::size_t size, typename... Bs>
struct increment_size<dict<size, Bs...>> {
using type = dict<size + 1, Bs...>;
};
template<typename D, typename E>
struct dict_merge;
template<std::size_t n, typename... Ds, std::size_t m, typename... Es>
struct dict_merge<dict<n, Ds...>, dict<m, Es...>> {
using type = dict<n + m, Ds..., Es...>;
};
template<std::size_t n, typename HB, typename... Bs, std::size_t ix, typename B>
struct bucket_replace<dict<n, HB, Bs...>, ix, B> {
using type =
typename dict_merge<
dict<0, HB>,
typename bucket_replace<dict<n, Bs...>, ix - 1, B>::type>::type;
};
template<std::size_t n, typename HB, typename... Bs, typename B>
struct bucket_replace<dict<n, HB, Bs...>, 0, B> {
using type = dict<n, B, Bs...>;
};
} // namespace detail
inline auto cdict() {
return detail::dict<0,
detail::bucket<>,
detail::bucket<>,
detail::bucket<>,
detail::bucket<>,
detail::bucket<>,
detail::bucket<>,
detail::bucket<>,
detail::bucket<>>{};
}
} // namespace cdict
Raw
main.cc
#include <stdio.h>
#include "constexpr_dict.h"
using cdict::operator""_s;
using cdict::operator""_i;
int main() {
auto d = cdict::cdict();
auto first = d.emplace("ayy"_s, 100_i);
auto second = first.emplace("lmao"_s, 200_i);
auto third = second.emplace(300_i, "mixed dtype keys and values!"_s);
// printf's asm is easier to follow than std::cout
std::printf("ayy: %d\nlmao: %d\n300: %s\n",
third.get("ayy"_s),
third.get("lmao"_s),
third.get(300_i));
return 0;
}
Raw
main.s
.file "main.cc"
# GNU C++14 (GCC) version 7.1.1 20170516 (x86_64-pc-linux-gnu)
# compiled by GNU C version 7.1.1 20170516, GMP version 6.1.2, MPFR version 3.1.5-p2, MPC version 1.0.3, isl version isl-0.18-GMP
# GGC heuristics: --param ggc-min-expand=100 --param ggc-min-heapsize=131072
# options passed: -D_GNU_SOURCE -D _FORTIFY_SOURCE=2 main.cc
# -mtune=generic -march=x86-64 -O3 -std=gnu++1z -fPIE
# -fstack-check=specific -fstack-protector-strong -fverbose-asm
# options enabled: -fPIC -fPIE -faggressive-loop-optimizations
# -falign-labels -fasynchronous-unwind-tables -fauto-inc-dec
# -fbranch-count-reg -fcaller-saves -fchkp-check-incomplete-type
# -fchkp-check-read -fchkp-check-write -fchkp-instrument-calls
# -fchkp-narrow-bounds -fchkp-optimize -fchkp-store-bounds
# -fchkp-use-static-bounds -fchkp-use-static-const-bounds
# -fchkp-use-wrappers -fcode-hoisting -fcombine-stack-adjustments -fcommon
# -fcompare-elim -fcprop-registers -fcrossjumping -fcse-follow-jumps
# -fdefer-pop -fdelete-null-pointer-checks -fdevirtualize
# -fdevirtualize-speculatively -fdwarf2-cfi-asm -fearly-inlining
# -feliminate-unused-debug-types -fexceptions -fexpensive-optimizations
# -fforward-propagate -ffp-int-builtin-inexact -ffunction-cse -fgcse
# -fgcse-after-reload -fgcse-lm -fgnu-runtime -fgnu-unique
# -fguess-branch-probability -fhoist-adjacent-loads -fident -fif-conversion
# -fif-conversion2 -findirect-inlining -finline -finline-atomics
# -finline-functions -finline-functions-called-once
# -finline-small-functions -fipa-bit-cp -fipa-cp -fipa-cp-clone -fipa-icf
# -fipa-icf-functions -fipa-icf-variables -fipa-profile -fipa-pure-const
# -fipa-ra -fipa-reference -fipa-sra -fipa-vrp -fira-hoist-pressure
# -fira-share-save-slots -fira-share-spill-slots
# -fisolate-erroneous-paths-dereference -fivopts -fkeep-static-consts
# -fleading-underscore -flifetime-dse -flra-remat -flto-odr-type-merging
# -fmath-errno -fmerge-constants -fmerge-debug-strings
# -fmove-loop-invariants -fomit-frame-pointer -foptimize-sibling-calls
# -foptimize-strlen -fpartial-inlining -fpeel-loops -fpeephole -fpeephole2
# -fplt -fpredictive-commoning -fprefetch-loop-arrays -free
# -freg-struct-return -freorder-blocks -freorder-functions
# -frerun-cse-after-loop -fsched-critical-path-heuristic
# -fsched-dep-count-heuristic -fsched-group-heuristic -fsched-interblock
# -fsched-last-insn-heuristic -fsched-rank-heuristic -fsched-spec
# -fsched-spec-insn-heuristic -fsched-stalled-insns-dep -fschedule-fusion
# -fschedule-insns2 -fsemantic-interposition -fshow-column -fshrink-wrap
# -fshrink-wrap-separate -fsigned-zeros -fsplit-ivs-in-unroller
# -fsplit-loops -fsplit-paths -fsplit-wide-types -fssa-backprop
# -fssa-phiopt -fstack-protector-strong -fstdarg-opt -fstore-merging
# -fstrict-aliasing -fstrict-overflow -fstrict-volatile-bitfields
# -fsync-libcalls -fthread-jumps -ftoplevel-reorder -ftrapping-math
# -ftree-bit-ccp -ftree-builtin-call-dce -ftree-ccp -ftree-ch
# -ftree-coalesce-vars -ftree-copy-prop -ftree-cselim -ftree-dce
# -ftree-dominator-opts -ftree-dse -ftree-forwprop -ftree-fre
# -ftree-loop-distribute-patterns -ftree-loop-if-convert -ftree-loop-im
# -ftree-loop-ivcanon -ftree-loop-optimize -ftree-loop-vectorize
# -ftree-parallelize-loops= -ftree-partial-pre -ftree-phiprop -ftree-pre
# -ftree-pta -ftree-reassoc -ftree-scev-cprop -ftree-sink
# -ftree-slp-vectorize -ftree-slsr -ftree-sra -ftree-switch-conversion
# -ftree-tail-merge -ftree-ter -ftree-vrp -funit-at-a-time -funswitch-loops
# -funwind-tables -fverbose-asm -fzero-initialized-in-bss
# -m128bit-long-double -m64 -m80387 -malign-stringops
# -mavx256-split-unaligned-load -mavx256-split-unaligned-store
# -mfancy-math-387 -mfp-ret-in-387 -mfxsr -mglibc -mieee-fp
# -mlong-double-80 -mmmx -mno-sse4 -mpush-args -mred-zone -msse -msse2
# -mstv -mtls-direct-seg-refs -mvzeroupper
.section .rodata.str1.1,"aMS",@progbits,1
.LC0:
.string "ayy: %d\nlmao: %d\n300: %s\n"
.section .text.startup,"ax",@progbits
.p2align 4,,15
.globl main
.type main, @function
main:
.LFB1635:
.cfi_startproc
subq $4136, %rsp #,
orq $0, (%rsp) #,
addq $4128, %rsp #,
.cfi_def_cfa_offset 16
# /usr/include/bits/stdio2.h:104: return __printf_chk (__USE_FORTIFY_LEVEL - 1, __fmt, __va_arg_pack ());
leaq _ZZN5cdict6detail4dictILm2EJNS0_6bucketIJEEES3_NS2_IJNS0_5entryISt16integer_sequenceIcJLc108ELc109ELc97ELc111EEELi200EEEEEES3_NS2_IJNS4_IS5_IcJLc97ELc121ELc121EEELi100EEEEEES3_S3_S3_EE7emplaceISt17integral_constantIiLi300EEJLc109ELc105ELc120ELc101ELc100ELc32ELc100ELc116ELc121ELc112ELc101ELc32ELc107ELc101ELc121ELc115ELc32ELc97ELc110ELc100ELc32ELc118ELc97ELc108ELc117ELc101ELc115ELc33EEEEDaT_S5_IcJXspT0_EEEE5value(%rip), %r8 #,
leaq .LC0(%rip), %rsi #,
movl $200, %ecx #,
movl $100, %edx #,
movl $1, %edi #,
xorl %eax, %eax #
call __printf_chk@PLT #
# main.cc:20: }
xorl %eax, %eax #
addq $8, %rsp #,
.cfi_def_cfa_offset 8
ret
.cfi_endproc
.LFE1635:
.size main, .-main
.weak _ZZN5cdict6detail4dictILm2EJNS0_6bucketIJEEES3_NS2_IJNS0_5entryISt16integer_sequenceIcJLc108ELc109ELc97ELc111EEELi200EEEEEES3_NS2_IJNS4_IS5_IcJLc97ELc121ELc121EEELi100EEEEEES3_S3_S3_EE7emplaceISt17integral_constantIiLi300EEJLc109ELc105ELc120ELc101ELc100ELc32ELc100ELc116ELc121ELc112ELc101ELc32ELc107ELc101ELc121ELc115ELc32ELc97ELc110ELc100ELc32ELc118ELc97ELc108ELc117ELc101ELc115ELc33EEEEDaT_S5_IcJXspT0_EEEE5value
.section .rodata._ZZN5cdict6detail4dictILm2EJNS0_6bucketIJEEES3_NS2_IJNS0_5entryISt16integer_sequenceIcJLc108ELc109ELc97ELc111EEELi200EEEEEES3_NS2_IJNS4_IS5_IcJLc97ELc121ELc121EEELi100EEEEEES3_S3_S3_EE7emplaceISt17integral_constantIiLi300EEJLc109ELc105ELc120ELc101ELc100ELc32ELc100ELc116ELc121ELc112ELc101ELc32ELc107ELc101ELc121ELc115ELc32ELc97ELc110ELc100ELc32ELc118ELc97ELc108ELc117ELc101ELc115ELc33EEEEDaT_S5_IcJXspT0_EEEE5value,"aG",@progbits,_ZZN5cdict6detail4dictILm2EJNS0_6bucketIJEEES3_NS2_IJNS0_5entryISt16integer_sequenceIcJLc108ELc109ELc97ELc111EEELi200EEEEEES3_NS2_IJNS4_IS5_IcJLc97ELc121ELc121EEELi100EEEEEES3_S3_S3_EE7emplaceISt17integral_constantIiLi300EEJLc109ELc105ELc120ELc101ELc100ELc32ELc100ELc116ELc121ELc112ELc101ELc32ELc107ELc101ELc121ELc115ELc32ELc97ELc110ELc100ELc32ELc118ELc97ELc108ELc117ELc101ELc115ELc33EEEEDaT_S5_IcJXspT0_EEEE5value,comdat
.align 16
.type _ZZN5cdict6detail4dictILm2EJNS0_6bucketIJEEES3_NS2_IJNS0_5entryISt16integer_sequenceIcJLc108ELc109ELc97ELc111EEELi200EEEEEES3_NS2_IJNS4_IS5_IcJLc97ELc121ELc121EEELi100EEEEEES3_S3_S3_EE7emplaceISt17integral_constantIiLi300EEJLc109ELc105ELc120ELc101ELc100ELc32ELc100ELc116ELc121ELc112ELc101ELc32ELc107ELc101ELc121ELc115ELc32ELc97ELc110ELc100ELc32ELc118ELc97ELc108ELc117ELc101ELc115ELc33EEEEDaT_S5_IcJXspT0_EEEE5value, @gnu_unique_object
.size _ZZN5cdict6detail4dictILm2EJNS0_6bucketIJEEES3_NS2_IJNS0_5entryISt16integer_sequenceIcJLc108ELc109ELc97ELc111EEELi200EEEEEES3_NS2_IJNS4_IS5_IcJLc97ELc121ELc121EEELi100EEEEEES3_S3_S3_EE7emplaceISt17integral_constantIiLi300EEJLc109ELc105ELc120ELc101ELc100ELc32ELc100ELc116ELc121ELc112ELc101ELc32ELc107ELc101ELc121ELc115ELc32ELc97ELc110ELc100ELc32ELc118ELc97ELc108ELc117ELc101ELc115ELc33EEEEDaT_S5_IcJXspT0_EEEE5value, 29
_ZZN5cdict6detail4dictILm2EJNS0_6bucketIJEEES3_NS2_IJNS0_5entryISt16integer_sequenceIcJLc108ELc109ELc97ELc111EEELi200EEEEEES3_NS2_IJNS4_IS5_IcJLc97ELc121ELc121EEELi100EEEEEES3_S3_S3_EE7emplaceISt17integral_constantIiLi300EEJLc109ELc105ELc120ELc101ELc100ELc32ELc100ELc116ELc121ELc112ELc101ELc32ELc107ELc101ELc121ELc115ELc32ELc97ELc110ELc100ELc32ELc118ELc97ELc108ELc117ELc101ELc115ELc33EEEEDaT_S5_IcJXspT0_EEEE5value:
.byte 109
.byte 105
.byte 120
.byte 101
.byte 100
.byte 32
.byte 100
.byte 116
.byte 121
.byte 112
.byte 101
.byte 32
.byte 107
.byte 101
.byte 121
.byte 115
.byte 32
.byte 97
.byte 110
.byte 100
.byte 32
.byte 118
.byte 97
.byte 108
.byte 117
.byte 101
.byte 115
.byte 33
.byte 0
.ident "GCC: (GNU) 7.1.1 20170516"
.section .note.GNU-stack,"",@progbits
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment