search

c9s / r3

libr3 is a high-performance path dispatching library. It compiles your route paths into a prefix tree (trie). By using the constructed prefix trie in the start-up time, you may dispatch your routes with efficiency
http://c9s.github.com/r3/bench.html
MIT License
813 stars 83 forks source link

Correcting issue and memory leak when using multiple edges #141

Closed bjosv closed 2 years ago

bjosv commented 2 years ago

When r3_node_find_common_prefix() searches for the common prefix it selects the first matched edge, which might not be the best match.

This PR makes sure the longest matching prefix is selected, and includes a testcase for reproducing the issue on baseline. This makes sure the following paths can be inserted without problems:

  "/path/{id}"
  "/path/{id1}/{id2}"
  "/path/{id1}/{id2}/{id3}"

The issue also triggered memoryleaks in the legacy testcase check_tree::test_insert_pathl(). This was seen by building using: CFLAGS="-fno-omit-frame-pointer -fsanitize=leak" cmake .. These leaks are now gone aswell, see:

check_tree::test_insert_pathl()
    ..
    ret = r3_tree_insert_path(n, "/foo/{id}",  NULL);
    ..
    ret = r3_tree_insert_path(n, "/foo/{idx}/{idy}",  NULL);
    ..
    ret = r3_tree_insert_path(n, "/foo/{idx}/{idh}",  NULL); <-- leaks (..and the path was not added)
bjosv commented 2 years ago

Hi! Is there anything missing in this PR that I need look at?

c9s commented 2 years ago

sorry, was too busy so i missed the mail.

everything looks great! thank you!

bjosv commented 2 years ago

Thanks!