Calculate the levenshtein distance between two string values
| 1761 | |
| 1762 | // Calculate the levenshtein distance between two string values |
| 1763 | FORCE_INLINE |
| 1764 | gdv_int32 levenshtein(int64_t context, const char* in1, int32_t in1_len, const char* in2, |
| 1765 | int32_t in2_len) { |
| 1766 | if (in1_len < 0 || in2_len < 0) { |
| 1767 | char err_msg[128]; |
| 1768 | snprintf(err_msg, sizeof(err_msg), |
| 1769 | "LEVENSHTEIN: input lengths must be non-negative, got %d and %d", in1_len, |
| 1770 | in2_len); |
| 1771 | gdv_fn_context_set_error_msg(context, err_msg); |
| 1772 | return 0; |
| 1773 | } |
| 1774 | |
| 1775 | // Check input size 0 |
| 1776 | if (in1_len == 0) { |
| 1777 | return in2_len; |
| 1778 | } |
| 1779 | if (in2_len == 0) { |
| 1780 | return in1_len; |
| 1781 | } |
| 1782 | |
| 1783 | // arr_larger and arr_smaller is one pointer for entries |
| 1784 | const char* arr_larger; |
| 1785 | const char* arr_smaller; |
| 1786 | // len_larger and len_smaller is one copy from lengths |
| 1787 | int len_larger; |
| 1788 | int len_smaller; |
| 1789 | |
| 1790 | if (in1_len < in2_len) { |
| 1791 | len_larger = in2_len; |
| 1792 | arr_larger = in2; |
| 1793 | |
| 1794 | len_smaller = in1_len; |
| 1795 | arr_smaller = in1; |
| 1796 | } else { |
| 1797 | len_larger = in1_len; |
| 1798 | arr_larger = in1; |
| 1799 | |
| 1800 | len_smaller = in2_len; |
| 1801 | arr_smaller = in2; |
| 1802 | } |
| 1803 | |
| 1804 | int* ptr = reinterpret_cast<int*>( |
| 1805 | gdv_fn_context_arena_malloc(context, (len_smaller + 1) * 2 * sizeof(int))); |
| 1806 | if (ptr == nullptr) { |
| 1807 | gdv_fn_context_set_error_msg(context, |
| 1808 | "LEVENSHTEIN: could not allocate working memory"); |
| 1809 | return 0; |
| 1810 | } |
| 1811 | |
| 1812 | // MEMORY ADDRESS MALLOC |
| 1813 | // v0 -> (0, ..., &ptr[in2_len]) |
| 1814 | // v1 -> (in2_len+1, ..., &ptr[in2_len * 2]) |
| 1815 | int* v0; |
| 1816 | int* v1; |
| 1817 | int* aux; |
| 1818 | v0 = &ptr[0]; |
| 1819 | v1 = &ptr[len_smaller + 1]; |
| 1820 |