aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--erts/emulator/beam/atom.names2
-rw-r--r--erts/emulator/beam/bif.tab4
-rw-r--r--erts/emulator/beam/binary.c4
-rw-r--r--erts/emulator/beam/erl_alloc.types1
-rw-r--r--erts/emulator/beam/erl_bif_binary.c317
-rw-r--r--erts/emulator/beam/erl_binary.h15
-rw-r--r--erts/emulator/beam/erl_nif.c4
-rw-r--r--lib/stdlib/test/binary_module_SUITE.erl82
-rw-r--r--lib/stdlib/test/binref.erl74
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 ]).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -319,6 +320,77 @@ at(Subject,X) ->
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%% 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
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
part(Subject,Part) ->
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-24 08:43:15 +0000