Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Fix RubyNonConcurrentPriorityQueue#delete method #905

Merged
merged 1 commit into from Jun 4, 2021

Conversation

andrykonchin
Copy link
Contributor

Close #872

The issue is that #delete method assumes that deleted element is always "greater" than the last array element and tries to find a proper place in a subtree. But actually the deleted element can be "smaller" and we need to swap it with some parent node.

Example

Let's consider an example:
[2, 1, 2, 0, 1, 1, 2]

   2
  /  \
 1    2
/ \  / \
0 1  1  2

After deleting element 0 we have the following incorrect array:

[2, 1, 2, 2, 1, 1]

   2
  /  \
 1    2
/ \  /
2 1  1 

@andrykonchin
Copy link
Contributor Author

Some jobs fail on bundle install step with error:

Retrying fetcher due to error (2/4): Bundler::Fetcher::CertificateFailureError Could not verify the SSL certificate for https://rubygems.org/.
There is a chance you are experiencing a man-in-the-middle attack, but most likely your system doesn't have the CA certificates needed for verification. For information about OpenSSL certificates, see http://bit.ly/ruby-ssl. To connect without using SSL, edit your Gemfile sources and change 'https' to 'http'.

Looks like it's related only to Windows platform on CI and not related to the changes in the PR

@pitr-ch pitr-ch added the bug A bug in the library or documentation. label Jun 4, 2021
@pitr-ch
Copy link
Member

pitr-ch commented Jun 4, 2021

@andrykonchin Great fix, thank you!

@pitr-ch pitr-ch merged commit 663fe73 into ruby-concurrency:master Jun 4, 2021
@andrykonchin andrykonchin deleted the fix-priority-queue branch June 5, 2021 15:06
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug A bug in the library or documentation.
Projects
None yet
Development

Successfully merging this pull request may close these issues.

Concurrent::Collection::RubyNonConcurrentPriorityQueue#delete works wrong
2 participants