Tarantool development patches archive
 help / color / mirror / Atom feed
* [PATCH v1 1/1] implement mp_stack class
@ 2019-01-16 13:36 Kirill Shcherbatov
  2019-01-16 18:03 ` Konstantin Osipov
                   ` (2 more replies)
  0 siblings, 3 replies; 19+ messages in thread
From: Kirill Shcherbatov @ 2019-01-16 13:36 UTC (permalink / raw)
  To: tarantool-patches, vdavydov.dev; +Cc: kostja, Kirill Shcherbatov

From: Kirill Shcherbatov <kshcherbatov@gmail.com>

https://github.com/tarantool/tarantool/tree/kshch/gh-1012-msgpuck-class

A new mp_stack class is a stack of service contexts mp_frame to
do complex msgpack parse. The structure is needed in order to
facilitate the decoding of nested msgpack structures without
recursion.

Needed for #1012
---
 msgpuck.h      | 108 +++++++++++++++++++++++++++++++++++++++++++++++++
 test/msgpuck.c |  59 ++++++++++++++++++++++++++-
 2 files changed, 166 insertions(+), 1 deletion(-)

diff --git a/msgpuck.h b/msgpuck.h
index b0d4967..45e19f9 100644
--- a/msgpuck.h
+++ b/msgpuck.h
@@ -359,6 +359,23 @@ enum mp_type {
 	MP_EXT
 };
 
+struct mp_frame {
+	enum mp_type type;
+	uint32_t size;
+	uint32_t curr;
+};
+
+/**
+ * Stack of service contexts mp_frame to do complex msgpack parse.
+ * The structure is needed in order to facilitate the decoding
+ * of nested msgpack structures without recursion.
+*/
+struct mp_stack {
+	uint32_t size;
+	uint32_t used;
+	struct mp_frame *frames;
+};
+
 /**
  * \brief Determine MsgPack type by a first byte \a c of encoded data.
  *
@@ -1184,6 +1201,97 @@ mp_check(const char **data, const char *end);
  * {{{ Implementation
  */
 
+/**
+ * \brief Initialize mp_stack \stack of specified size \size and
+ * user-allocated array \frames.
+ * The \frames allocation must have at least \size mp_frame items.
+ * \param stack - the pointer to a mp_stack to initialize.
+ * \param size - stack size, count of stack::frames to use.
+ * \param frames - mp_frame service context allocation to use,
+ *                 must have at least \size items.
+ */
+MP_PROTO void
+mp_stack_init(struct mp_stack *stack, uint32_t size, struct mp_frame *frames)
+{
+	stack->frames = frames;
+	stack->size = size;
+	stack->used = 0;
+}
+
+/**
+ * \brief Test if mp_stack \stack is empty.
+ * \param stack - the pointer to a mp_stack to a stack to test.
+ */
+MP_PROTO bool
+mp_stack_is_empty(struct mp_stack *stack)
+{
+	return stack->used == 0;
+}
+
+/**
+ * \brief Test if mp_stack \stack is full.
+ * \param stack - the pointer to a mp_stack to a stack to test.
+ */
+MP_PROTO bool
+mp_stack_is_full(struct mp_stack *stack)
+{
+	return stack->used >= stack->size;
+}
+
+/**
+ * \brief Pop the top mp_stack \stack frame.
+ * \stack must not be empty.
+ * \param stack - the pointer to a mp_stack to operate with.
+ */
+MP_PROTO void
+mp_stack_pop(struct mp_stack *stack)
+{
+	assert(!mp_stack_is_empty(stack));
+	--stack->used;
+}
+
+/**
+ * \brief Get a pointer to a top mp_stack \stack frame.
+ * \param stack - the pointer to a mp_stack to operate with.
+ * The \stack must not be empty.
+ * \retval a pointer to a top stack frame.
+ */
+MP_PROTO struct mp_frame *
+mp_stack_top(struct mp_stack *stack)
+{
+	assert(!mp_stack_is_empty(stack));
+	return &stack->frames[stack->used - 1];
+}
+
+/**
+ * \brief Construct a new mp_frame and push it on to mp_stack
+ * \stack. The \stack must not be full.
+ * \param stack - the pointer to a stack to operate with.
+ * \retval a pointer to a top stack frame.
+ */
+MP_PROTO void
+mp_stack_push(struct mp_stack *stack, enum mp_type type, uint32_t size)
+{
+	assert(!mp_stack_is_full(stack));
+	uint32_t idx = stack->used++;
+	stack->frames[idx].type = type;
+	stack->frames[idx].size = size;
+	stack->frames[idx].curr = 0;
+}
+
+/**
+ * \brief Advance a mp_stack::curr attribute of the mp_stack.
+ * \stack top frame. The \stack must not be empty.
+ * \retval true, when the top frame have already parsed:
+ *         mp_stack::curr >= mp_stack::size; false otherwise.
+ */
+MP_PROTO bool
+mp_stack_advance(struct mp_stack *stack)
+{
+	struct mp_frame *frame = mp_stack_top(stack);
+	return ++frame->curr > frame->size;
+}
+
 /** \cond false */
 extern const enum mp_type mp_type_hint[];
 extern const int8_t mp_parser_hint[];
