MySQL Bugs: #74426: Switch to a template-based queue/heap

Bug #74426	Switch to a template-based queue/heap
Submitted:	17 Oct 2014 9:15	Modified:	30 Oct 2014 17:24
Reporter:	Tor Didriksen	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: Compiling	Severity:	S3 (Non-critical)
Version:	5.7	OS:	Any
Assigned to:		CPU Architecture:	Any

View
Add Comment
Files
Developer
Edit Submission
View Progress Log
Contributions

Description:
Our QUEUE implementation should be replaced by a templatized C++ version.
Templatized heaps are
 - type safe
 - easier to read/maintain
 - faster

How to repeat:
Read the code.

Suggested fix:
For performance reasons, we need a mutable heap, hence std::priority_queue is not applicable.
We could have used one of the Boost heaps:
http://www.boost.org/doc/libs/1_55_0/doc/html/heap/concepts.html
http://www.boost.org/doc/libs/1_55_0/doc/html/heap/data_structures.html

However, the mutable heaps are all node based, and do not scale well.

Solution: implement our own Priority_queue.

Fixed in 5.7.6. Code cleanup. No changelog entry needed.