sort.c

Go to the documentation of this file.

/*
 *  inf.c
 *  mod_musicindex
 *
 *  $Id: sort.c 862 2009-09-01 12:58:42Z varenet $
 *
 *  Created by Thibaut VARENE on Thu Mar 20 2003.
 *  Copyright (c) 2003-2004 Regis BOUDIN
 *  Copyright (c) 2007-2008 Thibaut VARENE
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU Lesser General Public License version 2.1,
 *  as published by the Free Software Foundation.
 *
 */

/*
 * Some history on the inf_by_artist() (etc) algorithm (all comments relative to
 * code built at -O0, ie no compiler optimization):
 *
 * The initial algorithm read as follows:
 * if ((!first->artist) || (!second->artist)) {
 *              if (first->artist)
 *                      return -1;
 *              else if (second->artist)
 *                      return 1;
 *              else
 *                      return 0;
 * }
 * return (strcasecmp(first->artist, second->artist));
 *
 * This algorithm had 4 checks in the worst case condition, and 4 return points
 * and 4 conditional branches in the code stream, including one taken branch in the
 * most frequent path (we assume the most frequent case to be the one where both
 * fields are !NULL).
 * Depending on the cases, the number of checks to perform varied between 4 to 2.
 *
 * This algorith was later on reduced to:
 * if (first->artist) {
 *      if (second->artist)
 *              return strcasecmp(first->artist, second->artist);
 *      else
 *              return -1;
 * } else if (second->artist)
 *      return 1;
 * else
 *      return 0;
 *
 * This particular implementation reduced the number of checks to 2 in ALL cases
 * but still had 4 return points and 4 conditional branches. In the fast path (the
 * most frequent case), the code had 2 checks and NO taken branch.
 *
 * Then the final algorithm was implemented:
 * register short ret = -1;
 * if (first->artist)
 *      ret &= 0x1;
 * if (second->artist)
 *      ret &= ~0x1;
 * return (!ret ? strcasecmp(first->artist, second->artist) : ~ret);
 *
 * This algorithm has 3 checks in ALL cases, zero taken branch in the fast path,
 * and 3 taken branch in the worst case. It has only one return point. The generated
 * machine code is thus much more compact and much less prone to pipeline bubbles.
 * The return value is slightly different than the first algorithm (-2 instead of -1)
 * but since we're using a sort algorithm that only deals with the relative
 * position of 2 elements, it doesn't matter.
 * Also the use of short values should enable immediate loads and masks on most
 * architectures (tested on ppc).
 *
 * Of course, this algorithm is also very easy to invert if the most frequent case
 * is the "empty one":
 * register short ret = 0;
 * if (!first->artist)
 *      ret |= ~0x1;
 * if (!second->artist)
 *      ret |= 0x1;
 * return (!ret ? strcasecmp(first->artist, second->artist) : ~ret);
 */

#include "sort.h"

#ifdef HAVE_STRING_H
#include <string.h>
#endif

/* static declarations of local routines */
static inline short inf_by_rand(const mu_ent *const restrict first, const mu_ent *const restrict second);
static inline short inf_by_track(const mu_ent *const restrict first, const mu_ent *const restrict second);
static inline short inf_by_posn(const mu_ent *const restrict first, const mu_ent *const restrict second);
static inline short inf_by_date(const mu_ent *const restrict first, const mu_ent *const restrict second);
static inline short inf_by_length(const mu_ent *const restrict first, const mu_ent *const restrict second);
static inline short inf_by_bitrate(const mu_ent *const restrict first, const mu_ent *const restrict second);
static inline short inf_by_freq(const mu_ent *const restrict first, const mu_ent *const restrict second);
static inline short inf_by_size(const mu_ent *const restrict first, const mu_ent *const restrict second);
static inline short inf_by_mtime(const mu_ent *const restrict first, const mu_ent *const restrict second);
static inline short inf_by_artist(const mu_ent *const restrict first, const mu_ent *const restrict second);
static inline short inf_by_album(const mu_ent *const restrict first, const mu_ent *const restrict second);
static inline short inf_by_title(const mu_ent *const restrict first, const mu_ent *const restrict second);
static inline short inf_by_filetype(const mu_ent *const restrict first, const mu_ent *const restrict second);
static inline short inf_by_file(const mu_ent *const restrict first, const mu_ent *const restrict second);
static inline short inf_by_uri(const mu_ent *const restrict first, const mu_ent *const restrict second);
static inline short inf_by_genre(const mu_ent *const restrict first, const mu_ent *const restrict second);
static inline short inf_by_dir(const mu_ent *const restrict first, const mu_ent *const restrict second);
static inline short inf_global(const mu_ent *const first, const mu_ent *const second, const unsigned char *const order);

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

