Skip to content
GitLab
Projects Groups Snippets
  • /
  • Help
    • Help
    • Support
    • Community forum
    • Submit feedback
    • Contribute to GitLab
  • Register
  • Sign in
  • G GLib
  • Project information
    • Project information
    • Activity
    • Labels
    • Members
  • Repository
    • Repository
    • Files
    • Commits
    • Branches
    • Tags
    • Contributors
    • Graph
    • Compare
  • Issues 856
    • Issues 856
    • List
    • Boards
    • Service Desk
    • Milestones
  • Merge requests 56
    • Merge requests 56
  • CI/CD
    • CI/CD
    • Pipelines
    • Jobs
    • Schedules
  • Deployments
    • Deployments
    • Releases
  • Packages and registries
    • Packages and registries
    • Container Registry
  • Analytics
    • Analytics
    • Value stream
    • CI/CD
    • Repository
  • Wiki
    • Wiki
  • Snippets
    • Snippets
  • Activity
  • Graph
  • Create a new issue
  • Jobs
  • Commits
  • Issue Boards
Collapse sidebar
  • GNOMEGNOME
  • GLib
  • Merge requests
  • !2327
The source project of this merge request has been removed.

guri: Improve performance of remove_dot_segments() algorithm

Merged Sebastian Wilhelmi requested to merge (removed):main into main Nov 10, 2021
  • Overview 33
  • Pipelines 0
  • Changes 2

Replace the remove_dot_segments algorithm with quadratic time complexity with the linear complexity RFC algorithm

The current remove_dot_segments algorithm has quadratic time complexity, which causes fuzzing to fail with certain large inputs.

Instead we can simply implement the pseudo algorithm from the actual RFC, which is linear and can still operate in place.

Closes: #2526 (closed)

Edited Nov 17, 2021 by Philip Withnall
Assignee
Assign to
Reviewers
Request review from
Time tracking
Source branch: main