From 9413c3a0d12d8f137fc1024d099eff429fba8ab9 Mon Sep 17 00:00:00 2001 From: Timothy Flynn Date: Tue, 3 Aug 2021 09:14:06 -0400 Subject: LibUnicode: Generate a map of code points to their Unicode table index The current strategy of searching for a code point within the generated table is slow for code points > U+0377 (the last code point whose index is the same value as the code point itself). For larger code points, we are doing a linear search through the table. Instead, generate a HashMap of each code point to its entry in the table for faster runtime lookups. This had the added benefit of being able to remove a fair amount of code from the generator. We no longer need to track that last contiguous code point (U+0377) nor each code point's index in the generated table. --- .../CodeGenerators/GenerateUnicodeData.cpp | 56 +++++++++------------- 1 file changed, 23 insertions(+), 33 deletions(-) (limited to 'Userland/Libraries/LibUnicode/CodeGenerators') diff --git a/Userland/Libraries/LibUnicode/CodeGenerators/GenerateUnicodeData.cpp b/Userland/Libraries/LibUnicode/CodeGenerators/GenerateUnicodeData.cpp index f18dec6518..a29aff8867 100644 --- a/Userland/Libraries/LibUnicode/CodeGenerators/GenerateUnicodeData.cpp +++ b/Userland/Libraries/LibUnicode/CodeGenerators/GenerateUnicodeData.cpp @@ -23,7 +23,6 @@ // 3400;;Lo;0;L;;;;;N;;;;; // 4DBF;;Lo;0;L;;;;;N;;;;; struct CodePointRange { - u32 index; u32 first; u32 last; }; @@ -55,7 +54,6 @@ struct Alias { // Field descriptions: https://www.unicode.org/reports/tr44/tr44-13.html#UnicodeData.txt // https://www.unicode.org/reports/tr44/#General_Category_Values struct CodePointData { - u32 index { 0 }; u32 code_point { 0 }; String name; String general_category; @@ -110,7 +108,7 @@ struct UnicodeData { // https://unicode.org/reports/tr18/#General_Category_Property PropList prop_list { { "Any"sv, {} }, - { "ASCII"sv, { { 0, 0, 0x7f } } }, + { "ASCII"sv, { { 0, 0x7f } } }, }; Vector prop_aliases; @@ -207,10 +205,10 @@ static void parse_prop_list(Core::File& file, PropList& prop_list) auto begin = AK::StringUtils::convert_to_uint_from_hex(segments[0]).value(); auto end = AK::StringUtils::convert_to_uint_from_hex(segments[1]).value(); - code_points.append({ 0, begin, end }); + code_points.append({ begin, end }); } else { auto code_point = AK::StringUtils::convert_to_uint_from_hex(code_point_range).value(); - code_points.append({ 0, code_point, code_point }); + code_points.append({ code_point, code_point }); } } } @@ -296,10 +294,6 @@ static void parse_value_alias_list(Core::File& file, StringView desired_category static void parse_unicode_data(Core::File& file, UnicodeData& unicode_data) { Optional code_point_range_start; - Optional code_point_range_index; - - Optional last_contiguous_code_point; - u32 previous_code_point = 0; while (file.can_read_line()) { auto line = file.read_line(); @@ -310,7 +304,6 @@ static void parse_unicode_data(Core::File& file, UnicodeData& unicode_data) VERIFY(segments.size() == 15); CodePointData data {}; - data.index = static_cast(unicode_data.code_point_data.size()); data.code_point = AK::StringUtils::convert_to_uint_from_hex(segments[0]).value(); data.name = move(segments[1]); data.general_category = move(segments[2]); @@ -328,23 +321,17 @@ static void parse_unicode_data(Core::File& file, UnicodeData& unicode_data) data.simple_titlecase_mapping = AK::StringUtils::convert_to_uint_from_hex(segments[14]); if (data.name.starts_with("<"sv) && data.name.ends_with(", First>")) { - VERIFY(!code_point_range_start.has_value() && !code_point_range_index.has_value()); - + VERIFY(!code_point_range_start.has_value()); code_point_range_start = data.code_point; - code_point_range_index = data.index; data.name = data.name.substring(1, data.name.length() - 9); } else if (data.name.starts_with("<"sv) && data.name.ends_with(", Last>")) { - VERIFY(code_point_range_start.has_value() && code_point_range_index.has_value()); + VERIFY(code_point_range_start.has_value()); - unicode_data.code_point_ranges.append({ *code_point_range_index, *code_point_range_start, data.code_point }); + unicode_data.code_point_ranges.append({ *code_point_range_start, data.code_point }); data.name = data.name.substring(1, data.name.length() - 8); code_point_range_start.clear(); - code_point_range_index.clear(); - } else if ((data.code_point > 0) && (data.code_point - previous_code_point) != 1) { - if (!last_contiguous_code_point.has_value()) - last_contiguous_code_point = previous_code_point; } for (auto const& casing : unicode_data.special_casing) { @@ -381,11 +368,8 @@ static void parse_unicode_data(Core::File& file, UnicodeData& unicode_data) if (!unicode_data.general_categories.contains_slow(data.general_category)) unicode_data.general_categories.append(data.general_category); - previous_code_point = data.code_point; unicode_data.code_point_data.append(move(data)); } - - unicode_data.last_contiguous_code_point = *last_contiguous_code_point; } static void generate_unicode_data_header(UnicodeData& unicode_data) @@ -557,12 +541,11 @@ static void generate_unicode_data_implementation(UnicodeData unicode_data) generator.set("special_casing_size", String::number(unicode_data.special_casing.size())); generator.set("code_point_data_size", String::number(unicode_data.code_point_data.size())); - generator.set("last_contiguous_code_point", String::formatted("0x{:x}", unicode_data.last_contiguous_code_point)); generator.append(R"~~~( #include #include -#include +#include #include #include @@ -655,17 +638,27 @@ static constexpr Array s_unicode_data { {)~ generator.append(R"~~~( } }; +static HashMap const& ensure_code_point_map() +{ + static HashMap code_point_to_data_map; + code_point_to_data_map.ensure_capacity(s_unicode_data.size()); + + for (auto const& unicode_data : s_unicode_data) + code_point_to_data_map.set(unicode_data.code_point, &unicode_data); + + return code_point_to_data_map; +} + static Optional index_of_code_point_in_range(u32 code_point) {)~~~"); for (auto const& range : unicode_data.code_point_ranges) { - generator.set("index", String::formatted("{}", range.index)); generator.set("first", String::formatted("{:#x}", range.first)); generator.set("last", String::formatted("{:#x}", range.last)); generator.append(R"~~~( if ((code_point > @first@) && (code_point < @last@)) - return @index@;)~~~"); + return @first@;)~~~"); } generator.append(R"~~~( @@ -676,22 +669,19 @@ namespace Detail { Optional unicode_data_for_code_point(u32 code_point) { + static auto const& code_point_to_data_map = ensure_code_point_map(); VERIFY(is_unicode(code_point)); - if (code_point <= @last_contiguous_code_point@) - return s_unicode_data[code_point]; + if (auto data = code_point_to_data_map.get(code_point); data.has_value()) + return *(data.value()); if (auto index = index_of_code_point_in_range(code_point); index.has_value()) { - auto data_for_range = s_unicode_data[*index]; + auto data_for_range = *(code_point_to_data_map.get(*index).value()); data_for_range.simple_uppercase_mapping = code_point; data_for_range.simple_lowercase_mapping = code_point; return data_for_range; } - auto it = AK::find_if(s_unicode_data.begin(), s_unicode_data.end(), [code_point](auto const& data) { return data.code_point == code_point; }); - if (it != s_unicode_data.end()) - return *it; - return {}; } -- cgit v1.2.3