Replace insertion sort with hpsort in our kernel's qsort() function.
AbandonedPublic
Actions

Authored by • hselasky on Feb 10 2016, 12:15 PM.

Tags

None

Referenced Files

	F81589382: D5241.diff
	Thu, Apr 18, 2:26 PM

	Unknown Object (File)
	Tue, Apr 16, 10:48 AM

	Unknown Object (File)
	Mar 15 2024, 8:21 PM

	Unknown Object (File)
	Mar 15 2024, 7:19 PM

	Unknown Object (File)
	Dec 22 2023, 11:22 PM

	Unknown Object (File)
	Nov 18 2023, 5:10 AM

	Unknown Object (File)
	Nov 1 2023, 5:17 PM

	Unknown Object (File)
	Jun 3 2023, 5:27 PM

View All 34 Files

Subscribers

imp

Details

Reviewers

rrs
gnn

Diff Detail

Repository

rS FreeBSD src repository - subversion

Lint

Lint Skipped

Unit

Tests Skipped

Event Timeline

• hselasky updated this revision to Diff 13178.Feb 10 2016, 12:15 PM

• hselasky retitled this revision from to Document the characteristics of our qsort() function..

• hselasky updated this object.

• hselasky edited the test plan for this revision. (Show Details)

• hselasky set the repository for this revision to rS FreeBSD src repository - subversion.

Herald added a subscriber: imp. · View Herald TranscriptFeb 10 2016, 12:15 PM

• hselasky added reviewers: rrs, gnn.Mar 31 2016, 9:17 AM

Don't use insertion sort which is O(N*N)

Use hpsort instead which is O(log2(N)*log2(N)*N).

I'm in private conversation with hps@ about this proposal.

This revision now requires changes to proceed.Apr 20 2016, 1:41 PM

• hselasky abandoned this revision.May 20 2016, 1:16 PM

Revision Contents
Changeset List

Path

Size

sys/

libkern/

qsort.c

130 lines

sys/

libkern.h

4 lines

Diff 15373

View Options

sys/libkern/qsort.c