Sorting routines. More...

#include "sort.h"

Typedefs
typedef short(*	inf_ptr )(const mu_ent const restrict, const mu_ent const restrict)
	sort function pointer type

Functions
static short	inf_by_rand (const mu_ent const restrict first, const mu_ent const restrict second)
static short	inf_by_track (const mu_ent const restrict first, const mu_ent const restrict second)
static short	inf_by_posn (const mu_ent const restrict first, const mu_ent const restrict second)
static short	inf_by_date (const mu_ent const restrict first, const mu_ent const restrict second)
static short	inf_by_length (const mu_ent const restrict first, const mu_ent const restrict second)
static short	inf_by_bitrate (const mu_ent const restrict first, const mu_ent const restrict second)
static short	inf_by_freq (const mu_ent const restrict first, const mu_ent const restrict second)
	Sorts by samplerate.
static short	inf_by_size (const mu_ent const restrict first, const mu_ent const restrict second)
static short	inf_by_mtime (const mu_ent const restrict first, const mu_ent const restrict second)
	Sorts by mtime.
static short	inf_by_artist (const mu_ent const restrict first, const mu_ent const restrict second)
static short	inf_by_album (const mu_ent const restrict first, const mu_ent const restrict second)
static short	inf_by_title (const mu_ent const restrict first, const mu_ent const restrict second)
static short	inf_by_filetype (const mu_ent const restrict first, const mu_ent const restrict second)
static short	inf_by_file (const mu_ent const restrict first, const mu_ent const restrict second)
static short	inf_by_uri (const mu_ent const restrict first, const mu_ent const restrict second)
static short	inf_by_genre (const mu_ent const restrict first, const mu_ent const restrict second)
static short	inf_by_dir (const mu_ent const restrict first, const mu_ent const restrict second)
static short	inf_global (const mu_ent const first, const mu_ent const second, const unsigned char *const order)
void	sort_mergesort (mu_pack const pack, const unsigned char const order)
	Sorts the list of musical entries.
static short	inf_global (const mu_ent const first, const mu_ent const second, const unsigned char *const restrict order)
	Returns the "difference" between 2 entries.

Variables
static const inf_ptr const	sort_order_functions []
	This array is used in conjonction with mu_config->order which acts as a hash table for the user to specify their desired sort order.

Detailed Description

Sorting routines.

All the functions in this file are time-critical. They will be used very extensively during any module operation.

To ensure stability, inf_by_*() functions must return a <= 0 number if first is equal to second.

Author: Regis Boudin; Thibaut Varene

Version

Revision:: 862

Date: 2003-2004; 2007-2008

Todo:: review int types

Definition in file sort.c.

Typedef Documentation

typedef short(* inf_ptr)(const mu_ent *const restrict, const mu_ent *const restrict)

sort function pointer type

Definition at line 126 of file sort.c.

Function Documentation

static short inf_by_album	(	const mu_ent *const restrict	first,
		const mu_ent *const restrict	second
	)

inlinestatic

Definition at line 359 of file sort.c.

References likely.

static short inf_by_artist	(	const mu_ent *const restrict	first,
		const mu_ent *const restrict	second
	)

inlinestatic

Definition at line 349 of file sort.c.

References likely.

static short inf_by_bitrate	(	const mu_ent *const restrict	first,
		const mu_ent *const restrict	second
	)

inlinestatic

Definition at line 312 of file sort.c.

static short inf_by_date	(	const mu_ent *const restrict	first,
		const mu_ent *const restrict	second
	)

inlinestatic

Definition at line 302 of file sort.c.

static short inf_by_dir	(	const mu_ent *const restrict	first,
		const mu_ent *const restrict	second
	)

inlinestatic

Definition at line 401 of file sort.c.

static short inf_by_file	(	const mu_ent *const restrict	first,
		const mu_ent *const restrict	second
	)

inlinestatic

Definition at line 380 of file sort.c.

static short inf_by_filetype	(	const mu_ent *const restrict	first,
		const mu_ent *const restrict	second
	)

inlinestatic

Definition at line 375 of file sort.c.

static short inf_by_freq	(	const mu_ent *const restrict	first,
		const mu_ent *const restrict	second
	)

inlinestatic

Sorts by samplerate.

Parameters

first	first
second	second

Returns: order

Definition at line 324 of file sort.c.

static short inf_by_genre	(	const mu_ent *const restrict	first,
		const mu_ent *const restrict	second
	)

inlinestatic

Definition at line 390 of file sort.c.

References likely.

static short inf_by_length	(	const mu_ent *const restrict	first,
		const mu_ent *const restrict	second
	)

inlinestatic

Definition at line 307 of file sort.c.

static short inf_by_mtime	(	const mu_ent *const restrict	first,
		const mu_ent *const restrict	second
	)

