[tarantool-patches] [PATCH v5 2/9] lib: implement JSON tree class for json library

[Vladimir Davydov]

On Thu, Nov 29, 2018 at 08:38:16PM +0300, Vladimir Davydov wrote:
> On Mon, Nov 26, 2018 at 03:53:03PM +0300, Kirill Shcherbatov wrote:
> > +int
> > +json_tree_add(struct json_tree *tree, struct json_token *parent,
> > +	      struct json_token *token)
> > +{
> > +	if (parent == NULL)
> > +		parent = &tree->root;
> > +	uint32_t rolling_hash =
> > +	       json_token_hash(token, parent->rolling_hash);
> > +	assert(json_tree_lookup(tree, parent, token) == NULL);
> > +	uint32_t insert_idx = (token->key.type == JSON_TOKEN_NUM) ?
> > +			      (uint32_t)token->key.num - 1 :
> > +			      parent->child_size;
> > +	if (insert_idx >= parent->child_size) {
> > +		uint32_t new_size =
> > +			parent->child_size == 0 ? 1 : 2 * parent->child_size;
> > +		while (insert_idx >= new_size)
> > +			new_size *= 2;
> > +		struct json_token **children =
> > +			realloc(parent->children, new_size*sizeof(void *));
> > +		if (unlikely(children == NULL))
> > +			return -1;
> > +		memset(children + parent->child_size, 0,
> > +		       (new_size - parent->child_size)*sizeof(void *));
> > +		parent->children = children;
> > +		parent->child_size = new_size;
> 
> Ouch, this looks much more complex than it was in the previous version.
> Please revert. Quoting myself:
> 
> } > +     if (insert_idx >= parent->children_count) {
> } > +             uint32_t new_size = insert_idx + 1;
> } 
> } We usually double the size with each allocation. If this is intentional,
> } please add a comment.
> 
> I didn't push you to change that. I just wanted you to add a comment
> saying that we can afford quadratic algorithmic complexity here, because
> this function is far from a hot path and we expect the tree to be rather
> small.

Come to think of it, don't bother. Doubling the array will probably
increases chances that the allocation will stay close to the node
itself, and it looks saner in a common sense. Let's please just rename
child_size to child_count_max and increase the initial allocation up to
say 8, OK?