Use new sorting mechanism.
Switch the pending job sorting mechanism the new topological-sort-like
mechanism. The new system is generally more efficient and easier to
maintain than the previous implementation and allows for further
improvements such as batching in the queue (to reduce process restarts).
Runtime changes (A=# of apps, J=average # jobs per app):
Previous implementation New implementation
Sorting: A*J*log(A*J) A*J*log(J)
Insertion: log(A*J) log(A*J)+J
Remove(Object): A*J log(A*J)
Iteration: A*J A*J (amortized)
Contains: A*J log(A*J)
Bug: 141645789
Bug: 204924801
Bug: 223437753
Test: atest frameworks/base/services/tests/servicestests/src/com/android/server/job
Test: atest frameworks/base/services/tests/mockingservicestests/src/com/android/server/job
Test: atest CtsJobSchedulerTestCases
Change-Id: I61cf8488d574e3c7be624b753a02e8c1f151f4fd
3 files changed