Uploaded image for project: 'Qpid Proton'
  1. Qpid Proton
  2. PROTON-1984

[c] pn_data_inspect has order n^2 running time

    Details

    • Type: Bug
    • Status: Closed
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: proton-c-0.27.0
    • Component/s: proton-c
    • Labels:
      None

      Description

      pni_node_index which is used in a couple of places to find out the index of a node inside a pn_data_t has a run time that is linear in the size of the level of the pn_data_t it is at.

      pni_inspect_enter and pni_inspect_exit which are called for every node in the pn_data_t when traversing it using pn_data_inspect use pni_node_index. This means that the overall time complexity is n^2 in the size of any embedded compound data structure (array, list, map).

      So for large compound data structures this can take an extremely long time.

        Attachments

          Activity

            People

            • Assignee:
              astitcher Andrew Stitcher
              Reporter:
              astitcher Andrew Stitcher
            • Votes:
              0 Vote for this issue
              Watchers:
              2 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved: