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. --- erts/emulator/beam/atom.names | 2 + erts/emulator/beam/bif.tab | 4 +- erts/emulator/beam/binary.c | 4 +- erts/emulator/beam/erl_alloc.types | 1 + erts/emulator/beam/erl_bif_binary.c | 317 ++++++++++++++++++++++++++++++++ erts/emulator/beam/erl_binary.h | 15 +- erts/emulator/beam/erl_nif.c | 4 +- lib/stdlib/test/binary_module_SUITE.erl | 82 +++++++++ lib/stdlib/test/binref.erl | 74 +++++++- 9 files changed, 492 insertions(+), 11 deletions(-) diff --git a/erts/emulator/beam/atom.names b/erts/emulator/beam/atom.names index 06ff0e11a4..386b040a27 100644 --- a/erts/emulator/beam/atom.names +++ b/erts/emulator/beam/atom.names @@ -101,6 +101,8 @@ atom band atom big atom bif_return_trap atom binary +atom binary_longest_prefix_trap +atom binary_longest_suffix_trap atom binary_match_trap atom binary_matches_trap atom block diff --git a/erts/emulator/beam/bif.tab b/erts/emulator/beam/bif.tab index 85674664e4..536f9ac5c8 100644 --- a/erts/emulator/beam/bif.tab +++ b/erts/emulator/beam/bif.tab @@ -765,8 +765,8 @@ bif binary:match/2 bif binary:match/3 bif binary:matches/2 bif binary:matches/3 -# bif binary:longest_common_prefix/1 -# bif binary:longest_common_suffix/1 +bif binary:longest_common_prefix/1 +bif binary:longest_common_suffix/1 # bif binary:first/1 # bif binary:last/1 # bif binary:at/2 diff --git a/erts/emulator/beam/binary.c b/erts/emulator/beam/binary.c index 7ca3eb686d..9c4076c8ff 100644 --- a/erts/emulator/beam/binary.c +++ b/erts/emulator/beam/binary.c @@ -180,7 +180,7 @@ erts_realloc_binary(Eterm bin, size_t size) } byte* -erts_get_aligned_binary_bytes_extra(Eterm bin, byte** base_ptr, unsigned extra) +erts_get_aligned_binary_bytes_extra(Eterm bin, byte** base_ptr, ErtsAlcType_t allocator, unsigned extra) { byte* bytes; Eterm* real_bin; @@ -208,7 +208,7 @@ erts_get_aligned_binary_bytes_extra(Eterm bin, byte** base_ptr, unsigned extra) bytes = (byte *)(&(((ErlHeapBin *) real_bin)->data)) + offs; } if (bit_offs) { - byte* buf = (byte *) erts_alloc(ERTS_ALC_T_TMP, byte_size + extra); + byte* buf = (byte *) erts_alloc(allocator, byte_size + extra); *base_ptr = buf; buf += extra; erts_copy_bits(bytes, bit_offs, 1, buf, 0, 1, byte_size*8); diff --git a/erts/emulator/beam/erl_alloc.types b/erts/emulator/beam/erl_alloc.types index 5d2872a4e3..6f88bbe5b8 100644 --- a/erts/emulator/beam/erl_alloc.types +++ b/erts/emulator/beam/erl_alloc.types @@ -232,6 +232,7 @@ type RE_SUBJECT SHORT_LIVED SYSTEM re_subject type RE_HEAP STANDARD SYSTEM re_heap type RE_STACK SHORT_LIVED SYSTEM re_stack type UNICODE_BUFFER SHORT_LIVED SYSTEM unicode_buffer +type BINARY_BUFFER SHORT_LIVED SYSTEM binary_buffer type PRE_ALLOC_DATA LONG_LIVED SYSTEM pre_alloc_data type DRV_THR_OPTS DRIVER SYSTEM driver_thread_opts type DRV_TID DRIVER SYSTEM driver_tid diff --git a/erts/emulator/beam/erl_bif_binary.c b/erts/emulator/beam/erl_bif_binary.c index a635280ac1..5bde065049 100644 --- a/erts/emulator/beam/erl_bif_binary.c +++ b/erts/emulator/beam/erl_bif_binary.c @@ -55,6 +55,10 @@ static Export binary_match_trap_export; static BIF_RETTYPE binary_match_trap(BIF_ALIST_3); static Export binary_matches_trap_export; static BIF_RETTYPE binary_matches_trap(BIF_ALIST_3); +static Export binary_longest_prefix_trap_export; +static BIF_RETTYPE binary_longest_prefix_trap(BIF_ALIST_3); +static Export binary_longest_suffix_trap_export; +static BIF_RETTYPE binary_longest_suffix_trap(BIF_ALIST_3); static Uint max_loop_limit; @@ -76,6 +80,22 @@ void erts_init_bif_binary(void) binary_matches_trap_export.code[3] = (BeamInstr) em_apply_bif; binary_matches_trap_export.code[4] = (BeamInstr) &binary_matches_trap; + sys_memset((void *) &binary_longest_prefix_trap_export, 0, sizeof(Export)); + binary_longest_prefix_trap_export.address = &binary_longest_prefix_trap_export.code[3]; + binary_longest_prefix_trap_export.code[0] = am_erlang; + binary_longest_prefix_trap_export.code[1] = am_binary_longest_prefix_trap; + binary_longest_prefix_trap_export.code[2] = 3; + binary_longest_prefix_trap_export.code[3] = (BeamInstr) em_apply_bif; + binary_longest_prefix_trap_export.code[4] = (BeamInstr) &binary_longest_prefix_trap; + + sys_memset((void *) &binary_longest_suffix_trap_export, 0, sizeof(Export)); + binary_longest_suffix_trap_export.address = &binary_longest_suffix_trap_export.code[3]; + binary_longest_suffix_trap_export.code[0] = am_erlang; + binary_longest_suffix_trap_export.code[1] = am_binary_longest_suffix_trap; + binary_longest_suffix_trap_export.code[2] = 3; + binary_longest_suffix_trap_export.code[3] = (BeamInstr) em_apply_bif; + binary_longest_suffix_trap_export.code[4] = (BeamInstr) &binary_longest_suffix_trap; + max_loop_limit = 0; return; } @@ -1549,6 +1569,303 @@ BIF_RETTYPE binary_part_2(BIF_ALIST_2) BIF_ERROR(BIF_P,BADARG); } +typedef struct { + int type; /* CL_TYPE_XXX */ + byte *temp_alloc; /* Used for erts_get/free_aligned, i.e. CL_TYPE_ALIGNED */ + unsigned char *buff; /* Used for all types, malloced if CL_TYPE_HEAP */ + Uint bufflen; /* The length (in bytes) of buffer */ +} CommonData; + +#define COMMON_LOOP_FACTOR 10 + +#define DIRECTION_PREFIX 0 +#define DIRECTION_SUFFIX 1 + +#define CL_OK 0 +#define CL_RESTART 1 + +/* The type field in the above structure */ +#define CL_TYPE_EMPTY 0 /* End of array */ +#define CL_TYPE_HEAP 1 +#define CL_TYPE_ALIGNED 2 +#define CL_TYPE_COMMON 3 /* emacsulated */ +#define CL_TYPE_HEAP_NOALLOC 4 /* Will need allocating when trapping */ + + +static int do_search_forward(CommonData *cd, Uint *posp, Uint *redsp) +{ + Uint pos = *posp; + Sint reds = (Sint) *redsp; + int i; + unsigned char current = 0; + + for(;;) { + for(i = 0; cd[i].type != CL_TYPE_EMPTY; ++i) { + if (pos >= cd[i].bufflen) { + *posp = pos; + if (reds > 0) { + *redsp = (Uint) reds; + } else { + *redsp = 0; + } + return CL_OK; + } + if (i == 0) { + current = cd[i].buff[pos]; + } else { + if (cd[i].buff[pos] != current) { + *posp = pos; + if (reds > 0) { + *redsp = (Uint) reds; + } else { + *redsp = 0; + } + return CL_OK; + } + } + --reds; + } + ++pos; + if (reds <= 0) { + *posp = pos; + *redsp = 0; + return CL_RESTART; + } + } +} +static int do_search_backward(CommonData *cd, Uint *posp, Uint *redsp) +{ + Uint pos = *posp; + Sint reds = (Sint) *redsp; + int i; + unsigned char current = 0; + + for(;;) { + for(i = 0; cd[i].type != CL_TYPE_EMPTY; ++i) { + if (pos >= cd[i].bufflen) { + *posp = pos; + if (reds > 0) { + *redsp = (Uint) reds; + } else { + *redsp = 0; + } + return CL_OK; + } + if (i == 0) { + current = cd[i].buff[cd[i].bufflen - 1 - pos]; + } else { + if (cd[i].buff[cd[i].bufflen - 1 - pos] != current) { + *posp = pos; + if (reds > 0) { + *redsp = (Uint) reds; + } else { + *redsp = 0; + } + return CL_OK; + } + } + --reds; + } + ++pos; + if (reds <= 0) { + *posp = pos; + *redsp = 0; + return CL_RESTART; + } + } +} + +static void cleanup_common_data(Binary *bp) +{ + int i; + CommonData *cd; + cd = (CommonData *) ERTS_MAGIC_BIN_DATA(bp); + for (i=0;cd[i].type != CL_TYPE_EMPTY;++i) { + switch (cd[i].type) { + case CL_TYPE_HEAP: + erts_free(ERTS_ALC_T_BINARY_BUFFER,cd[i].buff); + break; + case CL_TYPE_ALIGNED: + erts_free_aligned_binary_bytes_extra(cd[i].temp_alloc, ERTS_ALC_T_BINARY_BUFFER); + break; + default: + break; + } + } + return; +} + +static BIF_RETTYPE do_longest_common(Process *p, Eterm list, int direction) +{ + Eterm l = list; + int n = 0; + Binary *mb; + CommonData *cd; + int i = 0; + Uint reds = get_reds(p, COMMON_LOOP_FACTOR); + Uint save_reds = reds; + int res; + Export *trapper; + Uint pos; + Eterm epos; + Eterm *hp; + Eterm bin_term; + Eterm b; + + /* First just count the number of binaries */ + while (is_list(l)) { + b = CAR(list_val(l)); + if (!is_binary(b)) { + goto badarg; + } + ++n; + l = CDR(list_val(l)); + } + if (l != NIL || n == 0) { + goto badarg; + } + + /* OK, now create a buffer of the right size, we can do a magic binary right away, + thats not to costly. */ + mb = erts_create_magic_binary((n+1)*sizeof(CommonData),cleanup_common_data); + cd = (CommonData *) ERTS_MAGIC_BIN_DATA(mb); + l = list; + while (is_list(l)) { + Uint bitoffs; + Uint bitsize; + Uint offset; + Eterm real_bin; + ProcBin* pb; + + cd[i].type = CL_TYPE_EMPTY; + b = CAR(list_val(l)); + ERTS_GET_REAL_BIN(b, real_bin, offset, bitoffs, bitsize); + if (bitsize != 0) { + erts_bin_free(mb); + goto badarg; + } + cd[i].bufflen = binary_size(b); + cd[i].temp_alloc = NULL; + if (*(binary_val(real_bin)) == HEADER_PROC_BIN) { + pb = (ProcBin *) binary_val(real_bin); + if (pb->flags) { + erts_emasculate_writable_binary(pb); + } + cd[i].buff = erts_get_aligned_binary_bytes_extra(b, &(cd[i].temp_alloc), + ERTS_ALC_T_BINARY_BUFFER,0); + cd[i].type = (cd[i].temp_alloc != NULL) ? CL_TYPE_ALIGNED : CL_TYPE_COMMON; + } else { /* Heap binary */ + cd[i].buff = erts_get_aligned_binary_bytes_extra(b, &(cd[i].temp_alloc), + ERTS_ALC_T_BINARY_BUFFER,0); + /* CL_TYPE_HEAP_NOALLOC means you have to copy if trapping */ + cd[i].type = (cd[i].temp_alloc != NULL) ? CL_TYPE_ALIGNED : CL_TYPE_HEAP_NOALLOC; + } + ++i; + l = CDR(list_val(l)); + } + cd[i].type = CL_TYPE_EMPTY; +#if defined(DEBUG) || defined(VALGRIND) + cd[i].temp_alloc = NULL; + cd[i].buff = NULL; + cd[i].bufflen = 0; +#endif + + pos = 0; + if (direction == DIRECTION_PREFIX) { + trapper = &binary_longest_prefix_trap_export; + res = do_search_forward(cd,&pos,&reds); + } else { + ASSERT(direction == DIRECTION_SUFFIX); + trapper = &binary_longest_suffix_trap_export; + res = do_search_backward(cd,&pos,&reds); + } + epos = erts_make_integer(pos,p); + if (res == CL_OK) { + erts_bin_free(mb); + BUMP_REDS(p, (save_reds - reds) / COMMON_LOOP_FACTOR); + BIF_RET(epos); + } else { + ASSERT(res == CL_RESTART); + /* Copy all heap binaries that are not already copied (aligned) */ + for(i = 0; i < n; ++i) { + if (cd[i].type == CL_TYPE_HEAP_NOALLOC) { + unsigned char *tmp = cd[i].buff; + cd[i].buff = erts_alloc(ERTS_ALC_T_BINARY_BUFFER, cd[i].bufflen); + memcpy(cd[i].buff,tmp,cd[i].bufflen); + } + } + hp = HAlloc(p, PROC_BIN_SIZE); + bin_term = erts_mk_magic_binary_term(&hp, &MSO(p), mb); + BUMP_ALL_REDS(p); + BIF_TRAP3(trapper, p, bin_term, epos,list); + } + badarg: + BIF_ERROR(p,BADARG); +} + +static BIF_RETTYPE do_longest_common_trap(Process *p, Eterm bin_term, Eterm current_pos, + Eterm orig_list, int direction) +{ + Uint reds = get_reds(p, COMMON_LOOP_FACTOR); + Uint save_reds = reds; + Uint pos; + Binary *bin; + CommonData *cd; + int res; + Eterm epos; + Export *trapper; + +#ifdef DEBUG + int r; + r = term_to_Uint(current_pos, &pos); + ASSERT(r != 0); +#else + term_to_Uint(current_pos, &pos); +#endif + ASSERT(ERTS_TERM_IS_MAGIC_BINARY(bin_term)); + bin = ((ProcBin *) binary_val(bin_term))->val; + cd = (CommonData *) ERTS_MAGIC_BIN_DATA(bin); + if (direction == DIRECTION_PREFIX) { + trapper = &binary_longest_prefix_trap_export; + res = do_search_forward(cd,&pos,&reds); + } else { + ASSERT(direction == DIRECTION_SUFFIX); + trapper = &binary_longest_suffix_trap_export; + res = do_search_backward(cd,&pos,&reds); + } + epos = erts_make_integer(pos,p); + if (res == CL_OK) { + BUMP_REDS(p, (save_reds - reds) / COMMON_LOOP_FACTOR); + BIF_RET(epos); + } else { + ASSERT(res == CL_RESTART); + /* Copy all heap binaries that are not already copied (aligned) */ + BUMP_ALL_REDS(p); + BIF_TRAP3(&binary_longest_prefix_trap_export, p, bin_term, epos, orig_list); + } +} + +static BIF_RETTYPE binary_longest_prefix_trap(BIF_ALIST_3) +{ + return do_longest_common_trap(BIF_P,BIF_ARG_1,BIF_ARG_2,BIF_ARG_3,DIRECTION_PREFIX); +} + +static BIF_RETTYPE binary_longest_suffix_trap(BIF_ALIST_3) +{ + return do_longest_common_trap(BIF_P,BIF_ARG_1,BIF_ARG_2,BIF_ARG_3,DIRECTION_SUFFIX); +} + +BIF_RETTYPE binary_longest_common_prefix_1(BIF_ALIST_1) +{ + return do_longest_common(BIF_P,BIF_ARG_1,DIRECTION_PREFIX); +} + +BIF_RETTYPE binary_longest_common_suffix_1(BIF_ALIST_1) +{ + return do_longest_common(BIF_P,BIF_ARG_1,DIRECTION_SUFFIX); +} + + /* * Hard debug functions (dump) for the search structures diff --git a/erts/emulator/beam/erl_binary.h b/erts/emulator/beam/erl_binary.h index 5b0b3bcec2..74d7966ca0 100644 --- a/erts/emulator/beam/erl_binary.h +++ b/erts/emulator/beam/erl_binary.h @@ -150,7 +150,7 @@ do { \ void erts_init_binary(void); -byte* erts_get_aligned_binary_bytes_extra(Eterm, byte**, unsigned extra); +byte* erts_get_aligned_binary_bytes_extra(Eterm, byte**, ErtsAlcType_t, unsigned extra); #if defined(__i386__) || !defined(__GNUC__) /* @@ -168,6 +168,7 @@ byte* erts_get_aligned_binary_bytes_extra(Eterm, byte**, unsigned extra); ERTS_GLB_INLINE byte* erts_get_aligned_binary_bytes(Eterm bin, byte** base_ptr); ERTS_GLB_INLINE void erts_free_aligned_binary_bytes(byte* buf); +ERTS_GLB_INLINE void erts_free_aligned_binary_bytes_extra(byte* buf, ErtsAlcType_t); ERTS_GLB_INLINE Binary *erts_bin_drv_alloc_fnf(Uint size); ERTS_GLB_INLINE Binary *erts_bin_drv_alloc(Uint size); ERTS_GLB_INLINE Binary *erts_bin_nrml_alloc(Uint size); @@ -184,17 +185,23 @@ ERTS_GLB_INLINE Binary *erts_create_magic_binary(Uint size, ERTS_GLB_INLINE byte* erts_get_aligned_binary_bytes(Eterm bin, byte** base_ptr) { - return erts_get_aligned_binary_bytes_extra(bin, base_ptr, 0); + return erts_get_aligned_binary_bytes_extra(bin, base_ptr, ERTS_ALC_T_TMP, 0); } ERTS_GLB_INLINE void -erts_free_aligned_binary_bytes(byte* buf) +erts_free_aligned_binary_bytes_extra(byte* buf, ErtsAlcType_t allocator) { if (buf) { - erts_free(ERTS_ALC_T_TMP, (void *) buf); + erts_free(allocator, (void *) buf); } } +ERTS_GLB_INLINE void +erts_free_aligned_binary_bytes(byte* buf) +{ + erts_free_aligned_binary_bytes_extra(buf,ERTS_ALC_T_TMP); +} + /* Explicit extra bytes allocated to counter buggy drivers. ** These extra bytes where earlier (< R13B04) added by an alignment-bug ** in this code. Do we dare remove this in some major release (R14?) maybe? diff --git a/erts/emulator/beam/erl_nif.c b/erts/emulator/beam/erl_nif.c index 2790020117..cee4df72a2 100644 --- a/erts/emulator/beam/erl_nif.c +++ b/erts/emulator/beam/erl_nif.c @@ -250,7 +250,7 @@ int enif_is_ref(ErlNifEnv* env, ERL_NIF_TERM term) static void aligned_binary_dtor(struct enif_tmp_obj_t* obj) { - erts_free_aligned_binary_bytes((byte*)obj); + erts_free_aligned_binary_bytes_extra((byte*)obj,ERTS_ALC_T_TMP); } int enif_inspect_binary(ErlNifEnv* env, Eterm bin_term, ErlNifBinary* bin) @@ -260,7 +260,7 @@ int enif_inspect_binary(ErlNifEnv* env, Eterm bin_term, ErlNifBinary* bin) byte* raw_ptr; }u; u.tmp = NULL; - bin->data = erts_get_aligned_binary_bytes_extra(bin_term, &u.raw_ptr, + bin->data = erts_get_aligned_binary_bytes_extra(bin_term, &u.raw_ptr, ERTS_ALC_T_TMP, sizeof(struct enif_tmp_obj_t)); if (bin->data == NULL) { return 0; 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