You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@qpid.apache.org by as...@apache.org on 2018/12/20 03:32:25 UTC
[qpid-proton] 02/02: PROTON-1984: [c] Avoid O(n^2) complexity in
pn_data_inspect - Rework original change to preserve correct stringifying
of pn_data_t - Unfortunately restores some potential O(n^2) behaviour but
in many fewer cases.
This is an automated email from the ASF dual-hosted git repository.
astitcher pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/qpid-proton.git
commit b456360bf26fda5cf787bb1f7cc480bbc5103127
Author: Andrew Stitcher <as...@apache.org>
AuthorDate: Wed Dec 19 14:45:26 2018 -0500
PROTON-1984: [c] Avoid O(n^2) complexity in pn_data_inspect
- Rework original change to preserve correct stringifying of pn_data_t
- Unfortunately restores some potential O(n^2) behaviour but in many
fewer cases.
This reverts commit 58ec2b1e54d00fce4a07b7c3c6de2b504b2525ee.
---
c/src/core/codec.c | 63 +++++++++++++++++++++++++++++-----------------------
c/src/core/data.h | 4 ++--
c/src/core/encoder.c | 6 ++---
3 files changed, 39 insertions(+), 34 deletions(-)
diff --git a/c/src/core/codec.c b/c/src/core/codec.c
index 1a01bb2..f8608a1 100644
--- a/c/src/core/codec.c
+++ b/c/src/core/codec.c
@@ -237,10 +237,20 @@ int pni_inspect_atom(pn_atom_t *atom, pn_string_t *str)
}
}
-int pni_inspect_enter(void *ctx, pn_data_t *data, pni_nid_t index)
+/* Return index in current list, array etc.*/
+static int pni_node_lindex(pn_data_t *data, pni_node_t *node)
+{
+ int count = 0;
+ while (node) {
+ node = pn_data_node(data, node->prev);
+ count++;
+ }
+ return count - 1;
+}
+
+int pni_inspect_enter(void *ctx, pn_data_t *data, pni_node_t *node)
{
pn_string_t *str = (pn_string_t *) ctx;
- pni_node_t *node = pn_data_node(data, index);
pn_atom_t *atom = (pn_atom_t *) &node->atom;
pni_node_t *parent = pn_data_node(data, node->parent);
@@ -254,8 +264,9 @@ int pni_inspect_enter(void *ctx, pn_data_t *data, pni_nid_t index)
if (atom->type == PN_NULL) {
return 0;
}
- const char *name = (index < grandfields->field_count)
- ? (const char*)FIELD_STRINGPOOL.STRING0+FIELD_FIELDS[grandfields->first_field_index+index]
+ pni_nid_t lindex = pni_node_lindex(data, node);
+ const char *name = (lindex < grandfields->field_count)
+ ? (const char*)FIELD_STRINGPOOL.STRING0+FIELD_FIELDS[grandfields->first_field_index+lindex]
: NULL;
if (name) {
err = pn_string_addf(str, "%s=", name);
@@ -274,7 +285,7 @@ int pni_inspect_enter(void *ctx, pn_data_t *data, pni_nid_t index)
case PN_MAP:
return pn_string_addf(str, "{");
default:
- if (fields && index == 0) {
+ if (fields && node->prev == 0) {
err = pn_string_addf(str, "%s", (const char *)FIELD_STRINGPOOL.STRING0+FIELD_NAME[fields->name_index]);
if (err) return err;
err = pn_string_addf(str, "(");
@@ -300,14 +311,9 @@ pni_node_t *pni_next_nonnull(pn_data_t *data, pni_node_t *node)
return NULL;
}
-int pni_inspect_exit(void *ctx, pn_data_t *data, pni_nid_t index)
+int pni_inspect_exit(void *ctx, pn_data_t *data, pni_node_t *node)
{
pn_string_t *str = (pn_string_t *) ctx;
- pni_node_t *node = pn_data_node(data, index);
- pni_node_t *parent = pn_data_node(data, node->parent);
- pni_node_t *grandparent = parent ? pn_data_node(data, parent->parent) : NULL;
- const pn_fields_t *grandfields = pni_node_fields(data, grandparent);
- pni_node_t *next = pn_data_node(data, node->next);
int err;
switch (node->atom.type) {
@@ -324,11 +330,14 @@ int pni_inspect_exit(void *ctx, pn_data_t *data, pni_nid_t index)
break;
}
+ pni_node_t *parent = pn_data_node(data, node->parent);
+ pni_node_t *grandparent = parent ? pn_data_node(data, parent->parent) : NULL;
+ const pn_fields_t *grandfields = pni_node_fields(data, grandparent);
if (!grandfields || node->atom.type != PN_NULL) {
- if (next) {
- if (parent && parent->atom.type == PN_MAP && (index % 2) == 0) {
+ if (node->next) {
+ if (parent && parent->atom.type == PN_MAP && (pni_node_lindex(data, node) % 2) == 0) {
err = pn_string_addf(str, "=");
- } else if (parent && parent->atom.type == PN_DESCRIBED && index == 0) {
+ } else if (parent && parent->atom.type == PN_DESCRIBED && node->prev == 0) {
err = pn_string_addf(str, " ");
if (err) return err;
} else {
@@ -1313,42 +1322,40 @@ bool pn_data_prev(pn_data_t *data)
}
int pni_data_traverse(pn_data_t *data,
- int (*enter)(void *ctx, pn_data_t *data, pni_nid_t index),
- int (*exit)(void *ctx, pn_data_t *data, pni_nid_t index),
+ int (*enter)(void *ctx, pn_data_t *data, pni_node_t *node),
+ int (*exit)(void *ctx, pn_data_t *data, pni_node_t *node),
void *ctx)
{
- pni_nid_t index = data->size ? 1 : 0;
- while (index!=0) {
- pni_node_t *node = pn_data_node(data, index);
+ pni_node_t *node = data->size ? pn_data_node(data, 1) : NULL;
+ while (node) {
+ pni_node_t *parent = pn_data_node(data, node->parent);
- int err = enter(ctx, data, index);
+ int err = enter(ctx, data, node);
if (err) return err;
size_t next = 0;
if (node->down) {
next = node->down;
} else if (node->next) {
- err = exit(ctx, data, index);
+ err = exit(ctx, data, node);
if (err) return err;
next = node->next;
} else {
- err = exit(ctx, data, index);
+ err = exit(ctx, data, node);
if (err) return err;
- pni_nid_t parenti = node->parent;
- while (parenti) {
- err = exit(ctx, data, parenti);
+ while (parent) {
+ err = exit(ctx, data, parent);
if (err) return err;
- pni_node_t *parent = pn_data_node(data, parenti);
if (parent->next) {
next = parent->next;
break;
} else {
- parenti = parent->parent;
+ parent = pn_data_node(data, parent->parent);
}
}
}
- index = next;
+ node = pn_data_node(data, next);
}
return 0;
diff --git a/c/src/core/data.h b/c/src/core/data.h
index 454ec55..94dc7d6 100644
--- a/c/src/core/data.h
+++ b/c/src/core/data.h
@@ -68,8 +68,8 @@ static inline pni_node_t * pn_data_node(pn_data_t *data, pni_nid_t nd)
}
int pni_data_traverse(pn_data_t *data,
- int (*enter)(void *ctx, pn_data_t *data, pni_nid_t index),
- int (*exit)(void *ctx, pn_data_t *data, pni_nid_t index),
+ int (*enter)(void *ctx, pn_data_t *data, pni_node_t *node),
+ int (*exit)(void *ctx, pn_data_t *data, pni_node_t *node),
void *ctx);
#endif /* data.h */
diff --git a/c/src/core/encoder.c b/c/src/core/encoder.c
index 43afe43..505db47 100644
--- a/c/src/core/encoder.c
+++ b/c/src/core/encoder.c
@@ -254,10 +254,9 @@ typedef union {
double d;
} conv_t;
-static int pni_encoder_enter(void *ctx, pn_data_t *data, pni_nid_t index)
+static int pni_encoder_enter(void *ctx, pn_data_t *data, pni_node_t *node)
{
pn_encoder_t *encoder = (pn_encoder_t *) ctx;
- pni_node_t *node = pn_data_node(data, index);
pni_node_t *parent = pn_data_node(data, node->parent);
pn_atom_t *atom = &node->atom;
uint8_t code;
@@ -345,10 +344,9 @@ static int pni_encoder_enter(void *ctx, pn_data_t *data, pni_nid_t index)
#include <stdio.h>
-static int pni_encoder_exit(void *ctx, pn_data_t *data, pni_nid_t index)
+static int pni_encoder_exit(void *ctx, pn_data_t *data, pni_node_t *node)
{
pn_encoder_t *encoder = (pn_encoder_t *) ctx;
- pni_node_t *node = pn_data_node(data, index);
char *pos;
// Special case 0 length list
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@qpid.apache.org
For additional commands, e-mail: commits-help@qpid.apache.org