[tarantool-patches] Re: [PATCH v1 1/1] implement mp_stack class
Kirill Shcherbatov
kshcherbatov at tarantool.org
Thu Jan 17 15:28:34 MSK 2019
On 17.01.2019 14:58, Alexander Turenko wrote:
> Look at the `make doc` warnings, the doxygen format is slightly
> different then yours one.
> Please, start the commit mesaage from the upper letter (because it has
> no prefix).
Tnx, fixed.
> Can you please share how do you intend to use it? One or more real
> cases.
Please take a look at
[tarantool-patches] [PATCH v8 3/5] box: introduce JSON Indexes
tuple_init_field_map routine
==============================
Introduced a new mp_stack class to make complex msgpack parsing.
The structure is needed in order to facilitate the decoding
nested MP_ARRAY and MP_MAP msgpack containers without recursion.
This allows you to determine that the parsing of the current
container is complete.
Needed for #1012
---
msgpuck.h | 135 +++++++++++++++++++++++++++++++++++++++++++++++++
test/msgpuck.c | 59 ++++++++++++++++++++-
2 files changed, 193 insertions(+), 1 deletion(-)
diff --git a/msgpuck.h b/msgpuck.h
index b0d4967..3b1249f 100644
--- a/msgpuck.h
+++ b/msgpuck.h
@@ -359,6 +359,45 @@ enum mp_type {
MP_EXT
};
+/** Message pack MP_MAP or MP_ARRAY container descriptor. */
+struct mp_frame {
+ /** MP frame type calculated with mp_typeof(). */
+ enum mp_type type;
+ /**
+ * Total items in MP_MAP or MP_ARRAY container
+ * calculated with mp_decode_map() or mp_decode_array().
+ */
+ uint32_t size;
+ /**
+ * Count of items already processed. Must be less or
+ * equal to mp_frame::size member.
+ */
+ uint32_t curr;
+};
+
+/**
+ * Stack of service contexts mp_frame to do complex msgpack parse.
+ * The structure is needed in order to facilitate the decoding
+ * nested MP_ARRAY and MP_MAP msgpack containers without
+ * recursion. This allows you to determine that the parsing of
+ * the current container is complete.
+*/
+struct mp_stack {
+ /** The maximum stack depth. */
+ uint32_t size;
+ /**
+ * Count of used stack frames. Corresponds to the index
+ * in the array to perform the push operation. Must be
+ * less or equal to mp_stack::size member.
+ */
+ uint32_t used;
+ /**
+ * Array of mp_frames descriptors having at least
+ * mp_stack::size items.
+ */
+ struct mp_frame *frames;
+};
+
/**
* \brief Determine MsgPack type by a first byte \a c of encoded data.
*
@@ -1184,6 +1223,102 @@ mp_check(const char **data, const char *end);
* {{{ Implementation
*/
+/**
+ * \brief Initialize mp_stack \a stack of specified size \a size
+ * and user-allocated array \a frames.
+ * The \a frames allocation must have at least \a 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 \a 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 \a 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 \a 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 \a stack frame.
+ * The \a 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 \a stack frame.
+ * \param stack - the pointer to a mp_stack to operate with.
+ * The \a 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
+ * \a stack. The \a stack must not be full.
+ * \param stack - the pointer to a stack to operate with.
+ * \param type - the type of mp_frame to create.
+ * \param size - size size of mp_frame to create.
+ * \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_top()::\a curr attribute of the
+ * \a stack. The \a stack must not be empty.
+ * \param stack - the pointer to a stack to operate with
+ * \retval true, when the top frame have already parsed:
+ * mp_stack_top()::\a curr >= mp_stack_top()::\a 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
More information about the Tarantool-patches
mailing list