static const inf_ptr const sort_order_functions[] = {
        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,
};

void sort_mergesort(mu_pack *const pack, const unsigned char *const order)
{
        const mu_ent    *p,     /*< left sorted set pointer */
                        *q,     /*< right sorted set pointer */
                        *m,     /*< merge element */
                        *head = pack->head;     /*< head of the merged list */
        mu_ent          *tail;  /*< tail of the merged list */

        unsigned long   packsize,       /*< total number of elements in the list */
                        ssmsize,        /*< maximum size of the sorted sets */
                        count,          /*< number of elements left to merge */
                        psize,          /*< size of the left sorted set */
                        qsize;          /*< size of the right sorted set */

        packsize = pack->dirnb + pack->filenb;

        /* we begin with packsize sorted sets of 1 elements, merge them,
         * then double the size of the sorted sets to merge on each pass,
         * until we're left with 1 sorted set of packsize elements */
        for (ssmsize = 1; ssmsize <= packsize; ssmsize *= 2) {
                /* have both left and right sorted set begin at the last known head of the list */
                q = p = head;

                /* forget about previous head and tail as we'll set new ones */
                head = tail = NULL;

                /* start counter at packsize */
                count = packsize;

                while (count) {
                        /* move q at most ssmsize positions ahead of p */
                        for (psize=0; (psize < ssmsize) && q; psize++)
                                q = q->next;

                        /* q set has at most ssmsize elements */
                        qsize = ssmsize;

                        /* merge both sets */
                        while (psize || (qsize && q)) {
                                if (!psize) {
                                        /* p empty -> m = first elt of q */
                                        m = q;
                                        q = q->next;
                                        qsize--;
                                } else if (!qsize || !q) {
                                        /* q empty -> m = first elt of p */
                                        m = p;
                                        p = p->next;
                                        psize--;
                                } else if (inf_global(p, q, order) <= 0) {
                                        /* 1st elt of p is <= q; -> m = 1st elt of p */
                                        /* the "equal" case ensures stability */
                                        m = p;
                                        p = p->next;
                                        psize--;
                                } else {
                                        /* 1st elt of q is < p; -> m = 1st elt of q */
                                        m = q;
                                        q = q->next;
                                        qsize--;
                                }

                                /* put the merge element at the tail of the merged list */
                                if (likely(tail))
                                        tail->next = m;
                                else
                                        head = m;

                                /* update the tail pointer */
                                /* we have to deconstify, but this should be the
                                 * /only/ place where we have to */
                                tail = (mu_ent *)m;
                                
                                /* decrease the counter of elements remaining to merge */
                                count--;
                        }

                        /* at the end of this loop, p now points to where q was
                         * at the begining of the loop (that is, the head of the
                         * right sorted set), and q now points to the next left
                         * sorted set, so have p point to it as well, before we
                         * start another iteration */
                        p = q;
                }

                /* we've walked packsize elements, mark the end of this pass' list */
                tail->next = NULL;
        }

        /* At this point we have a list of packsize sorted elements */
        pack->head = head;
        
        /* In order to simplify the module's work, we're gonna mark the head of
         * songs list (if any) here */
        if (pack->filenb) {
                for (p = pack->head; p->filetype < 0; p = p->next);
                pack->fhead = p;
        }
        
        return;
}


/* All the following function should return an INCREASING order,
 * unless specified otherwise. */

static inline short inf_by_rand(const mu_ent *const restrict first, const mu_ent *const restrict second)
{
        return (rand()-(RAND_MAX/2));   /* if rand returns long, the implicit cast will add entropy ;o) */
}

static inline short inf_by_track(const mu_ent *const restrict first, const mu_ent *const restrict second)
{
        return (first->track - second->track);
}

static inline short inf_by_posn(const mu_ent *const restrict first, const mu_ent *const restrict second)
{
        return (first->posn - second->posn);
}

static inline short inf_by_date(const mu_ent *const restrict first, const mu_ent *const restrict second)
{
        return (first->date - second->date);
}

