diff options
Diffstat (limited to 'app/models/namespaces/traversal/linear.rb')
-rw-r--r-- | app/models/namespaces/traversal/linear.rb | 27 |
1 files changed, 27 insertions, 0 deletions
diff --git a/app/models/namespaces/traversal/linear.rb b/app/models/namespaces/traversal/linear.rb index 1963745cf4d..6320e0bc39d 100644 --- a/app/models/namespaces/traversal/linear.rb +++ b/app/models/namespaces/traversal/linear.rb @@ -49,6 +49,33 @@ module Namespaces before_commit :sync_traversal_ids, on: [:create], if: -> { sync_traversal_ids? } end + class_methods do + # This method looks into a list of namespaces trying to optimise a returned traversal_ids + # into a list of shortest prefixes, due to fact that the shortest prefixes include all childrens. + # Example: + # INPUT: [[4909902], [4909902,51065789], [4909902,51065793], [7135830], [15599674, 1], [15599674, 1, 3], [15599674, 2]] + # RESULT: [[4909902], [7135830], [15599674, 1], [15599674, 2]] + def shortest_traversal_ids_prefixes + raise ArgumentError, 'Feature not supported since the `:use_traversal_ids` is disabled' unless use_traversal_ids? + + prefixes = [] + + # The array needs to be sorted (O(nlogn)) to ensure shortest elements are always first + # This allows to do O(n) search of shortest prefixes + all_traversal_ids = all.order('namespaces.traversal_ids').pluck('namespaces.traversal_ids') + last_prefix = [nil] + + all_traversal_ids.each do |traversal_ids| + next if last_prefix == traversal_ids[0..(last_prefix.count - 1)] + + last_prefix = traversal_ids + prefixes << traversal_ids + end + + prefixes + end + end + def sync_traversal_ids? Feature.enabled?(:sync_traversal_ids, root_ancestor, default_enabled: :yaml) end |