Skip to content

core/clist: add clist_sort()#7655

Merged
kaspar030 merged 2 commits intoRIOT-OS:masterfrom
kaspar030:add_list_sort
Nov 6, 2017
Merged

core/clist: add clist_sort()#7655
kaspar030 merged 2 commits intoRIOT-OS:masterfrom
kaspar030:add_list_sort

Conversation

@kaspar030
Copy link
Copy Markdown
Contributor

@kaspar030 kaspar030 commented Sep 28, 2017

This PR adds a function that sorts clists, using a stable merge-sort algorithm that runs in O(N log N) best-case and worst-case.

The actual sorting code is BSD-licensed (taken from https://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html).

@kaspar030 kaspar030 added Area: core Area: RIOT kernel. Handle PRs marked with this with care! Type: enhancement The issue suggests enhanceable parts / The PR enhances parts of the codebase / documentation CI: ready for build If set, CI server will compile all applications for all available boards for the labeled PR labels Sep 28, 2017
smlng
smlng suggested changes Sep 28, 2017
View reviewed changes
Copy link
Copy Markdown
Member

@smlng smlng left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

minor nits

core/clist.c Outdated
* @{
*
* @file
* @brief clist helper implentations
Copy link
Copy Markdown
Member

@smlng smlng Sep 28, 2017

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

/implentations/implementations/

Copy link
Copy Markdown
Contributor Author

@kaspar030 kaspar030 Sep 30, 2017

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

fixed

core/clist.c Outdated
psize = 0;
for (i = 0; i < insize; i++) {
psize++;
q = (q->next == oldhead ? NULL : q->next);
Copy link
Copy Markdown
Member

@smlng smlng Sep 28, 2017

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I would place parentheses around the condition, i.e., (q->next == oldhead)

Copy link
Copy Markdown
Contributor Author

@kaspar030 kaspar030 Sep 30, 2017

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Yup.

@smlng
Copy link
Copy Markdown
Member

smlng commented Oct 2, 2017

Please fix issues reported by Murdock, and also squash - pre-ACK.

@jnohlgard
Copy link
Copy Markdown
Member

jnohlgard commented Oct 2, 2017

Sorry, I don't have time to review this at the moment.

@kaspar030
Copy link
Copy Markdown
Contributor Author

kaspar030 commented Oct 2, 2017

Please fix issues reported by Murdock

done

@kaspar030 kaspar030 added CI: ready for build If set, CI server will compile all applications for all available boards for the labeled PR and removed CI: ready for build If set, CI server will compile all applications for all available boards for the labeled PR labels Oct 4, 2017
@OlegHahm
Copy link
Copy Markdown
Member

OlegHahm commented Oct 4, 2017

kaspar030 added Ready for CI build Ready for CI build Ready for CI build and removed Ready for CI build Ready for CI build Ready for CI build labels 5 hours ago

lol

What is the motivation for this PR?

@kaspar030
Copy link
Copy Markdown
Contributor Author

kaspar030 commented Oct 10, 2017

What is the motivation for this PR?

Needed this for a pet project...

Also I'm trying to fill the feature gap between clist & utlist. (#6209)

@kaspar030
Copy link
Copy Markdown
Contributor Author

kaspar030 commented Oct 10, 2017

pre-ACK.

I think all comments were addressed. @smlng you good?

@kaspar030
Copy link
Copy Markdown
Contributor Author

kaspar030 commented Oct 16, 2017

I think all comments were addressed. @smlng you good?

ping might have slipped through the release already...

@kaspar030 kaspar030 mentioned this pull request Oct 19, 2017
Merged
@kaspar030 kaspar030 added Type: new feature The issue requests / The PR implemements a new feature for RIOT and removed Type: enhancement The issue suggests enhanceable parts / The PR enhances parts of the codebase / documentation labels Oct 24, 2017
@kaspar030
Copy link
Copy Markdown
Contributor Author

kaspar030 commented Nov 6, 2017

@smlng ping you've basically already ACK'ed this. :)

@smlng
Copy link
Copy Markdown
Member

smlng commented Nov 6, 2017

ah sorry, for the delay ...

@kaspar030 kaspar030 removed the CI: ready for build If set, CI server will compile all applications for all available boards for the labeled PR label Nov 6, 2017
@kaspar030 kaspar030 added the CI: ready for build If set, CI server will compile all applications for all available boards for the labeled PR label Nov 6, 2017
@kaspar030
Copy link
Copy Markdown
Contributor Author

kaspar030 commented Nov 6, 2017

&go.

Thanks @smlng!

@kaspar030 kaspar030 merged commit f142908 into RIOT-OS:master Nov 6, 2017
@kaspar030 kaspar030 deleted the add_list_sort branch November 6, 2017 11:46
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@jnohlgard jnohlgard Awaiting requested review from jnohlgard

@cgundogan cgundogan Awaiting requested review from cgundogan

1 more reviewer

@smlng smlng smlng approved these changes

Reviewers whose approvals may not affect merge requirements

Assignees

@smlng smlng

Labels

Area: core Area: RIOT kernel. Handle PRs marked with this with care! CI: ready for build If set, CI server will compile all applications for all available boards for the labeled PR Type: new feature The issue requests / The PR implemements a new feature for RIOT

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

4 participants

@kaspar030 @smlng @jnohlgard @OlegHahm