inlinestatic

Sorts by mtime.

Sort order is inverted here (decreasing), since it wouldn't make sense to have "oldest" entries first.

Parameters

first	first
second	second

Returns: order

Definition at line 343 of file sort.c.

static short inf_by_posn	(	const mu_ent *const restrict	first,
		const mu_ent *const restrict	second
	)

inlinestatic

Definition at line 297 of file sort.c.

static short inf_by_rand	(	const mu_ent *const restrict	first,
		const mu_ent *const restrict	second
	)

inlinestatic

Definition at line 287 of file sort.c.

static short inf_by_size	(	const mu_ent *const restrict	first,
		const mu_ent *const restrict	second
	)

inlinestatic

Definition at line 329 of file sort.c.

static short inf_by_title	(	const mu_ent *const restrict	first,
		const mu_ent *const restrict	second
	)

inlinestatic

Definition at line 370 of file sort.c.

Referenced by inf_global().

static short inf_by_track	(	const mu_ent *const restrict	first,
		const mu_ent *const restrict	second
	)

inlinestatic

Definition at line 292 of file sort.c.

static short inf_by_uri	(	const mu_ent *const restrict	first,
		const mu_ent *const restrict	second
	)

inlinestatic

Definition at line 385 of file sort.c.

static short inf_global	(	const mu_ent *const	first,
		const mu_ent *const	second,
		const unsigned char *const	order
	)

inlinestatic

Referenced by sort_mergesort().

static short inf_global	(	const mu_ent *const	first,
		const mu_ent *const	second,
		const unsigned char *const restrict	order
	)

inlinestatic

Returns the "difference" between 2 entries.

If one entry is a dir, put it first. If both are, sort them by alpahbetic order. Then, compare according to each different parameter designed.

Optimizations:
This function should be tuned as much as possible, it's the one doing all the dirty work while sorting.

Passing the order pointer instead of 'conf' saves a couple dereference.
Asserting that order is always 'NULL' terminated and that it will never trigger an out of bound access saves us another numerical check.
Right now we're not keeping track of which entry in the array actually gave us a valid result. This might leave room for more optimization.
We've switched from a 4 tests filetype check to a 3 tests one.
In order to enforce the restrict contract, this function MUST make sure that first != second before calling subsequent inf_*() functions.

Warning: Values within order param should NEVER trigger an out of bound access in sort_order_functions. Checking for that would add too much overhead when we're trying to reduce it, and we have placed enough checks everywhere to be reasonably certain that this will never happen.

Parameters

first	The first entry
second	The second entry
order	The order hash table for the inf_by functions array

Returns: The difference between entries (<0 means first is "before" second)

Definition at line 451 of file sort.c.

References mu_ent::filetype, inf_by_title(), sort_order_functions, and unlikely.

void sort_mergesort	(	mu_pack *const	pack,
		const unsigned char *const	order
	)

Sorts the list of musical entries.

This is a home-made, non-recursive, mergesort implementation.

It presents several advantages over quicksort:

Since we're sorting a linked list, we can merge in place, meaning the drawback of mergesort goes away (the need to use twice the space)
It's a non-recursive implementation, meaning it won't pollute the stack, which is already a major performance gain
It's mergesort, so it will perform in O(n*logn) in ALL cases.
As an added bonus, it's stable (meaning it will not swap two already sorted elements, so it can handle the case where it's impossible to differentiate two elements based on sort order.

Given the implementation of inf_global(), directories will always be at the top of the pack.

Parameters

pack	The pack to be sorted
order	The order hash table for the inf_by functions array

Returns: The pack, sorted

Definition at line 181 of file sort.c.

References mu_pack::dirnb, mu_pack::fhead, mu_pack::filenb, mu_ent::filetype, mu_pack::head, inf_global(), likely, and mu_ent::next.

Variable Documentation

const inf_ptr const sort_order_functions[]

static

Initial value:

 {
        NULL,
        inf_by_album,
        inf_by_posn,
        inf_by_track,
        inf_by_artist,
        inf_by_title,
        inf_by_length,
        inf_by_bitrate,
        inf_by_freq,
        inf_by_filetype,
        inf_by_file,
        inf_by_uri,
        inf_by_genre,
        inf_by_date,
        inf_by_size,
        inf_by_mtime,
        inf_by_rand,
        inf_by_dir,
        NULL,
}

This array is used in conjonction with mu_config->order which acts as a hash table for the user to specify their desired sort order.

Warning: BEWARE: this array must be kept in sync with the enum in mod_musicindex.h The current order is such that the default sort order accesses this array in a linear order.

Definition at line 136 of file sort.c.

Referenced by inf_global().

Typedefs

Functions

Variables

Detailed Description

Typedef Documentation

Function Documentation

Variable Documentation