search

amphp / amp

A non-blocking concurrency framework for PHP applications. 🐘
https://amphp.org/amp
MIT License
4.25k stars 257 forks source link

Add PriorityQueue #429

Closed trowski closed 8 months ago

trowski commented 10 months ago

This adds a priority queue implementation which we've copied in some form or another to use as a queue for timeouts. We're currently using a simplified version in amphp/http-server and I've used similar code in some personal and work projects. @bwoebi would now like to use this in amphp/quic without having to copy the implementation yet again, so I'm proposing we add it here.

This queue implementation provides ordering of array-keys based on an updatable priority. These array keys may then be used with a separate map to reference any other value, such as an object.

kelunik commented 10 months ago

We ship a similar implementation as Timer Queue in Revolt. Should we place it there instead?

trowski commented 10 months ago

We could, though I hesitate to provide extra tools in revolt/event-loop which aren't directly related to the loop API. We could make it a separate library under Revolt. What do you think?

trowski commented 10 months ago

Quick note: The revolt loop uses a similar class, but is tailored for TimerCallback objects and uses floats for timer expirations. We could use this implementation there, but it would require multiplying timeouts by 1000 (or more?) and a map of timer IDs to TimerCallback.

trowski commented 8 months ago

Moving this to amphp/sync instead, see https://github.com/amphp/sync/pull/27.