From 9d2fe9d9af19ab94ff3feb1e7b9ffd83fa6927ff Mon Sep 17 00:00:00 2001 From: Patrik Nyblom Date: Fri, 23 Apr 2010 18:53:51 +0200 Subject: Add binary:longest_common_prefix/longest_common_suffix Add allcoator parameter to erts_get_aligned_binary_bytes_extra. Add testcases for the functions above. Add reference implementation for the functions above. --- lib/stdlib/test/binary_module_SUITE.erl | 82 +++++++++++++++++++++++++++++++++ lib/stdlib/test/binref.erl | 74 ++++++++++++++++++++++++++++- 2 files changed, 155 insertions(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/stdlib/test/binary_module_SUITE.erl b/lib/stdlib/test/binary_module_SUITE.erl index 24545f296a..5ab9bb7b25 100644 --- a/lib/stdlib/test/binary_module_SUITE.erl +++ b/lib/stdlib/test/binary_module_SUITE.erl @@ -179,6 +179,88 @@ do_interesting(Module) -> [<<4,5>>,<<7>>,<<8>>],<<>>, [global,{scope,{0,5}}, {insert_replaced,1}])), + ?line 2 = Module:longest_common_prefix([<<1,2,4>>,<<1,2,3>>]), + ?line 2 = Module:longest_common_prefix([<<1,2,4>>,<<1,2>>]), + ?line 1 = Module:longest_common_prefix([<<1,2,4>>,<<1>>]), + ?line 0 = Module:longest_common_prefix([<<1,2,4>>,<<>>]), + ?line 1 = Module:longest_common_prefix([<<1,2,4>>,<<1,2,3>>,<<1,3,3>>]), + ?line 1 = Module:longest_common_prefix([<<1,2,4>>,<<1,2,3>>,<<1,3,3>>,<<1,2,4>>]), + ?line 1251 = Module:longest_common_prefix([<<0:10000,1,2,4>>, + <<0:10000,1,2,3>>, + <<0:10000,1,3,3>>, + <<0:10000,1,2,4>>]), + ?line 12501 = Module:longest_common_prefix([<<0:100000,1,2,4>>, + <<0:100000,1,2,3>>, + <<0:100000,1,3,3>>, + <<0:100000,1,2,4>>]), + ?line 1251 = Module:longest_common_prefix( + [make_unaligned(<<0:10000,1,2,4>>), + <<0:10000,1,2,3>>, + make_unaligned(<<0:10000,1,3,3>>), + <<0:10000,1,2,4>>]), + ?line 12501 = Module:longest_common_prefix( + [<<0:100000,1,2,4>>, + make_unaligned(<<0:100000,1,2,3>>), + <<0:100000,1,3,3>>, + make_unaligned(<<0:100000,1,2,4>>)]), + ?line 1250001 = Module:longest_common_prefix([<<0:10000000,1,2,4>>, + <<0:10000000,1,2,3>>, + <<0:10000000,1,3,3>>, + <<0:10000000,1,2,4>>]), + if % Too cruel for the reference implementation + Module =:= binary -> + ?line 125000001 = Module:longest_common_prefix( + [<<0:1000000000,1,2,4>>, + <<0:1000000000,1,2,3>>, + <<0:1000000000,1,3,3>>, + <<0:1000000000,1,2,4>>]); + true -> + ok + end, + ?line 1 = Module:longest_common_suffix([<<0:1000000000,1,2,4,5>>, + <<0:1000000000,1,2,3,5>>, + <<0:1000000000,1,3,3,5>>, + <<0:1000000000,1,2,4,5>>]), + ?line 1 = Module:longest_common_suffix([<<1,2,4,5>>, + <<0:1000000000,1,2,3,5>>, + <<0:1000000000,1,3,3,5>>, + <<0:1000000000,1,2,4,5>>]), + ?line 1 = Module:longest_common_suffix([<<1,2,4,5,5>>,<<5,5>>, + <<0:1000000000,1,3,3,5,5>>, + <<0:1000000000,1,2,4,5>>]), + ?line 0 = Module:longest_common_suffix([<<1,2,4,5,5>>,<<5,5>>, + <<0:1000000000,1,3,3,5,5>>, + <<0:1000000000,1,2,4>>]), + ?line 2 = Module:longest_common_suffix([<<1,2,4,5,5>>,<<5,5>>, + <<0:1000000000,1,3,3,5,5>>, + <<0:1000000000,1,2,4,5,5>>]), + ?line 1 = Module:longest_common_suffix([<<1,2,4,5,5>>,<<5>>, + <<0:1000000000,1,3,3,5,5>>, + <<0:1000000000,1,2,4,5,5>>]), + ?line 0 = Module:longest_common_suffix([<<1,2,4,5,5>>,<<>>, + <<0:1000000000,1,3,3,5,5>>, + <<0:1000000000,1,2,4,5,5>>]), + ?line 0 = Module:longest_common_suffix([<<>>,<<0:1000000000,1,3,3,5,5>>, + <<0:1000000000,1,2,4,5,5>>]), + ?line 0 = Module:longest_common_suffix([<<>>,<<0:1000000000,1,3,3,5,5>>, + <<0:1000000000,1,2,4,5,5>>]), + ?line 2 = Module:longest_common_suffix([<<5,5>>,<<0:1000000000,1,3,3,5,5>>, + <<0:1000000000,1,2,4,5,5>>]), + ?line 2 = Module:longest_common_suffix([<<5,5>>,<<5,5>>,<<4,5,5>>]), + ?line 2 = Module:longest_common_suffix([<<5,5>>,<<5,5>>,<<5,5>>]), + ?line 3 = Module:longest_common_suffix([<<4,5,5>>,<<4,5,5>>,<<4,5,5>>]), + ?line 0 = Module:longest_common_suffix([<<>>]), + ?line badarg = ?MASK_ERROR(Module:longest_common_suffix([])), + ?line badarg = ?MASK_ERROR(Module:longest_common_suffix([apa])), + ?line badarg = ?MASK_ERROR(Module:longest_common_suffix([[<<>>]])), + ?line badarg = ?MASK_ERROR(Module:longest_common_suffix([[<<0>>, + <<1:9>>]])), + ?line 0 = Module:longest_common_prefix([<<>>]), + ?line badarg = ?MASK_ERROR(Module:longest_common_prefix([])), + ?line badarg = ?MASK_ERROR(Module:longest_common_prefix([apa])), + ?line badarg = ?MASK_ERROR(Module:longest_common_prefix([[<<>>]])), + ?line badarg = ?MASK_ERROR(Module:longest_common_prefix([[<<0>>, + <<1:9>>]])), ok. parts(doc) -> diff --git a/lib/stdlib/test/binref.erl b/lib/stdlib/test/binref.erl index 484112428c..e98b1b2bc8 100644 --- a/lib/stdlib/test/binref.erl +++ b/lib/stdlib/test/binref.erl @@ -3,7 +3,8 @@ -export([compile_pattern/1,match/2,match/3,matches/2,matches/3, split/2,split/3,replace/3,replace/4,first/1,last/1,at/2, part/2,part/3,copy/1,copy/2,encode_unsigned/1,encode_unsigned/2, - decode_unsigned/1,decode_unsigned/2,referenced_byte_size/1]). + decode_unsigned/1,decode_unsigned/2,referenced_byte_size/1, + longest_common_prefix/1,longest_common_suffix/1 ]). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -318,6 +319,77 @@ at(Subject,X) -> end. +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% longest_common_prefix +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +longest_common_prefix(LB) -> + try + true = is_list(LB) and (length(LB) > 0), % Make badarg instead of function clause + do_longest_common_prefix(LB,0) + catch + _:_ -> + erlang:error(badarg) + end. + +do_longest_common_prefix(LB,X) -> + case do_lcp(LB,X,no) of + true -> + do_longest_common_prefix(LB,X+1); + false -> + X + end. +do_lcp([],_,_) -> + true; +do_lcp([Bin|_],X,_) when byte_size(Bin) =< X -> + false; +do_lcp([Bin|T],X,no) -> + Ch = at(Bin,X), + do_lcp(T,X,Ch); +do_lcp([Bin|T],X,Ch) -> + Ch2 = at(Bin,X), + if + Ch =:= Ch2 -> + do_lcp(T,X,Ch); + true -> + false + end. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% longest_common_suffix +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +longest_common_suffix(LB) -> + try + true = is_list(LB) and (length(LB) > 0), % Make badarg instead of function clause + do_longest_common_suffix(LB,0) + catch + _:_ -> + erlang:error(badarg) + end. + +do_longest_common_suffix(LB,X) -> + case do_lcs(LB,X,no) of + true -> + do_longest_common_suffix(LB,X+1); + false -> + X + end. +do_lcs([],_,_) -> + true; +do_lcs([Bin|_],X,_) when byte_size(Bin) =< X -> + false; +do_lcs([Bin|T],X,no) -> + Ch = at(Bin,byte_size(Bin) - 1 - X), + do_lcs(T,X,Ch); +do_lcs([Bin|T],X,Ch) -> + Ch2 = at(Bin,byte_size(Bin) - 1 - X), + if + Ch =:= Ch2 -> + do_lcs(T,X,Ch); + true -> + false + end. + + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% part %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -- cgit v1.2.3