qpid-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From astitc...@apache.org
Subject qpid-proton git commit: PROTON-1984: [c] Avoid O(n^2) complexity in pn_data_inspect
Date Tue, 11 Dec 2018 19:24:49 GMT
Repository: qpid-proton
Updated Branches:
  refs/heads/master 3b1edb510 -> 58ec2b1e5


PROTON-1984: [c] Avoid O(n^2) complexity in pn_data_inspect


Project: http://git-wip-us.apache.org/repos/asf/qpid-proton/repo
Commit: http://git-wip-us.apache.org/repos/asf/qpid-proton/commit/58ec2b1e
Tree: http://git-wip-us.apache.org/repos/asf/qpid-proton/tree/58ec2b1e
Diff: http://git-wip-us.apache.org/repos/asf/qpid-proton/diff/58ec2b1e

Branch: refs/heads/master
Commit: 58ec2b1e54d00fce4a07b7c3c6de2b504b2525ee
Parents: 3b1edb5
Author: Andrew Stitcher <astitcher@apache.org>
Authored: Tue Dec 11 14:17:52 2018 -0500
Committer: Andrew Stitcher <astitcher@apache.org>
Committed: Tue Dec 11 14:24:12 2018 -0500

----------------------------------------------------------------------
 c/src/core/codec.c                              |  44 ++++++++-----------
 c/src/core/data.h                               |   4 +-
 c/src/core/encoder.c                            |   6 ++-
 .../crash/5691758789263360                      | Bin 0 -> 291 bytes
 4 files changed, 24 insertions(+), 30 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/qpid-proton/blob/58ec2b1e/c/src/core/codec.c
----------------------------------------------------------------------
diff --git a/c/src/core/codec.c b/c/src/core/codec.c
index 37165f5..1a01bb2 100644
--- a/c/src/core/codec.c
+++ b/c/src/core/codec.c
@@ -111,16 +111,6 @@ static const pn_fields_t *pni_node_fields(pn_data_t *data, pni_node_t
*node)
   }
 }
 
-static int pni_node_index(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_atom(pn_atom_t *atom, pn_string_t *str)
 {
   switch (atom->type) {
@@ -247,16 +237,16 @@ int pni_inspect_atom(pn_atom_t *atom, pn_string_t *str)
   }
 }
 
-int pni_inspect_enter(void *ctx, pn_data_t *data, pni_node_t *node)
+int pni_inspect_enter(void *ctx, pn_data_t *data, pni_nid_t index)
 {
   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);
   const pn_fields_t *fields = pni_node_fields(data, parent);
   pni_node_t *grandparent = parent ? pn_data_node(data, parent->parent) : NULL;
   const pn_fields_t *grandfields = pni_node_fields(data, grandparent);
-  int index = pni_node_index(data, node);
 
   int err;
 
@@ -310,9 +300,10 @@ 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_node_t *node)
+int pni_inspect_exit(void *ctx, pn_data_t *data, pni_nid_t index)
 {
   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);
@@ -335,7 +326,6 @@ int pni_inspect_exit(void *ctx, pn_data_t *data, pni_node_t *node)
 
   if (!grandfields || node->atom.type != PN_NULL) {
     if (next) {
-      int index = pni_node_index(data, node);
       if (parent && parent->atom.type == PN_MAP && (index % 2) == 0) {
         err = pn_string_addf(str, "=");
       } else if (parent && parent->atom.type == PN_DESCRIBED && index
== 0) {
@@ -1323,40 +1313,42 @@ 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_node_t *node),
-                      int (*exit)(void *ctx, pn_data_t *data, pni_node_t *node),
+                      int (*enter)(void *ctx, pn_data_t *data, pni_nid_t index),
+                      int (*exit)(void *ctx, pn_data_t *data, pni_nid_t index),
                       void *ctx)
 {
-  pni_node_t *node = data->size ? pn_data_node(data, 1) : NULL;
-  while (node) {
-    pni_node_t *parent = pn_data_node(data, node->parent);
+  pni_nid_t index = data->size ? 1 : 0;
+  while (index!=0) {
+    pni_node_t *node = pn_data_node(data, index);
 
-    int err = enter(ctx, data, node);
+    int err = enter(ctx, data, index);
     if (err) return err;
 
     size_t next = 0;
     if (node->down) {
       next = node->down;
     } else if (node->next) {
-      err = exit(ctx, data, node);
+      err = exit(ctx, data, index);
       if (err) return err;
       next = node->next;
     } else {
-      err = exit(ctx, data, node);
+      err = exit(ctx, data, index);
       if (err) return err;
-      while (parent) {
-        err = exit(ctx, data, parent);
+      pni_nid_t parenti = node->parent;
+      while (parenti) {
+        err = exit(ctx, data, parenti);
         if (err) return err;
+        pni_node_t *parent = pn_data_node(data, parenti);
         if (parent->next) {
           next = parent->next;
           break;
         } else {
-          parent = pn_data_node(data, parent->parent);
+          parenti = parent->parent;
         }
       }
     }
 
-    node = pn_data_node(data, next);
+    index = next;
   }
 
   return 0;

http://git-wip-us.apache.org/repos/asf/qpid-proton/blob/58ec2b1e/c/src/core/data.h
----------------------------------------------------------------------
diff --git a/c/src/core/data.h b/c/src/core/data.h
index 94dc7d6..454ec55 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_node_t *node),
-                      int (*exit)(void *ctx, pn_data_t *data, pni_node_t *node),
+                      int (*enter)(void *ctx, pn_data_t *data, pni_nid_t index),
+                      int (*exit)(void *ctx, pn_data_t *data, pni_nid_t index),
                       void *ctx);
 
 #endif /* data.h */

http://git-wip-us.apache.org/repos/asf/qpid-proton/blob/58ec2b1e/c/src/core/encoder.c
----------------------------------------------------------------------
diff --git a/c/src/core/encoder.c b/c/src/core/encoder.c
index 505db47..43afe43 100644
--- a/c/src/core/encoder.c
+++ b/c/src/core/encoder.c
@@ -254,9 +254,10 @@ typedef union {
   double d;
 } conv_t;
 
-static int pni_encoder_enter(void *ctx, pn_data_t *data, pni_node_t *node)
+static int pni_encoder_enter(void *ctx, pn_data_t *data, pni_nid_t index)
 {
   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;
@@ -344,9 +345,10 @@ static int pni_encoder_enter(void *ctx, pn_data_t *data, pni_node_t *node)
 
 #include <stdio.h>
 
-static int pni_encoder_exit(void *ctx, pn_data_t *data, pni_node_t *node)
+static int pni_encoder_exit(void *ctx, pn_data_t *data, pni_nid_t index)
 {
   pn_encoder_t *encoder = (pn_encoder_t *) ctx;
+  pni_node_t *node = pn_data_node(data, index);
   char *pos;
 
   // Special case 0 length list

http://git-wip-us.apache.org/repos/asf/qpid-proton/blob/58ec2b1e/c/tests/fuzz/fuzz-connection-driver/crash/5691758789263360
----------------------------------------------------------------------
diff --git a/c/tests/fuzz/fuzz-connection-driver/crash/5691758789263360 b/c/tests/fuzz/fuzz-connection-driver/crash/5691758789263360
new file mode 100644
index 0000000..df239f6
Binary files /dev/null and b/c/tests/fuzz/fuzz-connection-driver/crash/5691758789263360 differ


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@qpid.apache.org
For additional commands, e-mail: commits-help@qpid.apache.org


Mime
View raw message