search

php-ds / ext-ds

An extension providing efficient data structures for PHP 7
https://medium.com/p/9dda7af674cd
MIT License
2.11k stars 95 forks source link

Global compare FCI should be saved and restored (allowing nested comparators) #48

Open rtheunissen opened 8 years ago

rtheunissen commented 8 years ago

All structures share the same global FCI, so if while sorting something you try to sort something else, things will break. The best way to handle this is to save the current FCI, use it, then restore it.

nikic commented 8 years ago

Why does this need a global at all?

rtheunissen commented 8 years ago

Because we need to call a user function inside a comparator (C function pointer).

nikic commented 8 years ago

Why can't it be passed along as a context pointer? As you aren't using zend_hash_sort, you shouldn't be limited by a context-free comparator.

rtheunissen commented 8 years ago

I don't believe qsort supports a context parameter.

nikic commented 8 years ago

Huh, you're right. I could have sworn there was a qsort_ex variant, but looks like there isn't :(

rtheunissen commented 8 years ago

There is, but it's not standard. I wonder how plausible it is to implement quick sort manually.

morrisonlevi commented 7 years ago

There are two variants commonly found: qsort_r and qsort_s. Sadly the APIs aren't quite the same even though they are supporting the same idea: add a context parameter.

Perhaps we could use this: https://github.com/noporpoise/sort_r. It is in the public domain, so no issue there.

rtheunissen commented 7 years ago

@morrisonlevi interesting idea, would be very easy to just nab that header file and include it. I like.

rtheunissen commented 5 years ago

Coming back to this 2 years later, do we think that a third party sort is still the way to go?

rtheunissen commented 5 years ago

@morrisonlevi the sort_r lib you linked falls back to their own quicksort implementation, but uses qsort_r if it is available. Seems reasonable to me to just include that header then. Might look for some others too..