From e73aadd97b8d6ba6934783823ae533038cfdbed1 Mon Sep 17 00:00:00 2001 From: reimar Date: Sun, 2 Jan 2005 14:29:43 +0000 Subject: Use libc qsort to sort ODML index. Based on patch by phillip at phdcam dot com git-svn-id: svn://svn.mplayerhq.hu/mplayer/trunk@14298 b3059339-0415-0410-9bf9-f77b7e298cf2 --- libmpdemux/aviheader.c | 45 +++++---------------------------------------- 1 file changed, 5 insertions(+), 40 deletions(-) diff --git a/libmpdemux/aviheader.c b/libmpdemux/aviheader.c index 32e48b3405..32222faa24 100644 --- a/libmpdemux/aviheader.c +++ b/libmpdemux/aviheader.c @@ -44,45 +44,10 @@ static int odml_get_vstream_id(int id, unsigned char res[]) return 0; } -/** - * Simple quicksort for AVIINDEXENTRYs - * To avoid too deep recursion, the bigger part is handled iteratively, - * thus limiting recursion to log2(n) levels. - * The pivot element is randomized to "even out" otherwise extreme cases. - */ -static void avi_idx_quicksort(AVIINDEXENTRY *idx, int from, int to) -{ - AVIINDEXENTRY temp; - int lo; - int hi; - off_t pivot_ofs; - int pivot_idx; - while (from < to) { - pivot_idx = from; - pivot_idx += rand() % (to - from + 1); - pivot_ofs = AVI_IDX_OFFSET(&idx[pivot_idx]); - lo = to; - hi = from; - do { - while(pivot_ofs < AVI_IDX_OFFSET(&idx[lo])) lo--; - while(pivot_ofs > AVI_IDX_OFFSET(&idx[hi])) hi++; - if(hi <= lo) { - if (hi != lo) { - memcpy(&temp, &idx[lo], sizeof(temp)); - memcpy(&idx[lo], &idx[hi], sizeof(temp)); - memcpy(&idx[hi], &temp, sizeof(temp)); - } - lo--; hi++; - } - } while (lo >= hi); - if ((lo - from) < (to - hi)) { - avi_idx_quicksort(idx, from, lo); - from = hi; - } else { - avi_idx_quicksort(idx, hi, to); - to = lo; - } - } +int avi_idx_cmp(const void *elem1,const void *elem2) { + register off_t a = AVI_IDX_OFFSET((AVIINDEXENTRY *)elem1); + register off_t b = AVI_IDX_OFFSET((AVIINDEXENTRY *)elem2); + return (a > b) - (b > a); } void read_avi_header(demuxer_t *demuxer,int index_mode){ @@ -535,7 +500,7 @@ if (priv->isodml && (index_mode==-1 || index_mode==0)) { } } } - avi_idx_quicksort(priv->idx, 0, priv->idx_size-1); + qsort(priv->idx, priv->idx_size, sizeof(AVIINDEXENTRY), avi_idx_cmp); /* Hack to work around a "wrong" index in some divx odml files -- cgit v1.2.3