static inline short inf_by_length(const mu_ent *const restrict first, const mu_ent *const restrict second)
{
        return (first->length - second->length);
}

static inline short inf_by_bitrate(const mu_ent *const restrict first, const mu_ent *const restrict second)
{
        /* bitrate is long */
        return ((first->bitrate <= second->bitrate) ? -1 : 1);
}

static inline short inf_by_freq(const mu_ent *const restrict first, const mu_ent *const restrict second)
{
        return (first->freq - second->freq);
}

static inline short inf_by_size(const mu_ent *const restrict first, const mu_ent *const restrict second)
{
        /* size is long */
        return ((first->size <= second->size) ? -1 : 1);
}

static inline short inf_by_mtime(const mu_ent *const restrict first, const mu_ent *const restrict second)
{
        /* mtime is long */
        return ((first->mtime < second->mtime) ? 1 : -1);
}

static inline short inf_by_artist(const mu_ent *const restrict first, const mu_ent *const restrict second)
{
        register short ret = -1;
        if (likely(first->artist))
                ret &= 0x1;
        if (likely(second->artist))
                ret &= ~0x1;
        return (likely(!ret) ? strcasecmp(first->artist, second->artist) : ~ret);
}

static inline short inf_by_album(const mu_ent *const restrict first, const mu_ent *const restrict second)
{
        register short ret = -1;
        if (likely(first->album))
                ret &= 0x1;
        if (likely(second->album))
                ret &= ~0x1;
        return (likely(!ret) ? strcasecmp(first->album, second->album) : ~ret);
}

/* title always exists now */
static inline short inf_by_title(const mu_ent *const restrict first, const mu_ent *const restrict second)
{
        return strcasecmp(first->title, second->title);
}

static inline short inf_by_filetype(const mu_ent *const restrict first, const mu_ent *const restrict second)
{
        return (first->filetype - second->filetype);
}

static inline short inf_by_file(const mu_ent *const restrict first, const mu_ent *const restrict second)
{
        return strcasecmp(first->file, second->file);
}

static inline short inf_by_uri(const mu_ent *const restrict first, const mu_ent *const restrict second)
{
        return strcmp(first->uri, second->uri);
}

static inline short inf_by_genre(const mu_ent *const restrict first, const mu_ent *const restrict second)
{
        register short ret = -1;
        if (likely(first->genre))
                ret &= 0x1;
        if (likely(second->genre))
                ret &= ~0x1;
        return (likely(!ret) ? strcasecmp(first->genre, second->genre) : ~ret);
}

/* XXX celle la elle meriterait un ptit commentaire... */
static inline short inf_by_dir(const mu_ent *const restrict first, const mu_ent *const restrict second)
{
        const char *const restrict one = first->uri;
        const char *const restrict two = second->uri;
        unsigned char cone = 'a', ctwo = 'a';
        register unsigned short i;

        for (i=0; one[i] == two[i]; i++)
                continue;

        for (; ((cone!='\0') && (cone!='/')) || ((ctwo!='\0') && (ctwo!='/')); i++) {
                if (((one[i]=='\0')||(one[i]=='/')) && (cone!='\0') && (cone!='/'))
                        cone = one[i];

                if (((two[i]=='\0')||(two[i]=='/')) && (ctwo!='\0') && (ctwo!='/'))
                        ctwo = two[i];
        }

        return ((short)cone - (short)ctwo);
}

static inline short inf_global(const mu_ent *const first, const mu_ent *const second, const unsigned char *const restrict order)
{
        short result;
        register unsigned short i;
        
        if (unlikely(first == second))
                return 0;

        if (first->filetype < 0) {
                if (second->filetype < 0)
                        return inf_by_title(first, second);
                else
                        return -1;
        } else if (second->filetype < 0)
                return 1;

        /* This loop will return the first element of comparison between two
         * entries. eg. if the user set "title artist" as MusicSortOrder, then
         * this function will first compare titles. If they differ it will return
         * the difference. Otherwise, it will compare artists and return the
         * difference. */
        /* XXX NOTE: We assert here that order[i] will never trigger an out of
         * bound access */
        for (i = 0; sort_order_functions[order[i]]; i++) {
                if ((result = (sort_order_functions[order[i]](first, second))))
                        return result;
        }
        return 0;
}