search

ruby-concurrency / concurrent-ruby

Modern concurrency tools including agents, futures, promises, thread pools, supervisors, and more. Inspired by Erlang, Clojure, Scala, Go, Java, JavaScript, and classic concurrency patterns.
https://ruby-concurrency.github.io/concurrent-ruby/
Other
5.68k stars 418 forks source link

Fix RubyNonConcurrentPriorityQueue#delete method #905

Closed andrykonchin closed 3 years ago

andrykonchin commented 3 years ago

Close https://github.com/ruby-concurrency/concurrent-ruby/issues/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 commented 3 years ago

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 commented 3 years ago

@andrykonchin Great fix, thank you!