Use radix tree for character encoding conversions.

Heikki Linnakangas <heikki.linnakangas@iki.fi>

Commit: aeed17d00037950a16cc5ebad5b5592e5fa1ad0f
Author: Heikki Linnakangas <heikki.linnakangas@iki.fi>
Date: 2017-03-13T18:46:39Z
Releases: 10.0
Use radix tree for character encoding conversions.

Replace the mapping tables used to convert between UTF-8 and other
character encodings with new radix tree-based maps. Looking up an entry in
a radix tree is much faster than a binary search in the old maps. As a
bonus, the radix tree representation is also more compact, making the
binaries slightly smaller.

The "combined" maps work the same as before, with binary search. They are
much smaller than the main tables, so it doesn't matter so much. However,
the "combined" maps are now stored in the same .map files as the main
tables. This seems more clear, since they're always used together, and
generated from the same source files.

Patch by Kyotaro Horiguchi, with lot of hacking by me at various stages.
Reviewed by Michael Paquier and Daniel Gustafsson.

Discussion: https://www.postgresql.org/message-id/20170306.171609.204324917.horiguchi.kyotaro%40lab.ntt.co.jp

Files

PathChange+/−
src/backend/utils/mb/conv.c modified +173 −78
src/backend/utils/mb/conversion_procs/utf8_and_big5/utf8_and_big5.c modified +2 −2
src/backend/utils/mb/conversion_procs/utf8_and_cyrillic/utf8_and_cyrillic.c modified +4 −4
src/backend/utils/mb/conversion_procs/utf8_and_euc2004/utf8_and_euc2004.c modified +2 −4
src/backend/utils/mb/conversion_procs/utf8_and_euc_cn/utf8_and_euc_cn.c modified +2 −2
src/backend/utils/mb/conversion_procs/utf8_and_euc_jp/utf8_and_euc_jp.c modified +2 −2
src/backend/utils/mb/conversion_procs/utf8_and_euc_kr/utf8_and_euc_kr.c modified +2 −2
src/backend/utils/mb/conversion_procs/utf8_and_euc_tw/utf8_and_euc_tw.c modified +2 −2
src/backend/utils/mb/conversion_procs/utf8_and_gb18030/utf8_and_gb18030.c modified +2 −2
src/backend/utils/mb/conversion_procs/utf8_and_gbk/utf8_and_gbk.c modified +2 −2
src/backend/utils/mb/conversion_procs/utf8_and_iso8859/utf8_and_iso8859.c modified +30 −45
src/backend/utils/mb/conversion_procs/utf8_and_johab/utf8_and_johab.c modified +2 −2
src/backend/utils/mb/conversion_procs/utf8_and_sjis2004/utf8_and_sjis2004.c modified +2 −4
src/backend/utils/mb/conversion_procs/utf8_and_sjis/utf8_and_sjis.c modified +2 −2
src/backend/utils/mb/conversion_procs/utf8_and_uhc/utf8_and_uhc.c modified +2 −2
src/backend/utils/mb/conversion_procs/utf8_and_win/utf8_and_win.c modified +15 −39
src/backend/utils/mb/Unicode/big5_to_utf8.map modified +4603 −13718
src/backend/utils/mb/Unicode/convutils.pm modified +656 −150
src/backend/utils/mb/Unicode/euc_cn_to_utf8.map modified +2277 −7446
src/backend/utils/mb/Unicode/euc_jis_2004_to_utf8_combined.map deleted +0 −29
src/backend/utils/mb/Unicode/euc_jis_2004_to_utf8.map modified +3440 −11304
src/backend/utils/mb/Unicode/euc_jp_to_utf8.map modified +4139 −13198
src/backend/utils/mb/Unicode/euc_kr_to_utf8.map modified +2495 −8228
src/backend/utils/mb/Unicode/euc_tw_to_utf8.map modified +7831 −23576
src/backend/utils/mb/Unicode/gb18030_to_utf8.map modified +11148 −30734
src/backend/utils/mb/Unicode/gbk_to_utf8.map modified +6551 −21793
src/backend/utils/mb/Unicode/iso8859_10_to_utf8.map modified +108 −129
src/backend/utils/mb/Unicode/iso8859_13_to_utf8.map modified +108 −129
src/backend/utils/mb/Unicode/iso8859_14_to_utf8.map modified +108 −129
src/backend/utils/mb/Unicode/iso8859_15_to_utf8.map modified +108 −129
src/backend/utils/mb/Unicode/iso8859_16_to_utf8.map modified +108 −129
src/backend/utils/mb/Unicode/iso8859_2_to_utf8.map modified +76 −129
src/backend/utils/mb/Unicode/iso8859_3_to_utf8.map modified +76 −122
src/backend/utils/mb/Unicode/iso8859_4_to_utf8.map modified +76 −129
src/backend/utils/mb/Unicode/iso8859_5_to_utf8.map modified +108 −129
src/backend/utils/mb/Unicode/iso8859_6_to_utf8.map modified +74 −84
src/backend/utils/mb/Unicode/iso8859_7_to_utf8.map modified +108 −126
src/backend/utils/mb/Unicode/iso8859_8_to_utf8.map modified +108 −93
src/backend/utils/mb/Unicode/iso8859_9_to_utf8.map modified +76 −129
src/backend/utils/mb/Unicode/johab_to_utf8.map modified +6277 −17050
src/backend/utils/mb/Unicode/koi8r_to_utf8.map modified +108 −129
src/backend/utils/mb/Unicode/koi8u_to_utf8.map modified +108 −129
src/backend/utils/mb/Unicode/Makefile modified +4 −6
src/backend/utils/mb/Unicode/shift_jis_2004_to_utf8_combined.map deleted +0 −29
src/backend/utils/mb/Unicode/shift_jis_2004_to_utf8.map modified +3231 −11272
src/backend/utils/mb/Unicode/sjis_to_utf8.map modified +2414 −7788
src/backend/utils/mb/Unicode/UCS_to_BIG5.pl modified +8 −4
src/backend/utils/mb/Unicode/UCS_to_EUC_CN.pl modified +7 −3
src/backend/utils/mb/Unicode/UCS_to_EUC_JIS_2004.pl modified +16 −6
src/backend/utils/mb/Unicode/UCS_to_EUC_JP.pl modified +96 −93
src/backend/utils/mb/Unicode/UCS_to_EUC_KR.pl modified +8 −6
src/backend/utils/mb/Unicode/UCS_to_EUC_TW.pl modified +7 −3
src/backend/utils/mb/Unicode/UCS_to_GB18030.pl modified +7 −3
src/backend/utils/mb/Unicode/UCS_to_JOHAB.pl modified +7 −5
src/backend/utils/mb/Unicode/UCS_to_most.pl modified +4 −2
src/backend/utils/mb/Unicode/UCS_to_SHIFT_JIS_2004.pl modified +13 −8
src/backend/utils/mb/Unicode/UCS_to_SJIS.pl modified +17 −15
src/backend/utils/mb/Unicode/UCS_to_UHC.pl modified +8 −4
src/backend/utils/mb/Unicode/uhc_to_utf8.map modified +6550 −17238
src/backend/utils/mb/Unicode/utf8_to_big5.map modified +4097 −13712
src/backend/utils/mb/Unicode/utf8_to_euc_cn.map modified +4041 −7446
src/backend/utils/mb/Unicode/utf8_to_euc_jis_2004_combined.map deleted +0 −29
src/backend/utils/mb/Unicode/utf8_to_euc_jis_2004.map modified +12564 −11304
src/backend/utils/mb/Unicode/utf8_to_euc_jp.map modified +7138 −13176
src/backend/utils/mb/Unicode/utf8_to_euc_kr.map modified +6389 −8228
src/backend/utils/mb/Unicode/utf8_to_euc_tw.map modified +6862 −17712
src/backend/utils/mb/Unicode/utf8_to_gb18030.map modified +9558 −30734
src/backend/utils/mb/Unicode/utf8_to_gbk.map modified +4268 −21793
src/backend/utils/mb/Unicode/utf8_to_iso8859_10.map modified +111 −129
src/backend/utils/mb/Unicode/utf8_to_iso8859_13.map modified +110 −129
src/backend/utils/mb/Unicode/utf8_to_iso8859_14.map modified +143 −129
src/backend/utils/mb/Unicode/utf8_to_iso8859_15.map modified +98 −129
src/backend/utils/mb/Unicode/utf8_to_iso8859_16.map modified +128 −129
src/backend/utils/mb/Unicode/utf8_to_iso8859_2.map modified +111 −129
src/backend/utils/mb/Unicode/utf8_to_iso8859_3.map modified +110 −122
src/backend/utils/mb/Unicode/utf8_to_iso8859_4.map modified +111 −129
src/backend/utils/mb/Unicode/utf8_to_iso8859_5.map modified +100 −129
src/backend/utils/mb/Unicode/utf8_to_iso8859_6.map modified +87 −84
src/backend/utils/mb/Unicode/utf8_to_iso8859_7.map modified +122 −126
src/backend/utils/mb/Unicode/utf8_to_iso8859_8.map modified +101 −93
src/backend/utils/mb/Unicode/utf8_to_iso8859_9.map modified +97 −129
src/backend/utils/mb/Unicode/utf8_to_johab.map modified +6330 −17050
src/backend/utils/mb/Unicode/utf8_to_koi8r.map modified +172 −129
src/backend/utils/mb/Unicode/utf8_to_koi8u.map modified +183 −129
src/backend/utils/mb/Unicode/utf8_to_shift_jis_2004_combined.map deleted +0 −29
src/backend/utils/mb/Unicode/utf8_to_shift_jis_2004.map modified +7682 −11272
src/backend/utils/mb/Unicode/utf8_to_sjis.map modified +4250 −7398
src/backend/utils/mb/Unicode/utf8_to_uhc.map modified +6374 −17238
src/backend/utils/mb/Unicode/utf8_to_win1250.map modified +142 −124
src/backend/utils/mb/Unicode/utf8_to_win1251.map modified +131 −128
src/backend/utils/mb/Unicode/utf8_to_win1252.map modified +143 −124
src/backend/utils/mb/Unicode/utf8_to_win1253.map modified +132 −112
src/backend/utils/mb/Unicode/utf8_to_win1254.map modified +154 −122
src/backend/utils/mb/Unicode/utf8_to_win1255.map modified +154 −106
src/backend/utils/mb/Unicode/utf8_to_win1256.map modified +191 −129
src/backend/utils/mb/Unicode/utf8_to_win1257.map modified +142 −117
src/backend/utils/mb/Unicode/utf8_to_win1258.map modified +164 −120
src/backend/utils/mb/Unicode/utf8_to_win866.map modified +151 −129
src/backend/utils/mb/Unicode/utf8_to_win874.map modified +127 −98
src/backend/utils/mb/Unicode/win1250_to_utf8.map modified +108 −124
src/backend/utils/mb/Unicode/win1251_to_utf8.map modified +108 −128
src/backend/utils/mb/Unicode/win1252_to_utf8.map modified +108 −124
src/backend/utils/mb/Unicode/win1253_to_utf8.map modified +108 −112
src/backend/utils/mb/Unicode/win1254_to_utf8.map modified +108 −122
src/backend/utils/mb/Unicode/win1255_to_utf8.map modified +108 −106
src/backend/utils/mb/Unicode/win1256_to_utf8.map modified +108 −129
src/backend/utils/mb/Unicode/win1257_to_utf8.map modified +108 −117
src/backend/utils/mb/Unicode/win1258_to_utf8.map modified +108 −120
src/backend/utils/mb/Unicode/win866_to_utf8.map modified +108 −129
src/backend/utils/mb/Unicode/win874_to_utf8.map modified +106 −98
src/include/mb/pg_wchar.h modified +70 −14

Discussion