From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Date: Thu, 29 Nov 2018 20:50:57 +0300 From: Vladimir Davydov Subject: Re: [tarantool-patches] [PATCH v5 2/9] lib: implement JSON tree class for json library Message-ID: <20181129175057.gy4gqxdvej63f7sm@esperanza> References: <02671a3d0a2236ecd6e12c0bc51b7f5e39272a2f.1543229303.git.kshcherbatov@tarantool.org> <20181129173816.kprfjhki5o7ytfbl@esperanza> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20181129173816.kprfjhki5o7ytfbl@esperanza> To: Kirill Shcherbatov Cc: tarantool-patches@freelists.org, Kostya Osipov List-ID: 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?