[commit] master: track IMAP message sequence numbers (and therefore expunges)
mailbox synchronizer
Brought to you by:
ossi
Menu
▾
▴
[commit] master: track IMAP message sequence numbers (and therefore expunges)
|
From: Oswald B. <os...@us...> - 2022-06-19 14:38:47
|
commit 1a1ac25bc867da5b934ddf8acf00f994f6033f25
Author: Oswald Buddenhagen <os...@us...>
Date: Tue Apr 26 13:45:05 2022 +0200
track IMAP message sequence numbers (and therefore expunges)
.gitignore | 1 +
src/.gitignore | 3 +
src/Makefile.am | 9 ++-
src/drv_imap.c | 125 +++++++++++++--------------------
src/imap_msgs.c | 153 ++++++++++++++++++++++++++++++++++++++++
src/imap_p.h | 48 +++++++++++++
src/tst_imap_msgs.c | 166 ++++++++++++++++++++++++++++++++++++++++++++
7 files changed, 427 insertions(+), 78 deletions(-)
diff --git a/.gitignore b/.gitignore
index 236dae50..74de561f 100644
--- a/.gitignore
+++ b/.gitignore
@@ -29,6 +29,7 @@
/stamp-h
/stamp-h.in
/stamp-h1
+/test-driver
Makefile
Makefile.in
diff --git a/src/.gitignore b/src/.gitignore
index 15e76dbc..4c388832 100644
--- a/src/.gitignore
+++ b/src/.gitignore
@@ -2,8 +2,11 @@
/drv_proxy.inc
/mbsync
/mdconvert
+/tst_imap_msgs
/tst_timers
/tmp
.deps/
+*.log
*.o
+*.trs
diff --git a/src/Makefile.am b/src/Makefile.am
index f241db27..ad8552b7 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -5,13 +5,13 @@
mbsync_SOURCES = \
util.c config.c socket.c \
driver.c drv_proxy.c \
- drv_imap.c \
+ drv_imap.c imap_msgs.c \
drv_maildir.c \
sync.c sync_state.c \
main.c main_sync.c main_list.c
noinst_HEADERS = \
common.h config.h socket.h \
- driver.h \
+ driver.h imap_p.h \
sync.h sync_p.h \
main_p.h
mbsync_LDADD = $(DB_LIBS) $(SSL_LIBS) $(SOCK_LIBS) $(SASL_LIBS) $(Z_LIBS) $(KEYCHAIN_LIBS)
@@ -52,6 +52,11 @@ endif
bin_PROGRAMS = mbsync $(mdconvert_prog)
man_MANS = mbsync.1 $(mdconvert_man)
+tst_imap_msgs_SOURCES = tst_imap_msgs.c imap_msgs.c util.c
+
+check_PROGRAMS = tst_imap_msgs
+TESTS = $(check_PROGRAMS)
+
tst_timers_SOURCES = tst_timers.c util.c
EXTRA_PROGRAMS = tst_timers
diff --git a/src/drv_imap.c b/src/drv_imap.c
index 23dcfd45..3c54a2d1 100644
--- a/src/drv_imap.c
+++ b/src/drv_imap.c
@@ -6,7 +6,7 @@
* mbsync - mailbox synchronizer
*/
-#include "driver.h"
+#include "imap_p.h"
#include "socket.h"
@@ -58,14 +58,6 @@ typedef union imap_store_conf {
};
} imap_store_conf_t;
-typedef union imap_message {
- message_t gen;
- struct {
- MESSAGE(union imap_message)
- // uint seq; will be needed when expunges are tracked
- };
-} imap_message_t;
-
#define NIL (void*)0x1
#define LIST (void*)0x2
@@ -112,8 +104,8 @@ union imap_store {
// but mailbox totals.
int total_msgs, recent_msgs;
uint uidvalidity, uidnext;
- imap_message_t **msgapp, *msgs; // FETCH results
- uint msgcnt;
+ imap_messages_t msgs;
+ uint fetch_seq; // FETCH results
uint caps; // CAPABILITY results
string_list_t *auth_mechs;
parse_list_state_t parse_list_sts;
@@ -139,8 +131,9 @@ union imap_store {
int sasl_cont;
#endif
+ void (*expunge_callback)( message_t *msg, void *aux );
void (*bad_callback)( void *aux );
- void *bad_callback_aux;
+ void *drv_callback_aux;
conn_t conn; // This is BIG, so put it last
};
@@ -1206,10 +1199,9 @@ parse_fetch_rsp( imap_store_t *ctx, list_t *list, char *s ATTR_UNUSED )
// Workaround for server not sending UIDNEXT and/or APPENDUID.
ctx->uidnext = uid + 1;
} else if (ctx->fetch_sts == FetchMsgs) {
- cur = nfzalloc( sizeof(*cur) );
- *ctx->msgapp = cur;
- ctx->msgapp = &cur->next;
- ctx->msgcnt++;
+ imap_ensure_absolute( &ctx->msgs ); // In case of interleaved EXPUNGE
+ cur = imap_new_msg( & ctx->msgs );
+ cur->seq = ctx->fetch_seq;
cur->uid = uid;
cur->flags = mask;
cur->status = status;
@@ -1524,6 +1516,14 @@ prepare_trash( char **buf, const imap_store_t *ctx )
return prepare_name( buf, ctx, ctx->prefix, ctx->conf->trash );
}
+static void
+record_expunge( imap_store_t *ctx, uint seq )
+{
+ imap_message_t *eptr = imap_expunge_msg( &ctx->msgs, seq );
+ if (eptr)
+ ctx->expunge_callback( &eptr->gen, ctx->drv_callback_aux );
+}
+
typedef union {
imap_cmd_t gen;
struct {
@@ -1542,6 +1542,7 @@ imap_socket_read( void *aux )
imap_cmd_t *cmdp, **pcmdp;
char *cmd, *arg, *arg1, *p;
int resp, resp2, tag;
+ uint seq;
conn_iovec_t iov[2];
for (;;) {
@@ -1622,10 +1623,19 @@ imap_socket_read( void *aux )
if (!strcmp( "EXISTS", arg1 )) {
ctx->total_msgs = atoi( arg );
} else if (!strcmp( "EXPUNGE", arg1 )) {
+ if (!(seq = strtoul( arg, &arg1, 10 )) || *arg1) {
+ badseq:
+ error( "IMAP error: malformed sequence number '%s'\n", arg );
+ break;
+ }
+ record_expunge( ctx, seq );
ctx->total_msgs--;
} else if (!strcmp( "RECENT", arg1 )) {
ctx->recent_msgs = atoi( arg );
} else if (!strcmp( "FETCH", arg1 )) {
+ if (!(seq = strtoul( arg, &arg1, 10 )) || *arg1)
+ goto badseq;
+ ctx->fetch_seq = seq;
resp = parse_list( ctx, cmd, parse_fetch_rsp );
goto listret;
}
@@ -1777,7 +1787,7 @@ imap_cancel_store( store_t *gctx )
cancel_pending_imap_cmds( ctx );
free( ctx->ns_prefix );
free_string_list( ctx->auth_mechs );
- free_generic_messages( &ctx->msgs->gen );
+ free_generic_messages( &ctx->msgs.head->gen );
free_string_list( ctx->boxes );
imap_deref( ctx );
}
@@ -1793,19 +1803,20 @@ imap_deref( imap_store_t *ctx )
}
static void
-imap_set_callbacks( store_t *gctx, void (*exp_cb)( message_t *, void * ) ATTR_UNUSED,
- void (*cb)( void * ), void *aux )
+imap_set_callbacks( store_t *gctx, void (*exp_cb)( message_t *, void * ),
+ void (*bad_cb)( void * ), void *aux )
{
imap_store_t *ctx = (imap_store_t *)gctx;
- ctx->bad_callback = cb;
- ctx->bad_callback_aux = aux;
+ ctx->expunge_callback = exp_cb;
+ ctx->bad_callback = bad_cb;
+ ctx->drv_callback_aux = aux;
}
static void
imap_invoke_bad_callback( imap_store_t *ctx )
{
- ctx->bad_callback( ctx->bad_callback_aux );
+ ctx->bad_callback( ctx->drv_callback_aux );
}
/******************* imap_free_store *******************/
@@ -1838,8 +1849,7 @@ imap_free_store( store_t *gctx )
return;
}
- free_generic_messages( &ctx->msgs->gen );
- ctx->msgs = NULL;
+ reset_imap_messages( &ctx->msgs );
imap_set_callbacks( gctx, NULL, imap_cancel_unowned, gctx );
ctx->next = unowned;
unowned = ctx;
@@ -2630,10 +2640,7 @@ imap_select_box( store_t *gctx, const char *name )
assert( !ctx->pending && !ctx->in_progress && !ctx->wait_check );
- free_generic_messages( &ctx->msgs->gen );
- ctx->msgs = NULL;
- ctx->msgapp = &ctx->msgs;
- ctx->msgcnt = 0;
+ reset_imap_messages( &ctx->msgs );
ctx->name = name;
return DRV_OK;
@@ -2922,47 +2929,6 @@ imap_load_box( store_t *gctx, uint minuid, uint maxuid, uint finduid, uint pairu
}
}
-static int
-imap_sort_msgs_comp( const void *a_, const void *b_ )
-{
- const message_t *a = *(const message_t * const *)a_;
- const message_t *b = *(const message_t * const *)b_;
-
- if (a->uid < b->uid)
- return -1;
- if (a->uid > b->uid)
- return 1;
- return 0;
-}
-
-static void
-imap_sort_msgs( imap_store_t *ctx )
-{
- uint count = ctx->msgcnt;
- if (count <= 1)
- return;
-
- imap_message_t **t = nfmalloc( sizeof(*t) * count );
-
- imap_message_t *m = ctx->msgs;
- for (uint i = 0; i < count; i++) {
- t[i] = m;
- m = m->next;
- }
-
- qsort( t, count, sizeof(*t), imap_sort_msgs_comp );
-
- ctx->msgs = t[0];
-
- uint j;
- for (j = 0; j < count - 1; j++)
- t[j]->next = t[j + 1];
- ctx->msgapp = &t[j]->next;
- *ctx->msgapp = NULL;
-
- free( t );
-}
-
static void imap_submit_load_p2( imap_store_t *, imap_cmd_t *, int );
static void
@@ -2994,8 +2960,8 @@ imap_submit_load_p3( imap_store_t *ctx, imap_load_box_state_t *sts )
DONE_REFCOUNTED_STATE_ARGS(sts, {
ctx->fetch_sts = FetchNone;
if (sts->ret_val == DRV_OK)
- imap_sort_msgs( ctx );
- }, &ctx->msgs->gen, ctx->total_msgs, ctx->recent_msgs)
+ imap_ensure_relative( &ctx->msgs );
+ }, &ctx->msgs.head->gen, ctx->total_msgs, ctx->recent_msgs)
}
/******************* imap_fetch_msg *******************/
@@ -3023,7 +2989,9 @@ imap_fetch_msg_p2( imap_store_t *ctx, imap_cmd_t *gcmd, int response )
imap_cmd_fetch_msg_t *cmd = (imap_cmd_fetch_msg_t *)gcmd;
if (response == RESP_OK && !cmd->msg_data->data) {
- /* The FETCH succeeded, but there is no message with this UID. */
+ // The UID FETCH succeeded, but there is no message with this UID.
+ // The corresponding EXPUNGE response has been received by this time,
+ // so the message is already marked as dead.
response = RESP_NO;
}
imap_done_simple_msg( ctx, gcmd, response );
@@ -3140,9 +3108,9 @@ imap_close_box( store_t *gctx,
int bl;
char buf[1000];
- for (msg = ctx->msgs; ; ) {
+ for (msg = ctx->msgs.head; ; ) {
for (bl = 0; msg && bl < 960; msg = msg->next) {
- if (!(msg->flags & F_DELETED))
+ if ((msg->status & M_DEAD) || !(msg->flags & F_DELETED))
continue;
if (bl)
buf[bl++] = ',';
@@ -3161,7 +3129,9 @@ imap_close_box( store_t *gctx,
} else {
/* This is inherently racy: it may cause messages which other clients
* marked as deleted to be expunged without being trashed. */
- // Note that, to save bandwidth, we don't use EXPUNGE.
+ // Note that, to save bandwidth, we don't use EXPUNGE. Also, in many
+ // cases, we wouldn't be able to map the EXPUNGE responses' seq numbers
+ // anyway, due to not having fetched the messages.
INIT_IMAP_CMD(imap_cmd_simple_t, cmd, cb, aux)
imap_exec( ctx, &cmd->gen, imap_done_simple_box, "CLOSE" );
}
@@ -3281,7 +3251,7 @@ imap_find_new_msgs( store_t *gctx, uint newuid,
imap_store_t *ctx = (imap_store_t *)gctx;
INIT_IMAP_CMD(imap_cmd_find_new_t, cmd, cb, aux)
- cmd->out_msgs = ctx->msgapp;
+ cmd->out_msgs = ctx->msgs.tail;
cmd->uid = newuid;
// Some servers fail to enumerate recently APPENDed messages without syncing first.
imap_exec( ctx, &cmd->gen, imap_find_new_msgs_p2, "CHECK" );
@@ -3346,6 +3316,9 @@ imap_find_new_msgs_p4( imap_store_t *ctx ATTR_UNUSED, imap_cmd_t *gcmd, int resp
ctx->fetch_sts = FetchNone;
transform_box_response( &response );
+ // Note: unlike in load_box(), we don't call imap_ensure_relative() here,
+ // as it's unnecessary. It being called due to unsolicited responses
+ // causes no harm.
cmdp->callback( response, &(*cmdp->out_msgs)->gen, cmdp->callback_aux );
}
diff --git a/src/imap_msgs.c b/src/imap_msgs.c
new file mode 100644
index 00000000..97959278
--- /dev/null
+++ b/src/imap_msgs.c
@@ -0,0 +1,153 @@
+// SPDX-FileCopyrightText: 2022 Oswald Buddenhagen <os...@us...>
+// SPDX-License-Identifier: GPL-2.0-or-later WITH LicenseRef-isync-GPL-exception
+//
+// mbsync - mailbox synchronizer
+//
+
+#include "imap_p.h"
+
+#ifdef DEBUG_IMAP_MSGS
+# define dbg(...) print(__VA_ARGS__)
+#else
+# define dbg(...) do { } while (0)
+#endif
+
+imap_message_t *
+imap_new_msg( imap_messages_t *msgs )
+{
+ imap_message_t *msg = nfzalloc( sizeof(*msg) );
+ *msgs->tail = msg;
+ msgs->tail = &msg->next;
+ msgs->count++;
+ return msg;
+}
+
+void
+reset_imap_messages( imap_messages_t *msgs )
+{
+ free_generic_messages( &msgs->head->gen );
+ msgs->head = NULL;
+ msgs->tail = &msgs->head;
+ msgs->count = 0;
+ msgs->cursor_ptr = NULL;
+ msgs->cursor_seq = 0;
+}
+
+static int
+imap_compare_msgs( const void *a_, const void *b_ )
+{
+ const imap_message_t *a = *(const imap_message_t * const *)a_;
+ const imap_message_t *b = *(const imap_message_t * const *)b_;
+
+ if (a->uid < b->uid)
+ return -1;
+ if (a->uid > b->uid)
+ return 1;
+ return 0;
+}
+
+void
+imap_ensure_relative( imap_messages_t *msgs )
+{
+ if (msgs->cursor_ptr)
+ return;
+ uint count = msgs->count;
+ if (!count)
+ return;
+ if (count > 1) {
+ imap_message_t **t = nfmalloc( sizeof(*t) * count );
+
+ imap_message_t *m = msgs->head;
+ for (uint i = 0; i < count; i++) {
+ t[i] = m;
+ m = m->next;
+ }
+
+ qsort( t, count, sizeof(*t), imap_compare_msgs );
+
+ imap_message_t *nm = t[0];
+ msgs->head = nm;
+ nm->prev = NULL;
+ uint seq, nseq = nm->seq;
+ for (uint j = 0; m = nm, seq = nseq, j < count - 1; j++) {
+ nm = t[j + 1];
+ m->next = nm;
+ m->next->prev = m;
+ nseq = nm->seq;
+ nm->seq = nseq - seq;
+ }
+ msgs->tail = &m->next;
+ *msgs->tail = NULL;
+
+ free( t );
+ }
+ msgs->cursor_ptr = msgs->head;
+ msgs->cursor_seq = msgs->head->seq;
+}
+
+void
+imap_ensure_absolute( imap_messages_t *msgs )
+{
+ if (!msgs->cursor_ptr)
+ return;
+ uint seq = 0;
+ for (imap_message_t *msg = msgs->head; msg; msg = msg->next) {
+ seq += msg->seq;
+ msg->seq = seq;
+ }
+ msgs->cursor_ptr = NULL;
+ msgs->cursor_seq = 0;
+}
+
+imap_message_t *
+imap_expunge_msg( imap_messages_t *msgs, uint fseq )
+{
+ dbg( "expunge %u\n", fseq );
+ imap_ensure_relative( msgs );
+ imap_message_t *ret = NULL, *msg = msgs->cursor_ptr;
+ if (msg) {
+ uint seq = msgs->cursor_seq;
+ for (;;) {
+ dbg( " now on message %u (uid %u), %sdead\n", seq, msg->uid, (msg->status & M_DEAD) ? "" : "not " );
+ if (seq == fseq && !(msg->status & M_DEAD)) {
+ dbg( " => expunging\n" );
+ msg->status = M_DEAD;
+ ret = msg;
+ break;
+ }
+ if (seq < fseq) {
+ dbg( " is below\n" );
+ if (!msg->next) {
+ dbg( " no next\n" );
+ goto done;
+ }
+ msg = msg->next;
+ seq += msg->seq;
+ } else {
+ dbg( " is not below\n" );
+ if (!msg->prev) {
+ dbg( " no prev\n" );
+ break;
+ }
+ uint pseq = seq - msg->seq;
+ if (pseq < fseq) {
+ dbg( " prev too low\n" );
+ break;
+ }
+ seq = pseq;
+ msg = msg->prev;
+ }
+ }
+ dbg( " => lowering\n" );
+ assert( msg->seq );
+ msg->seq--;
+ seq--;
+ done:
+ dbg( " saving cursor on %u (uid %u)\n", seq, msg->uid );
+ msgs->cursor_ptr = msg;
+ msgs->cursor_seq = seq;
+ } else {
+ dbg( " => no messages\n" );
+ }
+ return ret;
+}
diff --git a/src/imap_p.h b/src/imap_p.h
new file mode 100644
index 00000000..76e02e21
--- /dev/null
+++ b/src/imap_p.h
@@ -0,0 +1,48 @@
+// SPDX-FileCopyrightText: 2022 Oswald Buddenhagen <os...@us...>
+// SPDX-License-Identifier: GPL-2.0-or-later WITH LicenseRef-isync-GPL-exception
+//
+// mbsync - mailbox synchronizer
+//
+
+#ifndef IMAP_P_H
+#define IMAP_P_H
+
+#include "driver.h"
+
+//#define DEBUG_IMAP_MSGS
+
+typedef union imap_message {
+ message_t gen;
+ struct {
+ MESSAGE(union imap_message)
+
+ union imap_message *prev; // Used to optimize lookup by seq.
+ // This is made relative once the fetches complete - to avoid that
+ // each expunge re-enumerates all subsequent messages. Dead messages
+ // "occupy" no sequence number themselves, but may still jump a gap.
+ // Note that use of sequence numbers to address messages in commands
+ // imposes limitations on permissible pipelining. We don't do that,
+ // so this is of no concern; however, we might miss the closing of
+ // a gap, which would result in a tiny performance hit.
+ uint seq;
+ };
+} imap_message_t;
+
+typedef struct {
+ imap_message_t *head;
+ imap_message_t **tail;
+ // Bulk changes (which is where performance matters) are assumed to be
+ // reported sequentially (be it forward or reverse), so walking the
+ // sorted linked list from the previously used message is efficient.
+ imap_message_t *cursor_ptr;
+ uint cursor_seq;
+ uint count;
+} imap_messages_t;
+
+imap_message_t *imap_new_msg( imap_messages_t *msgs );
+imap_message_t *imap_expunge_msg( imap_messages_t *msgs, uint fseq );
+void reset_imap_messages( imap_messages_t *msgs );
+void imap_ensure_relative( imap_messages_t *msgs );
+void imap_ensure_absolute( imap_messages_t *msgs );
+
+#endif
diff --git a/src/tst_imap_msgs.c b/src/tst_imap_msgs.c
new file mode 100644
index 00000000..f1df3d9e
--- /dev/null
+++ b/src/tst_imap_msgs.c
@@ -0,0 +1,166 @@
+// SPDX-FileCopyrightText: 2022 Oswald Buddenhagen <os...@us...>
+// SPDX-License-Identifier: GPL-2.0-or-later
+//
+// isync test suite
+//
+
+#include "imap_p.h"
+
+static imap_messages_t smsgs;
+
+// from driver.c
+void
+free_generic_messages( message_t *msgs )
+{
+ message_t *tmsg;
+
+ for (; msgs; msgs = tmsg) {
+ tmsg = msgs->next;
+ // free( msgs->msgid );
+ free( msgs );
+ }
+}
+
+static void
+dump_messages( void )
+{
+ print( "=>" );
+ uint seq = 0;
+ for (imap_message_t *msg = smsgs.head; msg; msg = msg->next) {
+ seq += msg->seq;
+ if (msg->status & M_DEAD)
+ print( " (%u:%u)", seq, msg->uid );
+ else
+ print( " %u:%u", seq, msg->uid );
+ }
+ print( "\n" );
+}
+
+static void
+init( uint *in )
+{
+ reset_imap_messages( &smsgs );
+ for (; *in; in++) {
+ imap_message_t *msg = imap_new_msg( &smsgs );
+ msg->seq = *in;
+ // We (ab)use the initial sequence number as the UID. That's not
+ // exactly realistic, but it's valid, and saves us redundant data.
+ msg->uid = *in;
+ }
+}
+
+static void
+modify( uint *in )
+{
+ for (; *in; in++) {
+ imap_expunge_msg( &smsgs, *in );
+#ifdef DEBUG_IMAP_MSGS
+ dump_messages();
+#endif
+ }
+}
+
+static void
+verify( uint *in, const char *name )
+{
+ int fails = 0;
+ imap_message_t *msg = smsgs.head;
+ for (;;) {
+ if (msg && *in && msg->uid == *in) {
+ if (msg->status & M_DEAD) {
+ printf( "*** %s: message %u is dead\n", name, msg->uid );
+ fails++;
+ } else {
+ assert( msg->seq );
+ }
+ msg = msg->next;
+ in++;
+ } else if (*in && (!msg || msg->uid > *in)) {
+ printf( "*** %s: message %u is missing\n", name, *in );
+ fails++;
+ in++;
+ } else if (msg) {
+ if (!(msg->status & M_DEAD)) {
+ printf( "*** %s: excess message %u\n", name, msg->uid );
+ fails++;
+ }
+ msg = msg->next;
+ } else {
+ assert( !*in );
+ break;
+ }
+ }
+ if (fails)
+ dump_messages();
+}
+
+static void
+test( uint *ex, uint *out, const char *name )
+{
+ printf( "test %s ...\n", name );
+ modify( ex );
+ verify( out, name );
+}
+
+int
+main( void )
+{
+ static uint arr_0[] = { 0 };
+ static uint arr_1[] = { 1, 0 };
+
+ static uint full_in[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 0 };
+ init( full_in );
+#if 0
+ static uint nop[] = { 0 };
+ static uint nop_out[] = { /* 1, */ 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, /* 17, */ 18 /*!*/, 0 };
+ test( nop, nop_out, "self-test" );
+#endif
+ static uint full_ex_fw1[] = { 18, 13, 13, 13, 1, 1, 1, 0 };
+ static uint full_out_fw1[] = { 4, 5, 6, 7, 8, 9, 10, 11, 12, 16, 17, 0 };
+ test( full_ex_fw1, full_out_fw1, "full, forward 1" );
+ static uint full_ex_fw2[] = { 10, 10, 0 };
+ static uint full_out_fw2[] = { 4, 5, 6, 7, 8, 9, 10, 11, 12, 0 };
+ test( full_ex_fw2, full_out_fw2, "full, forward 2" );
+
+ init( full_in );
+ static uint full_ex_bw1[] = { 18, 17, 16, 15, 14, 13, 5, 4, 3, 0 };
+ static uint full_out_bw1[] = { 1, 2, 6, 7, 8, 9, 10, 11, 12, 0 };
+ test( full_ex_bw1, full_out_bw1, "full, backward 1" );
+ static uint full_ex_bw2[] = { 2, 1, 0 };
+ static uint full_out_bw2[] = { 6, 7, 8, 9, 10, 11, 12, 0 };
+ test( full_ex_bw2, full_out_bw2, "full, backward 2" );
+
+ static uint hole_wo1_in[] = { 10, 11, 12, 20, 21, 31, 32, 33, 34, 35, 36, 37, 0 };
+ init( hole_wo1_in );
+ static uint hole_wo1_ex_1[] = { 31, 30, 29, 28, 22, 21, 11, 2, 1, 0 };
+ static uint hole_wo1_out_1[] = { 10, 12, 20, 32, 33, 34, 35, 36, 37, 0 };
+ test( hole_wo1_ex_1, hole_wo1_out_1, "hole w/o 1, backward" );
+
+ init( hole_wo1_in );
+ static uint hole_wo1_ex_2[] = { 1, 1, 9, 18, 18, 23, 23, 23, 23, 0 };
+ test( hole_wo1_ex_2, hole_wo1_out_1, "hole w/o 1, forward" );
+ test( arr_1, hole_wo1_out_1, "hole w/o 1, forward 2" );
+ static uint hole_wo1_ex_4[] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0 };
+ static uint hole_wo1_out_4[] = { 37, 0 };
+ test( hole_wo1_ex_4, hole_wo1_out_4, "hole w/o 1, forward 3" );
+ test( arr_1, arr_0, "hole w/o 1, forward 4" );
+ test( arr_1, arr_0, "hole w/o 1, forward 5" );
+
+ static uint hole_w1_in[] = { 1, 10, 11, 12, 0 };
+ init( hole_w1_in );
+ static uint hole_w1_ex_1[] = { 11, 10, 2, 1, 0 };
+ static uint hole_w1_out_1[] = { 12, 0 };
+ test( hole_w1_ex_1, hole_w1_out_1, "hole w/ 1, backward" );
+ test( arr_1, hole_w1_out_1, "hole w/ 1, backward 2" );
+
+ init( hole_w1_in );
+ static uint hole_w1_ex_2[] = { 1, 1, 8, 8, 0 };
+ test( hole_w1_ex_2, hole_w1_out_1, "hole w/ 1, forward" );
+ static uint hole_w1_ex_4[] = { 1, 1, 1, 1, 1, 1, 1, 0 };
+ static uint hole_w1_out_4[] = { 12, 0 };
+ test( hole_w1_ex_4, hole_w1_out_4, "hole w/ 1, forward 2" );
+ test( arr_1, arr_0, "hole w/ 1, forward 3" );
+ test( arr_1, arr_0, "hole w/ 1, forward 4" );
+
+ return 0;
+}
|
