Cttrie – Compile-time trie-based string matching for C++
smilingthax.github.io
Cttrie – Compile-time trie-based string matching for C++
1–10 of 21 posts
Re: Cttrie – Compile-time trie-based string matching for C++
#2Another approach not mentioned: LLVM's StringSwitch [1]. Unfortunately it's not designed to be used independent of LLVM, so it has a dependency or two. Also note that it's a slightly different use case (can only return different values, is not used for flow control).
[1] https://github.com/llvm-mirror/llvm/blob/master/include/llvm...
Re: Cttrie – Compile-time trie-based string matching for C++
#3This only an issue if you want to have many hardcoded strings in a switch. If you want that, there is a probably a better way to organize the code.
Re: Cttrie – Compile-time trie-based string matching for C++
#4I like this trick that I use in C. It's limited, as it only matches string prefixes, but it works pretty well in the end: https://tia.mat.br/posts/2018/02/01/more_on_string_switch_in...
It allows you to write something like this: https://github.com/lpereira/lwan/blob/master/src/lib/lwan-ti... -- which is generated as a binary search by GCC.
Re: Cttrie – Compile-time trie-based string matching for C++
#5Another approach not mentioned: LLVM's StringSwitch [1]. Unfortunately it's not designed to be used independent of LLVM, so it has a dependency or two. Also note that it's a slightly different use case (can only return different values, is not used for flow control). [1] https://github.com/llvm-mirror/llvm/blob/master/include/llvm...
It is mentioned right near the end of the slides.
Re: Cttrie – Compile-time trie-based string matching for C++
#6If you're OK with textual code generation, you can also use something like re2c:
And then you get the power of regexes too. re2c will match an arbitrary set of regexes (including constant strings) by walking through the string byte-by-byte, a single time.
A trie is basically a special case of a DFA.
Re: Cttrie – Compile-time trie-based string matching for C++
#7I like this trick that I use in C. It's limited, as it only matches string prefixes, but it works pretty well in the end: https://tia.mat.br/posts/2018/02/01/more_on_string_switch_in... It allows you to write something like this: https://github.com/lpereira/lwan/blob/master/src/lib/lwan-ti... -- which is generated as a binary search by GCC.
Something we’ve used before is preprocessor string hashing similar to [1]. Basically we hash strings at compile time to ints and use those for our case statements. Word of caution though, there’s the possibility of collisions. It works great on a limited set of strings like XML tags and such.
1. http://lolengine.net/blog/2011/12/20/cpp-constant-string-has...
Re: Cttrie – Compile-time trie-based string matching for C++
#8[deleted]
Re: Cttrie – Compile-time trie-based string matching for C++
#9This only an issue if you want to have many hardcoded strings in a switch. If you want that, there is a probably a better way to organize the code.
I'd assume that in most cases where this comes up, you're not exactly in a position to not use those strings, e.g. because they're defined in an input format you're processing.
Re: Cttrie – Compile-time trie-based string matching for C++
#10Interesting. The way I would have thought of doing something like this is by laying out each "switch" case sequentially in memory, then having the "SWITCH(string)" macro expand out to something that compute the offset necessary, using a similar pre-computed trie, and jump to that offset. That way fallthrough should work as expected.