diff --git a/test/msgpuck.c b/test/msgpuck.c
index 9265453..fe6aa47 100644
--- a/test/msgpuck.c
+++ b/test/msgpuck.c
@@ -1093,10 +1093,66 @@ test_overflow()
 	return check_plan();
 }
 
+static int
+test_mpstack()
+{
+	plan(18);
+	header();
+
+	char tuple[1024];
+	char *wptr = tuple;
+	/* ["first", {"key1": 1, "key2": [1]}, [1]] */
+	wptr = mp_encode_array(wptr, 3);
+	wptr = mp_encode_str(wptr, "first", 5);
+	wptr = mp_encode_map(wptr, 2);
+	wptr = mp_encode_str(wptr, "key1", 4);
+	wptr = mp_encode_uint(wptr, 1);
+	wptr = mp_encode_str(wptr, "key2", 4);
+	wptr = mp_encode_array(wptr, 1);
+	wptr = mp_encode_uint(wptr, 1);
+	wptr = mp_encode_array(wptr, 1);
+	wptr = mp_encode_uint(wptr, 1);
+	const char *rptr = tuple;
+
+	struct mp_frame mp_frames[2];
+	struct mp_stack mp_stack;
+	mp_stack_init(&mp_stack, 2, mp_frames);
+	is(mp_stack_is_empty(&mp_stack), true, "Stack is empty");
+	mp_stack_push(&mp_stack, MP_ARRAY, mp_decode_array(&rptr));
+	is(mp_stack_is_empty(&mp_stack), false, "Stack is not empty");
+	is(mp_stack_is_full(&mp_stack), false, "Stack is not full");
+	is(mp_stack_top(&mp_stack)->type, MP_ARRAY, "Correct field type");
+	is(mp_stack_top(&mp_stack)->size, 3, "Correct items count");
+	is(mp_stack_advance(&mp_stack), false, "Not all items on level 1 parsed");
+	mp_next(&rptr);
+	is(mp_stack_top(&mp_stack)->curr, 1, "Correct current item index");
+	mp_stack_push(&mp_stack, MP_MAP, mp_decode_map(&rptr));
+	is(mp_stack_top(&mp_stack)->type, MP_MAP, "Correct field type");
+	is(mp_stack_top(&mp_stack)->size, 2, "Correct items count");
+	is(mp_stack_is_full(&mp_stack), true, "Stack is full");
+	is(mp_stack_advance(&mp_stack), false, "Not all items on level 2 parsed");
+	mp_next(&rptr);
+	mp_next(&rptr);
+	is(mp_stack_advance(&mp_stack), false, "Not all items on level 2 parsed");
+	is(mp_stack_advance(&mp_stack), true, "All items on level 2 parsed");
+	mp_next(&rptr);
+	mp_next(&rptr);
+	mp_stack_pop(&mp_stack);
+	is(mp_stack_is_full(&mp_stack), false, "Stack is not full");
+	is(mp_stack_advance(&mp_stack), false, "Not all items on level 1 parsed");
+	mp_next(&rptr);
+	is(mp_stack_advance(&mp_stack), false, "Not all items on level 1 parsed");
+	is(mp_stack_advance(&mp_stack), true, "All items on level 1 parsed");
+	mp_stack_pop(&mp_stack);
+	is(mp_stack_is_empty(&mp_stack), true, "Stack is empty");
+
+	footer();
+	return check_plan();
+}
 
 int main()
 {
-	plan(20);
+	plan(21);
 	test_uints();
 	test_ints();
 	test_bools();
@@ -1117,6 +1173,7 @@ int main()
 	test_mp_check();
 	test_numbers();
 	test_overflow();
+	test_mpstack();
 
 	return check_plan();
 }
-- 
2.19.2

^ permalink raw reply	[flat|nested] 19+ messages in thread

end of thread, other threads:[~2019-01-24 17:58 UTC | newest]

Thread overview: 19+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-01-16 13:36 [PATCH v1 1/1] implement mp_stack class Kirill Shcherbatov
2019-01-16 18:03 ` Konstantin Osipov
2019-01-17  7:26   ` Kirill Shcherbatov
2019-01-17  7:32 ` [tarantool-patches] " Kirill Shcherbatov
2019-01-17 11:58 ` Alexander Turenko
2019-01-17 12:28   ` [tarantool-patches] " Kirill Shcherbatov
2019-01-17 16:34     ` Alexander Turenko
2019-01-18  7:03       ` Kirill Shcherbatov
2019-01-18 10:32       ` Kirill Shcherbatov
2019-01-21  9:46         ` Kirill Shcherbatov
2019-01-21 11:25         ` Alexander Turenko
2019-01-21 12:35           ` Kirill Shcherbatov
2019-01-21 20:25             ` Vladimir Davydov
2019-01-22 12:28               ` Kirill Shcherbatov
2019-01-22 20:21                 ` Vladimir Davydov
2019-01-23  8:23                   ` Kirill Shcherbatov
2019-01-23 10:06                     ` Vladimir Davydov
2019-01-23 11:39                       ` Kirill Shcherbatov
2019-01-24 17:58                     ` Konstantin Osipov

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox